2.1.2 Matematické struktury, plán S

Garantující pracoviště: Katedra algebry
Oborový garant: prof. RNDr. Jan Krajíček, DrSc.

Plán S je určen pro studenty, kteří zahájili studium oboru Matematické struktury v roce 2012/13 nebo dříve.

Doporučený průběh studia

Doporučený průběh studia pro studijní plán S je uveden v oranžové Karolince pro rok 2013/14.

Shrnutí studijního plánu

Povinné předměty

kódPředmětKredityZSLS
NMAG333Okruhy a moduly152/2 Z+Zk
NMAG334Úvod do teorie Lieových grup252/2 Z+Zk
NMAG335Úvod do analýzy na varietách352/2 Z+Zk
NMAG337Úvod do teorie grup452/2 Z+Zk
NMMA335Obecná topologie 1552/2 Z+Zk
NALG015Komutativní algebra 1*63/1 Z+Zk
NLTM006Základy matematické logiky*32/0 Zk
NMAT001Základy teorie kategorií*62/2 Z+Zk
NSZZ023Diplomová práce I 60/4 Z
NSZZ024Diplomová práce II 90/6 Z
NSZZ025Diplomová práce III 150/10 Z

* Místo NALG015 lze zapsat NMAG460. Místo NLTM006 lze zapsat NMAG331. Místo NMAT001 lze zapsat NMAG471.

1Předmět je ekvivalentní s předmětem NALG028.

2Předmět je ekvivalentní s předmětem NALG018.

3Předmět je ekvivalentní s předmětem NGEM002.

4Předmět je ekvivalentní s předmětem NALG017.

5Předmět je ekvivalentní s předmětem NMAT039.

Povinně volitelné předměty

Je třeba získat alespoň 15 kreditů z povinně volitelných předmětů.

Zkratky v závorce označují téma státní závěrečné zkoušky, k němuž je předmět doporučen.

kódPředmětKredityZSLS
NMAG403Kombinatorika 52/2 Z+Zk
NMAG411Riemannova geometrie 1(RG)52/2 Z+Zk
NMAG433Riemannovy plochy 32/0 Zk
NMAG437Seminář z diferenciální geometrie 30/2 Z0/2 Z
NMAG440Binární systémy 32/0 Zk
NMAG448Teorie invariantů 52/2 Z+Zk
NMAG454Fibrované prostory a kalibrační pole 63/1 Z+Zk
NMMB204Počítačová algebra(AI)63/1 Z+Zk
NALG011Přepisující systémy(AI, UL)*62/0 —2/0 Zk
NALG016Komutativní algebra 2(AP)*32/0 Zk
NALG021Reprezentace grup(AP)*62/2 Z+Zk
NALG029Kategorie modulů a homologická algebra(AP)*63/1 Z+Zk
NALG033Kombinatorická teorie grup(AI, UL)*92/2 Z2/0 Zk
NALG103Univerzální algebra I(AI, UL)*62/2 Z+Zk
NALG104Univerzální algebra II(AI, UL)*32/0 Zk
NDMA001Teorie grafů a algoritmy pro matematiky 1(KG, TG)*52/2 Z+Zk
NDMI007Kombinatorické algoritmy(KG, TG)62/2 Z+Zk
NDMI009Kombinatorická a výpočetní geometrie I(KG)62/2 Z+Zk
NDMI012Kombinatorika a grafy II(TG)62/2 Z+Zk
NDMI066Algebraická teorie čísel(AP,AI)32/0 Zk
NDMI073Kombinatorika a grafy III(TG)62/2 Z+Zk
NGEM003Reprezentace Lieových grup 1(HA, RG)*62/2 Z+Zk
NGEM011Základy Riemannovy geometrie 1(RG)*62/2 Z+Zk
NGEM013Seminář z harmonické analýzy a teorie reprezentací I(HA, RG)*30/2 Z
NGEM035Reprezentace Lieových grup 2(HA, RG)*62/2 Z+Zk
NGEM036Základy Riemannovy geometrie 2(RG)*52/2 Z+Zk
NLTM001Teorie množin(ML)62/2 Z+Zk
NLTM005Topologická dynamika(DYN)32/0 Zk
NLTM011Pokročilá teorie modelů(ML, UL)62/2 Z+Zk
NMAA039Hyperkomplexní analýza(HA)*32/0 Zk
NMAI040Úvod do teorie čísel(KG)32/0 Zk
NMAT007Algebraická topologie 1(TTK, HA)*62/2 Z+Zk
NMAT008Algebraická topologie 2(TTK, HA)*62/2 Z+Zk
NMAT009Úvod do diferenciální topologie(RG, TTK)*32/0 Zk
NMAT026Reprezentace v kategoriích(TTK)*62/2 Z+Zk
NMAT042Obecná topologie II(TTK)*62/2 Z+Zk
NMIB004Samoopravné kódy(AI)*64/0 Zk
NMIB103Počítačová algebra II(AI)*32/0 Zk
NTIN022Pravděpodobnostní techniky(KG, TG)*62/2 Z+Zk
NTIN062Složitost I(KG, TG)52/1 Z+Zk

* vyučovány. Místo NALG016 lze zapsat NMAG561. Místo NALG021 lze zapsat NMAG438. Místo NALG029 lze zapsat NMAG434. Místo NALG033 lze zapsat NMAG431 a NMAG432. Místo NALG103 lze zapsat NMAG405. Místo NALG104 lze zapsat NMAG450. Místo NDMA001 lze zapsat NMIN331. Místo NGEM013 lze zapsat NMAG569. Místo NMAA039 lze zapsat NMAG461. Místo NMAT007 lze zapsat NMAG409. Místo NMAT008 lze zapsat NMAG532. Místo NMAT009 lze zapsat NMAG452. Místo NMAT042 lze zapsat NMMA462. Místo NMIB004 lze zapsat NMMB304. Místo NMIB103 lze zapsat NMMB403.

Státní závěrečná zkouška

Podmínky pro přihlášení ke státní závěrečné zkoušce

Získání alespoň 120 kreditů.
Splnění všech povinných předmětů studijního plánu.
Splnění povinně volitelných předmětů v rozsahu alespoň 15 kreditů.
Odevzdání vypracované diplomové práce ve stanoveném termínu.

Ústní část státní závěrečné zkoušky

Ústní část státní závěrečné zkoušky studijního oboru Matematické struktury se skládá ze společných požadavků z okruhů Algebra a logika a Geometrie a topologie a z požadavků užšího zaměření. Toto zaměření si posluchač určí volbou jednoho z témat uvedených níže.

Požadavky k ústní části státní závěrečné zkoušky

I. Společné požadavky

I.1 Algebra a logika

1. Grupy
Normální a subnormální řady. Zassenhausovo lemma a jeho důsledky. Horní a dolní centrální řada, stupeň nilpotence nilpotentní grupy a charakterizace konečných nilpotentních grup. Sylowovy věty. Komutant, řešitelné grupy. Struktura konečně generovaných Abelových grup. Působení grupy na množině a základní vlastnosti permutačních grup (jádro a stabilizátor působení, působení translací a konjugací.)

2. Okruhy a moduly
Struktura polojednoduchých (= totálně rozložitelných) modulů. Wedderburn-Artinova věta. Noetherovské a artinovské moduly, moduly konečné délky. Noetherovské a artinovské okruhy. Hopkinsova věta. Hilbertova věta o bázi. Moduly nad algebrami cest orientovaných grafů jako lineární representace těchto grafů. Volné moduly. Projektivní a injektivní moduly a jejich vztah k funktorům Hom. Kaplanského charakterizace projektivních modulů. Struktura injektivních modulů nad noetherovskými okruhy. Struktura divizibilních abelovských grup.

3. Komutativní algebry
Základy teorie komutativních noetherovských okruhů, Věta Artin-Reesova. Lomené ideály a Dedekindovy obory. Rozšíření homomorfizmů a valuační obory. Celistvá a slabě celistvá rozšíření oborů a okruhů.

4. Matematická logika
Výroková logika: dedukce, pravdivost, algebra výroků, filtry na algebrách výroků, normální tvary výroků. Dokazatelné, nerozhodnutelné a konsistentní výroky. Predikátová logika: jazyk 1. řádu, teorie, dokazatelnost, spornost, věty o dokazování, semantický model teorie 1. řádu, pravdivost, věta o existenci modelu, o kompaktnosti, o úplnosti. Úplnost teorie. Diagram, základní vztahy mezi modely, podmodel, rozšíření, elementární rozšíření, homomorfní, isomorfní a elementární vnoření. Příklady teorii a jejich základních vlastností, zejména s ohledem na úplnost (teorie uspořádání, Booleových algeber, aritmetiky, grafu). Teorie množin jako teorie 1. řádu.

I.2 Geometrie a topologie

1. Diferenciální geometrie
Křivky v E3, Frenetovy formule, křivost a torze a jejich význam. Rovinné křivky. Křivky s konstantní křivostí a torzí. Plochy v E3, první a druhá fundamentální forma, hlavní, Gaussova a střední křivost a jejich význam. Význačné křivky na ploše (hlavní, asymptotické křivky). Plochy s konstantní Gaussovou křivostí, přímkové plochy, minimální plochy (stručná charakterizace). Pojem kovariantní derivace na ploše, geodetické křivky na ploše. Příklady geodetických křivek.

2. Komplexní analýza
Holomorfní funkce, Cauchy-Riemannovy podmínky. Cauchyova věta, Cauchyova integrální formule a její aplikace na výpočet integrálu. Taylorova a Laurentova řada, příklady funkcí komplexní proměnné vzniklých rozšířením reálných funkcí (např. log, exp, goniometrické funkce). Residuum a residuová věta, základní příklady na výpočet integrálů.

3. Funkcionální analýza
Banachovy prostory, Hilbertovy prostory, jejich základní vlastnosti, příklady. Spojitá linearní zobrazení a jejich vlastnosti, Hahn-Banachova věta, věta o uzavřeném zobrazení, věta o uzavřeném grafu. Základy spektrální teorie kompaktních operátorů v Hilbertově prostoru. Adjungované operátory, samoadjungované operátory a jejich vlastnosti.

4. Obecná topologie
Topologický prostor, jeho základní popisy (otevřené a uzavřené množiny, uzávěrová operace, okolí atd.) Spojitá zobrazení a homeomorfismy. Podprostory, faktorprostory. Oddělovací axiomy a jejich význam pro vlastnosti prostoru. Separabilní topologické prostory, existence spočetné baze otevřených množin. Metrický prostor jako topologický prostor. Kompaktní prostory a jejich vlastnosti. Parakompaktní prostory, rozklad jednotky (existence). Příklady topologických prostorů s vymezenými vlastnostmi.

II. Užší zaměření

B1. Harmonická analýza a teorie reprezentací (HA)

1. Algebraická topologie
Fundamentální grupa prostoru — základní vlastnosti. Singulární homologická a kohomologická teorie, jejich základní vlastnosti. CW-komplexy — jejich elementární vlastnosti a určení jejich homologických grup. Některé aplikace algebraické topologie v analýze, topologii a geometrii. De Rhamova věta.

2. Teorie reprezentací
Klasifikace jednoduchých Lieových algeber. Souvislost mezi reprezentacemi Lieových grup a algeber. Klasifikace konečně-dimensionálních representací klasických Lieových algeber pomocí nejvyšších vah. Charaktery representací, některé formule pro charaktery.

3. Analýza na varietách
Vnější algebra vektorového prostoru, Diferenciální formy na varietě a jejich integrace. Forma objemu na riemannovské varietě a integrace funkcí. Variety s krajem, Stokesova věta.

4. Harmonická analýza
Homogenní prostory. Základní problémy harmonické analýzy na homogenních prostorech, invariantní operátory. Příklady (euklidovská rovina, sféra, hyperbolická rovina).

B2. Riemannova geometrie (RG)

1. Analýza na varietách
Vnější algebra vektorového prostoru, diferenciální formy na varietě a jejich integrace. Variety s krajem, Stokesova věta. Forma objemu na riemannovské varietě a integrace funkcí.

2. Riemannova geometrie
Definice afinní konexe a kovariantního derivování. Paralelní přenos vektoru podél křivky na varietě s konexí, geodetické křivky a jejich základní vlastnosti, exponenciální zobrazení v bodě variety. Pojem Riemannovy metriky a Riemannovy variety, izometrie Riemannových variet. Existence a jednoznačnost Riemannovy konexe, extremální vlastnosti geodetické křivky na Riemannově varietě. Prostory s konstantní křivostí. Divergence, gradient a Laplaceův operátor na Riemannově varietě.

3. Algebraická topologie
Fundamentální grupa prostoru — základní vlastnosti. Singulární homologická a kohomologická teorie, jejich základní vlastnosti. CW-komplexy — jejich elementární vlastnosti a určení jejich homologických grup. Některé aplikace algebraické topologie v analýze, topologii a geometrii. De Rhamova věta.

4. Homogenní prostory
Lieovy grupy a homogenní prostory. Invariantní formy a konexe na homogenním prostoru. Příklady klasických prostorů.

B3. Algebra v přírodních vědách (AP)

1. Teorie reprezentací
(a) Reprezentace grup: základní pojmy, reprezentace grup jako moduly nad grupovými algebrami; Maschkeho věta, věty o ortogonalitě, věta o stupni ireducibilní reprezentace, reprezentace nad tělesem komplexních čísel, tabulky charakterů; základní vlastnosti modulárních reprezentací.

(b) Reprezentace algeber: algebry cest grafů, lineární reprezentace grafů jako moduly nad algebrami cest, příklady.

2. Kategorie modulů a homologická algebra
(a) Moritovská ekvivalence okruhů, adjungovanost funktorů Hom a tenzorového součinu; Moritova charakteristická ekvivalence.

(b) Funktory Ext a Tor, jejich konstrukce a základní vlastnosti; homologická dimenze okruhů a modulů; vztah Ext a rozšíření modulů.

3. Aproximace modulů
(a) Základní pojmy, metody dekonstrukce kotorzních párů, aproximace třídami modulů omezené homologické dimenze.

(b) Vychylující aproximace: základní vlastnosti a příklady, vztahy k Moritovské ekvivalenci a k Bassovým hypotézám.

4. Komutativní algebra
(a) Lokalizace a ploché moduly, prvoideály a primární rozklady, Krullova věta, Krullova dimenze, I-adická zúplnění.

(b) Celistvá rozšíření, valuační, Dedekindovy a Prüferovy obory.

B4. Algebra v informatice (AI)

1. Univerzální algebra a přepisující systémy
Subdirektně ireducibilní algebry. Volné algebry, variety, Birkhoffova věta. Věty Malcevova typu Variety s distributivními kongruencemi. Konvergence v grafech. Unifikace termů. Kritické dvojice pro přepisující systém. Knuth-Bendixův algoritmus. Simplifikační dobré kvaziuspořádání a jeho význam pro terminovanost, Knuth-Bendixovo kvaziuspořádání.

2. Počítačová algebra
Karacubův a Strassenův algoritmus. Rychlá Fourierova transformace, rychlé násobení. Rozšířený Euklidův algoritmus a jeho varianty. Modulární reprezentace, zobecněná čínská věta o zbytcích. Garnerův algoritmus na interpolaci polynomů. Berlekampův algoritmus na faktorizaci polynomů. Groebnerovy báze, Buchbergerův algoritmus, aplikace.

3. Kombinatorická teorie grup
Volné součiny grup a jejich prezentace, Nielsenova a Reidemeister-Schreierova metoda použitá pro podgrupy volných grup. HNN rozšíření a volné součiny s amalgamovanou podgrupou včetně normální formy a Brittonova lemmatu. Fundamentální grupa 2-komplexu. Problém slov a konjugace, jejich rozhodnutelnost.

4. Kódy
Kapacita kanálu, pravděpodobnost chyby a Shannonova věta, odhady a meze, perfektní kódy. Lineární, cyklické, Hammingovy, Reed-Mullerovy, Golayovy, BCH a QR kódy. Metody dekódování.

B5. Matematická logika a teorie množin (ML)

1. Nerozhodnutelnost a neúplnost
Rekursivní funkce a rekursivně spočetné množiny. Formalisace syntaxe. Rozhodnutelné a nerozhodnutelné teorie. Gödelova a Rosserova věta o neúplnosti. Formalisace dokazatelnosti, nedokazatelnost bezespornosti, Lobova věta. Nestandardní modely přirozených čísel.

2. Teorie modelů
Existence modelů, kompaktnost, Lowenheim-Skolemovy věty. Diagramy, homomorfismus, vnoření. Řetěz modelů. Lindenbaumovy algebry. Typy, věta o pomíjení typů a její důsledky. Saturované modely, jednoznačnost, existence, aplikace. Omega-kategoričnost. Universální, homogenní a minimální modely. Ultraprodukt, fundamentální věta, regulární ultramocnina.

3. Transfinitní čísla, transitivní modely
Ordinální funkce, ordinální a kardinální aritmetika. Velké kardinály, nedosažitelný a měřitelný kardinál. Ramseyovy věty. Fundované relace, fundovaná indukce a rekurse. Věta o kolapsu a kompresi, fundované jádro. Transitivní modely. Konstruovatelné množiny.

4. Generické rozšíření. Nestandardní teorie
Booleovské universum. Generické rozšíření. Algebra C(kappa). Negace hypotézy kontinua. Nestandardní teorie množin: standardní, internální a externální množiny. Princip standardisace, saturovanosti a finitarisace. Nestandardní čísla, spojitost, derivace.

B6. Univerzální algebra a matematická logika (UL)

1. Univerzální algebra a přepisující systémy
Subdirektně ireducibilní algebry. Volné algebry, variety, Birkhoffova věta. Věty Malcevova typu Variety s distributivními kongruencemi. Konvergence v grafech. Unifikace termů. Kritické dvojice pro přepisující systém. Knuth-Bendixův algoritmus. Simplifikační dobré kvaziuspořádání a jeho význam pro terminovanost, Knuth-Bendixovo kvaziuspořádání.

2.Kombinatorická teorie grup
Volné součiny grup a jejich prezentace, Nielsenova a Reidemeister-Schreierova metoda použitá pro podgrupy volných grup. HNN rozšíření a volné součiny s amalgamovanou podgrupou včetně normální formy a Brittonova lemmatu. Fundamentální grupa 2-komplexu. Problém slov a konjugace, jejich rozhodnutelnost.

3. Teorie modelů
Existence modelů, kompaktnost, Lowenheim-Skolemovy věty. Diagramy, homomorfismus, vnoření. Řetěz modelů. Lindenbaumovy algebry. Typy, věta o pomíjení typů a její důsledky. Saturované modely, jednoznačnost, existence, aplikace. Omega-kategoričnost. Universální, homogenní a minimální modely. Ultraprodukt, fundamentální věta, regulární ultramocnina.

4. Nerozhodnutelnost a neúplnost
Rekursivní funkce a rekursivně spočetné množiny. Formalisace syntaxe. Rozhodnutelné a nerozhodnutelné teorie. Gödelova a Rosserova věta o neúplnosti. Formalisace dokazatelnosti, nedokazatelnost bezespornosti. Lobova věta. Nestandartní modely přirozených čísel.

B7. Obecná topologie a teorie kategorií (TTK)

1. Obecná topologie
Základní topologické pojmy. Kompaktní a lokálně kompaktní prostory — Tichonovova věta, kompaktifikace, Čech-Stoneova kompaktifikace, kontinua. Pokrývací vlastnosti — kolektivní normalita, Lindelofovy prostory, parakompaktnost, metrizační věty. Metrizovatelné prostory — úplnost, totální omezenost, čechovsky úplné prostory, Baireova věta. Uniformní prostory — stejnoměrně spojitá zobrazení, vztah k topologii, jemná uniformita, uniformizovatelnost, úplnost. Teorie dimenze: dim, ind, Ind, věty o monotonii, věty o shodě dimenzí, příklady.

2. Topologické grupy a Lieovy grupy
Topologické grupy — levá a pravá uniformita, věta o otevřené poddgrupě, volné topologické grupy. Základy teorie Lieových grup, příklady Lieových grup.

3. Teorie kategorií
Základní pojmy teorie kategorií, Speciální funktory, Yonedovo lemma, Yonedovo vnoření. Koma-kategorie, hustota. Adjungované funktory, věty o adjungovaných funktorech (AFT a SAFT) a jejich použití. Aplikace v obecné topologii a algebře.

4. Algebraická topologie
Fundamentální grupa prostoru — základní vlastnosti. Singulární homologická a kohomologická teorie, jejich základní vlastnosti. CW-komplexy — jejich elementární vlastnosti a určení jejich homologických grup. Některé aplikace algebraické topologie v analýze, topologii a geometrii. Věta o universálních koeficientech a Kunnethova formule.

B8. Dynamika (DYN)

1. Systémy diferenciálních rovnic
Systémy diferenciálních rovnic prvního řádu, stacionární body a jejich stabilita, linearizace, stabilní a nestabilní varieta, Ljapunovovy funkce, strukturální stabilita, bifurkace.

2. Dynamické systémy
Topologické dynamické systémy, trajektorie, pseudotrajektorie, periodické body a jejich stabilita, minimální, transitivní a chaotické systémy, distální a proximální systémy, atraktory, oblasti atrakce, rekurentní body, symbolická dynamika, topologická entropie.

3. Stochastické procesy
Stochastické procesy a jejich rozdělení, korelační funkce, stacionární procesy, Markovské procesy a řetězce.

4. Ergodická teorie
Metrické dynamické systémy, ergodické věty (von Neumannova a Birkhofova), dekompozice invariantní míry na ergodické složky, isomorfismus a spektrální ekvivalence, Lebesgueovo a bodové spektrum, entropie.

B9. Teorie grafů a kombinatorické algoritmy (TG)

1. Grafy
Orientované a neorientované grafy, isomorfismus grafů. Prostor cyklů v grafu. Stromy, ekvivalentní definice, počet stromů, isomorfismus stromů. Kostry grafu, počet koster grafu. Hamiltonovské kružnice. Souvislost grafu. Barevnost grafu a hranová barevnost. Rovinné grafy, Eulerův vztah, Kuratowského věta, barevnost rovinných grafů. Bipartitní grafy. Tuttova věta. Náhodné grafy a pravděpodobnostní metoda. Szemerédi Regularitz Lemma a Removal Lemma.

2. Kombinatorika
Kombinatorické počítání, princip inkluze a exkluze, vytvořující funkce. Hallova věta o systému různých reprezentantů, Birkhoffova věta o bistochastických maticích. Ramseyova teorie, Schurovo lemma, Hales-Jewettova věta, van der Wardenova věta.

3. Algoritmy
Dijkstrův algoritmus pro nejkratší cestu. Algoritmy pro toky v sítích. Hledání párování v bipartitních obecných grafech. Minimální kostra grafu, hladový algoritmus a jeho souvislost s matroidy.

4. Výpočetní složitost
Modely výpočtu (Turingův stroj), vztahy mezi časovými a prostorovými mírami a determinismem a nedeterminismem. Savitchova věta. Úplné problémy pro třídy NP a PSPACE. Polynomiální hierarchie. Pseudopolynomiální algoritmy. Aproximační algoritmy a schémata.

B10. Kombinatorická geometrie a geometrické algoritmy (KG)

1. Konvexita
Věty o konvexních množinách, vlastnosti konvexních mnohostěnů (např. kombinatorická složitost), perfektní grafy, konvexita a kombinatorické optimalizace (elipsoidová metoda, lineární programovaní).

2. Kombinatorická geometrie
Složitost arrangementu nadrovin (věta o zóně), kombinatorika bodů a přímek v rovině, geometrické reprezentace grafů a uspořádaných množin (průnikové a inkluzní).

3. Výpočetní geometrie
Voroného diagram a Delaunayova triangulace, arrangementy nadrovin, stratégie návrhu geometrických algoritmů (pravděpodobnostní, inkrementální), příklady efektivních algoritmů pro konkrétní problémy (problém lokalizace bodu, výpočet konvexního obalu, konstrukce arrangementu, lineární programování v malé dimenzi, triangulace mnohoúhelníka v rovině).

4. Teorie čísel
Aproximace reálných čísel zlomky, rozložení prvočísel, geometrické metody (mřížky, Minkovského věta), teorie kongruencí (kvadratické zbytky).

© 2013–2017 Univerzita Karlova, Matematicko-fyzikální fakulta. Design noBrother.
Za obsah odpovídá Studijní oddělení.