PředmětyPředměty(verze: 797)
Předmět, akademický rok 2016/2017
   Přihlásit přes CAS
Algoritmy a datové struktury II - NTIN061
Anglický název: Algorithms and Data Structures II
Zajišťuje: Katedra aplikované matematiky (32-KAM)
Fakulta: Matematicko-fyzikální fakulta
Platnost: od 2016
Semestr: zimní
E-Kredity: 6
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: prof. RNDr. Luděk Kučera, DrSc.
RNDr. Jan Hric
Třída: Informatika Bc.
Kategorizace předmětu: Informatika > Teoretická informatika
Anotace -
Poslední úprava: G_I (24.05.2004)

Pokračování přednášky TIN060 Algoritmy a datové struktury I
Literatura -
Poslední úprava: prof. RNDr. Luděk Kučera, DrSc. (04.10.2004)

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

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

Sylabus -
Poslední úprava: prof. RNDr. Luděk Kučera, DrSc. (04.10.2004)

  • Vyhledávání v textu:

Algoritmy Aho-Corasicková, Knuth-Morris-Pratt, volitelně Rabin-Karp

  • Toky v sítích:

algoritmus zlepšující cesty (Ford-Fulkerson),

algoritmus Dinicův a Goldbergův,

volitelně hledání maximálního toku minimální ceny a párování v bipartitním grafu

  • Algebraické algoritmy:

Diskrétní Fourierova transformace, její motivace a aplikace,

algoritmus FFT (Fast Fourier Transform) a jeho implementace obvodem "butterfly"

volitelně příbuzné transformace (kosinová - komprese JPEG)

  • Paralelní aritmetické algoritmy:

třídící sítě (merge-sort nebo bitonic-sort)

sčítání čísel - algoritmus carry look-ahead

volitelně algoritmus Karatsuba-Ofman pro násobení čísel

  • Základní geometrické algoritmy v rovině:

Konvexní obal

Voronoi diagram a Delanauy triangulace (algoritmus Fortune)

  • 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

  • Aproximační algoritmy:

použití aproximačních algoritmů, poměrová a relativní chyba

jeden až dva příklady, např. knapsack, bin-packing, rozvrhování na paralelních strojích,

včetně horního odhadu chyby

  • Pravděpodobnostní algoritmy a kryptografie:

algoritmy typu Monte Carlo (Rabin-Millerův test prvočíselnosti)

šifrování s otevřeným klíčem (RSA šifra)

volitelně DES a podobné algoritmy a další kryptografické protokoly

  • Dynamické programování
 
Univerzita Karlova | Informační systém UK