Tvorba efektívnych algoritmov

Prednášky: streda 9:00
Cvičenia: štvrtok 8:10

Bodovanie

Počas semestra bude zverejnených 8 programátorských domácich úloh. V 7 z nich bude vašou úlohou odovzdať na testovač odladený program, ktorý dá správnu odpoveď na všetky testy. V jednej úlohe budete odovzdávať slovný popis riešenia, ktorý bude hodnotený na základe správnosti a efektívnosti.
Za každú vyriešenú úlohu získate 5 bodov, v prípade teoretickej úlohy je možné získať čiastkové body.

Počas skúškového bude písomka, za ktorú sa dá získať 80 bodov.

Na úspešné absolvovanie predmetu potrebujete získať aspoň 23 bodov z domácich úloh a aspoň 20 bodov z písomky.
Po splnení týchto podmienok sa vaša výsledná známka určí podľa nasledovnej stupnice:

známka A: aspoň 90 bodov
známka B: aspoň 80 bodov
známka C: aspoň 70 bodov
známka D: aspoň 60 bodov
známka E: aspoň 50 bodov

Opravné termíny písomky môžu prebiehať formou ústnej skúšky. Takisto je možné si ústnou skúškou vylepšiť už získanú známku.

Domáce úlohy

V priebehu semestra bude zverejnených 8 programátorských domácich úloh. Domáce úlohy sa odovzdávajú na stránke foja.dcs.fmph.uniba.sk/eval/.

Pri riešení sa silne odporúča používať C++. Python môže prechádzať tiež, limity však budú určite tesnejšie.
Pripomínam, že za riešenie dostanete body iba ak vyrieši všetky vstupné sady.

Ak dostávate Time limited exceeded je možné, že pracujete zle so štandardným vstupom a výstupom. Prečítajte si tento dokument (PDF), v ktorom sú dobré postupy na prácu s IO pre C++, Javu aj Python.

Domáca úloha 1: (PDF) (odovzdať do nedele 23.3.2025) (úloha je riešiteľná len v C++/Java)
Domáca úloha 2: (PDF) (odovzdať do nedele 6.4.2025) (úloha je riešiteľná len v C++/Java)
Domáca úloha 3: (PDF) (odovzdať do nedele 13.4.2025) (úloha je riešiteľná len v C++/Java)
Domáca úloha 4: (PDF) (odovzdať do nedele 20.4.2025) (úloha je riešiteľná len v C++/Java)

Materiály

Pôvodné skriptá k predmetu: PDF.
Dijkstrov algoritmus implementácia s haldou
Intervalové stromy: článok o intervalových stromoch a nadväzujúci článok o lazy propagácii. Články by mali pokrývať obsah prednášky, ktorý bude aj na skúške.
Modulárna matematika: PDF
Pokročilé využitie DFS: PDF
Vyhľadávanie v texte: článok o KMP algoritme. Na skúšku treba vedieť do detailov vysvetliť fungovanie algoritmu KMP na vyhľadávanie vzorky v texte a takisto algoritmu Aho-Corasik na hľadanie viacerých vzoriek.

Nahrané prednášky:

Prednášky z roku 2020. Môžu sa mierne líšiť od toho, čo prednášam naživo, mali by však pokrývať zhruba rovnaké témy a mali by byť vhodným materiálom na učenie sa.

Cvičenia

Cvičenia č.1 (zadania) (riešenia) – Dijkstrov algoritmus
Cvičenia č.2 (zadania) (riešenia) – Intervalové stromy
Cvičenia č.3 (zadania) (riešenia) – Union-find, kostry
Cvičenia č.4 (zadania) – Vyhľadávanie v texte; Modulárna matematika

Prednášky

19. február: hľadanie najkratších ciest v grafe – Dijkstrov algoritmus; Floyd-Warshallov algoritmus
25. február: intervalové stromy
5. marec: Kruskalov algoritmus na hľadanie najlacnejších kostier v grafe; Union-find
12. marec: Modulárna matematika
19. marec: pokročilé využitie DFS – hľadanie mostov a artikulácií
26. marec: 2-SAT; metóda rozdeľuj a panuj
2. apríl: vyhľadávanie v texte, KMP a Aho-Corasik

Kontakt

Meno: Michal Anderle
Email: michal.anderle@fmph.uniba.sk