Fakulta elektrotechnická

České vysoké učení technické v Praze

ČVUT v Praze

Popis předmětu - A4M33PAL

Přehled studia | Přehled oborů | Všechny skupiny předmětů | Všechny předměty | Seznam rolí | Vysvětlivky               Návod
A4M33PAL Pokročilá algoritmizace Rozsah výuky:2+2c
Garanti:  Role:PO,P,V Jazyk výuky:CS
Vyučující:  Zakončení:Z,ZK
Zodpovědná katedra:13133 Kreditů:6 Semestr:Z

Anotace:

Základní grafové algoritmy a reprezentace grafů. Kombinatorické algoritmy. Aplikace teorie formálních jazyků v informatice - hledání v textu.

Výsledek studentské ankety předmětu je zde: A4M33PAL

Cíle studia:

Základní přehled a dovednosti související s tématy předmětu.

Osnovy přednášek:

Diskuse paměťové a časové složitosti probíraných datových typů a algoritmů je integrální součástí každého tématu, neuvádíme ji explicitně u každého tématu zvlášť.
1. Pøipomenutí asymptotické složitosti. Reprezentace grafů.
2. Minimální kostra grafu. Union-Find problém.
3. Eulerovy cesty. Orientované grafy: souvislost, acykličnost.
4. Haldy. Fibonacciho halda. Srovnání hald.
5. Dynamické datové struktury. Garbage collector.
6. Generování, enumerace a izomorfizmus datových struktur a kombinatorických objektů. Permutace, kombinace, variace, stromy.
7. Generování dalších kombinatorických struktur: k-prvkové podmožiny, Gray code, neizomorfní grafy.
8. Posloupnosti - vyhledávání interpolační, kvadratické; hledání mediánu v lineárním čase.
9. Konečné automaty, jejich implementace, redukce automatu.
10. Regulární výrazy a vyhledávání v textu pomocí regulárních výrazů.
11. Přibližné vyhledávání v textu pomocí konečných automatù, slovníkové automaty.
12. Hledání ve více dimenzích, K-D stromy, Quadtree.
13. Vyhledávací stromy: B a B+; 2-3-4 a R-B stromy.
14. Vyhledávací stromy: Trie, suffixový strom, splay tree.

Osnovy cvičení:

Náplní cvičení a navazující domácí přípravy je především praktická implementace témat přednášky. Témata cvičení proto formálně kopírují témata přednášek.

Literatura:

R. Sedgewick: Algoritmy v C, SoftPress 2003,
T. H. Cormen, C. E. Leiserson, R. L. Rievest, C. Stein: Introduction to Algorithms, 2nd ed., MIT Press, 2001
B. Melichar: Jazyky a překlady, Praha , ČVUT 1996
J. E. Hopcroft, R. Motwani, J. D. Ullman: Introduction to Automata Theory, Languages, and Computation, 2nd ed., Addison-Wesley, 2001

Požadavky:

Důležitou součástí cvičení je samostatná implementace datových typů a algoritmů přednášky. Znalost programování na urovni manipulace se spojovými strukturami v některém z rozšířených programovacích jazyků (C/C++/Java/...) je proto nezbytná. Další důležité informace naleznete na: http://cw.felk.cvut.cz/doku.php/courses/a4m33pal/start.

Poznámka:

Rozsah výuky v kombinované formě studia: 14p+6c

Webová stránka:

http://cw.felk.cvut.cz/doku.php/courses/a4m33pal/start

Klíčová slova:

Orientovaný a neorientovaný graf, grafový algoritmus, prioritní fronta, vyhledávání v textu,

Předmět je zahrnut do těchto studijních plánů:

Plán Obor Role Dop. semestr
MPIB Před zařazením do oboru V
MPOI1 Umělá inteligence P 1
MPOI2 Počítačové inženýrství P 1
MPOI3 Počítačové vidění a digitální obraz P 1
MPOI5NEW Softwarové inženýrství P 1
MPOI5 Softwarové inženýrství P 1
MPOI4NEW Počítačová grafika a interakce P 1
MPOI4 Počítačová grafika a interakce P 1
MPKME2 Multimediální technika V 1
MPKME4 Sítě elektronických komunikací V 1
MPKME1 Bezdrátové komunikace V 1
MPKME3 Elektronika V 1
MPKME5 Komunikační systémy V 1
MPEEM5 Ekonomika a řízení elektrotechniky V 1
MPEEM4 Ekonomika a řízení energetiky V 1
MPEEM2 Elektrické stroje, přístroje a pohony V 1
MPEEM1 Technologické systémy V 1
MPEEM3 Elektroenergetika V 1
MPKYR4 Letecké a kosmické systémy V 1
MPBIO1 Biomedicínská informatika PO 1
MPKYR1 Robotika V 1
MPKYR2 Senzory a přístrojová technika V 1
MPKYR3 Systémy a řízení V 1


Stránka vytvořena 12.12.2017 05:47:39, semestry: L/2016-7, Z,L/2017-8, Z/2018-9, připomínky k informační náplni zasílejte správci studijních plánů Návrh a realizace: I. Halaška (K336), J. Novák (K336)
Za obsah odpovídá: doc. Ing. Ivan Jelínek, CSc.