NPRG062 Algoritmizace

školní rok 2024/2025

12 přednášek

1. 10. 2024 - Algoritmy a jejich efektivita

Úvodní informace o obsahu přednášky a studijních materiálech.

Algoritmus - vlastnosti, důkaz správnosti, porovnávání kvality algoritmů.

Příklady: Eukleidův algoritmus, problém stabilních manželství.

8. 10. 2024 – Asymptotická složitost, základní algoritmy s čísly

Časová a prostorová složitost algoritmů.

Asymptotická složitost, notace „velké O, Omega, Theta“.

Složitost algoritmu v nejhorším, nejlepším a průměrném případě.

Složitost problému.

Dělitelnost, rozklad čísla na cifry, ciferný součet.

Prvočísla – test prvočíselnosti, Eratosthenovo síto.

„Dlouhá čísla“ – uložení, operace.

Polynomy – vyhodnocení (Hornerovo schéma), operace.

15. 10. 2024 – Číselné soustavy, vyhledávání a řazení dat

Převody mezi číselnými soustavami.

Rychlé umocňování.

Vyhledávání v poli – sekvenční, pomocí zarážky, binární vyhledávání (půlení intervalů).

Řazení dat v poli – přímé metody (SelectSort, InsertSort, BubbleSort).

Rychlejší třídění – iterativní implementace třídění sléváním (MergeSort).

22. 10. 2024 – Třídicí algoritmy, reprezentace dat

Složitost problému vnitřního třídění.

Třídění s lineární složitostí (CountingSort, BucketSort, RadixSort).

Vnější třídění.

Reprezentace dat v paměti, pole a seznamy.

29. 10. 2024 - Základní datové struktury

Lineární spojový seznam jako alternativa k poli a seznamu.

Slovník a jeho implementace pomocí hešování. Hešovací tabulky, řešení kolizí.

Abstraktní datové typy: zásobník, fronta, halda.

Haldové operace, implementace haldy v poli.

Haldové třídění (HeapSort).

Konstrukce haldy v lineárním čase.

5. 11. 2024 – Děkanský den MFF UK

výuka na fakultě je zrušena

12. 11. 2024 – Rekurze, rekurzivní generování

Další abstraktní datové struktury – prioritní fronta.

Rekurze – princip, příklady, efektivita (kešování mezivýsledků - memoizace).

Rekurzivní generování – algoritmy založené na zkoušení všech možností.

19. 11. 2024 – Binární stromy

Rekurzivní generování – další příklady.

Binární strom – způsoby reprezentace, procházení do hloubky a do šířky.

Binární vyhledávací strom – reprezentace, operace.

Princip vyvažování, dokonale vyvážený strom a výškově vyvážený strom.

26. 11. 2024 - Prohledávání stavového prostoru do hloubky a do šířky

Prohledávání stavového prostoru do hloubky – princip, příklady použití, realizace.

Zrychlení pomocí ořezávání a heuristik.

Prohledávání stavového prostoru do šířky – princip, příklady použití, realizace.

3. 12. 2024 - Algoritmus minimaxu, metoda Rozděl a panuj

Hra s úplnou informací, strom hry, algoritmus minimaxu, alfa-beta prořezávání.

Metoda Rozděl a panuj – princip, příklady použití.

Vyhodnocení aritmetického výrazu.

10. 12. 2024 – QuickSort, QuickSelect, aritmetické výrazy

MergeSort (rekurzivní implementace).

QuickSort, efektivita, možnosti volby pivota, náhrada rekurze.

K-tý nejmenší prvek, QuickSelect.

Reprezentace aritmetického výrazu binárním stromem.

Notace aritmetického výrazu (infix, prefix, postfix) – vyhodnocení výrazu.

17. 12. 2024 - Grafy, prohledávání grafu, grafové algoritmy

Vyhodnocení a převody aritmetických notací (dokončení z minulé přednášky).

Reprezentace grafu v programu.

Prohledávání grafu do hloubky a do šířky.

Základní grafové algoritmy založené na prohledávání grafu.

24. 12. 2024 a 31. 12. 2024 – vánoční prázdniny

7. 1. 2025 – Faktorové množiny, obecný strom, další metody návrhu algoritmů

Faktorové množiny a jejich použití při řešení grafových problémů.

Obecný strom – reprezentace, průchod, použití (trie, vícecestné vyhledávací stromy).

Zrychlení algoritmu pomocí předvýpočtu.

Hladové algoritmy.