Sylaby předmětů bakalářského studia dle pracovní skupiny pro algebru a geometrii. Zpracovány předměty 1) povinné předměty pro všechna zaměření: Diskrétní matematika, Lineární algebra I a II, Algebra I 2) povinné předměty specializace "Obecná matematika" Lineární algebra a geometrie III, Algebra II, Dif. geometrie křivek a ploch, Topologie (Pozn: "[Inf]" znamená "informativně".) ================================================================== Lineární algebra a geometrie I 1. Vektorové prostory. 2. Operace s maticemi. 3. Gaussova eliminace. 4. Podprostory. 5. Lineární nezávislost. 6. Báze a dimenze. 7. Souřadnice. 8. Lineární zobrazení. 9. Matice lineárního zobrazení. 10. Soustavy lineárních rovnic. 11. Determinanty. 12. Afinní geometrie (afinní prostory a podprostory, vzájemná poloha, geometrické úlohy, afinní zobrazení). 13. Aplikace lineární algebry [Stručný popis změn: v rámci sloučení M1110 a M1111 doporučena praxe z M1110, kde se učí Afinní geometrie. Položka "Aplikace" nebude na konci semestru, ale samozřejmě průběžně.] ================================================================== Lineární algebra a geometrie II 1. Lineární formy (pouze nezbytné minimum). 2. Bilineární a kvadratické formy (definice, matice vzhledem k dané bázi, diagonalizace, signatura, Sylvestrův zákon setrvačnosti, definitnost a semidefinitnost pomocí hlavních minorů, definitnost na podprostoru[Inf], kvadriky[Inf]). 3. Euklidovká geometrie (skalární součin, kolmá projekce, vzdálenost a odchylka afinních podprostorů). 4. Lineární operátory (invariantní podprostory, vlastní čísla a vektory, charakteristický polynom, algebraická a geometrická násobnost vlastních čísel, podobnost matic, podmínky diagonalizovatelnosti). 5. Ortogonální a unitární operátory (definice a základní vlastnosti,vlastní čísla a jejich geometrický význam). 6. Samoadjungované operátory (adjungovaný operátor, symetrické a hermitovské matice, spektrální rozklad, věta o hlavních osách). 7. Rozklady matic (singulární a QR rozklad, pseudoinverzní matice, aplikace na řešení soustav lineárních rovnic). 8. Jordanův kanonický tvar (nilpotentní endomorfismy, kořenové podprostory, výpočet pomocí řetězců). 9. Kuželosečky (osy, vrcholy, střed) [Stručný popis změn: a) odstraněno: afinní geometrie přesunuta do LAI, duální vektorový prostor z položky 2 přesunut do LAIII, b) novinky: i) rozklady matic (zapracovávají se již od 2017), ii) kuželosečky jsou vyžádány navazujícími předměty (optimalizace a statistika), kde se znalost využívá. Přesný obsah se musí dojasnit v dalších fázích příprav sylabů (Zemánek, D. Kraus). Mělo by jít zřejmě o jakousi základní "kuchařku". Zařazeno bude někde dřív v semestru.] ===================================================================== Diskrétní matematika 1. Základní logické pojmy (výroková logika, kvantifikátory, formule, zápis matematických tvrzení, důkazy). 2. Základní množinové pojmy (množinové operace včetně kartézského součinu). 3. Zobrazení (typy zobrazení, skládání zobrazení). 4. Mohutnost množiny (konečné, spočetné a nespočetné množiny). 5. Relace (typy a vlastnosti relací, skládání, aplikace v databázích). 6. Ekvivalence a rozklady (jádro zobrazení, využití při konstrukci číselných oborů). 7. Uspořádané množiny (relace uspořádání, Hasseové diagramy, úplné svazy, izotonní zobrazení, svazy a Boolovy algebry[Inf], princip maximality [Inf]). 8. Kombinatorika (elementární pojmy a principy - permutace, variace, kombinace, pravidla součtu, součinu a bijekce, Dirichletův princip, pricip inkluze a exkluze). 9. Teorie grafů (orientované a neorientované grafy, souvislost, kostry, Eulerovy grafy, základní algoritmy, aplikace). [Stručný popis změn: a) odstraněno: zatím nic b) novinky: i) svazy a Boolovy algebry, ii) navrhujeme přidat princip maximality (tj. ukázku použití axiomu výběru - v rozvaze nedořešeno) např. použitý na existenci báze ve vekt. prostorech, iii) rozepsaná položka 8, aby byla v souladu s kapitolou 5.3. interních materiálů, iv) zmínka o databázích přesunuta z výstupů do sylabů.] ======================================================================= Algebra I 1. Binární operace na množině, asociativita, komutativita, pojem grupy, příklady grup (grupy čísel, zbytkových tříd, permutací, transformací a matic) a počítání v nich. 2. Základní vlastnosti grup (včetně krácení, mocniny prvku, řádu prvku). 3. Podgrupy (včetně podgrupy generované množinou) a homomorfismy grup (včetně jádra). 4. Izomorfismus grup, součin grup, základní reprezentace grup (Cayleyova věta)[Inf], klasifikace cyklických grup, klasifikace konečných komutativních grup[Inf]. 5. Rozklad grupy podle podgrupy (Lagrangeova věta). 6. Základy elementární teorie čísel (malá Fermatova, Eulerova věta, příklad aplikací směrem k RSA[Inf]). 7. Ukázka aplikace teorie grup v kombinatorice (Burnsidovo lemma)[Inf]. 8. Pojem (komutativního) okruhu, oboru integrity, tělesa, jejich základní vlastnosti. 9. Podokruh (včetně podokruhu generovaného množinou) a homomorfismy okruhů. 10. Dělitelnost v komutativních okruzích (ireducibilita, okruh s jednoznačným rozkladem). 11. Polynomy (základní vlastnosti, dělení polynomů se zbytkem, Euklidův algoritmus, hodnota polynomu v nějakém prvku, kořen polynomu, násobné kořeny, souvislost s derivací polynomu). 12. Polynomy nad okruhy komplexních, reálných, racionálních a celých čísel (ireducibilní polynomy, Viétovy vztahy, racionální kořeny polynomů s celočíselnými koeficienty, násobné kořeny, základní věta algebry[Inf]). 13. Polynomy více proměnných - symetrické polynomy [Stručný popis změn: a) odstraněno: konec teorie grup (faktorizace, akce grupy na množině, Sylowovy věty) - přesun do Algebry II; b) novinky: aplikace v kombinatorice a šifrování, symetrické polynomy, zpomalený začátek s posílením příkladů s maticemi] ====================================================================== Algebra II 1. Svazy (dvojí definice polosvazů a svazů, morfismy svazů, zúplnění svazů, distributivní a modulární svazy, Booleovy algebry, reprezentace konečných distributivních svazů a konečných Booleových algeber). 2. Pokračování teorie grup (normální podgrupy, faktorizace grup, akce grupy na množině, centrum grupy, p-grupy, Sylowovy věty). 3. Okruhy a polynomy (ideály, faktorové okruhy, prvoideály a maximální ideály, podílové těleso, rozšíření těles, stupeň rozšíření, konečná tělesa, základy Galoisovy teorie). [Stručný popis změn: a) odstraněno: univerzální algebra, b) novinky: konec teorie grup z algebry I, základy Galoisovy teorie. Komentář: odstranění univerzální algebry je velká změna oproti interním materiálům, viz 5.20. Pokud bychom ji chtěli nechat bylo by asi nutné zvýšit hodinovou dotaci.] ====================================================================== Lineární algebra a geometrie III 1. Afinní a projektivní prostor (definice, projektivní rozšíření, aplikace na klasifikaci kuželoseček a kvadrik[Inf]). 2. Duální prostor (definice, duální báze, věta o druhém duálu). 3. Základy lineárního programování (systémy lineárních nerovnic, Farkasovo lemma, věta o dualitě v lineárním programování, konvexní kužely a polyedry, rozklady polyedrů - Minkowského věta, geometrické odvození simplexové metody). 4. Tenzory, symetrické a antisymetrické tenzory (báze, souřadnice, základní vlastnosti). 5. Determinant, objem, orientace (objemová forma, orientovaný úhel, vektorový součin). 6. Kvaterniony (aplikace na geometrii v prostoru). 7. Smithův normální tvar nad Z (souvislost s konečně generovanými komutativními grupami). 8. Smithův normální tvar nad K[x] (souvislost s charakteristickým a minimálním polynomem, souvislost s Jordanovým kanonickým tvarem). [Stručný popis změn: a) odstraněno: podrobný výklad kvadrik, b) novinky: základy lineárního programování.] ====================================================================== Topologie 1. Topologický prostor, spojité zobrazení, konstrukce s topologickými prostory (součin, součet, podprostor, kvocient). 2. Axiomy oddělitelnosti (Hausdorffovy, regulární, úplně regulární a normální prostory). 3. Kompaktnost, lokální kompaktnost, kompaktifikace (jednobodová, Čechova-Stoneova). 4. Souvislost, lokální souvislost, oblouková souvislost. 5. Homotopie, fundamentální grupa, nakrytí[Inf]. 6. Simpliciální komplexy, triangulace, Brouwerova věta. 6. Uniformní prostory, metrizovatelnost. 7. Případně další koncepty (kompaktní generovanost, parakompaktnost, topologické grupy, Stoneova dualita atp.). [Stručný popis změn: a) odstraněno: nic, b) novinky: nakrytí.] ====================================================================== Diferenciální geometrie křivek a ploch 1. Geometrická interpretace základních konceptů analýzy s použitím pojmů lineární algebry (tečný prostor, lineární zobrazení, tenzory) a s důrazem na invarianci vůči reparametrizacím. Integrování forem jakožto (skoro) invariantní operace, zavedení grad, div, curl a jejich vztah k Stokesově větě. 2. Parametrické vyjádření a rovnice křivek a ploch. Styk křivek a ploch. 3. Oblouk křivky, Frenetův trojhran, křivost a torze prostorové křivky. 4. První a druhá základní forma prostorové plochy, střední a Gaussova křivost, vnitřní geometrie plochy (Gaussova Theorema Egregium). [Stručný popis změn: a) odstraněno: nic, b) novinky: první bod.] ============================================================ Komentář: a) Klíčová slova z rozvahy předaná subkomisi pro mat. analýzu: -- bod 5.2.: základní koncepty množinové topologie (spojitost, kompaktnost) -- bod 5.3.: vytvořující funkce -- bod 5.3.: diskrétní varianty konceptů a postupů matematické a infinitesimální analýzy[Inf] b) Odchylky od rozvahy: -- bod 5.2: základní koncepty geometrické topologie, homotopie, homologie, diskretizace Nevíme kam zařadit v rámci společného základu. Navrhujeme přeřadit do bodu 5.20 jen pro specializaci Obecná matematika, kde bude pokryto předmětem Topologie. Výjimkou je položka "homologie" která by mohla být v předmětu Topologie, nebo ještě lépe v předmětu LAIII, ale nejlépe vyřazena zcela, což je aktuální návrh. -- bod 5.2: kvadriky. V rozvaze informativně pro všechny. V aktuálním návrhu informativně pro specializaci Obecná matematika (v předmětu LAIII). -- bod 5.3: kardinální a ordinální čísla. Domníváme se, že zůstalo v rozvaze omylem a bylo nahrazeno položkou "mohutnost", která je v sylabech předmětu Diskr. matematika. Kardinální a ordinální čísla se učí v nepovinném předmětu Teorie množin. -- bod 5.20(Algebra): klasifikace konečných komutativních grup, symetrické polynomy. Aktualní plán počítá s informativním seznámením pro všechny studenty (v Algebře I). -- bod 5.20(Algebra): univerzální algebra (celá). Aktualní plán počítá s přesunem do navazujícího magisterského studia. c) Připomínky ke státnicovým otázkám: Předložené návrhy počítají s vyřazením podotázek ze schválených státnicových otázek: (D1) Základy univerzální algebry (D7) Kuželosečky a kvadriky a jejich klasifikace. d) Rozdělení tématu "kuželosečky a kvadriky" je třeba dopracovat ve spolupráci s vyučujícími předmětů, které mají téma zmíněné v sylabech (LA II, LA III, Seminář z matematiky II) a předmětů, které znalosti využívají (Optimalizace a některé statistické předměty). Hlavní komplikace je dána nepovinností předmětů LA III a Seminář z matematiky II pro většinu zaměření. e) Předměty LA I a II by měly obsahovat ukázky aplikací. A. Kraus připravila několik námětů, které vyučující lineární algebry může při přípravě kurzů využít. Jedná se o pracovní materiál, který není výstupem práce pracovní skupiny, ale je přiložen, aby nedošlo k jeho zapadnutí. ------------------------------------------------------------------------------ ================================================================================ Příloha: (předběžný nástřel námětů možných aplikací pro předměty Lineární algebra I a II dle A.Kraus) 1. Lineárna regresia ———————————————————— ———————————————————— Idea: …………… Chceme vysvetliť veličinu y pomocou veličín x_1, … x_k; preto n-krát pozorujeme (y, x_1, … x_k). I-te pozorovanie označíme (y_i, x_{i,1}, … x_{i,k}) a nájdeme takú lineárnu kombináciu \hat{y} stĺpcov matice (x_{i,j}), ktorá je najbližšie (y_1, … y_n). Koeficient tejto lineárnej kombinácie pri vektore (x_{1,j}, … x_{n,j}) udáva vplyv x_j na y. Využijeme: ………………………… lineárne zobrazenie, lineárny priestor generovaný stĺpcami matice, súradnice, ortogonálnu projekciu Podrobnejšie ……………………………… V dôkazoch využívame, že ortogonálna projekcia je lineárne zobrazenie dané symetrickou a idempotentnou maticou, ktoré vektoru priradí najbližší vektor z lineárneho obalu stĺpcov projekčnej matice. Hodí sa nám vedieť, že ak je P projekčná matica, potom I-P je projekčná matica na ortogonálny doplnok, t.j. y-Py je projekcia y na ortogonálny doplnok lineárneho obalu stĺpcov P. Tiež sa nám hodí, že postupným projektovaním na vzájomne vnorené podpriestory dostaneme projekciu na ten najmenší podpriestor. Ďalej sa nám hodí, že projekcia na lineárny obal zjednotenia ortogonálnych podpriestorov je súčet projekcií na tieto podpriestory. Hodia sa nám aj vlastnosti projekčných matíc, napr. že stopa je rovná hodnosti, že vlastné čísla sú buď 0 alebo 1. Súvislosti s ďalšími témami z lineárnej algebry ……………………………………………………………………………………………………………………………… - Sústava lineárnych rovníc, kde rovníc je viac než neznámych, je iný pohľad na riešenie lineárnej regresie. - Sústava lineárnych rovníc, kde rovníc je menej než neznámych, sa v lineárnej regresii využije vtedy, keď ju máme takzvane preparametrizvovanú, t.j. ak stĺpce matice (x_{i,j}) sú lineárne závislé. Potom je lineárna kombinácia \hat{y} daná jednoznačne, ale koeficienty pri vektoroch (x_{1,j}, … x_{n,j}) už nie. Používame riešenie pomocou Moore-Penrosovej pseudoinverzie. - Projekčná matica aj Moore-Penrosova pseudoinverzia sa dajú skonštruovať pomocou SVD rozkladu. 2. Metóda najmenších štvorcov ————————————————————————————— ————————————————————————————— Idea: …………… Ak sa nedá n-rozmerný vektor y vyjadriť ako lineárna kombinácia k n-rozmerných vektorov (x_{1,j}, … x_{n,j}), chceme aspoň minimalizovať kvadratickú normu rozdielov r_i = y_i-\sum_{j=1}^k \beta_j x_{i, j}. (Túto metódu využívame v lineárnej regresii, ale má širšie použitie.) Využijeme: ……………………… kvadratická forma, QR rozklad na numericky schodné riešenie 3. Analýza hlavných komponentov ——————————————————————————————— ——————————————————————————————— Idea: …………… Chceme zo znakov x_1, … x_k vyrobiť menší počet znakov tak, že nové znaky budú lineárnymi kombináciami tých starých a touto redukciou dimenzie stratíme čo najmenej informácie. Opäť n-krát pozorujeme (x_1, … x_k) a i-te pozorovanie označíme (x_{i,1}, … x_{i,k}). Z týchto pozorovaní vyjadríme ich variabilitu pomocou výberovej rozptylovej matice a hľadáme ineárne kombinácie u^T x zložiek vektoru x, ktoré zachovajú čo najväčšiu časť tejto variability. Rozptylová matica je symetrická pozitívne semidefinitná matica \Sigma. Rozptyl lineárnej kombinácie u^T x je u^T \Sigma u, i-ta najväčšia hodnota je i-te vlastné číslo a dostaneme ju, ak za ňu dosadíme i-ty vlastný vektor. Využijeme: ………………………… kvadratická forma, spektrálny rozklad 4. a 5. Zhluková a diskriminačná analýza ———————————————————————————————————————— ———————————————————————————————————————— Ide o metódy z data miningu, ktoré využívajú lineárnu algebru. Po očistení od štatistických pojmov možno tieto metódy aj problémy, ktoré riešia, vyznejú trochu neelegantne/vyumelkovane (podobne ako analýza hlavných komponentov), preto by sa asi viac hodilo ich rozoberať až po tom, čo študenti majú základy pravdepodobnosti a štatistiky (od 3. ročníka vyššie). Aplikácie, ktoré sú použiteľné až po tom, čo študenti majú základy pravdepodobnosti a štatistiky ================================================================================================ (od 3. ročníka vyššie) 6. Vlastnosti rozptylových matíc sú užitočné pre získanie intuície o danom rozdelení. Napr. na vysvetlenie degenerovaného mnohorozmerného normálneho rozdelenia môžme použiť, že sa jedná o lineárnu (príp. afinnú) transformáciu nedegenerovaného mnohorozmerného normálneho rozdelenia náhodného vektoru nižšej dimenzie. Matica zobrazenia je \tilde\Sigma taká, že \tilde\Sigma\times(\tilde\Sigma)^T=\Sigma. Dá sa jednoducho zostrojiť pomocou spektrálneho rozkladu. 7. Množiny, na ktorých je hustota n-rozmerného normálneho rozdelenia konštantná, sú n-rozmerné elipsoidy, ktorých hlavné smery a dĺžky hlavných osí sú dané vlastnými vektormi a vlastnými číslami rozptylovej matice. Tam sa využije determinant (je priamo v definícii hustoty), spektrálny rozklad aj elipsoidy. Aj mnohé konfidenčné množiny sú elipsoidy, pretože sú odvodené z mnohorozmerného normálneho rozdelenia. 8. Priestor náhodných veličín s konečným rozptylom je Hilbertov priestor. Podmienená stredná hodnota je projekcia na jeho vhodne zvolený podpriestor.