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)
Lecture about various types of algorithms and their time complexity (follows NTIN060 Algorithms and data
structures 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
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)
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)
public key cryptography (RSA algorithm)
Poslední úprava: Töpfer Pavel, doc. RNDr., CSc. (01.02.2018)
