I1 Teoretická informatika

1. Teoretická informatika I1

Garantující pracoviště: Katedra teoretické informatiky a matematické logiky
Oborový garant: prof. RNDr. Roman Barták, Ph.D.

Povinné předměty

Povinně volitelné předměty

Je požadováno splnění povinně volitelných předmětů z následujícího seznamu v rozsahu alespoň 60 kreditů:

Zaměření: Algoritmy a složitost

Zkušební okruhy

1. Rekurze a strukturální složitost

2. Obecná teorie algoritmů

3. Konkrétní algoritmy

Zkušební požadavky

1. Rekurze a strukturální složitost
Aritmetická hierarchie tříd množin, třídy nekonečných větví rekurzivních stromů. Věta o nízké bázi. Diagonálně nerekurzivní funkce, význam a aplikace. Základy aritmetického forcingu, 1-generické množiny. Algoritmická náhodnost, 1-náhodné množiny – základní vlastnosti. Existence těžkých problémů (Shannonova věta), pravděpodobnostní třídy složitosti a jejich vlastnosti, neuniformní třídy složitosti a jejich vlastnosti, polynomiální hierarchie, vztahy tříd složitosti definovaných pomocí různých prostředků, separace různých tříd složitosti, vlastnosti řídkých množin, základy kryptografie.

Doporučené předměty: NTIN073 Rekurze I, NTIN074 Rekurze II, NTIN081 Strukturální složitost I, NTIN082 Výpočetní složitost 
Rozšiřující předměty: NTIN085 Vybrané kapitoly z výpočetní složitosti I, NTIN086 Vybrané kapitoly z výpočetní složitosti II 

2. Obecná teorie algoritmů
Pravděpodobnostní a randomizované algoritmy: jejich popis a parametry kvantifikující jejich vlastnosti, třídy složitosti pravděpodobnostních algoritmů (BPP, RP, ZPP a příklady problémů v těchto třídách), pravděpodobnostní binární vyhledávací stromy.

Paralelní algoritmy: modely paralelních počítačů, počítače první a druhé třídy a paralelní teze, techniky paralelních algoritmů. Dolní odhady, P-úplnost, NC- a AC-třídy.

Deterministické algoritmy: různé typy složitosti (složitost v nejhorším případě, složitost v průměrném případě, amortizovaná složitost). Distribuce vstupních dat, statistické metody odhady doby výpočtu na základě experimentů, interpretace výsledků statistických metod.

Doporučené předměty: NTIN063 Složitost II, NTIN017 Paralelní algoritmy, NTIN018 Pravděpodobnostní analýza algoritmů, NTIN081 Strukturální složitost I, NMAI060 Pravděpodobnostní metody, NMAI061 Metody matematické statistiky 
Rozšiřující předměty: NDMI025 Pravděpodobnostní algoritmy 

3. Konkrétní algoritmy
Třídící algoritmy: algoritmy založené na porovnávání prvků (Shellsort, Mergesort, Heapsort, Quicksort) a jejich složitost, algoritmy založené na adresovacích metodách (Bucketsort, Hybridsort). Hledání mediánu a k-tého prvku. Třídící sítě, paralelní Mergesort, externí třídící algoritmy.

Algebraické algoritmy: algoritmy založené na algoritmech pro násobení matic, rychlá diskrétní Fourierova transformace. LUP-dekompozice matic. Testy prvočíselnosti.

Grafové algoritmy: testy planarity, maximální tok v síti a jeho aplikace (párování, k-souvislost), transitivní uzávěr, metoda Eulerových cyklů, paralelní algoritmy pro souvislost a dvousouvislost grafu, hledání minimální kostry a hledání nejkratší cesty v grafech.

Algoritmy testování splnitelnosti Booleovských formulí.

Doporučené předměty: NTIN067 Datové struktury II, NDMI010 Grafové algoritmy, NTIN017 Paralelní algoritmy, NAIL021 Booleovské funkce a jejich aplikace, NDMI025 Pravděpodobnostní algoritmy 
Rozšiřující předměty: NDMI007 Kombinatorické algoritmy, NTIN081 Strukturální složitost I, NTIN084 Bioinformatické algoritmy, NTIN085 Vybrané kapitoly z výpočetní složitosti I, NTIN086 Vybrané kapitoly z výpočetní složitosti II, NAIL025 Evoluční algoritmy I, NAIL086 Evoluční algoritmy II, NTIN087 Textové algoritmy, NAIL094 Rozhodovací procedury a verifikace

Zaměření: Neprocedurální programování a umělá inteligence

Zkušební okruhy

1. Logika a výpočtová složitost

2. Umělá inteligence

3. Neprocedurální programování

4. Neuronové sítě

5. Adaptivní agenti a evoluční algoritmy

6. Robotika

Zkušební požadavky

1. Logika a výpočtová složitost
Formální systémy, logika 1. řádu, jazyk, axiomy, odvozovací pravidla. Výroková logika, sémantika výrokové logiky, tautologie a splnitelnost, dokazatelnost, věta o dedukci, věta o kompaktnosti a věty o úplnosti. Konjunktivně-disjunktivní a disjunktivně-konjunktivní tvary formulí.

Predikátová logika, realizace jazyka, splňování a pravdivost formulí. Teorie 1. řádu, dokazatelnost, věta o dedukci, věta o konstantách, prenexní tvary formulí. Věta o korektnosti. Věta o úplnosti, Henkinovy teorie, úplné teorie. Rozšíření teorie, konservativní rozšíření, rozšíření teorie o definice funkcí a predikátů.

Míry výpočtové složitosti, třídy složitosti (P, NP, PSPACE, NPSPACE, LOGSPACE), NP-těžké a NP-úplné úlohy. Složitost algoritmů v umělé inteligenci, prohledávání, rezoluční odvozování.

Doporučené předměty: NAIL062 Výroková a predikátová logika, NTIN062 Složitost I 

2. Umělá inteligence
Reprezentace znalostí: stavový prostor, produkční systémy, reprezentace v predikátové logice. Prohledávací algoritmy; stromové, grafové a lokální prohledávání, heuristiky, algoritmus A* a jeho varianty. Hry; minimax a alfa-beta algoritmy. Splňování omezujících podmínek. Strojové dokazování vět, model checking (DPLL), dopředné a zpětné řetězení, rezoluční metoda a unifikace. Automatické plánování; plánovací doména a problém, plánovací operátory. Zpracování neurčité informace; Bayesovské sítě, podmíněná nezávislost, výpočet v Bayesovské síti, rozhodovací grafy, Markovské modely, Kalmanův filtr. Strojové učení; prohledávání prostoru verzí, rozhodovací stromy, Bayesovské učení, maximálně věrohodná hypotéza, EM algoritmus, zpětnovazební učení.

Doporučené předměty: NAIL069 Umělá inteligence I, NAIL070 Umělá inteligence II 
Rozšiřující předměty: NAIL004 Seminář z umělé inteligence I, NAIL052 Seminář z umělé inteligence II, NAIL021 Booleovské funkce a jejich aplikace, NAIL031 Reprezentace booleovských funkcí, NAIL029 Strojové učení, NOPT042 Programování s omezujícími podmínkami, NAIL071 Plánování a rozvrhování, NAIL068 Umělé bytosti, NAIL094 Rozhodovací procedury a verifikace 

3. Neprocedurální programování
Odlišnost procedurálního a neprocedurálního způsobu programování. Principy funkcionálního a logického programování. Lambda kalkulus, syntax, volné a vázané proměnné a principy redukce. Churchova a Rosserova vlastnost a konsistence kalkulu. Věty o pevném bodu. Normální tvar objektů. Typovaný lambda kalkul. Curryho a Churchovy systémy typování. Základní charakteristiky funkcionálních jazyků.

Hornova logika, Hornovy klausule. Substituce, unifikace a jejich vlastnosti. SLD-resoluce a logické programy. Korektnost a úplnost SLD-resoluce. Negace definovaná neúspěchem, obecné logické programy. Čistý Prolog jako podmnožina Prologu. Postačující podmínky ukončení výpočtu. Unifikace bez kontroly výskytu proměnných. Implementace Prologu. Programování s omezujícími podmínkami: inferenční a prohledávací algoritmy splňování podmínek.

Doporučené předměty: NAIL078 Lambda-kalkulus a funkcionální programování I, NAIL076 Logické programování I, NOPT042 Programování s omezujícími podmínkami 
Rozšiřující předměty: NAIL079 Lambda-kalkulus a funkcionální programování II, NAIL077 Logické programování II, NAIL022 Metody logického programování, NAIL006 Seminář z logického programování I, NAIL009 Seminář z logického programování II 

4. Neuronové sítě
Neurofyziologické minimum: struktura neuronu, typy synapsí, hlavní části mozku. Modely pro učení s učitelem: perceptron, algoritmus zpětného šíření, strategie pro urychlení učení, interní reprezentace znalostí, generalizace, regularizační techniky. Asociativní paměti; Hebbovské učení, BAM, Hopfieldův model, energetická funkce a hledání suboptimálních řešení. Stochastické modely; simulované žíhání, Boltzmannův stroj. Umělé neuronové sítě založené na principu učení bez učitele; Ojův algoritmus učení, laterální inhibice, Kohonenovy mapy a jejich varianty pro učení s učitelem, sítě typu ART. Modulární, hierarchické a hybridní modely neuronových sítí; adaptivní směsi lokálních expertů, vícevrstvé Kohonenovy mapy, RBF-sítě, kaskádová korelace. Genetické algoritmy, věta o schématech. Aplikace umělých neuronových sítí a evolučních technik (analýza dat, bioinformatika, zpracování obrazové informace, robotika a další).

Doporučené předměty: NAIL002 Neuronové sítě, NAIL013 Aplikace teorie neuronových sítí 
Rozšiřující předměty: NTIN084 Bioinformatické algoritmy, NAIL060 Implementace neuronových sítí I, NAIL015 Implementace neuronových sítí II, NAIL065 Evoluční robotika, NDBI023 Dobývání znalostí 

5. Adaptivní agenti a evoluční algoritmy
Architektura autonomního agenta; percepce, mechanismus výběru akcí, paměť; psychologické inspirace. Metody pro řízení agentů; řídící architektury podle Wooldridge, symbolické a konekcionistické reaktivní plánování, hybridní přístupy (Belief Desire Intention, Soar), srovnání s plánovacími technikami. Problém hledání cesty; navigační pravidla, reprezentace terénu. Komunikace a znalosti v multiagentních systémech, ontologie, problém omezené racionality, Kripkeho sémantika možných světů. Etologické motivace, modely populační dynamiky. Metody pro učení agentů; zpětnovazební učení, základní formy učení zvířat.

Umělá evoluce; genetické algoritmy, genetické a evoluční programování. Základní přístupy a pojmy: populace, fitness, rekombinace, genetické operátory; dynamická vs. statická selekce, mechanismus rulety, turnaje, elitismus. Reprezentační schémata, hypotéza o stavebních blocích. Pravděpodobnostní modely jednoduchého genetického algoritmu. Koevoluce, otevřená evoluce. Aplikace evolučních algoritmů (výběr akcí, evoluce expertních systému, konečných automatů, adaptace evolučních pravidel, neuroevoluce, řešení kombinatorických úloh).

Doporučené předměty: NAIL068 Umělé bytosti, NAIL025 Evoluční algoritmy I, NAIL086 Evoluční algoritmy II, NAIL087 Informatika a kognitivní vědy I 
Rozšiřující předměty: NAIL071 Plánování a rozvrhování, NAIL054 Adaptivní agenti, NAIL086 Evoluční algoritmy II, NAIL082 Seminář z umělých bytostí, ALGV00003 Úvod do teoretické sémantiky (předmět je vyučován na Filosofické fakultě UK), NAIL065 Evoluční robotika, NAIL002 Neuronové sítě, NAIL088 Informatika a kognitivní vědy II, NAIL106 Multiagentní systémy

6. Robotika
Řídící systém robota: základní modely, řízení, kinematika, autonomní systémy, mobilní systémy. Lokalizace: absolutní a relativní, lokální a globální, lokalizace v dynamickém prostředí, pravděpodobnostní lokalizace. Mapování, simultánní lokalizace a mapování. Plánování aktivit: plánování ve stavovém prostoru a v prostoru plánu, práce s časem a zdroji. Kognitivní robotika: modely, senzorika, zpracování dat, rozpoznávání. Multi-robotické systémy: základní modely, synchronizace a kooperace, plánování. Softwarová realizace: návrh systému, modelování, simulace, programování pro specifické běhové prostředí.

Doporučené předměty: NAIL028 Úvod do mobilní robotiky, NPGR001 Počítačové vidění a inteligentní robotika, NAIL071 Plánování a rozvrhování, NSWE001 Vestavěné systémy a systémy reálného času
Rozšiřující předměty: NAIL029 Strojové učení, NAIL065 Evoluční robotika, NAIL068 Umělé bytosti, NAIL025 Evoluční algoritmy I, NAIL101 Pravděpodobnostní robotika, NAIL070 Umělá inteligence II