Pokročilá algoritmizace

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 2024/2025:

Rozvrh není připraven

Rozvrh na letní semestr 2024/2025:

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)