Tvorba efektívnych algoritmov

Prednášky: streda 14:50
Cvičenia: štvrtok 8:10

Prednáška v stredu 15.5. bude v miestnosti F1-328.

Termíny písomiek: primárny termín 28.5. (ak môžete vtedy, tak vtedy); druhý termín 3.6.; opravný termín 10.6. Všetky skúšky budú prebiehať online

Bodovanie

Počas semestra bude zverejnených aspoň 7 domácich úloh. Body za úlohu dostanete iba keď ju plne vyriešite, prejde teda cez všetky testy. Za každú vyriešenú úlohu môžete dostať 10 bodov. Najväčší možný počet bodov, ktoré môžete získať za úlohy počas semestra je 80, na absolvovanie predmetu musíte za úlohy získať aspoň 50 bodov.
Počas skúškového bude písomka, za ktorú sa dá získať maximálne 80 bodov. Na absolvovanie predmetu musíte z písomky získať aspoň 20 bodov.
Opravné termíny písomky môžu prebiehať formou ústnej skúšky. Takisto je možné ústnou skúškou vylepšiť už získanú známku.
Stupnica známok je nasledovná:

Domáce úlohy

V priebehu semestra bude zverejnených aspoň 7 programátorských domácich úloh. Na úspešné absolvovanie tohto predmetu je potrebné vyriešiť aspoň 5 z nich, každú do stanoveného termínu.
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. Úlohy, ktoré nebudú riešiteľné v Pythone budú označené.
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 24.3.2024) (úloha je riešiteľná len v C++/Java) – riešenie
Domáca úloha 2: (PDF) (odovzdať do nedele 31.3.2024) (úloha je riešiteľná len v C++/Java)
Domáca úloha 3: (PDF) (odovzdať do nedele 14.4.2024) (úloha je riešiteľná aj v Pythone)
Domáca úloha 4: (PDF) (odovzdať do nedele 28.4.2024)
Domáca úloha 5 je špecifická, keďže obsahuje praktickú aj teoretickú časť. Pozorne si preto prečítajte pokyny v zadaní. Bodovanie predmetu bolo tiež upravené aby reflektovalo túto úlohu (pozitívne pre vás).
Kombinovaná domáca úloha 5: (PDF) (odovzdať do stredy 8.5.2024)
Domáca úloha 6: (PDF) (odovzdať do nedele 19.5.2024)

Písomka

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. Niektoré pokyny sa na reálnej písomke môžu líšiť, budú to skôr drobnosti (napr. bodovanie).

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.

Materiály

Pôvodné skriptá k predmetu: PDF.
Dijkstrov algoritmus implementácia s haldou
Pokročilé využitie DFS: PDF
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.
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.
Modulárna matematika: PDF
Lowest common ancestor (LCA) a Range minimum query (RMQ): článok o LCA
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