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í


Plán pro zimní semestr 2025


Data Téma přednášky Democvičení (pátek od 10:00) Cvičení (ve skupinách dle rozvrhu) Další aktivity
1. týden od 15.9. Přednáška mimořádně proběhne ve středu
Úvod a motivace do studia formálních jazyků + Úvod do regulárních jazyků
Opakování diskrétní matematiky + Formální jazyky
2. týden od 22.9. Pokročilé aspekty regulárních jazyků Regulární jazyky
3. týden od 29.9. Bezkontextové jazyky (**) Páteční cvičení od 13:00
Úvod do bezkontextových jazyků
pátek 3.10. od 10:00 -- První vnitrosemestrální test (Regulární jazyky)
4. týden od 6.10. Turingovy stroje a rozhodnutelnost Bezkontextové jazyky + Turingovy stroje a rozhodnutelnost
5. týden od 13.10. Úvod do složitosti Bezkontextové jazyky + Turingovy stroje a rozhodnutelnost
6. týden od 20.10. Analýzy složitosti mimo Turingovy stroje + Amortizovaná složitost Asymptotická a amortizovaná analýza složitosti Odevzdání 1. úkolu
7. týden od 27.10. Vlastnosti složitostních tříd + Polynomiální redukce (*) Svátek 28.10.
Analýza složitosti I
8. týden od 3.11. Regex Matching (od regulárních výrazů přes automaty a algoritmy ke složitosti a bezpečnosti) Analýza složitosti II
9. týden od 10.11. Nerozhodnutelnost Pokročilá složitost + Polynomiální redukce čtvrtek 13.11. od 18:00 -- Druhý vnitrosemestrální test (Bezkontextové jazyky + Turingovy stroje + složitost)
10. týden od 17.11. Přednáška odpadá Nerozhodnutelnost: použití redukce a diagonalizace
11. týden od 24.11. Logické systémy pro výrokovou a predikátovou logiku Nerozhodnutelnost: použití redukce
12. týden od 1.12. Gödelovy věty o neúplnosti logických systémů Logické systémy Odevzdávání 2. úkolu
13. týden od 8.12. Hromadná konzultace Neúplnost logických systémů

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 10:00 v E112 (+ E104 + E105). 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 bude pořízen záznam. I tak ale prosím pokud možno přijďte osobně.


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ě.

Domácí úkoly

Součástí bodového hodnocení předmětu jsou 2 domácí úlohy. Zadání úloh a pokyny pro vypracování budou postupně zveřejněny na e-learningu VUT.

Úlohy na procvičení



Odkazy na WWW

Jsou průběžně doplňovány...