Matematika

V matematice a lineární algebře se jako soustava lineárních rovnic označuje množina lineárních rovnic. Většinou tyto rovnice obsahují více než jednu proměnnou. Řešením takovýchto rovnic je pak uspořádaná n-tice popisující hodnoty jednotlivých proměnných. Soustava nemusí mít žádné řešení, může mít určitý počet, či nekonečně mnoho řešení. Následuje jednoduchá ukázka soustavy lineárních rovnic.
Obecně lze jakoukoliv soustavu zapsat jako:
Jakoukoliv soustavu lze rovněž zapsat užitím matice. Počet řádků označuje počet rovnic, počet sloupců-1 označuje počet proměnných. Poslední sloupec obsahuje konstanty.

Některé rovnice v soustavě mohou být na sobě závislé, resp jedna může být lineární kombinací druhé. Např.
Takové to rovnice nám nepřidávají novou informaci a stačí nám jedna z nich. V opačném případě nazýváme rovnice lineárně nezávislé.
atici neobsahující sloupec konstant budu označovat jako matici soustavy A samotný poslední sloupec je v podstatě vektor b, který přidáváme k matici soustavy a dostáváme tak rozšířenou matici soustavy A'. A' = (A|b).

Počet řešení

• Uvažujeme soustavu lineárně nezávislých rovnic.
• Frobeniova věta říká: "Soustava má řešení právě tehdy, když hodnost matice soustavy A je stejná jako hodnost rozšířené matice soustavy A' "
• Soustavy, kde je počet lineárně nezávislých rovnic větší než počet proměnných, nemají žádné řešení. Nazýváme je přeurčenými.
• Soustavy, kde počet proměnných je právě roven počtu rovnic, mají právě jedno řešení.
• A soustavy, kde je počet proměnných vyšší, než počet rovnic, mají nekonečně mnoho řešení. Přebytečné proměnné lze nahradit parametry a soustavu vyřešit s jejich užitím.

Metody řešení

Ekvivalentní operace

Existují 3 základní ekvivalentní operace, které používáme k řešení soustav lineárních rovnic. Tyto operace nemění výsledek rovnic, pouze je zaměňují za ekvivalentní a jednodušší rovnice.

1. Záměna pořadí rovnic
2. Násobení obou stran rovnice nenulovým číslem
3. Přičtení násobku rovnice k jiné rovnici (záporný násobek = odčítání)

Gaussova eliminační metoda

1. Zapíšeme koeficienty do rozšířené matice soustavy
2. Dopředná redukce - Matici převedeme pomocí ekvivalentních řádkových úprav na schodovitý tvar.
3. Aplikujeme Frobeniovu větu. Tím zjistíme počet řešení soustavy.
4. Zpětná substituce - Ze schodovitého tvaru rozšířené matice sestavíme zpět soustavu rovnic, ze které snadno dopočítáme řešení soustavy. Postupujeme od poslední rovnice, která obsahuje nejméně neznámých, postupným dosazováním do „vyšších“ rovnic.

Gauss-Jordanova metoda

Postup shodný s Gaussovou eliminační metodou, avšak nekončíme na schodkovém tvaru,ale pokračujeme do tzv. normovaného schodkového tvaru (A = I = jednotková matice)

Cramerovo pravidlo

Cramerovo pravidlo je vhodné především v případě, kdy chcete postup algoritmizovat, snadno se programuje. Řešit soustavu pomocí Cramerova pravidla ručně bývá obvykle složitější, než ji řešit Gaussovou eliminační metodou.

Cramerovo pravidlo funguje pouze na čtvercových maticích A. Používá k výpočtu determinant matice. Nebudu dále popisovat.

Algebraické operace

Malé info co to je algebraická operace. Jedná se o zobrazení (většinou uvažujeme binární operaci), kdy každé uspořádané dvojici (a,b) z množiny A přiřazujeme určitý výsledek, také z množiny A.

Například sčítání celých čísel je binární algebraická operace. Vezměme si dvojici (2,5). Operace sčítání přiřadí této dvojici rovněž prvek z množiny celých čísel - 7.

Vektorový prostor

Vektorový prostor (nebo též lineární prostor) je neprázdná množina V, jejíž prvky nazýváme vektory. Na této množině existují dvě algebraické operace: sčítání dvou vektorů(+) a násobení vektorů skalárem(•)

Výsledkem sčítání vektorů je rovněž vektor - např. (a1,a2) + (b1,b2) = (a1+b1,a2+b2)

Výsledkem násobení vektoru skalárem je rovněž vektor - např. (a1,a2) • b = (a1*b,a2*b)

Při dokazování zda-li je těleso opravdu vektorovým prostorem, musíme ověřit 8 následujících axiomů (počet se liší v závislosti na literatuře)

1. Asociativní zákon pro sčítání ->
2. Existence nulového vektoru o ->
3. Existence opačného vektoru -u k u ->
4. Komutativita sčítání ->
5. Násobení vektoru jedničkou ho nezmění ->
6. Asociace násobení ->
7. Distributivita vzhledem ke sčítání ->
8. Distributivita vzhledem k násobení ->

Formálně je tedy vektorový prostor definován jako čtveřice - Množina V (zpravidla R^2), Množina T (zpravidla R), operace sčítání, operace násobení. V tomto prostoru musí platit výše uvedené pravidla.

Mezi jednotlivými prostory je definováno sčítání prostorů a jejich průnik (nenulový, jelikož každý vektorový prostor obsahuje nulový prvek)

Následující obrázek graficky popisuje algebraické operace sčítání dvou vektorů a násobení vektoru skalárem (zleva).

Zobrazení mezi vektorovými prostory X a Y tak, že zůstanou zachovány operace součtu a součinu skalárem. Patří zde lineární funkce a také Derivace a Integrace.

Superpozice = pokud známe už výsledky x a y, tak když chceme počítat f(x+y), stačí sečíst x a y (vyplývá z definice lineárního zobrazení)

Nejrychlejší způsob jak zjistit zda zobrazení NENÍ lineární je podívat se, zda-li po dosazení za všechny proměnné 0, nám vyjde 0. (jelikož 0+0 = 0)... pokud ne tak to není lineární zobrazení, pokud jo, musíme dále ověřovat.

Každé lineární zobrazení je funkcí, ne každá funkce je linární zobrazení. Každé lineární zobrazení lze zapsat maticí (urychluje práci, zapíšu ASAP).

Zobrazení = mapuje obraz z množiny M na vzor z množiny N

Definiční obor = množina všech vzorů

Obor hodnot = množina všech obrazů

Nulový prostor/Jádro zobrazení

Jedná se o takovou podmnožinu definičního oboru, tak že A je zobrazeno na nulový vektor. Resp. množina vzorů, jejichž obrazy jsou nulové vektory.

Derivace nějaké funkce je změna (růst či pokles) obrazu této funkce v poměru k (ideálně) nekonečně malé změně jejích argumentů. Opačným procesem k derivování je integrování. V určitém bodě se dá derivace znázornit jako směrnice tečny (úhel) a udává nám jak se funkce mění v bezprostředním okolí. Nulová derivace v bodě znamená, že tečna je vodorovná s osou x a funkce tedy neklesá ani neroste. Jedná se o tzv. "stacionární bod", který může a nemusí mýt lokálním extrémem.

Derivaci můžeme derivovat znova a dostat tzv. druhou derivaci, obecně pak derivaci vyššího řádu. Logicky popisuje změnu první derivace v bezprostředním okolí. Pomocí první derivace hledáme stacionární body, potažmo jestli funkce v daném bodě klesá, či roste. Pomocí druhé derivace můžeme zjistit zda-li je stacionární bod lokálním minimem (f'=0 a f''>0), či maximem (f'=0 a f''<0). Obecně sama o sobě druhá derivace udává zda-li je fce konvexní (f''>0) či konkávní (f''<0).

Spolu s derivací tvoří dvě hlavní operace matematické analýzy. Pojem integrálu je zobecněním pojmů jako plocha, objem, součet či suma.

Mějme funkci ƒ reálné proměnné x na intervalu [a, b].
Pod pojmem (určitý) integrál rozumíme obsah plochy ve dvojrozměrné rovině, který je omezen grafem funkce ƒ, osou x a svislými přímkami x = a a x = b.

Neurčitý integrál je takový, který není "omezený" body a,b. Hledáme množinu funkcí, které když zderivujeme získáme původní funkci. Tuto množinu nazýváme Primitivní funkce F. ( F'(x) = f(x) ) a značíme

Variace - Kolik možností jak vybrat z k prvků z n, přičemž záleží na pořadí (1,2) != (2,1)

Permutace - Uspořádání n prvků, nevybíráme. Opakování = některý prvek je v množině vícekrát, ale nerozlišujeme mezi nimi.(permutace = variace kde n=k)

• Příklad bez opakování = počet různého uspořádání slova "ABC"| s opakováním = počet různého uspořádání slova "AAC".

Kombinace - Variace, přičemž nezáleží na pořadí = kolika možnostmi vybrat neuspořádanou k-tici z n. (1,2) = (2,1)

Kombinační číslo - udává počet kombinací, značíme čteme "n nad k". Také se nazývá binomický koeficient.

Pascalův trojúhelník - trojúhelník kde číslo na dalším řádku bude součtem sousedních čísel o řádek výše. Odvozený z kombinační věty.

Pojmy

Neorientovaný graf je dvojice G = (V,E), kde V je množina vrcholů a E je množina neuspořádaných dvouprvkových množin vrcholů = hran

Orientovaný graf je rovněž dvojice, ale E je množina uspořádaných dvouprvkových množin vrcholů.

Sousední vrcholy jsou vrcholy spojené hranou

Smyčka jedna hrana vedoucí z jednoho uzlu do sebe samého (Většinou nepovoleno v neorientovaném grafu - vzniká tzv. pseudograf)

Podgraf - Množina jeho vrcholů je podmnožinou původního a to samé platí u hran, přičemž hrana může existovat pouze mezi zahrnutými vrcholy.

Faktor - podgraf obsahující všechny jeho vrcholy (liší se pouze hranami)

Stupeň vrcholu - počet hran spojených s vrcholem, orientovaný graf má dva stupně - vstupní a výstupní

Sled - sled vrcholů a hran; začíná i končí vrcholem

Tah - sled ve kterém není žádná hrana více než jednou.

Eulerův tah - tah zahrnující všechny hrany grafu

• Neorientovaný souvislý graf má Eulerův tah právě když - obsahuje dva uzly lichého stupně a zbytek má stupeň sudý.
• Orientovaný souvislý graf má Eulerův tah právě když - jeden uzel má výstupní stupeň vyšší než vstupní, výstupní stupeň o jedna nižší než vstupní a zbytek má výstupní a vstupní stupně shodné.
• Graf obsahující Eulerův tah se nazývá Eulerův graf

Eulerův okruh - to samé co Eulerův tah, navíc končí v místě kde se začalo (Uzavřený Eulerův tah)

• Neorientovaný souvislý graf má Eulerův tah právě když všechny stupně mají sudý stupeň
• Orientovaný souvislý graf má Eulerův tah právě když všechny vrcholy mají stejný vstupní i výstupní stupeň

Cesta - tah ve kterém se neopakují žádné vrcholy

Hamiltonova cesta - cesta obsahující všechny uzly

Kružnice / cyklus - Uzavřená cesta, cyklus je v orientovaném, kružnice v neorientovaném; obdobně existuje Hamiltonova kružnice

Souvislost -

Strom - minimální souvislý graf bez kružnic, odebráním jakékoliv hrany se stane nesouvislým, přidáním vznikne kružnice

Les - Množina navzájem nepropojených stromů.

Kořenový strom (root tree) - orientovaný strom ve kterém je vyzačený jeden vrchol jako strom

Kostra (spanning tree) - Podgraf, který obsahuje všechny vrcholy (= faktor) a zároveň je stromem (neobsahuje kružnice)

Izomorfismus grafů - stejné grafy jinom jinak pojmenované/pokroucené.(existuje kompletní zobrazení z jednoho grafu do druhého). Stejný počet hran, vrcholů, stejné stupně, stejné sousedy...

Typy grafů

Orientovaný / neorientovaný - orientované / neorientované hrany (popsané výše)

Ohodnocený / neohodnocený - Hrany mohou mít hodnotu (cenu), většinou slouží například ke znázornění vzdálenosti mezi městy atp., Hrany mohou mít i podmínku atp.

Úplný graf - každý vrchol spojen s každým

Plánární graf(rovinný) - graf jehož hrany se v žádném místě nekříží

k - partitní - graf, který jde rozdělit na k částí tak, že vrcholy v jedné části mezi sebou nesdílí žádnou hranu. Respektive každý vrchol sousedí pouze s vrcholem z jiné skupiny. Nejčastěji nás zajímá bipartitní graf(neobsahuje liché kružnice)

Síť - orientovaný graf, kde každý vrchol má nezáporné hodnocení (x >= 0)

Symetrický = pro každý vrchol platí, že počet hran z X do Y je stejný jako z Y do X

Chromatické číslo - minimální počet barev, kterým lze graf obarvit tak, aby sousedící vrcholy neměly stejnou barvu.

Algoritmy

Kruskalův algoritmus - vyhledávání minimální kostry grafu (přidáváme všechny hrany s co nejnižší cenou, aby nevznikla kružnice)

Dijkstrův algoritmus - vyhledávání nejkratší cesty v orientovaném grafu. Začneme na začátku, projdeme všechny hrany a aktualizujeme vzdálenost. Vezmeme vrchol s nejmenší vzdáleností a pro všechny jeho hrany aktualizujeme vrcholy. Postupujeme dokud máme jakýkoliv vrchol k projití. Výsledkem jsou nejkratší vzdálenosti do všech vrcholů v grafu vzhledem k počátku.

Barvení grafů - NP úplný problém.

Užití grafu

Stromy - efektivní vyhledávání a seřazování

Popis relací - např. kdo je čí kamarád, co je dělitel čeho atp.

Nejkratší cesta - Dijkstrův algoritmus

Maximální tok

Automaty

"Jednotažky" :3