Számítástudomány matematikai alapjai segédlet táv és levelez˝o Horváth Árpád 2008. december 16. A segédletek egy része a matek honlapon található: 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) A beadandó feladatok eredménye 20 %-ban beleszámít a félévközi- illetve vizsgajegybe. Beadás: a következ˝o alkalomkor vagy addig papíron vagy a következ˝o elektronikus formákban pdf, png, gif, jpg, odt (OpenOffice, Abiword vagy KWord), Microsoft Word (.doc). Az utolsó beadási határidejét még pontosítjuk. 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. definíció. Euler-sétának nevezzük azt az élsorozatot a gráfban, amely minden élet pontosan egyszer érint. (Minden élen átmegy, és egyiken sem többször.) Az Eulersétát zártnak nevezzük, ha az utolsó csúcspontja egyezik az els˝ovel, különben nyílt Euler-sétának nevezzük. 1., 4. (csak Euler-séta kell) 5.4. fejezetbol ˝ 1., 3., 4., 8., 9., 10., 11.,
2.
Beadandó feladatok 1.
2.1. feladat. Írjuk fel az alábbi gráf szomszédsági mátrixát. Adjunk meg benne egy feszít˝ofát.
2.2. feladat. Ábrázoljuk az alábbi súlymátrix-szal megadott súlyozott mátrixot! Adjuk 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! Adjuk meg a feszít˝ofa Prüfer-kódját! ∞ 10 ∞ ∞ 6 ∞ 10 ∞ 7 ∞ 8 7 ∞ 7 ∞ 2 9 ∞ S = ∞ ∞ 2 ∞ 4 3 6 8 9 4 ∞ ∞ ∞ 7 ∞ 3 ∞ ∞ 2
2.3. feladat. Az alábbi Prüfer-kódok esetén rajzoljuk fel a fát, amennyiben lehetséges: 62, 121314, 54321
Alapfogalmak A fogalmak definíciói megtalálhatóak a feladatgyujtemény ˝ 23. oldalától kezd˝od˝oen. 2. definíció. Egy gráfot egyszeru˝ gráfnak nevezünk, ha nincs benne többszörös és hurokél.
3.
Fák
3. definíció. Fáknak az összefügg˝o körmentes gráfokat nevezzük. 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 öszuszes ˝ csúcsát, és fák.
4.
Három fákkal kapcsolatos algoritmus
1. 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ó.
4.1.
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. 2. tétel. A Prüfer-kód csak egyféle fához tartozhat, és bármilyen {1, 2, . . . , n} elemekb˝ol álló n − 2 elemu˝ Prüfer-kód egyetlen fát ír le. Ezt 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.
3
4.2.
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.
4.3.
A legkisebb súlyú feszítofa ˝ létrehozása
5. 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. 6. 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.
4
5.
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
6.
Relációk
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 6.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 Descart-szorzattal kell kezdenünk. 7. 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.
5
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)}. 8. 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. 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.
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. 9. definíció. Egy relációt homogénnek nevezünk, ha a Descartes-szorzat tényez˝oi mind azonos halmazok. 6.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 x virágnak y a latin neve és z a hivatalos magyar neve}
6
6.1.
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: 10. 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
11. 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. 12. 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. 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.
7
6.2.
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. 13. 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).
7.
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. 14. 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). 15. definíció. A természetes számok számosságát megszámlálhatóan végtelen számosságnak nevezzük. 4. 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.
8
|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. 5. 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. 16. 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 . 5. példa. P({a, b}) = {∅; {a}; {b}; {a, b}}. 6. tétel. Egy n elemu˝ halmaz hatványhalmaza 2n elemu. ˝ 7. tétel. Minden halmaz hatványhalmaza nagyobb számosságú az eredeti halmaznál.
8.
Absztrakt algebra
Az absztrakt algebrában az a célunk, hogy a muveletek ˝ 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
8.1.
Egymuveletes ˝ struktúrák
17. definíció. Félcsoportnak nevezünk egy halmazt egy muveletre ˝ nézve, ha a mu˝ velet 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, /) félcsoport, 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. 18. 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. 9
19. 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. 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. 8.1. 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?
8.2.
Kétmuveletes ˝ struktúrák
Ezt még sajnos a feladatgyujteményb˝ ˝ ol kell megnézni. gyur ˝ u, ˝ test 8. 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. 10
9.
Beadandó feladatok 2.
9.1. feladat. 1.3.2. b) (részletezve, szöveges magyarázattal) 9.2. 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. 9.3. 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ó? 9.4. 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. 9.5. feladat. Írjuk fel H = P({0; 1; 2}) hatványhalmazt elemeinek felsorolásával. Hány eleme van? 9.6. 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 valós számok a szorzásra nézve Abel-csoportot alkotnak. 3. Van a valós számoknál nagyobb számosságú halmaz. 4. A mod 5 kongruenciareláció ekvivalenciareláció. 9.7. 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. A mod 5 kongruenciareláció ekvivalenciareláció. 9.8. 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.
11
3. konzultáció – Formális nyelvek, automaták Tóth Mihály PowerPoint bemutatójának PDF változata elérhet˝o a honlapjáról: http://www.roik.bmf.hu/~mtoth Oktatási anyagok/A szám. tud/formalnyelvek*.pdf Az itt szerepl˝o szöveg eredetileg a Demetrovics-féle könyv jelöléseit követte, jelenleg közelítettem a jelöléseket Tóth Mihály jelöléséhez, de a következ˝o dolgok esetén a jelölések eltérnek attól: ebben a segédletben a szavakat görög betuk ˝ jelölik, a nem teminális jeleket latin nagybetuk ˝ (A,B,C), a terminális jeleket kisbetuk ˝ (ez egyezik).
10.
Formális nyelvek
20. definíció. A formális nyelvek alapvet˝o definíciói. • Ábécé: jelek véges halmaza (K, W, V) Ezek egyesítése, különbsége a halmazokéhoz hasonlóan definiált. • Ábécé betui: ˝ a jelek (a, b, ck ) a ∈ K • Szó: jelek véges sorozata (α, β, ω) • Szó hossza: a sorozat hossza (length) (lg(α)) • Üres szó (λ): melyre lg(λ) = 0 • Szavak konkatenációja (összefuzése): ˝ αβ = a1 a2 a3 · · · an b1 b2 · · · bm , ahol α = a1 a2 a3 · · · an , β = b1 b2 · · · bm (Asszociatív, kommutatív, egységelemes-e? lg(αβ) =?) • Tükörkép: α−1 = an · · · a2 a1 a fenti alfával. • Hatvány: α0 = λ, α1 = α, αn = αn−1 α • W(V) a V ábécé összes szava (zárt a konkatenációra) • V ábécéb˝ol alkotott formális nyelv (L(V) vagy L): bármely L(V) ⊆ W(V) • Nyelvek konkatenációja: L1 L2 = {αβ|α ∈ L1 , β ∈ L2 } • Nyelvek hatványa: L0 = {λ}, L1 = L, Ln = Ln−1 L Példák: • V1 = {0, 1}, L1 (V1 ) = ∅, L2 (V1 ) = {01, 0, λ}, L3 (V1 ) = {ω0ω−1 |ω ∈ W({0; 1})}, • V2 = {i f ; then; a; b}
L1 (V2 ) = {if a then b; if a then if b then c}
• 0100 01010 ∈ L2 (V1 )L3 (V1 )
az ’ csak a határt jelöli
(Generatív) grammatikák megadásához 4 dolgot kell megadni: G(VT ; VN ; X0 ; F) VT : terminális jelek, VN : nem terminális jelek, X0 : kezd˝oszimbólum, F: helyettesítési szabályok.
Grammatikák típusai (Chomsky-hierarchia) Legyen α, β, ω ∈ W(VT ∪ VN ) A, B ∈ VN a ∈ VT (X0 → λ szabály mindenhol megengedett) szabályok típusa grammatika típusa automata αAβ → ω 0-típusú, általános Turing-gép αAβ → αωβ 1-típusú, környezetfügg˝o A→ω 2-típusú, környezetfüggetlen PDA A → aB vagy A → a 3-típusú, reguláris FDA A fentieken kívül az X0 → λ szabály mindenhol megengedett, ha sehol sem szerepel a → jobboldalán X0 . Ha ezt hozzávesszük, akkor egy nyelv típusa nem fog függeni attól, ha az üres szót λ hozzáadjuk, vagy elvesszük bel˝ole.
12
21. definíció. A nyelvet n-típusúnak nevezünk, ha van olyan n-típusú generatív grammatika, amely a nyelvet generálja. (Pl: környezetfügg˝o nyelvet generál a környezetfügg˝o grammatika.) automaták: PDA: push-down automaton=nem determinisztikus veremautomata; FDA: véges (angolul finite) determinisztikus automata véges determinisztikus automata (FDA) megadása állapotgráffal (ez irányított gráf): nyíl mutat a kezdeti (általában q0 -lal jelölt) állapotra. A nyilakon szerepl˝o jelek (az ábécéb˝ol) jelzik, hogy egy adott állapotból azt olvasván a szalagról hova jut tovább. A kett˝os körök jelzik a végállapotokat. Ha egy szó esetén a kezdeti állapotból elindulva végállapotba jutunk amikor a szó végére értünk, akkor az automata felismerte a szót.
11.
Beadandó feladatok 3.
1. Határozzuk meg, hogy az L(G) nyelvben benne van-e: λ, abb, aabb? Írjuk le szavakkal és halmazjelölésekkel, milyen szavakat tartalmaz! Soroljuk be a Chomsky-féle hierarchiába a grammatikát! VT = {a, b},
VN = {X0 }
F = {X0 → ab; X0 → aX0 b} 2. Határozzuk meg, hogy az L(G) nyelvben benne van-e: 01, 111, 1111? Írjuk le szavakkal milyen szavakat tartalmaz! Soroljuk be a Chomsky-féle hierarchiába a grammatikát! VT = {0, 1}, VN = {X0 , A} F = {X0 → 1; X0 → 1A; X0 → 0X0 ; A → 1X0 ; A → 0A} 3. Adjunk meg olyan reguláris grammatikát, amely pontosan azokat az 0 és 1 jelb˝ol álló szavakat generálja: (a) melyek két 0-ra kezd˝odnek; (b) melyekben pontosan egy 0 van. 4. Felismeri-e az alábbi automata a csupa egyesekb˝ol álló szavakat? Adjunk meg három olyan szót, amit az alábbi véges determinisztikus automata felismer! Adjuk meg, milyen szavakat ismer fel (szóban vagy halmazjelöléssel)!
5. Adjunk meg FDA-t, amely az alábbi nyelvet ismeri fel, illetve grammatikát, amely ezt generálja: L = {αα−1 |α ∈ W({0, 1})}
13
6. Adjunk meg FDA-t, amely az alábbi nyelvet ismeri fel, illetve reguláris grammatikát, amely ezt generálja: L = {α01|α ∈ W({0, 1})} 7. 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.) (a) Egy környezetfüggetlen nyelvhez létezhet olyan általános grammatika, amely azt állítja el˝o. (b) A szavak konkatenációja egységelemes félcsoport. 8. Adjuk meg halmazleírással vagy írjuk le szavakkal milyen nyelveket ad meg a 4.9 és 4.10 ábrán látható véges determinisztikus automaták.
14
Tartalomjegyzék 1. Gráfelmélet 1.1. Mintafeladatok . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2 2
2. Beadandó feladatok 1.
2
3. Fák
3
4. Három fákkal kapcsolatos algoritmus 4.1. A Prüfer-kód el˝oállítása . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.2. A Prüfer-kódból a fa visszaállítása . . . . . . . . . . . . . . . . . . . . . . . 4.3. A legkisebb súlyú feszít˝ofa létrehozása . . . . . . . . . . . . . . . . . . . . .
3 3 4 4
5. Relációk, számosság, algebrai struktúrák – Definíciók, tételek
5
6. Relációk 6.1. Homogén binér relációk . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.2. Függvények . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5 7 8
7. Halmazok számossága
8
8. Absztrakt algebra 9 8.1. Egymuveletes ˝ struktúrák . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 8.2. Kétmuveletes ˝ struktúrák . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 9. Beadandó feladatok 2.
11
10. Formális nyelvek
12
11. Beadandó feladatok 3.
13
15
