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

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

M.Mareš, T.Valla : Průvodce labyrintem algoritmů, CZ.NIC z.s.p.o. Praha 2017, 978-80-88168-19-5, http://pruvodce.ucw.cz/

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

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

Je třeba rozumět teorii z přednášky a být schopen ji aplikovat na řešení algoritmických úloh.

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“

• [příbuzné transformace (kosinová - JPEG komprese)]

4. Paralelní aritmetické algoritmy

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

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"

• [related transformations (cosine transformation - JPEG compression)]

4. Parallel arithmetic algorithms

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