I1 - Teoretická informatika

Garantující pracoviště: Katedra teoretické informatiky a matematické logiky
Odpovědný učitel: Doc. 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ů:

Studijní plán: Algoritmy a složitost

Garantující pracoviště: Katedra teoretické informatiky a matematické logiky
Odpovědný učitel: RNDr. Václav Koubek, DrSc.

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. Minimální stupně. Algoritmická náhodnost, 1-náhodné množiny. Strukturální složitost, Shanonova věta, pravděpodobnostní a neuniformní třídy složitosti, polynomiální hierarchie a vztah k ostatním třídám. Úplné problémy, řídké množiny a množiny nad jednoprvkovou abecedou a separace tříd složitosti pomocí nich. Relativizace. Biimunost a silná biimunost. Low and high hierarchie.

2. Obecná teorie algoritmů
Pravděpodobnostní a randomizované algoritmy: měření jejich složitosti a odhad chyby, generování náhodných dat, třídy algoritmů BPP (Atlantic City), RPP (Monte Carlo), ZPP (Las Vegas).

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.

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, rychlé násobení čísel a polynomů, algoritmy založené na násobení čísel nebo polynomů. 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 bisouvislost grafu.

Algoritmy testování splnitelnosti pro speciální třídy boolovských formulí.

Studijní plán: Neprocedurální programování a umělá inteligence

Garantující pracoviště: Katedra teoretické informatiky a matematické logiky
Odpovědný učitel: Prof. RNDr. Petr Štěpánek, DrSc.

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

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

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, 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, d-separace, 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í.

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.

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. Klastrovací techniky a samoorganizace; k-means algoritmus, hierarchické shlukování, evoluční stromy. 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, sítě se vstřícným šířením, 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ší).

5. Adaptivní agenti a evoluční algoritmy
Agenti a animati; virtuální svět, autonomie. Architektura agentů; deliberativní, reaktivní, hybridní. Metody pro řízení agentů; symbolické a konekcionistické reaktivní plánování, hybridní přístupy (BDI, Soar), srovnání s plánovacími technikami, etologické motivace. Problém hledání cesty; navigační pravidla, reprezentace terénu. Simulace stádního chování. Komunikace a znalosti v multiagentních systémech, ontologie, problém omezené racionality, Kripkeho sémantika možných světů. Metody pro učení agentů; zpětnovazební učení.

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émů, konečných automatů, adaptace evolučních pravidel, neuroevoluce, řešení kombinatorických úloh).