Alkalmazott algebra előadás

2013-2014. tanév, tavaszi félév


2014. febr. 11.

2014. febr. 18.

2014. febr. 25.

2014. márc. 4.

2014. márc. 11.

2014. márc. 18.

2014. márc. 25.

2014. ápr. 1.

2014. ápr. 8.

2014. ápr. 15.

2014. ápr. 22.

2014. ápr. 29.

2014. máj. 6.

2014. máj. 13.







2014. febr. 11. (100 + 50 perc)

Tárgy tematikájának ismertetése, előfeltételek, tárgy teljesítése, stb.

Csoportok

Csoport fogalma. Példák (többek között): általános lineáris csoportok, szimmetrikus csoportok, alakzatok szimmetria- és mozgáscsoportja, diédercsoportok, kvaterniócsoport. Elem egész kitevős hatványozása csoportban. Multiplikatív és additív írásmód. Csoport ekvivalens definíciói: asszociatív művelet esetén az invertálhatóság ekvivalens az egységelem és inverzelemek létezésével.

A ciklus fogalma. A mozgatott elemek halmaza.

Magasabb lineáris algebra

Konvenciók (jobbról írás, bázisáttérés mátrixa, jelölések Szabó László jegyzete alapján). A Bevezetés a lineáris algebrába tárgyból szükséges legalapvetőbb ismeretek átismétlése.

Emlékeztető: alterek összegének definíciója, U1+...+Uk a legszűkebb olyan altér, amely tartalmazza U1,...,Uk-t. Definíció: A V vektortér az U1,...,Uk altereinek direkt összege, ha V minden eleme egyértelműen előáll U1,...,Uk-beli vektorok összegeként. Tétel: Bármely V véges dimenziós vektortér tetszőleges U1,...,Uk altereire ekvivalensek a következők: (1) a V vektortér az U1,...,Uk altereinek direkt összege; (2) az U1,...,Uk alterek tetszőleges E1,...,Ek bázisaira az utóbbiak összessége bázis V-ben; (3) az U1,...,Uk altereknek van olyan E1,...,Ek bázisa, amelyre az utóbbiak összessége bázis V-ben; (4) V= U1+...+Uk, és tetszőleges i>1 indexre Ui és U1+...+Ui-1 metszete triviális.

2014. febr. 18. (100 + 50 perc)

Az idegen permutációk fogalma, az idegen permutációk felcserélhetők, az idegen permutációk szorzata által mozgatott elemek. Permutációk előállítása páronként idegen ciklusok szorzataként. Példák, szorzás, hatványozás idegen ciklusos alakban. Permutációk előállítása transzpozíciók szorzataként. Tétel a transzpozíciók szorzataként történő előállításban fellépő tényezők számának paritásáról. Páros és páratlan permutáció, a paritás és a műveletek kapcsolata. Az n-edfokú alternáló csoport: An.

Elem rendje és tulajdonságai.

A lineáris transzformációk, illetve négyzetes mátrixok sajátértékeivel, sajátvektoraival és karakterisztikus polinomjával kapcsolatos alapfogalmak és összefüggések átismétlése. Lineáris transzformáció, illetve mátrix sajátaltereinek fogalma. A különböző sajátértékekhez tartozó sajátalterek metszete triviális. Egy vektortér lineáris transzformációjának mátrixa pontosan akkor diagonális egy adott bázisban, ha a bázis a lineáris transzformáció sajátvektoraiból áll. Ebben az esetben a báziselemek közül pontosan annyi tartozik a c sajátértékhez, amennyi a c-hez tartozó sajátaltér dimenziója. Továbbá az egyes sajátértékekhez tartozó báziselemek által generált alterek éppen a megfelelő sajátalterek, és a vektortér előáll a lineáris transzformáció sajátaltereinek direkt összegeként.

Az euklideszi tér fogalma, az Rn euklideszi tér (a standard belső szorzással). Vektorok hossza (v. normája).

2014. febr. 25. (100 + 50 perc)

Részcsoport fogalma, szükséges és elegendő feltétel arra, hogy csoport valamely részhalmaza részcsoport legyen. Részcsoportok metszete részcsoport, részhalmaz által generált részcsoport, csoport generátorrendszere, részhalmaz által generált részcsoport megadása a részhalmaz elemeivel. A ciklikus csoport fogalma, elemei. Ciklikus csoport minden részcsoportja ciklikus, a ciklikus csoportok összes részcsoportja.

Az izomorfizmus fogalma. Példák. A homomorfizmus fogalma, példák. Homomorfizmusok szorzata, izomorfizmusok szorzata és inverze. Csoportok izomorfiája, az izomorfia mint ekvivalenciareláció.

Bunyakovszkij-Cauchy-Schwarz-egyenlőtlenség, nemnulla vektorok szöge, háromszög-egyenlőtlenség, merőleges (v. ortogonális) vektorok; vektor, illetve altér ortogonális komplementuma; ortogonális, illetve ortonormált vektorrendszerek fogalma és lineáris függetlenségük. Minden euklideszi térben van ortonormált bázis. Gram-Schmidt-féle eljárás.

2014. márc. 4. (100 + 50 perc)

Az egységelem és az inverzelemek képe homomorfizmus mellett. Elem és homomorfizmus melletti képének rendje. Homomorfizmus képhalmaza részcsoport. A homomorf kép fogalma. Csoport generátorrendszerének képe a csoport homomorf képének generátorrendszere. Minden ciklikus csoport izomorf Z-vel vagy Zn-nel (n pozitív egész). Permutációcsoportok, Cayley-tétel.

A komplexus fogalma, komplexusok szorzata és inverze. A részcsoportok jellemzése komplexusokkal. A részcsoport szerinti bal és jobb oldali mellékosztály fogalma, a bal, illetve jobb oldali mellékosztályok osztályozást határoznak meg. Szükséges és elegendő feltétel arra, hogy két elem ugyanabba a bal, illetve jobb oldali mellékosztályba essen. Az adott részcsoport szerinti bal és jobb oldali mellékosztályok azonos elemszámúak (számosságúak). Az adott részcsoport szerinti bal oldali mellékosztályozás szerint ugyanannyi mellékosztály van, mint a jobb oldali mellékosztályozás szerint (végtelen csoport esetén csak megemlítve). A részcsoport indexének fogalma. Lagrange-tétel és következményei.

Euklideszi tér minden ortonormált vektorrendszere kiegészíthető ortonormált bázissá. Minden euklideszi tér előáll bármely alterének és ortogonális komplementumának direkt összegeként. Minden n dimenziós euklideszi tér izomorf az Rn euklideszi térrel (standard belső szorzás). Lineáris leképezés adjungáltjának létezése és egyértelműsége, kapcsolat a lineáris leképezés és adjungáltjának mátrixa között adott ortonormált bázisokban.

2014. márc. 11. (100 + 50 perc)

Példa arra, hogy egy részcsoport szerinti bal és jobb oldali mellékosztályozás általában nem esik egybe. Azon részcsoportok jellemzése, amelyek szerinti bal és jobb oldali mellékosztályozás egybeesik, a normálosztó fogalma. Elem és részhalmaz konjugáltjának, ill. részhalmaz konjugálásra való zártságának fogalma. A konjugáltsági reláció. A konjugáltsági osztályok Sn-ben. Normálosztók metszete normálosztó, részhalmaz által generált normálosztó, a generált normálosztó megadása a generátorelemekkel, példa. A kongruencia és a kompatibilis osztályozás fogalma csoportokra, kapcsolatuk, példák. Egy csoport kompatibilis osztályozásai éppen a csoport normálosztó szerinti osztályozásai.

Az önadjungált lineáris transzformáció fogalma. Egy lineáris transzformáció pontosan akkor önadjungált, ha valamely [minden] ortonormált bázisban szimmetrikus a mátrixa. Az ortogonális lineáris transzformáció fogalma: olyan lineáris transzformáció, amely „megőrzi” a normát. Minden ortogonális transzformáció bijektív. Az ortogonális transzformációk jellemzései (a lineáris transzformációk között): „megőrzik” a belső szorzatot, ortonormált vektorrendszert ugyanilyenbe visznek, ortonormált bázist ugyanilyenbe visznek, adjungáltjuk megegyezik az inverzükkel. Az ortogonális transzformációk mátrixának jellemzése ortonormált bázisban. Az ortogonális mátrix fogalma.

2014. márc. 18. (100 + 50 perc)

A faktorcsoport fogalma.

A faktorcsoport a csoport homomorf képe. A csoport-homomorfizmus magjának fogalma. Homomorfizmus magja normálosztó, és egy homomorfizmus pontosan akkor injektív, ha magja triviális. A csoportelméleti homomorfiatétel, példa. Csoport centruma, Inn G izomorf G/Z(G)-vel. Az 1. és 2. izomorfiatétel csoportokra (bizonyítás nélkül), példák.

Az egyszerű csoport fogalma. Az egyszerű Abel-csoportok. Az An csoport egyszerű tetszőleges n>4 esetén (bizonyítás nélkül). A maximális normálosztó fogalma, kapcsolata az egyszerű csoportokkal.

Valós szimmetrikus mátrix karakterisztikus polinomjának minden gyöke valós. Főtengelytétel (lineáris transzformációs alak): Egy V euklideszi tér minden önadjungált lineáris transzformációja esetén van V-nek olyan ortonormált bázisa, amely az önadjungált lineáris transzformáció sajátvektoraiból áll. (Az ilyen bázisban az önadjungált lineáris transzformáció mátrixa diagonális, a főátlóban az önadjungált lineáris transzformáció sajátértékei állnak, mindegyik annyiszor, mint a megfelelő sajátérték multiplicitása a karakterisztikus polinomban.) Főtengelytétel (mátrixos alak): Bármely A valós szimmetrikus mátrixhoz van olyan Q valós ortogonális mátrix, amelyre a D=Q-1AQ mátrix diagonális. (Az ilyen Q mátrixok esetén D főátlójában A sajátértékei állnak, mindegyik annyiszor, mint a megfelelő sajátérték multiplicitása A karakterisztikus polinomjában.) Főtengelytétel (kvadratikus alakokra): Egy V euklideszi téren értelmezett bármely q kvadratikus alakhoz létezik V-nek olyan ortonormált bázisa, amelyben q mátrixa diagonális [azaz amelyben q koordinátás alakja kanonikus]. (A mátrix főátlójában ekkor q bármely ortonormált bázisában felírt mátrixának sajátértékei állnak, mindegyik annyiszor, amennyi a megfelelő sajátérték multiplicitása a karakterisztikus polinomban.) Spektráltétel: Legyen V euklideszi tér, rajta adott egy önadjungált lineáris transzformáció. Ekkor V előáll az önadjungált lineáris transzformáció páronként különböző sajátértékeihez tartozó sajátaltereinek direkt összegeként, és a sajátalterek páronként ortogonálisak. (Dimenziójuk a megfelelő sajátértékek multiplicitása a karakterisztikus polinomban.)

2014. márc. 25. (100 + 50 perc)

(A bizonyítás befejezése.) Az egyszerű csoportok szerepe a véges csoportok elméletében.

Gyűrűk

A gyűrű definíciója, speciális gyűrűk, példák (a korábban tanultak felelevenítése).

A részgyűrű fogalma, jellemzése. Homomorfizmus, izomorfizmus, izomorfia fogalma, alaptulajdonságok, példák.

Az ideál fogalma, jellemzése.

Az invariáns altér fogalma. Adott vektortér és lineáris transzformáció esetén a testelemekkel való szorzás kiterjesztése polinomokkal való szorzásra, számolási tulajdonságok. Az invariáns alterek éppen a polinomokkal való szorzásra zárt alterek. Adott v vektor által generált invariáns altér: <v>. Egy lineáris transzformáció mátrixa adott bázisban pontosan akkor blokkos szerkezetű, ha a blokkokhoz tartozó báziselemek invariáns alteret feszítenek ki, és a vektortér ezen alterek direkt összege.


2014. ápr. 1. (100 + 50 perc)

Részgyűrűk, illetve ideálok metszete részgyűrű, illetve ideál, részhalmaz által generált részgyűrű, illetve ideál, részhalmaz által generált részgyűrű, illetve ideál megadása a részhalmaz elemeivel. A főideál fogalma, főideálok az egységelemes kommutatív gyűrűkben. Az ideál szerinti osztályozás. Egy gyűrű kompatibilis osztályozásai éppen a gyűrű ideál szerinti osztályozásai. A faktorgyűrű fogalma. A természetes homomorfizmus.

Homomorfizmus magja. Homomorfiatétel. Kapcsolat a csoportelméleti homomorfiatétellel.

Az egyszerű gyűrű, ill. a maximális ideál fogalma, kapcsolatuk. Minden test fölötti teljes mátrixgyűrű egyszerű (bizonyítás nélkül). A test fogalma. Az egységelemes kommutatív egyszerű gyűrűk éppen a testek.

Véges dimenziós vektortéren értelmezett lineáris transzformáció minimálpolinomjának fogalma, vektor rendjének fogalma (adott lineáris transzformációra vonatkozóan). Minden vektor rendje osztja a minimálpolinomot. Alaptétel: Legyen V véges dimenziós vektortér a K test felett, melyen rögzítünk egy lineáris transzformációt. Ekkor V olyan <v1>, <v2>, … , <vs> invariáns alterek direkt összege, ahol v rendje K[x]-beli irreducibilis polinom hatványa. Továbbá az ilyen előállításokban fellépő rendek rendszere egyértelműen meghatározott. Speciális bázis megadása a <v> invariáns alterekben.

2014. ápr. 8. (100 + 50 perc)

Egy főideálgyűrű faktortestei éppen az irreducibilis elemek által generált főideálok szerinti faktorgyűrűk. Az egész számok gyűrűjének, ill. a test fölötti polinomgyűrűk faktortestei. Számolás az utóbbi faktortestekben. Véges testek konstrukciója Zp[x] (p prím) faktortesteként.

A résztest, ill. a testbővítés fogalma. Résztestek metszete résztest. A prímtest definíciója. A test fölötti egyhatározatlanú polinomgyűrűk faktortestei mint testbővítések. A karakterisztika definíciója. Test karakterisztikája 0 vagy prímszám. Test prímteste izomorf Q-val vagy Zp-vel (p prím) (bizonyítás nélkül).

A lineáris transzformáció (megszorításának) mátrixa ebben a bázisban. A Jordan-blokk és a Jordan-mátrix fogalma. Tétel (lineáris transzformációs alak): Minden lineáris transzformációhoz létezik olyan bázis a vektortérben, amelyben a lineáris transzformáció mátrixa Jordan-mátrix. Továbbá az ilyen Jordan-mátrix a blokkok sorrendjétől eltekintve egyértelműen meghatározott. Tétel (mátrixos alak): Minden négyzetes mátrix hasonló egy Jordan-mátrixhoz, és ez a Jordan-mátrix a Jordan-blokkok sorrendjétől eltekintve egyértelműen meghatározott. Neve: a mátrix Jordan-féle normálalakja. Példák: Jordan-mátrixok R és C felett. Mátrix karakterisztikus mátrixának fogalma. Hasonló mátrixok karakterisztikus mátrixa megkapható egymásból elemi átalakítások véges sokszori alkalmazásával.

2014. ápr. 15. (100 + 50 perc)

Az algebrai, ill. transzcendens elem fogalma. Elem minimálpolinomjának fogalma, példák. Az egyszerű algebrai testbővítés, a K[x]/(f) test mint egyszerű algebrai bővítés. Egy K test f minimálpolinomú elemmel való egyszerű algebrai bővítése izomorf a K[x]/(f) testtel. A véges fokú testbővítés fogalma, a bővítés fokszáma. Az egyszerű algebrai testbővítés fokszáma megegyezik az adjungált elem minimálpolinomjának fokszámával. A véges fokú testbővítések minden eleme algebrai. A fokszámok szorzástétele (bizonyítás nélkül). Példák.

Minden véges test prímhatvány rendű. A véges testek résztesteinek rendje. A véges testek multiplikatív csoportja ciklikus. Minden véges test izomorf valamely Zp(x)/(f) testtel, ahol p prím és f irreducibilis polinom Zp fölött; sőt, f választható úgy, hogy az x+(f) elem generálja Zp(x)/(f) multiplikatív csoportját. Tetszőleges p prím és n pozitív egész esetén létezik, méghozzá izomorfiától eltekintve egyetlen pn elemű test (bizonyítás nélkül). Továbbá minden p prím és n pozitív egész esetén létezik n-edfokú irreducibilis f polinom Zp fölött, és a pn elemű test izomorf Zp(x)/(f)-fel.

Polinommátrixok, azaz K[x] feletti négyzetes mátrixok elemi átalakításai. A kanonikus diagonális polinommátrix fogalma: a főátlóban lévő d1, d2, ..., dn polinom 0 vagy főpolinom, valamint d1| d2 | ... | dn . Tétel: Minden polinommátrix kanonikus diagonális alakra hozható elemi átalakítások véges sokszori alkalmazásával, és az így kapott kanonikus diagonális alak egyértelműen meghatározott (bizonyítás a köv. előadáson). Következmény: Hasonló mátrixok karakterisztikus mátrixának kanonikus diagonális alakja azonos; így a következőkben mondottak lineáris transzformációkra is átfogalmazhatók. Jordan-mátrix kanonikus diagonális alakja. Négyzetes K feletti mátrix invariáns faktorai és elemi osztói, a mátrix Jordan-normálalakjának kiszámítása. Tétel: Egy mátrix invariáns faktorainak, illetve elemi osztóinak szorzata --- előjeltől eltekintve --- éppen a mátrix karakterisztikus polinomja. Tétel: Egy lineáris transzformáció, illetve mátrix elemi osztóinak legkisebb közös többszöröse (azaz „utolsó” invariáns faktora) éppen a lineáris transzformáció, illetve mátrix minimálpolinomja.

2014. ápr. 22. (100 + 50 perc)

Cayley-Hamilton-tétel: Legyen a fi lineáris transzformáció, illetve A mátrix karakterisztikus polinomja h. Ekkor h(fi)=0 (azaz a triviális lineáris transzformáció), illetve h(A)=0 (azaz a nullmátrix). Példa mátrix Jordan-normálalakjának kiszámítására.

Példa: elem inverzének kiszámolása, illetve elem minimálpolinomjának meghatározása véges testben.

Alkalmazások

Kódolás intuitív fogalma, legfontosabb alkalmazási területek. Példák titkosírásokra, Enigma.

2014. ápr. 29. (0 + 50 perc)

A hibajelző kódolás definíciója. A BCH-kódolás alaptétele. A BCH-kódolások definíciója, hibajelző képessége.


2014. máj. 6. (50 perc: 11.00-11.50 + 50 perc)

Egy tétel a kódtávolság tervezésével kapcsolatban. Példa BCH-kódolásra.

A nyilvános kulcsú titkosítás alapelve, az RSA-titkosítás.

2014. máj. 13. (vizsgadolgozat + 50 perc) 11.00: FÉLÉVKÖZI ÍRÁSBELI VIZSGADOLGOZAT

Miller-Rabin tétele (bizonyítás nélkül), a Miller-Rabin-teszt, példa.



Vissza az elejére