Logika a složitost - NMAG446
Anglický název: Logic and Complexity
Zajišťuje: Katedra algebry (32-KA)
Fakulta: Matematicko-fyzikální fakulta
Platnost: od 2022
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: nevyučován
Jazyk výuky: angličtina, čeština
Způsob výuky: prezenční
Způsob výuky: prezenční
Další informace: http://www.karlin.mff.cuni.cz/~krajicek/ls.html
Garant: prof. RNDr. Jan Krajíček, DrSc.
Třída: M Mgr. MSTR
M Mgr. MSTR > Povinně volitelné
Kategorizace předmětu: Matematika > Algebra
Neslučitelnost : NALG128
Záměnnost : NALG128
Je záměnnost pro: NALG128
Výsledky anket   Termíny zkoušek   Rozvrh   Nástěnka   
Anotace -
Poslední úprava: doc. Mgr. et Mgr. Jan Žemlička, Ph.D. (31.05.2019)
Přednáška probírá souvislosti mezi matematickou logikou a teorií výpočetní složitosti. Předmět nemusí být vyučován každý rok.
Podmínky zakončení předmětu - angličtina
Poslední úprava: prof. RNDr. Jan Krajíček, DrSc. (22.02.2019)

Oral exam.

Literatura -
Poslední úprava: doc. Mgr. et Mgr. Jan Žemlička, Ph.D. (17.05.2019)

J.Krajicek, Proof complexity, Cambridge U. Press, 2019.

http://www.karlin.mff.cuni.cz/~krajicek/prfdraft.html
Sylabus -
Poslední úprava: doc. Mgr. et Mgr. Jan Žemlička, Ph.D. (17.05.2019)

Základní kocepty teorie výpočetní složitosti. Definovatelnost v logice prvního řádu. Konečná teorie modelů. Důkazová složitost a SAT algoritmy, Herbrandova věta a dosvědčující věty.

Vstupní požadavky -
Poslední úprava: doc. Mgr. et Mgr. Jan Žemlička, Ph.D. (17.05.2019)

Základní znalosti matematické logiky.