Arbologie

Garant předmětu:

Jan Janoušek, Bořivoj Melichar

Přednášející:

Cvičící:

Jan Janoušek, Bořivoj Melichar

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

Rozvrh není připraven

Rozvrh na letní semestr 2023/2024:

Rozvrh není připraven

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

• Informatika (doktorská) (povinně volitelný předmět)
• Informatika (povinně volitelný předmět)