Tvorba efektívnych algoritmov

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

Písomka

Prihlasovanie na písomky v AIS. Očakáva sa, že sa každý zúčastní jedného z hlavných termínov 2.6. alebo 10.6.
Termín 20.6. je opravný. V prípade potreby budú ešte v posledný týždeň vypísané ústne skúšky.

Ukážková písomka

Toto je ukážková písomka, kde si môžete pozrieť, čo zhruba môžete očakávať a čo zhruba očakávam ja od vás. Pokyny sa na reálnej písomke budú líšiť – počas písomky budete môcť používať iba papier a pero, žiadne online či offline pomôcky. Odovzdávanie bude takisto iné, keďže budete riešenia spisovať na papier.
Pokúsim sa pred písomkou zverejniť aj platné pokyny.

Pri učení na písomku je dobré mať prehľad o algoritmoch, ktoré sme sa učili, niektoré úlohy na nich budú stavať. Špeciálne dynamické programovanie je niečo, čo by som si pri príprave pozrel. Pomôcť môžu tiež cvikové úlohy. V rámci písomky budem od vás chcieť aj nejaký program – nebude sa však nikde testovať, dokonca ani nemusí byť nutne skompilovateľný. Môžem si však vypýtať implementovať nejakú konkrétnu funkciu. Pseudokód bude tiež akceptovateľný, dôležité budú hlavné myšlienky, ktoré do kódu pretavíte.

Písomka sa bude javiť ako ťažká (aj keď si vždy vravím, že ju spravím ľahšiu), netreba sa báť a odradiť. Je v nej veľa bodov, ktoré sa dajú získať za pomalšie riešenia, čiastočné myšlienky a podobne. Dôležité je pracovať a niečo odovzdať ku každej úlohe.

Pri príprave na písomku sa môžete pozrieť na niektoré z najlepších 10 bodových riešení úlohy 5, pre inšpiráciu ako si predstavujem teoretické riešenia:

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á)
Domáca úloha 6: (PDF) (odovzdať do nedele 18.5.2025) (úloha je riešiteľná len v C++/Java)
Domáca úloha 7: (PDF) (odovzdať do nedele 1.6.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.
Lowest common ancestor (LCA) a Range minimum query (RMQ): článok o LCA
Párenie v bipartitných grafoch: PDF
Geometria: PDF

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