Pokročilá algoritmizace

Přednášející:

Marko Genyk-Berezovskyj, Jiří Vyskočil

Cvičící:

Jiří Matas (gar.), Čeněk Albl, Marko Genyk-Berezovskyj, Martin Grill, Michal Jančošek, Viliam Lisý, Radek Mařík, Radek Píbil, Jiří Vyskočil

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

Rozvrh na zimní semestr 2011/2012:

	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	místnost KN:E-132 Lisý V. 18:00–19:30 LICHÝ TÝDEN (přednášková par. 1 paralelka 101) Karlovo nám. Laboratoř PC místnost KN:E-127 Lisý V. 18:00–19:30 SUDÝ TÝDEN (přednášková par. 1 paralelka 101) Karlovo nám. Kotkova cvičebna K4 místnost KN:E-127 Grill M. 18:00–19:30 LICHÝ TÝDEN (přednášková par. 1 paralelka 102) Karlovo nám. Kotkova cvičebna K4 místnost KN:E-132 Grill M. 18:00–19:30 SUDÝ TÝDEN (přednášková par. 1 paralelka 102) Karlovo nám. Laboratoř PC
Út
St	místnost KN:E-107 Genyk-Berezovskyj M. Vyskočil J. 11:00–12:30 (přednášková par. 1) Karlovo nám. Zengerova posluchárna K1místnost KN:E-132 Píbil R. 18:00–19:30 LICHÝ TÝDEN (přednášková par. 1 paralelka 103) Karlovo nám. Laboratoř PC místnost KN:E-127 Píbil R. 18:00–19:30 SUDÝ TÝDEN (přednášková par. 1 paralelka 103) Karlovo nám. Kotkova cvičebna K4 místnost KN:E-127 18:00–19:30 LICHÝ TÝDEN (přednášková par. 1 paralelka 104) Karlovo nám. Kotkova cvičebna K4 místnost KN:E-132 18:00–19:30 SUDÝ TÝDEN (přednášková par. 1 paralelka 104) Karlovo nám. Laboratoř PC
Čt	místnost KN:E-132 Genyk-Berezovskyj M. 09:15–10:45 LICHÝ TÝDEN (přednášková par. 1 paralelka 105) Karlovo nám. Laboratoř PCmístnost KN:E-132 Jančošek M. 11:00–12:30 LICHÝ TÝDEN (přednášková par. 1 paralelka 107) Karlovo nám. Laboratoř PCmístnost 12:45–14:15 LICHÝ TÝDEN (přednášková par. 1 paralelka 109) místnost KN:A-421 Genyk-Berezovskyj M. 09:15–10:45 SUDÝ TÝDEN (přednášková par. 1 paralelka 105) Karlovo nám. Cvičebnamístnost KN:A-421 Jančošek M. 11:00–12:30 SUDÝ TÝDEN (přednášková par. 1 paralelka 107) Karlovo nám. Cvičebnamístnost 12:45–14:15 SUDÝ TÝDEN (přednášková par. 1 paralelka 110) místnost KN:A-421 Mařík R. 09:15–10:45 LICHÝ TÝDEN (přednášková par. 1 paralelka 106) Karlovo nám. Cvičebnamístnost KN:A-421 Albl Č. 11:00–12:30 LICHÝ TÝDEN (přednášková par. 1 paralelka 111) Karlovo nám. Cvičebna místnost KN:E-132 Mařík R. 09:15–10:45 SUDÝ TÝDEN (přednášková par. 1 paralelka 106) Karlovo nám. Laboratoř PCmístnost KN:E-132 Albl Č. 11:00–12:30 SUDÝ TÝDEN (přednášková par. 1 paralelka 111) Karlovo nám. Laboratoř PC
Pá

Rozvrh na letní semestr 2011/2012:

Rozvrh není připraven

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

• Otevřená informatika - Umělá inteligence (povinný předmět programu)
• Otevřená informatika - Počítačové inženýrství (povinný předmět programu)
• Otevřená informatika - Počítačové vidění a digitální obraz (povinný předmět programu)
• Otevřená informatika - Počítačová grafika a interakce (povinný předmět programu)
• Otevřená informatika - Softwarové inženýrství (povinný předmět programu)
• Biomedicínské inženýrství a informatika - Biomedicínská informatika (povinný předmět oboru)