Libor Barto

DOMU VYZKUM PRO STUDENTY

ARCHIV 09/10 letni semestr

[Zpet]

LINEARNI ALGEBRA A GEOMETRIE II (NALG002)

Streda 12:20 M1, Ctvrtek 14:00 M1

Terminy zkousek jiz jsou v SISu. Zkousky budou vzdy od 9:00, 9:00-10:00 bude pocetni pisemka, cca 10:10-11:10 teoreticka. Pozadavky = latka probrana na prednaskach (nize je shrnuti prednasek). Pro uspesne zvladnuti zkousky je nutne dobre rozumet definicim a tvrzenim, pro lepsi znamku je treba znat i slozitejsi dukazy. Na zkousku je nutne mit zapocet! Na zkousku musite jit k prednasejicimu, ke kteremu patrite (podle SISu).

Strucny obsah prednasek:

24.2. a 25.2. Pripomenuti z minuleho semestru - souradnice vektoru v vzhledem k bazi (znacime [v]_B), matice homomorfismu f vzhledem k bazim B a C (znacime [f]_B,C), matice prechodu od baze B k bazi C (znacime [id]_C,B), souradnice linearni formy f vzhledem k B (znacime [f]_B) + k cemu to je.
Bilinearni formy - definice, jak vypadaji - analyticke vyjadreni a matice BF vzhledem k nejake bazi (znacime [f]_B, kde f je BF a B je baze). Zmena matice BF pri prechodu k jine bazi.
Operace s BF (scitani a nasobeni skalarem). Rozklad BF na symetrickou a antisymetrickou. Kvadratike formy (jsou jednoznacne urcene symetrickou casti BF). Linearni formy f(u,_) a f(_,u), kde u je pevny vektor, jejich souradnice.
3.3. a 4.3. Levy a pravy vrchol BF, jejich vypocet, nulita a hodnost. Polarni baze symetricke BF (existuje, pokud charakteristika telesa neni 2). Metoda I - postupne bereme vektory, aby hodnota prislusne kvadraticke formy byla nenulova, dokud to jde; zbytek je vrchol. Metoda I* - napred urcime vrchol, pak polarni bazi restrikce na doplnek (tam je regularni). Polarni baze maticove - k dane matici A hledame R aby R^TAR byla diagonalni. Metoda II - symetricke upravy. Tady je textik o polarni bazi BF (bohuzel obsahuje dost chyb, ktere neumim opravit, protoze jsem nekde propil zdrojak).
10.3. a 11.3. Priklad na urceni tvaru a stredu kvadraticko-linearniho utvaru v rovine. Metoda III na hledani polarni baze f - explicitni vzorecek pomoci algebraicky doplnku, pokud jsou hlavni subdeterminanty [f]_B nenulove. Sylvesteruv zakon setrvacnosti, signatura symetrickych BF nad R, vypocet signatury. Pozitivne (negativne) (semi)definitni sym. BF, charakterizace pozitivne (negativne) definitnich sym. BF pomoci hlavnich subdeterminantu (Sylvesterovo kriterium).
17.3. a 18.3. Skalarni soucin na realnem v.p. (=pozitivne definitni symetricka BF), infixova notace (u.v, misto f(u,v)). Priklady - standardni skalarni soucin na R^n, ostatni skalarni souciny na R^n, skalarni soucin na prostoru spojitych funkci na intervalu (f.g je integral jejich soucinu). Pozitivne definitni matice = Q^TQ pro regularni Q. Norma (velikost), vzdalenost, jednoduche vlastnosti (napr. rovnobeznikove pravidlo). Cauchy-Schwartzova nerovnost, trojuhelnikova nerovnost. Odbocka - definice normovaneho linearniho prostoru a metrickeho prostoru; UP -> NLP -> MP. Kolme (ortogonalni) vektory, velikost uhlu, vlastnosti (napr. kosinova veta, Pythagorova veta), velikost uhlu v R^2 se standardnim sk. soucinem odpovida definici pres jednotkovou kruznici. Ortogonalni a ortonormalni mnoziny a baze. Kolmost dvou mnozin, ortogonalni doplnek, vlastnosti, vypocet (vzhledem k ON bazi). Rozklad prostoru na podprostor (konecne dimenze) a jeho doplnek. Ortogonalni projekce (nejlepsi aproximace) a kolmice (chyba) vektoru na podprostor, vypocet pomoci Gramovy matice.
24.3. Ortogonalni projekce aplikovana na nejlepsi priblizne reseni SLR - nejlepsi priblizna reseni (A|b^T) jsou prave presna reseni (A^TA|A^Tb^T). Ortogonalni projekce na podprostor, zname-li jeho OG bazi, Fourierovy koeficienty, dusledky (vyjadreni vektoru vzhledem k OG bazi, Besselova nerovnost, Parcevalova rovnost). Gram-Schmidtova ortogonalizace.
31.3. a 1.4. Ortogonalni matice, QR-rozklad (pro ctvercove regularni matice). Unitarni zobrazeni a zakladni vlastnosti (zachovava normy, uhly, vzdalenosti, je to monomorfismus), matice unitarniho zobrazeni vzhledem k ON bazim, matice prechodu od ON baze k ON bazi je ortogonalni. Vektorovy soucin na prostorech dimenze 3 (vzhledem k dane ON bazi), trojny soucin, smer a velikost vektoroveho soucinu, zmena vektoroveho soucinu pri zmene ON baze. Rychly prehled seskvilinearnich, hermitovskych forem, skalarni soucin nad C (=pozitivne definitni hermitovska seskvilinearni forma).
7.4. a 8.4. Co budeme dal delat - zkraslovat endomorfismy (predtim jsme zkraslovali sym. BF, viz polarni baze). Pripomenuti: matice endomorfismu vzhledem k bazi B (znacime [f]_B), chovani pri zmene baze. Zavedeni znaceni f_A pro homomorfismus x -> Ax (vektory ve sloupcich). Motivace - explicitni vzorec pro Fibonacciho posloupnost, bez podvodu. Vlastni cisla a vektory endomorfismu a matic. Metoda na jejich pocitani. Charakteristicky polynom, algebraicka nasobnost vl. cisla, spektrum matice. Podobne matice, maji stejny char. polynom. Charakteristicky polynom, alg. nasobnost, spektrum pro endomorfismus. Vlastni vektory prislusne ruznym vlastnim cislum jsou LN. Geometricka nasobnost (dimenze prostoru tvoreneho vlastnimi vektory k danemu cislu + 0) je mensi nebo rovna algebraicke nasobnosti. Definice diagonalizovatelneho endomorfismu a diagonalizovatelne matice. Charakterizace diagonalizovatelnych endomorfismu (resp. matic) - f diag <=> ex. baze z vlastnich vektoru <=> n vlastnich cisel (s nasobnostmi) + geom.nasobnost = alg.nasobnost; cast dukazu.
14.4. a 15.4. Dokonceni dukazu charakterizace diagonalizovatelnych endomorfismu (matic), algoritmus, priklad. Priklad pouziti diagonalizovaneho tvaru - vypocet mocnin matice i slozitejsich vyrazu (exponenciela, sinus, ...). Symetricke realne matice jsou ortogonalne diagonalizovatelne (a naopak), algoritmus, vypocet. (Zmineny normalni matice nad C = unitarne diagonalizovatelne.) Dusledek - symetricke BF na realnem unitarnim prostoru maji ON polarni bazi - pozname jak presne vypada kvadraticky utvar, priklad. Polynomy nad telesem, delitelnost, asociovanost, deleni se zbytkem, NSD.
21.4. a 22.4. Bezoutovy koeficienty, priklad nad Z. Jordanova bunka, Jordanova matice, formulace vety o Jordanove kanonickem tvaru: matice A typu n x n ma JKT (tj. A je podobna Jordanove matici) <=> A ma n vlastnich cisel vc. nasobnosti; navic JKT je urcen jednoznacne az na poradi bunek, na diagonale jsou vlastni cisla (kazde tolikrat kolik je jeho alg. nasobnost), pocet bunek prislusnych danemu cislu = geom. nasobnost. Dukaz snadne implikace (=>). Priklady na rozpoznani JKT pomoci alg. a geom. nasobnosti (do dimenze 3 to jeste vzdy jde, od dimenze 4 uz ne vzdy). Plan dukazu obtiznejsi implikace - 1. kazda \lambda-matice je ekvivalentni kanonicke \lambda-matici, 2. tento kanonicky tvar je urcen jednoznacne, 3. A- \lambda E je ekvivalentni B - \lambda E <=> A a B jsou podobne, 4. vypocet kanonickeho tvaru Jordanovych matic.
Krok 1.: \lambda-matice (lze chapat tez jako polynom s maticovymi koeficienty), invertibilni matice + charakterizace (invertibilni <=> determinant je nenulovy prvek telesa), ekvivalentni matice (jedna lze ziskat z druhe pronasobenim invertibilni matici zprava a invertibilni matici zleva), elementarni upravy \lambda-matic, po uprave ziskame ekvivalentni matici. Kanonicky tvar \lambda-matice (diagonalni, polynomy na diagonale se postupne deli a jsou normovane), kazda \lambda-matice je ekvivalentni nejake kanonicke.
Krok 2.: Jednoznacnost kanonickeho tvaru - naznak dukazu (pres NSD vsech subdterminantu), invariantni faktory.
Krok 4.: Vypocet invariantnich faktoru Jordanovy matice - posledni "popisuje" nejvetsi bunky pro vsechna ruzna cisla na diagonale, predposledni druhe nejvetsi, atd., priklady.
Krok 3.: Tvrzeni o deleni \lambda-matice \lambda-matici (A - \lambda E).
28.4. a 29.4. Dokonceni kroku 3.: A a B jsou podobne <=> A-\lambda E je ekvivalentni B - \lambda E (<=> matice A-\lambda E, B-\lambda E maji stejne invariantni faktory).
Determinant je +- soucin invariantnich faktoru. Dukaz vety o JKT, postup, priklad. Metoda nalezeni matice X, ze X^{-1}AX = J (pro endomorfismy: nalezeni baze B, ze [f]_B=J) - retizky vektoru, priklad. Priklad na reseni soustavy linearnich diferencialnich rovnic.
Dosazeni matice do polynomu. Hamilton-Cayleyova veta (kdyz dosadim A do char. pol., vyjde 0; dokonce dosadim-li do posledniho invariantniho faktoru vyjde 0, ukazka), vyuziti (pocitani inverzni matice, mocnin).
Afinni a eukleidovske prostory - motivace, definice, priklady, jednoduche vlastnosti.
5.5. a 6.5. Podprostory afinnich prostoru, charakterizace (mnoziny tvaru b+W). Soustava souradnic v afinnim prostoru, kartezka s.s. v eukleidovskem prostoru, souradnice bodu a vektoru vzhledem k dane soustave, prechodove vztahy mezi soustavami souradnic, priklad. Parametricke a rovnicove vyjadreni podprostoru, prechod mezi nimi, priklad, normalovy prostor (pro eukleidovske prostory). Vzajemna poloha podprostoru (rovnobezne, ruznobezne, mimobezne), kriteria na urceni vzajemne polohy pomoci dimenzi, popis pruniku, priklad na urceni pruniku podprostoru. Afinni zobrazeni, unitarni afinni zobrazeni. Tady je textik o afinnich a eukleidovskych prostorech (bohuzel opet obsahuje dost chyb a nepresnosti, opet neumim opravit; rovnez znaceni se trochu lisi od prednasky).
13.5. Delici pomer, charakterizace afinnich zobrazeni jako zobrazeni zachovavajici delici pomer. Charakterizace unitarnich afinnich zobrazeni jako zobrazeni zachovavjici vzdalenosti. Projektivni prostor.
19.5. a 20.5. Prestava projektivniho prostoru P(T^{n+1}) jako rozsireni afinniho prostoru T^n o "nevlastni body". Podprostory projektivniho prostoru, Fannova rovina. Kvadriky, studium "kvadratickych utvaru" v afinnich prostorech pomoci kvadrik. Polarni a tecna nadrovina, vypocet tecen v bode a z bodu.

ODKAZY

POCITACOVA ALGEBRA (NMIB003)

Ctvrtek 8:10 K2, Ctvrtek 16:15!!! K2

Informace k prednasce i cviceni jsou na strankach Davida Stanovskeho.

25.2. Skolske algoritmy pro pocitani s prirozenymi cisly (scitani, odcitani, nasobeni, deleni se zbytkem, prevod mezi bazemi) a vypocet jejich slozitosti. Metoda rozdel a panuj pro nasobeni prirozenych cisel (Karatsubovo nasobeni - slozitost O(n^{1.58}), algoritmus se slozitosti O(n^{1.46})).
4.3. Mocneni, binarni mocneni, pouziti na pocitani mocniny modulo Z_m. Eukleiduv algoritmus na NSD, odhad poctu kroku (hrubsi odhad jako cviceni), odhad velikosti koeficientu, vypocet slozitosti. Binarni NSD. Zakladni operace v Q a Z_p.
11.3. Husta a ridka reprezentace polynomu, distributivni a rekurzivni forma pro polynomy vice promennych. Realny a zjednoduseny model slozitosti. Zakladni operace s polynomy (+, *, div, mod) a slozitosti v obou modelech, NSD, Hornerovo schema. Operace v konecnych telesech a rozsireni Q. Zobecnena Cinska veta o zbytcich (specialni pripady - Cinska veta o zbytcich, veta o interpolaci).
18.3. Prevod do modularni reprezentace (v Z a T[x]), Lagrangeuv a Garneruv algoritmus na prevod z modularni reprezentace (v Z a T[x]), slozitost. Prevod z modularni reprezentace v T[x] naivnim pristupem - reseni soustavy rovnic s Vandermondovou matici. Shamirovo (k,n)-schema na sdileni tajemstvi.
25.3. DFT, IDFT pomoci DFT, FFT - slozitost O(n log n).
1.4. Nerekurzivni verze FFT. Primitivni odmocniny z jedne v Z_p, C, FFT-prvocisla. Rychle nasobeni polynomu, zejmena v Z. Formalni mocnine a Laurentovy rady. Rychle deleni polynomu - prevod na nasobeni a invertovani mocninne rady. Rychle invertovani mocninne rady, n-clenu lze vypocitat v case O(n log n).
8.4. Vylet do numericke matematiky - metody hledani korenu rovnic. Puleni intervalu, regula falsi. Newtonova metoda (metoda tecen), konvergence radu 2 (pro hezke fce). Metoda secen.
15.4. Pseudodeleni, posloupnost polynomialnich zbytku (PRS), eukleidovska, primitivni, redukovana a subrezultantova PRS. Kriterium na soudelnost polynomu. Sylvesterova matice, rezultant, sylvesterovo kriterium. Rezultant vyjadreny pomoci korenu (v alg. uzaveru). Vyjadreni resultantu jako kombinace danych polynomu. Subrezultanty, fundamentalni veta o PRS (bez dukazu). Gaussova veta, pocitani NSD v R[x], kde R je Gaussuv.
22.4. Modularni algoritmus na vypocet NSD v Z[x] - pouzitelna, stastna prvocisla, smolnych prvocisel je malo (deli jisty rezultant), Landau-Mignottova mez, problem vedouciho koeficientu, zjednoduseny modularni algoritmus, modularni algoritmus, odhad slozitosti. Modularni algoritmus v R[x,y] - pouzitelne, stastne hodnoty, atd..
29.4. Faktorizace polynomu - plan. Bezctvercova faktorizace nad okruhy charakteristiky 0 a nad konecnymi telesy. Zakladni tvrzeni potrebne k Berlekampovu algorimu.
6.5. Berlekampuv algoritmus, slozitost, priklad polynomu, ktery se rozklada v kazdem Z_p, ale nerozklada se v Z (Q). Rozklad v Z[x] - strategie, pomocne tvrzeni k Henselove liftovani.
13.5. Henselovo liftovani, rozklad primitivnich celociselnych polynomu - bezctvercovy rozklad, Berlekamp, Hensel, kombinace faktoru (Zassenhaus).
20.5. Faktorizace polynomu vice promennych - Kroneckeruv algoritmus, zobecnena veta o liftovani a aplikace: Henselovo lemma, faktorizace, reseni soustav rovnic nad Z.

KAFKA (ALG080)

Streda 15:40 seminarni mistnost KA

SEMINAR K PROBLEMU CSP (NALG118)

Pondeli 13:30 laborator KA

SEMINAR Z TEORIE KROTKYCH KONGRUENCI (NALG123)

Streda 17:20 laborator KA

ODKAZY

  • D. Hobby, R. McKenzie, The Structure of Finite Algebras [download]
  • M. Clasen, M. Valeriote, Tame Congruence Theory [PS]
  • A course in TCT

RUZNE

Text Petara Markovice z prednasky o konecne bazovanosti rovnicovych teorii jsou [Zde] (verze z 28.4.2008).

ARCHIV

[Archiv 2009/10 zimni semestr]
[Archiv 2008/09 letni semestr]
[Archiv 2008/09 zimni semestr]
[Archiv 2007/08 letni semestr]
[Archiv 2007/08 zimni semestr]
[Archiv 2006/07 letni semestr]
[Archiv 2006/07 zimni semestr]
[Archiv 2005/06 letni semestr]