PředmětyPředměty(verze: 953)
Předmět, akademický rok 2023/2024
   Přihlásit přes CAS
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 [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í
Způsob výuky: prezenční
Garant: Mgr. Martin Mareš, Ph.D.
prof. RNDr. Ondřej Čepek, Ph.D.
doc. Mgr. Jan Hubička, Ph.D.
Třída: Informatika Bc.
Kategorizace předmětu: Informatika > Teoretická informatika
Neslučitelnost : NTIX061
Záměnnost : NTIX061
Je neslučitelnost pro: NTIX061
Je záměnnost pro: NTIX061
Ve slož. záměnnosti pro: NUIN021
Anotace -
Přednáška o různých typech algoritmů a jejich časové složitosti (navazuje na NTIN060 Algoritmy a datové struktury 1).
Poslední úprava: Töpfer Pavel, doc. RNDr., CSc. (01.02.2018)
Podmínky zakončení předmětu

Je třeba získat zápočet a složit zkoušku (v libovolném pořadí).

Pro zápočet je třeba získat 100 bodů z alespoň 150 možných udělovaných průběžně za řešení domácích úloh, písemné testy a další aktivity. Z průběžné povahy kontroly neplyne nárok na vypisování opravných termínů testů ani zadání náhradních domácích úloh.

V důvodných případech (dlouhodobá nemoc, pobyt v zahraničí, apod.) může cvičící stanovit individuální podmínky na udělení zápočtu.

Zkouška může být písemná, ústní nebo kombinovaná. Zkouška může mít kontaktní nebo distanční formu. Formu zkoušky určuje vyučující.

Poslední úprava: Mareš Martin, Mgr., Ph.D. (26.09.2023)
Literatura -

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

Poslední úprava: Hric Jan, RNDr. (03.10.2017)
Požadavky ke zkoušce

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

Poslední úprava: Mareš Martin, Mgr., Ph.D. (11.10.2017)
Sylabus -

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)

Poslední úprava: Töpfer Pavel, doc. RNDr., CSc. (01.02.2018)
 
Univerzita Karlova | Informační systém UK