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í
-
4. termín z TINu proběhne v pondělí 21.2. od
10:00 v učebně A218.
Počítám, že se dostaví studenti, kteří se přihlásili
v dotazníku na moodle a studenti, kteří se se mnou osobně
domluvili. Pokud má ještě někdo právo na 4. termín a chtěl
by dorazit, prosím napište mi - učebna má omezenou kapacitu.
-
Hromadná konzultace k hodnocení 3. termínu proběhne
v pondělí (14.2.) od 10:00 v místnosti A218.
-
Hromadná konzultace k hodnocení 2. termínu proběhne
v středu (26.1.) od 13:00 v místnosti A218.
- 2. termín žávěrečné zkoušky se
koná 19.1. od 13:00 v místnosti D105.
Na řešení budete mít k dispozici 2:30 čistého času.
S sebou si přineste psací potřeby, průkaz s fotografií a eventuelně
láhev s pitím. Papíry dostanete od nás v dostatečném množství. Při
použití jakýchkoliv nepovolených pomůcek bude zkouška hodnocena 0
body a budou zváženy další kroky.
Pokud Vám nebude dobře, prosím zůstaňte doma a omluvte se oficielní cestou. Váš výkon u zkoušky by navíc neodpovídal vaším možnostem.
-
Hromadná konzultace k hodnocení 1. termínu proběhne
v pondělí (17.1.) od 12:00 v místnosti A218
-
Konzultace k hodnocení Vašich testů proběhne v úterý
(14.12.) po ukončení hromadné konzultace k TINu.
Předpokládaný start je kolem 15:30 v místnosti D105.
Pokud se někdo z vážných důvodů (např. kolize s výukou či
nemoc) nemůže dostavit a chtěl by hodnocení konzultovat,
ozvěte se emailem (ceskam@fit.vutbr.cz).
- Záznam democvičení z 22.10. bohužel není kompletní. Místo toho můžete využít záznam z minulého roku (democvičení z 16.10. 2010), kde se dělají z velké části stejné příklady (ignorujte začátek na regulární jazyky).
- Na základě Vaších žádostí a současné epidemiologické situace opět zprovozníme youtube stream z přednášek TINu. Stream bude dostupný na
odkazu
https://youtube.com/playlist?list=PL_eb8wrKJwYskX8EJeqE2n6qJgqNbT-z3.
- 1. průběžný test se koná dne 22.10. od 14:00 do
16:00.
Rozdělení studentů do učeben bude následující:
- D105: A. - M.
- E112: N. - Šťa.
- G108: Ště. - Ž.
Na řešení budete mít k dispozici 2 hodinu čistého času.
S sebou si přineste psací potřeby, průkaz s fotografií a eventuelně
láhev s pitím. Papíry dostanete od nás v dostatečném množství. Při
použití jakýchkoliv nepovolených pomůcek bude zkouška hodnocena 0
body.
- Po skončení 1. průběžného testu bude následovat democvičení TIN v
místnosti D105 (začátek cca 16:10).
-
V uterý 19.10 začne přednáška v 14:30 a bude probíhat v učebně D0206.
- Hromadná konzultace k 1. testu proběhem v pondělí 18.10 od
11.00 v místnosti D0206. Jelikož nelze zajistit dostatečnou
kapacitu učeben, konzultace bude streamována na odkazu
https://youtube.com/playlist?list=PL_eb8wrKJwYskX8EJeqE2n6qJgqNbT-z3
(záznam bude dostupný ihned na youtube).
- Vzhledem ke schůzce studentů a pedagogů ke kvalitě výuky
na FIT, která je plánována na úterý 19.10 od 14:00, jsem se
(zatím předběžně) domluvil s panem proděkanem, že TIN začne
o 30 minut později (tj. v 14:30). Toto dovolí jak mně, tak i
Vám se schůzky aspoň částečně zúčastnit. V prvních zhruba
15-20 minutách budu odpovídat studentům na dotazy ohledně
TIN a MSP. Pak budete mít možnost se krátce zapojit do
diskuze. V 14:30 se přesuneme na přednášku TIN.
Z kapacitních důvodů možná dojde k prohození učeben (tj. TIN
by byl v D0206). Prosím sledujte stránky předmětu TIN, kde
bude upřesněno, jak a kde bude výuka v úterý 19.10 probíhat.
- Na základě Vašich žádostí dojde k prohození dema a prvního
testu. Tudíž test se bude psát v pátek 22.10. od 14:00
(rozdělení studentů do učeben zveřejníme příští týden na
stránkách předmětu). Test bude na 2 až 2.5 hodiny. Poté bude
krátká přestávka a budeme pokračovat v demu v místnosti
D105.
- 1. test bude na regulární jazyky a bude obsahovat jak
otázky na teorii, tak příklady, které budou testovat
pochopení probírané látky. U testu nebudou povoleny žádné
studijní materiály. Další organizační pokyny budou
zveřejněný příští týden na stránkách předmětu.
- Záznamy z 3. týdne výuky (2. přednáška a 2. demo na téma
pokročilé aspekty regulárních jazyků) budou zveřejněny
nejpozději do konce tohoto týdne.
Pokud máte k organizaci příštího týdne jakékoliv dotazy,
napište mi email či využijte diskuzní fórum předmětu na
platformě moodle.vut. Rovněž prosím sledujte aktuální
informace na stránkách předmětu, kde budeme průběžně
informace doplňovat.
Plán pro zimní semestr 2021
|
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 20.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 27.9. |
Státní svátek |
|
Konstrukce a transformace pro regulární jazyky |
|
3. týden |
od 4.10. |
Regulární jazyky 2 |
Pumping lemma, Myhill-Nerodova věta a uzávěrové vlastnosti |
|
|
4. týden |
od 11.10. |
Bezkontextové jazyky 1 |
|
Pumping lemma, Myhill-Nerodova věta a uzávěrové vlastnosti |
|
5. týden |
od 18.10. |
Bezkontextové jazyky 2 |
Konstrukce a Pumping lemma pro bezkontextové jazyky |
|
22.10. od 14:00 -- První vnitrosemestrální test (Regulární jazyky) |
6. týden |
od 25.10. |
Turingovy stroje 1 |
|
Konstrukce a transformace pro bezkontextové jazyky |
|
7. týden |
od 1.11. |
Turingovy stroje 2 |
|
Pumping lemma uzávěrové vlastnosti a algoritmy pro bezkontextové jazyky |
|
8. týden |
od 8.11. |
Nerozhodnutelnost 1 |
|
Turingovy stroje a rozhodnutelnost |
|
9. týden |
od 15.11. |
Nerozhodnutelnost 2 |
|
Opakování před testem |
|
10. týden |
od 22.11. |
Vyčíslitelné funkce a Gödelova nerozhodnutelnost |
Nerozhodnutelnost |
|
26.11. od 14:00 -- Druhý vnitrosemestrální test (Bezkontextové jazyky + Turingovy
stroje) |
11. týden |
od 29.11. |
Složitost 1 |
|
Nerozhodnutelnost |
|
12. týden |
od 6.12. |
Složitost 2 |
Složitost |
|
|
13. týden |
od 13.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
14: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
- 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 6. a 11. týdnu semestru a v 1. týdnu zkouškového období.
Úlohy na procvičení
- Sbírka příkladů s řešením typových úloh je k dispozici zde (verze z 23.12. 2021). Pokud v řešení naleznete chybu, napište email na ceskam@fit.vutbr.cz -- můžete získat prémiové body.
- Zadání domácích úloh z minulých let jsou k dispozici zde,
nebo v dokumentovém skladu ve Wisu.
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:
|