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í
- 1.termín zkoušky se koná v úterý 3.1. od 13:00. Rozdělení studentů do místností je následující:
- D105: A.-Ml.
- D0206: Mo.-Ž.
S sebou psací potřeby, průkaz s fotografií a eventuálně lahev s pitím.
Na vypracování budete mít 150 minut.
Plán pro zimní semestr 2022
|
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 19.9. |
Úvod do jazyků a gramatik + regulární jazyky 1 |
Formální jazyky,operace nad nimi a konstrukce pro regulární jazyky |
|
|
2. týden |
od 26.9. |
Regulární jazyky 2 |
Pumping lemma, Myhill-Nerodova věta a uzávěrové vlastnosti |
|
|
3. týden |
od 3.10. |
Bezkontextové jazyky 1 |
|
Regulární jazyky |
|
4. týden |
od 10.10. |
Bezkontextové jazyky 2 |
Konstrukce a Pumping lemma pro bezkontextové jazyky |
|
14.10. od 12:00 -- První vnitrosemestrální test (Regulární jazyky) |
5. týden |
od 17.10. |
Turingovy stroje 1 |
|
Konstrukce a transformace pro bezkontextové jazyky |
|
6. týden |
od 24.10. |
Turingovy stroje 2, vztah TS k vyčíslitelným funkcím |
|
* svátek 28.10. Pumping lemma uzávěrové vlastnosti a algoritmy pro bezkontextové jazyky |
|
7. týden |
od 31.10. |
Nerozhodnutelnost 1 |
|
Turingovy stroje a rozhodnutelnost |
|
8. týden |
od 7.11. |
Nerozhodnutelnost 2 |
|
Opakování před testem |
|
9. týden |
od 14.11. |
Gödelova nerozhodnutelnost |
Nerozhodnutelnost |
|
18.11. od 12:00 -- Druhý vnitrosemestrální test (Bezkontextové jazyky + Turingovy
stroje) |
10. týden |
od 21.11. |
Složitost 1 |
|
Nerozhodnutelnost |
|
11. týden |
od 28.11. |
Složitost 2 |
Složitost |
|
|
12. týden |
od 5.12. |
Složitost 3 |
|
Gödelova nerozhodnutelnost a složitost |
|
13. týden |
od 12.12. |
Hromadná konzultace |
Složitost |
Změna, tento týden proběhne democvičení. |
|
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í.
Vyučující
Studijní materiály
- Prezentace z přednášek budou průběžně doplňovány (starší prezentace
dostupné zde):
- Materiály k demo cvičením a numerickým cvičením budou průběžně doplňovány:
- Studijní text (opora): pdf.
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 4. a 8. 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 18.11. 2022). 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:
|