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:
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)
Domáca úloha 5: (PDF) (odovzdať do štvrtka 8.5.2025) (úloha je teoretická)

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.
Lowest common ancestor (LCA) a Range minimum query (RMQ): článok o LCA

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

Prednášky

Kontakt

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