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

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

Předmět B4M33PAL nesmí být zapsán, je-li v témže semestru zapsán anebo již dříve absolvován předmět AE4M33PAL (vztah je symetrický)

Předmět B4M33PAL nesmí být zapsán, je-li v témže semestru zapsán anebo již dříve absolvován předmět BE4M33PAL (vztah je symetrický)

Podmínkou zápisu na předmět B4M33PAL je, že student si nejpozději ve stejném semestru zapsal příslušný počet předmětů ze skupiny BEZBM

Předmět B4M33PAL nesmí být zapsán, je-li v témže semestru zapsán anebo již dříve absolvován předmět AE4M33PAL (vztah je symetrický)

Předmět B4M33PAL nesmí být zapsán, je-li v témže semestru zapsán anebo již dříve absolvován předmět BE4M33PAL (vztah je symetrický)

Předmět B4M33PAL může být splněn v zastoupení předmětem BE4M33PAL

Garant předmětu:
Daniel Průša
Přednášející:
Marko Genyk-Berezovskyj, Daniel Průša
Cvičící:
Ondřej Drbohlav, Marko Genyk-Berezovskyj, Daniel Průša, Petr Ryšavý
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:
https://cw.fel.cvut.cz/wiki/courses/B4M33PAL
Rozvrh na zimní semestr 2023/2024:
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-126
Drbohlav O.
12:45–14:15
(přednášková par. 1
paralelka 102)

Karlovo nám.
Trnkova posluchárna K5
místnost KN:E-127
Drbohlav O.
14:30–16:00
(přednášková par. 1
paralelka 105)

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

Karlovo nám.
Kotkova cvičebna K4
místnost FS_KN:A-312
Genyk-Berezovskyj M.
Průša D.

11:00–12:30
(přednášková par. 1)
Karlovo nám.
Posluchárna FS A:312 - záp.
Č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
Drbohlav O.
12:45–14:15
(přednášková par. 1
paralelka 104)

Karlovo nám.
Kotkova cvičebna K4
místnost KN:E-128

07:30–09:00
(přednášková par. 1
paralelka 107)

Karlovo nám.
Cvičebna K3

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