| KMI/PGSIM |
Uspořádané množ. a teorie svazů pro inf. |
5 |
20+0+0S |
B |
| |
|
Anotace kurzu:
Uspořádané množiny, speciální prvky v uspořádaných množinách. Svazy a polosvazy. Úplné svazy. Modulární a distributivní svazy. Komplementární a relativně komplementární svazy. Ideály a kongruence ve svazech. Booleovy algebry.
Rámcový obsah kurzu:
Předmět seznamuje studenty s uspořádanými množinami a důraz je kladen na speciální uspořádané množiny - svazy. Probrány jsou vlastnosti svazů: vztah svazů jako uspořádaných množin a jako algeber, úplnost svazů a vlastnosti dané identitami (modularita, distributivita). Dále je věnována pozornost vztahu ideálů a jader kongruencí, komplementárním svazům, Booleovým algebrám a dalším speciálním svazům, které hrají roli v neklasických logikách.
1. Úvodní pojmy z teorie svazů
Uspořádané množiny. Typy uspořádání. Hasseovy diagramy. Polosvazy a svazy jako uspořádané množiny a jako algebraické struktury. Významné prvky svazů, spojová a průseková ireducibilita prvků. Úplné svazy. Algebraické svazy. Distributivní svazy a jejich charakterizace. Modulární svazy. Komplementární svazy. Relativně komplementární svazy.
2. Kongruence a ideály
Kongruence, tolerance, faktorové svazy. Ideály, svazy ideálů. Vztah mezi kongruencemi a ideály. Prvoideály a maximální ideály.
3. Booleovy svazy a Booleovy algebry
Booleovy svazy. Booleovy algebry a jejich vlastnosti. Úplné Booleovy algebry. Booleovy okruhy. Booleovské funkce, polynomy, úplné disjunktivní a konjuktivní normální formy. Logické obvody a jejich vztah k Booleovským funkcím. Minimalizační metody.
4. Další témata
Pseudokomplenety, pseudokomplementární svazy, Glivenkova kongruence, relativně pseudokomplementární svazy.
|
| KMI/PGSIU |
Univerzální algebra pro informatiky |
5 |
20+0+0S |
B |
| |
|
Anotace kurzu:
Seznamit studenty s obecnými algebraickými konstrukcemi a hlavními
výsledky dosaženými v univerzální algebře.
Rámcový obsah kurzu:
Kurs studenty seznamuje s obecnými algebraickými konstrukcemi a hlavními
výsledky dosaženými v univerzální algebře. Úvod kursu je věnován algebrám
a hlavním algebraickým konstrukcím: podalgebrám, morfismům, součinům,
subdirektní reprezentaci algeber a podobně. Další partie kursu se věnují
třídám algeber definovatelným pomocí identit a kvaziidentit a jejich
algebraické charakterizaci pomocí uzavřenosti na jisté operátory
(Birkhoffova věta o varietách, charakterizace kvazivariet). Kurs je
ukončen vybranými partiemi týkajícími se aplikací výsledků univerzální
algebry v informatice.
|
| KMI/PGDA |
Paralelní a distribuované algoritmy |
5 |
20+0+0S |
B |
| |
|
Anotace kurzu:
Studenti se seznámí s vybranými problémy řešenými distribuovanými algoritmy.
Rámcový obsah kurzu:
V předmětu jsou studovány vybrané problémy v distribuovaných systémech a algoritmy jejich řešení. Předmět rozšiřuje úvodní partie z magisterského studia.
Snímkové a vlnové algoritmy.
Vzájemné vyloučení a detekce uváznutí a terminace.
Garbage collection: počítání referencí a trasování.
Směrovací algoritmy.
Volba lídra.
Anonymní a synchronní sítě.
Byzantská dohoda.
Stabilizace algoritmů.
|
| KMI/PGFL |
Fuzzy logika |
5 |
20+0+0S |
B |
| |
|
Anotace kurzu:
Studenti se seznámí se základními pojmy z fuzzy logiky.
Rámcový obsah kurzu:
Struktury pravdivostních hodnot: Reziduované svazy a jejich vlastnosti. Podtřídy reziduovaných svazů dané identitami: MTL-algebry, BL-algebry, MV-algebry, G-algebry, Pi-algebry. Filtry na reziduovaných svazech. Subdirektní reprezentace MTL a BL-algeber.
Výroková BL-logika a její schématická rozšíření: Jazyk výrokové BL-logiky, formule, axiomatický systém. Odvozené logické spojky. Dokazatelnost, věta o dedukci. Korektnost a úplnost výrokové BL-logiky. Schématické rozšíření, Lukasiewiczova logika, Goedelova logika, produktová logika a jejich standardní úplnost.
Pavelkova abstraktní logika: Logika s ohodnocenou syntaxí. Teorie jako fuzzy množiny formulí. Vážené důkazy a stupně dokazatelnosti. Obecný koncept úplnosti v Pavelkově stylu. Příklady konkrétních kalkulů: Pavelkova racionální logika a důkaz úplnosti.
Predikátová BL-logika a další logiky: Fuzzy struktury, safe interpretace. Úplnost predikátové BL-logiky. Výroková a predikátová MTL-logika. Rozšíření logik o unární spojky (Baazovo delta a jiné). Fuzzy logika versus modality a zobecněné kvantifikátory. Fuzzy logické kalkuly pracující s formulemi ve speciálním tvaru: fuzzy ekvacionální logika, fuzzy hornovská logika, logika fuzzy atributových implikací.
Fuzzy struktury a jejich vlastnosti: Fuzzy množiny a fuzzy relace (v naivním smyslu) jako speciální fuzzy struktury. Vlastnosti fuzzy struktur. Reprezentace fuzzy struktur pomocí klasických množin (řezová reprezentace). Speciální fuzzy relace: podobnost, fuzzy rovnost. Kompatibilita a zachovávání podobnosti. Řezová sémantika.
|
| KMI/PGFM |
Fuzzy množiny a jejich aplikace |
5 |
20+0+0S |
B |
| |
|
Anotace kurzu:
Zvládnout základy teorie fuzzy množin a vybrané aplikace.
Rámcový obsah kurzu:
Předmět podává přehled o teorii fuzzy množin a jejich vybraných aplikacích, je zaměřen na vybrané aktuální oblasti výzkumu.
Struktury pravdivostních hodnot, logické spojky ve fuzzy logice, t-(ko)normy, reziduované svazy, agregace, věty o reprezentaci.
- Fuzzy množiny, fuzzy relace, operace s fuzzy množinami a fuzzy relacemi, reprezentace řezy, zobecněné fuzzy množiny. Základní typy fuzzy relací na množině, stupňovité vlastnosti fuzzy relací. Speciální typy fuzzy množin (fuzzy čísla a intervaly). Zobecněné fuzzy množiny (typu 2) a jejich algebra.
Fuzzy množiny a fuzzy relace -- pokročilé partie.
Fuzzy relační rovnice, jejich řešitelnost, metody řešení, aplikace.
- Fuzzifikace, intuitivní postup, postup z hlediska fuzzy logiky, základní požadavky. Princip rozšíření.
Fuzzifikace, základní požadavky, možné přístupy a jejich porovnání. Principy rozšíření.
Pravidlové fuzzy systémy a fuzzy regulátory, inference, fuzzifikace a defuzifikace, univerzální aproximační schopnost různých systémů.
Fuzzy shlukování.
Fuzzy množiny a databáze, relační model dat nad doménami s podobností. Fuzzy množiny a získávání informací (information retrieval).
Fuzzy automaty, fuzzy jazyky. Různé přístupy a aplikace.
|
| KMI/PGFP |
Funkcionální programování |
5 |
20+0+0S |
B |
| |
|
Anotace kurzu:
Studenti se seznámí se základními pojmy z funkcionálního programování.
Rámcový obsah kurzu:
Předmět se zabývá metodami funkcionálního programování, vztahem k lambda kalkulu a souvisejícími výpočetními modely. Obsah je zaměřen na teoretické aspekty funkcionálního programování a výrazně rozšiřuje úvodní představení základních konceptů v bakalářském a magisterském studiu.
Funkcionální programování a lambda kalkul: Syntax lambda výrazů a jejich vyhodnocování. Aplikace funkcí a currying, Lambda abstrakce. Operační sémantika lambda kalkulu: vázané a volné proměnné, beta-konverze, alfa-konverze; vzájemná zastupitelnost. Přepisovací systémy, terminace, konfluence, Churchova-Rosserova vlastnost, normální formy. Vazba na čistý lambda kalkul. Reprezentace booleovských formulí, přirozených čísel, $n$-tic. Vyčíslitelné funkce: lambda-vyčíslitelné, totální rekurzivní, částečné rekurzivní. Věty o pevném bodu, nerozhodnutelné vlastnosti. Rekurzivní funkce, Y kombinátor jako lambda abstrakce. Denotační sémantika lambda kalkulu. Překlad vyššího programovacího jazyka do lambda kalkulu: let-výrazy, letrec-výrazy, strukturované typy a porovnávání se vzory.
Funkcionální programování a uspořádané algebry: Specifikace abstraktních datových typů: vícedruhové algebry, jejich podalgebry, morfismy a součiny; princip konečné algebraické rekurze; ekvacionální teorie, vícedruhová ekvacionální logika; ekvacionální specifikace; počáteční sémantika a operační sémantika. Uspořádané algebry, jejich morfismy a součiny. Uspořádané variety a jejich charakterizace pomocí volných uspořádaných algeber. Logika nerovností (inekvacionální logika). Striktní uspořádané algebry, omega-uspořádané algebry. Rekurzivní schémata funkcionálních programů a jejich sémantika, vypočtené hodnoty, symbolická řešení, sémantické ekvivalence.
Zásobníkový model vyhodnocování symbolických výrazů: Funkcionální programy jako posloupnosti symbolických výrazů. Zásobníkový vyhodnocovací proces. Elementy jazyka: primitivní a definované procedury (funkce), speciální formy, makra, prostředí, páry. Rozšiřování vyhodnocovacího procesu: lexikální a dynamické vazby, líné vyhodnocování, vyhodnocování s vyrovnávací pamětí, imperativní rysy, únikové funkce, aktuální pokračování, nedeterminismus a paralelismus. Metody implementace interpretů a překladačů funkcionálních programovacích jazyků.
|
| KMI/PGKA |
Formální konceptuální analýza |
5 |
20+0+0S |
B |
| |
|
Anotace kurzu:
Studenti se seznámí se základními pojmy z formální konceptuální analýzy.
Rámcový obsah kurzu:
Pozornost je věnována dvěma základním výstupům konceptuální analýzy -- konceptuálním svazům a atributovým implikacím. Důraz je kladen na teoretické základy a algoritmy pro vybrané problémy. Samostatná část kursu je věnována rozšířením konceptuální analýzy z pohledu vícehodnotových logik, zejména fuzzy logiky.
Formální kontext a konceptuální svaz:
Úvod do formální konceptuální analýzy. Formální kontext, formální koncept, konceptuální svaz. Matematické struktury na pozadí konceptuální analýzy: Galoisovy konexe a uzávěrové operátory. Hlavní věta o konceptuálních svazech. Vícehodnotové kontexty,
škálování a faktorizace konceptuálních svazů.
Atributové implikace:
Atributové implikace: definice pojmu, atributové implikace jako predikátové formule, pravdivost atributových implikací. Atributové implikace generované z dat: úplné množiny atributových implikací, neredundantní báze kontextů, minimální báze kontextů. Stanovení minimálních bází pomocí pseudo-intentů. Vztah atributových implikací a funkčních závislostí. Vztah atributových implikací a asociačních pravidel.
Algoritmy:
Algoritmy pro výpočet konceptuálního svazu. Neinkrementální algoritmy (Ganterův algoritmus, Lindigův algoritmus, Titanic). Analýza složitosti algoritmů. Inkrementální algoritmy. Algoritmy pro výpočet minimálních bází kontextů.
Úplné kongruence a uzavřené podrelace:
Úplné tolerance a blokové relace. Dimenze kontextu. Morfismy kontextů. Měření, škálové míry.
Rozšíření z pohledu vícehodnotových logik:
Fuzzy kontexty, fuzzy koncepty, fuzzy konceptuální svazy. Hlavní věta fuzzy konceptuálních svazů. Metody redukce počtu fuzzy konceptů. Metody faktorizace fuzzy konceptuálních svazů pomocí relace podobnosti. Atributové implikace mezi fuzzy atributy: atributové implikace jako formule, pravdivost implikací, sémantické vyplývání a jeho axiomatizace, hledání minimálních bází.
Vybrané aplikace formální konceptuální analýzy:
Information retrieval, softwarové inženýrství, neredundantní báze asociačních pravidel, faktorová analýza.
|
| KMI/PGKK |
Kvantová kryptografie pro informatiky |
5 |
20+0+0S |
B |
| |
|
Anotace kurzu:
Kurz podává základní přehled o využití principů kvantové mechaniky v oblasti bezpečné výměny společného šifrovacího klíče. Cílem kurzu je porozumět základním kvantově-informačním principům, fyzikálním metodám a experimentálním aplikacím kvantové kryptografie a také poznat současné problémy tohoto oboru. Student má získat praktické dovednosti v aplikaci kvantové mechaniky při přenosu informace.
Rámcový obsah kurzu:
1. Matematický základ kvantové mechaniky: Hilbertův prostor nad tělesem komplexních čísel, ortonormalita vektorů, vlastnosti a reprezentace operátorů, tenzorový součin Hilbertových prostorů, vlastnosti projektorů, kompletně positivní mapy.
2. Fyzikální principy kvantové mechaniky: postuláty kvantové mechaniky, kvantová interference, porušení lokálního realismu klasické teorie, evoluce kvantových systémů, kvantové kanály, měření v kvantové mechanice.
3. Kvantová informace: kvantový bit, kvantový analogový signál, diskriminace kvantových stavů, kvantové klonování, kvantová provázanost, míry kvantové provázanosti.
4. Kvantové kanály, klasická a kvantová kapacita kvantového kanálu, kvantové kódy.
5. Principy kvantové kryptografie: protokol Bennet-Brassard (BB84), protokol Bennet (B92), protokol s využitím provázaných stavů.
6. Podmíněná a nepodmíněná bezpečnost kvantové kryptografie, kvantové opakovače, optimální individuální a kolektivní odposlech, nepodmíněná bezpečnost, robustnost kvantové kryptografie.
7. Experimentální realizace kvantové kryptografie: fotonové protokoly, protokoly s koherentními stavy a provázanými stavy, kvantové paměti, experimentální realizace kvantových opakovačů.
8. Současné problémy kvantové kryptografie.
9. Kryptografické protokoly s více účastníky: kvantová provázanost mezi více účastníky, GHZ a W stavy, kvantové sdílení tajemství.
|
| KMI/PGLP |
Logické programování |
5 |
20+0+0S |
B |
| |
|
Anotace kurzu:
Studenti se seznámí se základními pojmy z logického programování.
Rámcový obsah kurzu:
Předmět podrobněji seznamuje studenty s logickým programováním, nad rámec úvodního představení v magisterském studiu. Je zaměřen na teoretické aspekty logického programování související se sémantikami logického programu, modely jeho výpočtu a propojením s predikátovou logikou.
Logické programování. Logický program a jeho sémantika: Logické paradigma jako jedno z paradigmat programování. Definitní programy a jejich syntaxe. Klauzule, fakta, pravidla a dotazy. Deklarativní sémantika definitního programu: Herbrandova struktura, Herbrandův model, nejmenší Herbrandův model a jeho nalezení. Sémantické vyplývání z definitních programů. Substituce, aplikace substituce, uzavřené instance klausulí, korektní odpovědi. Čisté logické programování a PROLOG.
Procedurální sémantika logického programu. Rekurzivní datové struktury: konečné a nekonečné Herbrandovy modely. Rekurzivní pravidla. Unifikace. Nedeterministická inference. Metody odstranění nedeterminismu. Nejobecnější unifikátor a jeho nalezení. Procedurální sémantika definitního programu. Vztah deklarativní a procedurální sémantiky: korektní odpovědi versus vypočtené odpovědi. Činnost zásobníku během výpočtu PROLOGu, backtracking, nalezení alternativních řešení.
Řezy a negace v logickém programování: Metalogický predikát řezu. Výpočtová efektivita a řezy. Řízení výpočtu pomocí řezů. Činnost zásobníku během výpočtu PROLOGu obohaceného o řezy. Vytváření podmínek a cyklů pomocí vestavěných predikátů. Teoretické přístupy k negaci: předpoklad uzavřenosti světa; negace pomocí neúspěchu v konečně mnoha krocích. Problém neexistence Herbrandovského modelu při použití negace. SLDNF-rezoluce. Zavedení negace pomocí řezu.
Logické programování a matematická logika: propojení logického programování a klasické predikátové logiky. Logický program jako teorie prvního řádu. Herbrandovské modely jako struktury prvního řádu. Princip obecné rezoluční metody a její adaptace pro definitní programy. Korektnost a úplnost SLD-rezoluce.
|
| KMI/PGML |
Matematická logika |
5 |
20+0+0S |
B |
| |
|
Anotace kurzu:
Studenti se seznámí se základními pojmy z matematické logiky.
Rámcový obsah kurzu:
Předpokládá se znalost základních partií výrokové a predikátové logiky
(syntax, sémantika, úplnost). Obsahem je jednak prohloubení znalostí těchto partií,
jednak (a to zejména) pokročilé partie klasické matematické logiky a vybraných
neklasických logik. Studenti budou připraveni na studium dalších logických kalkulů, případně na jejich aplikace v informatice (analýza dat, relační databáze, a podobně).
Metody důkazů vět o úplnosti klasické logiky a vybraných neklasických logik,
jejich historický vývoj.
Přidání funkčních symbolů a další rozšíření jazyka. Hilbert-Ackermannova věta.
Skolemizace, Herbrandova věta, Skolemova věta.
Základy teorie modelů klasické predikátové logiky: elementární ekvivalence,
Löwenheim-Skolemovy věty, pomíjení typů, saturovanost, kategoricita, ultraprodukt
a jeho použití, úplnost teorií.
Omezení predikátové logiky (vlastnosti struktur, které nelze vyjádřit teoriemi prvního
řádu). Logika druhého a vyšších řádů, základní vlastnosti.
Vybrané negativní výsledky v logice. Neúplnost (Gödelovo číslování, aritmetizace logiky, Gödelovy věty o neúplnosti); nerozhodnutelnost (a rozhodnutelnost) vybraných problémů
v logice.
Úvod do vybraných rozšíření klasické logiky. Modální a temporální logiky, fuzzy logiky, pravděpodobnostní logiky.
|
| KMI/PGMR |
Machine Learning |
5 |
20+0+0S |
B |
| |
|
Anotace kurzu:
Studenti nastudují vybrané nové metody strojového učení a získávání znalostí z dat. Předmět dále rozšiřuje znalosti z dvousemestrálního kurzu v navazujícím magisterském studiu věnovanému hlavním metodám.
Rámcový obsah kurzu:
1. Shlukování.
2. Klasifikace.
3. Závislosti v datech.
4. Grafové modely.
5. Redukce dimenzionality.
|
| KMI/PGRD |
Teorie relačních databází |
5 |
20+0+0S |
B |
| |
|
Anotace kurzu:
Studenti se seznámí se základními pojmy z teorie relačních databází.
Rámcový obsah kurzu:
Předmět v první části dále prohlubuje teoretické znalosti relačních databází z bakalářského a magisterského studia. Obsaženy jsou pokročilé partie z funkčních závislostí a normalizace relačního schématu databáze a z dotazovacích jazyků.
Ve druhé části jsou představena rozšíření relačního databázového modelu, zejména modely zaměřené na práci s neurčitostí.
Relační databázový model: Relační databáze. Relační schéma, atributy a domény. Relace nad relačním schématem. Vztah relací a datových tabulek. Operace s relacemi: booleovské operace; selekce, projekce, spojení (přirozené spojení, spojení na rovnost, vnější spojení). Vlastnosti relačních operací. Relační algebra. Relační kalkul a jeho úplnost.
Funkční závislosti a normalizace: Funkční závislosti a jejich platnost. Klíče. Sémantické vyplývání z funkčních závislostí. Sémantické ekvivalence množin funkčních závislostí. Syntaktické vyplývání z funkčních závislostí: Armstrongova pravidla, dokazatelnost. Úplnost logiky funkčních závislostí. Druhá a třetí normální forma relačních schémat. Dekompozice relací. Hledání minimálních bází funkčních závislostí. Redukce levých a pravých stran funkčních závislostí. Algoritmy pro ověření sémantického vyplývání. RAP-sekvence a DAG-diagramy. Struktura neredundantních a minimálních množin funkčních závislostí. Boyce-Coddova normální forma. Multifunkční závislosti. Bezeztrátová dekompozice tabulek.
Dotazovací jazyky: Strukturovaný dotazovací jazyk SQL: tabulky, sekvence, indexy, typy indexů, integritní omezení, operace se záznamy, dotazování, pohledy a snímky, kurzory. Logický dotazovací jazyk DATALOG: predikáty, atomy, pravidla a dotazy; vztah relační algebry a DATALOGu; rekurzivní pravidla a jejich sémantika, pevné body, problémy týkající se negace.
Rozšíření databázového modelu o neurčitost: Relační model dat s doménami s podobností, datové závislosti, relační algebra a kalkul, různé přístupy. Pravděpodobnostní rozšíření relačního modelu dat.
|
| KMI/PGSC |
Soft Computing |
5 |
20+0+0S |
B |
| |
|
Anotace kurzu:
Studenti se seznámí se základními pojmy ze soft computing.
Rámcový obsah kurzu:
Přehled poskytuje úvod pro studium oblastí soft computing. Zaměřuje se na teorie a aplikace fuzzy množin, teorie neurčitosti, neuronových sítí a genetických algoritmů.
Fuzzy množiny: fuzzy množiny a operace s nimi, fuzzy relace a operace s nimi, základní typy fuzzy relací. Vybrané aplikace fuzzy množin: pravidlové systémy, fuzzy regulátory, aproximační vlastnosti.
Teorie neurčitosti založené na monotónních měrách: Choquetovy kapacity, possibility/necessity míry, belief/plausibility míry, pravděpodobnostní míry, další speciální míry.
Rough sets, nerozlišitelnost, horní a dolní aproximace a související pojmy, zejm. pojmy informační systém, rozhodovací tabulka, indukované relace. Rough sets a fuzzy množiny. Vybrané oblasti použití rough sets.
Neuronové sítě: základní pojmy, neuron, neuronová síť, učení, trénovací a testovací množina. Jednoduchý perceptron a jeho adaptace. Vícevrstvé neuronové sítě, univerzální aproximační schopnost, adaptace metodou backpropagation. Příklady použití vícevrstvých neuronových sítí. Vybrané teoretické problémy (složitost učení, aproximační vlastnosti). Hopfieldovy a asociativní neuronové sítě: architektura, stabilita, adaptace, použití v optimalizačních problémech (stabilní body jako řešení).
Genetické algoritmy: základní princip a pojmy, Hollandova věta o schématech.
|
| KMI/PGST |
Průzkumová mnohorozměrná stat. analýza |
5 |
20+0+0S |
B |
| |
|
Anotace kurzu:
Cílem předmětu je poskytnout studentům doktorského programu Informatika, zejména těm, kteří jsou zaměřeni na relační metody analýzy dat, vzdělání ve vybraných tradičních statistických metodách analýzy mnohorozměrných dat. V předmětu se důkladně seznámí se základními pojmy statistických metod a jejich teoretickými základy.
Rámcový obsah kurzu:
Předmět je určen pro studenty doktorského studia informatiky zaměřené na metody analýzy relačních dat. Podává přehled o vybraných metodách klasické statistické analýzy dat.
- Úvod do mnohorozměrné statistiky: zobrazení dat, předzpracování.
- Maticová algebra a náhodné vektory.
- Geometrie výběrového prostoru a náhodný výběr.
- Mnohorozměrné normální rozdělení.
- Metoda hlavních komponent.
- Faktorová analýza.
- Faktorová analýza pro binární data.
- Shluková analýza.
|
| KMI/PGTI |
Teorie informace |
5 |
20+0+0S |
B |
| |
|
Anotace kurzu:
Studenti se seznámí se základními pojmy z teorie informace.
Rámcový obsah kurzu:
Předmět obsahuje pokročilé partie z klasické teorie informace a vybraných aplikací, jejíž základy jsou probírány v magisterském studiu, a dále poskytuje úvod do zobecněné teorie informace.
Klasická teorie informace: entropie a jednoznačnost funkce entropie, vlastnosti, vzájemná informace, divergence.
Komunikační kanály: modely kanálu bez paměti, kapacita, Shannonova věta o kapacitě kanálu, kanály s pamětí.
Zdroje informace: matematický model, Markov chains, AEP.
Pokročilé samoopravné kódy: cyklické, BCH a konvoluční kódy.
Úvod do zobecněné teorie informace: monotónní míry a jejich speciální případy (nepřesné pravděpodobnosti, possibility, Dempster-Shafer), míry neurčitosti a informace pro tyto míry.
|
| KMI/PGTK |
Teorie kategorií pro informatiky |
5 |
20+0+0S |
B |
| |
|
Anotace kurzu:
Studenti budou obeznámeni se základními principy teorie kategorií a s možnostmi aplikací těchto principů v informatice.
Rámcový obsah kurzu:
Studenti budou obeznámeni se základními principy teorie kategorií a s možnostmi aplikací těchto principů v informatice. Získané vědomosti pak budou moci využít při řešení konkrétních problémů ve svojí specializaci.
1. Grafy a kategorie
2. Algebraické struktury jako kategorie
3. Konstrukce na kategoriích
4. Vlastnosti objektů a morfismů
5. Součiny a součty objektů
6. Objekty přirozených čísel a deduktivní systémy
7. Funktory a diagramy
8. Funktorové kategorie, gramatiky a automaty
9. Přirozené transformace
10. Limity a kolimity
11. Adjungované funktory
12. Kartézsky uzavřené kategorie a typovaný lambda-kalkul
13. Kartézsky uzavřená kategorie Scottových domainů
|
| KMI/PGTM |
Teorie modelů |
5 |
20+0+0S |
B |
| |
|
Anotace kurzu:
Studenti se seznámí se základními pojmy z teorie modelů.
Rámcový obsah kurzu:
Úvod do problematiky: Jazyk, formule, strukturální indukce, teorie. Struktury jako modely teorií, expanze a redukt struktury. Mohutnost množin, dobré uspořádání, ordinální čísla, transfinitní indukce.
Modely konstruované z konstant: Konstrukce modelů z konstant. Kanonické struktury. Zúplňování teorií. Věta o kompaktnosti a její aplikace. Pomíjení typů.
Metoda elementárních řetězců: Diagramy struktur. Elementární ekvivalence. Elementární podstruktury. Řetězce struktur a jejich sjednocení. Elementární řetězce struktur. Aplikace.
Löwenheim-Skolemova věta: Směr ,,dolů'' a jeho důsledky. Skolemův zdánlivý paradox. Směr ,,nahoru'' a jeho důsledky pro predikátovou logiku. Redukovaný součin a ultrasoučin. Centrovaný systém množin, filtr, ultrafiltr, existence netriviálního ultrafiltru. Redukované součiny, ultrasoučiny. Los'ova věta. Ultrasoučinová verze kompaktnosti. Elementární třídy struktur. Aplikace ultraproduktů v univerzální algebře při charakterizaci implikačně definovatelných tříd algeber.
|
| KMI/PGTO |
Topologické metody v informatice |
5 |
20+0+0S |
B |
| |
|
Anotace kurzu:
Studenti se seznámí se základními pojmy z obecné a algebraické topologie a jejich aplikacemi v informatice.
Rámcový obsah kurzu:
Předmět zahrnuje pokročilé partie z topologie a jejích aplikací v informatice.
Obecná topologie.
Úvod do teorie homotopií.
Algebraická topologie: singulární homologie, základy homologické algebry.
Výpočet homologických grup: Mayerova-Vietorisova posloupnost.
Simpliciální homologie, výpočet homologií simpliciálních komplexů jako diskrétní problém, simpliciální struktury pro MV-algebry.
Algebraická topologie konečných prostorů.
Topologie v analýze dat.
Topologie a distribuované výpočty.
|
| KMI/PGTP |
Těžké problémy |
5 |
20+0+0S |
B |
| |
|
Anotace kurzu:
Studenti se seznámí s algoritmy pro těžké problémy, s příslušnými metodami a teoretickými základy.
Rámcový obsah kurzu:
Obsahem předmětu jsou těžké problémy, přístupy k jejich řešení, algoritmy a související teoretické základy.
Optimalizační problémy, základní pojmy, příklady problémů a jejich typy, třídy NPO, PO, NP-těžké optimalizační problémy.
Aproximační algoritmy, základní pojmy, PTAS, FPTAS, důležité podtřídy třídy NPO, stabilita.
Vybrané problémy a aproximační algoritmy: pokrytí množiny a jeho varianty, vrcholové pokrytí a jeho varianty, maximální řez, problém ruksaku, problém obchodního cestujícího a jeho varianty.
Neaproximovatelnost: redukce na NP-těžké rozhodovací problémy, redukce na prokazatelně těžké optimalizační problémy, PCP teorém a jeho použití.
Úvod do randomizovaných algoritmů. Základní pojmy, klasifikace algoritmů, randomizované optimalizační algoritmy, RPTAS, RFPTAS, příklady randomizovaných algoritmů, metody jejich návrhu.
Úvod do parametrizované složitosti. Základní pojmy, parametrizace problému, problém schůdný s pevným parametrem, příklady problémů a příslušných algoritmů.
Heuristiky, simulované žíhání, genetické algoritmy, věta o schématech a základní teoretické výsledky.
|
| KMI/PGVR |
Formální metody pro verifikaci systémů |
5 |
20+0+0S |
B |
| |
|
Anotace kurzu:
Studenti se seznámí se základními metodami pro rigorózní ověření požadovaného chování (softwarových či hardwarových) systémů a porozumí teoretickým základům těchto metod a možnostem jejich praktického nasazení.
Rámcový obsah kurzu:
Předmět je zaměřen na hlubší pochopení formálních metod zejména v oblasti automatizované verifikace systémů.
Zahrnuje např. tyto části:
Logika a částečně automatizované dokazování teorémů.
Modelování softwarových a hardwarových systémů.
Formální specifikace, temporální logiky a automaty.
Automatizovaná verifikace, ověřování modelu (model checking).
Procesní algebry a ekvivalence.
Softwarové verifikační nástroje.
|
| KMI/PGVS |
Vyčíslitelnost a složitost |
5 |
20+0+0S |
B |
| |
|
Anotace kurzu:
Studenti se důkladně seznámí se základními pojmy a metodami z teorie vyčíslitelnosti a složitosti.
Rámcový obsah kurzu:
Předmět se zaměřuje na vybrané pokročilé partie vyčíslitelnosti a složitosti, např. následující:
Diagonalizace a její limity: hierarchické věty, relativizace.
Prostorová složitost: třídy PSPACE a NL úplnosti.
Polynomiální hierarchie a alternace.
Booleovské okruhy: neuniformní modely výpočtu, třída P/poly.
Interaktivní dokazovací systémy: třída IP a pravděpodobnostní verifikátory, věta IP=PSPACE.
PCP teorém a aproximovatelnost: přibližná řešení těžkých problémů, varianty PCP teorému, neaproximovatelnost.
Složitost počítacích problémů (counting problems): příklady problémů, třída \#P a \#P-úplnost, Todova věta.
Úvod do složitosti v průměrném případě: třídy distP a distNP.
|