PředmětyPředměty(verze: 945)
Předmět, akademický rok 2023/2024
   Přihlásit přes CAS
Algoritmy pro reprezentaci znalostí - NTIN099
Anglický název: Algorithms for knowledge representation
Zajišťuje: Katedra teoretické informatiky a matematické logiky (32-KTIML)
Fakulta: Matematicko-fyzikální fakulta
Platnost: od 2020
Semestr: letní
E-Kredity: 3
Rozsah, examinace: letní s.:2/0, Zk [HT]
Počet míst: neomezen
Minimální obsazenost: neomezen
4EU+: ne
Virtuální mobilita / počet míst pro virtuální mobilitu: ne
Stav předmětu: vyučován
Jazyk výuky: čeština, angličtina
Způsob výuky: prezenční
Způsob výuky: prezenční
Další informace: http://ktiml.mff.cuni.cz/~kucerap/abf/
Garant: RNDr. Petr Kučera, Ph.D.
Třída: Informatika Mgr. - volitelný
Informatika Mgr. - Teoretická informatika
Kategorizace předmětu: Informatika > Informatika, Aplikační software, Počítačová grafika a geometrie, Databázové systémy, Didaktika informatiky, Diskrétní matematika, Předměty širšího základu, Předměty obecného základu, Počítačová a formální lingvistika, Optimalizace, Programování, Softwarové inženýrství, Teoretická informatika
Anotace -
Poslední úprava: doc. RNDr. Pavel Töpfer, CSc. (01.02.2019)
Přednáška seznamující s některými algoritmy pro booleovské funkce, zejména splnitelnost. Exponenciální algoritmy pro splnitelnost. Parametrizované algoritmy pro splnitelnost a MaxSAT. Prohledávací algoritmy pro MaxSAT. Reprezentace znalostí založené na NNF.
Cíl předmětu -
Poslední úprava: RNDr. Jan Hric (07.06.2019)

TBA

Podmínky zakončení předmětu -
Poslední úprava: RNDr. Jan Hric (07.06.2019)

TBA

Literatura -
Poslední úprava: T_KTI (27.02.2014)

A. Biere, M. Heule, H. van Maaren, T. Walsh (Eds.). Handbook of Satisfiability, in: Frontiers in Artificial Intelligence and Applications, vol. 185, IOS Press, 2009, pp. 131-153

Niedermeier, Rolf. Invitation to fixed-parameter algorithms. Vol. 3. Oxford: Oxford University Press, 2006

Flum, Jörg, and Martin Grohe. Parameterized complexity theory. Vol. 3. Heidelberg: Springer, 2006

Sylabus -
Poslední úprava: doc. RNDr. Pavel Töpfer, CSc. (01.02.2019)
  • Exponenciální algoritmy pro k-SAT a obecný SAT
  • Parametrizované algoritmy pro SAT založené na backdoor množinách.
  • Algoritmy pro SAT parametrizované stromovou šířkou
  • Kernelizace pro MaxSAT a parametrizace MaxSAT
  • Algoritmy pro MaxSAT založené na větvení a prořezávání (branch & bound)
  • Algoritmy pro #SAT
  • Reprezentace znalostí založené na NNF (negation normal form)
  • OBDD, DNNF, d-DNNF, SDD
  • Srovnání těchto reprezentací s ohledem na zodpovídání dotazů a velikost
  • Kompilace formule v KNF do různých typů reprezentací
  • Využití pro počítání modelů

 
Univerzita Karlova | Informační systém UK