1-AIN-105: Efektívne algoritmy a dátové štruktúry
Zima 2025
Prednášky a poznámky

Kontakt | Info | Domáce úlohy | Písomky a skúšky | Prednášky a poznámky | Predchádzajúce semestre

Na tejto stránke nájdete orientačný rozvrh semestra. Tento rozvrh bude aktualizovaný vždy po skončení príslušného týždňa prednášok, takisto budú pribúdať študijné materiály.
 
Literatúra:

 
Týždeň 22.09.2025-26.09.2025
P1: Administratíva. Úvod do zložitosti. Analýza triediacich algoritmov. Asymptotická analýza, časová zložitosť / najhorší prípad, elementárne operácie
P2: notácie O, Omega, Theta. Prioritné fronty. Pojem abstraktný dátový typ. Triedenie s prioritnými frontami. Halda.
C: Určovanie časovej zložitosti kódov, porovnávanie funkcii, netriviálne operácie
Literatúra: CLSR3:1.1-1.2,2.2-2.3,3.1; CLRS3:6
Slajdy:Poznámky a ďalšie materiály:
Admin: [ PDF, 144 Kb ]
Asymptotická analýza (prednáška): [ PDF, 154 Kb ]
Prioritné fronty (prednáška): [ PDF, 84 Kb ]
Výpočtová zložitosť (cvičenia): [ PDF, 69 Kb ]
 Časová zložitosť, O notácia (video): [ linka ]
Zložitosť, prioritná fronta, halda (video): [ linka ]
Asymptotická analýza (poznámky): [ PDF, 183 Kb ]
Asymptotic Cheat Sheet: [ PDF, 56 Kb ]
Theoretical Computer Science Cheat Sheet: [ PDF, 164 Kb ]

Týždeň 29.09.2025-03.10.2025
P1: Lineárna konštrukcia haldy. HeapSort. Pokročilé triedenia. Randomizovaný QuickSort.
P2: Stredná hodnota. Očakávaná časová zložitosť. Analýza časovej zložitosti QuickSortu. Dolný odhad časovej zložitosti triedenia pomocou porovnaní.
C: Princíp fungovania haldy, modifikácia haldy, abstraktný dátový typ prioritná fronta
Literatúra: CLRS3:6.3-6.4; CLRS3:7
Slajdy:Poznámky a ďalšie materiály:
HeapSort (prednáška): [ PDF, 92 Kb ]
QuickSort (prednáška): [ PDF, 44 Kb ]
Haldy (cvičenia): [ PDF, 538 Kb ]
 HeapSort (video): [ linka ]
QuickSort a analýza (video): [ linka ]
Prioritné fronty (poznámky): [ PDF, 172 Kb ]

Týždeň 06.10.2025-10.10.2025
P1: Lineárne triedenia (counting sort, radix sort). Slovníky. Implementácie pomocou polí a zoznamov. Binárne vyhľadávanie. Hašovacie tabuľky: hašovanie s otvorenou adresáciou
P2: Klasické hašovacie funkcie, univerzálne hašovacie funkcie, hašovanie s uzavretou adresáciou. Hašovacie tabuľky s dynamickou veľkosťou. Amortizovaná analýza časovej zložitosti.
C: pravdepodobnosti, aplikácie triedenia
Literatúra: CLRS3:8.1-8.3; CLRS3:11
Slajdy:Poznámky a ďalšie materiály:
Lineárne triedenia (prednáška): [ PDF, 98 Kb ]
Hašovanie (prednáška): [ PDF, 60 Kb ]
Triedenie (cvičenia): [ PDF, 87 Kb ]
 Lineárne triedenia, hašovanie (video): [ linka ]
Hašovanie (pokr.), amortizovaná zložitosť (video): [ linka ]
Pokročilé triedenia (poznámky): [ PDF, 193 Kb ]

Týždeň 13.10.2025-17.10.2025
P1: Binárne vyhľadávacie stromy. AVL stromy (definície, výška, vyvažovanie)
P2: Scapegoat stromy. Slovníky pre reťazce (trie, PATRICIA - komprimovaný trie).
C: Príklady na hašovanie a binárne vyhľadávacie stromy
Literatúra: CLRS3:11; CLRS3:17.4; CLRS3: 12,13.2
Slajdy:Poznámky a ďalšie materiály:
Binárne vyhľadávacie stromy (prednáška): [ PDF, 48 Kb ]
Scapegoat stromy (prednáška): [ PDF, 154 Kb ]
Hašovanie, binárne vyhľadávacie stromy (cvičenie): [ PDF, 43 Kb ]
 Binárne vyhľadávacie stromy (video): [ linka ]
Scapegoat stromy (video): [ linka ]
Slovníky (poznámky): [ PDF, 258 Kb ]

Týždeň 20.10.2025-24.10.2025
P1: Vyhľadávanie v texte. Rabin-Karpov algoritmus. Vyhľadávanie pomocou konečných automatov.
P2: Knuth-Morris-Prattov algoritmus. Sufixové stromy
C: Vzorové riešenia DÚ1. Vyhľadávanie v texte.
Literatúra: CLRS3:32
Slajdy:Poznámky a ďalšie materiály:
Vyhľadávanie v texte (prednáška): [ PDF, 153 Kb ]
Vyhľadávanie v texte (cvičenie): [ PDF, 31 Kb ]
 Vyhľadávanie v texte (video): [ linka ]
KMP algoritmus, sufixové stromy (video): [ linka ]
Vyhľadávanie v texte (poznámky): [ PDF, 205 Kb ]

Týždeň 27.10.2025-31.10.2025
P1: Greedy algoritmy. Problém výberu aktivít. Dokazovanie správnosti greedy algoritmov.
P2: Huffmanovo kódovanie.
C: Greedy algoritmy.
Literatúra: BB:6; CLRS3:16.1; CLRS3:16.2; CLRS3:16.3
Slajdy:Poznámky a ďalšie materiály:
Výber aktivít (prednáška): [ PDF, 106 Kb ]
Huffmanovo kódovanie (prednáška): [ PDF, 96 Kb ]
Greedy algoritmy (cvičenie): [ PDF, 33 Kb ]
 Výber aktivít, Huffman (video): [ linka ]
Greedy algoritmy (poznámky): [ PDF, 221 Kb ]

Týždeň 03.11.2025-07.11.2025
P1: Dynamické programovanie. Rozmienanie peňazí. Problém batohu.
P2: Najdlhšia spoločná podpostupnosť. Najkratšia triangulácia.
C: Príklady na dynamické programovanie
Literatúra: BB:8.2,8.4;CLRS:15.3,15.4
Slajdy:Poznámky a ďalšie materiály:
Rozmieňanie peňazí, problém batohu (slajdy): [ PDF, 93 Kb ]
Najdlhšia spoločná podpostupnosť, najkratšia triangulácia (slajdy): [ PDF, 111 Kb ]
Dynamické programovanie (cvičenie): [ PDF, 27 Kb ]
 Dynamické programovanie 1 (video): [ linka ]
Dynamické programovanie 2 (video): [ linka ]
Dynamické programovanie (poznámky): [ PDF, 199 Kb ]

Týždeň 10.11.2025-14.11.2025
P1: Rozdeľuj a panuj. Násobenie veľkých čísel. Master theorem.
P2: Najbližší pár bodov.
C: Memoizácia, riešenia DÚ2, príprava na midterm
Literatúra: BB:4.7,7.1-7.4; CLRS3:4.4-4.6; CLRS3:33.4
Slajdy:Poznámky a ďalšie materiály:
Master theorem (prednáška): [ PDF, 166 Kb ]
Najbližší pár bodov (prednáška): [ PDF, 123 Kb ]
Dynamické programovanie / memoizácia (cvičenie): [ PDF, 38 Kb ]
 Násobenie čísel, Master theorem (video): [ linka ]
Master theorem - dôkaz, najbližší pár bodov (video): [ linka ]
Rozdeľuj a panuj (poznámky): [ PDF, 287 Kb ]

Týždeň 17.11.2025-21.11.2025
P1: Základné grafové algoritmy. Grafová terminológia, reprezentácia grafov, BFS, DFS.
P2: vzorové riešenia midtermu
C: rozdeľuj a panuj, rekurencie
Literatúra: CLRS3:22.1-22.3
Slajdy:Poznámky a ďalšie materiály:
Úvod do grafov (prednáška): [ PDF, 188 Kb ]
Rekurencie a rozdeľuj a panuj (cvičenie): [ PDF, 37 Kb ]
 Reprezentácia grafov, prehľadávanie (video): [ linka ]

Týždeň 24.11.2025-28.11.2025
P: Hľadanie najkratších ciest: Floyd-Warshallow algoritmus, Dijkstrov algoritmus
druhá prednáška a cvičenia odpadnú
Literatúra: CLRS3:25.2; CLRS3:24.3
Slajdy:Poznámky a ďalšie materiály:
Najkratšie cesty (slajdy): [ PDF, 59 Kb ]
 Najkratšie cesty - Floyd-Warshall, Dijkstra (video): [ linka ]

Týždeň 01.12.2025-05.12.2025
P1: Najlacnejšie kostry: Kruskalov algoritmus, ADT disjunktné množiny / UNION-FINDSET dátová štruktúra
P2: Primov algoritmus, grafové algoritmy ako black box riešenia
C: Grafové algoritmy.
Literatúra: CLRS3:23;CLRS3:21
Slajdy:Poznámky a ďalšie materiály:
Kruskalov algoritmus, UNION/FIND-SET (prednáška): [ PDF, 63 Kb ]
Primov algoritmus, blackbox riešenia (prednáška): [ PDF, 56 Kb ]
Grafové algoritmy (cvičenie): [ PDF, 122 Kb ]
 Najlacnejšie kostry, Kruskalov algoritmus (video): [ linka ]
Primov algoritmus, grafové algoritmy ako blackbox (video): [ linka ]
Grafy (poznámky): [ PDF, 291 Kb ]

Týždeň 08.12.2025-12.12.2025
P1: NP-ťažké a NP-úplné problémy. Problém obchodného cestujúceho. Rozhodovacie vs. optimalizačné problémy. Nedeterministické výpočty. Trieda P a trieda NP. Problémy SAT, 3-SAT, VC, CLIQUE, HAM a nedeterministické polynomiálne algoritmy na ich riešenie.
P2: Polynomiálne redukcie. Ukážky (HAM na TSP, 3-SAT na VC).
C: Najlacnejšie kostry.
Literatúra: CLRS3:23;CLRS3:34 alebo BB:12.5
Slajdy:Poznámky a ďalšie materiály:
Nedeterministické výpočty: [ PDF, 305 Kb ]
Kostry (cvičenie): [ PDF, 27 Kb ]
 Triedy P a NP (video): [ linka ]
NP ťažké problémy (poznámky): [ PDF, 239 Kb ]

Týždeň 15.12.2025-19.12.2025
P1: Cookova veta (formulácia). NP-ťažké a NP-úplné problémy. Zhrnutie semestra
C: nedeterminizmus, rozhodovacie problémy, triedy P a NP
Slajdy:Poznámky a ďalšie materiály:
Zhrnutie semestra: [ PDF, 235 Kb ]
Triedy P a NP (cvičenie): [ PDF, 34 Kb ]
 Cookova veta, dokazovanie NP ťažkosti (video): [ linka ]

Maintained by 1-AIN-105 personnel