|
|
Close Help | ||||||||||||||
Letni semestr 06/07: Teorie konecnych modelu
Pro ilustraci, prehledovy clanek R.Fagina, skripta J.Vaananena a M.Otta). Toto bylo doplneno prednaskami hostu: Neil Thapen (prednaska Resolution and pebbling games) a Pavel Pudlak (prednaska Resolution proofs and games).
Zimni semestr 07/08: Studium clanku
Dana Scott, A proof of the independence of the continuum hypothesis, Mathematical Systems Theory, 1, (1967), str.89-111.
Toto je jeden z nejkrasnejsich prehledovych clanku v matematicke logice vsech dob. Byl napsan pro matematiky bez prupravy v matematicke logice a je dostupny i matematickym zacatecnikum. Predklada dukaz, ze tzv. Hypoteza Kontinua (tez jeden ze slavnych Hilbertovych problemu) neni dokazatelna v teorii mnozin.
Letni semestr 07/08: Omezena aritmetika
Omezena aritmetika je souborny nazev pro skupinu teorii (formalne podteoriich Peanovy aritmetiky). Tyto teorie matematicky podchycuji neformalni pojem "feasible reasoning", podobne jako pojmy (pravdepodobnostni) polynomialni algoritmus ci log-space algoritmus (a rada dalsich) formalizuji pojem "feasible computation". Literatura.
Paralelne s timto tematem oragizoval student p.Jan Pich dalsi studium literatury o konecne teorii modelu, zejmena skripta M.Otta - viz informace o letni semestru 06/07 vyse (ucast na tomto drivejsim seminari neni podminkou).
Zimni semestr 08/09: Booleovska slozitost
Radu otevrenych problemu v teorii vypocteni slozitosti (vcetne tzv. P vs. NP problemu) lze redukovat na ukol dokazat vhodny spodni odhad na velikost obvodu pocitajici konkretni funkci. Potrebne odhady neumime zatim dokazat pro obecne obvody, ale pouze pro obvody splnujici dodatecna omezeni (konstatni hloubky, monotonni a pod.). Toto tema je jednou z fundamentalnich souvislosti mezi logikou a teorii vypocetni slozitosti. Literatura.
