Popis předmětu - B4M33PAL
Přehled studia |
Přehled oborů |
Všechny skupiny předmětů |
Všechny předměty |
Seznam rolí |
Vysvětlivky
Návod
Výsledek studentské ankety předmětu je zde: A4M33PAL
| B4M33PAL | Pokročilá algoritmizace | ||
|---|---|---|---|
| Role: | PS, PV, P | Rozsah výuky: | 2P+2C |
| Katedra: | 13133 | Jazyk výuky: | CS |
| Garanti: | Průša D. | Zakončení: | Z,ZK |
| Přednášející: | Genyk-Berezovskyj M., Průša D. | Kreditů: | 6 |
| Cvičící: | Drbohlav O., Genyk-Berezovskyj M., Průša D., Ryšavý P. | Semestr: | Z |
Webová stránka:
https://cw.fel.cvut.cz/wiki/courses/B4M33PALAnotace:
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.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ů:
| Stránka vytvořena 14.9.2024 17:50:41, semestry: Z/2024-5, Z/2025-6, Z,L/2023-4, L/2024-5, 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) |