news rss feed
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.