Teoretická informatika (TIN) - informace pro studenty
Tato stránka obsahuje aktuální informace k předmětu TIN, studijní materiály, termíny zkoušek a dosažené
výsledky. Obecné informace o předmětu naleznete na adrese
http://www.fit.vut.cz/study/course/TIN/.
Aktuální upozornění
- Zadána 1. domácí úloha. Termín odevzdání je stanoven na 30.10.
- Informace o organizaci výuky během uzavření fakulty pro prezenční
výuku budou průběžně zveřejňovány ve WISu ve fóru předmětu: TIN:
organizace předmětu v období zrušené prezenční výuky
Plán pro zimní semestr 2020
|
Data |
Téma přednášky |
Democvičení (pátek od 13:00) |
Cvičení (ve skupinách dle rozvrhu) |
Další aktivity |
1. týden |
od 21.9. |
Úvod do jazyků a gramatik + regulární jazyky 1 |
Formální jazyky,operace nad nimi a konstrukce obecných gramatik |
|
|
2. týden |
od 28.9. |
Regulární jazyky 2 |
Konstrukce pro RJ a Pumping lemma |
|
|
3. týden |
od 5.10. |
Bezkontextové jazyky 1 |
|
Konstrukce pro RJ a Pumping lemma |
|
4. týden |
od 12.10. |
Bezkontextové jazyky 2 |
Konstrukce pro bezkontextové jazyky |
|
15.10. od 18:00 -- První vnitrosemestrální test (Regulární jazyky) |
5. týden |
od 19.10. |
Turingovy stroje 1 |
|
Transformace bezkontextových gramatik a jenodznačnost |
|
6. týden |
od 26.10. |
Turingovy stroje 2 |
|
Pumping lemma a pokročilé konstrukce pro bezkontextové jazyky |
|
7. týden |
od 2.11. |
Nerozhodnutelnost 1 |
|
Turingovy stroje 1 |
|
8. týden |
od 9.11. |
Nerozhodnutelnost 2 |
|
Opakování před testem |
|
9. týden |
od 16.11. |
|
Nerozhodnutelnost |
|
19.11. od 18:00 -- Druhý vnitrosemestrální test (Bezkontextové jazyky + Turingovy
stroje) |
10. týden |
od 23.11. |
Vyčíslitelné funkce a Gödelova nerozhodnutelnost |
|
Nerozhodnutelnost |
|
11. týden |
od 30.11. |
Složitost 1 |
Složitost 1 |
|
|
12. týden |
od 7.12. |
Složitost 2 |
Složitost 2 |
|
|
13. týden |
od 14.12. |
Hromadná konzultace |
|
Složitost |
|
Semináře a cvičení
V rámci TIN se budou nepravidelně střídat demonstrační cvika (demo) a cvičení ve skupinách po
cca 45 studentech (numerická cvičení). Demonstrační cvičení budou probíhat v pátek od
13:00 v D105. Numerická cvičení pak v termínech vypsaných v rozvrhu a ve WISu.
V rámci každého týdne výuky budou vždy buď pouze democvičení, nebo pouze numerická
cvičení.
Vyučující
Studijní materiály
Referenční literatura
Zejména na těchto textech je předmět vystavěn. U knih v angličtině (zejména knihy D.C. Kozen a Hopcroft, J.E. et al) doporučujeme
možnost do těchto knih nahlédnout
(příp. si je vypůjčit) v knihovně FIT -- jedná se o velmi kvalitní texty používané na
řadě univerzit ve světě.
- Češka, M.: Teoretická informatika, učební text FIT VUT v Brně,
2002. Viz výše uvedená elektronická verze.
- Kozen, D.C.: Automata and Computability, Springer-Verlag, New York, Inc, 1997. ISBN 0-387-94907-0
- Černá, I., Křetínský, M., Kučera, A.: Automaty a formální jazyky
I, učební text FI MU, Brno, 1999.
- Hopcroft, J.E., Motwani, R., Ullman, J.D.: Introduction to Automata Theory, Languages, and
Computation, Addison Wesley, 2. vydání, 2000. ISBN 0-201-44124-1
- Gruska, J.: Foundations of Computing, International Thomson
Computer Press, 1997. ISBN 1-85032-243-0
- Bovet, D.P., Crescenzi, P.: Introduction to the Theory of
Complexity, Prentice Hall Europe, Pearson Education Limited, 1994. ISBN
0-13-915380-2
- Meduna, A.: Formal Languages and Computation, CRC Press, 2014, ISBN
978-1-46651345-7 (k dispozici v knihovně FIT)
Domácí úkoly
Součástí bodového hodnocení předmětu jsou 3 domácí úlohy. Jejich zadání se
postupně bude objevovat v této části stránek předmětu. Úlohy se budou odevzdávat ve 6. a 11. týdnu semestru a v 1. týdnu zkouškového období.
Pozor na opisování! Při opravování úkolů více než dříve kontrolujeme opisování.
Opsané nebo i jen částečně opsané úkoly jsou hodnoceny 0 body, a to pro autora opsaného
i pro autora zdrojového textu. Vážně, doopravdy, kontrolujeme to a rozdáváme nuly.
Můžete řešení úkolu probrat s kolegy, ale nepřežeňte to, a určitě si neukazujte
vypracovaná řešení. Tak jen velmi těžko vytvoříte řešení, kde se na stejných
řádcích vyskytuje skoro stejný text... Buďte opatrní na to, komu svůj úkol dáváte ke
čtení nebo kam jej posíláte. Řada případů opisování se děje bez autorova vědomí. Dále
upozorňujeme, že některá internetová fóra jsou otevřená a nejsou anonymní. Často
obsahují chyby, podle kterých se potom zvlášť dobře identifikují podobná vypracování
úkolů.
Vypracování a odevzdávání úloh:
Úlohu můžete napsat rukou, na počítači, nebo libovolně kombinovat tyto
možnosti (např. napsat text na počítači a doplnit obrazky rukou). Ručně
napsané části pak naskenujte, nebo nafoťte a celou úlohu převeďte do
jednoho souboru ve formátu PDF. Odevzdávat se bude prostřednictvím https://moodle.vutbr.cz
Seznam domácích úloh:
- Úkol 1 (5 bodů): pdf - opravuje
A. Rogalewicz, termín odevzdání: pátek 30.10. do 23:59.
Soubor PDF odevzdejte prostřednictvím https://moodle.vutbr.cz
- Úkol 2 (5 bodů): pdf - opravuje
O. Lengál, termín odevzdání: pátek 4.12. do 23:59.
Soubor PDF odevzdejte prostřednictvím https://moodle.vutbr.cz
- Úkol 3 (5 bodů): pdf - opravuje
L. Holík, termín odevzdání: úterý 5.1. do 23:59.
Soubor PDF odevzdejte prostřednictvím https://moodle.vutbr.cz
Úlohy na procvičení
Zde se budou postupně (koncem každého týdne) přidávat úlohy na procviční aktuálně probírané látky
Doporučujeme si tyto úlohy
projít, zkusit vyřešit a v případě nejasnosti se zeptat
(domluvit si konzultaci), a to pokud možno ještě před zkouškou... V případě zájmu/potřeby je možno najít
také jistě řadu dalších zadání na webu -- najdete-li něco zajímavého i pro ostatní, pošlete odkaz
do fóra předmětu.
Příklady označené * jsou náročnější a patří do kategorie příkladů do domácích úloh. Proto se nebojte, že by se příklady této náročnosti mohly objevit na testech případě na zkoušce.
Odkazy na WWW
Jsou průběžně doplňovány...
- Skripta Teoretická informatika, pokrývající část přednášené látky:
pdf.
- Javier Esparza: Automata theory, an
algorithmic approach. Konečné automaty nad konečnými a nekonečnými slovy,
konečné převodníky, aplikace automatů, vazba na logiku.
- Warshalův algoritmus pro
výpočet tranzitivního uzávěru relace. Slidy
zde
- Důkaz ekvivalence kontextových a nezkracujících gramatik: pdf.
- Řecká abeceda: pdf.
- Encyklopedie -- můžete je s výhodu využít pro vyhledání významu neznámých pojmů z matematiky,
příp. i teoretické informatiky:
- Knihovny pro práci s konečnými automaty a jejich (často netradiční a zajímavé využití nejen v oblasti
překladačů):
- FSA. Knihovna napsaná v Prologu,
snadno použitelná, poměrně výkonná, linkovatelná z jiných jazyků. Zahrnuje převodníky
a vážené automaty. Využití mj. ve formální verifikaci či v lingvistice. Dá se snadno použít
také pro experimenty s různými jazykovými operacemi.
- Mona. Knihovna pro práci s logikami WS1S a
WS2S založená na velmi optimalizované implementaci konečných automatů nad slovy a také nad
stromy (ty lze použít i samostatně). Celá řada aplikací v oblasti formální verifikace,
symbolických výpočtů apod. Obecně řeší některé problémy o neelementární složitosti, tj. složitosti
vyjádřené věží exponenciál, jejíž výška není konstantní, ale závisí na vstupní instanci
(zkuste se mimochodem zamyslet, udělat si pár výpočtů, jak rychle taková složitost roste).
- Timbuk. Knihovna pro práci
se stromovými automaty v jazyce Ocaml. Aplikace ve verifikaci, analýze kryptografických
protokolů apod.
- LASH. Nástroj pro
symbolickou analýzu systémů popsaných pomocí soustav lineárních rovnic nad celočíselnými
či reálnými čísly. Nekonečné množiny celočíselných/reálných vektorů jsou reprezentovány
konečnými automaty nad konečnými či nekonečnými slovy (Büchiho automaty -- nepřijímají
pochopitelně zastavením v koncovém stavu, ale namísto toho nekonečným cyklením přes
přijímající stav).
- VATA.
Knihovna pro práci s konečnými a konečnými stromovými automaty. Je založená na
efektivních algoritmech, které umožňují práci přímo s nedeterministickými automaty bez
nutnosti determinizace.
- Kleeneho algebry: D. Kozen.
A Completeness Theorem for Kleene Algebras and the Algebra of Regular Events.
Information and Computation, 1994.
- Známé otevřené problémy matematiky (The Millenium Prize Problems) včetně otázky,
zda P = NP: pro zájemce je možno doporučit mj. zajímavou knihu Keith Devlin:
Problémy pro třetí tisíciletí, Nakladatelství Dokořán a Argo, 2005.
(Z anglického originálu The Millennium Problems: The Seven Greatest Unsolved Mathematical Puzzles of Our Time, Basic Books, 2002.)
Za vyřešení každého z těchto problémů je vypsána odměna 1.000.000 USD.
- Složitost:
- First-Order Logic Glossary
-- některé pojmy z oblasti logiky, teorie množin, rekurzívních funkcí.
- Pro zájemce o skutečně zásadní poznatky --
Gödelovy teorémy
a z nich plynoucí meze formálního usuzování. Mimochodem Kurt Gödel je rodák z Brna (podle něj je pojmenována posluchárna E112).
- Zajímavosti:
|