Pokročilá algoritmizace
Kód | Zakončení | Kredity | Rozsah | Jazyk výuky |
---|---|---|---|---|
B4M33PAL | Z,ZK | 6 | 2P+2C | česky |
- 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 Čt Pá - Rozvrh na letní semestr 2023/2024:
- Rozvrh není připraven
- Předmět je součástí následujících studijních plánů:
-
- Lékařská elektronika a bioinformatika - Specializace Bioinformatika (PS)
- Otevřená informatika - Interakce člověka s počítačem 2018 (povinný předmět programu)
- Otevřená informatika - Kybernetická bezpečnost 2018 (povinný předmět programu)
- Otevřená informatika - Počítačová grafika 2018 (povinný předmět programu)
- Otevřená informatika - Počítačové inženýrství 2018 (povinný předmět programu)
- Otevřená informatika - Počítačové vidění a digitální obraz 2018 (povinný předmět programu)
- Otevřená informatika - Softwarové inženýrství 2018 (povinný předmět programu)
- Otevřená informatika - Umělá inteligence 2018 (povinný předmět programu)
- Otevřená informatika - Bioinformatika 2018 (povinný předmět programu)
- Otevřená informatika - Datové vědy 2018 (povinný předmět programu)
- Lékařská elektronika a bioinformatika - Specializace Lékařská technika (povinně volitelný předmět)
- Lékařská elektronika a bioinformatika - Specializace Zpracování obrazu (PS)
- Lékařská elektronika a bioinformatika - Specializace Zpracování signálů (povinně volitelný předmět)
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 může být splněn v zastoupení předmětem BE4M33PAL