AdamátorZápiskyHlášky

Příprava na státní závěrečnou zkoušku (MINF magisterské studium)

Zde jsou mnou vypracované odpovědi na zkouškové otázky ke zkouškovým předmětům Teorie grafů, Teorie čísel a Jazyky a automaty.

Některé věci jsem si dovolil formulovat jinak než odpovídající vyučující, protože mi to přišlo jednodušší/přehlednější.

Teorie grafů

1. Lesy a stromy: definice, charakterizační věty. Úloha minimální kostry, Kruskalův algoritmus, počet koster grafu, počet stromů na daném počtu vrcholů.
Definice Nenulový graf G=(V,E) je strom, pokud platí jedna z ekvivalentních definic:
  1. G je souvislý a neobsahuje cyklus.
  2. Mezi každými dvěma vrcholy existuje právě jedna cesta.
  3. G je souvislý a všechny tahy jsou cesty.
  4. G neobsahuje cyklus a přidáním libovolné hrany vznikne cyklus.
  5. G je souvislý a každá hrana je most.
  6. G je souvislý a |V|=|E|+1.
  7. G neobsahuje cyklus a |V|=|E|+1.
Definice Les je acyklický graf.
Definice Kostra grafu je faktor, který je strom.
Věta Nechť Gw je vážený graf, přičemž w je prostá funkce. Potom existuje právě jedna kostra T taková, že ∑e∈E(T)w(e) je minimální.
Definice Této kostře říkáme minimální kostra.
Algoritmus Kruskalův pro hledání minimální kostry Pro daný vážený graf Gw seřaďme hrany tak, že w(e1)<⋯<w(em). Začneme s prázdným grafem. Pro i=1,…,m se postupně podíváme, jestli by přidáním hrany ei vznikl cyklus, a pokud ne, tak ji přidáme.
Věta Cayleyova formule Počet stromů na n vrcholech je nn−2.
Definice Laplaceova matice multigrafu G=([n],E,w) je matice LG∈ℕ0n×n definovaná jako (LG)i,j≔−w({i,j}), kde jako váhu neexistující hrany bereme 0 a za (LG)i,i volíme degG(i).
Věta Kirchhoffova Počet koster grafu G=([n],E,w) můžeme pro libovolné i∈[n] spočítat jako T(G)=detLG(i).
2. Vrcholová a hranová souvislost: definice, Mengerova věta, grafové posloupnosti (skóre grafu), algoritmus pro určení souvislosti komponent grafu.
Definice Nechť G=(V,E) a u,w∈V. Potom pG(u,w) je maximální počet vnitřně vrcholově disjunktních cest z u do w.
Definice Graf G=(V,E) je (vrcholově) k-souvislý, jestliže pro všechny vrcholy u,w∈V je pG(u,w)≥k.
Definice Nechť G=(V,E) a u,w∈V,{u,w}∉E. Potom cG(u,w) je minimální velikost množiny W takové, že v G−W neexistuje cesta z u do w.
Věta Mengerova, vrcholová varianta, lokální příchuť Pro každý graf G=(V,E) a vrcholy u,w∈V,{u,w}∉E je pG(u,w)=cG(u,w).
Věta Mengerova, vrcholová varianta, globální příchuť Graf je k-souvislý, právě když má alespoň k+1 vrcholů a po odstranění libovolných k−1 vrcholů je souvislý.
Definice Nechť G=(V,EM) je multigraf a u,w∈V,u≠w. Potom p′(u,w) je maximální k takové, že existuje k hranově disjunktních cest z u do w. G je hranově k-souvislý, pokud pro všechna u,w∈V,u≠w je p′(u,w)≥k. κ′(G) je největší k takové, že G je hranově k-souvislý.
Definice Nechť G=(V,EM) je multigraf a u,w∈V,u≠w. Potom c′(u,w) je minimální počet hran, které je nutné odstranit, aby neexistovala cesta z u do w.
Věta Mengerova, hranová verze, lokální příchuť Nechť G=(V,EM) je multigraf a u,w∈V,u≠w. Potom cG′(u,w)=pG′(u,w).
Věta Mengerova, hranová verze, globální příchuť alias Fordova-Fulkersonova Multigraf je hranově k-souvislý, právě když po odstranění libovolných k−1 hran je souvislý.
Definice Skóre grafu s vrcholy [n] je (d1,…,dn), kde di≔degG(i).
Věta Nechť 0≤d1≤⋯≤dn<n. Potom existuje graf velikosti n se skórem (d1,…,dn), právě když existuje graf velikosti n−1 se skórem
(d1,d2,…,dn−dn−2,dn−dn−1,dn−dn−1,dn−dn+1−1,…,dn−2−1,dn−1−1).

Pro nalezení souvislých komponent grafu lze použít například prohledávání do hloubky nebo do šířky.

3. Párování v grafu: definice, rozhodování o maximalitě párování, vztah maximálního párování a minimálního pokrytí, algoritmus pro maximální párování s využitím toků v sítích.
Definice Nechť G=(V,E) je graf. Množina M⊂E je párování v G, pokud každé dvě hrany jsou disjunktní. Největší možnou velikost párování označíme ν(G).
Definice Nechť G=(V,E) je graf. Množina X⊂V je vrcholové pokrytí v G, pokud každá hrana obsahuje alespoň jeden vrchol z X. Nejmenší možnou velikost vrcholového pokrytí označíme τ(G).
Věta Pro každý graf G je ν(G)≤τ(G)≤2ν(G).
Definice Nechť M je párování v grafu G. Cesta v G je M-střídavá, pokud se v ní střídají hrany v M a mimo M. M-střídavá cesta je M-zlepšující, pokud její počáteční a koncový vrchol neleží v žádné hraně M.
Lemma Bergeovo Párování M je maximální, právě když neexistuje M-zlepšující cesta.
Věta Königova Je-li graf G bipartitní, potom τ(G)=ν(G).
4. Perfektní párování: definice, věty o existenci perfektního párování v bipartitním grafu a obecném grafu.
Definice Nechť G=(V,E) je graf. Sousedství množiny S⊂V je NG(S)≔⋃x∈SNG(x).
Definice Párování M v grafu G=(V,E) je perfektní, pokud |M|=|V|2.
Věta Hallova Nechť G je bipartitní graf s partitami A,B. Potom ν(G)=|A|, právě když ∀S⊂A:|NG(S)|≥S.
Definice Je-li G graf, potom odd(G) je počet komponent souvislosti liché velikosti v G.
Definice Bariéra v grafu G=(V,E) je množina B⊂V taková, že odd(G−B)>|B|.
Důsledek Tutte Graf má perfektní párování, právě když ∀B⊂V:|B|≥odd(G−B) neboli neobsahuje bariéru.
5. Eulerovské a hamiltonovské grafy: definice, Eulerovy věty pro cykly a sledy, postačující podmínky pro existenci hamiltonovské kružnice v grafu.
Definice Eulerovský tah v multigrafu je tah, který obsahuje všechny hrany. Eulerovská kružnice v multigrafu je uzavřený tah, který obsahuje všechny hrany.
Věta Eulerova V multigrafu bez izolovaných vrcholů existuje eulerovská kružnice, právě když je souvislý a sudý.
Důsledek V multigrafu bez izolovaných vrcholů existuje eulerovský tah, právě když je souvislý a existují nanejvýš dva vrcholy lichého stupně.
Definice Graf je hamiltonovský, pokud obsahuje cyklus procházející všechny vrcholy (hamiltonovskou kružnici).
Poznámka Na rozdíl od eulerovského tahu nelze efektivně určit, jestli je graf hamiltonovský. Konkrétně je to NP-úplná úloha.
Věta Ore Nechť graf G=(V,E),|V|≥3 splňuje podmínku
∀u,v∈V:{u,v}∉E⟹degG(u)+degG(v)≥|V|,
potom je hamiltonovský.
Důsledek Dirac Má-li graf G=(V,E),|V|≥3 minimální stupeň alespoň |V|2, potom je hamiltonovský.
6. Hranová barevnost: definice, vztah k párování, Koenigova věta, optimální obarvení, Vizingova věta, aplikace při tvorbě rozvrhu.
Definice Nechť k∈ℕ. Hranové k-obarvení multigrafu G=(V,EM) je funkce c:EM→[k] taková, že pro každé i∈[k] je c−1(i) párování. Hranová barevnost G je nejmenší k takové, že existuje hranové k-obarvení; značíme ji χ′(G).
Poznámka Zjevně χ′(G)≥Δ(G). Ovšem rovnost obecně neplatí, například χ′(C3)=3, ale Δ(C3)=2.
Věta Königova Je-li G=(V,EM) bipartitní multigraf, potom χ′(G)=Δ(G).
Věta Vizingova Pro každý graf G=(V,E) platí χ′(G)≤Δ(G)+1.
Poznámka Pro multigrafy věta neplatí. Vezmeme-li například „tlustý trojúhelník“, který má tři vrcholy a každé dva jsou spojené μ hranami, potom χ′(G)=3μ a Δ(G)=2μ.

Aplikace při tvorbě rozvrhu: Máme-li například graf, kde jsou propojeni vyučující a třídy, přičemž hrany reprezentují hodinu, potom můžeme obarvit hrany několika možnými časy, abychom určili, kdy bude jaká hodina.

7. Vrcholová barevnost: definice, odhady vrcholové barevnosti grafu, kritické grafy, Brooksova věta, vrcholová barevnost planárního grafu.
Definice Nechť k∈ℕ. Vrcholové k-obarvení grafu G=(V,E) je funkce c:V→[k] taková, že pro každé i∈[k] je c−1(i) nezávislá množina. Vrcholová barevnost G je nejmenší k takové, že existuje hranové k-obarvení; značíme ji χ(G).
Poznámka Bipartitní graf můžeme ekvivalentně definovat jako 2-obarvitelný.
Pozorování Pro každý graf G je χ(G)≤Δ(G)+1.
Definice Nechť d∈ℕ0. Graf G=(V,E) je d-degenerovaný, pokud je nulový nebo existuje v∈V takový, že deg(v)≤d a G−v je d-degenerovaný.
Pozorování Pro d-degenerovaný graf G je χ(G)≤d+1.
Definice Klika v grafu G=(V,E) je množina W⊂V taková, že podgraf indukovaný W je úplný. Velikost největší kliky v grafu značíme ω(G).
Pozorování Pro každý graf G je χ(G)≥ω(G).
Věta Brooksova Pro neúplný souvislý graf G s Δ(G)≥3 platí χ(G)≤Δ(G).
Definice Nechť k∈ℕ. Graf G je k-kritický, pokud χ(G)=k a pro všechny podgrafy H je χ(H)<k.
Pozorování Každý graf G s χ(G)≥k obsahuje k-kritický podgraf.
Pozorování Je-li graf k-kritický, potom je souvislý.
Věta o čtyřech barvách Každý rovinný graf jde obarvit čtyřmi barvami.
8. Planární grafy: definice, vztah planarity a počtu hran, minimální neplanární grafy, Kuratowského věta.
Definice Nakreslení grafu G=(V,E) je (g,(fe)E), kde g:V→ℝ2 je prostá funkce, pro každé e∈E je fE:[0,1]→ℝ2 prostá spojitá funkce a pro každou hranu e∈E platí
{fe(0),fe(1)}=g(e)∧fe((0,1))∩g(V)=∅.
Nakreslení je rovinné, pokud pro všechny e1,e2∈E je fe1((0,1))∩fe2((0,1))=∅.
Definice Graf je rovinný, pokud pro něj existuje rovinné nakreslení (g,(fe)E). Potom (G,g,(fe)E) je topologický rovinný graf. Značíme G.
Věta Eulerův vzorec Nechť G=(V,E) je rovinný graf a s je počet stěn v nějakém jeho nakreslení. Potom
|V|−|E|+s=1+comp(G).
Důsledek Je-li G=(V,E) rovinný graf s |V|≥3, potom |E|≤3|V|−6. Pokud navíc G neobsahuje trojúhelník, potom |E|≤2|V|−4.
Věta minimální nerovinné grafy Grafy K5 a K3,3 nejsou rovinné.
Definice Graf H je podrozdělení grafu G, pokud existuje posloupnost grafů G=G0,G1,…,Gk−1,Gk=H taková, že Gi+1=Gi:ei pro nějaké ei∈E(Gi). Je-li H podgraf nějakého grafu F, potom F obsahuje podrozdělení G.
Věta Kuratowského Graf G=(V,E) je rovinný, právě když neobsahuje podrozdělení K5 nebo K3,3.
9. Adjacenční matice grafu: definice, základní vlastnosti spektra adjacenční matice, vztah spektrálního poloměru k některým charakteristikám grafu, spektrum regulárního a bipartitního grafu.
Definice Matice sousednosti multigrafu G=([n],E,w) je matice AG∈ℕ0n×n definovaná jako (AG)i,j≔w({i,j}), kde jako váhu neexistující hrany bereme 0.
Věta Nechť G je multigraf a k∈ℕ0. Potom (AGk)i,j je počet sledů délky k z vrcholu i do vrcholu j.
Definice Spektrum grafu G je množina vlastních čísel AG.
Věta Nechť G je graf a λ1 je jeho největší vlastní číslo. Potom Δ(G)≥λ1≥avgdeg(G)≥δ(G).
Důsledek Pro d-regulární graf je λ1=d.
Věta Nechť G=([n],E) je souvislý graf s alespoň dvěma vrcholy, λ1 je největší vlastní číslo AG a v je příslušný vlastní vektor. Potom buď v>0, nebo v<0.
Věta Nechť G=([n],E) je souvislý graf se spektrem (λ1,…,λn). Potom λn=−λ1, právě když G je bipartitní.
10. Toky v sítích: definice sítě a toku. Vztah maximálního řezu a minimálního toku, aplikace v teorii grafů.
Definice Tok v digrafu z vrcholu s do vrcholu t je funkce φ:E→ℕ0 taková, že pro všechna w∈V∖{s,t} platí Kirchhoffův zákon:
∑e∈∂−(w)φ(e)=∑e∈∂+(w)φ(e).
Hodnota toku je val(φ)≔∑e∈∂+(s)φ(e)−∑e∈∂−(s)φ(e). Nosič toku je supp(φ)≔{e∈A|φ(e)>0}.
Lemma Je-li φ tok v digrafu G=(V,A), potom existuje tok φ′ v G se stejnou hodnotou, jehož nosič je acyklický faktor G.
Definice Kapacita hran digrafu G=(V,A) je funkce c:E→ℕ0. Tok φ je c-přípustný, pokud ∀e∈A:φ(e)≤c(e).
Definice Síť je pětice (V,A,s,t,c), kde (V,A) je digraf, s,t∈V a c je kapacita.
Definice Nechť φ je tok v síti (V,A,s,t,c). Neorientovaná cesta P=(s=v0,e1,…,vl=t) je φ-zlepšující cesta, pokud pro každou hranu ei platí:
  • je-li orientovaná po směru, potom φ(ei)≤c(ei)−1,
  • je-li orientovaná proti směru, potom φ(ei)≥1.
Lemma Existuje-li k c-přípustnému toku φ v síti zlepšující cesta P, potom existuje c-přípustný tok ψ s val(ψ)=val(φ)+1.
Definice Nechť (V,A,s,t,c) je síť. Kapacita množiny {s}⊂X⊂V∖{t} je
cap(X)≔∑e∈∂G+(X)c(e).
Věta Fordova-Fulkersonova Nechť Φ je množina všech přípustných toků v síti (V,A,s,t,c). Potom
maxφ∈Φval(φ)=min{s}⊂X⊂V∖{t}cap(X).

Teorie čísel

1. Aproximace reálných čísel zlomky, Fareyovy a řetězové zlomky, Hurwitzova věta, řetězový zlomek kvadratického čísla, řetězový zlomek čísla e.
Definice Nechť n∈ℕ. Potom Fareyovy zlomky řádu n jsou posloupnost 0=f0<f1<⋯<fk=1, kde
{f0,…,fk}=ℱn≔{pq|p≤q≤n}.
Zlomky budeme vždy uvažovat v základním tvaru.
Věta Pro každé n∈ℕ je
#ℱn=1+∑d=1nφ(d).
Věta Pro každé dva po sobě jdoucí Fareyovy zlomky ab<cd platí c⋅b−a⋅d=1.
Věta mediánová vlastnost Pro každé tři po sobě joucí Fareyovy zlomky ab<ef<cd platí, že prostřední je „špatně spočtený součet“ krajních:
ef=a+cb+d.
Věta Dirichletova Pro každé ξ∈ℝ∖ℚ existuje pq∈ℚ takové, že
Definice Nechť ξ∈ℝ. Označme ξ0≔ξ. Pro každé i∈ℕ vezmeme ai≔⌊ξi⌋. Pokud ξi∈ℤ, potom zastavíme, jinak ξi+1≔1ξi−ai. Potom (ai) je řetězový zlomek pro ξ. Značíme ξ=[a0;a1,…].
Poznámka Název je odvozen z toho, že platí
ξ=a0+1a1+1⋱+1an+1ξn+1.
Věta Řetězový zlomek čísla ξ∈ℝ je konečný, právě když ξ∈ℚ.
Definice Označme pnqn n-tý sblížený zlomek (částečný řetězový zlomek) (což se dá vyjádřit pomocí kontinuálních polynomů).
Věta Nechť ξ∈ℝ∖ℚ má částečný řetězový zlomek ξ=[a0;a1,…,an,ξn+1]. Potom
ξ−pnqn=(−1)nqn(qn−1+ξn+1qn).
Důsledek
limn→∞pnqn=ξ.
Důsledek
p2nq2n<ξ<p2n+1q2n+1.
Důsledek
|ξ−pnqn|<1qnqn+1.
Poznámka Navíc můžeme odhadnout
|ξ−pnqn|<1qn2,
čímž dostáváme alternativní důkaz Dirichletovy věty.
Důsledek
|ξ−pnqn|>1qn+1qn+2.
Poznámka Z toho plyne, že aproximace se v každém kroku zlepšuje.
Důsledek
|ξqn+1−pn+1|<1qn+1.
Poznámka Z toho se dá odvodit, že řetězové zlomky jsou v určitém smyslu nejlepší aproximace.
Definice Nechť ξ∈ℝ∖ℚ. Zlomek rs je nejlepší aproximace ξ, pokud pro každé pq∈ℚ,q≤s,pq≠rs platí
|ξ⋅q−p|>|ξ⋅s−r|.
Věta Nejlepší aproximace ξ∈ℝ∖ℚ jsou právě jeho sblížené zlomky.
Věta Hurwitzova Pro každé ξ∈ℝ∖ℚ existuje nekonečně mnoho zlomků pq∈ℚ takových, že
|ξ−pq|<15⋅q.
Zároveň tvrzení neplatí pro žádnou konstantu větší než 5.
Poznámka Takovouto aproximací je vždy jeden ze tří po sobě jdoucích řetězových zlomků.
Věta Lagrangeova Řetězový zlomek iracionálního čísla ξ je periodický, právě když ξ je kvadratické číslo.
Věta Řetězový zlomek Eulerova čísla je
𝕖=[2;1,2,1,1,4,1,1,6,1,1,8,1,…]
2. Transcendence, Liouvilleova čísla.
Věta Liouvillova Pro každé algebraické číslo α stupně d≥2 existuje c>0 takové, že pro každé pq∈ℚ je
|α−pq|≥cqd.
Věta Číslo
α≔∑n=1∞10−n!
je transcendentní.
Věta Nechť pro α∈ℝ∖ℚ existuje prostá posloupnost (pnqn) taková, že pro každé n∈ℕ platí
|α−pnqn|<1qnn.
Potom α je transcendentní.
Definice Čísla splňující podmínku v předchozí větě se nazývají Liouvillova.
Poznámka Existují i transcendentní čísla, která nejsou Liouvillova, například π,𝕖 nebo Champernowneova konstanta:
α≔0.123456789101112131415…
Věta Každé reálné číslo α je součet dvou Liouvillových čísel.
Věta Rothova Nechť α∈ℝ∖ℚ je algebraické číslo. Potom pro každé ε>0 existuje c>0 takové, že pro všechna pq∈ℚ je
|α−pq|≥cq2+ε.
3. Diofantické rovnice, lineární diofantické rovnice, existence a struktura řešení Pellovy rovnice, kvadratická rezidua, součet dvou a čtyř čtverců.
Věta Nechť |B|<d. Pokud x⟂y jsou řešení Pellovy rovnice x2−dy2=B, potom xy=pnqn, kde pnqn je sblížený zlomek pro d.
Věta Nechť d∈ℕ,d∉ℕ. Potom řešení x,y∈ℤ Pellovy rovnice x2−dy2=−1 existuje, právě když perioda l řetězového zlomku pro d je lichá. Zároveň řešení Pellovy rovnice x2−dy2=1 existuje a platí:
  • pokud l je sudé, potom x=pkl−1,y=qkl−1;
  • pokud l je liché, potom x=p2kl−1,y=q2kl−1.
Věta Nechť d∈ℕ,d∉ℕ. Pak existuje řešení x0,y0∈ℤ rovnice x2−dy2=1 takové, že každé řešení splňuje
x+d⋅y=±(x0+d⋅y0)n.
Věta Existuje-li řešení rovnice x2−dy2=B, potom jich existuje nekonečně mnoho.
Definice Nechť n∈ℕ. Číslo y∈ℤn je kvadratický zbytek modulo n, pokud existuje x∈ℤn takové, že y=x2. Množinu všech kvadratických zbytků modulo n značíme ℛn.
Příklad ℛ2=ℛ3=ℛ4={0,1}.
Věta Pro každé n∈ℕ je #ℛn≤1+⌊n2⌋. Navíc je-li n∈ℙ, potom nastává rovnost.
Věta Je-li p∈ℙ, potom −1∈ℛp, právě když p=2 nebo p≡1(mod4).

Uvažujme množinu

M≔{a2+b2|a,b∈ℤ}.
Pozorování Pro každé k∈ℕ je k2∈M.
Pozorování Je-li k∈ℕ,n∈M, potom k2⋅n∈M.
Pozorování Je-li n∈ℕ,n≡3(mod4), potom n∉M.
Věta Je-li n,n′∈M, potom n⋅n′∈M.
Věta Každé p∈ℙ,p≡1(mod4) se dá vyjádřit právě jedním způsobem jako součet dvou čtverců (až na pořadí).
Věta Číslo n∈ℕ se dá vyjádřit jako součet dvou čtverců, právě když každé prvočíslo kongruentní s 3 modulo 4 se v prvočíselném rozkladu n vyskytuje v sudé mocnině.
4. Algebraická a algebraická celá čísla, vlastnosti minimálního polynomu, vlastnosti množiny algebraických čísel. Gaussovo lemma o faktorizaci polynomů, Eisensteinovo kritérium ireducibility.
Definice Nechť S⊂T jsou tělesa. Prvek α∈T je algebraický nad S, pokud existuje polynom f∈S[x] takový, že f(α)=0. Množinu algebraických komplexních čísel nad ℚ značíme 𝔸.
Věta Je-li α∈T algebraický nad S, potom existuje právě jeden monický polynom f∈S[x] minimálního stupně takový, že f(α)=0. Navíc je-li g∈S[x] libovolný polynom splňující g(α)=0, potom f|g.
Definice Polynom f z této věty nazveme minimální polynom prvku α.
Věta Minimální polynom f algebraického prvku α∈T nad S je ireducibilní nad S. Naopak pokud je nějaký monický polynom f∈S[x] s kořenem α ireducibilní nad S, potom je to minimální polynom α.
Věta 𝔸 je podtěleso ℂ.
Poznámka Dokazuje se pomocí tenzorového součinu doprovodných matic.
Lemma Gaussovo Nechť F,G,H∈ℤ[x],F=G⋅H. Dělí-li p∈ℙ všechny koeficienty f, potom dělí všechny koeficienty g nebo všechny koeficienty h.
Definice Číslo α∈ℂ je algebraické celé, pokud existuje monický polynom f∈ℤ[x] s kořenem α. Množinu všech algebraických celých čísel značíme 𝔹.
Věta Nechť α∈𝔸. Potom α∈𝔹, právě když minimální polynom α je celočíselný.
Věta Eisensteinovo kritérium ireducibility Nechť f(x)=xn+∑i=0n−1aixi∈ℤ[x] je polynom takový, že nějaké prvočíslo p∈ℙ dělí všechny ai pro i=0,…,n−1, ale p2∤a0. Potom f je ireducibilní nad ℚ.
5. Číselná tělesa 𝐐(α), isomorfismy mezi tělesy 𝐐(αi), rozkladové těleso polynomu, Galoisovy automorfismy, sdružené kořeny algebraického čísla, tělesový polynom, norma, stopa.
Definice Nechť α∈𝔸. Potom definujeme
ℚ(α)≔⋂{T⊂ℂ|Ttěleso,α∈T}.
Věta Nechť α∈𝔸 stupně n. Potom
ℚ(α)={∑i=0n−1aiαi|ai∈ℚ}={g(α)|g∈ℚ[x],degq<n}.
Věta Nechť α,αi∈𝔸 jsou algebraicky sdružené. Potom ℚ(α)≃ℚ(αi).
Věta Je-li α∈𝔸 stupně n, potom ℚ(α) je lineární prostor nad ℚ dimenze n s bází 1,α,…,αn−1.
Věta Nechť α,β∈𝔸. Potom existuje γ∈𝔸 takové, že ℚ(α,β)=ℚ(γ).
Poznámka Z toho indukcí plyne, že pro libovolnou konečnou M⊂𝔸 existuje γ∈𝔸 takové, že ℚ(M)=ℚ(γ).
Definice Nechť α=α1,α2,…,αn∈𝔸 jsou algebraicky sdružená stupně n a β=g(α)∈ℚ(α). Potom tělesový polynom pro β je
Pβ(x)≔∏i=1n(x−σi(β)).
Definice Nechť α=α1,…,αn jsou sdružené a β∈ℚ(α). Potom
  • norma β v ℚ(α) je
    N(β)≔∏i=1nσi(β),
  • stopa β v ℚ(α) je
    Tr(β)≔∑i=1nσi(β).
Poznámka Všimněme si, že norma a stopa jsou (až na znaménko) koeficienty stupně 0, resp. n−1 u Pβ, z čehož plyne, že jsou racionální.
Věta multiplikativita normy Nechť β,γ∈ℚ(α). Potom
N(β⋅γ)=N(β)⋅N(γ).
Věta aditivita stopy Nechť β,γ∈ℚ(α). Potom
Tr(β+γ)=Tr(β)+Tr(γ).
Věta Nechť β∈𝔸. Potom
TrMβ=Trℚ(β)(β).
6. Okruh celých čísel v číselném tělese, jeho integrální báze, diskriminant souboru čísel, diskriminant tělesa.
Věta Nechť K je těleso takové, že ℚ⊂K⊂ℂ a [K:ℚ]<∞. Potom existuje α∈𝔸 takové, že K=ℚ(α).
Definice Nechť α∈𝔸,K∈ℚ(α). Potom OK≔K∩𝔹 je okruh celých čísel v K.
Příklad Oℚ=ℤ.
Věta Nechť K=ℚ(α) pro α∈𝔸. Potom
OK={β∈K|Pβ(x)∈ℤ[x]},
kde Pβ značí tělesový polynom v K.
Definice Diskriminant souboru (β1,…,βn)∈Kn je
Δ(β1,…,βn)≔detM(β1,…,βn),
kde
M(β1,…,βn)i,j≔Tr(βiβj).
Věta Nechť β1,…,βn∈K. Potom Δ(β1,…,βn)=(detN(β1,…,βn))2, kde
(N(β1,…,βn))j,k=σk(βj).
Příklad Nechť α1,…,αn jsou sdružená čísla k α. Potom
Δ(1,α,…,αn−1)=det2(11⋯1α1α2⋯αn⋮⋮⋱⋮α1n−1α2n−1⋯αnn−1)=∏1≤j<k≤n(αj−αk)2≠0.
Věta Je-li f minimální polynom pro α, potom
Δ(1,α,…,αn−1)=(−1)(n2)⋅N(f′(α)),
kde N značí normu.
Lemma Nechť pro β1,…,βn,γ1,…,γn∈K existuje B∈ℚn×n taková, že
γi=∑j=1nBi,j⋅βj.
Potom Δ(γ1,…,γn)=det2B⋅Δ(β1,…,βn).
Věta Soubor (β1,…,βn)∈Kn tvoří bázi K nad ℚ, právě když Δ(β1,…,β1)≠0.
Definice Soubor (β1,…,βn)∈OKn je integrální báze OK, pokud pro všechna β∈OK existují jednoznačné c1,…,cn∈ℤ takové, že β=∑i=1nci⋅βi.
Věta V každém algebraickém číselném tělese existuje integrální báze. Tato báze je β1,…,βn∈OK takové, že Δ(β1,…,βn)≠0 a |Δ(β1,…,βn)| je minimální.
Věta Nechť (β1,…,βn) je integrální báze OK. Potom každá γ1,…,γn tvoří integrální bázi OK, právě když Δ(β1,…,βn)=Δ(γ1,…,γn).
Definice Diskriminant číselného tělesa K je diskriminant každé integrální báze OK. Značíme ΔK.
Důsledek Mají-li γ1,…,γn∈OK čtvercuprostý diskriminant, potom tvoří integrální bázi OK.
Poznámka Opačná implikace neplatí:
7. Dělitelnost v oborech integrity, jednotky (Dirichletova věta), ireducibilní prvek, prvočíslo, okruhy jednoznačné faktorizace, okruhy hlavních ideálů, eukleidovské okruhy.
Definice Nechť R je obor integrity.
  • Prvek a∈R dělí prvek b∈R, pokud existuje c∈R takové, že b=a⋅c. Značíme a|b.
  • Prvek a∈R je asociovaný s prvkem b∈R, pokud a⋅R=b⋅R nebo ekvivalentně a|b∧b|a. Značíme a∼b.
  • Prvek u∈R je jednotka, pokud u∼1. Značíme u∈U(R).
Poznámka a∼b, právě když existuje u∈U(R) taková, že b=u⋅a.
Věta Nechť β∈OK. Potom β∈U(OK), právě když N(β)=±1.
Věta Dirichletova o jednotkách Nechť K=ℚ(α), kde minimální polynom pro α∈𝔸 má r1 reálných a r2 párů komplexních kořenů. Označme t≔r1+r2−1 a l největší přirozené číslo takové, že exp2π𝕚l∈K. Potom existují fundamentální jednotky η1,…,ηt takové, že
U(OK)={ξk∏i=1tηiji|k,j1,…,jt∈ℤ}.
8. Kvadratická tělesa a jejich okruhy celých čísel, integrální báze, jednotky v reálných a imaginárních kvadratických tělesech, hledání fundamentální jednotky, jednoznačnost faktorizace, Gaussova celá čísla.
Definice Nechť m∈ℤ∖{1} je čtvercuprosté. Potom
  • je-li m>0, ℚ(m) je reálné kvadratické těleso,
  • je-li m<0, ℚ(m) je imaginární kvadratické těleso.
Poznámka V kvadratickém tělese pro a,b∈ℤ platí
σ(a+bm)=a−bm,
Pa+bm(x)=(x−(a+m))(x−(a−m))=x2−2ax+a2−mb2,
Tr(a+bm)=2a,
N(a+bm)=a2−mb2,
ℚ(a+bm)∼ℤ2.
Věta Nechť 1<m∈ℕ je čtvercuprosté. Potom integrální báze Oℚ(m) je
{(1,m)m≡2,3(mod4),(1,1+m2)m≡1(mod4).
Poznámka Nechť m∈ℤ je čtvercuprosté a K≔ℚ(m). Pro mmod4∈{2,3} je
OK={a+bm|a,b∈ℤ},N(a+bm)=a2−m⋅b2.
Speciálně pro m>0 to vede na řešení Pellovy rovnice. Pro m=−1 máme Gaussova celá čísla. Pro m<−1 máme pouze U(OK)={±1}. Pro mmod4=1 je
OK={c+dm2|c,d∈ℤ},N(c+dm2)=c2−m⋅d24.
Je-li m<0, potom pro m=−3 máme Eisensteinova celá čísla s množinou jednotek {exp(π𝕚3k)|k=0,…,5}, jinak U(OK)={±1}. Pro m>0 opět dostáváme Pellovu rovnici.
Věta Nechť m∈ℤ je čtvercuprosté a K≔ℚ(m). Potom existuje fundamentální jednotka η∈OK,η>1 taková, že U(OK)={±ηj|j∈ℤ}.
Poznámka Jelikož Pellova rovnice má netriviální řešení, jistě existuje nějaké ξ∈U(OK),ξ>1. Nechť ε∈U(OK). Potom existují c,d∈ℤ splňující c2−m⋅d2=4 a
ε=c+d⋅m2,1ε=±c−d⋅m2≕±ε′.
Potom c=ε±ε′. Je-li 1<ε≤ξ, potom 0<c<ξ+1. To dává jen konečně mnoho možností na c. Fundamentální jednotka je
η≔min{ν∈U(OK)|1<ν≤ξ}.
9. Cyklotomické polynomy, cyklotomická tělesa, integrální báze jejich okruhu celých čísel, konstruovatelnost pomocí pravítka a kružítka.
Definice Nechť n∈ℕ. Potom grupa n-tých kořenů jedničky je
Cn≔{exp2π𝕚nj|j=0,…,n−1}.
Poznámka Nechť k⟂n a ξ≔exp2π𝕚n. Potom
Cn={(ξk)j|j=0,…,n−1}.
Definice Nechť n∈ℕ,ξ≔exp2π𝕚n. Potom n-tý cyklotomický polynom je
Φn(x)≔∏k=1k⟂nn(x−ξk).
Pozorování Nechť n∈ℕ. Potom
xn−1=∏d|nΦd(x).
Věta Nechť n∈ℕ. Potom Φn∈ℤ[x], Φn(0)=±1 a Φn je ireducibilní nad ℚ.
Důsledek Nechť n∈ℕ,ξ≔exp2π𝕚n. Potom ξ∈𝔸 stupně φ(n) s minimálním polynomem Φn.
10. Číselné soustavy s neceločíselnou bází β, Pisotova a Salemova čísla, periodické β-rozvoje.

Jazyky a automaty

1. Konečné automaty. Definice konečného automatu a třídy RecΣ*. Uzávěrové vlastnosti třídy RecΣ*. Užitečný (trim) automat a jeho využití.
2. Rozhodování regularity jazyka. Uzavřenost třídy RecΣ* na levý kvocient a (základní) nutná podmínka rozeznatelnosti jazyka. Věty o vkládání pro rozeznávané jazyky – znění a hierarchie. Věta Ehrenfeucht–Parikh–Rosenberg.
3. Kleenova věta. Definice tříd RecΣ* a RegΣ*. Kleenova věta. Princip důkazu Kleenovy věty s důrazem na směr reg. výraz → automat.
4. Deterministické konečné automaty. Definice deterministického konečného automatu (DKA). Algoritmus determinizace. Použití DKA.
5. Minimální automat. Myhillovy–Nerodeovy relace pro jazyk L a Nerodeova ekvivalence ≡L. Myhillova–Nerodeova věta. Mooreův algoritmus konstrukce minimálního automatu.
6. Bezkontextové gramatiky. Definice bezkontextové gramatiky (BKG), jazyk generovaný BKG, nejednoznačnost BKG. Speciální typy BKG: gramatika bez zbytečných symbolů, bez ε-pravidel a bez jednotkových pravidel. Chomského normální forma (CNF) a převod BKG do CNF.
7. Zásobníkové automaty. Definice zásobníkového automatu (ZA). Jazyk přijímaný ZA – dva způsoby akceptování slova a jejich ekvivalence. Princip důkazu ekvivalence bezkontextových jazyků a jazyků rozeznávaných ZA.
8. Vlastnosti bezkontextových jazyků. Věta o vkládání pro bezkontextové jazyky (BKJ) – znění, princip důkazu a použití. Uzávěrové vlastnosti třídy BKJ. Deterministické ZA.
9. Turingovy stroje. Definice Turingova stroje (TS), jazyk přijímaný TS, třídy ℒRS a ℒREK. TS vyčíslující (verbální a aritmetické) funkce, Turingova téze. Modifikace TS: více hlav, více pásek, nedeterminismus.
10. Nerozhodnutelnost. Definice (ne)rozhodnutelného problému. Uzávěrové vlastnosti tříd ℒRS a ℒREK. Jazyky LD a LU a jejich klasifikace.
11. Nerozhodnutelnost problémů týkajících se Turingových strojů. Redukce v teorii nerozhodnutelnosti – definice a použití. Jazyky LNE a LE a jejich klasifikace. Riceova věta a její důsledky.
12. Postův korespondenční problém. Definice Postova korespondenčního problému (PCP), idea důkazu nerozhodnutelnosti PCP. Jazyk LA pro seznam slov A (tzv. list language). Použití PCP na důkazy nerozhodnutelnosti problémů týkajících se bezkontextových jazyků.
13. Algoritmické problémy v teorii formálních jazyků. Prázdnost, konečnost a nekonečnost jazyka přijímaného konečným automatem. Prázdnost, konečnost a nekonečnost bezkontextového jazyka. Prázdnost a neprázdnost jazyka přijímaného Turingovým strojem.