Pokročilá algoritmizace

Přednášející:

Cvičící:

Předmět zajišťuje:

katedra kybernetiky

Anotace:

Základní grafové algoritmy a reprezentace grafů. Aplikace teorie formálních jazyků v informatice - syntaktická analýza a hledání v textu. Vybrané partie aritmetiky v pohyblivé řádové čárce.

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. Grafy, multigrafy, jejich vlastnosti a reprezentace v počítači. Prohledávání grafu, prioritní fronta.

2. Minimální kostry, algoritmus Borůvkův a Jarníkův. Problém Union-find.

3. Barevnost grafu, souvislost se SAT-problémem, barvení rovinných grafů.

4. Reprezentace dynamických datových struktur. Garbage collector.

5. Počítačová aritmetika. Přirozená čísla, celá čísla, čísla s pevnou řádovou čárkou, čísla s pohyblivou řádovou čárkou. Problémy zpracování čísel: přetečení, zaokrouhlování, komutativita.

6. Odhady výpočetních chyb v numerických algoritmech: hledání kořenu funkce, inverzní matice. Vzájemná kompatibilita mezi architekturami, jazyky a překladači.

7. Vyhledvání v textu, klasické algoritmy, Knuth-Morris-Pratt alg., Boyer-Moore alg. a jejich varianty.

8. Konečné automaty pro vyhledvání v textu, faktorové, prefixové a suffixové automaty.

9. Komprese textu, Huffmanovo kodovani, LZW algoritmus.

10. Návrh a realizace lexikálního analyzátoru.

11. LL(1) gramatiky, rozkladové tabulky.

12. Realizace syntaktické analýzy rekurzívním sestupem.

(13.) (Přesné výpočty matematických funkcí, vzajemná kompatibilita mezi architekturami, jazyky a překladači.)

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:

Rozsah výuky v kombinované formě studia: 14p+6c

Další informace:

Pro tento předmět se rozvrh nepřipravuje

Předmět je součástí následujících studijních plánů:

• Otevřená informatika - Umělá inteligence_145417 (povinný předmět programu)
• Otevřená informatika - Počítačové inženýrství_145440 (povinný předmět programu)
• Otevřená informatika - Počítačové vidění a digitální obraz_145456 (povinný předmět programu)
• Otevřená informatika - Počítačová grafika a interakce_145515 (povinný předmět programu)
• Otevřená informatika - Softwarové inženýrství_145534 (povinný předmět programu)