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
Midterm
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ť:
- Úlohu podobnú úlohám z cvík – táto úloha bude iba z tém, ktoré sa cvičili na prvých 2 cvikách
- Popis konkrétneho algoritmu z prednášky – z tém odprednášaných do midtermu (napr. "Popíšte ako funguje Kruskalov algoritmus")
- Práca s algoritmom alebo obsahom z prednášok – napr. úloha "Ako upraviť Kruskalov algoritmus pre grafy so zápornými hranami?" (viď. Cvičenie 3)
- Možnosť získavať čiastočné body za čiastočné alebo menej efektívne riešenia.
- Midterm bude "close-book". Pri riešení teda nebudete môcť používať žiadne pripravené materiály.
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:
- 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 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)
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.
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
- 19. február: hľadanie najkratších ciest v grafe – Dijkstrov algoritmus; Floyd-Warshallov algoritmus
- 26. február: intervalové stromy
- 5. marec: Kruskalov algoritmus na hľadanie najlacnejších kostier v grafe; Union-find
- 12. marec: Modulárna matematika (prednáša Jozef Rajník)
- 19. marec: Výpočtová geometria (prednáša Jozef Rajník)
- 26. marec: vyhľadávanie v texte, KMP, Aho-Corasik
- 2. apríl: výučba neprebieha
- 9. apríl: Midterm na prednáške
- 16. apríl: Dynamické programovanie
Kontakt
Meno: Michal Anderle
Email: michal.anderle@fmph.uniba.sk