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 do 2016
• Semestr: zimní
• E-Kredity: 6
• 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í
• Garant: prof. RNDr. Luděk Kučera, DrSc.; RNDr. Jan Hric
• Vyučující: prof. RNDr. Ondřej Čepek, Ph.D.; RNDr. Jan Hric; RNDr. Radek Hušek, Ph.D.; RNDr. Miloš Chromý, Ph.D.; Mgr. Karel Král, Ph.D.; Mgr. Veronika Králová, Ph.D.; prof. RNDr. Luděk Kučera, DrSc.; RNDr. Petr Kučera, Ph.D.; Mgr. Martin Mareš, Ph.D.; RNDr. Jiří Švancara, Ph.D.
• Třída: Informatika Bc.
• Kategorizace předmětu: Informatika > Teoretická informatika

Anotace

čeština

Pokračování přednášky TIN060 Algoritmy a datové struktury I

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

angličtina

Continuation of TIN060 Algorithms and data structures I

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

Literatura

čeština

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

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

angličtina

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

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

Poslední úprava: Hladík Milan, prof. Mgr., Ph.D. (22.11.2012)

Sylabus

čeština

• 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í

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

angličtina

Searching in text:

Algorithms Aho-Corasick, Knuth-Morris-Pratt, optionally Rabin-Karp

Network flows

Augmenting path algorithms (Ford-Fulkerson),

Dinic's and Goldberg's algorithm

Optionally finding maximum flow of minimum cost and bipartite matchings

Algebraic algorithms

Discrete Fourier transform, its motivation and applications

FFT algorithm (Fast Fourier Transform) and its implementation as "butterfly" circuits

Optionally related transforms (DCT -- JPEG compression)

Parallel arithmetic algorithms

Sorting networks (merge-sort or bitonic sort)

Addition of binary numbers -- carry look-ahead

Optionally the Karatsuba-Ofman algorithm for multiplication

Basic algorithms of planar geometry

Convex hull

Voronoi diagram and Delaunay triangulation (Fortune's algorithm)

Reducibility of problems and classes of time complexity:

Polynomial transformations and reductions between decision problems

Non-deterministic algorithms, classes P and NP

NP-completeness

Approximation algorithms

Use of approximation algorithms, relative errors

Examples of approximation algorithms: e.g., knapsack, bin packing, scheduling on parallel machines, including upper bounds of approximation errors

Probabilistic algorithms and cryptography

Monte Carlo algorithms (Rabin-Miller primality test)

Public key cryptography (RSA cryptosystem)

Optionally DES and similar cryptographic algorithms and protocols

Dynamic programming

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