Pokročilá algoritmizace

Garant předmětu:

Pavel Smrčka

Přednášející:

Jan Broulím, Pavel Smrčka

Cvičící:

Jan Broulím, Pavel Smrčka

Předmět zajišťuje:

katedra informačních a komunikačních technologií v lékařství

Anotace:

Cíl předmětu je seznámit studenty s problematikou algoritmizace a základů teoretické informatiky. Studenti se seznámí s metodami návrhů algoritmů, určení jejich složitosti, s grafovými a optimalizačními algoritmy. V předmětu budou popsány běžné využívané datové struktury a způsoby jejich implementace. Přednášky budou také věnované formálním jazykům a automatům. Důležitou součástí cvičení je samostatná implementace datových typů a algoritmů přednášky.

Požadavky:

Podmínky zápočtu jsou absolvování čtyř praktických testů s celkovým ziskem alespoň 50 % bodů a odevzdání zápočtové úlohy. Zkouška má písemnou část, která se skládá z převážně teoretických otázek s následním ústním dozkoušení v rozsahu odpřednášené a odcvičené látky.

Požadavky na studenty: Povinná účast na cvičeních (max. 2 absence).

Osnova přednášek:

1.Techniky algoritmizace - metoda top down, bottom-up, rozděl a panuj, žravý algoritmus, rekurze, dynamické programování. Výpočetní modely.

2.Abstraktní datové typy; agregace a systematizace znalostí. Zásobník, fronta, seznam atd. a jejich efektivní implementace. Zopakování základních metod řazení a vyhledávání.

3.Složitost algoritmů - časová a paměťová náročnost, asymptotická časová složitost, třídy složitosti.

4.Grafy. Základní pojmy, možnosti reprezentace pomocí datových struktur. Minimální kostra grafu, minimální cesta v grafu.

5.Algoritmy průchodů grafem - prohledávání do hloubky a do šířky, heuristické metody prohledávání.

6.Binární vyhledávací stromy. Základní pojmy a operace, vyhledávání, vkládání, rušení vrcholů, průchody stromem.

7.Vyvážené a vícecestné stromy. AVL-stromy, red-black stromy. B-stromy. Haldy.

8.Hešovací tabulka, řešení kolizí - zřetězení, otevřená adresace, perfektní hešování. Kešování. Asociativní pole.

9.Dynamická alokace paměti. Pointery, operátory reference, dereference, alokování a dealokování paměti. Fragmentace paměti.

10.Garbage collector, principy a srovnání základních algoritmů - reference counting algoritmy, tracing algoritmy.

11.Formální jazyky - základní pojmy (abeceda, slovo, jazyk). Operace na jazycích. Druhy gramatik. Konečné automaty. Deterministický a nedeterministický konečný automat. Turingův stroj.

12.Algoritmy numerické matematiky ? přehled a příklady aplikací.

13.Algoritmy optimalizace. Lineární programování. Formulace problému, přehled metod. Grafická metoda řešení, Simplexová metoda.

14.Dynamické programování. Bellmanův princip optimality. Souvislost s rekurzí, příklady užití, Floydův-Warshallův algoritmus.

Osnova cvičení:

Důležitou součástí cvičení je samostatná implementace datových typů a algoritmů přednášky.

Cíle studia:

Cíl předmětu je seznámit studenty s problematikou algoritmizace a základů teoretické informatiky. Studenti se seznámí s metodami návrhů algoritmů, určení jejich složitosti, s grafovými a optimalizačními algoritmy.

Studijní materiály:

Povinná literatura:

[1] SEDGEWICK, Robert. Algoritmy v C. Praha: SoftPress, 2003. ISBN 80-86497-56-9.

[2] WRÓBLEWSKI Piotr.: Algoritmy. Datové struktury a programovací techniky, Computer Press, Praha, druhé vydání 2015, ISBN 80-251-0343-9

Doporučená literatura:

[3] SKIENA, Steven S. The algorithm design manual. 2nd ed. London: Springer, c2008. ISBN 978-1-84800-069-8.

Poznámka:

Rozvrh na zimní semestr 2023/2024:

	06:00–08:0008:00–10:0010:00–12:0012:00–14:0014:00–16:0016:00–18:0018:00–20:0020:00–22:0022:00–24:00
Po
Út
St	místnost AL:101 Broulím J. 10:00–12:50 (přednášková par. 1) Praha 2 - Albertov Albertov - učebnamístnost AL:101 Broulím J. Smrčka P. 13:00–16:50 (přednášková par. 1 paralelka 1) Praha 2 - Albertov Albertov - učebna
Čt
Pá

Rozvrh na letní semestr 2023/2024:

Rozvrh není připraven

Předmět je součástí následujících studijních plánů:

• Navazující magisterská studijní specializace Asistivní technologie (povinný předmět)
• Navazující magisterská studijní specializace Softwarové technologie (povinný předmět)
• Navazující magisterská studijní specializace Nanotechnologie (povinný předmět)