Logo ČVUT
ČESKÉ VYSOKÉ UČENÍ TECHNICKÉ V PRAZE
STUDIJNÍ PLÁNY
2019/2020

Arbologie

Přihlášení do KOSu pro zápis předmětu Zobrazit rozvrh
Kód Zakončení Kredity Rozsah
PI-ARB ZK 4 3C
Přednášející:
Cvičící:
Jan Janoušek (gar.)
Předmět zajišťuje:
katedra teoretické informatiky
Anotace:

Seznámení se s typy algoritmů zpracovávajících stromové struktury a s jejich efektivními řešeními.

Důraz kladen na přístup skrze model stromových a zásobníkových automatů.

Z konkrétních praktických aplikací jsou podrobněji diskutovány zpracování XML a algoritmy používané při tvorbě překladačů.

Požadavky:
Osnova přednášek:

1.Základní definice pojmů, stromové jazyky, stromové automaty.

2.Stromové automaty shora dolů - nedeterministické, deterministické.

3.Stromové automaty zdola nahoru - nedeterministické, deterministické.

4.Vyhledávání vzorků ve stromech - algoritmy založené na stromových automatech.

5.Vyhledávání vzorků ve stromech - jiné známé algoritmy.

6.Stromové automaty a zásobníkové automaty

7.Vyhledávaní vzorků ve stromech pomocí zásobníkového automatu.

8.Indexování stromu.

9.Vyhledávání repetic ve stromech.

10.Přibližné vyhledávání ve stromech - Hamingova vzdálenost.

11.Přibližné vyhledávání ve stromech - Levensteinova vzdálenost.

12.Automaty a úlohy pro zpracování XML.

13.Pokrývání stromu - generování kódu v tvorbě překladačů.

Osnova cvičení:
Cíle studia:

Stromové datové struktury představují jednu ze základních datovych struktur ve vypočetní technice. Předmět studenty seznamuje s principy efektivních algoritmů pracujících se stromy pro úlohy jako jsou například přijetí a překlad stromových jazyků, vyhledávání přesných vzorků ve stromu, přibližné vyhledávání ve stromu nebo indexace stromu pro různé typy stromů (seřazené a neseřazené stromy, stromy s uzly s aritou a bez arity). Algoritmy jsou prezentovány na základe existujících vypočetních modelů pro stromové jazyky, jako jsou například ruzné druhy stromových automatů (finite tree automata, tree walking automata, atd.) nebo zásobníkové automaty. Předmět demonstruje také praktické použití těchto algoritmů v úlohách jako jsou různá zpracování formátu XML nebo výběr instrukcí při generování kódu.

Studijní materiály:

Cleophas, L.: Tree Algorithms. Two Taxonomies and a Toolkit, Technische Universiteit Eindhoven, Eindhoven, 2008

Gecseg, F, Steinby, M. Tree Languages, In: Vol 3: Beyond Words. Handbook of Formal Languages. pp. 1 -- 68, Springer, Berlin, Heidelberg, 1997.

Hoffman, C. M., O'Donnell M. J. Pattern Matching in Trees. Journal of ACM, vol. 29, pp. 68 -- 95, 1982.

Janoušek, J., Melichar, B. On Regular Tree Languages and Deterministic Pushdown Automata. In Acta Informatica, Vol. 46, No. 7, pp. 533-547, Springer, 2009.

Poznámka:
Rozvrh na zimní semestr 2019/2020:
Rozvrh není připraven
Rozvrh na letní semestr 2019/2020:
Rozvrh není připraven
Předmět je součástí následujících studijních plánů:
Platnost dat k 17. 9. 2019
Aktualizace výše uvedených informací naleznete na adrese http://bilakniha.cvut.cz/cs/predmet1600906.html