ADS2.md 1.99 KB
Newer Older
1
# NTIN061: Algoritmy a datové struktury II
Martin Mareš's avatar
Martin Mareš committed
2
3
4

## Anotace

Martin Mareš's avatar
Martin Mareš committed
5
Přednáška o různých typech algoritmů a jejich časové složitosti (navazuje na NTIN060).
Martin Mareš's avatar
Martin Mareš committed
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

## Sylabus

(volitelná témata _kurzívou_, zbytek je povinný; hodinové dotace jsou orientační)

1. 	Vyhledávání v textu (2 přednášky)
	* algoritmus Knuth-Morris-Pratt
	* algoritmus Aho-Corasicková
	* _algoritmus Rabin-Karp_

1. 	Toky v sítích (2 přednášky)
	* 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_

1. 	Algebraické algoritmy (1.5 přednášky)
	* diskrétní Fourierova transformace, její motivace a aplikace
	* algoritmus FFT a jeho implementace obvodem „butterfly“
	* _příbuzné transformace (kosinová komprese – JPEG)_

1. 	Paralelní aritmetické algoritmy (1.5 přednášky)
	* 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

1. 	Základní geometrické algoritmy v rovině (1 přednáška)
	* konvexní obal
	* princip zametání roviny řízeného událostmi
	* _Voroného diagram a Delaunayova triangulace (Fortunův algoritmus)_

1. 	Převoditelnost problémů a třídy časové složitosti (2 přednášky)
	* polynomiální transformace a redukce mezi rozhodovacími problémy
	* nedeterministické algoritmy, třídy P a NP
	* NP-úplnost 

1. 	Aproximační algoritmy (1 přednáška)
	* 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

1. 	Pravděpodobnostní algoritmy a kryptografie (1 přednáška)
	* algoritmy typu Monte Carlo (Rabinův-Millerův test prvočíselnosti)
	* šifrování s veřejným klíčem (algoritmus RSA)