Számítástudomány matematikai alapjai segédlet táv és levelez˝o Horváth Árpád 2010. június 18. A segédletek egy része az http://elearning.bmf.hu oldal Számítástudomány kurzusában található, de esetleg a matek honlapon is érdemes végignézni: http://www.roik.bmf.hu/matek Kötelez˝o irodalom: • Bagyinszki–György: Diszkrét matematika f˝oiskolásoknak, TypoTEX Kiadó, Bp. 2001. • György–Kárász–Sergyán–Vajda–Záborszky: Diszkrét matematika példatár, Bp. 2003, BMF-NIK-5003, (Továbbiakban Példatár). • Levelez˝osöknek a matek honlapon elérhet˝o NetworkX-es segédlet. Ajánlott irodalom: • Tóth Mihály: Számítástudomány algebrai alapjai • Tóth Mihály: Bevezetés a formális nyelvek és automaták elméletébe (Handout, 1992.) • Fellegi Tibor: Absztrakt algebrai összefoglaló (a matek honlapról utalás van rá) • Demetrovics, Denev, Pavlov: A számítástudomány matematikai alapjai (a formális nyelvek és absztrakt automaták részhez) Beadás: a https://elearnin.bmf.hu oldalon megadott határid˝ovel papíron vagy a következ˝o elektronikus formákban pdf, png, gif, jpg, odt (OpenOffice, Abiword vagy KWord), Microsoft Word (.doc). Ahol nem tüntetünk fel mást, a feladatsorszámok a Diszkrét matematika példatár feladataira utalnak.
1
1.
Gráfelmélet
1.1.
Mintafeladatok
5.1. fejezetbol ˝ 1., 2., 3. (három feladat!), 6. 7. Az illeszkedési mátrix |E| × |V| (4 csúcs, 3 él esetén 4 × 3-as) típusú mátrix, i j-dik eleme 1, ha i-dik csúcs rajta van j-dik élen, különben 0. 8., 14., 15. (izomorfia), 5.2. fejezetbol ˝ 1., 4. (csak Euler-séta kell) 5.4. fejezetbol ˝ 1., 3., 4., 8., 9., 10., 11.,
1.2.
Beadandó feladatok 1.
1.1. feladat. Írjuk fel az alábbi gráf szomszédsági mátrixát. Adjunk meg benne egy feszít˝ofát. Található-e a gráfban Euler-séta? 5 6 1
2 7
3
8 4
1.2. feladat. Ábrázoljuk az alábbi súlymátrix-szal megadott súlyozott mátrixot! Adjunk meg egy lehetséges maximális súlyú feszít˝ofát az ábrán (élek vastagításával vagy színezésével)! Írjuk fel a feszít˝ofa súlyát valamint az élek sorrendjét, ahogy hozzávettük a fához! ∞ 10 ∞ ∞ 6 ∞ 10 ∞ 7 ∞ 8 7 ∞ 7 ∞ 2 9 ∞ S = ∞ ∞ 2 ∞ 4 3 6 8 9 4 ∞ ∞ ∞ 7 ∞ 3 ∞ ∞ 1.3. feladat. Írjuk fel az alábbi fa Prüfer-kódját! 5 6 1
2 7
3
8 4
1.4. feladat. Az alábbi Prüfer-kódok esetén rajzoljuk fel a fát, amennyiben lehetséges: 62, 121314, 54321 2
1. ábra. Példa nyílt és zárt Euler-sétára
1.3.
Alapfogalmak
A fogalmak definíciói megtalálhatóak a feladatgyujtemény ˝ 23. oldalától kezd˝od˝oen. Ezek és a további részekben szerepl˝oek kellenek: gráf, csúcs fokszáma (mi d(n)-el jelöltük), élsorozat és annak hossza, út, kör, izolált pont, többszörös él, hurokél, teljes gráf, részgráf, feszített részgráf, mátrixreprezentációk, összefügg˝oség, komponensek. 1.1. definíció. Egy gráfot egyszeru˝ gráfnak nevezünk, ha nincs benne többszörös és hurokél. 1.2. definíció. Euler-sétának vagy Euler-bejárásnak nevezzük azt az élsorozatot a gráfban, amely minden élet pontosan egyszer érint. (Minden élen átmegy, és egyiken sem többször.) Az Euler-sétát zártnak nevezzük, ha az utolsó csúcsa egyezik az els˝ovel, különben nyílt Euler-sétának nevezzük. 1.1. tétel. Ha egy gráfban zárt Euler-séta van, akkor minden csúcs fokszáma páros. Ha egy gráfban nyílt Euler-séta van, akkor pontosan két csúcs fokszáma páratlan, ezek a séta kezd˝o és végpontjai. A fenti állítások fordítottjai is igazak összefügg˝o gráfok esetén. Azaz ha egy összefügg˝o gráfban a fokszámok párosak, akkor van zárt Euler-séta, ha kett˝o páratlan, a többi páros, akkor van nyílt Euler-séta a gráfban. Akár az élek (csúcspárok) listáját, akár az illeszkedési mátrixát ismerjük egy nagyobb méretu˝ gráfnak, elég nehéz megállapítani, hogy összefügg˝o-e. A gyakorlaton használt NetworkX modul szerencsére képes ezt megállapítani. A fokszámokat az illeszkedési mátrixból könnyedén megállapíthatjuk, hiszen csak a megfelel˝o sorokat kell összegezni. A 1. ábrán található egy-egy példa a zárt és nyílt Euler-sétára.
1.4.
Fák
1.3. definíció. Fáknak az összefügg˝o körmentes gráfokat nevezzük. 1.4. definíció. Egy összefügg˝o gráf feszít˝ofáján olyan fákat értünk, melyek részgráfjai az eredeti gráfnak, tartalmazzák annak összes csúcsát, és fák. 1.4.1.
Három fákkal kapcsolatos algoritmus
1.2. tétel. Egy n csúcspontú fát egy olyan n − 2 elemu˝ listával (egy számsorozattal) egyértelmuen ˝ leírhatunk, melyek elemei a számok 1-t˝ol n-ig. Ezt a listát nevezzük a fa Prüfer-kódjának Ez az alábbi algoritmussal bizonyítható. 3
1.5.
A Prüfer-kód eloállítása ˝
Kiindulás: egy fa valamilyen formában megadva (ábra, szomszédsági mátrix) 1. Legyen v 0 elemu˝ lista. Sorszámozzuk meg a csúcsokat 1-t˝ol n-ig. 2. Keressük meg a legkisebb sorszámú egyfokszámú csúcsot a (maradék) fán. Hagyjuk el az élet, és fuzzük ˝ a lista végéhez az él másik végén található csúcs sorszámát. 3. Ismételjük a 2. pontot addig, amíg egy él marad, az így kapott lista lesz a Prüfer-kód. 1.3. tétel. A Prüfer-kód csak egy fához tartozhat, és bármilyen {1, 2, . . . , n} elemekb˝ol álló n − 2 elemu˝ Prüfer-kód egyetlen fát ír le. Ez az alábbi algoritmussal bizonyítható. A fenti két tételb˝ol következik, hogy az ilyen kódok száma n · n · · · · · n = nn−2 , és ezzel az n csúcspontú fák száma is ennyi, mivel a Prüfer-kódok és fák között kölcsönösen egyértelmu˝ hozzárendelés, algebrai nyelven bijekció van.
1.6.
A Prüfer-kódból a fa visszaállítása
1. Legyen v a Prüfer-kód, számoljuk ki n-et, ha a kód hossza n − 2. Legyen E = {1, 2, . . . , n} a csúcsok halmaza. Induljunk ki egy n csúcsú 0 élu˝ gráfból. 2. Vegyük a lista (a Prüfer-kód) els˝o elemét. Kössük össze ezt a sorszámot E halmaznak azzal a legkisebb x sorszámával, ami nem szerepel a listában. 3. Hagyjuk el a lista els˝o elemét, és töröljük x-et az E halmazból. 4. Ismételjük a 2. és 3. pontot addig, amíg el nem fogy a lista összes eleme. 5. Az E megmaradt két elemét kössük össze. 1.5. definíció. (V1 , E1 ) és (V2 , E2 ) gráfokat izomorfnak nevezzük, ha létezik a csúcsaik között olyan f : V1 → V2 bijekció, melynél a, b ∈ V1 pontosan akkor van összekötve, ha f (a) és f (b) is össze vannak kötve. Ha adott csúcsszámú fák közül nem különböztetjük meg az izomorfakat, akkor az így el˝oálló fák száma lényegesen kisebb annál, mint a fentieknél meghatározott nn−2 esetszám. c a 1 2 a b G1 G2 3 4 c G2 d d b A fenti els˝o két gráfábra esetén például lerajzolva máshogy néz ki, mégis izomorfak. A következ˝o az egyik lehetséges bijekció a kett˝o közül. 2 7→ c,
1 7→ a,
3 7→ d,
4 7→ b
Például a {2, 1} élnek a másodikban a {c, a} él felel meg, mindkett˝o össze van kötve. A {2, 4} élnek a másodikban a {c, b} él felel meg, egyik sincs összekötve. Végigvizsgálva az összes csúcspárt G1 -ben, mindegyik G2 -beli képe pontosan akkor lesz összekötve, ha az eredeti is össze van kötve. Ha két gráf izomorf, akkor át is rajzolhatom o˝ ket úgy, hogy „ugyanúgy nézzenek ki”, ahogy G2 esetén is tettem. 4
1.7.
A legkisebb súlyú feszítofa ˝ létrehozása
1.6. definíció. Az olyan egyszeru˝ gráfokat nevezzük súlyozott gráfoknak, melynek minden éléhez egy pozitív számot rendelünk. A számot az él súlyának nevezzük, az összes él súlyának összegét a gráf súlyának nevezzük. 1.7. definíció. Egy n csúcsú súlyozott gráf súlymátrixának olyan n × n-es mátrixot nevezünk, amelyben, ha i és j között él fut, akkor a mátrix i j-edik eleme, és természetesen ji-dik eleme is az él fokszáma. A többi esetben a mátrixelem végtelen ∞. (Programban a végtelent egy olyan szám helyettesítheti, amely biztosan nagyobb a program által kezelt gráfok fokszámánál.) Algoritmus: Feladat: Legyen adott egy összefügg˝o súlyozott n-csúcsú G gráf például súlymátrix-szal. Keressük meg a minimális feszít˝ofáját, azaz azt a részgráfját, amely fa, és kisebb súlyú az ilyen fáknál. 1. A kezd˝ográfunk legyen egy csúcsú él nélküli G0 gráf. A pont sorszámát válasszuk 1-nek. (Vagy bárminek 1 és n között.) Ezt a gráfot tekintsük a G részhalmazának. 2. Keressük meg, azokat az éleket a G gráfban, amelyek a G0 gráfból kivezetnek. Keressük meg ezek közül a minimális súlyút. (Ha több ilyen van, akkor válasszunk közülük.) Vegyük hozzá G0 -höz ezt az élt és a másik végpontját. 3. Ismételjük a 2. pontot, amíg G-t kifeszít˝o fát nem kapunk. Ez lesz a minimális súlyú feszít˝ofa. A fenti algoritmusban minden minimális helyett írhatunk maximálisat.
5
2.
Halmazok
A halmaz alapfogalom. Axiómák vannak rá, elég bonyolult. A középiskolai szintu˝ halmazfogalom elegend˝o számunkra. Eszerint a halmaz adott, ha bármir˝ol eldönthet˝o, hogy hozzá tartozik-e vagy sem. Tehát a sorrend és a darabszám lényegtelen. {a, b} = {b, a} = {a, b, a} Megadás lehet felsorolással vagy a tulajdonságának megadásával. H = {1; 5; 7},
P = {x | x prímszám},
A = {x | x ∈ Z, −5 < x ≤ 7}
A függ˝oleges vonal el˝ott jelöljük, hogy mivel jelölöm a halmaz elemeit, utána pedig, hogy milyen feltételeket szabok rá ki. A dupla szárú jeleknek speciális jelentésük van, azok állandó jelölések, míg a sima nyomtatott nagybetuket ˝ tetsz˝oleges halmazra használhatjuk egy feladatban, bizonyításban. Az egyre b˝ovebb számhalmazok jelölései a következ˝oek: Jel név pár eleme, ami az el˝oz˝oben nincs benne N természetes számok 0; 1; 2; . . . Z egész számok −1; −2; −3; . . . Q racionális számok 1/2; √ −2/7; −7/3; 0, 1 R valós számok 2; e; π C komplex számok 3 + 4i; 5i; lg(−1) A valós számokból ha kivesszük a racionális számokat, tehát azokat, amelyek felírhatóak két szám hányasdosaként, az irracionális számok halmazát kapjuk. Jele Q∗ . R = Q∗ ∪ Q, azaz Q∗ = R \ Q Fels˝o indexben gyakran használjuk a + és − jeleket, amely arra utal, hogy a halmazt leszukítjük ˝ a pozitív illetve negatív elemeire, hasznájuk továbbá a halmaz többszörösét, valamint halmazhoz szám hozzáadását: Jel név pár eleme N+ = Z+ pozitív egész számok 1; 2; . . . Z− negatív egész számok −1; √ −2; −3; . . . R+ pozitív valós számok 2; e; π 2Z páros számok . . . ; −4; −2; 0; 2; 4; . . . 2Z + 1 páratlan számok . . . ; −3; −1; 1; 3; 5; . . . 3Z + 1 hárommal osztva egy maradékúak . . . ; −5; −2; 1; 4; 7; . . . A halmazokon általában három kétváltozós és egy egyváltozós muveletet ˝ szoktunk definiálni. Jel név A∪B unió két változós A∩B metszet két változós A\B különbség két változós A (felülvonás) komplementer egy változós A komplementer akkor értelmezhet˝o, ha adva van egy H alaphalmaz. Az A halmaz komplementere A tartalmazza ilyenkor azokat az elemeket, amelyek a H elemei, de A-nak nem. A = H\A
6
A példatárból szükséges még ismerni a hatványhalmaz fogalmát, és a halmazokon értelmezett relációkat (⊆, ⊂, =).
3.
Relációk, számosság, algebrai struktúrák – Definíciók, tételek
A következ˝o foglamak és tételek szükségesek pl. a példatár 5. és 19. oldaláról illetve a következ˝o fejezetekb˝ol. Descartes-szorzat, reláció (bináris, homogén), homogén bináris reláció tulajdonságai (dichotóm, ha a R b és a R b közül egyik mindig teljesül). Részbenrendezés, teljes rendezés. Ekvivalenciareláció, ekvivalenciaosztályok Függvénytulajdonságok (szürjektív, injektív, bijektív) a osztója b-nek, a kongruens b-vel Kétváltozós muvelet, ˝ tulajdonságai (asszociativitás, kommutativitás, idempotencia, disztributivitás) Félcsoport, csoport, Abel-csoport, gyur ˝ u, ˝ test
3.1.
Relációk
3.1. példa. Alább példákat mutatunk a kés˝obb definiálandó kételemu˝ (binér) relációkra. Számok között: • =, ≤, < • osztó (a osztója b-nek) • akár ez is lehet: a négyzetgyöke b-nek Egyenesek között: • párhuzamos, metsz˝o, kitér˝o Egyenes és sík között: • az egyenest tartalmazza a sík • az egyenes metszi a síkot • az egyenes párhuzamos a síkkal Ember és település között: a település az ember szül˝ohelye 3.1. feladat. Határozzunk meg binér relációkat a következ˝ok között: két ember; két háromszög; determináns és valós szám; ember és egész szám, két egész szám. A relációk általános definíciójának megadásához a Descartes-szorzattal kell kezdenünk. 3.1. definíció. Rendezett n-esnek nevezzük az olyan felsorolásokat, ahol a felsorolt elemek sorrendje és száma lényeges. A felsorolt elemeket ilyenkor kerek zárójelbe tesszük. (1, 2, 3) , (1, 3, 2) , (1, 3, 2, 2)
7
3.2. definíció. Legyenek H1 , . . . , Hn halmazok. Ekkor a D = {(h1 , . . . , hn ) | hi ∈ Hi } halmazt a Hi halmazok Descartes-szorzatának nevezzük és a H1 × · · · × Hn kifejezéssel jelöljük. 3.2. példa. Legyen A = {1, 2} és legyen B = {a, b}. Ekkor a Descartes-szorzat A × B = {(1, a), (1, b), (2, a), (1, b)}. 3.3. definíció. Legyen H1 × · · · × Hn a Hi (1 ≤ i ≤ n) halmazok Descartes-szorzata. Ekkor a R ⊆ H1 × · · · × Hn halmazt a Hi halmazokon értelmezett relációnak nevezzük. 3.3. példa. Legyen A = B = {1, 2, 3}. Reláció-e ekkor R = {(ai , bi ) | ai < bi és ai ∈ A valamint bi ∈ B}? Igen, mert
R = {(1, 2), (1, 3), (2, 3)} ⊆ A × B.
3.4. példa. Legyen A = {Lánczos Kornél, Esterházy Péter, Neumann János, Csoóri Sándor}, T a magyar települések halmaza, E az évszámok halmaza, F a foglalkozások halmaza. Válogassunk ki úgy elemnégyeseket, amelynél az els˝o tag ember A-ból van, a második az ember születési helye, a harmadik a sz. éve, a negyedik a foglalkozása. Ez reláció, mert része az A × T × E × F halmaznak. (Lánczos Kornél, Székesfehérvár, 1893, fizikus) (Esterházy Péter, Csákvár, 1950, író) (Neumann János, Budapest, 1903, matematikus) (Csoóri Sándor, Zámoly, 1930, költ˝o) (Csoóri Sándor, Zámoly, 1930, politikus) És ez már hasonlít egy szokványos relációs adatbázishoz, amelyr˝ol más tantárgyban esik szó. Ott tanulják meg, hogy az utolsó két sorban látható ismétl˝odésekhez hasonlóakat hogyan lehet csökkenteni egy adatbázisban. Az el˝obbi relációt 4-változósnak nevezzük, és általánosan definiálható az n-változós reláció. Minket a továbbiakban a kétváltozós reláció érdekel amit binér relációnak is nevezünk. 3.4. definíció. Egy relációt homogénnek nevezünk, ha a Descartes-szorzat tényez˝oi mind azonos halmazok. 3.2. feladat. Adjuk meg a következ˝ok esetén, hogy hány változósak, és homogének-e. • Pont illeszkedik az egyenesre. • Egyenesek párhuzamossága. • A valós számok a kisebb muveletre ˝ nézve. • {(x, y, z) ahol egy virágnak x a latin neve, y a hivatalos magyar neve, z a szirmainak a száma} 8
3.2.
Homogén binér relációk
A × A alakú szorzatok részhalmazai. Az ilyen relációt úgy szoktuk jelölni, hogy megadjuk az A alaphalmazt, és a rajta értelmezett reláció jelét egy rendezett párban. Például (R, ≤) A homogén binér relációkat a következ˝o tulajdonságok szerint csoportosíthatjuk: 3.5. definíció. Az alábbiakban R az A halmaz feletti R homogén binér reláció, a, b és c tetsz˝oleges elemei az A-nak (azaz bárhogy is választjuk ezeket A-ból, a tulajdonság feltételének mindig teljesülniük kell). 1. Reflexív: aRa 2.
(a) Szimmetrikus: Ha aRb akkor bRa. (b) Antiszimmetrikus: Ha aRb és bRa akkor a = b.
3. Tranzitív: Ha aRb és bRc, akkor aRc. 4. Dichotóm: aRb és bRa közül legalább egyik teljesül. Elnevezés Ekvivalenciareláció Rendezés vagy félig-rendezés Teljes rendezés
definíció reflexív, szimmetrikus és tranzitív reflexív, antiszimmetrikus és tranzitív reflexív, antiszimmetrikus, tranzitív és dichotóm
3.6. definíció. Legyenek a és b egész számok. Azt mondjuk, hogy a osztója b-nek, ha van olyan c ∈ Z, melyre a · c = b. Jelölése: a | b. Azt mondjuk, hogy a kongruens b mod m, ha m | (a − b) (azaz azonos maradékot adnak m-mel való osztáskor). Jelölése a ≡ b mod m vagy tömörebben a ≡m b. 3.7. definíció. Két halmazt diszjunktnak nevezünk, ha nincs közös elemük (azaz metszetük üres). Egy halmaz diszjunkt felbontásán olyan H1 , H2 . . . Hn halmazokból álló halmazt értünk, melyre • Hi ∩ H j = ∅ bármely olyan i és j pár esetén, melyek nem egyenl˝oek, és • az összes halmaz uniója a H halmazt adja. 3.1. tétel. Bármely (H, R) H halmaz feletti R ekvivalenciareláció esetén a H halmaznak létezik H1 , H2 . . . Hn diszjunkt felbontása, melyre 1. aRb ha a és b ugyanabban a Hi halmazban találhatóak 2. a és b ugyanabban a Hi halmazban találhatóak, akkor aRb Ezt a felbontást a H halmaz R ekvivalencia-reláció szerinti ekvivalenciaosztályainak nevezzük. A ≡m kongruenciához tartozó ekvivalenciaosztályokat gyakran egyszeruen ˝ és kissé pongyolán a 0, 1, . . . m − 1 számokkal jelöljük. Nyilván az adott szám jelöli azt az ekvivalenciaosztályt, amelybe az adott szám tartozik.
9
3.3.
Függvények
A már megszokott függvényeket most a relációkból származtatjuk úgy, hogy elhagyjuk a „többértéku˝ függvényeket”: egy értékhez csak egy másikat rendelhet a függvény. Például a négyzetgyök függvénynél csak a nemnegatív értéket hagyom meg. A továbbiakban a relációknál megszokott R jelölés helyett a függvényekhez jobban illeszked˝o f jelölést használjuk. 3.8. definíció. Az olyan nem feltétlenül homogén, de binér relációkat nevezzük függvényeknek, amelyben egy elem csak egyszer lehet a reláció bal oldalán. Másképpen fogalmazva, ahol a f b és a f c csak akkor teljesülhet, ha b = c. A függvényeknél az a f b jelölés helyett f (a) = b jelölésmódot vezetünk be. Az f (x) = y esetén azt mondjuk, hogy f az x változóhoz az y-t rendeli, vagy másképp, az x képe y. Egy f függvény esetén a zárójelben szerepl˝o elemek halmazát a függvény értelmezési tartományának nevezzük és D f -el jelöljük. (Angolul domain of f.) Egy f függvény esetén a képként fellép˝o elemek elemek halmazát a függvény értékkészletének nevezzük és R f -el jelöljük. (Angolul range of f.) Ha egy f függvény az A × B Descartes-szorzatból származik és D f = A, akkor a függvényt A → B típusúnak nevezzük és így jelöljük ezt: f :A→B Egy f : A → B függvényt bijekciónak (vagy kölcsönösen egyértelmu˝ függvénynek) nevezünk, ha • minden elem egyszer lép fel képként. Kissé precízebben: ha f (a) = b és f (c) = b csak akkor teljesülhet, ha a = c. • és B a függvény értékkészlete (nem b˝ovebb annál).
3.4.
Halmazok számossága
A halmazok egyenl˝oségének definíciója azon a nyilvánvaló tényen alapul, hogyha egy katonai táborban minden katona felül egy lóra és nem marad üres ló, akkor ugyanannyi a lovak és katonák száma. A pontos definíció azonban a végtelen számosságú halmazok szövevényes világában is alkalmazható. Érdemes tudatosítani, hogy míg a számok határértékeként csak egyféle pozitív végtelen szerepel, addig a halmazok számosságában többféle. 3.9. definíció. A és B halmazokat egyenl˝o számosságúnak nevezzük, ha létezik közöttük f : A → B bijekció. Jele: |A| = |B|. Egy A halmaz számossága |A| = n ∈ Z+ , ha |A| = |{1, 2, . . . , n}|. Ha van ilyen n, vagy üres halmaz esetén a halmazt véges halmaznak nevezzük (az üres halmaz számossága 0). 3.10. definíció. A természetes számok számosságát megszámlálhatóan végtelen számosságnak nevezzük. 3.2. tétel. Az egész számok, a páros számok, a prímszámok és a racionális számok számossága is megszámlálhatóan végtelen. |N| = |{páros számok}| bizonyítása: az n → 2n bijekció létezik a két halmaz között. |N| = |Q| bizonyítása kell. Lásd Példatár 1.3.1. c) megoldása. 10
3.3. tétel. A valós számok számossága nagyobb, mint megszámlálhatóan végtelen. Ezt kontinuum számosságnak nevezzük. 3.11. definíció. Halmaz hatványhalmaza: az összes részhalmazaiból álló halmaz. Az A halmaz hatványhalmazásnak jelölése P(A) vagy 2A . 3.5. példa. P({a, b}) = {∅; {a}; {b}; {a, b}}. 3.4. tétel. Egy n elemu˝ halmaz hatványhalmaza 2n elemu. ˝ 3.5. tétel. Minden halmaz hatványhalmaza nagyobb számosságú az eredeti halmaznál.
3.5.
Absztrakt algebra
Az absztrakt algebrában az a célunk, hogy a mveletek tulajdonságaiból származó következményeket egyszerre tárjuk fel különböz˝o matematikai objektumok esetén. Nem érdemes ugyanis ugyanazt külön bizonyítani számokra, mátrixokra, vektorokra és más pl. a kvantummechanikában szükséges bonyolultabb struktúrákra, érdemesebb ezeket egyszerre kezelni. n-változós muvelet ˝ Algebrai struktúra
3.6.
Egymuveletes ˝ struktúrák
3.12. definíció. Félcsoportnak nevezünk egy halmazt egy muveletre ˝ nézve, ha a muvelet ˝ 1. nem vezet ki soha a halmazból, 2. a muvelet ˝ asszociatív a halmaz felett, azaz bármely a, b, c ∈ G elemek esetén (a4b)4c = a4(b4c). Azaz mindegy melyik melyik 4 muvelete ˝ végzem el el˝obb, ugyanazt kapom. Példák: a valós számok az osztásra nézve (R, /) zárt, az egész számok az osztásra nézve (Z, /) nem az, mert ott például a 3/2 kivezet a számhalmazból. 3.13. definíció. Egy (G, 4) félcsoportot csoportnak nevezünk, ha 3. létezik egységeleme, azaz olyan e ∈ G melyre bármely G-beli a elem esetén e4a = a4e = a. Azaz van olyan elem, amivel a halmaz bármely másik elemét megszorozva ármelyik oldalról, azt a másik elemet kapjuk vissza. 4. minden G-beli a elemnek létezik (a−1 -nel jelölt) inverzeleme, melyre a−1 4a = a4a−1 = e. 3.14. definíció. Egy (G, 4) csoportot Kommutatív csoportnak vagy Abel-csoportnak nevezünk, ha a 4 muvelet ˝ kommutatív a csoport felett, azaz bármely G-beli a és b esetén a4b = b4a. 11
Niels Henrik Abel norvég matematikusról matematikai díjat is neveztek el. A díjat odaítél˝o öt f˝os nemzetközi bizottság tagja volt 2004 és 2006 között a jelenleg él˝o egyik legnagyobb magyar matematikusunk, Lovász László is. 3.3. feladat. Mi lesz a valós számok körében egy szám inverze, ha a muvelet ˝ az összeadás, és mi lesz, ha a muvelet ˝ a szorzás? Nézzük meg, hogy a természetes, egész, racionális, valós és komplex számok körében az összeadás illetve a szorzás muvelettel ˝ csoportot, Abel-csoportot alkotnak-e? Csoportot alkotnak-e a sík adott pont körüli elforgatásai? Ha igen, mi lesz az egységelem és egy adott forgatás inverze? Hogyan definiálhatnánk a kivonást és az osztást az összeadás és szorzás segítségével? Gondoljunk az inverzelemekre. És egy nehezebb kérdés: Vajon miért csak az utóbbi kett˝o alapmuvelet ˝ tulajdonságait vizsgáljuk a számok esetében?
3.7.
Kétmuveletes ˝ struktúrák
Ezt még sajnos a feladatgyujteményb˝ ˝ ol kell megnézni. gyur ˝ u, ˝ test 3.6. tétel. Az alábbi fontosabb algebrai struktúrákat érdemes ismerni: • (Z, +, ·) gyur ˝ u˝ • (Q, +, ·) test • (R, +, ·) test • (C, +, ·) test
Megjegyzések a feladatmegoldáshoz és mintafeladatok Gyakori feladat, hogy valamely véges halmaz feletti struktúrát muveleti ˝ táblázattal (kétmuveletesnél ˝ két táblázattal) adunk meg, és meg kell állapítani, hogy milyen algebrai struktúrát alkot a halmaz az adott egy vagy két muveletre. ˝ Általában az asszociativitás megállapítása a legnehezebb, ezért általában meg szoktuk adni a feladatban, hogy asszociatív a muvelet ˝ a halmazon. A további tulajdonságok esetén indokolni kell, hogy miért mondjuk. Egységelem esetén meg kell adni, hogy a struktúra melyik eleme az. Ha minden elemnek van inverzeleme, akkor azokat meg kell adni. A kommutativitást is indokolni kell (a táblázat szimmetrikus a f˝oátlóra). 1.2.23.; 1.2.26.; (1.3.1. megérteni a megoldást); 1.3.2. a) b) 4.1.2.; (4.2.1. és 4.2.1.) b) e) h); 4.2.4. a)–f); 4.2.5.; 4.2.6; 4.3.1; 4.3.3; 4.3.6. a) c) Döntsük el, hogy igaz-e az alábbi állítás. Válaszunkat indokoljuk! 1. Van olyan halmaz, amelynek számossága egyezik valamely valódi részhalmazásnak számosságával.
12
4.
Beadandó feladatok 2a) – Halmazok, relációk
4.1. feladat. 1.3.2. b) (részletezve, szöveges magyarázattal) 4.2. feladat. Legyen H = P({0; 1; 2}) halmaz a {0; 1; 2} halmaz hatványhalmaza, Igaz-e az efelett értelmezett részhalmaz relációra, hogy a) kétváltozós b) reflexiv c) szimmetrikus d) antiszimmetrikus e) tranzitív f) dichotóm? Ezek alapján milyen típusú reláció? 4.3. feladat. Ugyanilyen módon vizsgáljuk meg a valós számok felett értelmezett < relációt és a feljebb definiált mod 3 maradékosztályokon értelmezett ≡m kongruenciát. 4.4. feladat. Írjuk fel H = P({0; 1; 2; 3}) hatványhalmazt elemeinek felsorolásával. Hány eleme van? 4.5. feladat. Döntsük el, hogy igazak-e az alábbi állítások. Válaszunkat indokoljuk! (Nemleges válasz esetén általában ellenpéldával indokolhatunk.) 1. Minden rendezés teljes rendezés. 2. A mod 5 kongruenciareláció ekvivalenciareláció. 3. Van a komplex számok halmazáénál nagyobb számosság.
5.
Beadandó feladatok 2b) – Absztrakt algebra
5.1. feladat. Döntsük el, hogy igazak-e az alábbi állítások. Válaszunkat indokoljuk! (Nemleges válasz esetén általában ellenpéldával indokolhatunk.) 1. A valós számok a szorzásra nézve Abel-csoportot alkotnak. 2. Az adott pont körüli elforgatások csoportot alkotnak a két forgatás egymás utáni végzésére nézve. (Jelöljük az indoklásban az α szögu˝ elforgatást fα jellel, a forgatások egymás utáni végzését ◦ muvelettel ˝ ( fα ◦ fβ ). 5.2. feladat. Határozza meg, milyen algebrai struktúrát alkot az {a; b; c; d} halmaz az alábbi muveletre ˝ nézve. Az asszociativitás teljesül, azt nem kell vizsgálni. (Ha van, meg kell adni a neutrális elemet és az inverzeket is, nem elég megállapítani, hogy létezik.) ◦ a b c d a a b c d b b a d c c c d b a d d c a b 5.3. feladat. Határozza meg, milyen algebrai struktúrát alkot az ({0; 1; 2; 3}, +, ◦). Az asszociativitás mindkét muveletre ˝ teljesül, azt nem kell vizsgálni. A disztributivitás is teljesül, egy példán ellen˝orizzük. (Ha van, meg kell adni a neutrális elemeket és az inverzeket is, nem elég megállapítani, hogy létezik.) + 0 1 2 3 ◦ 0 1 2 3 0 0 1 2 3 0 0 0 0 0 1 1 2 3 0 1 0 1 2 3 2 2 3 0 1 2 0 2 0 2 3 3 0 1 2 3 0 3 2 1 Határozzuk meg (2 + 3) ◦ (3 + 3) értékét! 13
5.4. feladat. Milyen algebrai struktúrát alkotnak a reguláris mátrixok a mátrixszorzás muveletére ˝ nézve? (Reguláris mátrixok azok a négyzetes (n × n-es) mátrixok, amelyeknek nem nulla a determinánsuk.) 5.5. feladat. A mod 5 maradékoszályokra írjuk fel a szorzás és az összeadás muveleti ˝ tábláját. ({0; 1; 2; 3; 4}, ⊕5 , 5 ) milyen algebrai struktúrát alkot? ⊕5 , 5 az összeadás és szorzás maradéka öttel való osztás után.
14
6.
Formális nyelvek, automaták
A formális nyelvek rész egy külön Formális nyelvek és automaták segédletben találhatóak. Az ott látható követelményrendszer más tárgyra vonatkozik, Számítástudományhoz csupán az ott látható elméleti anyag és a feladatok kellenek.
7.
Beadandó feladatok 3. – Formális nyelvek és absztrakt automaták A Formális nyelvek segédletben található feladatok.
15
Tartalomjegyzék 1. Gráfelmélet 1.1. Mintafeladatok . . . . . . . . . . . . . . . . . 1.2. Beadandó feladatok 1. . . . . . . . . . . . . . 1.3. Alapfogalmak . . . . . . . . . . . . . . . . . . 1.4. Fák . . . . . . . . . . . . . . . . . . . . . . . . 1.4.1. Három fákkal kapcsolatos algoritmus 1.5. A Prüfer-kód el˝oállítása . . . . . . . . . . . . 1.6. A Prüfer-kódból a fa visszaállítása . . . . . . 1.7. A legkisebb súlyú feszít˝ofa létrehozása . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
2. Halmazok
2 2 2 3 3 3 4 4 5 6
3. Relációk, számosság, algebrai struktúrák – Definíciók, tételek 3.1. Relációk . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2. Homogén binér relációk . . . . . . . . . . . . . . . . . . . . 3.3. Függvények . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.4. Halmazok számossága . . . . . . . . . . . . . . . . . . . . . 3.5. Absztrakt algebra . . . . . . . . . . . . . . . . . . . . . . . . 3.6. Egymuveletes ˝ struktúrák . . . . . . . . . . . . . . . . . . . . 3.7. Kétmuveletes ˝ struktúrák . . . . . . . . . . . . . . . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
7 7 9 10 10 11 11 12
4. Beadandó feladatok 2a) – Halmazok, relációk
13
5. Beadandó feladatok 2b) – Absztrakt algebra
13
6. Formális nyelvek, automaták
15
7. Beadandó feladatok 3. – Formális nyelvek és absztrakt automaták
15
16
