Sylaby

Osnova predmetu

Anotácia predmetu

Predmet je zameraný na programovanie v jazyku Python a na praktické pochopenie dátových štruktúr, algoritmov a moderných programovacích prístupov. Študenti si postupne osvoja syntax jazyka, prácu s kolekciami, objektové a funkcionálne programovanie, analýzu zložitosti, základné dátové štruktúry, stromové a grafové štruktúry, dynamické programovanie, spätné prehľadávanie, kompresné algoritmy a asynchrónne aj paralelné spracovanie.

Dôraz je kladený na čitateľný kód, schopnosť vybrať vhodnú dátovú štruktúru alebo algoritmus, pochopenie výkonnostných dôsledkov riešení a praktické ukážky v Pythone.

Prehľad prednášok

Prednáška	Téma	Súbor	Stručné zameranie
01	Úvod do Pythonu	prednasky/01.intro/presentation.md	Syntax, typy, reťazce, súbory, kolekcie, moduly a prostredie
02	Funkcionálne programovanie	prednasky/02.functional/presentation.md	Čisté funkcie, testovanie, lambdy, map/filter/reduce a generátory
03	Objektové programovanie	prednasky/03.object/presentation.md	Triedy, objekty, OOP princípy, návrhové vzory a výnimky
04	Asymptotická zložitosť	prednasky/04.complexity/presentation.md	Big-O, vyhľadávanie, triediace algoritmy a analýza efektívnosti
05	Zásobník, fronta, hash tabuľka, halda a prioritná fronta	prednasky/05.structures/presentation.md	Stack, queue, hash table, heap, priority queue a work queue
06	Stromy	prednasky/06.tree/presentation.md	Základné pojmy, aplikácie stromov, prechádzanie, BST a špeciálne stromy
07	Grafové algoritmy	prednasky/07.graph/presentation.md	Pojmy grafovej teórie, reprezentácie, prehľadávanie, najkratšie cesty a toky
08	Dynamické programovanie a spätné prehľadávanie	prednasky/08.dynamic/presentation.md	Memoizácia, tabulácia, backtracking, CSP a Sudoku
09	Kompresné algoritmy	prednasky/09.compression/presentation.md	RLE, LZ77, LZ78 a LZW
10	Huffmanovo kódovanie	prednasky/10.huffman/presentation.md	Informácia, entropia, prefixové kódy, Huffmanov strom a heapq
11	Asynchrónne programovanie	prednasky/11.async/presentation.md	async, await, event loop, tasky, queue a async web
12	Paralelné programovanie	prednasky/12.parallel/presentation.md	Threading, multiprocessing, GIL, race condition a locky

Cvičenia podľa prednášok

Prednáška	Existujúce cvičenie	Stav a odporúčaný doplnok
01. Úvod do Pythonu	cvicenia/01.intro/item.md	Hotové úvodné cvičenie s prípravou prostredia a analyzátorom frekvencie slov. Doplniť jasný formát odovzdania, napr. solution.py, aby sa dalo jednotne testovať.
02. Funkcionálne programovanie	cvicenia/04.functional/item.md	Vecne patrí k funkcionálnej prednáške: čisté funkcie, map, filter, reduce, closure a testy. Bonus s Pool.map() presunúť alebo explicitne označiť ako prepojenie na paralelizmus.
03. Objektové programovanie	cvicenia/02.class/item.md	Rozpracované OOP cvičenie s triedami MenuItem, Order, Table, Restaurant. Doplniť presné rozhranie tried, ukážkové dáta a automatické testy špeciálnych metód __len__, __iter__ a __add__.
04. Asymptotická zložitosť	cvicenia/04.complexity/item.md, čiastočne cvicenia/logparser/item.md	Nové cvičenie cielene overuje O(n), O(log n) a neefektívne O(n^2) riešenia pomocou automatických testov s počítaním operácií. Log parser ponechať ako rozšírený dátový projekt.
05. Dátové štruktúry	čiastočne cvicenia/logparser/item.md	Log parser precvičí slovníky a agregácie. Navrhované cvičenie: validátor zátvoriek cez zásobník, simulácia fronty požiadaviek, top-k najčastejších prvkov cez hash tabuľku a heapq, s krátkou analýzou zložitosti.
06. Stromy	cvicenia/tree/item.md	Zatiaľ iba náčrt rozhodovacieho stromu. Doplniť testovateľné zadanie: binárny strom výrazov, prechody preorder/inorder/postorder, výpočet výšky a vyhodnotenie výrazu. Bonus môže byť jednoduchý rozhodovací strom s textovou vizualizáciou.
07. Grafové algoritmy	cvicenia/07.graph/item.md, rozšírenie cvicenia/netwok/item.md, čiastočne cvicenia/turtle/item.md	Nové cvičenie cielene pokrýva adjacency list, BFS najkratšiu cestu, DFS dosiahnuteľnosť, komponenty súvislosti a topologické triedenie s automatickými testami. Sieťový/OSM náčrt ponechať ako projektové rozšírenie.
08. Dynamické programovanie a backtracking	cvicenia/03.dynamic/item.md, čiastočne cvicenia/turtle/item.md	Cvičenie N-kráľovien dobre pokrýva backtracking. Chýba samostatná úloha na dynamické programovanie: Fibonacci s memoizáciou, problém batohu alebo edit distance s tabuľkou a rekonštrukciou riešenia.
09. Kompresné algoritmy	cvicenia/08.compression/item.md	RLE kódovanie/dekódovanie priamo nadväzuje na prednášku. Ako bonus doplniť LZ77 alebo LZ78 tokenizáciu na krátkych reťazcoch.
10. Huffmanovo kódovanie	cvicenia/10.huffman/item.md	Nové cvičenie pokrýva početnosti cez Counter, zostavenie Huffmanovho stromu pomocou heapq, prefixové kódy, zakódovanie, dekódovanie a porovnanie počtu bitov s ASCII.
11. Asynchrónne programovanie	cvicenia/05.async/item.md, cvicenia/web/item.md	FastAPI cvičenie dobre pokrýva asyncio.gather() a meranie súbežnosti. Webové cvičenie ponechať ako rozšírenie a doplniť konkrétne endpointy, testy a očakávané JSON odpovede.
12. Paralelné programovanie	cvicenia/12.parallel/item.md, čiastočne cvicenia/04.functional/item.md	Nové cvičenie pokrýva CPU-bound výpočet prvočísel, rozdelenie práce, sekvenčné a paralelné riešenie cez ProcessPoolExecutor a testovateľné použitie paralelného vykonávača. Bonus vo funkcionálnom cvičení ponechať ako prepojenie na čisté funkcie.

Detailná osnova

01. Úvod do Pythonu

Stručný obsah: Prednáška predstavuje jazyk Python, jeho použitie, interpretovaný charakter, základnú syntax, premenné, funkcie, dynamické typovanie a základné údajové typy. Ďalej pokrýva reťazce, indexovanie, slicing, formátovanie, vstup, prácu so súbormi, zoznamy, slovníky, comprehension konštrukcie, moduly, balíčky, pip a virtuálne prostredia.

Kľúčové slovíčka: Python, interpret, syntax, premenná, funkcia, dynamické typovanie, objekt, garbage collector, type hints, konverzia typov, str, slicing, f-string, stdin, súbor, list, dict, list comprehension, dict comprehension, modul, balíček, pip, virtuálne prostredie.

02. Funkcionálne programovanie

Stručný obsah: Prednáška predstavuje funkcionálny štýl programovania v Pythone, výhody čistých funkcií, minimalizáciu zmien stavu a prácu s funkciami ako objektmi. Vysvetľuje testovanie čistých funkcií, lambdy, funkcie vyššieho rádu, map, filter, reduce, list comprehensions, rekurziu, closures, dekorátory a generátory.

Kľúčové slovíčka: funkcionálne programovanie, čistá funkcia, vedľajší efekt, testovanie, assert, pytest, parametrizovaný test, immutability, lambda, funkcia vyššieho rádu, map, filter, reduce, list comprehension, rekurzia, tail recursion, closure, dekorátor, generátor.

03. Objektové programovanie v Pythone

Stručný obsah: Prednáška vysvetľuje základné princípy objektového programovania, objekty, triedy, atribúty, metódy, konštruktory, špeciálne metódy, dedičnosť, polymorfizmus a zapuzdrenie. Obsahuje aj iterátory, generátory, typovanie, výnimky, duck typing, singleton, factory pattern, best practices a prehľad SOLID princípov.

Kľúčové slovíčka: OOP, trieda, objekt, inštancia, atribút, metóda, __init__, dedičnosť, polymorfizmus, zapuzdrenie, abstrakcia, kompozícia, iterátor, generátor, výnimka, duck typing, EAFP, singleton, factory, SOLID.

04. Asymptotická zložitosť

Stručný obsah: Prednáška vysvetľuje, prečo je efektívnosť algoritmov dôležitá, ako sa používa asymptotická zložitosť a notácia Big-O. Obsahuje príklady zložitostí O(1), O(n), O(n²), O(log n), kombinovanú zložitosť, najlepší, priemerný a najhorší prípad, porovnanie rastu funkcií a lineárne aj binárne vyhľadávanie. Druhá časť sa venuje triediacim algoritmom, vstavanému triedeniu v Pythone a abstraktným modelom výpočtu.

Kľúčové slovíčka: Big-O, asymptotická zložitosť, časová zložitosť, pamäťová zložitosť, O(1), O(n), O(n²), O(log n), O(n log n), lineárne vyhľadávanie, binárne vyhľadávanie, množina, bubble sort, selection sort, insertion sort, merge sort, quick sort, Timsort, RAM model, RASP model.

05. Zásobník, fronta, hash tabuľka, halda a prioritná fronta

Stručný obsah: Prednáška vysvetľuje základné dátové štruktúry používané pri ukladaní prvkov, rýchlom vyhľadávaní a plánovaní úloh. Zaoberá sa zásobníkom, frontou, hash tabuľkou, haldou, prioritnou frontou a vzorom work queue, ktorý sa neskôr používa pri asynchrónnom a paralelnom spracovaní.

Kľúčové slovíčka: zásobník, stack, LIFO, fronta, queue, FIFO, hash tabuľka, hash funkcia, kolízia, reťazenie, otvorené adresovanie, load factor, dict, set, priority queue, priorita, halda, heap, heapq, queue.Queue, PriorityQueue, work queue, producer, worker.

06. Stromy

Stručný obsah: Prednáška predstavuje strom ako hierarchickú dátovú štruktúru zloženú z uzlov a hrán. Vysvetľuje základné pojmy, hĺbku, výšku, podstrom, vzťah stromov a grafov a praktické aplikácie stromov. Následne sa venuje binárnym stromom, BST, prechodom preorder/inorder/postorder, prechádzaniu po úrovniach, n-árnym stromom, iteratívnemu prechádzaniu a špecializovaným stromom ako B-stromy, B+-stromy a Red-Black stromy.

Kľúčové slovíčka: strom, uzol, hrana, koreň, rodič, potomok, list, podstrom, hĺbka, výška, úroveň, binárny strom, BST, preorder, inorder, postorder, level-order, queue, zásobník, n-árny strom, B-strom, B+-strom, Red-Black strom.

07. Grafové algoritmy

Stručný obsah: Prednáška slúži ako prehľad pojmov a algoritmov z grafovej teórie. Zahŕňa základné typy grafov, reprezentácie grafov, prehľadávanie BFS a DFS, komponenty súvislosti, topologické poradie, algoritmy najkratších ciest, minimálne kostry, sieťové toky, implementačné nástroje v Pythone a praktické aplikácie grafov.

Kľúčové slovíčka: graf, vrchol, hrana, orientovaný graf, neorientovaný graf, vážený graf, adjacency matrix, adjacency list, edge list, BFS, DFS, Dijkstra, Bellman-Ford, A*, Floyd-Warshall, minimálna kostra, Kruskal, Prim, union-find, maximum flow, Ford-Fulkerson, Edmonds-Karp, residual graph, NetworkX.

08. Dynamické programovanie a spätné prehľadávanie

Stručný obsah: Prednáška uvádza dynamické programovanie ako techniku na riešenie opakujúcich sa podproblémov pomocou memoizácie a tabulácie. Následne prechádza k naivnému prehľadávaniu a spätnému prehľadávaniu, ukazuje prácu s rozhodovacím stromom, prerezávaním, permutáciami, 8 kráľovnami, rozvrhovaním, min-konfliktovou heuristikou a Sudoku.

Kľúčové slovíčka: dynamické programovanie, podproblém, memoizácia, tabulácia, optimálna podštruktúra, prekrývajúce sa podproblémy, Fibonacciho čísla, problém batohu, backtracking, rozhodovací strom, pruning, CSP, 8 kráľovien, Sudoku, MRV heuristika.

09. Kompresné algoritmy v Pythone

Stručný obsah: Prednáška ukazuje praktické implementácie jednoduchých bezstratových kompresných algoritmov. Začína algoritmom Run Length Encoding, pokračuje algoritmami LZ77 a LZ78 a končí bonusovou praktickejšou verziou LZW používanou v rôznych formátoch. Pri každom algoritme sú ukázané kódovanie, dekódovanie a príklad použitia.

Kľúčové slovíčka: kompresia, bezstratová kompresia, RLE, run length encoding, LZ77, sliding window, offset, dĺžka, LZ78, slovník, token, LZW, kódovanie, dekódovanie, redundancia.

10. Kompresia a Huffmanovo kódovanie

Stručný obsah: Prednáška prepája teóriu informácií s kompresiou. Vysvetľuje pravdepodobnosť symbolov, entropiu, kódové slová, stratovú a bezstratovú kompresiu, prefixové kódovanie a princíp Huffmanovho kódovania. Praktická časť používa Counter, výpočet pravdepodobností a entropie, prioritnú frontu cez heapq, tvorbu Huffmanovho stromu, generovanie kódov a porovnanie veľkosti oproti ASCII.

Kľúčové slovíčka: teória informácií, symbol, početnosť, pravdepodobnosť, entropia, kódové slovo, prefixový kód, kompresia, stratová kompresia, bezstratová kompresia, Huffmanovo kódovanie, Huffmanov strom, prioritná fronta, Counter, heapq, kompresný pomer.

11. Asynchrónne programovanie v Pythone

Stručný obsah: Prednáška vysvetľuje, prečo a kedy používať asynchrónne programovanie. Zaoberá sa pojmami async def, coroutine, await, asyncio, event loop, tasky, gather, timeout, cancellation, výnimky, semaphore, async queue, async context manager, async iterátor a async generátor. Ukazuje použitie pri HTTP requestoch, databázach, frameworkoch a rozdiel medzi async, vláknami a paralelizmom.

Kľúčové slovíčka: async, await, coroutine, asyncio, event loop, task, asyncio.gather, create_task, timeout, cancellation, semaphore, async queue, producer-consumer, async context manager, async iterator, async generator, aiohttp, FastAPI, concurrency, parallelism.

12. Paralelné programovanie v Pythone

Stručný obsah: Prednáška sa venuje mechanizmom používaným pri konkurentnom a paralelnom programovaní. Vysvetľuje multithreading, multiprocessing, GIL, race condition, mutex, kritickú sekciu a porovnáva prístupy asyncio, threading a multiprocessing podľa typu úlohy. Obsahuje aj praktické príklady Pool.map a dôvod, prečo sa čisté funkcie dobre paralelizujú.

Kľúčové slovíčka: threading, thread, multiprocessing, process, Pool.map, GIL, race condition, mutex, lock, kritická sekcia, čistá funkcia, I/O-bound, CPU-bound, zdieľaná pamäť, event loop.

Chýbajúce alebo slabšie pokryté témy

Tieto témy by bolo vhodné doplniť ako samostatné prednášky, kratšie bloky alebo praktické cvičenia:

Téma	Odporúčané zaradenie	Dôvod
Práca s dátovými formátmi	po 01.intro	Prakticky dôležité sú JSON, CSV, pathlib a bezpečná práca so súborovými cestami.
Rekurzia ako samostatné precvičenie	po 02.functional, pred 06.tree	Rekurzia je v prednáške funkcionálneho programovania, ale používa sa aj v stromoch, backtrackingu a dynamickom programovaní; oplatí sa pridať krátke samostatné cvičenie.
Rozšírené meranie zložitosti	po 04.complexity	Základné cvičenie už overuje počet operácií automatickými testami; ako rozšírenie je vhodné doplniť meranie času a porovnanie implementácií na rovnakých vstupoch.
Cvičenie na zásobník, frontu, hash tabuľku a haldu	po 05.structures	Existujúce cvičenia tieto štruktúry pokrývajú iba nepriamo; vhodné je jedno kombinované zadanie s stack, queue, dict/set a heapq.
Union-Find / DSU	pred alebo v 07.graph	Potrebné pre Kruskalov algoritmus a prácu s komponentmi grafu.
Serializácia Huffmanovho stromu	po 10.huffman	Základné cvičenie už pokrýva strom, prioritnú frontu, kódovanie a dekódovanie; ako rozšírenie je vhodné doplniť uloženie stromu spolu so zakódovanými dátami.
Benchmark paralelného programovania	po 12.parallel	Základné cvičenie už pokrýva paralelné rozdelenie CPU-bound úlohy; ako rozšírenie je vhodné pridať meranie výkonu na rôznych počtoch workerov a porovnanie s vláknami.
Jednotná štruktúra cvičení	priebežne	Niektoré cvičenia sú hotové, iné sú iba náčrt. Každé zadanie by malo mať cieľ, vstup/výstup alebo API, požiadavky, príklady a automatické testy.
Dokumentácia a štýl kódu	priebežne	Vhodné doplniť PEP 8, pomenovanie premenných, docstringy a čitateľnosť programov.

Príliš zložité alebo voliteľné časti

Nasledujúce časti sú užitočné, ale pre základný priechod kurzom môžu byť príliš náročné. Odporúčané je označiť ich ako bonus, presunúť na koniec prednášky alebo rozdeliť do pokročilého bloku.

Prednáška	Časť	Odporúčanie
02.functional	Tail vs. head recursion	Označiť ako doplnok; v Pythone nie je tail-call optimalizácia bežná, preto môže študentov miasť.
03.object	SOLID princípy, singleton, factory pattern, viacnásobná dedičnosť	Nechať ako rozšírenie po zvládnutí tried, dedičnosti, polymorfizmu a výnimiek.
04.complexity	RAM/RASP abstraktné stroje	Presunúť do bonusovej časti; základom má byť praktická analýza zložitosti a triedenie.
06.tree	B-stromy, B+-stromy, Red-Black stromy	Uviesť najmä motivačne; detailné operácie rotácií a vyvažovania patria do pokročilej časti.
07.graph	Johnsonov algoritmus, sieťové toky, Dinic, Push-Relabel	Pre základnú grafovú prednášku stačia BFS, DFS, Dijkstra, topologické triedenie a MST; zvyšok ako prehľad alebo bonus.
08.dynamic	Min-konfliktová heuristika a komplexnejšie CSP	Zaradiť až po tom, čo študenti ovládajú základný backtracking a prerezávanie.
10.huffman	Entropia a kompletná implementácia Huffmanovho stromu naraz	Rozdeliť na teóriu kódovania a samostatnú implementačnú časť; predpokladom má byť prioritná fronta a strom.
11.async	Vlastná implementácia event loopu cez select	Ponechať ako bonus na konci; pre bežné použitie stačí model asyncio, await, tasky a queue.
11.async	Async databázy, frameworky a architektúra webovej aplikácie	Zredukovať na prehľad, ak kurz nie je zameraný na webový backend.
12.parallel	Súbežné porovnanie async, threading a multiprocessing	Vysvetľovať až po tom, čo študenti samostatne prešli async aj multiprocessing; inak sa pojmy miešajú.