====== Matematické struktury v informatice ======
[[http://www.explosm.net/comics/762/|{{ https://files.explosm.net/comics/Dave/comicexam.png}}]]
//A// → //B// = ¬//A// ∨ //B//
  * Argumentem komplexního čísla je jeho úhel vzhledem k reálné ose. Komplexní číslo má pak tvar //r//(cos//φ// + //i//sin//φ//).

===== Axiomy =====
  - //A// → (//B// → //A//)
  - (//A// → (//B// → //C//)) → %%((%%//A// → //B//) → (//A// → //C//%%))%%
  - (¬//B// → ¬//A//) → (//A// → //B//)
  * **[[wp>Modus ponens]]** (pravidlo odloučení) //A// → //B// můžeme přepsat na //A// ⊢ //B//((//A// dokazuje //B//)).
  * **Věta o dedukci** je Modus ponens obráceně.
  * **Pravidlo zobecnění** znamená, že někam připíšeš ∀//x//
  * **Axiom kvantifikátoru** -- ∀//x//(//A// ⇒ //B//) → (//A// ⇒ ∀//xB//)
===== Struktura = (množina, binární operace) =====
http://algebra.matfyz.info/1/struktury.jpg, [[wp>Template:Algebraic structures]]
^  grupoid   |  uzavřenost  |
^  pologrupa  |  asociativita((a(bc) = (ab)c))  |
^  monoid   |  neutrální prvek  |
^  grupa  |  inverzní prvek  |

Pokud je operace komutativní, je i struktura komutativní ("komutativní grupoid").

==== Podgrupy ====
Zmenšíme //M//, případně upravíme operaci. Musí to ale pořád být grupa (nesmí z //M// zmizet neutrální a inverzní prvek)!
===== Struktura = (množina, aditivní operace, multiplikativní operace) =====
^  okruh  |  (//M//, +, ·): %%((%%//M//, +) = komutativní grupa ∧ (//M//, ·) = monoid ∧ distributivita((a(b + c) = ab + ac))  |
^  obor integrity  |  neexistují dělitelé "nuly"  |
^  těleso  |  obor integrity (okruh), kde jsou všechny "nenulové" prvky invertibilní((Pro každý "nenulový" prvek platí, že najdeš nějaký jiný prvek, kterým, když ho vynásobíš, dostaneš "jedničku". To ale neznamená, že by (//M//, ·) byla grupa, protože pak by existovali dělitelé "nuly"!))  |
^  pole  |  komutativní těleso  |

  * "Nula" -- neutrální prvek +
  * "Jedinčka" -- neutrální prvek ·
  * Pokud je (//M//, ·) komutativní monoid, je i struktura komutativní ("komutativní okruh").
===== Kongruence =====
//g<sub>1</sub>// ≡ //g<sub>2</sub>// ∧ //h<sub>1</sub>// ≡ //h<sub>2</sub>// ⇒ //g<sub>1</sub>// ★ //h<sub>1</sub>// ≡ //g<sub>2</sub>// ★ //h<sub>2</sub>//
  * ★ je libovolná operace ve struktuře
  * ≡ znamená kongruence

Pravá kongruence: //g<sub>1</sub>// ≡ //g<sub>2</sub>// ⇒ //g<sub>1</sub>// ★ //w// ≡ //g<sub>2</sub>// ★ //w//

Aby to vůbec mohla být kongruence, musí platit **relace ekvivalence**!
  - **Reflexivita**: //a// ~ //a//
  - **Symetrie**: //a// ~ //b// ∧ //b// ~ //a//
  - **Tranzitivita**: //a// ~ //b// ∧ //b// ~ //c// ∧ //c// ~ //a//
===== Homomorfizmus =====
Zobrazení třeba z (ℂ, +) → (ℝ, ⊕).

//f//(//a// + //b//) = //f//(//a//) ⊕ //f//(//b//)\\
//a//, //b// ∈ ℂ

Když má ta struktura víc operací, musí se dokazovat pro všechny!

**Jádro** jsou ty prvky, které se zobrazí na neutrální prvek. Pokud má jádro právě jeden prvek, je homomorfizmus injektivní.
===== Prenexní tvar =====
  - Odstranění zbytečných kvantifikátorů((∀//xB//(//y//%%)%%))
  - Zbavení se spojek kromě ∧, ∨ a ¬
  - Přejmenování proměnných
  - Přesun kvantifikátorů doleva (a odstranění neatomických negací)

===== Metrika =====
[[wp>Metric (mathematics)]]
  * Musí vždy vyjít kladné číslo.
  * Pokud mají 2 body stejné souřadnice, musí vyjít 0.
  * Vzdálenost z bodu //A// do bodu //B// musí být stejná jako z bodu //B// do bodu //A//.
  * [[wp>Triangle inequality|Trojúhelníková nerovnost]].

===== Norma =====
[[wp>Norm (mathematics)]]

Značí se ||//x//||, v podstatě je to dálka vektoru. Euklidovská norma je sqrt(//x//² + //y//² + //z//²).
  * Musí vždy vyjít kladné číslo.
  * ||//x//|| = 0, pouze pokud //x// je nulový vektor.
  * ||//ax//|| = |//a//| · ||//x//||
  * ||//x// + //y//|| ≤ ||//x//|| + ||//y//|| ([[wp>Triangle inequality|Trojúhelníková nerovnost]])
[[wp>Norm (mathematics)#p-norm|{{http://upload.wikimedia.org/math/a/6/7/a67bac91ac0342f55440ee0e81facbae.png|||x||_p}}]]

Norma implikuje metriku: |//a//, //b//| = ||//a// − //b//||
===== Ortonormalizace =====
To jako že najdeme bázi jednotkových a kolmých vektorů.

Pokud //a// * //v<sub>1</sub>// + //b// * //v<sub>2</sub>// = //v<sub>3</sub>// má řešení, nejsou vektory lineárně nezávislé, tudíž nejsou bázové a nemá to řešení!

Vstupem je nějaká báze (lineárně nezávislé vektory, je jich tolik, jako má prostor dimenzí).
  - //φ<sub>1</sub>// = //f<sub>1</sub>// / ||//f<sub>1</sub>//||
  - //h<sub>n</sub>// = //f<sub>n</sub>// − (//f<sub>n</sub>// · //φ<sub>n−1</sub>//)((Skalární součin: //x<sub>1</sub>x<sub>2</sub>// + //y<sub>1</sub>y<sub>2</sub>// + //z<sub>1</sub>z<sub>2</sub>//)) × //φ<sub>n−1</sub>// − (//f<sub>n</sub>// · //φ<sub>n−2</sub>//) × //φ<sub>n−2</sub>// − …
  - //φ<sub>n</sub>// = //h<sub>n</sub>// / ||//h<sub>n</sub>//||
  - Opakuj kroky 2 a 3, dokud máš vektory.

==== Příklad ====
  * //f<sub>1</sub>// = (1, 1, 1)
  * //f<sub>2</sub>// = (2, 1, 2)
  * //f<sub>3</sub>// = (−1, 0, 1)

  - **//φ<sub>1</sub>//** = //f<sub>1</sub>// / ||//f<sub>1</sub>//|| = (1, 1, 1) / sqrt(1² + 1² + 1²) = **(1/sqrt(3), 1/sqrt(3), 1/sqrt(3))**
  - //f<sub>2</sub>// · //φ<sub>1</sub>// = (2, 1, 2) · (1/sqrt(3), 1/sqrt(3), 1/sqrt(3)) = (2/sqrt(3) + 1/sqrt(3) + 2/sqrt(3)) = 5/sqrt(3)
  - //h<sub>2</sub>// = //f<sub>2</sub>// − (//f<sub>2</sub>// · //φ<sub>1</sub>//) × //φ<sub>1</sub>// = (2, 1, 2) − 5/sqrt(3) × (1/sqrt(3), 1/sqrt(3), 1/sqrt(3)) = (2, 1, 2) − (5/3, 5/3, 5/3) = (1/3, −2/3, 1/3)
  - **//φ<sub>2</sub>//** = (1/3, −2/3, 1/3) / sqrt(2/3) = **(1/sqrt(6), −2/sqrt(6), 1/sqrt(6))**
  - //f<sub>3</sub>// · //φ<sub>1</sub>// = (−1, 0, 1) · (1/sqrt(3), 1/sqrt(3), 1/sqrt(3)) = 0
  - //f<sub>3</sub>// · //φ<sub>2</sub>// = (−1, 0, 1) · (1/sqrt(6), −2/sqrt(6), 1/sqrt(6)) = 0
  - //h<sub>3</sub>// = //f<sub>3</sub>// − (//f<sub>3</sub>// · //φ<sub>1</sub>//) × //φ<sub>1</sub>// − (//f<sub>3</sub>// · //φ<sub>2</sub>//) × //φ<sub>2</sub>// = (−1, 0, 1) − 0 × //φ<sub>1</sub>// − 0 × //φ<sub>2</sub>// = (−1, 0, 1)
  - **//φ<sub>3</sub>//** = (−1, 0, 1) / sqrt(2) = **(−1/sqrt(2), 0, 1/sqrt(2))**

===== Násobení matic =====
^ ^^  //a<sub>2</sub>//  ^  //b<sub>2</sub>//  ^
^:::^^  //c<sub>2</sub>//  ^  //d<sub>2</sub>//  ^
^  //a<sub>1</sub>//  ^  //b<sub>1</sub>//  |  //a<sub>1</sub>a<sub>2</sub>// + //b<sub>1</sub>c<sub>2</sub>//  |  //a<sub>1</sub>b<sub>2</sub>// + //b<sub>1</sub>d<sub>2</sub>//  |
^  //c<sub>1</sub>//  ^  //d<sub>1</sub>//  |  //c<sub>1</sub>a<sub>2</sub>// + //d<sub>1</sub>c<sub>2</sub>//  |  //c<sub>1</sub>b<sub>2</sub>// + //d<sub>1</sub>d<sub>2</sub>//  |

===== Grafy =====
  * Suma stupňů všech uzlů = 2 × počet hran
  * Grafy jsou izomorfní tehdy, pokud je dokážeš nakreslit jinak, ale přitom je to pořád stejný graf.
  * Při reprezentaci grafu maticí bývají řádky //odkud// a sloupce //kam//.
  * **Artikulace** je vrchol, který když odstraníme, zvýší se počet komponent.

  - **Sled** je libovolná posloupnost uzlů a hran.
  - **Tah** nesmí opakovat hrany (ale uzly může).
  - **Cesta** nesmí opakovat ani hrany ani uzly.
==== Nejkratší cesty ====
  - [[wp>Dijkstra's algorithm]] -- Neumí záporné smyčky.
  - [[wp>Floyd–Warshall algorithm]] -- Když na diagonále vyjde záporné číslo, je tam záporná smyčka. Matici následovníku na začátku vyplníme podle čísla sloupce.

==== Minimální kostry ====
[[wp>Minimum spanning tree]]
  * [[wp>Kruskal's algorithm]] -- Vybírej nejlevnější hrany dokud nemáš pokryté všechny uzly. Nesmí vzniknout kružnice!
  * [[wp>Prim's algorithm]] -- Zvol si uzel, a z něj jdi nejlevnější hranou. Teď máš 2 uzly, zase přidej nejlevnější hranu. Atd. dokud nemáš všechny uzly. Zase bacha na kružnice!