Algoritmy a programovanie I.

Sylabus predmetu

1. Úvod do algoritmizácie a informatiky. Pojem algoritmu, jeho vlastnosti. Turingov stroj. (História algoritmov, deterministickosť, konečnosť, efektivita. Úvod do teoretického modelu výpočtov – Turingov stroj. Diskusia: Čo je „dobrý“ algoritmus?) 2. Základné riadiace štruktúry algoritmu. Algoritmizácia slovných úloh. (Sekvencia, vetvenie, cyklus. Premena slovného zadania na algoritmus. Pseudokód a štruktúrované riešenia. Cvičenie: algoritmizácia každodenných úkonov.) 3. Tvorba vývojového diagramu. Aplikácia PS Diagram. (Pravidlá kreslenia diagramov. Vizualizácia logiky algoritmu. Použitie nástroja PS Diagram. Praktická úloha: tvorba vývojového diagramu pre jednoduchý problém.) 4. Základy programovania v jazyku Python. Dátové typy, vstup/výstup, podmienky. (Premenné, operátory, vstup od používateľa, vetvenie. Prepojenie medzi algoritmom a kódom. Prvé implementácie v prostredí Python.) 5. Parsovanie vývojových diagramov do jazyka Python. Funkcie a štruktúra programu. (Premena diagramov na kód. Deklarácia a volanie funkcií. Modularizácia programu. Cvičenie: funkčné prepisy algoritmov.) 6. Zložitosť algoritmov. Časová a pamäťová zložitosť. Notácia Big O. (Porovnanie algoritmov podľa efektivity. Odhadovanie zložitosti jednoduchých algoritmov. Vizuálne príklady rastu časovej náročnosti.) 7. Triediace algoritmy I. Bubble sort, Insertion sort. Hash tabuľky a ich význam. (Implementácia základných algoritmov triedenia. Princípy hashovania, využitie v praxi. Porovnanie výkonnosti.) 8. Triediace algoritmy II. Merge sort, Quick sort. Rekurzia v programovaní. (Rekurzívne implementácie, porovnanie s iteratívnymi. Vizualizácia a sledovanie volaní funkcií. Cvičenie: praktické príklady.) 9. Dátové štruktúry – lineárne zoznamy, stromy, haldy, grafy. (Reprezentácia a použitie dátových štruktúr. Vnorené štruktúry, operácie nad nimi. Úvod do objektovo orientovaného prístupu.) 10. Stavový priestor a neinformované algoritmy prehľadávania: BFS a DFS. (Modelovanie problému ako graf. Vyhľadávanie riešenia bez heuristiky. Implementácia prehľadávania v grafe.) 11. Informované algoritmy prehľadávania. Heuristiky, Hill Climbing a varianty. (Použitie heuristickej funkcie. Problémy lokálnych miním. Porovnanie efektivity so slepým prehľadávaním.) 12. Optimalizačné algoritmy A* a jeho modifikácie. (Heuristika a vzdialenosť cieľa. Algoritmus A, admissibility, efektivita. Príklady použitia v hrách a logistike.) 13. Práca s modulmi a knižnicami v jazyku Python. Záverečné opakovanie. (Použitie math, random, itertools, time. Tvorba vlastného modulu. Príprava na záverečný projekt/skúšku.)