Arbologie

Přednášející:

Bořivoj Melichar (gar.)

Cvičící:

Bořivoj Melichar (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:

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 2011/2012:

Rozvrh není připraven

Rozvrh na letní semestr 2011/2012:

Rozvrh není připraven

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

• Informatika (VO)