TIN
–
–
–
–
–
–
–
–
–
–
prohledávání grafů
– DFS – Depth first search
– BFS – Breadth first search
Souvislým grafem nazýváme takový neorientovaný graf, mezi jehož libovolnými dvěmi uzly existuje sled.
– DFS, BFS
Komponentou grafu nazýváme každý jeho maximální souvislý podgraf.
– DFS, BFS
Topologickým uspořádáním se rozumí takové úplné uspořádání uzlů, v němž je pro každou hranu (u, v) uzel u
před uzlem v. Takové uspořádání lze zavést pouze pro acyklické grafy.
Orientovaný graf G nazýváme silně souvislým, jestliže pro libovolnou dvojici uzlů u, v existuje spojení z uzlu
u do uzlu v a spojení z uzlu v do uzlu u.
Silnou komponentou orientovaného grafu nazýváme každý jeho maximální silně souvislý podgraf.
Kostrou grafu G je každý jeho faktor (hranový podgraf), který je stromem (tedy každý jeho souvislý faktor,
který je bez kružnic).
Minimální kostra grafu (hrany s co nejmenším ohodnocením)
– Borůvkův-Kruskalův algoritmus
– Pro přidávání vybíráme takovou hranu, která má ze všech možných hran spojujících dva různé
podstromy (tj. nevytvoří kružnici) ve vytvářené kostře tu nejměnší váhu
– Jarníkův-Primův algoritmus
– Hrany vybrané do množiny A tvoří stále jediný podstrom, k němuž se připojí přidanou hranou vždy
pouze jeden nový uzel. První uzel tohoto podstromu je možné zvolit libovolně. Dosud nepřipojené
uzly jsou uloženy v prioritní frontě podle jejich nejkratší možné vzdálenosti k prozatím vytvořenému
podstromu.
– Složitost závisí na implementaci prioritní fronty
Reprezentace
– Matice incidence - velikost U*H
– Matice sousednosti - velikost U*U
– Spojová reprezentace - 2 spojové seznamy, jeden pro uzly a druhý pro hrany. Ze spojového seznamu pro
uzly vede ukazatel do podseznamu jeho hran v seznamu hran. (jako v PAR, eulerova cesta)
– Binární halda - v podstatě binární strom s pár vlastnostmi a operacemi navíc
– Fibonnaciho halda
– Může se skládat s více oddělených stromů, uzel nemusí mít pevný počet potomků
– Operace řeskupování stromů se odkládají dokud to není nevyhnutelné
– Fibonacciho haldu tvoří skupina stromů vyhovující lokální podmínce na uspořádání haldy, která
vyžaduje, aby pro každý uzel stromu platilo, že prvek, který reprezentuje, je menší než prvek
reprezentovaný jeho potomky.
Nalezení nejkratších cest z jednohu uzlu
– Dijkstrův algoritmus
DIJKSTRA(G, s, w) // Graf, Startoivací uzel, Váha hrany
INIT-PATHS(G, s) // d[s]=0, ostatni nekonecno
S := prázdná množina
INIT-QUEUE(Q)
for každý uzel u ∈ U do
ENQUEUE(Q, u)
while not EMPTY(Q) do
u := EXTRACT-MIN(Q)
S := S ∪ {u}
for každý uzel v ∈ Adj(u) do
RELAX(u, v, w)
– Bellman-Fordův algoritmus
– Oproti Dijkstrově algoritmu se systematicky relaxují všechny hrany, ne jenom hrany vycházející z
jednoho uzlu. Bellman-Fordův algoritmus navíc dokáže detekovat výskyt cyklů se zápornou délkou
na cestě z výchozího uzlu s do nějakého uzlu u.
–
–
BELLMAN-FORD(G, s, w)
INIT-PATHS(G, s)
for i := 1 to |U| - 1 do
for každou hranu (u, v) ∈ H do
RELAX(u, v, w)
for každou hranu (u, v) ∈ H do
if d[v] > d[u] + w(u, v) then
return false
return true
Nejkratší cesty pro acyklický graf
– U acyklického grafu nehrozí výskyt cyklu záporné délky, takže je možné algoritmus značně zjednodušit.
Využívá se při něm topologické seřazení uzlů.
DAG-PATHS(G, s, w)
Topologické uspořádání uzlů grafu G
INIT-PATHS(G, s)
for každý uzel u v pořadí jeho topologického uspořádání do
for každé v ∈ Adj(u) do
RELAX(u, v, w)
Nejkratší cesty ze všech uzlů
– Opakované použití algoritmů pro nalezení nejkratších cest z jednohu uzlu
– Metoda prodlužování cest
– Postupně určujeme pro každý uzel všechny nejkratší cesty složené z maximálně dvou hran, pak tří,
čtyř, atd. Rozšíření algoritmu tak, aby kromě délek nejkratších cest vyrobil i příslušnou matici
předchůdců, je snadné. Algoritmus je podobný násobení matic, stačí za x dosazovat 0, místo minima
sčítat a místo sčítání násobit.
PRODLUŽ-CESTY(D1, W, D2)
for i := 1 to n do
for j := 1 to n do
x := ∞
for k := 1 to n do
x := min(x, d1(i,k) + w(k,j))
d2(i,j) := x
NEJKRATŠÍ-CESTY(W)
D(1) := W
for m := 2 to n - 1 do
PRODLUŽ-CESTY(D(m - 1), W, D(m))
return D(n – 1)
– Floydův-Warshallův algoritmus
– Opět dochází k postupnému zpřesňování odhadu délek nejkratších cest. Tentokrát se postupuje tak, že
se postupně zvětšuje množina přípustných vnitřních uzlů cesty. Opět zvažujeme pouze grafy bez
cyklů záporné délky.
FLOYD-WARSHALL(W)
D(0) := W
for k := 1 to n do
for i := 1 to n do
for j := 1 to n do
dij(k) := min(dij(k - 1), dik(k - 1) + dkj(k - 1))
return D(n)
– Johnsonův algoritmus
– Přehodnocení hran: Přidáme k grafu nový uzel s a z něj orientované hrany do všech uzlů původního
grafu. Všechny nově přidané hrany jsou ohodnoceny nulou. Pokud původní graf (a tedy ani
rozšířený) neobsahoval cykly se zápornou w-délkou, spočítáme pro každý uzel hodnotu h(u) = d(s,
u). Nové ohodnocení hran získáme podle vzorce x(u, v) = w(u, v) + h(u) - h(v). Platí přitom, že x(u,
v) ≥ 0.
JOHNSON(G)
Rozšíření grafu G na graf G2 (viz. přehodnocení hran)
if not BELLMAN-FORD(G2, w, s) then
write "Graf obsahuje cyklus záporné délky"
else
for každý uzel u ∈ U2 do
h(u) := d(s, u)
for každou hranu (u, v) ∈ H2 do
x(u, v) := w(u, v) + h(u) - h(v)
for každý uzel u ∈ U do
DIJKSTRA(G, x, u)
for každý uzel v ∈ U do
du,v := e(u, v) + h(v) - h(u)
–
–
–
return D
Algebraické souvislosti
– Floydův-Warshallův algoritmus lze využít také k výpočtu reflexivně-tranzitivního uzávěru grafu. Po
vhodné úpravě centrální dvojoperace může tento algoritmus poskytnout řešení i dalších grafových
úloh, v nichž je třeba určit nějaké hodnoty závislé na orientovaných spojeních v grafu, přičemž
hodnota příslušná každému spojení se odvozuje od hodnocení jeho hran.
Hladové algoritmy
– Vlastnost hladového výběru: ke globálně optimálnímu řešení lze dospět prostřednictvím lokálně
optimálních (hladových) výběrů. Podmínka, podle níž se lokální výběr provádí, by neměla záviset na
řešení podproblémů, ale pouze na okamžitém stavu řešené úlohy. Princip hladového výběru spočívá v
tom, že nejprve provedeme výběr a potom řešíme vzniklý podproblém - hladové algoritmy postupují
shora dolů (postupným prováděním lokálně optimálních výběrů se každá instance problému redukuje
na instanci menší).
– Dijkstrův algoritmus, Jarníkův-Primův algoritmus
Algoritmy dynamického programování
– Začínáme řešením dílčích podproblémů a z nich budujeme řešení většího problému
– Konstrukce optimálních binárních vyhedávacích stromů, hledání nejdelší společné podposloupnosti,
násobení posloupnosti matic
Výpočetní modely
– Abecedou nazýváme libovolnou konečnou množinu A, jejíž prvky nazýváme symboly.
– Řetěz (slovo) nad abecedou A je konečná posloupnost symbolů této abecedy včetně prázdné posloupnosti, tedy
uspořádaná n-tice symbolů pro n ≥ 0.
– Prázdný řetěz nad abecedou A označujeme ε (ε ∉ A). Množinu všech řetězů na abecedou A označujeme A*.
Délkou řetězu w = a1a2…an ∈ A* nazýváme počet jeho symbolů n a zapisujeme |w| = n.
– Libovolnou množinu řetězů nad abecedou A, tedy podmnožinu množiny A*, nazýváme jazykem nad abecedou
A. Jazyk lze popsat jedním z následujících způsobů:
– výčtem jednotlivých řetězů
– pomocí gramatiky
– pomocí automatu přijímajícího slova daného jazyka
– jiným zápisem (např. regulární výraz)
– Gramatikou nazýváme čtveřici G = (A, N, P, S), kde
– A je tzv. terminální abeceda
– N je tzv. neterminální abeceda
– P ⊆ ( (A ∪ N)*N(A ∪ N)*) × (A ∪ N)* je tzv. množina přepisovacích pravidel zapsaných ve tvaru α →
β, kde α ∈ ( (A ∪ N)*N(A ∪ N)*) a β ∈ (A ∪ N)*
– S ∈ N je tzv. počáteční symbol
– Chomského klasifikace gramatik:
– Gramatika typu 0 (neomezená) - pravidla musí být tvaru xXy → xβy, kde x, y ∈ (A ∪ N)*, X ∈ N, β ∈
(A ∪ N)* - rozpoznatelné Turingovým strojem
– Gramatika typu 1 (kontextová) - pravidla musí být tvaru xXy → xβy, kde x, y ∈ (A ∪ N)*, X ∈ N, β ∈
(A ∪ N)+ - rozpoznatelné lineárně ohraničeným Turingovým strojem
– Gramatika typu 2 (bezkontextová) - pravidla musí být tvaru X → β, kde X ∈ N, β ∈ (A ∪ N)* zásobníkovým automatem.
– Gramatika typu 3 (regulární) - pravidla musí být tvaru X → a nebo X → aY, kde a ∈ A, X, Y ∈ N
(výjimkou je pravidlo S → ε v případě, že S se nevyskytuje na pravé straně žádného pravidla v P) -
–
–
–
–
konečným automatem
Deterministický konečný automat (FSA) je pětice M = (Q, A, δ, s F), kde
– Q je konečná množina stavů automatu
– A je (konečná) abeceda
– δ je přechodové zobrazení automatu definované takto: δ: Q × A → Q
– s ∈ Q je počáteční stav
– F ⊆ Q je množina koncových stavů
Nedeterministický konečný automat (NFSA) je pětice M = (Q, A, Δ, s, F), kde
– Q je konečná množina stavů automatu
– A je (konečná) abeceda
– Δ je přechodové zobrazení automatu definované takto: Δ: (Q × (A ∪ {ε})) → 2Q
– s ∈ Q je počáteční stav
– F ⊆ Q je množina koncových stavů
Turinguv stroj
– Q je konečná množina stavů
– A je abeceda obsahující mj. prázdný symbol (mezeru) a symbol konce pásky, ale neobsahující symboly ←
a→
– s ∈ Q je počáteční stav
– F ⊆ Q je množina koncových stavů
– δ: (Q - F) × A → Q × (A ∪ {←, →}) je přechodové zobrazení
Univerzální Turingův stroj
– Tři pásky
– Na první pásce je vstup, tedy popis simulovaného TS a za ním zakódovaný vstupní řetězec
– Univerzální TS čte druhou pásku a hledá na ní čtveřici, jejíž první složka se shoduje s obsahem třetí
pásky a druhá složka se shoduje s právě čteným symbolem na první pásce. Pokud tuto čtveřici
nalezne, změní kód stavu na třetí pásce podle třetí složky této čtveřice a provede nad první páskou
akci odpovídající kódu ve čtvrté složce čtveřice.
– Turingův stroj je podobný pevně naprogramovanému počítači - jeho program je dán jeho strukturou.
Univerzální Turingův stroj je však schopný simulovat činnost libovolného jiného Turingova stroje.
DML
Predikátová logika
– Logické symboly, tj.
Spočetná množina individuálních proměnných (x, y, x1, x2, …)
Výrokové logické spojky ¬, ∧, ∨, ⇒, ⇔
Obecný kvantifikátor ∀ a existenční kvantifikátor ∃
– Speciální symboly, tj.
Množina P predikátových symbolů (nesmí být prázdná)
Množina K konstantních symbolů (může být prázdná)
Množina F funkčních symbolů (může být prázdná)
– Každá atomická formule je formule
– Jsou-li φ a ψ dvě formule, pak (¬φ), (φ ∧ ψ), (φ ∨ ψ), (φ ⇒ ψ), (φ ⇔ ψ) jsou opět formule
– Je-li φ formule a x proměnná, pak (∀x φ) a (∃x φ) jsou opět formule
– Nic, co nevzniklo pomocí konečně mnoha použití předchozích pravidel, není formule
– Sémantický důsledek
– Řekneme, že množina sentencí S je splnitelná, jestliže existuje interpretace, která je modelem každé
sentence φ z množiny S. Taková interpretace se nazývá model množiny S. Nemá-li množina sentencí
S model, říkáme, že je nesplnitelná.
– Řekneme, že formule φ je sémantickým, též konsekventem nebo tautologickým důsledkem množiny
formulí S, jestliže φ je pravdivá v každém ohodnocení u, v nìmž je pravdivá S.
– Sentence φ se nazývá tautologie, jestliže je pravdivá v každé interpretaci. Sentence se nazývá kontradikce,
jstliže je nepravdivá v každé interpretaci. Sentence se nazývá splnitelná, jestliže je pravdivá v aspoň jedné
interpretaci.
Matematická indukce
–
Matematická indukce: Máme dánu vlastnost V přirozených čísel. Jsou-li splněny následující podmínky, pak
vlastnost V mají všechna přirozená čísla n ≥ n0
– Vlastnost V má přirozené číslo n0
– Kdykoliv má vlastnost V přirozené číslo k ≥ n0, pak má vlastnost V také přirozené číslo k + 1
Strukturní indukce
– Množina zadaná induktivně: V tomto případě jsou zadána pravidla dvojího typu:
– Základní pravidlo - výčtem jsou dány základní prvky patřící do množiny M
– Induktivní pravidla, která říkají, jak z již zkonstruovaných prvků množiny M vytvořit nové prvky této
množiny.
– Množinu M tvoří všechny prvky, které vznikly konečným počtem použití základního pravidla a
induktivních pravidel
–
AVT
–
–
–
–
–
–
–
–
–
–
–
–
–
–
–
Dvojice (S, •), kde S je nějaká množina a • je binární operace na S, se nazývá grupoid. Množina S je
vzhledem k operaci • uzavřená, tj. výsledkem operace provedené na libovolných prvcích množiny S je prvek
množiny S.
Máme dánu binární operaci • na množině S. Jestliže pro každý x, y, z ∈ S platí asociativní zákon x • (y • z) =
(x • y) • z, nazývá se množina S s binární operací • pologrupa. Pologrupa je každý grupoid, který splňuje
asociativní zákon.
Máme dán grupoid (S, •). Prvek e ∈ S se nazývá jednotkovým (též neutrálním) prvkem právě tehdy, když e • x
= x = x • e pro každé x ∈ S. Např. množina celých čísel a operace sčítání má e=0, pro násobení je e=1.
Pologrupa se nazývá monoid, má-li jednotkový prvek. Monoid obvykle značíme (S, •, e), kde e je jednotkový
prvek pologrupy (S, •).
Mějme dán monoid (S, •, e). Řekneme, že prvek a ∈ S je invertibilní, jestliže existuje prvek y ∈ S takový, že a
• y = e = y • a.
Je dán monoid (S, •, e) a invertibilní prvek a ∈ S. Pak prvek y splňující předchozí definici je určen
jednoznačně a nazýváme jej inverzní prvek k prvku a a značíme jej a-1.
Monoid (S, •, e) se nazývá grupa, jestliže každý prvek je invertibilní, tj. ke každému prvku a ∈ S existuje
inverzní prvek a-1.
Pologrupa, monoid, grupa se nazývá komutativní, jestliže platí tzv. komutativní zákon, tj. pro každé dva
pravky x, y platí x • y = y • x. Komutativní grupa se nazývá Abelova grupa.
Řád grupy (G, ·, e) je počet prvků množiny G.
Řád prvku a je nejmenší kladné přirozené číslo r(a) takové, že a^(r(a)) = e.
Máme dánu grupu (G, *, 1) . Řekneme, že podmnožina H spolu s operací * tvoří podgrupu grupy (G, *, 1)
právě tehdy, když H je uzavřená na operaci *, obsahuje jednotkový prvek a je uzavřena na tvorbu inverzního
prvku.
Řád libovolné podgrupy G dělí řád grupy G.
Podgrupa generovaná prvkem a, značíme <a>, je množina {a^1, a^2, ..., a^(r(a))=1 } . Přitom r(a) je řád této
grupy. Prvek a se nazývá generátorem této grupy
V konečné grupě G o n prvcích dělí řád každého prvku číslo n. Navíc pro každý prvek a z G platí, že a^n=1.
Každá grupa která má generátor se nazývá cyklická grupa. Konečná grupa G o n prvcích je cyklická právě
tehdy, když v ní existuje prvek s řádem n.
Eulerova funkce
– Je dáno přirozené číslo n. Pak hodnota Eulerovy funkce φ(n) je rovna počtu všech přirozených čísel i, 0 ≤ i <
n, která jsou nesoudělná s číslem n.
– Vlastnosti Eulerovy funkce
– Je-li p prvočíslo, pak φ(p) = p – 1
– Je-li p prvočíslo, pak φ(pk) = p^k - p^(k – 1)
– Jestliže n a m jsou nesoudělná přirozená čísla, pak φ(n · m) = φ(n) · φ(m)
Euler-Fermatova věta
– Je dáno přirozené číslo n > 1. Pak pro každé celé číslo a nesoudělné s n platí a^(φ(n)) ≡ 1 (mod n).
– Je dáno prvočíslo p > 1. Pak pro každé celé číslo a nesoudělné s p platí a^(p - 1) ≡ 1 (mod p). Jedná se o EulerFermatovu větu pro prvočíselná p, tedy φ(p) = p – 1.
Aritmetika (mod p)
– (Zn , +, [0] ) je komutativní grupa.
– (Zn , ·, [1] ) je komutativní monoid, který nikdy netvoří grupu, protože prvek [0] není invertibilní.
Čínská věta o zbytcích
Princip RSA v kostce:
– Zvolí se dvě různá podobně velká prvočísla p, q
– Vypočítáme n = pq, to je nyní modul pro veřejný i tajný klíč
– Vypočítá se φ(pq) = (p − 1)(q − 1), kde φ je Eulerova funkce (všimněme si - výpočet je jednoduchý,
protože známe p,q a víme že jde o prvočísla)
– Zvolí se číslo e menší než φ(pq), tak že e a φ(pq) jsou nesoudělná. e je veřejný klíč (k šifrování)
– Vypočítá se d (za pomoci modulární aritmetiky) pro které platí že de=1 (mod φ(pq)). d je soukromý
(tajný) klíč.
– Šifrování probíhá tak, že se přenášená zpráva (číslo) umocní na e (mod n) a odešle jakožto zpráva c.
Dešifrování se provede tak, že zprávu c umocníme na d (mod n) a získáme dešifrovanou zprávu f. Síla
šifry spočívá v tom, že je velmi obtížné spočítat z (n,e) dešifrovací klíč (d). K tomu je potřeba znát φ(n).
To lze ale pouze pokud známe rozklad n na prvočísla, což je výpočetně náročný problém (exponenciální
složitost).
Těleso je pětice (F, +, •, 0, 1), kde F je množina s alespoň dvěma prvky 0 a 1 a dále platí:
– (F, +, 0) je Abelova grupa
– (F \ {0}, •, 1) je grupa
– distributivní zákon:
– a • (b + c) = a • b + a • c
– (a + b) • c = a • c + b • c
– Těleso zbytkových tříd je pětice (Zp, +, •, 0, 1), kde p je prvočíslo.
Polynomy nad konečnými tělesy Zp
– Polynomem na Zp rozumíme každý výraz a0 + a1x + a2x2 + … + anxn, kde ai ∈ Zp. Symbol x nazýváme
proměnná. Množinu všech polynomů nad Zp značíme Zp[x].
– Ireducibilita
– Polynom f(x) ze Zp[x] se nazývá ireducibilní (nad Zp), jestliže se polynom f(x) nedá napsat jako součin
dvou polynomů menšího stupně než st(f).
– Polynom stupně 2 nebo 3 je ireducibilní právě tehdy, když nemá kořen.
Okruh je Trojice (A, +, ·), jestliže
– (A, +) je komutativní grupa s neutrálním prvkem 0
– (A, ·) je pologrupa
– platí distributivní zákony
Galoisovo těleso
– Pro každé prvočíslo p a každé přirozené číslo k ≥ 1 existuje těleso o p^k prvcích. Toto těleso je až na
isomorfismus určeno jednoznačně a nazývá se Galoisovo těleso GF(p^k)
Eukleidův algoritmus pro polynomy nad Zp
- hledaní gcd dvou polynomů
–
analogicky pro polynomy
–
Binární relací R z množiny A do množiny B nazýváme libovolnou podmnožinu kartézského součinu A × B.
Skutečnost, že uspořádaná dvojice (a, b) je v relaci R, zapisujeme (a, b) ∈ R (nebo také zkráceně aRb)
Inverzní relace
Pro relace R ⊆ A × B a S ⊆ B × C je složením relací R a S relace R • S ⊆ A × C taková, že a(R • S)c ⇔ ∃b ∈
B: aRb ∧ bSc
reflexivní, pokud aRa pro všechna a ∈ A
symetrická, pokud aRb ⇒ bRa
tranzitivní, pokud aRb ∧ bRc ⇒ aRc
antisymetrická, pokud aRb ∧ bRa ⇒ a = b nebo aRb ∧ a ≠ b ⇒ ¬bRa
asymetrická, pokud aRb ⇒ ¬bRa
ireflexivní, pokud ¬aRa pro všechna a ∈ A
Relace
–
–
–
–
–
–
–
–
–
–
Relace, která je reflexivní, symetrická a tranzitivní, nazýváme ekvivalencí. Je-li R ekvivalence na množině A,
potom pro každý prvek a ∈ A nazýváme třídou prvku a v ekvivalenci R množinu [a]R = {x ∈ A: xRa}.
Binární relaci R na množině A, která je reflexivní, antisymetrická a tranzitivní, nazýváme (částečným)
uspořádáním množiny A. Dvojici (A, R) nazýváme uspořádanou množinou.
Svazy
–
–
–
–
–
Mějme uspořádanou množinu (A, R) a v ní nějakou podmnožinu X ⊆ A. Prvek c ∈ A nazveme supremem
množiny X, jestliže platí:
– aRc pro každé a ∈ X (tj. c je horní mez množiny X)
– jestliže také aRd pro každé a ∈ X, pak nutně cRd (tj. c je nejmenší horní mez množiny X)
analogicky infimum
Svaz je uspořádaná množina (A, R), kde pro každé a, b ∈ A existuje sup({a, b}) a inf({a, b}).
a pokrývá b, pokud a ≠ b, a ≤ c ≤ b → a = c ∨ b=c. Česky, pokud A pokrývá B, tak potom neexistuje žádné C
Svaz (A,∧,∨) se nazývá distributivní, platí-li:
– 1. a,b,c A : a ∧ (b ∨ c) = (a ∧ b) ∨ (a ∧ c)
– 2. a,b,c A : a ∨ (b ∧ c) = (a ∨ b) ∧ (a ∨ c)
– aby mohl být svaz distributivní, musí být porovnatelné každé dva prvky
Algebra
–
–
–
–
–
–
–
Univerzální algebra typu Δ je množina A spolu s operacemi, jejichž arity (unární, binární) jsou předepsány
právě typem Δ. Množinu A nazýváme nosnou množinou algebry. Rovnice, které algebra splňuje, nazýváme
rovnice E. Příkladem univerzálních algeber (různých typů) jsou pologrupy, grupy, monoidy, svazy, okruhy
Podalgebra algebry s nosnou množinou A je podmnožina B ⊆ A, která je uzavřena na všechny operace dané
algebry.
Homomorfismus algebry AL1 do algebry AL2 je zobrazení f: A → B, které respektuje všechny operace.
– Zachovává binární operaci
– Zachováná unární operaci
– Zachovává nulární operaci (existence jednotkového prvku) f(eA) = eB.
Homomorfismus f, který je bijektivním zobrazením, nazveme isomorfismus
Bijektivní zobrazení je zobrazení, které je zároveň prosté (každému prvku přiřadí právě jeden prvek) i na
(zobrazí na celou cílovou množinu).
Rovnice, které algebra splňuje, nazýváme rovnice E
Algebra AL je volná mezi všemi algebrami typu Δ splňujícími rovnice E, jestliže každé zobrazení generátorů
algebry AL do libovolné algebry AL' (rovněž typu Δ splňující rovnice E) lze jednoznačně rozšířit na
homomorfismus algeber typu Δ.
– (Z, +) je volná mezi komutativními grupami
– (Zn, +) není volná mezi komutativními grupami
– Volné jsou ty algebry, které splňují jen nutné rovnice E a nic navíc
F2P
Fourierova transformace
–
Oscilátor
–
–
spojitá funkce lze složit spojením nekonečného množství sinusovek a cosinusovek
Oscilátor je systém, ve kterém se vzájemně přeměňuje jedna forma energie v jinou a zpět
Harmonický oscilátor je oscilátor, kde platí:
– průběh potenciální energie je parabolický: Wp (x) = 1/2 * kx^2
– síla je úměrná výchylce a má opačný směr: F = −kx
– kmity mají tvar x(t) = a cos ωt + b sin ωt
– Tlumené oscilace:
– a=zrychlení=druha derivace x
– m*a = −kx − αx
– x(t) = A * e^(−δt) cos(ωt + ϕ)
– δ-koeficient útlumu
– Složení dvou kmitů ve shodném směru:
Nucené (vynucené) kmitání
– takové kmitání, které je ovlivňováno vnější silou (budící síla), která způsobuje změnu vlastních kmitů a
způsobuje, že systém kmitá s jiným kmitočtem.
– Rezonance
– vzniké při nuceném kmitání
Vlnová rovnice
Vlnoplocha = plocha konstantní fáze
Fázová rychlost = rychlost přemísťování vlnoplochy
Paprsek = kolmice na vlnoplochu
Úhlová frekvence = změna fáze s časem
Vlnový vektor = změna fáze s prostorem: k = ( ∂ϕ/∂x , ∂ϕ/∂y , ∂ϕ/∂z ) =ϕ=∂ϕ/∂x
Vlnová funkce: ψ(t, x) = A(t, x)e^(ıϕ(t,x))
–
Fázová rychlost
– Fázová rychlost je rychlost, kterou se přemisťuje fáze vlnění (rychlost přemisťování bodů se stejnou fází)
– Uvedený vztah lze také vyjádřit pomocí úhlové rychlosti ω a vlnového vektoru k jako
– c=ω / k
– může být vyšší než rychlost světla
Grupová rychlost
– Grupová rychlost ve fyzice je rychlost přenosu energie vlněním
– nemůže být vyšší než rychlost světla
Jevy
– Dopplerův jev
– změna frekvence při pohybu
–
–
Huygensův princip
– každý bod vlnoplochy se stává zdrojem elementárního vlnění
– vysvětlení ohybu, interference na mřížce
Elektromagnetické pole
– Maxwellovy rovnice
–
–
–
–
E – elektrické pole
D – intenzita elektrického toku
B – intenzita magnetického toku
H – intenzita magnetického pole
-
–
–
–
–
–
Elektromagnetické vlny ve vakuu
– E, B, k jsou na sebe navzájem kolmé
Elektromagnetické vlny ve vodiči
Elektromagnetické vlny v optických vláknech
– Z řešení Maxwellových rovnic vyplývá, že optickými vlákny se může šířit pouze konečný počet kvazipaprsků dopadajících na rozhraní jádro-plášť pod určitými diskrétními úhly. Jsou to tzv. vidy
elektromagnetického pole (skutečná řešení vlnové rovnice pro danou vlnovodovou strukturu)
Elektromagnetické vlny v plazmatu:
– Elektromagnetické vlny se šíří v plazmatu jen na vysokých frekvencích. Při frekvencích nižších než je tzv.
plazmová frekvence elektronů, dochází k rozkmitání elektronů a útlumu vlny.
Vlny v anizotropním prostředí:
– Po provedení Fourierovy transformace zjistíme, že vektory D a E nemíří ve stejném směru. V lineárním
prostředí permitivita matice čísel závisí na volbě souřadnicového systému. V každém krystalu lze najít
souřadnicový systém, ve kterém je permitivita diagonální matice.
Světlo
Fázová rychlost určuje rychlost přemisťování fáze vlnění - neurčuje rychlost přenosu informace ani energie (tu
určuje grupová rychlost).
Optická vlákna
-typy
-vlastnosti
-utlumy
Interference na optické mřížce
Difrakce
– ohyb, huygensuv princip
Dopplerův jev
Lorentzova transformace
– generalizace Galileovy transformace o relativistické jevy
Numerické metody
– Funkce f(t, y) (někdy se nazývá stavová rovnice) může být obecně velmi komplikovaná, proto je nutné řešit
rovnici numericky. V takovém případě probíhá řešení v diskrétních časových krocích Δt: y(t + Δt) = y(t) +
D(t,y)Δt, kde D(t,y) je funkce (někdy též směrová funkce), která se snaží aproximovat y'(t) tak, aby y(t + Δt)
bylo co nejpřesnější.
– Rovnice mají tvar
–
– tedy derivace funkce a počáteční podmínky
Eulerova metoda je nejjednodušší metodou numerického řešení obyčejných diferenciálních rovnic s danými
počátečními podmínkami. Jedná se o lineární aproximaci Taylorova rozvoje.
Používá první dva členy taylorova rozvoje (offset (nultý řád) a lineární funkce(první řád))
Vycházím z počátečního řešení, kde zpočítám hodnotu derivace (tangenty) funkce ze zadání diferenciální
rovnice
– posunu se dál o krok a opakuji
– získám tím množinu bodů, ze které je možné zrekonstruovat aproximaci funkce
Taylorův polynom tedy aproximuje hodnoty funkce, která má v daném bodě derivaci, pomocí polynomu, jehož
koeficienty závisí na derivacích funkce v tomto bodě.
–
–
–
Nebo (pouze první dva stupně)
–
metoda Runge-Kutta
Monte Carlo metody
Monte Carlo je třída algoritmů pro simulaci systémů. Jde o stochastické metody používající pseudonáhodná čísla.
Typicky jsou využívány pro výpočet integrálů, zejména vícerozměrných, kde běžné metody nejsou efektivní. Metoda Monte
Carlo má široké využití od simulaci experimentů přes počítání určitých integrálů až třeba řešení diferenciálních rovnic.
PAA
–
řád složitosti
Rozhodovací problémy:
– Rozhodovací problém patří do třídy P, jestliže pro něj existuje program pro deterministický Turingův stroj,
který jej řeší v čase O(n^k), kde n je velikost instance a k je konečné číslo. P znamená polynomiální (takže
únosný).
– PSPACE (polynomiální množství paměti), EXPTIME (v čase O(2P(n)), kde P(n) je polynom ve velikosti
instance n)
– Rozhodovací problém patří do třídy NP, jestliže platí alespoň jedno z následujících tvrzení:
– pro něj existuje program pro nedeterministický Turingův stroj, který každou instanci I z ∏ANO problému
∏ řeší v čase O(n^k), kde n je délka vstupních dat a k konečné číslo
– pro každou instanci I z ∏ANO problému ∏ existuje konfigurace Y taková, že kontrola, zda je Y řešením,
patří do P (Y je certifikátem) - to znamená, že omezující podmínky lze vyhodnotit v polynomiálním čase
– co-NP („protějšek“ třídy NP, patří sem opačně formulované problémy - např. je zadaná formule nesplnitelná?)
Optimalizační problémy
– Optimalizační problém ∏ patří do třídy NPO, jestliže splňuje následující podmínky:
– výstup lze zapsat v polynomiálním čase
– omezující podmínky lze vyhodnotit v polynomiálním čase
– optimalizační kritérium lze vyhodnotit v polynomiálním čase
– Optimalizační problém ∏ patří do třídy PO, jestliže splňuje následující podmínky:
– patří do třídy NPO
– existuje program pro deterministický Turingův stroj, který každou instanci vyřeší v polynomiálním čase
Souvislost se stavovým prostorem
– V případě NP problémů je stavový prostor nadpolynomiálně velký. Mohou nastat dva případy:
– cesta k řešení ve stavovém prostoru je únosně dlouhá (lze ji projít - nikoliv najít! (neznáme algoritmus,
který by šel správnou cestou) - v polynomiálním čase) ⇒ NP
– cesta k řešení ve stavovém prostoru je neúnosně dlouhá ⇒ problém je složitější než NP
– V případě P problému (což je podmnožina NP) vždy víme, kudy se ubírat ⇒ cesta stavovým prostorem k
řešení je vždy únosně dlouhá a umíme ji najít v polynomiálním čase.
Polynomiální redukce
– Problém ∏ je X-těžký, jestliže se efektivní řešení (tj. v polynomiálním čase) všech problémů z třídy X (NP,
NPO, APX, …) dá zredukovat na efektivní řešení problému ∏ (tj. dá vyřešit řešením problému ∏).
– NP-těžký problém je takový problém, na který lze redukovat všechny problémy z NP pomocí Turingovy
redukce.
– Problém ∏ je X-úplný, jestliže je X-těžký a sám patří do X.
– Karpova redukce (polynomiální redukce): Rozhodovací problém ∏1 je Karp-redukovatelný na ∏2 (píšeme
∏1 ∝ ∏2), jestliže existuje polynomiální program pro (deterministický) Turingův stroj, který převede každou
instanci I1 problému ∏1 na instanci I2 problému ∏2 tak, že výstup obou instancí je shodný.
– Turingova redukce: Rozhodovací problém ∏1 je Turing-redukovatelný na ∏2 (píšeme ∏1 ∝T ∏2), jestliže
existuje polynomiální program pro (deterministický) Turingův stroj, který řeší každou instanci I1 problému
∏1 tak, že používá program M2 pro problém ∏2 jako podprogram (jehož volání považujeme za jeden krok).
Karpova redukce je speciálním případem Turingovy redukce (volání podprogramu jednou, přímé použití
výsledku).
Cookův teorém
– Cook dokázal, že SAT je NP-úplný problém. Z toho vyplývá:
– NPC není prázdná
– otevření cesty k důkazům NP-úplnosti převodem: pokud je problém NP a je možné redukovat SAT na
tento problém pomocí Karpovy redukce, pak je problém NP-úplný.
pokud se nalezne polynomiální algoritmus pro řešení nějakého NPC problému (třeba SAT), pak lze tento
algoritmus použít na vyřešení libovolného NPC problému
– Princip důkazu příslušnosti problému k třídě NP-těžký
– z definice (nepraktické)
– ∏' ∈ NPC je speciálním případem ∏
– ∏ ∈ NP, ∃∏' ∈ NPC, ∏' ∝ ∏ ⇒ ∏ ∈ NPC
– Nejnadějnější je třetí postup: ∏ ∈ NP, SAT ∝ ∏ ⇒ ∏ ∈ NPC (obecně můžeme k důkazu použít i jiný
NPC problém než SAT). Pro NPH problémy se postupuje obdobně, pouze se místo Karpovy redukce
používá Turingova redukce.
Definice chyby
–
Aproximativní algoritmy
– problémy v třídě APX jsou řešitelné efektivními algoritmy které najdou odpoveď ne horší než nějaké dané
procento z optimální odpovědi. Tedy například odpověď se bude z 95% blížit optimu.“
– PTAS - (polynomial time approximation scheme) třída libovolně přesně aproximovatelných problémů.
Existuje algoritmus, který pro každou relativní chybu ε > 0 vyřeší každou instanci problému v čase
polynomiálním ve velikosti instance)
– FPTAS - (fully PTAS) třída libovolně přesně a rychle aproximovatelných problémů - pro problém existuje
plně polynomiální aproximační schéma (tj. algoritmus, jehož čas výpočtu závisí polynomiálně na 1/ε)
– APX redukce
Experimentální hodnocení algoritmů
– Je algoritmus A lepší než algoritmus B?
– Pro praktické instance, je algoritmus A lepší než algoritmus B?
– Pro praktické instance, reprezentované těmito zkušebními úlohami, je algoritmus A lepší než algoritmus
B?
Konstruktivní a iterativní heuristické metody
– Konstruktivní heuristiky: Začíná se z nějaké snadno získatelné (obvykle triviální nebo skoro triviální)
konfigurace a přibližujeme se k řešení, které vyhovuje omezením problému.
– Iterativní heuristiky: Začínáme z (nějakého) řešení, z kterého se dalším postupem snažíme více přiblížit k
optimálnímu řešení.
– Dvojfázové heuristiky První fáze slouží k získání řešení (konstruktivně, náhodné řešení), ve druhé fázi
iterativní vylepšování.
–
Metoda větví a hranic
– Tato metoda je založena na prohledávání stavového prostoru do šířky. Algoritmus funguje tak, že před každým
vstupem do další větve otestuje, zda-li je možné v dané větvi získat lepší řešení než dosud dosažené nejlepší
řešení(kontroluje, zda je možné vůbec se k řešení v této větvi dostat(omezující podmínky) nebo kontroluje zda
bude řešení dostatečně optimální(opt. kitréria) nebo kontroluje, zda bude řešení po vstupu do větve optimálnější
než je aktuální řešení(opt. kitréria)). Pokud ne, pokračuje zpracováním dalšího prvku z fronty. Kvalita algoritmu
spočívá v nalezení rozhodovací funkce, která odmítne co nejvíce větví, přitom však (pokud možno) neodmítne
větev, ve které se ukrývá optimální řešení.
Prohledávání s návratem (backtracking)
– jestliže je další postup ve smyslu DFS nemožný, vracíme se o krok (nebo několik kroků) zpět k poslednímu
„rozhodovacímu“ místu a hledáme další cesty k cílovému řešení (strategie pokusu a omylu)
Globální metody
rekurzivní
– výhoda: intuitivnost implementace - stavové proměnné se udržují na zásobníku
– rekurze není vhodná na paralelní zpracování
iterativní
– využívá cyklus v těle funkce - vychází se z triviální instance a počítají se všechny složitější podinstance,
až se dobereme zadáné instance
– vhodné pro paralelní zpracování (zásobník lze rozdělit)
rozděl a panuj
– založené na přibližné dekompozici
Lokální metody
– Lokální metoda prochází stavový prostor tak, že přejde z jednoho aktuálního stavu p do stavu q, který je v
okolí stavu p. Lokální metoda má aktuální vždy jeden stav a při změně stavu uvažuje pouze jeho (relativně
malé) okolí.
– Uváznutí
– jednoduché - uváznou
– Best-Only (pouze nejlepší z okolí)
– First-Improvement (první soused zlepšující řešení)
– s návratem - vycouvají
– pokročilé - překonají lokální minimum
– Úplné metody spočívají v systematickém procházení celého stavového prostoru.
– Metody neúplné vybírají pouze jediného souseda (proto není třeba udržovat seznam sousedů již
prozkoumaných stavů) a to různými přístupy. Problémem neúplných metod je, že nemáme zaručeno správné
řešení.
Dynamické programování
– globální metoda založená na čisté dekompozici
– metoda řešení problémů, které vykazují vlastnosti překrývajících se podproblémů a optimální podstruktury
– typy
– shora dolů (rekurzivní)
– problém rozložíme na podproblémy a jejich řešení si zapamatujeme (uložíme) pro případ, že by se
nám hodila
– odpovídá rekurzi, při které si pamatujeme již nalezená řešení
– zdola nahoru (dopředný)
– všechny podproblémy, které by se nám mohly při řešení problému hodit, jsou vyřešeny předem a
následně použity pro vybudování řešení většího problému
– začína se řešit u triviálních podproblémů
– nalézt všechny potřebné podproblémy může být těžké
MVT
Pravděpodobnost
Laplaceův a Kolmogorovův model pravděpodobnosti:
Laplaceův model
konečně mnoho jevů
pravděpodobnosti jen racionální
P(A) = 0 ⇒ A je nemožný
–
–
–
–
–
–
–
–
–
–
–
Kolmogorovův model
pravděpodobnosti i iracionální
nekonečně mnoho jevů
existují možné jevy s nulovou pravděpodobností
Náhodná veličina na pravděpodobnostím prostoru (Ω, A, P)je libovolná měřitelná funkce X: Ω → ℜ, tj.
taková, že pro každý interval I platí X-1(I) = {ω ∈ Ω : X(ω) ∈ I} ∈ A
Hustota pravděpodobnosti
Distribuční funkce náhodné veličiny
Kvantilová funkce náhodné veličiny
Druhy náhodných veličin:
– diskrétní,
– (absolutně) spojitá,
– smíšená,
– jiná (např. náhodná veličina se spojitou distribuční funkcí, kterou nelze vyjádřit jako integrál)
Střední hodnota
– EX=integral(-inf, inf, x * p(x), dx), tedy suma součinů hodnoty veličiny a pravděpodobnosti takové
hodnoty
– Er = r
– E(X + Y) = EX + EY, speciální případ: E(X + r) = EX + r
– E(X - Y) = EX - EY
– E(rX) = r · EX, obecněji: E(rX + sY) = r · EX + s · EY
– E(Mixc(U, V)) = c · EU + (1 - c) · EV
Rozptyl
– DX = E( (X - EX)^2) = E(X^2) – (EX)^2
Směrodatná odchylka
– sigma=sqrt(DX)
Normovaná náhodná veličina
– Normovaná veličina má nulovou střední hodnotu a jednotkový rozptyl (poud má vzorec smysl).
– normX=(X-EX)/sigma
Operace
– Přičtení konstanty r:
– odpovídá posunutí ve směru vodorovné osy
– Vynásobení nenulovou konstantou r:
– odpovídá podobnosti ve směru vodorovné osy
– Součet náhodných veličin:
– pokud nejsou sčítané náhodné veličiny nezávislé, není jednoznačně určen (ani v opačném případě
není vztah jednoduchý).
– Směs náhodných veličin
– X = Mixc(U, V): PX = cPU + (1 – c)PV
– Lineární kombinace náhodnách veličin
– ?
Základní rozdělení
– Diracovo rozdělení
– je jediný možný výsledek
– Rovnoměrné rozdělení
– Binomické rozdělení Bi(m, p): počet úspěchů z m nezávislých pokusů, je-li v každém stejná
pravděpodobnost úspěchu p ∈ <0; 1>
–
–
Poissonovo rozdělení Po(λ):
– limitní případ binomického rozdělení pro m → ∞
Geometrické rozdělení:
– počet úspěchů do prvního neúspěchu, je-li v každém pokusu stejná pravděpodobnost úspěchu p ∈ (0;
–
1)
– px(k)=p^k (1-p)
– Normální (Gaussovo) rozdělení N(μ, σ2)
Náhodné vektory
– n-rozměrný náhodný vektor na pravděpodobnostním prostoru (Ω, A, P) je měřitelná funkce X: Ω → ℜ^n,
tj. taková, že pro každý n-rozměrný interval I platí X^(-1)(I) = {ω ∈ Ω : X(ω) ∈ I} ∈ A. Náhodný vektor
lze považovat za vektor náhodných veličin.
Statistika
Metoda momentů
– k-tý obecný moment je definován vztahem mk = E(X^k), k ∈ N
– k-tý centrální moment je definován vztahem μk = E( (X - EX)^k), k ∈ N
Metoda maximální věrohodnosti
Odhady střední hodnoty a rozptylu
Stejný výpočet jako na teoretikém základě
Počítám z naměřených hodnot, tudíž jde o odhad
Testy dobré shody a korelace
– χ2-test dobré shody: slouží k testování hypotézy, že náhodná veličina má předpokládané rozdělení.
Protože umíme hypotézy jen zamítat, nikdy nepotvrdíme, že takové rozdělení opravdu má. Testujeme
vždy diskrétní rozdělení, které však mohlo vzniknout diskretizací spojitého rozdělení. Nulovou hypotézou
je tvrzení, že náhodná veličina má diskrétní rozdělení do k tříd s pravděpodobnostmi p1, p2, …, pn.
– χ2-test dobré shody dvou rozdělení: Nulovou hypotézou je tvrzení, že dvě diskrétní náhodné veličiny mají
stejné diskrétní rozdělení.
– χ2-test nezávislosti dvou rozdělení: Nulovou hypotézou je tvrzení, že dvě náhodné veličiny (jejichž
rozdělení neznáme) jsou nezávislé.
Testování hypotéz
– Základní úloha: Máme posoudit hypotézu o hodnotě nějakého parametru rozdělení (pomocí kritéria čili
testovací statistiky T, resp. její realizace t). Můžeme se přitom dopustit chyb dvou druhů
– Zamítneme nulovou hypotézu, která platí (obviníme nevinného)
– Nezamítneme nulovou hypotézu, která neplatí (osvobodíme vinného)
Download

– prohledávání grafů – DFS – Depth first search – BFS – Breadth