Úvod

Vítejte na našech stránkách zabývající se tématikou teoretické informatiky

Najde zde hlavně ukázky a příklady z oblastí:

Úvod, aplikace teorie formálních jazyků, modelovací a rozhodovací síla formálního modelu, operace nad jazyky. Regulární jazyky a jejich vlastnosti, Kleenova věta, Nerodova věta, věta o vkládání (Pumping theorem). Minimalizace konečného automatu, relace nerozlišitelnosti stavů, konstrukce redukovaného konečného automatu. Uzávěrové vlastnosti regulárních jazyků, regulární jazyky jako množinová Booleova algebra, rozhodnutelné problémy regulárních jazyků. Bezkontextové jazyky a jejich vlastnosti. Normální tvary bezkontextových gramatik, jednoznačné a deterministické bezkontextové jazyky, věta o vkládání pro bezkontextové jazyky. Uzávěrové vlastnosti bezkontextových jazyků, uzavřenost vzhledem k substituci, důsledky, rozhodnutelné problémy bezkontextových jazyků. Turingovy stroje (TS), definice TS a jazyka přijímaného TS, rekurzivně vyčíslitelné a rekurzivní jazyky a problémy, TS a funkce, metody konstrukce TS. Modifikace TS, TS s obousměrně nekonečnou páskou, s více páskami, nedeterministický TS, stroj se dvěma zásobníky, stroje s čitači. TS a jazyky typu 0, diagonalizace, vlastnosti rekurzivních a rekurzivně vyčíslitelných jazyků, lineárně ohraničené automaty a jazyky typu 1. Vyčíslitelné funkce, počáteční funkce, primitivně rekurzivní funkce, mí-rekurzivní funkce, vztah vyčíslitelných funkcí a Turingových strojů. Church-Turingova téze, univerzální TS, nerozhodnutelnost, problém zastavení TS, redukce, Postův korespondenční problém. Nerozhodnutelné problémy teorie formálních jazyků. Úvod do výpočetní složitosti, Turingovská složitost, třída P a NP problémů.

Dále zde najde i řešené příklady a ukázky z:

Konečné automaty a regulární gramatiky: Pumping lemma, Nerodova věta, minimalizace, nedeterministické konečné automaty. Vlastnosti regulárních jazyků: uzávěrové vlastnosti, regulární výrazy, Kleeneho věta, konečnost. Bezkontextové gramatiky a jazyky: transformace bezkontextových gramatik, vybrané normální formy, pumping lemma, uzávěrové vlastnosti. Zásobníkové automaty a jejich vztah k bezkontextovým gramatikám: nedeterministická syntaktická analýza shora dolů a zdola nahoru. Deterministické zásobníkové automaty.

a mnoho dalšího...

To stále ještě nekončí:

    • Konečné automaty a regulární jazyky, Nerodova věta, ekvivalence a redukce automatů, nedeterminismus.

    • Uzávěrové vlastnosti, regulární výrazy, Kleeneova věta, pumping (iterační) lemma. Gramatiky, Chomského hierarchie, regulární, bezkontextové a kontextové gramatiky

    • Bezkontextové gramatiky, derivace, redukce, normální tvary, pumping (iterační) lemma, uzávěrové vlastnosti, deterministické a nedeterministické zásobníkové automaty.

    • Rekurzivně spočetné jazyky, Turingovy stroje, algoritmicky nerozhodnutelné problémy

Na závěr je zde ještě pár vychytávek pro nejtvrdší drsňáky a to přímo od pana Kozena!

Důkazy, důkazy, důkazy...

Pokud máte vypočítaný příklad, se kterým se chcete pochlubit, můžete mi ho poslat a já ho sem vložím.