ADS1.md 2.47 KB
Newer Older
1
# NTIN060: Algoritmy a datové struktury I
Martin Mareš's avatar
Martin Mareš committed
2
3
4
5
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

## Anotace
Úvodní přednáška o základních typech algoritmů a datových strukturách
potřebných pro jejich implementaci. Navazuje na výklad v přednášce
„Algoritmizace“ v předchozím semestru.

## Sylabus

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

1. 	Prostředky pro popis složitosti algoritmů a operací nad datovými strukturami (1 přednáška)
	* měření velikosti dat, počet kroků algoritmu jako funkce velikosti dat
	* výpočetní model RAM
	* asymptotická notace

1. 	Základní grafové algoritmy (1 přednáška)
	* prohledávání do hloubky na neorientovaném grafu, detekce mostů _a artikulací_
	* prohledávání do hloubky na orientovaném grafu, tranzitivní uzávěr, topologické číslování
	* _detekce komponent silné souvislosti v lineárním čase_

1. 	Extremální cesty v grafech (2 přednášky)
	* extremální cesty v acyklickém orientovaném grafu, metoda kritické cesty
	* Dijkstrův algoritmus (zopakování binární haldy, srovnání implementace polem a binární haldou)
	* Bellmanův-Fordův algoritmus (hledání záporných cyklů)
	* _Floydův-Warshallův algoritmus_

1. 	Minimální kostra grafu (1 přednáška)
	* Jarníkův a Borůvkův algoritmus
	* _Kruskalův algoritmus a datová struktura pro Union-Find_

32
33
34
35
36
37
38
39
40
41
42
1. 	Stromové datové struktury (1.5 přednášky)
	* binární vyhledávací stromy
	* AVL stromy
	* (a,b)-stromy
	* _červeno-černé stromy_

1. 	Hešování (1 přednáška)
	* popis jednoduchých strategií řešení kolizí
	* analýza průměrné časové složitosti vyhledávání
	* univerzální hešování

Martin Mareš's avatar
Martin Mareš committed
43
44
45
46
47
48
49
50
51
52
1. 	Metoda rozděl a panuj (2.5 přednášky)
	* obecné schéma algoritmů typu rozděl a panuj, souvislost jejich složitosti s rekurentními rovnicemi
	* substituční metoda řešení rekurentních rovnic a „master theorem (kuchařka)“
	* jednoduché aplikace: binární vyhledávání, Mergersort, násobení čísel (Karatsuba-Ofman)
	* složitější aplikace: Strassenovo násobení matic, _hledání mediánu v lin. čase v nejhorším případě_

1. 	Dynamické programování (1 přednáška)
	* obecný princip dynamického programování
	* editační vzdálenost řetězců
	* _optimální vyhledávací stromy_
53
54
55
56

1. 	Třídění (1 přednáška)
	* analýza průměrného případu pro Quicksort, randomizovaný Quicksort
	* dolní odhad složitosti porovnávacích třídících algoritmů (rozhodovací stromy)