..:: Martin Kot ::..
Úvod do teoretické informatiky - šk. rok 2005/6
Aktuální informace
29.06.2006 Výsledky z dnešního termínu zkoušky již jsou v katisu. Zapsat body do indexu a prohlédnout písemky bude možné 3.7. ve 13:00 na J401. Poté už je zapisování do indexu možné jen po domluvě (e-mail, telefonicky) se Zdeňkem Sawou.
15.06.2006 Výsledky ze zkoušky z 15.6. budou v katisu 16.6. Na opravené písemky se můžete podívat a do indexu zapsat 26.6. ve 13 hodin na J401. Zapsat známku bude možné i ze starších termínů, starší písemky doneseme na podívání jen na požádání mailem.
08.06.2006 Bylo povoleno přihlašování na poslední termín zkoušky 29.6.2006. Více termínů již nebude.
03.06.2006 Výsledky zkoušky z 2.6. budou v KatISu 5.6., následující den 6.6. ve 13 hodin na J401 bude možnost se na opravené zkoušky podívat, ale bez možnosti zapsání bodů do indexu (hlavně pro ty, kdo chtějí znát chyby a jít na opravu 8.6.). 12.6. ve 13:00 na J401 se na písemky taky bude možné podívat (z 2.6. i 8.6.) a také zapsat zkoušku do indexu.
25.05.2006 V sekci ke stažení mezi příklady na cvičení je zveřejněno ukázkové zadání zkouškové písemky. Samozřejmě se na zkoušce mohou vyskytnout i jiné příklady. Jde hlavně o ukázání rozsahu a přibližné obtížnosti připravovaných zadání.
19.05.2006 V KatISu bylo povoleno přihlašování na termíny zkoušek (2.6., 8.6., 15.6.).
24.04.2006 Zveřejněna poslední 3 zadání bonusových referátů.
24.04.2006 Ve čtvrtek 27.04.2006 se učí podle pondělního rozhrhu, takže nejsou přednášky ani čtvrteční cvičení. Skupiny, které mívají cvičení v pondělí, mají tento týden dvě (v pondělí a ve čtvrtek).
06.04.2006 V pondělí bylo zveřejněno bonusové zadání č. 10 a dnes na přednášce č. 11. Zadání č. 11 je zároveň první, které bylo úspěšně vyřešeno a už za něj není možné získat body. Aktuální stav řešení bonusů sledujte na stránce věnované projektům úplně dole.
31.03.2006 V zádání zápočtového příkladu č. 36 opravena drobná chyba, která znamenala neexistenci požadovaného řešení
25.03.2006 Zveřejněno dalších 6 bonusových příkladů
24.03.2006 Písemka se bude psát na přednáškách 13.4.2006. Učivo bude z přednášek 1-5, příklady typově podobné na ty, které jsou ve cvičeních 1-5.
17.03.2006 Zveřejněno další zadání bonusového příkladu
09.03.2006 Zveřejněna zadání prvních 2 bonusových příkladů. Odkaz naleznete v sekci "Projekty" (tam jsou i pokyny k vypracování a seznam již vyřešených) i v sekci "Ke stažení"
20.02.2006 Zveřejněna zadání všech povinných zápočtových příkladů. Odkaz i s pokyny k vypracování najdete v sekci "Projekty".
 
Průběh přednášek
25.2.2006
  • Seznámení s podmínkami předmětu
  • Formální jazyky a operace s nimi
  • Motivační příklady pro zavedení konečných automatů
2.3.2006
  • Vyhledávání řetězce v textu
  • Formální definice deterministického konečného automatu
  • Uzávěrové vlastnosti regulárních jazyků - konstrukce automatu pro sjednocení a průnik jazyků, doplněk jazyka
  • Definice nedeterministického konečného automatu (zatím ne zobecněného)
9.3.2006
  • Nedeterministické a zobecněné nedeterministické automaty
  • Převod nedeterministických automatů (i zobecněných) na deterministické
  • Konstrukce pro zřetězení, iteraci, sjednocení regulárních jazyků
  • Uzavřenost třídy regulárních jazyků vůči různým operacím
  • Regulární výrazy
  • Převod regulárních výrazů na konečné automaty
  • Převod konečného automatu na regulární výraz (jen v 8:00 na B5)
  • Použití regulárních výrazů v praxi (jen v 8:00 na B5)
16.3.2006
  • Normovaný tvar automatu
  • Minimalizace konečného automatu
  • Ekvivalence konečných automatů
  • Motivace k pumping lemma a jeho znění zatím bez využití k důkazům neregularity jazyka
23.3.2006
  • Pumping lemma
  • Myhill-Nerodova věta
  • Bezkontextové gramatiky - definice, příklady
  • Derivace, levá a pravá derivace, derivační strom
  • Bezkontextové jazyky
30.3.2006
  • Zásobníkové automaty
  • Ekvivalence zásobníkových automatů a bezkontextových gramatik
  • Turingovy stroje
  • Lineárně omezený automat
  • Chomského hierarchie jazyků
6.4.2006
  • Definice problému, rozhodovací a optimalizační problémy
  • Kódování vstupu a výstupu
  • Algoritmus, funkce realizovaná algoritmem
  • Modely výpočtu - stroj RAM, Turingův stroj
  • Churchova-Turingova teze
  • Nerozhodnutelné problémy - Halting problém a další příklady
  • Redukce mezi problémy
20.4.2006
  • Složitost algoritmu v nejhoším, průměrném a nejlepším případě
  • Rychlost růstu funkcí, asymptotická notace
  • Prostorová složitost algoritmu
  • Složitost problému
  • Definice třídy časové složitosti a třídy prostorové složitosti
  • Třída PTIME
4.5.2006
  • Odhad složitosti rekurentních vztahů (Master teorém, ...)
  • Třídy složitosti problémů (PTIME, PSPACE, EXPTIME, EXPSPACE, LOGSPACE, ...)
  • Vztahy mezi třídami složitosti
  • Horní a dolní odhady složitosti problémů
  • Dolní odhad pro problém třídění
11.5.2006
  • Nedeterministický Turigův stroj a nedeterministiký RAM
  • Pojem nedeterminismu
  • Nedeterministické třídy složitosti (NPTIME, NPSPACE)
  • Polynomiální převoditelnost
  • NP-obtížnost, NP-úplnost
  • Cookova věta (SAT je NP-úplný) s náznakem důkazu
18.5.2006
  • Problém 3-SAT, převod SAT na 3-SAT
  • Problém barvení grafu 3 barvami (3-COL) a převod 3-SAT na 3-COL
  • Problém nezávislé množiny (IS) a převod 3-COL na IS
  • Problém vrcholového pokrytí (VC) a převod IS na VC
  • Problémy Hamiltonovský cyklus (HC) a Hamiltonovská kružnice (HK) a převod HC na HK
  • Problém obchodního cestujícího (TSP) a převod HK na TSP
  • Problém loupežníka (PART) a převod 3-SAT na PART