Last update: doc. RNDr. Pavel Töpfer, CSc. (01.02.2018)
Lecture about various types of algorithms and their time complexity (follows NTIN060 Algorithms and data
structures 1).
Last update: 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).
Course completion requirements - Czech
Last update: doc. 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.
Literature -
Last update: prof. Mgr. Milan Hladík, Ph.D. (22.11.2012)
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
Last update: 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
sorting networks (implementation of one sorting algorithm - either merge-sort or bitonic-sort)
carry look-ahead algorithm for addition
5. Basic geometric algorithms in a plane
convex hull
the principle of plane sweeping driven by events
[Voronoi diagram and Delaunay triangulation (Fortune's algorithm)]
6. Transferability of problems and classes of time complexity
polynomial transformation and reduction between decision problems
non-deterministic algorithms, Class P and NP
NP-completeness
7. Approximation algorithms
use of approximation algorithms, ratio and relative error
one or two simple examples of approximation algorithms (knapsack, bin-packing, scheduling on parallel machines) including an upper estimate for their ratio (or relative) error
approximation scheme: principle and example
8. Probabilistic algorithms and cryptography
Monte Carlo algorithms (Rabin-Miller's Primality Test)
public key cryptography (RSA algorithm)
Last update: 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“
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)