Jste zde

Matematické základy teorie formálních jazyků

S kolegou Lukášem Vrábelem jsme dokončili projekt, který jsme vypracovali v rámci získaného FRVŠ grantu za rok 2012. Týkal se matematických základů teorie formálních jazyků. O výsledky bych se chtěl podělit v následujícím příspěvku.

Co byla naším cílem

V současné době je na Fakultě informačních technologií Vysokého učení technického v Brně vyučována řada předmětů, jejichž jádro tvoří teorie formálních jazyků. V těchto předmětech však není prostor k vysvětlení matematických základů, na kterých teorie formálních jazyků, a potažmo celá teoretická informatika, stojí. Tyto základy by studentům měly dát povinné matematické prerekvizitní předměty, kterou jsou ovšem zaměřeny velice obšírně. Taktéž nevysvětlují návaznost a využití nabytých znalostí v dalších oblastech. Studenti si pak mnohdy neuvědomují fundamentální význam matematických konceptů a důležitost formálních zápisů.

Cílem tohoto projektu bylo vytvoření studijních podkladů, které studenty provedou základy matematiky v úzké návaznosti na teorii formálních jazyků. Názorně by jim měly ukázat využitelnost matematické notace a ozřejmit důvody použití rigorózních postupů. Důraz je kladen na osvětlení problematiky na příkladech a analogií z oblastí, které jsou studentům blízké (např. programovací jazyky).

Jelikož je většina literatury zabývající se formálními jazyky psána v angličtině, je naprosto nezbytné seznámit studenty s anglickou terminologií, a proto jsou výukové materiály vytvořeny v angličtině. Studenti se tak seznámí se současnou, ve světě používanou notací, což je připraví na práci ve špičkových týmech mimo Českou republiku, kde mohou být tyto znalosti požadovány.

Co jsme vyprodukovali

Projekt, včetně jeho výstupů, je prezentován na internetových stránkách fakulty, konkrétně na adrese

http://www.fit.vutbr.cz/~izemek/frvs2012

Zde je k dispozici jako doplňkový zdroj informací studentům všech předmětů, které se teoretickou informatikou zabývají (i mimo fakultu).

V rámci řešení projektu byly vypracovány následující výstupy:

  • Studijní text. Anglicky psaný text, který studenty seznamuje s matematickými základy teorie formálních jazyků a teoretické informatiky jako takové. Učí je formálním zápisům, vysvětluje přínos matematiky a návaznost na teorii formálních jazyků. Formát i styl výkladu je uzpůsoben tomu, aby k pochopení textu bylo třeba minimum dodatečných materiálů.
  • Prezentace k textu. Pět elektronických prezentací, které umožňují přednášejícímu projít se studenty některé obzvláště náročné pasáže ze studijního textu. Jejich hlavním cílem není nahrazení studijního textu, nýbrž usnadnění práce přednášejícímu. Konkrétně se jedná o následující prezentace:
    • Sets. Základy teorie množin, především co to jsou množiny, jak je lze zapisovat, vztahy mezi množinami, speciální množiny a operace nad množinami.
    • Sequences, Relations, and Functions. Jsou vysvětleny posloupnosti, relace a funkce.
    • Finite Automata. Tato prezentace se zabývá formální definicí konečného automatu, relace přechodu, výpočtu a přijímaného jazyka. Jsou využity koncepty z předchozích dvou prezentací.
    • Closures. Vysvětlení konceptu uzávěru relací, který slouží pro snadnější definici výpočtu prováděného konečným automatem.
    • Mathematical Statements and Their Proofs. Zdůvodnění, proč jsou důkazy v matematice důležité, ukázka obecného tvaru matematických tvrzení, typy tvrzení a jejich důkazy. 
  • Bonusové prezentace. Bylo vytvořeno sedm bonusových elektronických prezentací diskutujících pokročilá témata z moderní teorie formálních jazyků, které v současné době nejsou součástí ani doktorských předmětů. Prezentace jsou založeny na dalších článcích řešitelů tohoto projektu. Konkrétně se jedná o následující prezentace:

Komentáře

Pěkná práce :)
Mohu se zeptat, odkud pochází (předpokládám LaTeX-ová) šablona těch prezentací? Pokud to teda není "tajné". Na webu fakulty jsem ji nenalezl.

Jedná se o mírně upravenou verzi FIT šablony pro prezentace. Pokud je mi známo, tak není veřejně dostupná.

Přidat komentář