Logo ČVUT
ČESKÉ VYSOKÉ UČENÍ TECHNICKÉ V PRAZE
STUDIJNÍ PLÁNY
2018/2019

Pokročilá algoritmizace

Přihlášení do KOSu pro zápis předmětu Zobrazit rozvrh
Kód Zakončení Kredity Rozsah Jazyk výuky
B4M33PAL Z,ZK 6 2p+2c česky
Korekvizita:
Bezpečnost práce v elektrotechnice pro magistry (BEZM)
Předmět nesmí být zapsán současně s:
Advanced algorithms (AE4M33PAL)
Advanced algorithms (BE4M33PAL)
Přednášející:
Daniel Průša (gar.), Marko Genyk-Berezovskyj
Cvičící:
Daniel Průša (gar.), Marko Genyk-Berezovskyj, Petr Ryšavý, Martin Svatoš
Předmět zajišťuje:
katedra kybernetiky
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: http://www.fel.cvut.cz/anketa/aktualni/courses/A4M33PAL

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.

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

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

Cíle studia:

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

Studijní materiály:

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

Poznámka:
Další informace:
http://cw.fel.cvut.cz/wiki/courses/b4m33pal/start
Rozvrh na zimní semestr 2018/2019:
06:00–08:0008:00–10:0010:00–12:0012:00–14:0014:00–16:0016:00–18:0018:00–20:0020:00–22:0022:00–24:00
Po
Út
St
místnost KN:E-107
Genyk-Berezovskyj M.
Průša D.

11:00–12:30
(přednášková par. 1)
Karlovo nám.
Zengerova posluchárna K1
místnost KN:E-127
Genyk-Berezovskyj M.
18:00–19:30
(přednášková par. 1
paralelka 102)

Karlovo nám.
Kotkova cvičebna K4
místnost KN:E-127
Svatoš M.
14:30–16:00
(přednášková par. 1
paralelka 105)

Karlovo nám.
Kotkova cvičebna K4
místnost KN:E-127
Svatoš M.
16:15–17:45
(přednášková par. 1
paralelka 106)

Karlovo nám.
Kotkova cvičebna K4
Čt
místnost KN:E-127
Ryšavý P.
07:30–09:00
(přednášková par. 1
paralelka 101)

Karlovo nám.
Kotkova cvičebna K4
místnost KN:E-127
Ryšavý P.
11:00–12:30
(přednášková par. 1
paralelka 103)

Karlovo nám.
Kotkova cvičebna K4
místnost KN:E-127
Genyk-Berezovskyj M.
12:45–14:15
(přednášková par. 1
paralelka 104)

Karlovo nám.
Kotkova cvičebna K4
místnost

09:15–10:45
(přednášková par. 1
paralelka 107)


Rozvrh na letní semestr 2018/2019:
Rozvrh není připraven
Předmět je součástí následujících studijních plánů:
Platnost dat k 16. 6. 2019
Aktualizace výše uvedených informací naleznete na adrese http://bilakniha.cvut.cz/cs/predmet4684006.html