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, domácí úkoly atd.
Domácí úlohy a diskuzní fóra jsou k dispozici na e-learningu VUT.
Aktuální upozornění
Hromadná konzultace k hodnocení 2. testu proběhne v pondělí 27.11.
po přednášce z TINu (tj. zhruba od 13.15) v místnosti D105. Pro účely zpětné vazby jsme zveřejnili zadání 2. testu:
varianta A a
varianta B.
Příští pondělí (tj. 13.11.) od 8:00 proběhne 2. test z TINu. Test bude zaměřen na bezkontextové jazyky a Turingovy stroje včetně důkazů (částečné) rozhodnutelnosti (další informace viz hromadný email).
Zde najdete ukázku 2. testu z minulého roku.
V čtvrtek 9.11. od 14:00 se v místnosti M104+M105 bude konat náhradní termín za 1.test, kterého se mohou zúčastnit studenti, kteří byli řádně omluveni (nemoc, jiná omluvenka) z řádného termínu.
Abychom připravili správný počet zadaní, prosím požádejte do 7.11. 23:59 o náhradní termín pomocí skupiny založené v e-learningu.
Hromadná konzultace k hodnocení 1. testu proběhne v pondělí 23.10.
po přednášce z TINu (tj. zhruba od 13.00 – přednáška bude zkrácena) v místnosti D105.
Pro účely zpětné vazby jsme zveřejnili zadání 1. testu:
varianta A,
varianta B a
komentář k řešení a nejčastější chyby.
1. test z TINu se uskuteční tento pátek (to je 13.10.). Na základě
Vašich žádostí dojde k prohození dema a testu. Tudíž test se
bude psát od 14:00 v učebně D105. Poté se uskuteční democvičení
ve stejné učebně.
Plán pro zimní semestr 2023
|
Data |
Téma přednášky |
Democvičení (pátek od 14:00) |
Cvičení (ve skupinách dle rozvrhu) |
Další aktivity |
1. týden |
od 18.9. |
Úvod a motivace do studia formálních jazyků + regulární jazyky 1 |
Opakování diskrétní matematiky + formální jazyky |
|
|
2. týden |
od 25.9. |
Regulární jazyky 2 |
Regulární jazyky |
|
|
3. týden |
od 2.10. |
Bezkontextové jazyky 1 |
|
Regulární jazyky |
|
4. týden |
od 9.10. |
Bezkontextové jazyky 2 |
Bezkontextové jazyky |
|
pátek 13.10. od 17:00 -- První vnitrosemestrální test (Regulární jazyky) |
5. týden |
od 16.10. |
Turingovy stroje 1 |
|
Bezkontextové jazyky 1 |
|
6. týden |
od 23.10. |
Turingovy stroje 2 + vztah TS k vyčíslitelným funkcím |
|
Bezkontextové jazyky 2 |
Odevzdávání 1. úkolu |
7. týden |
od 30.10. |
Nerozhodnutelnost |
|
Turingovy stroje a rozhodnutelnost |
|
8. týden |
od 6.11. |
Logika 1 (axiomatizace) |
Nerozhodnutelnost |
|
|
9. týden |
od 13.11. |
Logika 2 (Gödelova nerozhodnutelnost) |
|
Nerozhodnutelnost pátek 17.11. svátek |
pondělí 13.11. od 8:00 -- Druhý vnitrosemestrální test (Bezkontextové jazyky + Turingovy stroje a rozhodnutelnost) |
10. týden |
od 20.11. |
Složitost 1 |
|
Logika 1 |
Odevzdávání 2. úkolu |
11. týden |
od 27.11. |
Složitost 2 |
Logika 2 |
|
|
12. týden |
od 4.12. |
Složitost 3 |
Složitost |
|
|
13. týden |
od 11.12. |
Hromadná konzultace |
|
Složitost |
Odevzdávání 3. úkolu |
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 14:00 v D105. Numerická cvičení pak v termínech
vypsaných v rozvrhu a ve STUDISUu.
V rámci každého týdne výuky budou vždy buď pouze democvičení, nebo pouze
numerická cvičení.
Z demonstračních cvičení a z přednášek (od 2. týdne) bude k dispozici stream přes YouTube i záznam. I tak ale prosím pokud možno přijďte osobně.
Vyučující
- garant/přednášky/numerická cvičení/testy během semestru: doc. RNDr. Milan Češka,
Ph.D.
(konzultace v předem neomezených termínech na základě vzájemné dohody se zájemci e-mailem)
- zástupce garanta/democvičení/numerická cvičení: Prof. Ing. Tomáš Vojnar, Ph.D.
(konzultace v předem neomezených termínech na základě vzájemné dohody se zájemci e-mailem)
- numerická cvičení/úkoly: doc. Mgr. Adam Rogalewicz, Ph.D.
(konzultace v předem neomezených termínech na základě vzájemné dohody se zájemci e-mailem)
- numerická cvičení/úkoly: doc. Mgr. Lukáš Holík, Ph.D.(konzultace v předem neomezených termínech na základě vzájemné dohody se zájemci e-mailem)
- numerická cvičení/úkoly: Ing. Ondřej Lengál, Ph.D.
(konzultace v předem neomezených termínech na základě vzájemné dohody se zájemci e-mailem)
Studijní materiály
- Prezentace z přednášek budou průběžně doplňovány (starší prezentace
dostupné zde):
- Studijní text (opora): pdf.
- Materiály k demo cvičením a numerickým cvičením budou průběžně doplňovány:
-
Demo 1: opakování z diskrétní matematiky,
jazyky a gramatiky
-
Demo 2: KA, Pumping lemma pro regulární jazyky
-
Cvičení 1: Pumping lemma pro regulární jazyky,
Myhill-Nerodova věta
-
Demo 3: ZA, konstrukce algoritmů, Pumping lemma pro
bezkontextové jazyky, uzávěrové vlastnosti
-
Cvičení 2: transformace bezkontextových gramatik,
jednoznačnost, DZA, syntaktická analýza
-
Cvičení 3: Pumping lemma pro bezkontextové jazyky,
konstrukce algoritmů
-
Cvičení 4: Turingovy stroje, rozhodnutelnost
-
Demo 4: nerozhodnutelnost
-
Cvičení 5: nerozhodnutelnost (redukce, diagonalizace)
-
Cvičení 6: logika (normální formy výrokové logiky;
jazyk, teorie, modely, bezespornost, úplnost,
rozhodnutelnost predikátové logiky)
-
Demo 5: logika +
poznámky
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.
Zadání úloh a pokyny pro vypracování budou postupně zveřejněny na e-learningu VUT.
Úlohy se budou odevzdávat ve 6. a 10. a 13. týdnu semestru.
Úlohy na procvičení
- Sbírka příkladů s řešením typových úloh je k dispozici zde (verze z 8.12.2023). Pokud v řešení naleznete chybu, napište email na ceskam@fit.vutbr.cz -- můžete získat prémiové body.
- Řešení (téměř) všech příkladů se sbírky, které vypracoval a poskytl Tomáš Kocourek najdete zde (verze z 31.12 2022). Jde o neoficiální studijní materiál, který neprošel korekturou ze strany vyučujích předmětu TIN. Silně doporučujeme ho využít pouze jako kontrolu vlastních řešení.
- Zadání domácích úloh z minulých let jsou k dispozici zde.
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:
|