1. előadás Algebrai struktúrák: csoport, gyűrű, test

Számítástudomány

Széchenyi István Egyetem

1. előadás Algebrai struktúrák: csoport, gyűrű, test

Dr. Kallós Gábor

2012–2013 11



Tartalom Műveletek Félcsoport, monoid Csoport Részcsoportok Elem rendje Ciklikus csoportok Kis elemszámú csoportok megadása

Gyűrű Részgyűrű

Nullosztó, integritási tartomány Test Véges testek

Testbővítések Algebrai és transzcendens elemek

Feladatok 2



Műveletek Műveletek és tulajdonságaik Definíció: Legyen H tetszőleges halmaz, és jelölje Hn a H halmaz elemeiből képzett n hosszú sorozatokat. Az f : Hn → H mindenütt értelmezett függvényt n-változós műveletnek nevezzük. Példák Kétváltozós műveletek: egész számok összeadása, kivonása, szorzása f (a, b) = a + b, f (a, b) = a – b, f (a, b) = a ⋅ b (vagy: a ∗ b) Tipikusan infix jelölés, pl. +(a, b) helyett inkább a két elem közé írjuk a műveleti jelet Ha a művelet a ⋅, akkor azt gyakran nem írjuk ki (a ⋅ b helyett ab)

Háromváltozós művelet: vektorok vegyesszorzata Nem művelet: pozitív számok kivonása, f (a, b) = a – b, hiszen ha a ≤ b, akkor nincs értelmezve

Definíció: Egy H halmazon értelmezett kétváltozós műveletet (jelölés: ◦) kommutatívnak nevezünk, ha tetszőleges a, b ∈ H esetén a ◦ b = b ◦ a; asszociatívnak nevezünk, ha tetszőleges a, b, c ∈ H esetén (a ◦ b) ◦ c = a ◦ (b ◦ c) Ha az asszociativitás érvényes, akkor zárójeleket bárhova lehet tenni, vagy bárhol el lehet hagyni. (Ez az állítás teljes indukcióval n-tagú kifejezésekre is igazolható.)

Példák Az egész számok összeadása/szorzása kommutatív és asszociatív Az egész számok kivonása nem kommutatív

Feladat: kommutatív-e a mátrixszorzás? 3



Félcsoport, monoid Definíció: Az S halmazt a rajta értelmezett ◦ művelettel félcsoportnak nevezzük, ha ◦ asszociatív. Ha ◦ kommutatív is, akkor kommutatív (vagy Abel-féle) félcsoportról beszélünk. Példák A pozitív számok az összeadásra/szorzásra nézve (kommutatív) félcsoportot alkotnak Az nxn-es mátrixok a szorzással (nem kommutatív) félcsoportot alkotnak

Definíció: Ha az S félcsoportban van olyan e egységelem, amelyikre igaz, hogy e ◦ a = a ◦ e = a, akkor e-t neutrális elemnek, vagy egységelemnek hívjuk, S-et pedig egységelemes félcsoportnak (monoid) nevezzük Az egységelem jelölése: gyakran 1, összeadás esetén 0 Megkülönböztethető bal- és jobboldali egységelem

Példák (R R, +) a 0 neutrális elemmel monoid (R R+, ⋅) az 1 egységelemmel monoid Az nxn-es mátrixok a szorzás művelettel és az egységmátrixszal monoidot alkotnak (R R+, +) nem monoid

Feladat (Hf.): Keressünk olyan (nemtriviális) struktúrákat, amelyek egy adott struktúrarendszer feltételeit teljesítik, de egy szigorúbbat már nem! (Pl. félcsoport, de nem monoid.) 4



Csoport Definíció: Egy G halmazt a ◦ művelettel csoportnak nevezünk, ha (a ◦ b) ◦ c = a ◦ (b ◦ c), minden a, b, c ∈ G esetén (a művelet asszociatív) ∃ olyan e ∈ G, amelyre a ◦ e (= e ◦ a) = a, ∀ a ∈ G-re (van egységelem) ∀ a ∈ G-re ∃ a' ∈ G úgy, hogy a ◦ a' = a' ◦ a = e (van inverz) Ha a ◦ művelet kommutatív is, akkor kommutatív (vagy Abel-féle) csoportról beszélünk A csoport elemszámát |G|-vel jelöljük, és G rendjének nevezzük Megjegyzések Az a' elemet gyakran a–1-nel jelöljük Az egységelem és az inverz csoportokban egyértelmű (nincs külön bal- és jobboldali)

Példák (R R, +), (Q Q, +), (Z Z, +) a 0 neutrális elemmel Abel-csoport, (N N, +) viszont nem (R R+, ⋅), (Q Q+, ⋅) az 1 egységelemmel Abel-csoport Az nxn-es invertálható mátrixok a szorzás művelettel (nem kommutatív) csoportot alkotnak n elem permutációi (önmagára való bijektív leképezés) csoportot alkotnak a kompozícióra. A csoportot n-ed fokú szimmetrikus csoportnak (Sn) nevezzük, rendje n!. A szabályos n-szög egybevágóságai csoportot alkotnak, ahol a művelet az egymás után való elvégzés. A csoport egységeleme a helybenhagyás, a csoport rendje 2n, ugyanis van n darab tengelyes tükrözés és a helybenhagyással együtt n darab forgatás. Jelölés: Dn (diédercsoport).

Feladat: Igazoljuk, hogy csoport esetén az egységelem és az inverz egyértelmű! 5



Csoport Csoportizomorfizmus, részcsoportok Definíció: A G1 és G2 csoportokat izomorfaknak nevezzük, ha van köztük egy kölcsönösen egyértelmű, művelettartó leképezés, azaz ∃ olyan φ : G1 → G2, amely bijektív, és tetszőleges g, h ∈ G1 esetén φ(g)φ(h) = φ(gh) teljesül Jelölés: G1 x G2 (vagy G1 xφ G2) Példák (R R+, ⋅) x (R R, +), ahol a φ izomorfizmus minden valós számhoz hozzárendeli annak a logaritmusát, azaz φ(a) = log(a). A bijektivitás a logaritmus függvény monotonitásából adódik, a művelettartás pedig a log(ab) = log(a) + log(b) összefüggésből. D3 x S3, azaz a szabályos háromszög egybevágóságainak csoportja izomorf a harmadfokú szimmetrikus csoporttal. A transzformációk: tükrözések a tengelyekre {t1, t2, t3} és forgatások {r, r2, r3 = e}; mindkét csoportnak 6 eleme van.

Definíció: Legyen G csoport. A H ⊆ G részhalmazt részcsoportnak nevezzük, ha H is csoport ugyanarra a műveletre nézve. Jelölés: H ≤ G. Minden csoportnak részcsoportja maga a csoport, és az egységelemet tartalmazó egyelemű halmaz. Ezek a triviális részcsoportok. 6



Csoport Részcsoportok Részcsoport példák (valódi részcsoportok) (R R, +), (Q Q, +), (Z Z, +) D3-nak részcsoportját alkotják a forgatások {r, r2, r3 = e} (r – rotatio) Az nxn-es invertálható mátrixok csoportjának részcsoportja az 1 determinánsú mátrixok Az n-ed fokú szimmetrikus csoportnak (Sn, permutációk) részcsoportját alkotják a páros permutációk (azaz: az inverziók száma bennük páros – részletesen nem tárgyaljuk!) A nem 0 komplex számok a szorzásra nézve csoportot alkotnak. Ennek részcsoportját alkotják az 1 abszolút értékű komplex számok, annak pedig részcsoportját az n-edik egységgyökök. Feladat: Mi a gond itt a 0 elemmel?

A részcsoport tulajdonság ellenőrzéséhez elég megnézni, hogy a, b ∈ H esetén a ◦ b és a–1 is H-beli Az asszociativitás ugyanis biztosan teljesül (öröklődik a csoportból), az egységelem pedig az inverzből megvan

7



Csoport Részcsoportok, elem rendje Állítás: Részcsoportok metszete is részcsoport Definíció: Legyen G csoport, és K ⊆ G (K nem feltétlenül csoport). K által generált részcsoportnak nevezzük és 〈K〉-val jelöljük a legkisebb K-t tartalmazó részcsoportot. (Ez nem más, mint a K-t tartalmazó részcsoportok metszete.) Egy elem által generált részcsoportok Ha a ∈ G, akkor 〈a〉 nyilván tartalmazza a ◦ a-t, a ◦ a ◦ a-t stb. Így értelmezhető an, és érvényes an + k = an ◦ ak, ill. (an)k = ank. Emellett 〈a〉 tartalmazza a–1-et is, és ennek egész kitevős hatványait. Így 〈a〉 = {an | n ∈ Z} Két lehetséges eset: a összes hatványa különböző; Vannak olyan k, l egész számok, hogy ak = al. Ekkor ak – l = 1 (= e, azaz van a-nak olyan hatványa, ami egységelem).

Elem rendje: a legkisebb olyan n szám, amelyre teljesül, hogy an = 1. (Ha nincs ilyen szám: az elem végtelen rendű.) Jelölés: o(a), „ordó a”

8



Csoport Részcsoportok, ciklikus csoportok Állítás: Egy elem rendje megegyezik az általa generált részcsoport rendjével Definíció: Az egy elem által generált csoportokat ciklikus csoportnak nevezzük, és Cn-nel jelöljük Következmény: Minden n > 0 egészre van n elemű csoport Az {1, a, a2, …, an – 1} halmaz a fenti szorzással ilyen (n elemű ciklikus) Példák n elemű ciklikus csoportra n-edik komplex egységgyökök a szorzásra Szabályos n-szög forgatásai Számok összeadása modulo n

Állítás: Azonos rendű ciklikus csoportok izomorfak Állítás: Ciklikus csoport részcsoportja is ciklikus Lagrange tétele: Legyen G véges csoport és H ≤ G. Ekkor H rendje osztja G rendjét. Következmény: Egy elem rendje osztja a csoport rendjét Legyen |G| = p, ahol p prím. Ekkor az egységelemtől különböző csoportelem által generált csoport rendje csak p lehet, azaz: Minden prímrendű csoport ciklikus. (Tétel (véges Abel-csoportok alaptétele): Legyen A véges Abel-csoport. Ekkor A előáll prímhatvány rendű ciklikus csoportok direkt szorzataként. Az előállításban szereplő prímhatványok egyértelműek. Példa: n = 100-ra a felbontások 4⋅25 = 2⋅2⋅25 = 4⋅5⋅5 = 2⋅2⋅5⋅5, így izomorfia erejéig 4 darab 100 elemű csoport létezik.) 9



Csoport Csoportok megadása (kis elemszámokra) Művelettáblázat: Cayley-féle táblázat Definíció: Legyen G = {g1, g2, …, gn} csoport. Ekkor azt az nxn-es táblázatot, amely i-edik sorának jedik oszlopában gi gj áll, a csoport Cayley-táblázatának nevezzük.

1 elemű: csak egy darab van, az egységelemből álló 2 elemű: ha p prím, akkor a p-edrendű csoport ciklikus, ezért 2, 3, 5 és 7 elemű csoport csak egy darab van 4 elemű: izomorfizmus erejéig kettő ilyen van, az egyik C4, a másik az ún. Klein-féle csoport (jelölés: V) Utóbbi izomorf C2  C2-vel C4 a négyzet forgási szimmetriáinak a csoportja, felírható {e, f, f2, f3} alakban

6 elemű: izomorfizmus erejéig kettő ilyen van, az egyik C6 x C2  C3, a másik a D3 x S3 Az első kommutatív, a második nem

8 elemű: izomorfizmus erejéig öt darab ilyen van A kommutatívak: C2  C2  C2, C2  C4 és C8 A nemkommutatívak: D4, a másik pedig a kvaterniócsoport Q = {1, –1, i, j, k, –i, –j, –k}, ahol i2 = j2 = k2 = –1, ij = k, jk = i, ki = j (de: ji = –k)

9 elemű: izomorfizmus erejéig kettő ilyen van C9 és C3  C3 Feladat Jelöljük D4-ben a tükrözéseket rendre h-val (horizontális), v-vel (vertikális), d-vel (dexter, jobb) és s-sel (sinister, bal), a forgatások pedig legyenek {r, r2, r3, r4 = e}. Ekkor D4-ben részcsoportok: {r, r2, r3, e}, {r2, h, v, e} és { r2, d, s, e}. Utóbbiak izomorfak egymással és a Klein-csoporttal.

10



Gyűrű Meghatározás Definíció: (R, +, ⋅) gyűrű, ha (R, +) Abel-féle csoport, (R, ⋅) félcsoport, és teljesül a jobb- és baloldali disztributivitási törvény Azaz másként a + b = b + a, ∀ a, b ∈ R esetén (i) (a + b) + c = a + (b + c), ∀ a, b, c ∈ R esetén (ii) ∃ olyan R-beli elem (jelöljük 0-val), amelyre a + 0 = 0 + a = a, ∀ a ∈ R-re (iii) ∀ a ∈ R-re ∃ a' ∈ R úgy, hogy a + a' = 0 (iv) (a ⋅ b) ⋅ c = a ⋅ (b ⋅ c), ∀ a, b, c ∈ R esetén (v) (a + b) ⋅ c = a ⋅ b + b ⋅ c, ∀ a, b, c ∈ R esetén (vi) c ⋅ (a + b) = c ⋅ a + c ⋅ b, ∀ a, b, c ∈ R esetén (vii) Megjegyzések Ha a szorzás is kommutatív, akkor kommutatív gyűrűről beszélünk Ha van a szorzásra nézve egységelem, akkor egységelemes gyűrűről beszélünk (iii)-ben: nullelem (iv)-ben: ellentett (a + műveletre), –a Kivonás művelet: a + (–b) = a – b A gyűrű megnevezést önmagában R-re is használjuk A ⋅ műveletet gyakran itt sem írjuk ki (elég ab)

11



Gyűrű Állítás: Egy gyűrűben teljesülnek azok a műveleti tulajdonságok, amelyeket elvárunk, azaz ha R gyűrű és a, b ∈ R, akkor a nullelem és az ellentett egyértelmű, 0a = a0 = 0, (–a)b = –ab és (–a)(–b) = ab. Példák (Z Z, +, ⋅) kommutatív, egységelemes gyűrű; hasonlóan Q, R, és C is Az m-mel osztható egész számok kommutatív gyűrűt alkotnak a szokásos műveletekre Jelölés: m⋅Z Z

Az nxn-es mátrixok (lehet: komplex, valós, racionális, egész) nemkommutatív gyűrűt alkotnak a mátrixösszeadásra és a szorzásra. Az egységelem az egységmátrix. A komplex (lehet még: valós, racionális, egész) együtthatós polinomok gyűrűt alkotnak a polinomösszeadásra és a szorzásra. Jelölés: C[x] (illetve R[x], Q[x], Z[x]). A valós függvények gyűrűt alkotnak az (f + g)(x) = f(x) + g(x) és (f ⋅ g)(x) = f(x) ⋅ 2 g(x) műveletekkel Változat: az [a, b] intervallumon értelmezett, és a folytonos függvényekre is igaz a kijelentés

12



Nullosztó, integritási tartomány Definíció: Legyen R gyűrű. Az a (≠ 0) ∈ R elemet baloldali (jobboldali) nullosztónak nevezzük, ha van hozzá olyan b (≠ 0) ∈ R, hogy ab = 0 (ba = 0). Egy gyűrűben pontosan akkor van baloldali nullosztó, ha van jobboldali is

Az R gyűrűt nullosztómentesnek nevezzük, ha nincs benne nullosztó. A kommutatív nullosztómentes gyűrű neve integritási tartomány. Azaz: a ⋅ b = 0 ⇒ a = 0 vagy b = 0, ∀ a, b ∈ R esetén

Ekvivalens definíció: Az integritási tartomány egy olyan kommutatív gyűrű, amelyben teljesül az egyszerűsítési szabály, azaz a ⋅ b = a ⋅ c és a ≠ 0 ⇒ b = c és ∀ a, b, c ∈ R esetén Példák Z és 2⋅Z Z integritási tartomány Z6-ban 2⋅3 = 0, ezért a 2, ill. a 3 nullosztók. Általánosan is igaz, hogy ha m nem prím, akkor Zm-ben található nullosztó. A Gauss-egészek, valamint Z ( − 5 )integritási tartomány Egy nxn-es A mátrix baloldali nullosztó, ha az A ⋅ B = 0 mátrixegyenletnek van 0-tól különböző megoldása, azaz ha A nem invertálható (az A ⋅ x = 0 lineáris egyenletrendszernek van nemtriviális megoldása). Ugyanezzel ekvivalens az, hogy A jobboldali nullosztó.

Feladatok Adjuk meg az összes nullosztót Z8-ban és Z10-ben! Adjunk meg olyan m-et, hogy Zm-ben csak pontosan egy nullosztó legyen! 13



Részgyűrű Definíció: Legyen R gyűrű. Az R' ⊆ R részhalmazt az R részgyűrűjének nevezzük, ha R' is gyűrű ugyanazokra a műveletekre nézve. Jelölés: R' ≤ R. R és {0} mindig részgyűrűk, ezeket triviális, az ettől eltérő részgyűrűket pedig valódi részgyűrűknek nevezzük Állítás: Legyen R gyűrű. Az R' ⊆ R részhalmaz az R részgyűrűje, ha zárt a műveletekre, és minden elemmel együtt benne van annak ellentettje is. Példák Az egész számok részgyűrűjét alkotják az m-mel osztható egész számok (m⋅Z Z) Q részgyűrűje R-nek, R pedig részgyűrűje C-nek Az nxn-es mátrixoknak (lehet: komplex, valós, racionális, egész) részgyűrűjét alkotják azok a mátrixok, amelyeknek az utolsó sora és az utolsó oszlopa 0

Állítás: Z minden részgyűrűje megkapható m⋅Z Z alakban Bizonyítás: Legyen R ≤ Z és R ≠ {0}. Ekkor R-ben van pozitív elem, legyen a legkisebb ilyen m. Megmutatjuk, hogy R az m többszöröseiből áll. Válasszunk egy tetszőleges s ∈ R elemet. Találhatók olyan q és r számok, hogy s = qm + r. Mivel m volt a legkisebb pozitív elem, ezért csak r = 0 lehet. 14



Test Definíció: Egy R egységelemes gyűrűt ferdetestnek nevezünk, ha a szorzásra nézve is van inverz, azaz ∀ 0 ≠ a ∈ R-hez ∃ a' ∈ R úgy, hogy aa' = 1 Egy ferdetestet testnek nevezünk, ha a szorzás is kommutatív Gyakran a ferdetestet hívják testnek, a testet pedig kommutatív testnek

Állítás: A ferdetest nullosztómentes Feladat: Igazoljuk az állítást!

Példák Q, R és C testet alkotnak a szokásos műveletekre Z2 test. Igazolás: Az elemek {n0, n1} = {0, 1}, elég ellenőrizni, hogy 1-nek van inverze; ez pedig 1 ⋅ 1 = 1 miatt önmaga. Z5 test. Igazolás: Az elemek {n0, n1, n2, n3, n4} = {0, 1, 2, 3, 4}, elég ellenőrizni, hogy az 1, 2, 3 és 4 elemeknek van inverze. Itt 1 ⋅ 1 = 1, 2 ⋅ 3 = 6 = 1, 4 ⋅ 4 = 16 = 1, azaz az 1 és 4 inverze önmaga, a 2 és 3 pedig egymás inverzei. Azok a speciális 2x2-es mátrixok, ahol A1, 1 = a, A1, 2 = b, A2, 1 = –b, A2, 2 = a, testet alkotnak a mátrixműveletekre A valós számtest feletti racionális törtfüggvények halmaza testet alkot a szokásos műveletekre Q d test, ahol d négyzetmentes szám. (Igazolni kell, hogy a struktúra gyűrű, és van multiplikatív inverz, …)

( )

15



Test Példák (folyt.): A kvaterniók ferdetestet alkotnak Elemek: a + bi + cj + dk alakú számok, ahol a, b, c, d ∈ R Az összeadás az elemenkénti összeadás, az i, j, k elemek pedig úgy szorzódnak, mint a kvaterniócsoportban Ferdetest tulajdonság: például ij ≠ ji (Nem igaz az sem, hogy itt egy n-edfokú polinomnak legfeljebb n gyöke lehet; példa: x2 + 1 polinom, ennek gyöke minden bi + cj + dk alakú szám, ahol b2 + c2 + d2 = 1, tehát végtelen sok gyöke van)

Tétel (Frobenius): Legyen K a valós számokat tartalmazó ferdetest. Ekkor K izomorf a komplex számok vagy a kvaterniók valamelyikével. Azaz a fentieken túl nem lehet más, valós számokat tartalmazó (ferde)testet szerkeszteni

Állítás: Minden véges integritási tartomány test Bizonyítás (ötlet): Meg kell mutatni az egységelem és a rá vonatkozó inverz létét

Következmény: Zm pontosan akkor test, ha m prím Bizonyítás: Zm akkor nullosztómentes, ha a, b ∈ Zm esetén ab = 0-ból a = 0 vagy b = 0 következik, azaz m | ab esetén m | a vagy m | b. Ez pont a prímtulajdonság.

A Zp gyűrűt, ha testként gondolunk rá, Fp-vel is jelöljük 16



Testbővítések Definíció: Legyenek L ≤ K testek. L-et K résztestének, K-t L bővítésének nevezzük. A K | L párt testbővítésnek nevezzük. K vektortér L felett. A K test L feletti dimenzióját (dimL(K)) a testbővítés fokának hívjuk, és |K : L|-lel jelöljük. Ha ez véges, akkor véges bővítésről beszélünk. Vektortér meghatározása…

Tétel (fokszámok szorzástétele): Legyenek K ⊆ L ⊆ M. Ekkor |M : K| = |M : L|⋅|L : K|. Példák A C | R pár véges testbővítés, foka 2, C = R(i) (Itt: C és R között nincs további test) Q d | Q másodfokú bővítése Q-nak Az R(x) | R pár végtelen bővítés. Az x, x2, …, xn, … elemek lineárisan függetlenek R felett. Az R | Q bővítés is végtelen

( )

Kérdés: mit tudunk mondani a Q | Z bővítésről?

A triviális résztest és a valódi résztest a korábbiakhoz hasonlóan értelmezhető Definíció: Egy testet prímtestnek nevezünk, ha nincs valódi részteste Tétel: Minden test tartalmaz prímtestet. Q és Fp prímtestek. Más prímtest nincs. Az igazolás két ágon fut le aszerint, hogy az 1 + 1 + 1 + … összeg lehet-e 0 (ha nem: 0 karakterisztikájú a test)

17



Testbővítések Állítás: Legyen K véges test. Ekkor K elemszáma prímhatvány. Jelölés (gyakran): GF(pn), ahol GF a Galois Field rövidítése Igaz továbbá az is, hogy minden q prímhatványra létezik olyan elemszámú véges test

Megj.: A véges testek fontos szerephez jutnak a kódelméletben és kriptográfiában. Ezzel még később foglalkozunk. Feladatok Melyik a legegyszerűbb véges test? Adjuk meg az elemeket, az összeadó és a szorzótáblát! Adjuk meg Z5-ben az elemek összeadási és szorzási tábláját. Ellenőrizzük a táblázat segítségével (is) az inverzek létezését! Adjuk meg Z6-ban az elemek összeadási és szorzási tábláját. A nullosztók bemutatásával szemléltessük így is, hogy a struktúra nem test.

Definíció: Legyen L | K testbővítés, és a ∈ L. Az a elemet algebrai elemnek nevezzük (K felett), ha van olyan f ∈ K[x] polinom, amelyre f ≠ 0 és f(a) = 0. Ha nincs ilyen polinom, akkor az elemet transzcendens elemnek nevezzük. A L | K bővítés algebrai, ha L minden eleme algebrai K felett. Példák Az R | Q testbővítésben a 2013 2012 és a 2 + 1 elemek algebraiak, hiszen gyökei az f(x) = x2013 – 2012 illetve a g(x) = x2 – 2x – 1 polinomoknak. Ugyanakkor e és pi transzcendens elemek (ezt nem könnyű igazolni). R | Q tehát nem algebrai bővítés.

18



Testbővítések Példák (folyt.) A C | R bővítés algebrai, hiszen z ∈ C esetén z gyöke az f(x) = x2 – (z + z')x + z⋅z' valós együtthatós polinomnak (ahol z' a z konjugáltja)

Állítás: Minden véges testbővítés algebrai Az állítás az előző példa általánosításaként igazolható. Legyen dimK(L) = n, és a ∈ L. Ekkor az 1, a, a2, …, an elemek lineárisan összefüggőek K felett, így vannak olyan αi ∈ K elemek, hogy Ʃin αi ai = 0. Ekkor tehát a gyöke az f(x) = Ʃin αi ai polinomnak.

Állítás: GF(pn) egy GF(p) felett irreducibilis n-edfokú polinom segítségével konstruálható Állítás: Algebrai bővítés algebrai bővítése is algebrai Következmény: Legyenek α, β algebraiak a K test felett. Ekkor α + β, α – β, αβ, α/β is algebrai K felett. A K felett algebrai számok testet alkotnak. Az állítás jelentőségét az adja, hogy – noha nem minden esetben könnyű megfelelő polinomot megadni – egy-egy ilyen szám esetén mégis nyilvánvaló, hogy algebrai

Tétel: Legyen K egy 0 karakterisztikájú test, L | K véges testbővítés. Ekkor L előáll egyetlen elem hozzáadásával (adjungálásával) K-ból, azaz minden véges testbővítés egyszerű.

19



Feladatok, gyakorlat Excel (Calc), Maple vagy Matlab programban nézzük meg, hogy az nxn-es mátrixok… Összeadása és szorzása elvégezhető (és a struktúra zárt); A szorzás – általában – nem kommutatív; Létezik egységelem; Létezik inverz (szorzásra: ha a determináns nem 0).

(Változat: Papíron nézzük meg 2x2-es mátrixokra.) Tudjuk, hogy az nxn-es mátrixok a szorzással félcsoportot alkotnak, tehát a művelet asszociatív. Következik ebből, hogy egy gépi szorzásnál mindegy, hogy hogyan zárójelezünk? Végezzünk hatékonysági számítást, példa: C-L-R könyv, dinamikus programozásos feladat !

Állítsuk elő a komplex n-edik egységgyököket Maple-ben! A Maple hatékony támogatást nyújt a véges testekben való számoláshoz (GF külső könyvtár, lásd a mellékelt munkalapon). Írjunk kis programot, amely előállítja GF(pn)ben a testelemek összegét és szorzatát! Elemezzük a struktúrát GF(3), GF(5), GF(7), illetve GF(4) és GF(9) esetén!

Elemezzük a gépi aritmetika sajátosságait! Mindig kommutatív és asszociatív a gépi számolás? Határozzuk meg a gépi epszilon értékét különböző környezetekben (pl. Excel, Calc)!

Jellemezzük Q ( 2 , 3 ) elemeit! Milyen alakba írhatók? Melyik lehet az az egyetlen elem, amelynek adjungálásával előáll a struktúra Q-ból? Mennyi a bővítés foka Q felett? 20



Gyakorlat – nxn-es mátrixok vizsgálata

21




22




23




24




25




26




27



Gyakorlat – véges test konstrukció

28




29




30



Gyakorlat – gépi epszilon

31



Ajánlott irodalom Katona Gyula, Recski András, Szabó Csaba: A számítástudomány alapjai, Typotex Kiadó, Budapest, 2003 Molnárka Győző és társai: Bevezetés a MapleV használatába, Springer, Budapest, 1996 Hujter Mihály: Betekintés a Matlab programrendszerbe, elektronikus segédanyag Cormen, Leiserson, Rivest: Algoritmusok, Műszaki Kiadó, Budapest, 2000 (több kiadás)

32

1. előadás Algebrai struktúrák: csoport, gyűrű, test

Recommend Documents