PředmětyPředměty(verze: 861)
Předmět, akademický rok 2019/2020
  
Algoritmizace - NPRG062
Anglický název: Introduction to Algorithms
Zajišťuje: Katedra softwaru a výuky informatiky (32-KSVI)
Fakulta: Matematicko-fyzikální fakulta
Platnost: od 2019 do 2019
Semestr: zimní
E-Kredity: 4
Rozsah, examinace: zimní s.:2/1 Z+Zk [hodiny/týden]
Počet míst: neomezen
Minimální obsazenost: neomezen
Stav předmětu: vyučován
Jazyk výuky: čeština, angličtina
Způsob výuky: prezenční
Garant: doc. RNDr. Pavel Töpfer, CSc.
doc. RNDr. Tomáš Dvořák, CSc.
Anotace -
Poslední úprava: doc. RNDr. Pavel Töpfer, CSc. (30.10.2019)
Úvodní kurz základních algoritmů, složitosti algoritmů a datových struktur pro posluchače prvního ročníku bakalářského studia informatiky a učitelství informatiky.
Podmínky zakončení předmětu -
Poslední úprava: doc. RNDr. Pavel Töpfer, CSc. (17.09.2019)

Předmět je zakončen zápočtem a zkouškou. Podmínkou pro přihlášení ke zkoušce je předchozí získání zápočtu.

K získání zápočtu se požaduje aktivní účast na cvičeních a úspěšné vyřešení úkolů v termínech stanovených cvičícím. Povaha tohoto požadavku neumožňuje vypsat opravné termíny. Vyučující může stanovit podmínky, za nichž student může nahradit chybějící domácí úkoly.

Zkouška má písemnou a ústní část. Na zkoušku je jeden řádný a dva opravné termíny.

Literatura -
Poslední úprava: doc. RNDr. Pavel Töpfer, CSc. (01.02.2018)

Thomas H. Cormen,‎ Charles E. Leiserson,‎ Ronald L. Rivest,‎ Clifford Stein, Introduction to Algorithms, 3. vydání, MIT Press, Cambridge, MA 2009

Pavel Töpfer, Algoritmy a programovací techniky, 2. vydání, Prometheus, Praha 2007

Martin Mareš, Tomáš Valla, Průvodce labyrintem algoritmů, CZ.NIC, Praha 2017, https://knihy.nic.cz

Sylabus -
Poslední úprava: doc. RNDr. Tomáš Dvořák, CSc. (23.09.2019)
Algoritmy a jejich efektivita.

  • Algoritmus - vlastnosti, důkaz správnosti, porovnávání kvality algoritmů.
  • Časová a paměťová složitost algoritmů, asymptotická složitost, notace „velké O“.
  • Složitost algoritmu v nejhorším, nejlepším a průměrném případě.

Základní algoritmy a techniky.

  • Dělitelnost - Eukleidův algoritmus, prvočíselný rozklad.
  • Prvočísla - test prvočíselnosti, Eratosthenovo síto.
  • Rozklad čísla na cifry, převody mezi číselnými soustavami.
  • „Dlouhá čísla“ - uložení, operace.
  • Hornerovo schéma, rychlé umocňování.

Základní datové struktury.

  • Vyhledávání v poli - sekvenční, binární.
  • Abstraktní datové typy: zásobník, fronta, prioritní fronta, slovník.
  • Hešovací tabulky - princip, řešení kolizí.
  • Halda. Binární vyhledávací strom, princip vyvažování.

Třídění.

  • Třídění čísel v poli - přímé metody (SelectSort, InsertSort, BubbleSort).
  • Haldové třídění (HeapSort), QuickSort.
  • Složitost problému vnitřního třídění.
  • Přihrádkové třídění (CountingSort, BucketSort, RadixSort).
  • Poznámka o vnějším třídění.

Rekurze.

  • Rekurze - princip, příklady, efektivita.
  • Binární strom - reprezentace, prohledávání, použití.
  • Reprezentace aritmetického výrazu binárním stromem.
  • Notace aritmetického výrazu (infix, prefix, postfix) - vyhodnocení, převody.
  • Obecný strom - reprezentace, průchod, použití.

Prohledávání stavového prostoru.

  • Rekurzivní algoritmy založené na zkoušení všech možností - backtracking.
  • Prohledávání do hloubky a do šířky - princip, použití, realizace.
  • Zrychlení pomocí ořezávání a heuristik.
  • Strom hry, algoritmus minimaxu, alfa-beta prořezávání.

Základní grafové algoritmy.

  • Reprezentace grafu.
  • Prohledávání grafů do hloubky a do šířky a jejich aplikace.

Obecné metody návrhu algoritmů.

  • Zrychlení předvýpočtem.
  • Hladový algoritmus.
  • Metoda „Rozděl a panuj“.
  • Memoizace.
 
Univerzita Karlova | Informační systém UK