F7PMIPAZ - Pokročilá algoritmizace

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.

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).

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.

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

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.

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.

• 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)