PředmětyPředměty(verze: 877)
Předmět, akademický rok 2020/2021
  
Algoritmy a datové struktury 2 - NTIN061
Anglický název: Algorithms and Data Structures 2
Zajišťuje: Katedra aplikované matematiky (32-KAM)
Fakulta: Matematicko-fyzikální fakulta
Platnost: od 2020
Semestr: zimní
E-Kredity: 5
Rozsah, examinace: zimní s.:2/2 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: Mgr. Martin Mareš, Ph.D.
doc. RNDr. Ondřej Čepek, Ph.D.
Mgr. Jan Hubička, Ph.D.
Třída: Informatika Bc.
Kategorizace předmětu: Informatika > Teoretická informatika
Neslučitelnost : NTIX061
Záměnnost : NTIX061
N//Je neslučitelnost pro: NTIX061
Z//Je záměnnost pro: NTIX061
Anotace -
Poslední úprava: doc. RNDr. Pavel Töpfer, CSc. (01.02.2018)
Přednáška o různých typech algoritmů a jejich časové složitosti (navazuje na NTIN060 Algoritmy a datové struktury 1).
Podmínky zakončení předmětu
Poslední úprava: Mgr. Jan Hubička, Ph.D. (24.09.2020)

Je třeba získat zápočet a složit zkoušku. Získání zápočtu není podmínkou pro absolvování zkoušky. Zápočet se uděluje za kombinaci účasti a aktivity na cvičení, řešení domácích úkolů a zápočtových písemek. Povaha kontroly na zápočet vylučuje možnost jejího opakování.

Zkouška se skládá z písemné a ústní části. Písemná část předchází části ústní, její nesplnění znamená, že termín zkoušky je hodnocen známkou nevyhověl(a) a ústní částí se již nepokračuje.

Zkouška může mít kontaktní nebo distanční formu.

Literatura -
Poslední úprava: RNDr. Jan Hric (03.10.2017)

A.Koubková, J.Pavelka : Úvod do teoretické informatiky, Matfyzpress 1999

Aho, Hopcroft, Ullman : The design and analysis of computer algorithms, Addison-Wesley 1976

T.Cormen, Ch.Leiserson, R. Rivest, C. Stein : Introduction to Algorithms (2nd Edition), McGraw-Hill 2001

L.Kučera : Kombinatorické algoritmy, SNTL Praha 1983

L.Kučera, J. Nešetřil : Algebraické metody diskretní matematiky, SNTL Praha 1989

M.Mareš, T.Valla : Průvodce labyrintem algoritmů, CZ.NIC z.s.p.o. Praha 2017, 978-80-88168-19-5, http://pruvodce.ucw.cz/

http://kam.mff.cuni.cz/~ludek

Požadavky ke zkoušce
Poslední úprava: Mgr. Martin Mareš, Ph.D. (11.10.2017)

Je třeba rozumět teorii z přednášky a být schopen ji aplikovat na řešení algoritmických úloh.

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

Volitelná témata v hranatých závorkách, zbytek je povinný.

1. Vyhledávání v textu

  • algoritmus Knuth-Morris-Pratt
  • algoritmus Aho-Corasicková
  • [algoritmus Rabin-Karp]

2. Toky v sítích

  • algoritmus zlepšující cesty
  • Dinicův algoritmus
  • Goldbergův algoritmus
  • párování v bipartitním grafu
  • [hledání maximálního toku minimální ceny]

3. Algebraické algoritmy

  • diskrétní Fourierova transformace, její motivace a aplikace
  • algoritmus FFT a jeho implementace obvodem „butterfly“
  • [příbuzné transformace (kosinová - JPEG komprese)]

4. Paralelní aritmetické algoritmy

  • třídící sítě (implementace jednoho třídícího algoritmu - buď merge-sort nebo bitonic-sort)
  • carry look-ahead algoritmus pro sčítání čísel

5. Základní geometrické algoritmy v rovině

  • konvexní obal
  • princip zametání roviny řízeného událostmi
  • [Voroného diagram a Delaunayova triangulace (Fortunův algoritmus)]

6. Převoditelnost problémů a třídy časové složitosti

  • polynomiální transformace a redukce mezi rozhodovacími problémy
  • nedeterministické algoritmy, třídy P a NP
  • NP-úplnost

7. Aproximační algoritmy

  • použití aproximačních algoritmů, poměrová a relativní chyba
  • jeden až dva jednoduché příklady aproximačních algoritmů (knapsack, bin-packing, rozvrhování na paralelních strojích) včetně horního odhadu pro jejich poměrovou (nebo relativní) chybu
  • aproximační schéma: princip a příklad

8. Pravděpodobnostní algoritmy a kryptografie

  • algoritmy typu Monte Carlo (Rabinův-Millerův test prvočíselnosti)
  • šifrování s veřejným klíčem (algoritmus RSA)

 
Univerzita Karlova | Informační systém UK