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. Rozdělení bodů je vždy nastaveno tak, aby body za alespoň dva písemné nebo elektronicky odevzdané výstupy (např. za 2 domácí úkoly, nebo za 1 domácí úkol a za 1 test, nebo za 2 testy) nebyly potřeba k dosažení hranice 100 bodů.
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á. Formu zkoušky určuje vyučující.
Poslední úprava: Čepek Ondřej, prof. RNDr., Ph.D. (31.08.2026)
It is necessary to get the course credit and pass the examination (in arbitrary order).
For the course credit you need to get 100 points out of at least 150 possible points awarded for homework, tests, and other activities. The distribution of these points is always set up in a way that points awarded for at least two written or electronically submitted outputs (e.g. 2 homework assignments, or 1 homework assignment and 1 test, or 2 tests) are not necessary to reach the 100 point limit.
In justified cases (long-term illness, stay abroad, etc.) the lecturer may set individual conditions for credit granting.
The examination can be written, oral, or combined. The form of the exam is determined by the teacher.
Poslední úprava: Čepek Ondřej, prof. RNDr., Ph.D. (31.08.2026)
Literatura -
T. Cormen, C. Leiserson, R. Rivest, C. Stein: Introduction to Algorithms (4th Edition), Sathya Publishers 2023
M. Mareš, T. Valla: Průvodce labyrintem algoritmů (2. vydání), CZ.NIC Praha 2022, https://pruvodce.ucw.cz/
L. Kučera: Kombinatorické algoritmy, SNTL Praha 1983
S. Dasgupta, C. Papadimitriou, U. Vazirani: Algorithms, McGraw-Hill Education 2006
J. Erickson: Algorithms, 2023, https://jeffe.cs.illinois.edu/teaching/algorithms/
Poslední úprava: Maxová Jana, RNDr., Ph.D. (17.05.2025)
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)
Kontroly studia předmětu a podmínky pro jejich úspěšné vykonání, způsob hodnocení
Je třeba rozumět teorii z přednášky a být schopen ji aplikovat na řešení algoritmických úloh.
Poslední úprava: Mareš Martin, Mgr., Ph.D. (11.10.2017)
Sylabus -
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)]
[šifrování s veřejným klíčem (algoritmus RSA)]
Poslední úprava: Maxová Jana, RNDr., Ph.D. (17.05.2025)
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: Maxová Jana, RNDr., Ph.D. (17.05.2025)
