Státnice Flashcards
Algo+Diskrétní mat (25 cards)
Lineární nezávislost
Žádný řádek není lineární kombinací ostatních.
U lináerně závislých dokážeme najít reálná čísla c1 … ck kdy alespoň jedno je různé od nuly a platí, že: 0 = c1x1 + c2x2 + … + ckxk
Hodnost matice
Dimenze lineárního obalu řádkových vektorů. (řádkového prostoru)
Hodnost matice je počet nenulových řádků (pivotů) v odspuňovaném tvaru.
Je hodnost matice stejná jako hodnot transponované matice?
Ano
Jak maximálně velká může být hodnost matice u n x m ?
Hodnot bude vždy menší než hodnota n nebo m (beru tu nižší hodnotu). Tedy menší než počet sloupců nebo řádků podle toho co je menší. (Právě třeba kvůli transponované matici, kdy 3x4 => 4x3 T )
Singulární a regulární matice.
Singularitu a regularitu řešíme pouze u čtvercových matic.
Singulární je tedy čtvercová matice, která je
- lineráně závislá (LZ),
- hodnot matice je menší než počet řádků matice h(A) < n
- determinant je roven 0
- nelze k ní vypočítat inverzní matici
Regulární
- lineárně nezávislá (LN)
- h (A) = n
- determinant je rozdílný od 0
- lze k ní vypočítat inverzní matici
Co je matice soustavy ?
Matice soustavy je zobrazení soustavy lineárních rovnic v maticovém zápisu, kdy žádky odpovídají jednotlivým soustavám a sloupce jednotlivým neznámým. Převodem na odstupňovaný tvar pomocí Gaussovi eliminace můžeme dopočítat hodnoty jednotlivých neznámých.
Frobeniova věta o řešitelnosti soustav lineárních rovnic
Soustava lineárních rovnic (S) má řešení tehdy a jen tehdy, když hodnost matice soustavy je rovna hodnosti rozšířené matice soustavy. (tzn. mám nulový řádek a za čarou nenulové číslo)
h(a) = n pak soustava má právě jedno řešení
h(a) < n pak soustava má nekonečně mnoho řešení
Co je aritmetický vektor ?
aritmetický vektor délky n je uspořádaná n-tice reálných čísel x1, x2, … xn značíme jako R^n
Vektory stejné délky můžeme sčítat, násobit reálným číslem
Lineární kombinace
Vektor a je lineární kombinací vektorů a1 … an jestliže existují reálná čísla c1 … ck taková, že platí: a = c1a1 + c2a2 + …. + ck ak.
Čísla c1 … ck se nazývají koeficienty lineární kombinace (skaláry)
Lineární závislost a nezávislost vektorů
Vektory jsou lineárně závislé, pokud existují taková reálná čísla c1 … ck kdy alespoň jedno je různé od nuly a platí: 0 = c1 x1 + c2 x2 + …. + ck xk
V opačném případě jsou nezávislé.
V odstupňovaném tvaru existují volné parametry ==> lineárně závislá soustava = nekonečně mnoho řešení
U čtvercových matic můžeme o lineární závislosti / nezávislosti rozhodnout například i podle hodnoti matice
Definice a vlastnosti aproximačního algoritmu
Aproximační algoritmus používáme pro řešení problémů, které jsou příliž těžké. Aproximačním algoritmem můžeme dosáhnout dostačujícího výsledku, který ale proběhne v polynomiálním čase. Tedy dostaneme výsledek který je uspokojový a dostatečný. Příkladem je hladový algoritmus nebo
Maximalizační a minimalizační úloha u aproximačního algoritmu
Maximalizační úloha: Hledáme řešení, které je co nejlepší (např. nejvyšší zisk nebo výkon). Aproximační algoritmus zaručuje, že dosažené řešení bude blízko k optimálnímu.
Příklad: Rozvrhování úkolů na procesory tak, aby bylo co nejvíce úkolů dokončeno za daný čas.
Minimalizační úloha: Hledáme řešení, které minimalizuje určitou hodnotu (např. náklady nebo čas). Aproximační algoritmus nám zajistí výsledek, který nebude příliš vzdálený od optimálního.
Příklad: Plánování tras kurýra tak, aby ujel co nejmenší vzdálenost.
Popiš hladový algoritmus
Je to aproximační algoritmus, kterým můžeme řešit úlohy jako plánování výrobní linky, kdy si úkoly s různými dobami řešení seřadíme od nejdelší po nejkratší a následně zkoušíme rozvrhnout na jednotlivé stroje - ukázka.
Další příklad hladového algoritmu je hledání minimální kostry grafu podle Kruskala
Vlastnosti hladového algoritmu
Rychlý a snadno implementovatelný
Aproximační poměr: tento algoritmus je 2-aproximační, což znamená že výsledek není nikdy horší než dvojnásobek optimálního řešení
Pravděpodobnostní algoritmy Las Vegas a Monte Carlo popis
Las Vegas - pravděpodobností algoritmus, který vždy vrátí správný výsledek, avšak s malou pravděpodobností může běžet velmi dlouho nebo vyžadovat velké zdroje
příklad: Kruskalův algoritmus, quick sort kdy výběr pivota je náhodný
Monte Carlo - může vrátit nesprávný výsledek, ale s garantovaným časem doběhnutí
=> aproximace čísla Pí
=> Miller-Rabinův test k určení prvečíselnosti
=> simulace šíření nemoci
Las Vegas a Monte Carlo - čas doběhnutí a výsledek
Las Vegas:
Čas doběhnutí: S největší pravděpodobností
Výsledek: Vždy
Monte Carlo
Čas doběhnutí: S největší pravděpodobností
Výsledek: Vždy
Co je to vektorový podprostor?
Podprostor K vektorového prostoru L je neprázdná podmnožina vektoru L, která je uzavřená na sčítání a uzavřená na násobení skalárním číslem. Také obsahuje nulový vektor.
Množina generátorů
Báze
Množina generátorů x1 … x vektorového prostoru L, jejíž vektory jsou lineárně nezávislé se nazývají báze L.
báze se dá jednoduše vyjádřit jako linární kombinace. Báze je optimální množina ve které lze vyjádřit všechno jednoznačně.
Dimenze
Počet vektorů ve všech bázích vektorového prostoru .
Přímka - dimenze 1
rovina - dimenze 2
prostor - dimenze 3
Co je Kartézský součin
Kartézský součin je množina všech uspořádaných dvojic z relace x, y kde x náleží X a y náleží Y
Důležité vlastnosti - záleží na pořadí, není komutativní
Co je binární relace, jak je můžeme zobrazovat?
Binární relace je podmnožinou kartézkého součinu.
Uzlový graf (klasický graf), maticový zápis, kartézský graf, nebo je vypsat do závorek
Jaké máme typy relací
Reflexivní
Symetrická
Asymetrická
Antisymetrická
Transitivní
Irreflexní
Dimenze prostoru a řešení homogenní soustavy rovnic
Dimenze je rovna počtu volných proměnných, což je rovné počtu neznámých - hodnot matice soustavy
Homogenní soustava má vždy alespoň triviální řešení
h = n pak má jedno řešení
h < n pak má nekonečně mnoho řešeí
