Prerekvizity
Od ľudí, ktorí si tento predmet zapíšu, sa očakáva, že rozumne ovládajú nejaký
programovací jazyk.
Presnejšie, treba v aspoň jednom programovacom jazyku vedieť programovať natoľko,
aby nebol problém zobrať pseudokód (obsahujúci napr. polia, cykly, rekurziu a pod.)
a podľa neho napísať spustiteľný program.
Ciele
Absolvent predmetu by mal získať nasledovné poznatky:
-
Analýza algoritmov. Časová zložitosť.
Daný (rozumne jednoduchý) algoritmus vie absolvent analyzovať, správne určiť jeho
asymptotickú časovú zložitosť a na jej základe odhadnúť, ako dlho by implementácia
takéhoto algoritmu bežala pri spracúvaní vstupných dát konkrétnej veľkosti.
-
Triedenie a vyhľadávanie.
Absolvent vie na základe konkrétnej situácie zvoliť vhodný algoritmus na
triedenie dát, prípadne na vyhľadávanie v nich. Vo svojom obľúbenom
programovacom jazyku pozná knižnice, v ktorých sú tieto algoritmy
implementované, a rozumie tomu, ako dotyčné implementácie fungujú.
-
Abstraktné dátové štruktúry.
Absolvent dokáže vidieť dátovú štruktúru ako dve vrstvy: abstraktnú
dátovú štruktúru (t. j. jej interface, predstavujúce funkčnú špecifikáciu
a prípadné záruky vhodnej časovej zložitosti) a konkrétnu dátovú
štruktúru (t. j. jej implementáciu, konkrétny spôsob organizácie dát).
Vo svojom obľúbenom programovacom jazyku vie, aké dátové štruktúry
má k dispozícii a vie ich používať v programoch.
-
Konkrétne dátové štruktúry.
Absolvent predmetu vie, čo je to zásobník, fronta, spájaný zoznam,
halda, (vyvažovaný) binárny (vyhľadávací) strom a hašovacia tabuľka.
Rozumie princípu ich fungovania a v prípade potreby by ľubovoľnú
z nich vedel naprogramovať.
-
Základné techniky návrhu algoritmov.
Na jednoduchých príkladoch dokáže absolvent použiť základné
techniky návrhu efektívnych algoritmov, ako napr. dynamické
programovanie.
Syllabus
- Potreba efektívnych algoritmov.
- Analýza algoritmov. Meranie veľkosti vstupu. Časová zložitosť ako funkcia veľkosti vstupu.
Asymptotická časová zložitosť. O-notácia.
- Triedenia (heapsort, quicksort, radixsort).
- Abstraktné dátové štruktúry: zásobník, fronta, prioritná fronta, množina, asociatívne pole.
- Konkrétne dátové štruktúry: halda, binárny strom, hašovacia tabuľka. Vyvažované vyhľadávacie stromy.
- Vzťah háld, stromov a triedenia.
- Pažravé algoritmy.
- Základy dynamického programovania.