Tato stránka vychází z podkladů pro tištěné studijní plány (tzv. Karolinku).
Aktuální složení rady je na adrese http://mff.cuni.cz/phd/or/p4m1.
Jsou k nahlédnutí v SIS na adrese http://mff.cuni.cz/phd/temata/p4m1.
kód | Předmět | ZS | LS | |
NAIL056 | Logický seminář I | 0/2 Z | — | |
NAIL080 | Logický seminář II | — | 0/2 Z | |
NDMI045 | Analytická a kombinatorická teorie čísel | — | 2/0 Zk | |
NMAG265 | Studentský seminář z teorie množin | 0/2 Z | — | |
NMAG405 | Universální algebra 1 | 2/2 Z+Zk | — | |
NMAG407 | Teorie modelů | 2/0 Zk | — | |
NMAG446 | Logika a složitost | — | 2/0 Zk | |
NMAG450 | Universální algebra 2 | — | 2/1 Z+Zk | |
NMAG455 | Kvadratické formy a třídová tělesa I | 2/0 Zk | — | |
NMAG456 | Kvadratické formy a třídová tělesa II | — | 2/0 Zk | |
NMAG462 | Modulární formy a L-funkce I | 2/0 Zk | — | |
NMAG466 | Teorie svazů 2 | — | 2/0 Zk | |
NMAG470 | Seminář z teorie čísel | 0/2 Z | 0/2 Z | |
NMAG473 | Modulární formy a L-funkce II | — | 2/0 Zk | |
NMAG475 | Výběrový seminář z MSTR | 0/2 Z | 0/2 Z | |
NMAG498 | Výběrová přednáška z MSTR 1 | 2/0 Zk | — | |
NMAG499 | Výběrová přednáška z MSTR 2 | — | 2/0 Zk | |
NMAG531 | Aproximace modulů | — | 2/0 Zk | |
NMAG536 | Důkazová složitost a P vs. NP problém | — | 2/0 Zk | |
NMAG562 | Homologická a homotopická algebra | 2/0 Zk | — | |
NMAG563 | Úvod do složitosti CSP | 2/0 Zk | — | |
NMAG565 | Algebra a nekonečná kombinatorika | 2/0 Zk | — | |
NMAG567 | Reprezentace grup 2 | 2/2 Z+Zk | — | |
NMAG571 | Algebraický seminář | 0/2 Z | 0/2 Z | |
NMAG573 | Seminář k problému CSP | 0/2 Z | 0/2 Z | |
NMIN160 | Teorie množin | 2/0 Zk | — | |
NMMB451 | Aplikace matematiky v informatice | — | 0/2 Z | |
NMMB452 | Seminář z matematiky inspirované kryptografií | 0/2 Z | 0/2 Z | |
NMMB453 | Studentský logický seminář | 0/2 Z | 0/2 Z | |
NMMB471 | Výběrový seminář z MIT | — | 0/2 Z | |
NMMB498 | Výběrová přednáška MIT 1 | 2/0 Zk | — | |
NMMB499 | Výběrová přednáška MIT 2 | — | 2/0 Zk | |
NMMB551 | Seminář z kombinatorické, algoritmické a finitní algebry | 0/2 Z | 0/2 Z | |
NMMB621 | Doktorandský seminář z kryptologie | 0/2 Z | 0/2 Z | |
NTIN071 | Automaty a gramatiky | — | 2/2 Z+Zk | |
NTIN090 | Základy složitosti a vyčíslitelnosti | 2/1 Z+Zk | — | |
NMAG575 | Forsing | 2/0 Zk | — | |
NMAG576 | Seminář z forsingu | — | 0/2 Z | |
NLTM014 | Nestandardní seminář 1 | 0/2 Z | — | |
NLTM015 | Nestandardní seminář 2 | — | 0/2 Z | |
NMAG577 | Seminář z počtů | 0/2 Z | 0/2 Z | |
NTIN062 | Složitost I | 2/1 Z+Zk | — | |
NTIN064 | Vyčíslitelnost | — | 2/0 Zk | |
NTIN073 | Rekurze | 2/0 Zk | — | |
NTIN088 | Algoritmická náhodnost | — | 2/0 Zk | |
NMAI067 | Logika v informatice | 2/0 Zk | — | |
NAIL021 | Booleovské funkce a jejich aplikace | 2/0 Zk | — | |
NMAI040 | Úvod do teorie čísel | 2/0 Zk | — | |
NDMI066 | Algebraická teorie čísel | 2/0 Zk | — |
I. Širší základ
Povinná část.
I.1 Základy algebry
Teorie grup: konečné grupy, Sylowovy věty, struktura
konečně generovaných komutativních grup, volné grupy
a jejich podgrupy.
Galoisova teorie: Galoisova rozšíření a grupy, radikálová rozšíření těles, neřešitelnost polynomiálních rovnic v radikálech.
Teorie reprezentací a algebraická geometrie: Reprezentace konečných grup, Maschkeho věta, charaktery. Korespondence mezi afinními algebraickými množinami a ideály okruhů polynomů, Hilbertova věta o nulách.
Univerzální algebra: Variety algeber, subdirektní rozklady, volné algebry, Birkhoffova věta. Svazy, úplné svazy, uzávěrové operátory, Galoisovy korespondence.
II. Pokročilé partie
Studující si vybere po dohodě se školitelem dvě různá témata z pokročilých partií
specializace ,,Algebra'', ,,Teorie čísel'' nebo ,,Matematická logika.''
Aspoň jedno z nich ale musí být některé z následujících (II.1–II.10):
II.1. Teorie grup
Akce grupy na množině. Permutační, řešitelné a nilpotentní grupy.
Lineární grupy. Jenoduché konečné grupy, jednoduchost An a PSLn(K).
Základy teorie rozšíření grup, semidirektní součiny grup.
Indukované reprezentace grup a Frobeniova reciprocita,
Mackeyova věta a její důsledky.
II.2 Binární systémy
Levodistributivní grupoidy (volné, monogenerované, problém slov),
souvislost s grupami pletenců. Mediální a oboustranně distributivní
grupoidy, rovnicová teorie mediálních idempotentních grupoidů.
Normální podkvazigrupy a kongruence lup a kvazigrup, nuklea, centrum, nilpotence.
Vazby na multiplikační grupu. LCC, CC, extra, bolovské a moufangovské lupy.
Inverzní vlastnosti, diasociativita. Izotopie, centrální a mediální kvazigrupy.
Toyodova věta.
II.3 Komutativní algebra
Komutativní noetherovské okruhy: spektrum, lokalizace, primární rozklady.
Celistvá rozšíření, Dedekindovy obory, faktorizace ideálů.
Lokalizace a zúplnění modulů. Krullova věta o hlavních ideálech.
Regulární posloupnosti, hloubka, Auslander–Buchsbaumova věta.
II.4 Algebraická geometrie
Afinní a projektivní algebraické množiny, Zariského topologie,
rozklad na ireducibilní komponenty.
Funkční tělesa, racionální zobrazení, biracionální ekvivalence.
Homomorfismy algebraických množin, projektivní eliminace,
uzavřenost morfismů z projektivních algebraických množin.
Bézoutova věta. Krullova dimenze a její vlastnosti.
II.5 Teorie modulů a homologická algebra
Projektivní a injektivní moduly. Řetězcové podmínky na ideály,
Hopkinsova-Levitzkého věta, Faitova charakterizace noetherovskosti.
Moritova ekvivalence. Kategorie modulů, tenzorový součin,
funktory Ext a Tor, dlouhé exaktní posloupnosti.
Direktní limity, čistá vnoření, čistě–injektivní moduly
a modelově–teoretické souvislosti. Derivované kategorie.
II.6 Aproximace modulů a nekonečná kombinatorika
Kotorzní páry, filtrace, Eklofovo lemma a Hillovo lemma.
Dekonstruovatelnost pro regulární a singulární kardinály
(závislost na rozšíření ZFC, Shelahova věta o singulární kompaktnosti).
Struktura Whiteheadových a Baerových modulů.
II.7 Reprezentace algeber konečné dimenze
Konečně dimenzionální algebry jako faktory algeber cest grafů.
Krullova-Schmidtova věta. Konečný, krotký a divoký reprezentační typ.
Dědičné algebry a Gabrielova charakterizace konečného reprezentačního typu.
Vychylující moduly a vychýlené algebry. Skoro štěpitelná zobrazení,
AR–posloupnosti, AR–graf konečně dimenzionální algebry.
II.8 Univerzální algebra a teorie svazů
Malcevské podmínky.
Abelovskost a komutátor v obecných algebrách.
Rovnicové teorie, přepisující systémy a Knuthův-Bendixův algorithmus, konečně bázované variety.
Distributivní, modulární, semimodulární a geometrické svazy,
kongruence svazů, volné svazy a problém slov. Jónssonovo lemma a variety svazů.
II.9 Univerzálně algebraické metody v CSP
Relační a algebraické klony,
homomorfismy klonů a primitivně pozitivní interpretace relačních struktur.
Složitost CSP a klony polymorfismů, Taylorovy klony, malcevské CSP a problémy konečné šířky,
Schaeferova věta o klasifikaci CSP nad dvouprvkovou množinou.
II.10 Kombinatorika na slovech
Dicksonovo lemma. F–pologrupy (minimální množina generátorů, kódy, podmínka stability, řády pologrupy).
Chomskeho hierarchie (formální gramatiky a odpovídající automaty, Kleenova věta, pumpovací lemmata, Parikhova věta).
Rovnice ve volných monoidech (věta o kompaktnosti, grafové lemma, vlastnosti defektu, ekvivalenční a testovací množiny).
Postův korespondenční problém.
I. Širší základ
Povinná část.
I.1 Základy logiky
Výroková logika a logika prvního řádu. Struktury prvního řádu,
Tarského definice splňování. Predikátový počet, dokazatelnost. Věty
o úplnosti a o kompaktnosti. Teorie množin jako teorie prvního řádu.
Gödelova věta o neúplnosti a o nedokazatelnosti bezespornosti.
Turingovy stroje: universální stroj, algoritmicky nerozhodnutelné
problémy, halting problem. Eliminace kvantifikátorů v uspořádaném
tělese reálných čísel.
II. Pokročilé partie
Studující si vybere po dohodě se školitelem dvě různá témata z pokročilých partií
specializace ,,Algebra'', ,,Teorie čísel'' nebo ,,Matematická logika.''
Aspoň jedno z nich ale musí být některé z následujících (II.1–II.6):
II.1. Obecná teorie modelů
Základní pojmy: podstruktura a elementární podstruktura, diagram,
homomorfisimus, vnoření a elementární vnoření, isomorfismus.
Löwenheim–Skolemovy věty. Modelová úplnost. Definovatelné množiny,
typy, eliminace kvantifikátorů. Konstrukce modelů: pomíjení typů,
Henkinova konstrukce, Skolemizace. Craigova interpolace, elementarní
řetězce, Robinsonova věta o bezespornosti, nerozlišitelné prvky.
Saturované a homogenní modely, prvomodely. Ultraprodukt a jeho
zakladní vlastnosti. Elementarní třídy.
II.2 Aplikovaná teorie modelů
Realně uzavřená uspořádaná tělesa a jejich redukty a rozšíření,
Věty Tarského a Wilkiova. O–minimálni struktury a jejich základní
geometrické a topologické vlastnosti.
Stabilní a omega–stabilní teorie, nespočetná kategoričnost,
Morleyho věta. Minimální a silně minimalní struktury, obecné
uzávěrové operace, geometrie a dimense v silně minimálních
strukturách. Omega–stabilní grupy, Cherlin–Zilberova hypotéza.
Hrushovského amalgamačni metoda.
II.3. Teorie množin
Axiomatika teorie ZFC. Axiom výběru AC, Zornovo lema, dobrá uspořádání.
Ordinální a kardinální aritmetika, transfinitní indukce.
Nekonečná kombinatorika: nezávislé a skorodisjunktní systémy množin,
Ramseyova věta, uzavřené a neomezené množiny a stacionární množiny,
diamantový princip, Martinův axiom. Stromy (Suslinovy, Aronszajnovy,
Kurepovy), Suslinova hypotéza. Booleovy algebry, ultrafiltry, Stoneova
dualita. GCH. Konstruktivní množiny, axiom V=L. GCH a AC v L.
Forcing a Booleovské modely, nezávislost CH. Nedosažitelné a měřitelné
kardinály, elementární vnoření.
Deskriptivní teorie množin: Borelovské, analytické a projektivní
množiny, nekonečné hry, determinovanost. Uniformizační věty. Borelovské
ekvivalence. Polské prostory, Polské grupy a jejich akce.
II.4. Teorie vyčíslitelnosti
Částečně rekurzivní funkce, rekurzivní množiny a rekurzivně
spočetné množiny. Univerzální částečně rekurzivní funkce, index.
Věty o rekurzi, Riceova věta. Kreativní množiny.
Efektivní neoddělitelnost. Operace skoku. Aritmetická hierarchie.
Stupně nerozhodnutelnosti. Aritmetický forcing, prioritní metody.
Kolmogorovská složitost, základy algoritmické náhodnosti.
II.5 Teorie důkazů a formální aritmetika
Gentzenův sekvenční kalkulus, eliminace řezu, Herbrandova věta.
Craigova interpolace. Robinsonova aritmetika Q a Peanova aritmetika PA.
Interpretovatelnost teoríi. Nerozhodnutelnost Q a PA. Dokazatelně
totální rekursivní funkce. Nemožnost konečné axiomatizace PA.
Logika druhého řádu, jednoduchá teorie typů, infinitární logika.
Reversní matematika. Neklasické logiky: intuitionistická, modální,
vícehodnotové.
II.6 Logika a složitost
Časová a prostorová složitost algoritmů, hlavní třídy složitosti.
Boolovské obvody a hlavní známé spodní odhady na jejich velikost.
Koncept přirozených důkazů spodních odhadů (Razborov–Rudich).
Teorie konečných modelů, deskriptivní složitost. Definovatelnost
v konečných strukturách, Faginova věta. Logiky s operátorem
pevného bodu. 0–1 zákony. Ehrenfeucht–Fraissého metoda. Lokalita
a věty Gaifmana a Hanfa. Oblázkové hry. Problém spektra.
Důkazová složitost, vyrokové důkazové systémy (Cook–Reckhow).
Resoluce, DPLL algoritmus pro SAT a jejich souvislost. Fregeho
systémy a rozšířené Fregeho systémy. Spodní odhad na délku
důkazů v resoluci. Omezená aritmetika. Definovatelnost polynomiální
hierarchie. Dosvědčovací funkce a vyhledávací problémy. Překlady
do výrokové logiky. Problém konečné axiomatizovatelnosti omezené aritmetiky.
I. Širší základ
Základy teorie čísel: Hustota prvočísel, Legendreovy a Jacobiho symboly,
kvadratická reciprocita, řetězové zlomky, kvadratická číselná tělesa,
Rabinův–Millerův algoritmus a RSA.
Algebraická teorie čísel: číselná tělesa, existence celistvé báze, Dedekindovskost. Větvení a štěpení prvočísel. Geometrie čísel, třídové číslo, Dirichletova věta o jednotkách. Cyklotomická tělesa, řešení diofantických rovnic. p–adická čísla.
Počítačová algebra: Berlekampův algoritmus pro faktorizaci polynomů. Groebnerovy báze a Buchbergerův algoritmus. Faktorizace polynomů s celočíselnými koeficienty.
II. Pokročilé partie oboru
Studující si vybere po dohodě se školitelem dvě různá témata z pokročilých partií
specializace ,,Algebra'', ,,Teorie čísel'' nebo ,,Matematická logika.''
Aspoň jedno z nich ale musí být některé z následujících (II.1–II.6):
II.1 Kryptologie a faktorizace
Generátory pseudonáhodných čísel, symetrické a proudové šifry,
hašovací funkce, dokazatelná bezpečnost, kryptografické protokoly,
důkazy s nulovou znalostí.
Číselné síto a jeho dílčí algoritmy (hledání odmocniny, volba polynomu aj.).
Další faktorizační algoritmy (p-1, p+1, rho, použití eliptických křivek)
a jejich význam pro číselné síto. Testy a důkazy prvočíselnosti
(kvadratický Frobeniův, N-1 test, ECPP, algoritmy pracující
v polynomiálním čase).
II.2 Pokročilé kryptoanalytické metody
Teorie booleovských funkcí, S–boxy, jejich kryptografické vlastnosti,
lineární a diferenciální kryptoanalýza, LLL–algoritmus a jeho
kryptoanalytické aplikace.
II.3 Samoopravné kódy
Klasická teorie cyklických kódů. Samoduální kódy a teorie invariantů.
Konvoluční kódy. Turbo kódy. Dekódovací algoritmy, zejména Viterbiho
a různé algoritmy pro Reed–Solomonovy kódy. Kvaternární kódy. Pokrývací poloměr
a aplikace ve steganografii. Podrobná znalost BCH, alternatních, Kerdockových,
Preparatových, Justensenových, Reedových–Mullerových a QR kódů.
Asymptotické odhady a konstrukce asymptoticky dobrých kódů. LDPC kódy. MDS kódy.
Základní odhady (Plotkin, Hamming, Griesmer, Singleton, Johnson, Gilbert–Varšamov,
lineární programování).
II.4 Eliptické křivky
Variety nad konečnými tělesy (Frobeniův morfismus, Hasse–Weilova věta
pro jakobián, Tatova věta). Aritmetika eliptických křivek (grupový zákon, racionální body,
torzní body, izomorfismy a izogenie). Montgomeryho skalární násobení. Párování a jeho
implementace. Výpočet počtu bodů (elementární metody, Schoofův a Satohův algoritmus,
komplexní násobení). Výpočet diskrétního logaritmu (činská věta o zbytku,
baby–step giant–step, Pollardovy metody). Kryptografie založená na párování.
Použití eliptických křivek pro faktorizaci a testy prvočíselnosti.
II.5 Algebraická teorie čísel II
Kvadratické formy: grupa tříd binárních forem, teorie rodů, prvočísla reprezentovaná binárními formami, univerzální formy, Hasseho-Minkowského věta, Hilbertův symbol.
Adély a idély, lokálně kompaktní grupy. Globální a lokální teorie třídových těles.
II.6 Analytická teorie čísel
L-funkce: Riemannova zéta-funkce, Dirichletovy L-funkce, Eulerův součin, meromorfní rozšíření, funkcionální rovnice, Dirichletova věta o aritmetické posloupnosti.
Modulární formy: Základní vlastnosti, dimenze prostoru modulárních forem. Fourierův rozvoj, Eisensteinovy řady. Heckeho operátory, aplikace.