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).
Poslední úprava: 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).
Podmínky zakončení předmětu
Poslední úprava: Mgr. Martin Mareš, Ph.D. (26.09.2023)
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
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: doc. RNDr. Pavel Töpfer, CSc. (01.02.2018)
Optional topics in square brackets, the rest is mandatory.
1. Searching in text
Knuth-Morris-Pratt algorithm
Aho-Corasick algorithm
[Rabin-Karp algorithm]
2. Flows in networks
augmenting path algorithm
Dinic's algorithm
Goldberg's algorithm
matching in bipartite graph
[search for maximum flow of minimum price]
3. Algebraic algorithms
discrete Fourier transformation, its motivation and application
the FFT algorithm and its implementation by the "butterfly"
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)
