Logika a složitost - NMAG446

• Anglický název: Logic and Complexity
• Zajišťuje: Katedra algebry (32-KA)
• Fakulta: Matematicko-fyzikální fakulta
• Platnost: od 2024
• 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: angličtina, čeština
• Způsob výuky: prezenční
• Další informace: http://www.karlin.mff.cuni.cz/~krajicek/ls.html
• Garant: prof. RNDr. Jan Krajíček, DrSc.
• Vyučující: 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

Anotace

čeština

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.

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

angličtina

The course maps connections between mathematical logic and computational complexity theory. The course may not be taught every academic year.

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

Podmínky zakončení předmětu

Oral exam.

Poslední úprava: Krajíček Jan, prof. RNDr., DrSc. (22.02.2019)

Literatura

čeština

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

http://www.karlin.mff.cuni.cz/~krajicek/prfdraft.html

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

angličtina

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

http://www.karlin.mff.cuni.cz/~krajicek/prfdraft.html

Poslední úprava: Krajíček Jan, prof. RNDr., DrSc. (22.02.2019)

Sylabus

čeština

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.

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

angličtina

Basic concepts of computational complexity theory. Definability in first-order logic. Finite model theory. Proof complexity and SAT algorithms. Herbrand's theorem and witnessing theorems.

Poslední úprava: Krajíček Jan, prof. RNDr., DrSc. (22.02.2019)

Vstupní požadavky

čeština

Základní znalosti matematické logiky.

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

angličtina

Basic knowledge of matematical logic.

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