Rozdíly

Zde můžete vidět rozdíly mezi vybranou verzí a aktuální verzí dané stránky.

--- mat:start [08. 06. 2012, 16.13:09] – [Struktura = (množina, binární operace)] pitel
+++ mat:start [14. 09. 2026, 04.42:31] (aktuální) – odstraněno - upraveno mimo DokuWiki (Neznámé datum) 127.0.0.1
@@ Řádek 1: / Řádek 1: @@
-====== Matematické struktury v informatice ======
-[[http://www.explosm.net/comics/762/|{{ http://www.explosm.net/db/files/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!

Kalábovi

Uživatelské nástroje

Nástroje pro tento web

Rozdíly

Nástroje pro stránku