PředmětyPředměty(verze: 964)
Předmět, akademický rok 2024/2025
   Přihlásit přes CAS
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 2022
Semestr: zimní
E-Kredity: 4
Rozsah, examinace: zimní s.:2/1, Z+Zk [HT]
Počet míst: neomezen
Minimální obsazenost: neomezen
4EU+: ne
Virtuální mobilita / počet míst pro virtuální mobilitu: ne
Stav předmětu: vyučován
Jazyk výuky: čeština, angličtina
Způsob výuky: prezenční
Garant: doc. RNDr. Tomáš Dvořák, CSc.
doc. RNDr. Pavel Töpfer, CSc.
Adam Dingle, M.Sc.
Vyučující: Mgr. Tomáš Bílý
Adam Dingle, M.Sc.
doc. RNDr. Tomáš Dvořák, CSc.
RNDr. Tomáš Holan, Ph.D.
Mgr. Martin Mareš, Ph.D.
Mgr. Jakub Mestek
RNDr. František Mráz, CSc.
RNDr. Martin Pergel, Ph.D.
Mgr. Klára Pešková, Ph.D.
Mgr. Vít Šefl
Mgr. Jiří Šejnoha
RNDr. Michal Töpfer
doc. RNDr. Pavel Töpfer, CSc.
Korekvizity : NPRG030
Neslučitelnost : NMIN102, NMIN112
Je korekvizitou pro: NPRG030
Je neslučitelnost pro: NMIN112
Anotace -
Ú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.
Poslední úprava: Töpfer Pavel, doc. RNDr., CSc. (30.10.2019)
Podmínky zakončení předmětu -

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.

Zkouška je organizována společně pro posluchače v českých paralelkách, avšak odděleně od zkoušky pro posluchače anglického programu Bachelor of Computer Science.

Poslední úprava: Dvořák Tomáš, doc. RNDr., CSc. (25.09.2024)
Literatura -

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

Martin Mareš, Tomáš Valla, Průvodce labyrintem algoritmů, 2. vydání, CZ.NIC, Praha 2022, https://knihy.nic.cz

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

Poslední úprava: Dvořák Tomáš, doc. RNDr., CSc. (11.09.2023)
Sylabus -
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.
Poslední úprava: Dvořák Tomáš, doc. RNDr., CSc. (23.09.2019)
 
Univerzita Karlova | Informační systém UK