Tvorba efektívnych algoritmov

Prednášky: štvrtok 9:50
Cvičenia: štvrtok 8:10 – cvičenia pre pokročilých; DAV+BIN
                 štvrtok 15:40 – INF

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 28.5. alebo 1.6.
Termín 18.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.

Midterm

Výsledky midtermu (Výsledky by mali byť finálne. V prípade otázok mi napíšte.)

Zadanie midtermu
Poznámky k riešeniam midtermu (Spísali sme najčastejšie chyby v midterm písomkách ako aj odporúčania, na čo dávať dôraz pri písaní riešení. Užitočné aj pri príprave na záverečný test.)

V štvrtok 9.4. bude namiesto prednášky prebiehať povinný midterm. Midterm bude mať písomnú formu, dostanete zadania niekoľkých úloch a vašou úlohou bude popísať riešenie týchto úloh.
Čo treba vedieť a čo môžete očakávať: Ukážková písomka
Toto je ukážková písomka. Pozor, toto je ukážka záverečnej písomky, obsahuje teda témy, ktoré ste ešte nemali prebrané alebo odcvičené. Má slúžiť len ako náhľad do toho, ako to zhruba môže vyzerať.
Pokyny k midtermu budú odlišné! (napr. midterm bude close-book bez možnosti použitia akýchkoľvek materiálov)
A taktiež, ukážkové úlohy sú o niečo ťažšie ako úlohy, ktoré by sa mali objaviť na midterme/písomke.

Bodovanie

Počas semestra bude zverejnených 7 programátorských domácich úloh. Za každú vyriešenú úlohu získate 4 body.

Počas semestra sa uskutoční papierový midterm. Bude sa konať v štvrtok 9. apríla počas prednášky. Získať zaň budete môcť 35 bodov.
Počas skúškového bude papierová písomka, za ktorú sa bude dať získať 60 bodov.

Na úspešné absolvovanie predmetu potrebujete získať aspoň 20 bodov z domácich úloh a aspoň 15 bodov zo záverečnej 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 https://algo.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 22.3.2026)
Domáca úloha 2: (PDF) (odovzdať do utorku 7.4.2026)
Domáca úloha 3: (PDF) (odovzdať do nedele 26.4.2026)
Domáca úloha 4: (PDF) (odovzdať do nedele 3.5.2026)
Domáca úloha 5: (PDF) (odovzdať do nedele 17.5.2026)
Domáca úloha 6: (PDF) (odovzdať do nedele 24.5.2026)
Domáca úloha 7: (PDF) (odovzdať do nedele 28.6.2026)

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
Geometria: 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.
Pokročilé využitie DFS: PDF
Lowest common ancestor (LCA) a Range minimum query (RMQ): článok o LCA
Párenie v bipartitných grafoch: 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