NPRG062 Algoritmizace

školní rok 2023/2024

12 přednášek

3. 10. 2023 - 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í.

Časová a paměťová složitost algoritmů.

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

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.

17. 10. 2023 – Čí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í čísel v poli – přímé metody (SelectSort, InsertSort, BubbleSort).

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

24. 10. 2023 – 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.

31. 10. 2023 - Základní datové struktury

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.

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

7. 11. 2023 – Rekurze, rekurzivní generování

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

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

14. 11. 2023 – Binární stromy

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

Binární strom – různé reprezentace, procházení do hloubky a do šířky.

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

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

21. 11. 2023 – Den otevřených dveří MFF UK

výuka v posluchárně N1 je zrušena

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

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

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

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

5. 12. 2023 - Algoritmus minimaxu, metoda Rozděl a panuj

Strom hry, algoritmus minimaxu, alfa-beta prořezávání.

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

MergeSort (rekurzivní implementace).

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

12. 12. 2023 – QuickSelect, aritmetické výrazy

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.

Převody aritmetických notací.

19. 12. 2023 - Grafy, prohledávání grafu, grafové algoritmy

Informace o zkouškách, zkušební termíny vypsány v SISu.

Reprezentace grafu v programu.

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

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

26. 12. 2023 a 2. 1. 2024 – vánoční prázdniny

9. 1. 2024 – Obecný strom, hešování, 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).

Metody ukládání a vyhledávání dat – přehled.

Hešování – hešovací tabulky, hešovací funkce, řešení kolizí. Datová struktura slovník.

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

Hladové algoritmy.