Számításelmélet Szigorlat

Számításelmélet Szigorlat Kidolgozott tételsor

Készítette: Horváth Mária, Pecze Tamás

A kidolgozás csak egy összefoglalónak készült, hogy áttekinthetővé váljanak a szigorlaton kérdezett főbb fogalmak, de semmiképpen sem helyettesíti a könyv áttekinté sét. A szigorlaton főleg az anyagok közti összefüggésekre kíváncsiak, nem elég kimondani egyes tételeket, azok értelmébe is bele kell látni.

Felhasznált irodalom: - Tar Domokos Géza-Iwatt Róbert féle kidolgozás java részben - saját órai jegyzetek (ábrák, bizonyítások, példák) - hivatalos könyvek

Módosítva: 2007. március 21.

Tartalom – 1. lap

Tartalomjegyzék-A01 2007. március 6. 1:06

Számításelmélet új szigorlati tételsor 2004. áprilisától ez az új tételsor az aktuális.

"A" tételsor 1. Végtelen halmazok számossága: egyenlő, kisebb-egyenlő, illetve kisebb számosságú halmaz definíciója, Cantor-Bernstein-tétel (NB). Megszámlálhatóan végtelen és kontinuum számosságú halmaz. Z, Q, R számossága és ezek összehasonlítása a természetes számok számosságával. Véges ábécé feletti szavak és nyelvek halmaza, e halmazok számossága. Hatványhalmaz, Cantor-tétel (*). N hatványhalmazának számossága (*). Kontinuum-hipotézis (NB).

2. Determináns definíciója, alaptulajdonságai (*), kiszámítása, kifejtési tétel (*). Mátrixok, műveletek mátrixokkal, ezek tulajdonságai (*). Determinánsok szorzástétele (NB). Mátrix inverze, létezésének szükséges és elégséges feltétele, az inverz kiszámítása. Mátrix rangja, a rangfogalmak egyenlősége (*). Gráf szomszédossági mátrixa, hatványainak jelentése; gráf illeszkedési mátrixa, annak rangja (*). 3. Lineáris egyenletrendszer megoldása Gauss-eliminációval, megoldhatóság, a megoldás egyértelműségének feltétele. nxn-es lineáris egyenletrendszer egyértelmű megoldhatóságának jellemzése a determináns segítségével (*), általános egyenletrendszer megoldhatóságának jellemzése a rang segítségével (*). Térbeli koordinátageometria: sík egyenlete, egyenes egyenletrendszere, metszéspontok és metszésvonalak számítása.

4. Vektortér definíciója, példák. Altér, lineáris kombináció, generált altér, generátorrendszer. Lineáris függetlenség, a kétféle definíció ekvivalenciája. Kicserélési tétel (*). Bázis, vektorok bázis szerinti felírásának egyértelműsége. Dimenzió, a dimenzió egyértelműsége. 5. Lineáris leképezés fogalma, példák. Lineáris leképezés mátrixa, vektor képének meghatározása a mátrix segítségével. Lineáris leképezések szorzata, szorzat mátrixa (*). Lineáris leképezések magtere, képtere, ezek altér volta. Dimenziótétel (*). 6. Lineáris transzformációk, illetve négyzetes mátrixok sajátértékei, sajátvektorai. A sajátértékek és sajátvektorok meghatározása. Sajátaltér, ennek altér volta.

7. Kombinatorikus leszámlálási alapfeladatok, példák. Binomiális tétel. Gráfelméleti alapfogalmak: gráf, egyszerű gráf, izomorfia, részgráf, feszített részgráf, élsorozat, út, kör, összefüggőség, összefüggő komponens, fa, feszítőfa. Fák egyszerű tulajdonságai. Cayley-tétel (*). 8. Minimális költségű feszítőfa keresése. Piros-kék algoritmus (*). Prim módszere, a módszer lépésszáma naív és kupacos (*) implementáció esetén. Kruskal algoritmusa, megvalósítása UNIO-HOLVAN adatszerkezettel, lépésszáma (*). Boruvka módszere (*). 9. Legrövidebb utak keresése. Szélességi bejárás, lépésszáma. Dijkstra algoritmusa (*), lépésszáma mátrixos (*) és éllistás (*) megadással. Bellman-Ford algoritmusa, lépésszáma mátrixos megadás esetén. Floyd algoritmusa, lépésszáma mátrixos megadás esetén (*).

Tartalom – 2. lap

Tartalomjegyzék-A02 2007. március 8. 21:35

10. Mélységi bejárás, lépésszáma, mélységi és befejezési számozás, az élek osztályozása irányított és irányítatlan gráfok esetén. Alkalmazások: DAG tulajdonság ellenőrzése (*), topologikus sorrend keresése (*), legrövidebb és leghosszabb út keresése DAG-ban, PERT módszer. 11. Síkbarajzolhatóság, kapcsolat a gömbre rajzolhatósággal, Euler-tétel (*), felsőbecslés az élek számára. Kuratowski-gráfok, ezek síkba nem rajzolhatósága, Kuratowskitétel (NB), Fáry-Wagner-tétel (NB). Dualitás, gyenge izomorfia fogalma, absztrakt dualitás, Whitney tételei (NB). 12. Hamilton-körök és -utak. Szükséges feltétel Hamilton-kör/út létezésére. Elégséges feltételek: Ore (*) és Dirac tétele. Hamilton-kör keresés bonyolultsága (*). Euler-körök és -utak, ezek létezésének szükséges és elégséges feltétele. 13. Gráfok színezése. χ(G) fogalma és viszonya ω(G)-hez, illetve D(G)-hez. Brooks tétele (NB). Mycielski konstrukciója (*). Intervallumgráfok színezése. Perfekt gráf fogalma. Síkbarajzolható gráfok kromatikus száma (*). 3-SZÍN nyelv bonyolultsága (*). Élkromatikus szám, χe(G) viszonya D(G)-hez, Vizing-tétel (*).

14. Páros gráfok. Párosítások páros gráfban, magyar módszer (*), lépésszáma. König tétele (*), Hall tétele (*), Frobenius tétele (*). Párosítások tetszőleges gráfban, és kapcsolata, Tutte tétele (csak a szükségesség bizonyításával). Gallai tételei (közülük szabadon választhatóan az egyik bizonyításával). 15. Hálózat, hálózati folyamok. A javító utas algoritmus. Ford-Fulkerson tétel (*), Edmonds-Karp tétel (NB). Egészértékűségi lemma. A folyamprobléma általánosításai. Menger tételei (*). Többszörös összefüggőség, élösszefüggőség. Dirac tétele (NB). 16. Oszthatóság, felbonthatatlan és prímtulajdonságú számok. A számelmélet alaptétele (*). Osztók száma. A prímek számának végtelensége. Kongruencia fogalma, alapműveletek kongruenciákkal. Lineáris kongruenciák, a megoldhatóság szükséges és elégséges (*) feltétele. Wilson tétele (*). 17. Teljes és redukált maradékrendszer, j-függvény definíciója. Euler-Fermat-tétel (*), kis Fermat-tétel. Euklideszi algoritmus. 18. Számelmélet és algoritmusok: alapműveletek, hatványozás az egészek körében és modulo m. Prímtesztelés (feladata, Fermat-féle teszt, Carmichael számok). Nyilvános kulcsú titkosírás. 19. Művelet fogalma, félcsoport, csoport, Abel-csoport, részcsoport, elem rendje. Példák: csoportok számokon, mátrixokon, rajzok szimmetriacsoportja, ciklikus csoport, diédercsoport, szimmetrikus csoport. Csoportok izomorfiája. Mellékosztály, Lagrange tétele (*), elemrend és csoport rendjének kapcsolata. 20. Gyűrű és test fogalma. Példák: Z, Q, R, nxn-es mátrixok, polinomok, Zp. Komplex számok, algebrai és trigonometrikus alak, alapműveletek komplex számokkal. Komplex szám n-edik gyöke, egységgyökök.

Tartalom – 3. lap

Tartalomjegyzék-B01 2007. március 11. 18:08

"B" tételsor 1. Rendezési feladat. Buborékrendezés, lépésszáma (*). Beszúrásos rendezés, lépésszáma. Rendezett sorozatok összefésülése, az összefésülés lépésszáma, összefésüléses rendezés, lépésszáma (*). Alsó korlát az összehasonlítás alapú rendezésekre (*). Gyorsrendezés, lépésszáma (*). Ládarendezés, radixrendezés (*), lépésszámuk (*). 2. Kupac adatszerkezet, műveletek, lépésszámuk, kupacépítés (*). Kupacos rendezés, lépésszáma. Lineáris és bináris keresés rendezett halmazban, a keresés lépésszáma, alsó korlát. Bináris keres fák, műveletek, lépésszámuk.

3. AVL-fák, szintszám (*), műveletek (*), lépésszámuk (*). 2-3 fák, szintszám, műveletek, lépésszámuk. B-fák, műveletek (*), lépésszámuk (*). 4. Vödrös hash-elés, a műveletek lépésszáma (*). Nyitott címzésű hash-elés: lineáris és kvadratikus maradék próba (*), kettős hash-elés. Jó hash-függvények (*). A hash-elés alkalmazhatósága, összehasonlítva a keresőfákkal. 5. A Turing-gép fogalma, működése. A többszalagos Turing-gép szimulálása egyszalagossal, az idő és tárkorlát változása (*). A Chomsky nyelvosztályok kapcsolata a Turing-gép változataival (*). Univerzális Turing-gépek létezése (*). Church-Turingtézis. 6. Rekurzív és rekurzívan felsorolható nyelvek és rekurzív, illetve parciálisan rekurzív függvények. Az R, RE, coR és coRE nyelvosztályok kapcsolata. Nevezetes nyelvek, bonyolultságuk: diagonális nyelv, univerzális nyelv (*), megállási nyelv, dominó probléma (*), Post megfeleltetési feladata (NB), környezetfüggetlen nyelvtanokkal kapcsolatos eldönthetetlen feladatok (*). 7. Kolmogorov-bonyolultság: adott Turing-gépre vett bonyolultság, invariancia-tétel, a Kolmogorovbonyolultság definíciója, a definíció értelmessége. Összenyomhatatlanság, összenyomhatatlan szavak létezése (*), a C függvény bonyolultsága (*). 8. Idő - és tárkorlátos Turing-gépek. Tár-idő-tétel (*). Nevezetes nyelvosztályok: P, PSPACE, EXPTIME, ezek kapcsolata.

9. Nemdeterminisztikus Turing-gépek, idő és tárbonyolultságuk. NP és coNP nyelvosztály, ezek kapcsolata P-vel és R-rel. Tanú-tétel (*). Példák NP és coNP-beli nyelvekre. 10. Karp-redukció, a Karp-redukció tranzitivitása. NP-teljesség. Cook-Levin-tétel (*). További nyelvek NPteljessége: 3-SAT (*), 3-SZÍN (*), MAXFTLEN, X3C (NB), H (NB), RH (NB), Ládapakolás (NB). 11. Dinamikus programozás: elve, példák a korábbi algoritmusok közül, hátizsák probléma megoldása kis súlyok esetén, az algoritmus lépésszáma. Közelítő algoritmusok: elv, algoritmus a ládapakolási feladatra (*). 12. Véges automata. Véges automaták determinizálása és teljesen specifikálása. Minimálautomata, konstrukciója, unicitása (*). Kétirányban mozgó véges automata, kapcsolata az egyirányban mozgó véges automatával (*).

Tartalom – 4. lap

Tartalomjegyzék-B02 2007. március 14. 19:35

13. Generatív nyelvtanok, Chomsky-nyelvosztályok. A generatív nyelvek számossága. Bal- és jobb-reguláris nyelvtanok, kapcsolatuk (*), reguláris nyelvek. Véges automaták és reguláris nyelvek kapcsolata.

14. Reguláris nyelvek zártsági tulajdonságai: metszet, unió (*), komplementer, konkatenált, tranzitív lezárt (*). Pumpálási lemma reguláris nyelvekre (*). Reguláris halmazok, kapcsolatuk a reguláris nyelvekkel (*). 15. Környezetfüggetlen nyelvek. Környezetfüggetlen nyelvtanok jólfésült alakra hozása. Chomskynormálformára hozás. Greibach-normálforma (*). Rekurzió és balrekurzió kiküszöbölhetősége.

16. Veremautomaták. Állapottal és üres veremmel elfogadó veremautomaták, ezek kapcsolata. Mélységbe látó veremautomata, kapcsolata a nem mélységbe látó veremautomatával (*). Környezetfüggetlen nyelvtanok és veremautomaták kapcsolata (*), környezetfüggetlen nyelvtanból veremautomata konstruálása. 17. Pumpálási lemma környezetfüggetlen nyelvekre (*). A környezetfüggetlen nyelvek zártsági tulajdonságai: metszet, unió, komplementer, konkatenált (*), tranzitív lezárt (*). Determinisztikus környezetfüggetlen nyelvek. A determinisztikus környezetfüggetlen nyelvek zártsági tulajdonságai: metszet, unió, komplementer (*).

18. A fordítás fogalma. Véges fordító. Reguláris (*) és környezetfüggetlen nyelvek zártsági tulajdonságai a véges fordítás esetén. Veremfordító, szintaxis vezérelt fordítási séma, kapcsolatuk (*). 19. Levezetési fa környezetfüggetlen nyelvtanok esetén. Környezetfüggetlen nyelvtanok és nyelvek egyértelműsége. A környezetfüggetlen nyelvtanok elemzésének célja. Cocke-Younger-Kasami algoritmusa. Az Earley-algoritmus. 20. Balelemzés. Az LL(k)-elemzés algoritmusa (erős és gyenge). LL(k) nyelvtanok (*) és nyelvek (*). 21. Jobbelemzés. Az LR(k)-elemzés algoritmusa. LR(k) nyelvtanok (*) és nyelvek (*). Prefix tulajdonságú nyelvek, kapcsolatuk az LR(k)-elemzéssel (*). 22. A precedenciaelemzés algoritmusa. Erős és gyenge precedencia-nyelvtanok, erősen és gyengén precedencia-elemezhető nyelvek kapcsolata (*). Az operátor precedencia elemzés.

Tartalom – 5. lap

A01-01

TARTALOMJEGYZÉK

2007. március 4. 20:15

Végtelen halmazok számossága: egyenlő, kisebb egyenlő, kisebb definíciója Def.: Az A halmaz számossága = a B halmaz számosságával, ha létezik köztük egy f:A→B kölcsönösen egyértelmű függvény Def.: Ha megadható olyan f:A→B leképezés, ami A minden eleméhez B más-más elemét rendeli, akkor

Def.:

Cantor-Bernstein-tétel:

Megszámlálhatóan végtelen és kontinuum számosságú halmaz: Minden olyan halmaz megszámlálhatóan végtelen, amelynek elemei sorba rendezhetőek. A megszámlálhatóan végtelen halmaz bármely részhalmaza véges vagy megszámlálhatóan végtelen. A természetes számok (N) halmazának számosságát megszámlálgatóan végtelennek nevezzük.

A valós számok (R) halmazának számossága kontinuum. Z,Q,R számossága: Z és N között egy egyértelmű leképzés lehet pl.:

A racionális számokat (Q) fel tudjuk számlálójuk és nevezőjük összegének növekvő sorrendjében sorolni.

R valós számok halmaza nagyobb, mint N-é

A valós számok és a számegyenes pontjai között kölcsönösen egyértelmű leképezés létesíthető.

A Tételsor – 6. lap

A01-02

TARTALOMJEGYZÉK

2007. március 4. 21:58

Véges ábécé feletti szavak és nyelvek halmaza, számossága: A véges ábécé feletti szavak halmaza megszámlálhatóan végtelen, hiszen a szavak sorba rendezhetők pl. lexikografikusan. A véges ábécé feletti nyelvek száma kontinuum /Cantor-féle módszerrel bizonyítható/. Véges ábécé feletti generatív nyelvek száma megszámlálhatóan végtelen, mivel minden nyelvhez tartozik egy nyelvtan, melyeket át tudunk úgy alakítani, hogy felsorolhatóak legyenek, így az általuk generált nyelvek is megszámlálhatóan végtelenek. Hatványhalmaz:

H hatványhalmazán H összes részhalmazának halmazát értjük. , ha n a halmaz elemeinek száma Cantor-tétel: A halmaz számossága mindig kisebb mint a hatványhalmazának számossága. Mindig van adott számosságnál nagyobb. N hatványhalmazának számossága:

kontinuum, tehát Kontinuum hipotézis:

általánosítva: nincs más számosság |A| és |P(A)| között


A02-01

TARTALOMJEGYZÉK

2007. március 4. 22:17

A permutáció egy függvény, az ,1…n- halmaznak önmagára történő bijektív leképzése /az i. helyen az ott álló (i) számot rendeli/. Azaz n különböző elem valamilyen sorrendje. Def.: Egy permutációban két elem inverzióban áll, ha a nagyobbik megelőzi a kisebbiket. A permutáció inverziószáma az inverzióban álló elemek száma. Def.: Determináns

A determináns tulajdonságai:

1. vagy

akkor detA a főátlóba írt elemek szorzata

2.

Ha valamelyik sor vagy oszlop csupa 0 detA = 0

3.

Ha az egyik sort vagy oszlopot -val szorzom, akkor detA is -szorosára változik

4.

Ha valamelyik sor vagy oszlop minden eleme egy két tagú összeg, akkor a determináns két determináns összegére bomlik:

5.

Ha két sor vagy oszlop egyenlő, akkor detA = 0

6.

Ha valamelyik sor vagy oszlop a másik szorosa, akkor detA = 0

7.

Ha egy sorhoz vagy oszlophoz hozzáadjuk a -szorosát, akkor a determináns nem változik

8.

Ha két sort vagy oszlopot felcserélünk, akkor a determináns a (-1)-szerese lesz


A02-02

TARTALOMJEGYZÉK

2007. március 4. 22:38

A determináns kiszámítása: Gauss-elliminációval lépcsős alakra (míg minden főátló alatti elem 0 nem lesz) kell hozni a mátrixot. Ekkor a determináns a főátlóbeli elemek szorzata lesz. Kifejtési tétel: Ha egy sor minden elemét megszorozzuk a hozzá tartozó előjeles aldeterminánssal, akkor megkapjuk a determinánst. Előjeles aldetermináns: Az aldeterminánst megszorozzuk (-1)i+j-nel Az ij előjeles aldeterminánsán az i. sor és a j. oszlop elhagyásával kapott (n-1)x(n-1)-es mátrix determinánsát értjük.

Mártix: Egy T test feletti kxn-es mátrixon egy olyan téglalap alakú táblázatot értünk, melynek k sora és n oszlopa van és elemei a T-ből valók. jele: Tkxn Műveletek: +:

A,B є Tkxn

skalárral való *:

A+B jelentése: a megfelelő helyeken levő elemeket összeadjuk A є Tkxn,

jelentése: minden elemét A-nak megszorozzuk -val

єT

Az összeadás asszociatív, kommutatív, létezik egységelem, létezik inverze minden elemnek: az összeadásra nézve kommutatív csoport *:

A є Tkxn, B є Tnxr

→

C=AB є Tkxr

Csak akkor szorozható össze, ha A-nak ugyanannyi oszlopa van, mint amennyi sora B-nek A szorzás asszociatív, létezik egységelem. Determinánsok szorzástétele:

det(AB) = det(A) * det(B)

Mátrixok inverze: Csak négyzetes mátrixoknak létezik inverze. Legyen E az egységmátrix A mátrix inverzén egy olyan K mátrixot értünk, hogy:

Egy elem kétoldali inverze meghatározott.


A02-03

TARTALOMJEGYZÉK

2007. március 4. 23:10

Inverz létezésének feltételei: 1.

Ha detA 0

2.

Ha létezik a bal-/jobbinverz Biz.:

→

létezik az inverz →

detA 0

1.

N=M, mivel

M=EM=(NA)M=N(AM)=NE=N

2.

Inverz mátrix kiszámítása: A mátrix mellé leírjuk az nxn-es egységmátrixot. Ezután (A|E)-ből Gauss-eliminációval (E|B)-t kell csinálni ahol (B=A-1).

Mátrixok rangja: vektorok lineárisan függetlenek, ha csak úgy valósulhat meg, hogy

Oszloprang/sorrang: lineárisan független oszlopok/sorok száma Determinánsrang: a legnagyobb részmátrix mérete, melynek detA 0 oszloprang = sorrang = determinánsrang


A02-04

TARTALOMJEGYZÉK

2007. március 4. 23:34

Gráf szomszédossági mátrixa:

n pontú gráf → nxn-es mátrix A(G)→aij=

0, ha az i. és a j. pontok nem szomszédosak k, ha i. és j. pont között k párhuzamos el fut l, ha i=j és l db hurokél illeszkedik rá

Az At=mij eleme az i-ből j-be vezető t hosszúságú élsorozatok száma Gráf illeszkedési mátrixa:

n pontú, e élű gráf → nxe-es mátrix B(G)→bij=

0, ha az i. pont nem illeszkedik a j. élre 1, ha i. pont a j. él kezdőpontja -1, ha i. pont a j. él végpontja

Az n pontú c db összefüggő komponensből álló, hurokélmentes irányított gráf illeszkedési mátrixának rangja n-c.


A03-01

TARTALOMJEGYZÉK

2007. március 5. 17:53

Lineáris egyenletrendszer megoldása Gauss-eliminációval: A k egyenletből álló n ismeretlenes lineáris egyenletrendszer általános alakja: α11x 1 + α12x 2 + … + α1nx n = β1 α21x 1 + α22x 2 + … + α2nx n = β2 … αk1x 1 + αk2x 2 + … + αknx n = βk Elemi ekvivalens átalakítások: 1. 2. 3. 4.

egyenletet nem 0 skalárral szorozzuk egyenlet skalárszorosát hozzáadjuk egy másik egyenlethez két sort felcserélünk csupa 0 sort elhagyunk

Mátrixos felírás: Együtthatómátrix: A = (α…α) Kibővített mátrix: A|b = (α…α|β) Mátrixon a fenti ekvivalens műveletek az elemi sorekvivalens átalakítások. Fontos: csak sorokkal dolgozunk! Ha oszlopokkal is dolgoznánk, a változók sorrendjét változtatnánk meg, amit nehéz nyomon követni. A Gauss-elimináció algoritmusa:

1. Ha α 11 ≠ 0, → 2. pont. Ha α 11 = 0, de létezik j≠1-re α j1≠0, akkor a 1. és j. egyenletet felcseréljük, → 2. pont. Ha α 11 = 0 és minden j≠1-re α j1=0, → 3. pont. 2. leosztjuk α 11-el az első egyenletet, majd minden j>1-edik egyenletből kivonjuk az első egyenlet α j1-szeresét. 3. Az 1. pontot végrehajtjuk a soron következő egyenlettel.

Az eredmény a lépcsős alak lesz, a főátlóban található elemek a vezéregyesek, a vezéregyesek alatt minden elem 0.

A lépcsős alakból kiindulva, a Gauss-eliminációt visszafelé haladva elvégezve, a sorokból kinullázódnak a nem vezéregyes együtthatói. Ezt az alakot hívjuk redukált lépcsős alaknak (RLA). Megoldhatóság:

Az egyenletrendszer akkor és csak akkor megoldható, ha az RLA-ban nem fordul el olyan sor, amelyben az együtthatóknak megfelel rész csupa 0, a jobb oldali rész pedig nem 0 (nincs tilos sor). Megoldás egyértelműségének feltételei: Az egyenletrendszer akkor és csak akkor egyértelműen megoldható, ha (nincs tilos sor és) a vezéregyesek száma megegyezik az ismeretlenek számával.


A03-02

TARTALOMJEGYZÉK

2007. március 5. 18:12

nxn-es lineáris egyenletrendszer egyértelmű megoldhatóságának jellemzése a determináns segítségével: Legyen A Tnxn Ha D=detA=0, akkor az Ax=b egyenletrendszer vagy nem oldható meg, vagy pedig egynél több megoldása van.

Az Ax=0 homogén lineáris egyenletrendszernek akkor és csak akkor van nemtriviális megoldása, ha det A=0 . Általános egyenletrendszer megoldhatóságának jellemzése a rang segítségével Az Ax=b egyenletrendszer akkor és csak akkor oldható meg, ha r(A)=r(A|b) , azaz az együtthatómátrix rangja megegyezik a kibővített mátrix rangjával. Megoldhatóság esetén a megoldás akkor és csak akkor egyértelmű , ha a (közös) rang megegyezik az ismeretlenek számával. Sík egyenlete: Az irányvektorok nem használhatók, mert egy síkban végtelen sokat fel tudunk venni, ezért egy irányvektor nem határozza meg egyértelműen a síkot.

normálvektor:

n(n1,n2,n3)

adott pont:

P0(x 0,y0,z0)

tetszőleges pont: P(x,y,z)

(x-x0)n1+(y-y0)n2+(z-z0)n3 = 0 n1x+n2y+n3z = n1x0+n2y0+n3z0

x=x 0+t*v1 y=y0+t*v2 z=z0+t*v3

Egyenes egyenletrendszere: irányvektor:

v(v1,v2,v3)

adott pont:

P0(x 0,y0,z0)

tetszőleges pont: P(x,y,z)

A t valós paraméter az összes valós számon végigfut.


A03-03

TARTALOMJEGYZÉK

2007. március 5. 18:59

Az egyenes paraméteres egyenletrendszere:

Metszéspontok és metszésvonalak számítása: Ahhoz, hogy az egyenletekből konkrét koordinátákat, vagy paraméteres egyenletet kapjunk, egyenletrendszerként meg kell oldani. Illeszkedést, metszéspont és metszésvonal számolásához egyszerűen venni kell mindkét objektum egyenleteit, és meg kell oldani az egyenletrendszert.


A04-01

TARTALOMJEGYZÉK

2007. március 5. 19:15

Vektortér definíciója, példák.: Egy V nemüres halmaz vektortér a T kommutatív test felett, ha az alábbi vektortéraxiómák teljesülnek rajta: Ö. A V halmazon értelmezve van egy összeadás nevű művelet: egy u,v є V elempárhoz egyértelműen hozzárendeljük u+v є V-t. Ö1. Az összeadás asszociatív:

u,v,w є V esetén (u+v)+w = u+(v+w)

Ö2. Az összeadás kommutatív:

u,v є V esetén u+v = v+u

Ö3. Létezik nullelem: 0є V, amire 0+v = v+0 = v

Ö4. Létezik ellentett: v є V -hez -v є V,amire v+(-v) = (-v)+v = 0 S. A T test és a V halmaz között értelmezve van egy skalárral való szorzás nevű művelet: egy λ є T, u є V elempárhoz egyértelműen hozzárendeljük λu є V-t. S1. (λ+μ)u = λu+μu

S2. λ(u+v) = λu+λv S3. (λμ)v = λ(μv) S4. 1v = v

Példák:

- Tk×n, azaz a k×n-es mátrixok a T test felett a mátrixok szokásos összeadására és skalárral való szorzására nézve. - A valós számsorozatok a valós test felett a szokásos műveletekre - A komplex számok a valós test felett a komplex számok körében értelmezett műveletekre

Altér, lineáris kombináció, generált altér, generátorrendszer: Egy T test feletti V vektortér egy nemüres W részhalmaza altér V-ben, ha W is vektortér ugyanazon T felett ugyanazon V-beli műveletekre. Jelölés: W V. Lineáris kombináció: Legyen V vektortér T felett, a1,…, an є V, λ1,… λn є T. Ekkor a λ1a1 +… +λnan vektor az ai vektorok lineáris kombinációja. Generátorrendszer: a1,…, an є V vektorokat a V vektortér generátorrendszerének nevezik, ha V minden eleme előáll az ai vektorok lineáris kombinációjaként. A rendszer azt jelenti, hogy (a halmazzal ellentétben) ugyanaz a vektor többször is előfordulhat az ai-k között. Az a1,…, an є V vektorok által generált altéren az ai vektorok összes lineáris kombinációinak a halmazát értjük és ezt -nel jelöljük.

Lineáris függetlenség, a kétféle definíció ekvivalenciája: Def1.: Az a1,…, an є V vektorok lineárisan függetlenek, ha semelyik sem fejezhető ki a többiből lineáris kombinációval. Def2.: Az a1,…, an є V vektorok lineárisan függetlenek, ha λ1a1 +… + λnan = 0 csak úgy fordulhat elő, hogy minden λi = 0


A04-02

TARTALOMJEGYZÉK

2007. március 5. 19:42

Biz.: Def1 → Def2, indirekt tegyük fel, hogy Def2 nem teljesül Azaz van olyan λ, ami nem 0 (legyen ez pl. a λ1) és

innen λ1-el végigosztva:

Def2 → Def1, indirekt tegyük fel, hogy Def1 nem teljesül

Kicserélési tétel: Legyen f 1,…,fn lineárisan független rendszer és g1,…,gk generátorrendszer egy V vektortérben. Ekkor bármely f i-hez található olyan gj, hogy f 1…fi-1, gj ,fi+1,…fn is lineárisan független rendszer legyen (azaz bármelyik f kicserélhető alkalmas g-vel). Bázis, vektorok bázis szerinti felírásának egyértelműsége:

Bázison lineárisan független generátorrendszert értünk. 1. Egy u1, …, um vektorrendszer akkor és csak akkor bázis, ha a vektortér minden eleme egyértelműen előáll az u1, …, um vektorok lineáris kombinációjaként. 2. Egy vektortérben bármely két bázis azonos elemszámú. 3. Legyen f1,…,fn lineárisan független rendszer és g1,…,gk generátorrendszer egy V vektortérben. Ekkor n<=k. 4. Egy V 0 vektortér bármely (véges) generátorrendszere tartalmaz bázist.

5. Ha egy V vektortérnek van (véges) generátorrendszere, akkor bármely lineárisan független rendszer kiegészíthető bázissá. Dimenzió, a dimenzió egyértelműsége:

Egy V vektortér dimenzióján egy bázisának elemszámát értjük. Ha a vektortérnek nincs véges generátorrendszere, akkor a dimenziója végtelen. A 0 tér dimenziója 0. A V vektortér dimenzióját dimV-vel jelöljük. Mivel a bázis minimális generátorrendszer, ezért adott vektortér minden bázisának elemszáma megegyezik, tehát a dimenzió egyértelmű.


A05-01

TARTALOMJEGYZÉK

2007. március 5. 22:50

Lineáris leképezés fogalma, példák: Legyen V 1,V 2 vektortér ugyanazon T test felett. Ekkor A: V1→V2 lineáris leképezés, ha művelettartó: u,v є V 1 esetén A(u+v) = Au + Av u є V 1, λ є T esetén A(λu) = λ(Au) V 1 vektortér minden eleméhez egyértelműen hozzárendel egy V 2-beli elemet, de egy V 2-beli vektornak lehet több V 1-beli ősképe is. Példák: Legyen V 1=V 2 a síkvektorok szokásos vektortere (T=R). Ekkor lineáris leképezés: • Az origó körül történő forgatás; • Az origóból történő középpontos nagyítás; • Az origón átmenő bármely egyenesre való tükrözés

Lineáris leképezés mátrixa: Legyen a1,…,an egy bázisa V 1 vektortérnek, b1,…,bk pedig V 2-nek. A:V 1→V 2 lineáris leképezés a1,…,an, b1,…,bk bázispár szerinti mátrixán azt a k×n-es mátrixot értjük, amelynek j-edik oszlopában az Aaj vektornak a b1,…,bk szerinti koordinátái állnak. Jele [A] a,b.

Az [A]a,b mátrix oszlopai tehát tulajdonképpen rendre az aj báziselemek képei, mégpedig a bi báziselemek segítségével felírva. A mátrix természetesen erősen függ attól, hogy milyen bázisokat választottunk a két vektortérben, más bázispár esetén általában a mátrix is egészen más lesz. Vektor képének meghatározása a mátrix segítségével: Legyen V 1 vektortér bázisa a1,…,an , a V2 vektortér egy bázisa pedig b1,…,bk , továbbá A:V 1→V2 és v є V 1. Ekkor: ahol a jobb oldalon a két mátrix szorzata áll. Lineáris leképezések szorzata: A(B(u))=(AoB)(u)

Az AB szorzatot tehát úgy kapjuk, hogy előbb a második tényezőként szereplő B leképzést alkalmazzuk, majd ezután az A-t. Szorzat mátrixa:

Legyen V 1 vektortér bázisa a1,…,an , a V 2 vektortér egy bázisa pedig b1,…,bk , V 3 egy bázisa pedig c1,…,cr. Legyen továbbá B:V1→V 2 illetveA:V2→V3 . Ekkor


A05-02

TARTALOMJEGYZÉK

2007. március 5. 23:34

Lineáris leképezések magtere: KerA = {x є V 1: Ax = 0}

(A nullvektorra képződő elemek halmaza)

Lineáris leképezések képtere:

ImA = {y є V 2: létezik x є V 1; Ax = y}

(Ez a képelemek halmaza)

Magtér, képtér, altér mivolta:

ImA altér V 2-ben, KerA altér V 1-ben. Dimenziótétel: Legyen V 1 és V 2 vektortér a T test felett. Ekkor tetszőleges A lineáris leképezésre (V 1→V 2): dim(KerA) + dim(ImA) = dim(V1)


A06-01

TARTALOMJEGYZÉK

2007. március 5. 23:48

Lineáris transzformációk, illetve négyzetes mátrixok sajátértékei, sajátvektorai: Legyen V 1,V 2 vektortér ugyanazon T test felett. Ekkor A: V1→V2 lineáris leképezés, ha művelettartó: u,v є V 1 esetén A(u+v) = Au + Av u є V 1, λєT esetén A(λu) = λ(Au) Lineáris transzformáció: A lineáris leképezés speciális esete A: V→V (ugyanabba a vektortérbe képez le) Egy A є Tn×n mátrix sajátértéke a λ skalár, ha létezik u≠0 vektor, amire Au=λu. Azaz a transzformáció a vektort önmaga skalárszorosába képezi le. A fenti tulajdonságú u vektor sajátvektor. (0 nem lehet sajátvektor, de 0 lehet sajátérték!) Minden sajátvektorhoz csak egy sajátérték tartozik.

Sajátértékek és sajátvektorok meghatározása: Egy λ skalár akkor és csak akkor sajátértéke A-nak, ha az A-λE mátrix determinánsa nulla: det(A-λE) = 0.

Az A karakterisztikus polinomja:

Ennek a megoldásai a sajátértékek.

Sajátaltér, ennek altér volta: Minden sajátvektorhoz csak egy sajátérték tartozik. Egy adott λ sajátértékhez tartozó összes sajátvektor és a 0 alteret alkotnak. Ezt az alteret a λ-hoz tartozó sajátaltérnek nevezzük. Biz.:

1. Ha valamely v 0 vektorra λ és μ-vel is teljesül Av = λv = μv, akkor ebből v 0 miatt λ = μ következik. 2. Az adott halmazba pontosan azok a v vektorok tartoznak, amelyekre Av = λv. Azt kell igazolni, hogy ez a nemüres halmaz zárt az összeadásra és a skalárral való szorzásra. Legyen A v = λv és Az= λz, ekkor A(v+z) = Av + Az = λv + λz = λ(v+z), és hasonlóan A(αv) = λ(αv).


A07-01

TARTALOMJEGYZÉK

2007. március 6. 19:45

Kombinatorikus leszámlálási alapfeladatok, példák: • Permutáció: n elem összes lehetséges sorrendje: n! Példa: Egy hallgatónak n vizsgát kell letennie. Hány különböző sorrendben teheti ezt meg? Megoldás: Az első vizsgát n-féleképpen választhatjuk ki, a másodikat n-1-féleképpen stb. • Ismétléses permutáció: k1 darab első, k2 darab második, …, kr darab r-edik típusú elem lehetséges sorbaállításai a k1 + k2 + … + kr elem ismétléses permutációi: n! / (k1!k2!…kr!) Példa: Hány permutáció alkotható a MATEMATIKA szó betűiből? Az elemek (betűk) száma n=10. Ezek között megegyezők is vannak: két M betű, három A betű, és két T betű. Tehát k1=2, k2=3,k3=2 . Az ismétléses permutációk száma:

• Ismétlés nélküli variáció: n elemből az összes lehetséges sorrendben k darab különböző kiválasztása:

n! / (n-k)! Példa: Az egyetemen összesen n különböző óránk van. Ezek közül k darabot akarunk hétfőre tenni. Hányféle lehet a hétfői órarend? • Ismétléses variáció: n elemből képezhető k tagú sorozatok száma (ha egy-egy elem többször is szerepelhet): nk Példa: Hány 5-jegyű szám írható fel a 0, 1, 2 számjegyekkel? A számjegyek ismétlődhetnek. E három elem ötödosztályú ismétléses variációi közül azok alkothatnak ötjegyű számot, amelyek nem nullával kezdődnek. Ezek száma:

• Kombináció: n elemből az összes lehetséges sorrendben k darab különböző kiválasztása, a sorrend nem számít: n! / [(n-k)!k!] Példa: 90 elemből 5 elemet válasszunk ki: (5-ös LOTTO)

• Ismétléses kombináció: n elemből az összes lehetséges sorrendben k darab különböző kiválasztása, a sorrend nem számít, de az elemek többször is előfordulhatnak:

Példa: A büfében n darab süti közül kell kiválasztanunk k darabot, amelyet megveszünk. Egyből vehetünk többet is. Ezt hány féle képen tehetjük meg? Ezeket nem árt tudni levezetni, mert kérdezték szigorlaton hogy jönnek ki!


A07-02

TARTALOMJEGYZÉK

2007. március 6. 20:44

Összefoglaló: Permutáció

Variáció

Kombináció

Ismétlés nélküli

Ismétléses

Binomiális tétel:

Gráfelméleti alapfogalmak: gráf, egyszerű gráf, izomorfia: Egy gráf egy rendezett pár: G = (V,E), ahol V egy nemüres halmaz, E pedig az ebből a halmazból képezhető párok egy halmaza. Ha egy G gráfról beszélünk, akkor V(G)-vel, illetve E(G)-vel jelöljük a pontjainak/éleinek halmazát, míg a pontok és élek számát v(G)-vel, ill. e(G)-vel jelöljük. Azokat a gráfokat, amelyekben nincsenek hurokélek és többszörös élek, egyszerű gráfnak nevezzük. A G = (V,E) és a G’=(V’,E’) gráfok izomorfak, ha van olyan egy-egyértelmű megfeleltetés (bijekció) V és V’ között, hogy G-ben pontosan akkor szomszédos két pont, ha G’-ben a nekik megfelelő pontok szomszédosak, és szomszédos pontpárok esetén ugyanannyi él fut közöttük. Részgráf, feszített részgráf:

A G’ = (V’, E’) gráf a G = (V, E) gráf részgráfja, ha V’ V, E’ illeszkedik egymásra G’-ben, ha G-ben is illeszkedők.

E, valamint egy pont és egy él pontosan akkor

Ha E’ azokból az E-beli élekből áll, amelyeknek mindkét végpontja V’-ben van, és E’ az összes ilyen élet tartalmazza, akkor G’ a G gráf V’ által feszített részgráfja. Élsorozat, út, kör: Egy (v0,e 1,v1,e 2,…,vk-1,ek ,vk) sorozatot élsorozatnak nevezünk, ha e i a vi-1-et és vi-t összekötő él. Ha v0 = vk , akkor az élsorozat zárt. Ha a csúcsok mind különbözőek, akkor ez egy út. Ha az élsorozat zárt, és a csúcsok mind különbözőek, akkor ez egy kör a gráfban. Az út vagy kör hossza az őt alkotó élek száma.

Összefüggőség, összefüggő komponens: Komponens: maximális nagyságú feszített részgráf. Összefüggő komponensek: bármely két csúcs között vezet út. Ha a komponensek száma 1, akkor a gráf összefüggő.


A07-03

TARTALOMJEGYZÉK

2007. március 6. 21:10

Fa, feszítőfa: Fa: Az összefüggő körmentes gráfokat fáknak nevezzük. Feszítő fa: Az F gráf a G gráf feszítő fája, ha F fa, pontjainak halmaza megegyezik G pontjainak halmazával, és F élei szerepelnek G-ben is.

Fák egyszerű tulajdonságai: • Minden legalább 2 pontú fában van legalább két elsőfokú pont • Egy n pontú fa éleinek száma n-1 • Minden összefüggő G gráf tartalmaz feszítő fát Cayley-tétel:

Az ,1,2,…,n- pontokon nn-2 különböző fa adható meg.


A08-01

TARTALOMJEGYZÉK

2007. március 6. 21:36

Minimális költségű feszítőfa keresése: Legyen G=(V,E) egy összefüggő gráf. A G gráf egy körmentes összefüggő F=(V,E’) részgráfja a gráf egy feszítőfája. Legyen továbbá az éleken értelmezve egy c:E → R súlyfüggvény. Ekkor a G gráf egy F feszítőfája minimális költségű, ha költsége (a benne szereplő élek súlyainak összege) minimális G összes feszítőfája közül. Egy feszítőfa egy olyan fa, ami a G minden pontját tartalmazza, és az élei a G élei közül valók. A feladat: adott egy összefüggő irányítatlan gráf és az élein értelmezett súlyfüggvény. Meg kell keresni a gráf egy minimális költség feszítőfáját. Piros-kék algoritmus:

A minimális feszítőfa keresési algoritmusok közös elve, hogy valamilyen módon sorra nézik a G éleit és bizonyos éleket bevesznek a végső minimális feszítőfába, másokat pedig kihagynak. Tekinthetjük úgy mintha két színnel színeznénk a G éleit aminek során a kék élek belekerülnek a végeredményt jelent minimális feszítőfába, a pirosak pedig nem. Tekintsük a súlyozott élű G gráf éleinek egy részleges színezését, melynél bármely él piros, kék vagy színtelen lehet. Ez a színezés takaros, ha van G-nek olyan minimális költségű feszítőfája, ami az összes kék élet tartalmazza, és egyetlen piros élet sem tartalmaz.

A színezés során két szabályt használunk és egy élet csak akkor festünk be, ha a szabályok egyike alkalmazható: • Kék szabály: Válasszunk ki egy olyan 0 ≠ X V csúcshalmazt, amiből nem vezet ki kék él. Ezután a legkisebb súlyú X-ből kimenő színezetlen élet fessük kékre. • Piros szabály: Válasszunk G-ben egy olyan egyszerű kört, amiben nincs piros él. A kör egyik legnagyobb súlyú színtelen élét fessük pirosra. A piros-kék eljárás működése során mindig takaros színezésünk van. Ezen felül a színezéssel sosem akadunk el: végül G minden éle színes lesz. Következmény: Ha a piros-kék algoritmussal befestjük az összefüggő G=(V,E) gráf minden élét, akkor a kék élek egy minimális költség feszítőfa élei. Ez már akkor is igaz, amikor van |V|-1 kék élünk (és esetleg van még színezetlen él).

Az algoritmus tanulsága, hogy bárhol és bármikor alkalmazva sorra a két szabályt, végül mindenképpen egy minimális költségű feszítőfát kapunk. A recept helyessége szempontjából közömbös a sorrend viszont a hatékonyságból nem. A következő nevezetes módszerek az eljárás pontosított változatai. Prim módszere: Ez az algoritmus csak a kék szabályt alkalmazza. Legyen s a G egy rögzített csúcsa. Minden egyes színező lépéssel az s-et tartalmazó U kék fát bővítjük. Kezdetben az U csúcshalmaza ,s-, végül pedig az egész V. A következő kék élnek az egyik legkisebb súlyú élet választjuk azok közül, amelyek U-beli pontból U-n kívüli pontba mennek.


A08-02

TARTALOMJEGYZÉK

2007. március 6. 21:52

Prim módszer lépésszáma naiv implementáció esetén: Tfh. a gráf az élsúlyokat tartalmazó C szomszédossági-mátrixával adott. C*i,j+= ha (i,j) nem éle G-nek. Minden lépésben ki kell tudni választani az épp aktuális U és V\U halmazok közt futó legkisebb súlyú élek egyikét:

j є U , melyre c(i,j) minimális, ha i є V\U KÖZEL*i+= *, ha i є U c(i, KÖZEL*i+) amelyik i є V\U-ra minimális. Ekkor i lesz az U új pontja és ,i, KÖZEL*i+- az új él.

A minimum meghatározása < n lépés, ahol n=|V|. Amikor i belekerül az U-ba, a KÖZEL tömböt frissíteni kell: i lesz , ha c(i,j) < c(j, KÖZEL*j+), KÖZEL*i+=*

KÖZEL*j+=

A frissítés lépésszáma: O(n) egyébként nem változik

Az algoritmus lépésszáma: O(n)*O(n-1) = O(n2)

Prim módszer lépésszáma kupacos implementáció esetén: Az U és V\U között futó éleket tartalmazza a kupac. Az élek súlyait tároljuk a csúcsokban. MINTÖR-el kapjuk meg a két halmaz között futó legkisebb él súlyát. BESZÚR-ral vesszük bele az új kék csúcs minden szomszédját. Lépésszáma: O(eloge) Kruskal algoritmusa:

Vegyük növekvő sorrendben az éleket. • Ha a következő él nem alkot kört a kék élekből, akkor legyen kék • Ha a következő él kört alkot a kék élekből, akkor legyen piros Azt kell eldönteni, hogy az él végpontja ugyanabban a kék komponensben van-e. Megvalósítása UNIO-HOLVAN adatszerkezettel: Adott egy n elemű S halmaz és ennek bizonyos U1,…,Um részhalmazai, melyekre Ui U1 … Um = S Műveletek: UNIÓ(Ui ,Uj ) = az Ui ,Uj halmazokat az uniójukkal helyettesíti. HOLVAN(v) eredménye * v є S + annak részhalmaznak a neve, amelynek v eleme


Uj ≠ 0 (ha i≠j) és

A08-03

TARTALOMJEGYZÉK

2007. március 6. 23:18

Kruskal algoritmusban: S:=V(G), az Uj részhalmazok pedig az F által meghatározott kék gráf fáinak a csúcshalmazai. Az éppen vizsgált (v,w) él az F-hez adva pontosan akkor nem eredményez kört, ha a végpontok különböző komponensben vannak, azaz HOLVAN(v)≠HOLVAN(w). Miután (v,w) élet F-be tettük, egyesítenünk kell a v-t és a w-t tartalmazó kék fákat. Ezt egy UNIÓ művelettel érhetjük el. Az induló feltétel is teljesül, ugyanis kezdetben n darab egypontú fánk van.

Lépésszáma : O(elogn) Boruvka módszere: Minden pontot összekötünk a legközelebbi szomszédjával.

Minden egyes kék fához válasszuk ki a legkisebb súlyú belőle kimenő (színtelen) élet. Színezzük kékre a kiválasztott éleket. Ennek előnye, hogy nagyszerűen párhuzamosítható.


A09-01

TARTALOMJEGYZÉK

2007. március 8. 19:54

Legrövidebb utak keresése: A G gráf egy u-t v-vel összekötő u→v irányított útjának a hossza az úton szereplő élek súlyainak összege. A legrövidebb u→v úton egy olyan u→v utat értünk, amelynek a hossza minimális a G-beli u→v utak között. A G-beli u és v csúcsok távolságán d(u,v)-t értjük, amely 0, ha u=v és , ha nincs u→v út. Adott G=(V,E) irányított gráf, a c:E→R+ nemnegatív érték súlyfüggvény, és egy s є V csúcs (a forrás). Határozzuk meg minden v є V -re a d(s,v) távolságot. Szélességi bejárás, lépésszáma:

A gráf csúcsainak olyan bejárási sorrendje, ami szerint csak akkor foglalkozunk a kezdő ponttól távolabbi csúcsokkal, ha a közelieket már mind meglátogattuk. Az algoritmus: Kezdetben minden csúcs bejáratlan, azaz bejarva[i]=hamis minden i-re. Egy v csúcsból indulunk. bejarva[v]=igaz v-t berakjuk egy L listába amíg L≠0 x az első eleme l-nek minden y csúcsra, amire x→y є E ha bejarva[y]=hamis, akkor bejaras[y]=igaz y-t a lista végére rakjuk

Ha maradt még bejáratlan csúcs, akkor onnan folytatjuk. Lépésszáma:

Minden csúcs egyszer kerül be az L listába Minden élen egyszer járunk

Mátrixos esetben: O(n2) Éllistás esetben: O(n+e) Dijkstra algoritmusa (csak pozitív élsúlyok esetén): Egy a G csúcsaival indexelt D*+ tömböt használunk. D*v+ az eljárás során eddig megismert legrövidebb s→v utak hosszát tartalmazza. A D*v+ mennyiség mindenkor a felső közelítése lesz a keresett d(s,v) távolságnak. Kezdetben D[v]:=C[s,v] minden v є V csúcsra. Válasszuk ki ezután az s csúcs szomszédai közül a hozzá legközelebbit, vagyis egy olyan x є V \{s} csúcsot, melyre D*x+ (= C*s,x+) minimális. x-et betesszük s mellé a KÉSZ halmazba.

A KÉSZ halmaz azokat a csúcsokat tartalmazza, amelyeknek az s-től való távolságát már tudjuk. Ezek után módosítsuk a többi csúcs D*w+ értékét, ha az eddig ismertnél rövidebb úton el lehet érni oda xen keresztül, azaz ha D[x]+c(x,w) < D[w]. Most újra válasszunk ki az x є V\KÉSZ csúcsok közül egy olyat, amelyre D*v+ minimális. Majd megint módosítsuk a D*+-értéket, és így tovább, míg minden csúcs be nem kerül a KÉSZ halmazba.


A09-02

TARTALOMJEGYZÉK

2007. március 8. 20:34

Példa: s

a

b

0

3

0

2

5

0

2

0

2

c

d

KÉSZ

1

s

7

1

s, d

4

7

1

s, d, a

4

5

1

s, d, a, b s, d, a, b, c

Lépésszáma mátrixos és éllistás megadással:

Mátrixos esetben: O(n2) Éllistás esetben: O((n+e)logn) Bellman-Ford algoritmusa, lépésszáma mátrixos megadás esetén: Ez az algoritmus akkor is működik, ha bizonyos élsúlyok negatívak. Csupán annyit teszünk fel, hogy G nem tartalmaz negatív összhosszúságú irányított kört. Az egyszerűség kedvéért tegyük még fel, hogy V=,1,2,… ,n- és s=1. A T[i,j] a legrövidebb olyan 1→j irányított utak hossza, melyek legfeljebb i élből állnak.

1 lépésben:

T[1,v] = C[1,v]

2 lépésben:

T[2,v] = min{ (T[1,w]+C[w,v]), T[1,v] }

k lépésben:

T[k,v] = min{ (T[k-1,w]+C[w,v]), T[k-1,v] }

w

w

A minimumot felveszi egy s-ből v-be menő úton. Az n csúcsú G gráfban minden él n...1 élből áll Tehát T*n-1,v] az s-ből v-be menő legrövidebb út hossza. Lépésszáma:

A T táblázat egy értékének számítása n-1 összeadást és ugyanennyi összehasonlítást (minimumkeresés n elem közül) igényel. Mindez összesen O(n3) elemi műveletet igényel. Floyd algoritmusa, lépésszáma mátrixos megadás esetén: Tegyük fel továbbra is, hogy V=,1,2,… ,n-. A pontpárok távolságának kiszámítására egy nxn-es F mátrixot fogunk használni. Kezdetben F[i,j]=C[i,j].

for k=1 to n for i=1 to n for j=1 to n F[i,j]=min{ F[i,j], F[i,k]+F[k,j] }


A09-03

TARTALOMJEGYZÉK

2007. március 8. 21:48

Lépésszáma: Az algoritmus lépésszáma n3-el arányos, hiszen a domináló rész a három egymásba ágyazott ciklus. Ez nagyságrendben ugyanannyi, mintha a Dijkstra mátrixos változatát minden csúcsra mint forrásra lefuttatnánk.


A10-01

TARTALOMJEGYZÉK

2007. március 8. 21:50

Mélységi bejárás, lépésszáma: Az algoritmus: procedure mb(v) bejarva[v]=igaz minden w csúcsra, amire v→w є E ha bejarva[w]=hamis, akkor mb(w)

Lépésszáma:

Minden w-re egyszer hívjuk meg az eljárást Minden csúcsra a kimenő éleket kell végignézni O(n+e)

Ha az eredeti kezdőpontból nem érhető el minden pont (irányított gráf esetén) és bejártuk az eredeti kezdőpontot, akkor tetszőlegesen választható új kezdőpontként egy még nem bejárt csúcs. Mélységi és befejezési számozás:

Mélységi számozás: hányadiknak érjük el a csúcsot Befejezési számozás: hányadiknak fejezzük be (amikor bejártuk az összes gyerekét) Az élek osztályozása:

Egy G gráf x→y éle (T egy mélységi feszítőerdő): Faél: Előreél: Visszaél: Keresztél:

ha x→y éle T-nek ha x→ y nem faél, y leszármazottja x-nek T-ben és x<>y ha x leszármazottja y-nak T-ben (a hurokél is ilyen) ha x és y nem leszármazottai egymásnak

Az élek osztályozása az algoritmusban: x→y egy Faél: Előreél: Visszaél: Keresztél:

ha az él vizsgálatakor mszám*y+=0 mszám*y+>mszám*x+ mszám*y+<=mszám*x+ és bszám*y+=0 mszám*y+<mszám*x+ és bszám*y+>0

DAG tulajdonság ellenőrzése: Egy G irányított gráf DAG (directed acyclic graph), ha nem tartalmaz irányított kört.

A következő tétel azt jelenti, hogy a mélységi bejárással O(n+e) időben eldönthető DAG-e egy irányított gráf. Legyen G=(V,E) egy irányított gráf. Ha G egy DAG, akkor egyetlen mélységi bejárása során sincs visszaél. Fordítva: ha G-nek van olyan mélységi bejárása, amelyre nézve nincs visszaél, akkor G egy DAG.


A10-02

TARTALOMJEGYZÉK

2007. március 8. 22:51

DAG topologikus rendezése:

Legyen G=(V,E) (|V|=n) egy irányított gráf. G egy topologikus rendezése a csúcsoknak egy olyan v 1, ..., vn sorrendje, melyben x→y E esetén x előbb van, mint y (azaz ha x=vi ,y=vj , akkor i<j). Egy irányított gráfnak akkor és csak akkor van topologikus rendezése, ha DAG. Legrövidebb és leghosszabb út keresése DAG-ban: Topologikus rendezést használva lineáris időben, azaz O(n+e) lépésben megoldható a legrövidebb út keresés. Tegyük fel hogy már meghatároztuk a G csúcsainak egy x 1, x 2, ..., x n topologikus rendezését. Feltehetjük, hogy s=x 1, mert csak a kisebbtől a nagyobb sorszámú felé mehet él.

Ezt használva sorban minden i-re kiszámíthatjuk a d távolságokat. Az a lényeg, hogy ha (x i, x j) él, akkor j
A leghosszabb út keresése DAG-okban ugyanúgy lineáris művelet, csak az előz algoritmusban nem minimumot, hanem maximumot számolunk. Tehát:

Összegezve: Ha G egy éllistával adott súlyozott élű DAG, akkor az egy forrásból utak meghatározásának feladatai O(n+e) lépésben megoldhatók. Pert módszer: A Program Evaluation and Review Technique tervezési módszer súlyozott élű DAG-okkal ábrázolja egy összetett feladat részei közötti viszonyokat. A csúcsok a nagy feladat részei, eleminek mondható teendői.

Az x teendőből irányított él vezet az y teendőbe, ha x-et előbb kell elvégezni, mint y-t. Külön csúcsok (pl. K és V) jelölik a teljes feladat kezdetét és végét. Értelmesen definiált élekkel minden topologikus rendezésnél K lesz az első és V az utolsó él. Az éleken nemnegatív súlyok vannak. c(x,y) azt mondja meg, hogy mennyi időnek kell eltelnie x megkezdésétől y megkezdéséig. Az x részfeladat legkorábbi kezdési idő pontja l(K,x) lesz, ami O(n+e)-ben megtehető. A módszertan fontos fogalmai a kritikus út, él és csúcs. Kritikus úton olyan K→V utat értünk, amelynek hossza l(K,V). Az elnevezés onnan ered, hogy ha a kritikus utakon késve kezdődnek a tevékenységek, ez az egész munka befejezését késlelteti. A kritikus csúcsokat és éleket a G PERT-gráf topologikus rendezésében visszafele azaz V-től K felé haladva határozhatjuk meg. Első lépésként megjelöljük V-t mint kritikus csúcsot. Általában tfh. az x i csúcsnál tartunk és x i kritikus csúcs. Ekkor az x j→x i élet és az x j csúcsot akkor kell megjelölnünk, ha l(K, xi )=l(K, xj )+c(xj, xi) teljesül . Az eljárás során minden élet egyszer veszünk szemügyre, így a költség O(n+e). Egy éllistával adott PERT-gráf esetén a részfeladatok legkorábbi kezdési ideje, ezenfelül a kritikus élek és csúcsok lineáris időben meghatározhatók.


A10-03

TARTALOMJEGYZÉK

2007. március 21. 12:47

Példa:


A11-01

TARTALOMJEGYZÉK

2007. március 8. 23:42

Síkbarajzolhatóság és kapcsolata a gömbre rajzolhatósággal: Ha egy gráf lerajzolható a síkba úgy, hogy az élei csak a csúcsokban messék egymást, akkor a gráf síkbarajzolható. A síkbarajzolt gráf a síkot tartományokra osztja. Hasonlóan definiáljuk a gömbre rajzolható gráfot. Egy G gráf pontosan akkor síkbarajzolható, ha gömbre rajzolható. Egy síkban lévő gráf leképezhető egy gömbfelületre oly módon, hogy ezt a gömbfelületet valamelyik pontjával a síkra helyezzük, az érintkezési pontot tekintjük a gömbfelület déli pólusaként, és az északi pólusból, mint vetítési pontból olyan egyenes vonalakat húzunk, amelyek a síkban lévő gráf minden egyes pontját összekötik az északi pólussal. Ezeknek a vonalaknak egy-egy további metszéspontja van a gömbfelülettel, ezek szolgáltatják a kívánt vetítést. Ez az ún. sztereografikus projekció. Ez az eljárás megfordítható, ha az északi pólus nem pontja a gráfnak és nem halad át rajta él, így a gömbre rajzolt gráfok leképezhetők a síkba.

Euler-tétel: Egy összefüggő síkbeli gráf, amelynek n csúcsa, e éle és t tartománya van (beleértve a külső, nem korlátos tartományt is), eleget tesz az Euler-formulának: n+t=e+2

Felsőbecslés az élek számára: Ha G egyszerű, síkbarajzolható gráf és pontjainak száma legalább 3, akkor az előbbi jelölésekkel: e

3n-6

Biz.: Mivel a gráf síkbarajzolható és egyszerű, minden tartományát legalább 3 él határolja. Nyilvánvaló, hogy egy él viszont legfeljebb két tartományt határához tartozik. Így 3t 2e. Az Euler-formulát felhasználva a 3(e+2-n) 2e egyenlőtlenséget kapjuk. Ebből átrendezéssel következik, hogy e Ha G-ben minden kör legalább 4 hosszú, akkor e

3(n-2)= 3n-6

2n-4 is teljesül. Bizonyítása hasonlóan.

Kuratowski-gráfok, ezek síkba nem rajzolhatósága:

Az ábrán látható két gráfot Kuratowski-gráfoknak nevezzük. Az első K5 az öt pontú teljes gráf. A másik , a K3,3 “három ház – három kút” gráf.


A11-02

TARTALOMJEGYZÉK

2007. március 9. 18:51

A Kuratowski-gráfok nem rajzolhatók síkba. Biz.: K3,3:

K5:

e=9, n=6, minden kör 4él ha síkbarajzolható volna, akkor e

2n-4, azaz 9

ha síkbarajzolható volna, akkor e

3n-6, azaz 10

2*6-4, ami ellentmondás

3*5-6, ami ellentmondás

Kuratowski tétel:

Egy gráf síkbarajzolhatóságát nyilván nem befolyásolja, hogyha egy élet egy 2 hosszú úttal helyettesítünk, azaz egy élet egy új 2 fokú csúcs felvételével két élre bontunk, vagy ha 2 fokú csúcsra illeszked éleket egybeolvasztunk, és a csúcsot elhagyjuk.

A G és H gráfok topológikusan izomorfak,ha a fent említett transzformációk ismételt alkalmazásával izomorf gráfokba transzformálhatóak. Egy gráf akkor és csak akkor síkbarajzolható, ha nem tartalmaz olyan részgráfot, amely topológikusan izomorf K3,3-mal vagy K5-el. Fáry-Wagner-tétel:

Ha G egy egyszerű, síkbarajzolható gráf, akkor létezik olyan síkbeli ábrázolása is, hogy minden élet egy egyenes szakasszal rajzolhatunk le. Dualitás, gyenge izomorfia fogalma, absztrakt dualitás: A G gráfhoz gyártsunk egy G* gráfot az alábbi utasítással: G tartományaihoz rendeljük az új G* gráf pontjait és G*-ban akkor kössünk össze két pontot éllel, ha a megfelelő két G-beli tartománynak van közös határvonala. Az így gyártott G* gráfot a G duálisának nevezzük.

Két gráfot gyengén izomorfnak nevezünk, ha élei között kölcsönösen egyértelmű és körtartó leképezés hozható létre. A G és G* gráfok egymás absztrakt duálisai, ha létezik köztük olyan, kölcsönösen egyértelmű leképezés, mely kört vágásba, vágást körbe visz. Whitney tételei:

I. Egy gráfnak akkor és csak akkor létezik absztrakt duálisa, ha síkbarajzolható. II. Legyen G síkbarajzolható gráf és H vele gyengén izomorf. Ekkor H is síkbarajzolható, G* és H* szintén gyengén izomorfak, végül (G* )* és (H* )* gyengén izomorfak G-vel, ill. H-val.


A12-01

TARTALOMJEGYZÉK

2007. március 9. 19:37

Hamilton-körök és –utak: Egy G gráfban Hamilton-körnek nevezünk egy H kört, ha G minden pontját (pontosan egyszer) tartalmazza. Egy utat pedig Hamilton-útnak, ha G minden pontját pontosan egyszer tartalmazza. Szükséges feltétel Hamilton-kör/út létezésére: Ha a G gráfban létezik Hamilton-kör, akkor bárhogy elhagyva k darab pontot, a gráf maximum k komponensre esik szét. Azaz, ha a G gráfban létezik k darab olyan pont, amelyeket elhagyva a gráf több mint k komponensre esik szét, akkor nem létezik G-ben Hamilton kör. Ha a G gráfban létezik Hamilton-út, akkor bárhogy elhagyva k darab pontot, a gráf maximum k+1 komponensre esik szét. Azaz, ha létezik k darab olyan pont melyeket elhagyva G több mint k+1 komponensre esik szét, akkor nem létezik G-ben Hamilton út. Biz.: Vesszük azt a k darab csúcsot, melyek elhagyásával G több mint k komponensre esik szét. Az elhagyott pontok közötti részen az eredeti Hamilton-kör élei futnak így ezek már nem összefüggőek. Ilyen „ívekből” k darabot kapunk. Vagyis G nem eshet szét k-nál több komponensre.

Csak arra használhatók a szükséges tételek, hogy kimutassuk, nincs a gráfban H-kör. Ha G Hamilton-gráf, akkor minden pontjának fokszáma legalább 2. Elégséges feltételek: Ore és Dirac tétele:

Ore: Ha az n pontú G gráfban minden x, y є V(G) nem szomszédos csúcsra fenáll d(x)+d(y) n, akkor G-ben van Hamilton-kör. Dirac: Ha egy n pontú G gráfban minden pont foka legalább n/2, akkor a gráfban létezik Hamilton-kör.

Biz.: Ore-tételből következik, mert ha minden pont foka legalább n/2, akkor d(x)+d(y) n/2+n/2 n Hamilton-kör keresés bonyolultsága: Legyen H a Hamilton-kört tartalmazó gráfokból álló nyelv. Állítás: H NP-teljes.

Euler-körök és –utak: Egy G gráf Euler-körének nevezünk egy zárt élsorozatot, ha az élsorozat pontosan egyszer tartalmazza G összes élét. Ha az élsorozat nem feltétlenül zárt, akkor Euler-utat kapunk. Minden Euler-kör egyben Euler-út is.


A12-02

TARTALOMJEGYZÉK

2007. március 9. 20:11

Euler-kör és út létezésének szükséges és elégséges feltétele: Egy G gráfban akkor és csak akkor van Euler-kör, ha G minden pontjának fokszáma páros és G összefüggő. Biz.:

• Ha az Euler-kör vonalán körüljárjuk a gráfot, akkor minden pontba ha bemegyünk, akkor ki is megyünk belőle egy másik, még be nem járt élen. A gráf összefüggő volt különben nem lehetett volna benne Euler-kör.

• G pontszámára való indukcióval. A háromszög a legkisebb pontszámú ilyen gráf, erre igaz. Tegyük fel, hogy minden G-nél kisebb pontszámú gráfra igaz az állítás. Létezik zárt élsorozat: Induljunk el a gráf egy tetszőleges pontjából, és haladjunk az élek mentén úgy, hogy egy élen kétszer nem megyünk át. Ha olyan pontba érünk, amelyb ől nem vezet ki olyan él, amelyen még nem haladtunk át, akkor ez csak a kiindulópont lehet, mivel minden pont foka páros. Válaszzuk ki a zárt élsorozatok közül a maximálisat, nevezzük E nek, ez Euler-kör mivel: Indirekt tegyük fel, hogy E nem egy Euler-köre G-nek. Vizsgáljuk a G' gráfot, amelyet úgy kapunk, hogy a G gráfból elhagyjuk az E-ben szereplő éleket. Ha E nem Euler kör, akkor G' nem csak izolált pontokból áll, hanem vannak benne komponensek, ráadásul ezekben minden fokszám páros (zárt sétát hagytunk el), tehát az indukciós feltevés alapján ezekben biztosan van Euler kör. Ekkor viszont E nem a maximális zárt élsorozat volt: E és a komponens közös pontjából elindulva végigjárhatjuk a komponenst, majd E-t. Ez ellentmond az indirekt feltevésnek, vagyis E valóban Euler-kör. Egy G gráfban akkor és csak akkor van Euler-út, ha 0 vagy 2 pont kivételével G minden pontjának fokszáma páros és G összefüggő. Biz.:

• Mint az előző • 0 páratlan fokú pont: az előző tétel. 2 páratlan fokú pont: kössük össze ezeket egy újabb e éllel. A keletkező G' gráfban minden pont foka páros lesz, így az előző tétel értelmében van benne Euler-kör, ami a definíció szerint tartalmazza az e élet is. Hagyjuk el ebből az Eulerkörből az e élet, így egy Euler-utat kaptunk G-ben.


A13-01

TARTALOMJEGYZÉK

2007. március 9. 20:42

Gráfok színezése: A G gráf színezésén egy f:V → {1,... , k- leképzést értünk, melyre ha (v,w) є E akkor f(v)≠f(w) . Azaz egy G hurokmentes gráf k színnel kiszínezhető, hogyha minden csúcsot ki lehet színezni k szín felhasználásával úgy, hogy bármely két szomszédos csúcs színe különböző legyen. (G) fogalma és viszonya (G)-hez, illetve (G)-hez:

G kromatikus száma (G)=k , ha G k színnel kiszínezhető, de k-1 színnel nem. Egy ilyen színezésnél az azonos színt kapott pontok halmazát színosztálynak nevezzük. G egy teljes részgráfját klikknek nevezzük. A G-ben található maximális méretű klikk méretét, azaz pontszámát (G)-vel jelöljük és a gráf klikkszámának nevezzük. Minden G gráfra (G) (G). Ha a maximális fokszám G-ben , akkor

G

(G)+1. Azaz:

G

G

(G)+1.

Brooks tétele: Ha G egyszerű, összefüggő, nem teljes gráf, és nem páratlan hosszúságú kör, akkor ekkor a kromatikus szám nem nagyobb, mint a maximális fokszám.

G

Mycielski konstrukciója: Minden k ≥ 2 egész számra van olyan Gk gráf, hogy ω(Gk) = 2 és (Gk) = k. Síkbarajzolható gráfok kromatikus száma: Ha G síkbarajzolható gráf, akkor (G) = 4. Ez a négyszíntétel. Intervallumgráfok színezése, perfekt gráf fogalma: *Berge+ Egy G gráf perfekt, ha hogy G' G' .

G

G és G minden G’ feszített részgráfjára is teljesül,


(G), azaz

A13-02

TARTALOMJEGYZÉK

2007. március 9. 21:23

Minden intervallumgráf perfekt. Biz.: Mivel egy intervallumgráf feszített részgráfja is intervallumgráf, ezért elég belátni, hogy a klikkszámuk megegyezik a kromatikus számukkal. Legyen ω(G)=k. Mivel (G)≥ω(G), elég belátni, hogy (G)≤k. Kezdjük el színezni a pontoknak megfelelő intervallumokat balról jobbra. A még színezetlen intervallumok közül mindig azt színezzük ki, amelyiknek a baloldali végpontja a legbalrább van. Ha egy intervallumot a k+1-dik színnel kéne kiszíneznünk, akkor az azt jelenti, hogy ennek az intervallumnak a bal vége benne van már k intervallumban, amelyeket már kiszíneztünk 1,2…k színekkel. Így van k+1 intervallum, amelyek közül bármely kettő metszi egymást, azaz van a gráfban egy k+1 méretű klikk, ez viszont ellentmond a feltevésünknek, miszerint a maximális klikk k-as. 3-SZÍN nyelv bonyolultsága:

3-SZÍN є NP. A nyelv az NP legnehezebbjei közül való, a 3-SZÍN nyelv NP-teljes. Élkromatikus szám,

e(G) viszonya

(G)-hez, Vizing-tétel:

Egy G gráf élei k színnel kiszínezhetők, hogyha minden élet ki lehet színezni k szín felhasználásával úgy, hogy két szomszédos él színe különböző legyen. G élkromatikus száma e(G)=k , ha G élei k színnel kiszínezhetők, de k-1 színnel nem. Az élkromatikus szám nem lehet kisebb a maximális fokszámnál, hiszen az egy pontra illeszkedő éleket mind különböző színekre kell színezni. Azaz: (G) e G

Vizing tétele: Ha G egyszerű gráf, akkor

e

G

G


A14-01

TARTALOMJEGYZÉK

2007. március 9. 21:46

Páros gráfok: Egy G gráfot páros gráfnak nevezünk, ha a G pontjainak V(G) halmaza két részre, egy A és B halmazra osztható úgy, hogy G minden élének egyik végpontja A-ban, másik végpontja B-ben van. Ennek jelölése: G = (A,B). A Ka,b-vel jelölt teljes páros gráf olyan G=(A,B) páros gráf, ahol |A|=a és |B|=b és amelyben minden A-beli pont össze van kötve minden B-beli ponttal. pl. K3,3 Kuratowski-gráf

Egy G gráf akkor és csak akkor páros, ha nincs benne páratlan hosszúságú kör. Párosítások páros gráfban: Párosításnak nevezünk egy élhalmazt, ha semelyik két élnek nincs közös végpontja. Az ilyen éleket független éleknek is nevezzük. A párosítás az élek végpontjait fedi le. Egy párosítást teljes párosításnak nevezünk, ha a gráf minden pontját lefedi (mindenkinek van párja), részlegesnek, ha csak részüket. Magyar módszer és lépésszáma: Legyen G egy tetszőleges gráf, és E’ a G egy párosítása. Egy G-beli utat E’-alternáló útnak hívunk, ha egy nem párosítottból indul és felváltva tartalmaz párosított és nem párosított éleket. Legyen E’ a G=(V,E) gráf egy párosítása. Ekkor egy olyan E’-alternáló út, melynek mindkét végpontja párosítatlan, E’-re nézve javító út, vagy röviden E’-javító út. Ha E’-re nézve nincs javító út G-ben, akkor E’ a G egy maximális párosítása.

Algoritmus: • Független élek felvétele, amíg lehetséges • Javító utak bevezetése, növelése a párosításnak, amíg lehet

Ha a gráf éllistával adott, akkor O(e) költséggel megvan az alternáló erdő konstruálása. Legfeljebb n/2-szer kell javító utat keresni, így: A magyar módszer időigénye O(ne). König tétele:

Ha G = (A,B) páros gráf, akkor (G) = τ(G) és (ha nincs G-ben izolált pont) α(G) = ρ(G) (G)

független élek maximális száma.

τ(G)

lefogó pontok minimális száma

α(G)

független pontok maximális száma

ρ(G)

lefogó élek minimális száma

Hall tétele: Egy G = (A,B) páros gráfban akkor és csak akkor van A-t lefedő párosítás, ha minden X |N(X)| ≥ |X|, ahol N(X)-el jelöljük egy X ponthalmaz szomszédainak halmazát.


A részhalmazra

A14-02

TARTALOMJEGYZÉK

2007. március 9. 22:48

Frobenius tétele: Egy G = (A,B) páros gráfban akkor és csak akkor van teljes párosítás, ha |A| = |B| és |N(X)| ≥ |X| minden X A-ra. Párosítások tetszőleges gráfban, (G) és τ(G) kapcsolata, Tutte tétele: Egy G gráfban akkor és csak akkor létezik teljes párosítás, ha minden X V(G) -re cp(G-X) X| , azaz akárhogyan hagyunk el a gráfból néhány pontot, a maradékban a páratlan komponensek száma ennél több nem lehet. Biz.: Legalább egy piros él kilép.

Gallai tételei:

• α(G)+τ(G) = n

minden hurokmentes gráfra

•

minden G gráfra, amelyben nincs izolált pont

(G)+ρ(G) = n

ahol n a csúcsok száma

Biz.: 1:


A15-01

TARTALOMJEGYZÉK

2007. március 10. 16:03

Hálózat, hálózati folyamok:

Legyen G egy irányított gráf. Rendeljünk minden élhez egy c(e) nemnegatív valós számot, amit az él kapacitásának nevezünk. Jelöljünk ki továbbá két s,t pontot G-ben, melyeket termelőnek illetve fogyasztónak hívunk. Ekkor a (G;s;t;c) négyest hálózatnak nevezzük. f függvény rendeljen a hálózat minden éléhez egy nemnegatív valós számot. f megengedett, ha minden e élre f(e)≤c(e), és minden v≠spontra érvényes a csomóponti törvény:

A megengedett függvényeket folyamoknak nevezzük. A folyam értéke: mf=

Egy élet telítettnek hívunk egy folyamban, ha f(e)=c(e), és telítetlennek, ha f (e) ≤ c(e) .

A javító utas algoritmus: Legyen a gráfban s=v0, v1…vk-1,vk=t egy út, aminek most nem kell feltétlenül az irányítás szerint haladnia. Minden t felé mutató élen x-szel növeljük az átfolyó mennyiséget, a visszafelé mutató éleken pedig ugyanennyivel csökkentsük. x megengedett maximuma ott van, ahol az egyik t felé mutató él telített, vagy az egyik s felé mutató el 0 értékű lesz. Az út minden egyes pontjába befolyó és onnan kifolyó mennyiség egyensúlyban marad, és betartottuk a kapacitáskorlátozást, tehát ez az út megengedett. A t pontba folyó mennyiséget figyelve viszont láthatjuk, hogy a folyam értéke x -szel nőtt.

Ford-Fulkerson tétel: Vágás: Azoknak az éleknek a C halmazát, amelyeknek egyik végpontja X-beli, a másik V(G)\X-beli a hálózati folyam egy (s,t) vágásának nevezzük.

A vágás értéke, c(C), azon az éleken levő kapacitások összege, amelyek egy X-beli pontból egy V(G)\X-beli pontba mutatnak. Ezeket előremutató éleknek nevezzük. Tehát a vágás értékében nem játszanak szerepet a visszafelé mutató élek, vagyis azok, amelyek egy X-beli pontba mutatnak. A maximális folyamérték egyenlő a minimális vágás értékével: max mf = min c(C)


A15-02

TARTALOMJEGYZÉK

2007. március 10. 16:47

Edmonds-Karp tétel: Ha mindig a legrövidebb (értsd legkevesebb élből álló) javító utak egyikén javítunk, akkor polinom sok lépésben eljutunk a maximális folyamig. Egészértékűségi lemma: Ha a kapacitások egész számok, akkor a maximális folyam értéke is egész szám, és található olyan maximális folyam, amely minden élhez egész számot rendel. Ez az algoritmusból következik. A folyamprobléma általánosításai:

• Tegyük fel, hogy a hálózatban több termelő s1,s2,..., sk és több fogyasztó t1, t2, …, tl van. A feladat az összes termelőtől az összes fogyasztóig eljutó termékmennyiség maximalizálása. Vegyünk fel két s’, t’ pontot, és kössük össze s’-t s1,s2,..., sk -val, t1, t2, …, tl-t pedig t’-vel, az új élek mindegyikének kapacitása legyen . Ha ebben a hagyományos folyamban meghatározzuk a maximális folyamot, akkor az eredeti éleken szereplő folyamértékek a keresett értékek.

• Ha nem csak az élekhez, hanem a pontokhoz is rendelünk c(v) kapacitásokat: pontszéthúzás művelete:

• Még könnyebb a visszavezetés abban az esetben, amikor megengedünk irányítatlan éleket. Ekkor az ilyen c kapacitású ,u,v- él helyett felveszünk két c kapacitású (u,v) és (v,u) élet.

Menger tételei: • Ha G egy irányított gráf, s,t є V(G) , akkor az s-ből t-be vezető páronként élidegen irányított utak maximális száma megegyezik az irányított s-t utakat lefogó élek minimális számával. • G irányított gráf s-t pontjai közötti pontidegen utak max száma egyenlő az összes s→t irányított utat lefogó pontok minimális számával (kivéve az s és t pontokat).


A15-03

TARTALOMJEGYZÉK

2007. március 10. 17:28

• G irányítatlan gráf s-t pontjai közötti élidegen utak max száma egyenlő az összes s-t utat lefogó irányítatlan élek minimális számával. • Egy G irányítatlan gráf s-t közötti irányítatlan pontidegen utak maximális száma megegyezik az összes irányítatlan s-t utat lefogó pontok minimális számával. Többszörös összefüggőség, élösszefüggőség: Egy G gráfot k-szorosan összefüggőnek nevezünk, ha legalább k+1 pontja van, és akárhogy hagyunk el belőle k-nál kevesebb pontot, a maradék gráf összefüggő marad. A gráf k-szorosan élösszefüggő, ha akárhogy hagyunk el belőle k-nál kevesebb élet, összefüggő marad.

Megjegyzés: a (pont)összefüggőség erősebb (kisebb), mint az élösszefüggőség. Menger tétele az összefüggőségre: A legalább 3 pontú G gráf akkor és csak akkor 2-szeresen összefüggő, ha tetszőleges két pontján át vezet kör. Igaz az is, hogy akkor és csak akkor 2-szeresen összefüggő, ha bármely két élén át vezet kör. Dirac tétele: Ha G k-szorosan összefüggő, akkor bármely k csúcsán keresztül megy kör.


A16-01

TARTALOMJEGYZÉK

2007. március 10. 17:42

Oszthatóság, felbonthatatlan és prímtulajdonságú számok: a osztója b-nek, ha létezik olyan k, hogy b=ka , jelölése: a|b.

p ≠-1,0,1 fölbonthatatlan, ha p=ab, akkor a=±1 vagy b=±1

(kizáró vagy)

p ≠-1,0,1 prím, ha p|ab akkor p|a vagy p|b (megengedő vagy) Prímszámnak hívunk egy egynél nagyobb pozitív p számot, ha nincs valódi osztója, vagyis ha a pozitív m szám osztója p-nek, akkor m=1 vagy m=p teljesül. A természetes számok körében a fölbonthatatlanok megegyeznek a prímekkel. Tehát p prím, ha csak 1 és p osztja. Ilyenkor nincs valódi osztója. Például: A 3 felbonthatatlan és prím is, de a -3 felbonthatatlan, de nem prímszám. A számelmélet alaptétele: Minden 1-nél nagyobb egész szám a sorrendtől és előjelektől eltekintve egyértelműen felírható prímszámok szorzataként. Osztók száma: Legyen n=p1 p2 pk és d|n. Ekkor d előáll d=p1 p2 alakú szám osztója n-nek. Ekkor az osztók száma:

Mivel Legyen n=p1

p2

i

i

ezért

i

i +1 (0...

pk valamint m=p1 p2

i)

pk , ahol

i

i. Minden ilyen

értéket vehet fel.

pk

Ekkor n és m legnagyobb közös osztója (n,m)=p1min{ A legkisebb közös többszöröse pedig *n,m+=p1max{

} p min{ 2 } p max{ 2

} }

pkmin{ pkmax{

} }

Az a,b számokat relatív prímeknek nevezzük, ha legnagyobb közös osztójuk 1. A prímek számának végtelensége: Végtelen sok prímszám van. Biz.: indirekt:


A16-02

TARTALOMJEGYZÉK

2007. március 10. 18:30

Kongruencia fogalma, alapműveletek kongruenciákkal: Definíció1: Azt mondjuk, hogy az a szám kongruens b-vel az m modulusra nézve, ha az (a-b) osztható m-mel, azaz m|a-b. Jelölése: a b Definíció2: Az a és b kongruens mod m, ha a és b is ugyanazt a maradékot adják m-mel osztva. A kongruenciareláció ekvivalenciareláció, vagyis teljesülnek következő tulajdonságok: 1. reflexív

a a (mod m)

2. szimmetrikus ha a b (mod m) akkor b a (mod m) 3. tranzitív

ha a b (mod m) és b c (mod m) akkor a c (mod m)

Alapműveletek: ha a b (mod m) illetve c d (mod m) akkor

1. a+c b+d (mod m) 2. a-c b-d (mod m) 3. ac bd (mod m) 4. ak bk (mod m)

Lineáris kongruenciák, a megoldhatóság szükséges és elégséges feltétele: Legyenek a,b,c egész számok. Az ax b (c) lineáris kongruenciában az x ismeretlen, és keressük azon x számokat, amelyre a c|ax-b igaz. Nyílván ha x kielégíti a feltételt, akkor kc+x is tetszőleges k egész számra, így a megoldásokat modulo c fogjuk keresni. Az ax b (c) kongruencia akkor és csak akkor oldható meg, ha (a,c)|b. Biz.:

Wilson tétele:

Minden k>=2 egészekre:

(k-1)!

-1 (mod k)

ha k prím

(k-1)!

2 (mod k)

ha k=4

(k-1)!

0 (mod k)

ha k>=6 és összetett


A17-01

TARTALOMJEGYZÉK

2007. március 10. 19:16

Teljes és redukált maradékrendszer, a

függvény definíciója:

A kongruencia segítségével maradékosztályokba soroljuk az egész számokat. Ugyanabba a maradékosztályba azok a számok fognak tartozni, amik m-mel osztva ugyanazt a maradékot adják. függvény: Az 1, …, m között m-hez relatív prím számok száma. Speciálisan (p)=p-1, ha p prímszám, vagy (m)=(p-1)(q-1) , ha m=pq, ahol p és q két különböző prímszám. Teljes maradékrendszer: {a1,…, ak - teljes maradékrendszert alkot mod m, ha minden mod m maradékosztályt pontosan egy ai képvisel, tehát teljesül: 1. k=m 2. ha i≠j akkor ai aj (mod m) Redukált maradékrendszer: {b1,…, bk } redukált maradékrendszer, ha i esetén (bi, m)=1, és az összes ilyen maradékosztályt képviseli pont egy bi: 1. k= (m) 2. ha i≠j akkor bi bj (mod m) 3. (bi, m)=1 Euler-Fermat-tétel: (a,m)=1, akkor a

(m)

1 (mod m)

Kis Fermat-tétel:

Bármely p prímre és a egészre:

ap a (mod p)

Biz.:

Euklideszi algoritmus: Az algoritmus a és b legnagyobb közös osztóját, d(a,b)-t határozza meg (legyen a>b). A maradékos osztáson alapszik. a = h1b + m1 (h1 egész szám, m1

A18-01

TARTALOMJEGYZÉK

2007. március 10. 22:11

Számelmélet és algoritmusok: alapműveletek, hatványozás az egészek körében: Egy k-jegyű x szám leírásához log10x számjegy kell. Ha két x,y szám között akarunk valamilyen alapműveletet megvalósítani, akkor az input hossza log10x + log10y log10xy azaz x*y logaritmusával arányos. Az írásbeli összeadás és kivonás a számjegyek számával arányos, így ezek polinom rendű (ráadásul lineáris) algoritmusok. Az írásbeli osztás és szorzás is polinomrendű algoritmusok (csak nem lineárisak). A hatványozás nem végezhető el polinom időben, mert pl. 2x végeredményének kiírásához már log2x=x lépés kell, ami az input hosszának (log x-nek) exponenciális függvénye. Hatványozás modulo m:

Egy osztályt alkot az összes m-mel osztható szám, egy másikat azok a számok melyek m-mel osztva egy maradékot adnak, egy újabb osztályt azok melyek kettő maradékot adnak stb. A mod m maradékosztályok is gyűrűt alkotnak, akár az egész számok. A maradékosztályok körében a hatványozás is polinomrendben végezhető el: tl (mod m) kiszámításához csak (logt + logl + logm) nagyságrendű lépés kell. Ez azért van, mert a t, t2, t3, … számoknak megfelelő maradékosztályok sorozata előbb-utóbb önmagát fogja ismételni (mivel csak m darab maradékosztály van). Összefoglalva:

mod m a b

lineáris

polinomiális

a*b

polinomiális

polinomiális

a:b

polinomiális

polinomiális

b

a

nincs polinomiális algoritmus polinomiális

Prímtesztelés feladata: Kérdés: hogy lehet eldönteni egy n számról, hogy prím-e.

Erasztothenész-féle szita-algoritmus: felírjuk az összes számot n-ig, majd egymás után kihúzzuk a 2-vel oszthatókat, aztán a 3-mal oszthatókat, aztán az 5-tel oszthatókat, stb... Másik lehetőség: minden n-nél kisebb számról megnézni, hogy nem osztója-e n-nek (elég sqrt(n)-ig elmenni). Ezek nem polinomrendű algoritmusok, de ha n nem prímszám, akkor legalább rögtön megmutatják annak összes osztóját. A hatékony prímtesztelés feladata, hogy olyan eljárást nyújtson, ami ha nem is biztosan, de nagy valószínűséggel megmutatja egy számról, hogy prím-e, anélkül, hogy ha összetett számnak bizonyul megtalálja az osztóit.


A18-02

TARTALOMJEGYZÉK

2007. március 10. 22:38

Fermat-féle teszt, Carmichael számok: (m)

Ha t és m relatív prímek, akkor

t

Ha m prím, akkor

tm

1 (m) 1 (m)

Ha ez egy konkrét t,m párra teljesül, akkor ez nem bizonyítja azt, hogy m prím (m lehet összetett szám, de t a cinkosa). Ha viszont nem teljesül, akkor minden további vizsgálat nélkül biztosak lehetünk benne, hogy m nem prím (t az m árulója). Carmichael-szám:

Ha egy összetett szám nem Carmichael szám, akkor legalább annyi az árulója mint a cinkosa. Az algoritmusa: 1. i=1 2. válasszunk ki véletlenszerűen egy 1
2. és 3. lépés is elvégezhető polinom időben, így ez a prímtesztelő -algoritmus polinomrendű. Nyilvános kulcsú titkosírás: Számítógépmemóriában szeretnénk elhelyezni fontos információt azzal, hogy csak a jogosultak olvashassák ki – anélkül, hogy a jogosultságot ellenőrző jelszót is eltároljuk a rendszerben. Válasszunk ki két 200-jegyű p és q prímszámot, n=pq értéket tároljuk a memóriában és nyilvánítsuk azokat jogosulttá, akik n valamely osztóját mondják meg. Egy kapott k számról gyorsan kideríthető, hogy valóban osztó-e (egyenlő-e p-val vagy q-val) de n-ből p és q előállítása (mai tudásunk szerint) reménytelenül nehéz. Így még n titokban tartása sem kötelező. A valóságban a kódolás és dekódolás bonyolultabb, mert nem lehet csakúgy p-t vagy q-t a rendszer rendelkezésére bocsátani, mert onnantól kezdve ugyanúgy nem vagyunk biztonságban mint előtte. A kódolva küldendő üzeneteket 400-jegyű számok sorozatára bontjuk. A kódolást tekinthetjük egy y=C(x) függvénynek, mely a 400-jegyű x számhoz egy másik 400-jegyű y számot rendel. A függvény inverzét az x=D(y) függvényt dekódoló függvénynek nevezhetjük. Tfh. mindenki nyilvánosságra hozza a saját C függvényét, de titokban tartja a D dekódoló függvényt. Ekkor ha az i-edik személy (feladó) el akarja küldeni az x üzenetet a j-edik személynek (a címzettnek) akkor az általa is hozzáférhet Cj kódolófüggvényt alkalmazva az y=Cj(x) üzenetet küldi el. A címzett alkalmazza a csak általa ismert Dj dekódoló függvényt és megkapja a Dj(y)=Dj(Cj(x))=x üzenetet. A rendszerben részt vevő többi ember számára y dekódolhatatlan.


A18-03

TARTALOMJEGYZÉK

2007. március 10. 23:44

Kérdés, hogy lehet olyan C, D függvényeket készíteni, hogy bármely x-re Ci(x) vagy Di(x) kiszámítása gyorsan elvégezhető legyen, de Ci ismeretében Di-re ne lehessen következtethetni. Ezekhez használhatjuk fel a prímszámokat. Tfh az i-ik résztvevő választ két 200-jegyű prímet, pi-t és qi-t. Legyen ni=pi*qi. (ni)=( pi-1)(qi-1) és ezt a mennyiséget jelöljük mi-vel. A résztvevő ezen kívül választ egy olyan ei számot is, melyre 1<=ei<=ni teljesül és amely relatív prím (pi-1)-hez és (qi-1)-hez is. Végül megoldva egy ax b (mod m) típusú kongruenciát meghatározza azt a di számot, amelyre ei*di 1 (mod mi). Ezek után az i-ik résztvevő nyilvánosságra hozza az ni és ei számokat, viszont titokban tartja a pi, qi, mi és di számokat. A Ci kódolófüggvény egy x üzenethez hozzárendeli azt az y=Ci(x) számot amelyre y x ei (mod ni) míg a Di dekódolófüggvény az y-hoz annak di-ik hatványát rendeli (mod ni). Így:

Mindez csak akkor működik, ha x relatív prím ni-hez. Ezt úgy biztosíthatjuk, hogy az üzenetet nem 400, hanem 399 jegyű számsorozatokra bontjuk, majd mindegyik sorozat utolsó elemét úgy választjuk meg, hogy e feltétel teljesüljön. Dekódolás után elhagyjuk az utolsó számjegyet.


A19-01

TARTALOMJEGYZÉK

2007. március 11. 14:48

Művelet fogalma, félcsoport, csoport, Abel-csoport, részcsoport, elem rendje: Legyen H tetszőleges halmaz, 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. Kétváltozós művelet például az egész számok összeadása, kivonása (f(a,b)=a+b, f(a,b)=a-b). Def.: Egy H halmazon értelmezett 2-változós művelet (jelöljük *-gal) kommutatív, ha minden a,b є H-ra a*b = b*a Def.: Egy H halmazon értelmezett 2-változós művelet (jelöljük *-gal) asszociatív, ha minden a,b,c є H-ra (a*b)*c = a*(b*c)

S halmaz és a rajta értelmezett * (kétváltozós) művelet párost félcsoportnak nevezünk, ha * asszociatív. Ha * kommutatív is, akkor kommutatív, vagy Abel-féle félcsoportnak nevezzük. Példák: 1. A pozitív számok az összeadásra nézve félcsoportot alkotnak 2. Az nxn-es mátrixok a szorzással félcsoportot alkotnak 3. A pozitív valós számok a szorzásra nézve félcsoportot alkotnak Def.: Ha az S félcsoportban van olyan e elem, amelyre igaz az, hogy e*a=a*e=a minden a є S esetén, akkor e-t egységelemnek hívjuk, S-et pedig egységelemes félcsoportnak nevezzük. Def.: a є H-nak b inverze, ha a*b=b*a=e, azaz visszaadja az egységelemet. {G, *} csoport, ha * asszociatív (kétváltozós művelet G-n), létezik egységelem, és mindegyik elem inverze is G eleme. Ha * kommutatív is, akkor Abel-féle csoportról beszélünk. A csoport elemszámát |G|-vel jelöljük, és G rendjének nevezzük. Legyen G csoport. Egy H G részhalmazt részcsoportnak nevezünk, ha H is csoport ugyanarra a műveletre nézve. Jelölése: H G .

Példák: 1. R\,0- a szorzásra nézve csoportot alkot, sőt Abel-csoportot is 2. Az nxn-es, nem 0 determinánsú (invertálható) mátrixok a szorzással csoportot alkotnak Def.: g є G elem rendje a legkisebb pozitív egész k, hogy gk=e (ha nincs ilyen, akkor g rendje ) Egy elem rendje megegyezik az általa generált részcsoport rendjével. Az egy elem által generált csoportokat ciklikus csoportnak nevezzük. Példák: csoportok számokon, mátrixokon, rajzok szimmetriacsoportja, ciklikus csoport, diédercsoport, szimmetrikus csoport 1. Az egész, a racionális és valós számok Abel-csoportot alkotnak az összeadásra nézve, a természetes számok viszont nem.

2. Az nxn-es invertálható mátrixok csoportot alkotnak a szorzásra nézve. R rajz szimmetriája: olyan egybevágósági transzformáció, mely R-et önmagába viszi át R szimmetria csoportja: alaphalmaz az R szimmetriái, művelet a kompozíció, egységeleme a helybenhagyás


A19-02

TARTALOMJEGYZÉK

2007. március 11. 15:37

Diédercsoport: 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. Itt 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 forgatás. A csoportot Dn-nel jelöljük. Szimmetrikus csoport: n. szimmetrikus csoport (Sn): {elemek, művelet-: ,n elem összes permutációja, a permutációk egymás után végrehajtása (kompozíciója)-. A csoport rendje n!, a csoport nem kommutatív.

(első oszlop: 1->1->2; második oszlop: 2->3->3; harmadik oszlop: 3->2->1) Csoportok izomorfiája: Két csoport izomorf egymással, ha létezik köztük kölcsönösen egyértelmű, művelettartó leképezés.

Mellékosztály, Lagrange tétele:

Legyenek K,M részhalmazok G-ben. A KM szorzaton a KM={km|k єK,m є M- halmazt értjük. Legyen H G részcsoport, g є G. A Hg (gH) szorzatot H g szerinti jobboldali (baloldali) mellékosztályának, g-t pedig a mellékosztály reprezentánsának nevezzük. Legyen H • • • •

G . Ekkor: g є Hg a Hg mellékosztály minden eleme reprezentálja a Hg mellékosztályt két különböző jobboldali mellékosztály vagy egybeesik, vagy diszjunktak ha H véges, akkor bármely mellékosztály elemszáma megegyezik H rendjével.

Langrange tétel: Legyen G véges, H G . Ekkor H rendje osztja G rendjét, azaz |H|||G| (G egy mellékosztályának rendje osztja maga G rendjét). Az elemrend és csoport rendjének kapcsolata: Mivel egy elem rendje megegyezik az általa generált részcsoport rendjével, ezért egy elem rendje osztja a csoport rendjét. Ha egy csoport rendje prímszám, akkor csak triviális részcsoportjai lehetnek. Ekkor az egységelemen kívül minden elem rendje megegyezik a csoport rendjével. Egy elem generálja a csoportot, tehát ciklikus.


A20-01

TARTALOMJEGYZÉK

2007. március 11. 16:32

Gyűrűfogalma: A R halmaz a + és * műveletekkel gyűrű, ha 1. a+b=b+a a,bєR esetén 2. (a+b)+c=a+(b+c) a,b,c єR esetén 3. van olyan R-beli elem (jelöljük 0-val), hogy a+0=0+a=a a єR esetén 4. aєG-re a'єG úgy, hogy a+a’=0 (ahol 0 a 3. pontban szereplő elem); 5. (a*b)*c=a*(b*c) a,b є R esetén 6. (a+b)*c=a*c+b*c a,b є R esetén 7. c*(a+b)=c*a+c*b a,b є R esetén Az első négy axióma azt mondja ki, hogy R Abel-csoport az összeadásra nézve, az 5. pedig, hogy félcsoport a szorzásra nézve. A hatodik illetve hetedik axiómákat jobboldali illetve baloldali disztributív törvénynek nevezzük. Ha a szorzás is kommutatív, kommutatív gyűrűről, ha van a szorzásra nézve egységelem, egységelemes gyűrűről beszélünk. A harmadik axiómában említett elemet nullelemnek nevezzük. Egy a R-beli elem összeadásra vonatkozó inverzét (negyedik axióma) ellentettnek hívjuk, és –a-val jelöljük. Az a-b=a+(-b) műveletet kivonásnak nevezzük.

Nullosztómentes gyűrű: ha a*b=0 csak abban az esetben teljesül, ha vagy a=0 vagy b=0 vagy mindkettő. Kommutatatív gyűrű: ha a * műveletre is kommutatív Test fogalma, példák: Z, Q, R, nxn-es mátrixok, polinomok, Zp:

Egy R egységelemes gyűrűt ferdetestnek hívunk, ha a szorzásra nézve is van inverz. Egy ferdetestet testnek nevezünk, ha a szorzás kommutatív. Z: értelmezzük a + és * műveleteket rajta. Ebben az esetben egységelemes/ nullosztómentes /kommutatív gyűrűt alkotnak, de nem alkotnak testet (ha csak a páros számokat nézzük, akkor nem alkotnak egységelemes gyűrűt) . Q, R, C: értelmezzük a + és * műveleteket rajtuk. Ekkor egységelemes /nullosztómentes és kommutatív gyűrűt alkotnak, és testet is.

nxn-es valós mátrixok: csak egységelemes gyűrűt alkotnak a szokásos mátrixműveletekre. nxn-es invertálható mátrixok: ferdetestet alkotnak a szokásos mátrixműveletekre. valós együtthatós polinomok: értelmezzük a + és * műveleteket rajta. Ebben az esetben egységelemes/ nullosztómentes /kommutatív gyűrűt alkotnak, de nem alkotnak testet. Zp (prímrendű test): (mod p) maradékosztályok halmaza, egységelemes, nullosztómentes, kommutatív gyűrű és test. Komplex számok, algebrai és trigonometrikus alak, alapműveletek komplex számokkal: Komplex számoknak nevezzük az a+bi alakú számokat, ahol a és b is valós számok. Például komplex szám a 3+2i vagy a -12+25i. Az a+bi komplex szám valós részén a-t, képzetes részén pedig b-t értjük. Például a 3+2i valós része a 3, képzetes része a 2. -12+25i valós része a -12, képzetes része a 25. A "képzetes" elnevezés az "immaginárius" szóból ered, ezért is jelöljük "i"-vel a komplex számoknak nem valós, "képzetes" részét. A "komplex" elnevezés pedig arra utal, hogy ezek a számok összetettek, több (kettő ) részből állnak.

Azt a számot, aminek csak valós része van, tiszta valós számnak, amelyiknek pedig csak képzetes része van, tiszta képzetes számnak nevezzük. Például a 3, azaz 3+0i tiszta valós szám, mert nincs képzetes része, csak valós. A 25i, azaz 0+25i pedig tiszta képzetes szám, mert nincs valós része, csak képzetes.


A20-02

TARTALOMJEGYZÉK

2007. március 11. 16:55

Két komplex szám egyenlő, ha valós részeik és képzetes részeik is egyenlők. Például a 3+2i nem egyenlő a -3+2i-vel, a 3-2i-vel, a -3-2i-vel, a 2+3i-vel stb. Egy a+bi komplex szám konjugáltján az a-bi komplex számot értjük. (A képzetes rész előjelét az ellenkezőjére változtatjuk.) Például a 3+2i konjugáltja 3-2i, a -12+25i konjugáltja -12-25i, a 27-42i konjugáltja a 27+42i. Fontos megjegyeznünk, hogy minden valós szám olyan komplex szám, amelynek képzetes része 0. Azaz komplex szám a 3 (+0i) vagy a 0 (+0i) is. A valós számok tehát tiszta valós komplex számok. Képzetes egység:

i = -1

Kanonikus alak:

z = a + bi

⋅

Trigonometrikus alak: z = r(cos + i sin )

Az r a komplex szám abszolútértéke, a -t pedig a komplex szám irányszögének nevezzük.

Átváltás K→T: Átváltás T→K:

Hatványozás:

⋅ ⋅ z1⋅+ z2 = (a1+a1) + (b1+b2)i ⋅ z1 z2 = r1 r2 ⋅(cos( 1+ 2) + i ⋅sin( 1+ 2)) ⋅ + i sin( 1- 2)) z1/z2 =⋅ r1/r2 ⋅(cos( ⋅ 1- 2) ⋅ zn = rn (cos(n ) + i sin(n )) ⋅

Gyökvonás:

z1/n = r1/n (cos(( +2kπ)/n ) + i sin(( +2kπ)/n ))

Összeadás: Szorzás: Osztás:

nem egyértelmű, n darab eredményt ad!

Komplex szám n-edik gyöke, egységgyökök: Mint feljebb, azaz:

Tehát az n-edik gyök n különböző komplex számot jelent.

Az n-edik (n pozitív egész) egységgyök egy olyan z komplex szám, ahol zn=1 Az n-edik egységgyökök az egységsugarú körön helyezkednek el egy szabályos n-szög csúcsaiként.


B01-01

TARTALOMJEGYZÉK

2007. március 11. 18:08

Rendezési feladat: Adott az (U,<) rendezett halmazból (típusból) való elemekből álló A*1:n+ tömb. Rendezzük át az A elemeit úgy, hogy azok a < szerint nem csökkenő sorrendben legyenek. A módszerek költségének számításakor általában két tényezőt veszünk figyelembe: az összehasonlításokat és az elemek mozgatásait. Buborékrendezés, lépésszáma:

Az alapötlet az, hogy a rosszul álló szomszédos elempárokat megcseréljük: ha valamely i-re A[i]>A[i+1], akkor a két cella tartalmát kicseréljük. Ha már nincs ilyen értelemben rosszul álló pár, akkor A rendezett állapotban van. A tömb elejéről indulva a rosszul álló szomszédos elemeket cserélgetve eljutunk a tömb végéig. Ekkor a legnagyobb elem(ek egyike) A[n]-ben van. Utána ismételjük ezt az A*1:n-1+ tömbre, majd az A*1:n-2] tömbre, stb. Végül A rendezett lesz.

procedure buborék (* az A*1:n+ tömböt csökkenően rendezi *) for ( j=n–1, j > 0, j:=j -1 ) do for ( i=1, i j, i:=i+1 ) do , ha A*i+1+
B Tételsor – 53. lap

B01-02

TARTALOMJEGYZÉK

2007. március 11. 18:36

Innen tetszőleges n-re K n log2n . A K költségét a fenti kifejezés alapján másként, valamivel pontosabban is becsülhetjük. Világos, hogy log2k

1+ log2k , amiből, K
Rendezett sorozatok összefésülése, az összefésülés lépésszáma: Tegyük fel, hogy az A*1:k+ valamint B*1:l+ tömbök rendezettek, és tartalmukat rendezetten tárolni akarjuk a C*1:k+l+ tömbben. A C*1+-be nyilván az A*1+ és B*1+ elemek közül a nem nagyobb kerül. Ha ez mondjuk A*1+, akkor az A*2+ és B*1+ egyike lesz a C*2+-ben. Általában, ha az A*1:i+ és B*1:j+ résztömböket már feldolgoztuk, tartalmuk nem csökkenően C[1:i+j] -ben vannak, akkor nyilván a jó választás.

Ezt az eljárást összefésülésnek nevezzük (jelölése: MERGE). Minden egyes összehasonlítás után egy elem a helyére kerül, kivéve az utolsót, amivel két elem helyét derítjük ki. A költség tehát k+l-1 összehasonlítás és k+l mozgatás. Az összefésülés igen hatékony eljárás, hiszen a bemenő adatok hosszával arányos időben, lényegében egyetlen végigolvasással elrendezi a két sorozatot. Összefésüléses rendezés, lépésszáma: Az összefésüléses rendezés alapötlete, hogy először rendezzük külön-külön az A*1:n+ tömb első felét és második felét, majd ezek tartalmát fésüljük össze. Mindezek a következő MSORT nevű rekurzív eljárást sugallják, melynek paramétere a rendezendő tömb. Ha n>1, akkor MSORT(A[1:n]):= MERGE(MSORT(A[1: n / 2 ],MSORT(A[ n / 2 +1:n])).

Hogy elvarrjuk a rekurzió alját, legyen MSORT(A*i,i+) az üres utasítás. Az összefésüléses rendezés költsége – mindkét tényezőt figyelembe véve – O(nlogn). Alsó korlát az összehasonlítás alapú rendezésekre:

Tegyük fel, hogy egy pusztán két kimenetelű döntéseket használó program legfeljebb k ilyen döntés alapján rendezi n elem bármelyik bemeneti sorrendjét. Ekkor k log2(n!) teljesül. Két kimenetelű döntések: if feltétel then akció 1 else akció2; ahol akciói ugrás egy másik utasításra vagy egy rendezés.

Gyorsrendezés, lépésszáma: A rendezendő A*1:n+ tömb egy véletlen elemét vesszük. Ezután a tömb elejébe mozgatjuk az s-nél kisebb elemeket, a végébe az s-nél nagyobbakat. A kettő között helyezkednek el az s előfordulásai. Nevezzük PARTICIÓnak az eljárást, ami megvalósítja ezt. A PARTÍCIÓ(s) tehát felbontja három részre az A tömböt. Az A*1:k+ résztömb elemei s-nél kisebbek, A*k+1:l+ minden eleme s, végül A*l+1:n+ elemei s-nél nagyobbak.


B01-03

TARTALOMJEGYZÉK

2007. március 11. 19:23

Tegyük fel, hogy az A*1:n+ tömbbel és az s elemmel dolgozunk. Az i és j változók értéke kezdetben 1, illetve n. Először i-t növeljük, amíg A*i+<s teljesül. Utána j-t csökkentjük, amíg A*j+ s . Ha mindkettő megáll (nem lehet továbblépni), és i<j, akkor kicseréljük A*i+ és A*j+ tartalmát. Ezután i:=i+1 és j:=j-1. Ha a két mutató összeér (már nem teljesül i<j), akkor s előfordulásait a felső rész elejére mozgatjuk. Innen világos, hogy PARTÍCIÓ(s) költsége O(n). A gyorsrendezés megvalósítása fentiek felhasználásával: GYORSREND(A[1:n]) 1. Válasszunk egy véletlen s elemet az A tömbből. 2. PARTÍCIÓ(s); az eredmény legyen az A*1:k+, A*k+1:l+, A*l+1:n+ felbontás. 3. GYORSREND(A[1:k]); GYORSREND(A[l+1:n]).

A rendezéshez felhasznált összehasonlítások várható száma: • ha végig sikerült a középső elemet választani: • ha mindig a legkisebb elemet választjuk: • átlagosan:

1,39nlog2n + O(n) .

Ládarendezés, lépésszáma:

Tegyük fel, hogy az A*1:n+ tömböt szeretnénk rendezni, és tudjuk, hogy A elemei az m elemű U univerzumból kerülnek ki. Ekkor lefoglalhatunk egy U elemeivel indexelt B tömböt (U egy rendezett típus). Ennek elemei – a ládák – U-beli elemek listái lesznek. Kezdetben minden lista (láda) üres. Az eljárás első fázisában végigolvassuk az A tömböt, és az s=A*i+ elemet a B*s+ lista végére fűzzük. A második fázisban az elejétől a végéig növő sorrendben végigmegyünk B-n, és a B*i+ listák tartalmát visszaírjuk A-ba. Hatékony eljárás, ha m nem túl nagy. Az eljárás költsége O(n+m) elemi lépés. Példa: Tegyük fel, hogy a rendezendő A*1:7+ tömb elemei 0 és 9 közötti egészek: A: 5,3,1,5,6,9,6 Ekkor egy tízelemű B*0:9+ tömböt célszer használni. Az első fázis után a B így képzelhető el: B:-,1,-,3,-,55,66,-,-,9 Radixrendezés, lépésszáma: Tegyük fel, hogy a rendezendő kulcsok összetettek, több komponensből állnak, és a < reláció a komponensek rendezéséből lexikografikus rendezés. Legyenek az U elemei k hosszúságú t1 … tk alakú szavak, ahol a ti komponens az Li rendezett típusból való. Tegyük fel még, hogy az Li típusnak összesen si eleme van. Legyen t1 … tk és u1 … uk két kulcs U-ból. A lexikografikus (szótárszerű ) rendezés definíciója szerint t1 … tk > u1 … uk éppen akkor teljesül, ha ti > ui a legkisebb i indexre nézve, amelyre ti ui.

A radix rendezés receptje: először rendezzük a sorozatot az utolsó, a k-adik komponensek szerint ládarendezéssel. Utána az eredményül kapott sorozatot ládarendezzük a k-1-edik komponens szerint, és így tovább, végül az első komponens szerint. Arra kell ügyelni, hogy az elemeket mindig a ládájukat jelentő lista végére rakjuk. A rendezés költsége a k ládarendezés költségének az összege. A ládarendezésről mondottak szerint ez:


B01-04

TARTALOMJEGYZÉK

2007. március 11. 20:03

Példa:


B02-01

TARTALOMJEGYZÉK

2007. március 11. 20:06

Kupac adatszerkezet: A kupac adatszerkezettel egy (U,<) rendezett halmaz (a kulcsok univerzuma) egy S véges részhalmazát szeretnénk tárolni. Két művelet tartozik a szerkezethez: BESZÚR (U egy elemének hozzávétele S-hez) és MINTÖR (az S halmaz < szerinti minimális elemének törlése). Kupactulajdonság: Minden csúcsra teljesül, hogy a csúcsban levő elem < mint a fiaiban levők. Kupac műveletek lépésszáma, kupacépítés:

A kupac adatszerkezet egy hatékony implementációja a bináris kupac. A bináris fa egy olyan fa, amelynek csúcsai szinteken helyezkednek el. A szintek száma l. A legfelső szinten levő egyetlen csúcs a gyökér. Tetszőleges csúcsból maximum két él indul ki. Ezek a csúcs bal és jobb fiai. Minden gyökértől különböző csúcsnak van egy és pontosan egy apja. Az a csúcs aminek nincs fia a levél. A nem-levél csúcsokat szokás belső csúcsoknak is nevezni. Egy tömb tekinthető bináris fának, ahol a csúcsok az A*1:n+ elemek. A*i+ bal fia A*2i+, jobb fia pedig A*2i+1+. Az ilyen alakban ábrázolható bináris fákat teljesnek nevezzük. Ezek levelei maximum 2 szinten, a legalsón és esetleg a felette levőn helyezkednek el és legfeljebb egy kivétellel minden belső csúcsuknak 2 fia van. Bináris fa tulajdonságai:

• i. szinten legfeljebb 2i csúcs lehet • n csúcsú bináris fa szintszáma max n, min logn

A kupac elemeit egy bináris fában tároljuk. A fa csúcsaiban vannak a tárolni kívánt S halmaz elemei. Egy csúcsban egy elem van, de ugyanaz az elem előfordulhat több csúcsban is. A fára teljesül a kupactulajdonság. Ha a kupacnak n eleme van, akkor a keretül szolgáló teljes bináris fa egy n elemű tömbben tárolható. Először tetszőleges sorrendben beolvassuk az elemeket a tömbbe majd gondoskodunk a kupactulajdonságról. Ehhez a segédeljárás a következő: felszivárog(f) {Ha min{a1,a2} < a , akkor min{a1,a2- és a helyet cserél. Ha az a elem ai-vel cserélt helyet, akkor felszivárog( f i ).} Itt f egy részfa gyökere, a az itt tárolt elem, f (a kupac-tulajdonságot már teljesítő ) fiai f 1, f 2, a bennük levő elemek a1, a2. Tehát a addig megy lefelé a fában, amíg sérti a kupac-tulajdonságot. kupacépítés(f) ,Az f fa v csúcsaira lentről felfelé, jobbról balra felszivárog(v).-

Azaz a fának megfelelő A tömbben A*n+-től A[1]-ig felszivárogtatunk. Az eljárás lineáris költséggel megvalósítható. Lépésszáma O(n). MINTÖR megvalósítása: a törlendő elem a kupac-tulajdonság miatt a fa f gyökerében van. Ezt kivesszük innen, majd f-be tesszük a fa utolsó szintjén a jobb szélső csúcsban levő elemet; az utóbbi csúcsot töröljük, majd felszivárog(f) következik. Összköltség O(l)=O(log n).


B02-02

TARTALOMJEGYZÉK

2007. március 11. 20:30

BESZÚR(s) megvalósítása: új levelet adunk a fához (ügyelve a teljességre). Ebbe tesszük az s elemet. Ezután s-t mozgatjuk felfelé, amíg az t tartalmazó csúcs apjában levő s’ elemre igaz, hogy s<s’. Összköltség O(l)=O(log n). Kupacos rendezés, lépésszáma:

Bemenete a rendezendő sorozatot tartalmazó A*1:n+ tömb. Először kupacot építünk, utána n darab MINTÖR adja nem csökken sorrendben az elemeket. Az összköltség: O(n)+O(n log n)=O(n log n). Lineáris és bináris keresés rendezett halmazban, a keresés lépésszáma, alsó korlát: A keresés lényege, hogy adott az (U,<) rendezett halmaz véges S részhalmaza. A bemenet része egy s elem az U-ból. A feladat annak eldöntése, hogy s eleme-e S-nek és ha igen, akkor mi az ott elfoglalt helye. Ezt a feladatot szeretnénk összehasonlítások sorozatával megoldani. Lineáris keresés: Addig lépkedünk végig összehasonlítgatásokkal az elemeken, amíg ki nem derül, hogy s benne van-e Sben vagy nincs. A legkedvezőtlenebb esetben ez |S|=n összehasonlítást jelent.

Átlagos esetben azt feltételezzük, hogy a keresett elem egyenlő eséllyel lehet a (- s1], (s1 s2+, … , (sn-1 sn], (sn ) intervallumok bármelyikében. Ha az elsőben van, akkor 1 összehasonlítást végeztünk, ha az utolsóban, akkor n-et. Ennek az n+1 számnak az átlaga: (n/2)+1. Átlagos esetben ennyi összehasonlítást végzünk. Bináris keresés:

Először az S halmaz középső elemét hasonlítjuk össze s-sel. Ennek az si elemnek az i sorszáma lehet k vagy k+1, ha n=2k. Ha n=2k+1, akkor i=k+1. Ha s i=s, akkor egyetlen lépésben végeztünk. Ha si<s, akkor elég az si „feletti”, ellenkező esetben az si „alatti” részhalmazban újrakezdeni a keresést. Így mindig egy feleakkora halmazzal folytathatjuk a keresést, összesen tehát j+1
A keresőfa adatszerkezethez egyetlen (U,<) rendezett típus tartozik. A célja az U egy véges S részhalmazát úgy tárolni, hogy BESZÚR, TÖRÖL, KERES, MIN, MAX, TÓLIG hatékonyak legyenek. A bináris keresőfák a tárolni kívánt S U halmaz elemeit a csúcsaikban tárolják, csúcsonként pontosan egy elemmel. A bináris fákra teljesül a keresőfa-tulajdonság: Tetszőleges x csúcsra és az x baloldali részfájában levő y csúcsra igaz, hogy elem(y) elem(x) . Hasonlóan, ha z egy csúcs az x jobb részfájából, akkor elem(x) elem(z) . KERES(s,S): egyszerű lépkedés a gyökértől a gyökérelem és s összehasonlítása alapján a keresőfatulajdonságot figyelembe véve a bal vagy a jobboldali részfába, majd rekurzívan végezve ezt addig, amíg megtaláljuk a keresett elemet. A módszer költsége arányos a szintek számával: O(l)


B02-03

TARTALOMJEGYZÉK

2007. március 11. 20:59

MIN(S), MAX(S): addig megyünk a gyökértől balra (minimumnál) illetve jobbra (maximumnál) a fában, amíg lehetséges. Lépésszám O(l). TÓLIG(a,b,S): Egy KERESsel megtaláljuk az alsó korlátot (a) majd inorder bejárjuk a fát a felső korlátig (b). Ha az inorder lépkedéshez van a csúcsokban mutatónk a következő bejárandó csúcshoz (inorder fonal), akkor a művelet költsége O(l+k), ahol k az S a és b közé es elemeinek száma. Ha nincsenek inorder fonalaink, akkor az inorder bejárással O(n) időben kapjuk meg a kívánt eredményt. Naiv módszerek beszúrásra és törlésre:

BESZÚR(s,S): Elindítunk egy KERES(s,S)-t. Ha már van olyan x csúcs a fában, melyre elem(x)=s, akkor nincs teendő. Ha nincs, akkor a keresés ott ért véget, ahol nem tudunk továbblépni abból a csúcsból, amelynek vagy új bal vagy új jobb fiaként vesszük fel a s-t. Ezzel nem sérül a keresőfa-tulajdonság. A művelet költsége O(l). TÖRÖL(s,S): a KERES lefutása után a lehetőségek: • • • •

ha nem találja - kész ha az elem egy levélben van - töröljük azt ha az elem egy olyan csúcsban van, aminek egy fia van - a csúcs helyébe feltoljuk részfástól ha az elem egy olyan csúcsban van, aminek két fia van • a jobboldali részfa legkisebb elemét rakjuk a csúcsba, ezt az elemet az eredeti helyéről töröljük VAGY • a baloldali részfa legnagyobb elemét rakjuk a csúcsba, ezt az elemet az eredeti helyéről töröljük

Az összköltség ekkor is O(l).


B03-01

TARTALOMJEGYZÉK

2007. március 11. 22:22

AVL-fák, szintszám, műveletek, lépésszámuk: Bináris keresőfák esetén a keresés és a többi művelet szempontjából lényeges jellemző a fa szintjeinek száma (~magassága). Egy fa magassága akkor mondható jónak, ha legfeljebb clog 2n, ahol n a csúcsok száma és c egy kis pozitív állandó. Az olyan fa- konstrukciókat, ahol c értéke 1-nél nem sokkal nagyobb, kiegyensúlyozott fáknak nevezzük. Jelölje m(f) az f bináris fa magasságát. Legyen x az f egy csúcsa; ekkor m(x) jelöli az x -gyökerű részfa magasságát. AVL-tulajdonság: Egy bináris kereső fa AVL-fa, ha minden x csúcsára teljesül, hogy |m(bal(x)) - m( jobb(x))| 1.

A feltétel szerint egy csúcs jobb és bal részfájának a magassága közel egyenl ő. Egy n-pontú AVL-fa szintjeinek k száma nem több mint O(logn), pontosan k 1,44log2(n-1) .

Az AVL-tulajdonságot a forgatással őrizhetjük meg. Legyen S egy bináris keresőfa, melynek gyökere az x csúcs, ennek bal fia y. Jelölje f az y bal, g pedig a jobb részfáját. Legyen h az x jobb részfája. A bináris keresőfa-tulajdonság megmarad, ha S fát átalakítjuk úgy, hogy y lesz a gyökere, ennek bal részfája marad f, az y jobb fia x, ennek részfái g (bal) és h (jobb). Ezt a műveletet nevezzük jobb forgatásnak. Inverze a bal forgatás. Legyen az S bináris keresőfa, gyökere az x csúcs, ennek bal fia y, y jobb fia z. Végezzünk el egy bal forgatást az y gyökerű részfára, majd egy jobb forgatást az így kapott S-re. Ennek az operációnak (és tükörképének is) a neve dupla forgatás.

A beszúrás és törlés magvalósítására a naiv algoritmusokat használjuk, kiegészítve azzal, hogy a m űvelet elvégzése után forgatásokkal visszaállítjuk (ha szükséges) az AVL-tulajdonságot. Legyen S egy n csúcsból álló AVL-fa. BESZÚR(s,S) után legfeljebb egy forgatással (szimpla vagy dupla) helyreállítható az AVL-tulajdonság. A beszúrás költsége ezzel együtt is O(logn). Az n szögpontú AVL-fából való naív törlés után egy forgatás nem feltétlenül elég, de O(logn) már igen. A KERES hasonlóan, mint a keresőfáknál O(logn). 2-3 fák, szintszám, műveletek, lépésszámuk: Igen hatékony keresőfa konstrukció, tárolási szerkezete fa, azonban egy nem levél csúcsnak 2 vagy 3 fia lehet. A cél egy rekordtípus hatékony tárolása és elérése úgy, hogy a rekordok a levelekben vannak míg a belső csúcsok csak kulcsokat és mutatókat tartalmaznak.


B03-02

TARTALOMJEGYZÉK

2007. március 11. 23:04

A 2-3-fa egy (lefelé) irányított gyökeres fa, melyre igazak az alábbiak: 1. A tárolni kívánt rekordok a fa leveleiben helyezkednek el, a kulcs értéke szerint balról jobbra növekvő sorrendben. Egy levél egy rekordot tartalmaz.

2. Minden belső (azaz nem levél) csúcsból 2 vagy 3 él megy lefelé; ennek megfelelően a belső csúcsok egy illetve két s є U kulcsot tartalmaznak. A belső csúcsok szerkezete tehát kétféle lehet.

Itt mutatók a csúcs részfáira, s1, s2 pedig U-beli kulcsok, melyekre teljesül, hogy s1 < s2. Az m1 által mutatott részfa minden kulcsa kisebb, mint s 1, az m2 részfájában s1 a legkisebb kulcs, és minden kulcs kisebb, mint s2. Végül m3 részfájában s2 a legkisebb kulcs. A másik esetben a csúcsnak csak két részfája van; a baloldaliban vannak az s1-nél kisebb kulcsú rekordok, a jobboldaliban pedig s1 a legkisebb kulcs.

3. A fa levelei a gyökértől egyforma távolságra vannak. A k. szinten levő csúcsok száma: 2k és 3k innen, ha a levelek a k. szinten vannak, akkor 2k n 3k log3n k log2n

A KERES(s,S) első lépéseként az s kulcsot összehasonlítjuk az S gyökerében lévő s1 és esetleg s2 kulcsokkal. Ennek eredményeként megtudhatjuk, hogy a 3 részfa melyikében kell folytatni a keresést. A keresést azután ugyanígy folytatjuk egy szinttel lejjebb. Ha a fában tárolt rekordok száma n, a fa szintjeinek száma pedig m, akkor szintenként nem több, mint két kulcs-összehasonlítást kell végezni. Így a keresés összköltsége: O(logn).

BESZÚR(s,S): • ha egy 2 gyerekes csúcshoz kell az újat rakni, akkor a 3-nak betesszük és a megfelelő "útjelzőt" is beállítjuk • ha 3 gyerekes csúcshoz jönne az új, akkor 2db 2 gyerekes csúcsot hozunk létre csúcsvágással:

De ilyenkor egy szinttel feljebb is egy újabb csúcsot kell beszúrni… Ezért rekurzíve új csúcsokat szúrunk be, amíg kell. Ha ez felmegy a gyökérig és az is 2 gyerekes, akkor keletkezik egy új szint. Összköltsége: O(logn).


B03-03

TARTALOMJEGYZÉK

2007. március 11. 23:35

TÖRÖL(s,S): egy KERES-el indul • ha 3 gyerek közül kell törölni, akkor a csúcsot töröljük és az "útjelzőket" korrigáljuk a csúcstól a gyökérig • ha 2 gyerek közül kellett, akkor két lehetőség van: • ha a törlendő csúcs valamelyik szomszédos testvérének 3 fia van

• ha ilyen nincs, alkalmazzuk a csúcsösszevonás műveletét:

Ezután még egy szinttel feljebb is törölni kell egy csúcsot, ezt egészen a gyökérig ismételjük, ha szükséges. A felment a gyökérig és annak 2 fia volt, akkor a szintszám csökken egyel. Összköltsége: O(logn). Tehát a három főművelet – a keresés, a beszúrás, a törlés – elvégezhető O(logn) költséggel, ahol n a tárolt rekordok száma. B-fák, műveletek, lépésszámuk:

A B-fák adják a keresőfa adatszerkezet ma ismert legjobb külső táras megvalósítását. A cél egy rekordokból álló állomány tárolása külső táron úgy, hogy az elérés alapjául egy (U,<) rendezett halmazból való kulcsok szolgálnak. A csúcsokon a külső tár lapjai vannak, ezért a lapelérések számát próbáljuk optimalizálni. A kitüntetett művetek a következők: BESZÚR, TÖRÖL, KERES, MIN, MAX, TÓLIG. A B-fák a 2-3-fák természetes általánosításai. A lényegi különbség, hogy a B-fáknak háromnál több fia is lehet, és a fa egy levelében egynél több rekord is helyet kaphat. Legyen m 3 egész szám. Ekkor m-edrendű B-fa, röviden Bm -fa egy gyökeres, (lefelé) irányított fa, melyre érvényesek az alábbiak:

1. A gyökér foka legalább 2, kivéve esetleg, ha a fa legfeljebb kétszintes. 2. Minden más belső csúcsnak legalább

fia van.

3. A levelek a gyökértől egyforma messze vannak. 4. Egy csúcsnak legfeljebb m fia lehet. A B-fák belső csúcsai is hasonlítanak a 2-3-fák belső csúcsaira, az eltérés annyi, hogy itt több bejegyzés lehet. Tegyük fel, hogy egy B-fának n levele és k szintje van, ekkor:

Műveletek: mint a 2-3 fáknál


B04-01

TARTALOMJEGYZÉK

2007. március 12. 0:00

Vödrös hash-elés, a műveletek lépésszáma: Hashelés lényege: olyan h függvény konstruálása és alkalmazása, ami kulcsok egy nagy halmazát (pl. összes lehetséges magyar személyi szám) képezi le értékek egy kisebb halmazára (pl. a 0 és 12 millió közötti intervallum egész számai). Ennek alkalmazásával egy olyan módszerhez jutunk, amely gyors és egyszerű megvalósítását teszi lehetővé a beszúrásnak, törlésnek és módosításnak. Nem tételezzük fel a lehetséges kulcsok rendezettségét. A hash-es megoldások átlagos értelemben nagyon gyorsak, a legrosszabb esetben viszont nagyon lassúak is lehetnek. Vödrös hash-elés: szokásos láncolásnak is nevezni. A vödörkatalógus egy h értékkészletének elemeivel indexelt V tömb, melynek elemei mutatók, pontosabban lapláncok (vödrök) fejei. A vödrök lapjain helyezkednek el a tárolni kívánt rekordok. A V*i+ mutatóval kezdődő vödörbe kerülnek azok a rekordok, amelyek K kulcsaira h(K)=i teljesül. Beszúrás és keresés előtt kiszámítjuk h(K) értékét, majd a megfelelő vödörbe beillesztjük az új elemet, illetve szekvenciális kereséssel elindulunk a vödör lapjain és kiderítjük, hogy megtalálható -e a keresett elem. Törlés és módosítás ugyanilyen egyszerű. Ha a módosítás kulcsot is érint, akkor törlés és újra beillesztés is kellhet, mert h értéke a kulcs változásával szintén megváltozhat. Küls ő táras adatszerkezetről lévén szó, a lapelérések száma a lényeges. A keresés átlagos költsége O(p/M) lapelérés (M vödör van és p lapnyi rekordot tárolunk összesen).

Nyitott címzésű hash-elés: Csak belső memóriás módszerként hasznos. A rekordokat a T*0 : M-1+ tömbben kívánjuk elhelyezni. A K kulcsú rekordnak a T*h(K)+ helyet szánjuk, feltéve, hogy az nem foglalt. Ellenkező esetben valamilyen szisztematikus módon próbálunk helyet keresni a T további celláiban. A nyitott címzés módszerek ütközésfeloldásra a 0,1,...,M-1 számok egy 0,h1(K),h2(K),… hM-1(K) permutációját használják (azaz végigpróbálgatják a h(K)+hi(K) sorszámú cellákat az első üres helyig). Ezt az ütközésfeloldást használja mind a beszúrás mind a keresés (utóbbi addig megy, amíg meg nem találjuk a keresett elemet vagy üres cellához vagy a tábla végéhez nem érünk – utóbbi két esetben nincs meg amit keresünk). Lineáris és kvadratikus maradék próba: Lineáris próba esetén , azaz a K kulcsú rekord beillesztése során a h(K) cím cellától indulva addig lépkedünk egyesével balra (T*0+ után a tömb végére ugorva) amíg üres helyet nem találunk. Sikeres keresések során megvizsgált cellák átlagos száma: Sikertelen keresések során megvizsgált cellák átlagos száma: ahol =N/M a telítettségi tényező (táblában levő rekordok / tábla celláinak száma)


B04-02

TARTALOMJEGYZÉK

2007. március 12. 0:18

Törlésnél arra kell figyelni, hogy az eltávolított elem helyére nem NULL-t kell tenni, hanem egy TÖRÖLT szimbólumot, különben a keresés elakadna a kivett elem helyén. Álvéletlen próbálás: a 0,h1(K),h2(K),… hM-1(K) próbasorozat a 0...M-1 számoknak egy K kulcstól független álvéletlen permutációja. A lineáris próbálgatásnál elsődleges csomósodás volt, ami azt jelenti, hogy ha egy R’ rekord beillesztése során elérjük a már tárolt R rekord keresési útját, akkor azt rendszerint végig is kell járni. Álvéletlen próbánál másodlagos csomósodás van, ami azt jelenti, hogy ha a K és L kulcsokra h(K)=h(L), akkor a K és L kulcsok teljes próbasorozata is megegyezik, így ha sok azonos címre kerül kulcs van, akkor a közös próbasorozatok mentén alakul ki a csomósodás. Kvadratikus maradék próba: az álvéletlen próbálás egy példája. M:=4k+3 alakú prím, ahol k egy egész. A próbasorozat legyen:

A keresési költségek:

Ezek az összefüggések érvényesek az összes olyan módszerre, ahol h i(K)=f i(h(K)), vagyis ahol a h(K) érték már az egész próbasorozatot meghatározza. Kettős hash-elés: Lényege, hogy a h mellett egy másik h’ hash-függvényt is használunk, ahol megköveteljük, hogy h’(K) értékek relatív prímek legyenek az M táblamérethez. Ekkor a K kulcs próbasorozata h i(K)=-ih'(K). A különböző K és K’ kulcsok próbasorozatai jó eséllyel akkor is különbözőek lesznek, ha h(K)=h(K’) és így kiküszöbölődik mindkét féle csomósodás. Másrészt sikertelen keresés esetén minden érdekes ra gyorsabb, mint a lineáris próba, viszont sikeres kereséskor csak az 0,8 tartományban gyorsabb annál. Jó hash-függvények: A h-val szembeni követelmény, hogy legyen gyorsan kiszámítható és minél kevesebb ütközést okozzon. A következő két módszer szolgál ilyen függvények el állítására: Osztómódszer: h(K):=K (mod M), ahol M a tábla vagy a vödörkatalógus mérete. Feltesszük, hogy a kulcsok egész számok. h(K) számítása gyors és egyszerű, csak egy maradékos osztás kell hozzá.

Szorzómódszer: Itt egy rögzített

paraméter használatos, ami egy valós szám. Ekkor h(K):= M*{ K}

A hash-elés alkalmazhatósága, összehasonlítva a keresőfákkal: Átlagos viselkedés – legrosszabb eset: Hashelt szervezésnél az alapműveletek átlagos értelemben gyorsabbak, ezért pl. ügyviteli alkalmazásoknál, ahol nagy mennyiség teendőt kell összességében kedvező időben elvégezni ez használatos. A keresőfák viszont garanciát nyújtanak a legrosszabb esetek idejére is, így pl. valós idejű feladatokban őket kell használni. Rendezés a felhasználói igényekben: ha komoly feltétel az adatok rendezhetősége, akkor a keresőfáknál megismert MIN, MAX és/vagy TÓLIG eljárások használhatók erre. A hash-elt szervezés csak bonyolult kiegészítő megoldásokkal tudja figyelembe venni az univerzum rendezettségét.

Dinamika: Ha nem tudunk a méretre realisztikus felső korlátot adni, akkor a rendkívül rugalmasan és tág határok között változtatható méretű keresőfákat kell alkalmazni. A hash-elt szervezésnél ha betelik a tábla vagy a telítettség már túl nagy, akkor új, nagyobb táblával (vödörkatalógussal) kell újraszervezni az állományt.


B05-01

TARTALOMJEGYZÉK

2007. március 12. 18:08

A Turing-gép fogalma, működése: Legyen k egy pozitív egész szám. Egy k-szalagos Turing gép egy hetessel jellemezhető: M = (Q, T, ü, I, q0, F, ) , • Q: egy véges halmaz, az M gép belső állapotainak halmaza. A gép a működése során mindig valamelyik q є Q állapotban van. ,q0, q1, …, qk } • T: egy véges halmaz, a szalagjelek halmaza, a szalag abc. Egy szalagmezőn mindig egy T-beli jel van. • ü: egy kitüntetett szalagjel, az üresjel. A bemenetként felírt jeleken és a gép számítása során kiírt jeleken kívül minden szalagcellában ü van. Az üres jelet tekinthetjük úgy, mint a még nem használt mezők tartalmát. • I: I T \,ü- az input jelek vagy bemenő jelek halmaza, más szóval az input abc. A gépnek adott bemenetet az I elemeiből kell összeállítani. Az üres jel nem lehet input jel. • q0: q0 є Q a kezdőállapot. A gép a munka megkezdése előtt a q0 állapotban van. • F: F Q az elfogadó állapotok halmaza. Bizonyos számításoknál csak egy kétértékű döntést várunk a géptől. Ekkor csak azt nézzük, hogy a gép milyen állapotban állt meg. Az egyik választ az jelenti, hogy ez a végállapot F-beli, a másikat pedig az, hogy nem F-beli. Ezzel összhangban a Q\F-be tartozó állapotokat elutasító állapotoknak nevezzük. •

A QxTk →Qx(Tx{jobb, bal, helyben}) k egy parciálisan értelmezett függvény a gép átmenetfüggvénye. Az átmenetfüggvény tekinthető a gép programjának. A függvény mondja meg, hogy ha gép a q állapotban van, és az i-edik fej alatt lévő szalagjel ai (1 i k), akkor mit kell lépni. Ennek megfelelően a (q; a1, a2, …, ak ) nincs értelmezve, ha ez a lépés a megállás. A többi esetben a (q; a1, a2, …, ak) érték 2k+1 összetevőből áll. Ezek: a gépnek a lépés utáni q' є Q állapota; továbbá az i-edik szalagra kiírt bi szalagjel, valamint az i-edik fej elmozdulása (1 i k). Az elmozdulás legfeljebb mezőnyi, ezért leírható a jobb, bal, és helyben lehetőségek egyikeként. A függvényről még feltesszük, hogy az F-beli állapotokon nincs értelmezve.

Az I input abc elemeiből álló véges sorozatokat szavaknak nevezzük. Az I jeleiből alkotott szavak halmazát I*-gal jelöljük. I* részhalmazait nyelveknek nevezzük. A gép a működés előtt kezdőhelyzetben van. A gép állapota a q0 kezdő állapot, az író-olvasó fejeik a szalagjaik első cellájára mutatnak, az s є I* bemenet az első szalag elejére van írva, az összes többi mezőn az ü üresjel található. A gép a kezdőhelyzetből kiindulva lépéseket tesz. A lépések tartalmát jelentő változásokat a függvény írja le: a lépés előtti állapotnak és a fejek alatti jeleknek megfelelő - érték adja meg az új állapotot, a kiírandó jeleket és a fejmozgásokat. Ha a gép egy olyan helyzethez ér, amelyre nincs értelmezve, akkor megáll. Ez történik egyebek között akkor, ha a gép elfogadó (azaz F-beli) állapotban van.


B05-02

TARTALOMJEGYZÉK

2007. március 12. 18:49

A többszalagos Turing-gép szimulálása egyszalagossal, az idő és tárkorlát változása:

A Turing-gép egyik előnye, hogy segítségével egyszerűen vizsgálhatjuk a számítások idő - és tárigényét. Az M Turing-gép számolási ideje az s inputon a megállásig végrehajtott lépések száma, tárigénye pedig a felhasznált szalagcellák száma. Jelölje TM(n) az M gép maximális számolási idejét az n jelből álló bemeneteken. Az n hosszú szavakon a maximális tárigényt SM(n)-nel jelöljük. Ha van olyan n jelből álló s є I* szó, amellyel elindítva M nem áll meg véges sok lépés után, akkor TM (n) értékét végtelennek tekintjük. Hasonló mondható az S M függvényről is. Legyen M egy k-szalagos Turing-gép. Ekkor létezik olyan egyszalagos M’ Turing-gép, melyre • LM=LM' (fM=fM'), azaz ugyanazt a nyelvet ismerik fel • TM'(n) 2TM2(n), azaz az egyszalagos időigénye kisebb, mint a k-szalagos időigényének a duplájának a négyzete • SM'(n) SM(n)+n, azaz a egyszalgos tárigénye kisebb, mint a k-szalagos tárigényéne plusz n Szimuláció:

A Chomsky nyelvosztályok kapcsolata a Turing-gép változataival: Minden 0-s nyelvosztályhoz tartozó nyelvhez szerkeszthető egy olyan Turing-gép, amely pontosan a nyelvtan által generált mondatokat, és csakis azokat fogadja el. Az 1-es osztályú, vagyis környezetfüggő nyelvek ekvivalensek a lineárisan korlátos automatákkal. A lineárisan korlátos automata nagyon hasonlít a Turing-gépre. Van egy véges állapothalmaza, van egy íróolvasófejjel ellátott szalagja, a különbség csupán annyi, hogy a szalag korlátos, pontosabban olyan terjedelmű, amilyen a bemeneti jelsorozat.

Univerzális Turing-gépek létezése: Az univerzális Turing-gépek a fordítóprogramok népes családján belül az interpreterek közé tartoznak. Bemenetük két részből áll. Az egyik komponens az interpretálandó program, ami egy M Turing-gép leírása. A másik része az interpretálandó M gép tetszőleges s є I* bemenete. Az univerzális gép az M leírását, más szóval kódját értelmezve lépésről lépésre utánozza M működését.


B05-03

TARTALOMJEGYZÉK

2007. március 12. 19:21

Minden szóba jövő gépet egy w є I* szóval írunk le. Tetszőleges w є I* szóhoz legfeljebb egy gép van – ennek jele legyen Mw –, amelynek a kódja w. Az M ismeretében a w kód algoritmussal kiszámítható. A w leírás ismeretében pedig az Mw gép jellemzői (állapotai, átmenetfüggvénye, stb.) algoritmussal megkaphatók. Van olyan 3-szalagos U Turing-gép, amelyre teljesül a következő: ha w,s є I*és Mw létezik, akkor az U gép a w#s bemenetet pontosan akkor fogadja el (utasítja el, kerül vele végtelen ciklusba), ha Mw az s bemenetet elfogadja (elutasítja, végtelen ciklusba kerül vele). Church-Turing-tézis: Ami algoritmussal – azaz véges eljárással – kiszámítható (eldönthető), az Turing értelemben kiszámítható (eldönthető). Nevezetesen: • Egy f:I*→I * parciális függvény kiszámítható f parciálisan rekurzív • Egy f:I*→I * (teljes) függvény kiszámítható f rekurzív • Egy L I* nyelvre a nyelvbe tartozás problémája algoritmussal eldönthető L


rekurzív

B06-01

TARTALOMJEGYZÉK

2007. március 12. 19:32

Rekurzív és rekurzívan felsorolható nyelvek és rekurzív, illetve parciálisan rekurzív függvények: Az M Turing-gép által felismert LM nyelv azokból az s є I* szavakból áll, amelyekkel mint bemenetekkel elindítva az M megáll, mégpedig elfogadó állapotban.

A továbbiakban I egy nemüres véges halmaz. Az L I* nyelvet rekurzíve felsorolhatónak nevezzük, ha van olyan M Turing-gép, melyre L=LM , azaz a gép által felismert nyelv éppen L. Az L

I* nyelv rekurzív, ha van olyan M Turing-gép, melyre L=LM és M minden s є I* szóra megáll.

Az f:I*→I* parciális függvény parciálisan rekurzív függvény, ha létezik olyan M Turing-gép, hogy f=fM. Ha ezen túl még f minden s є I* inputra értelmezve van, akkor f egy rekurzív függvény. A rekurzív nyelv/függvény rekurzív felsorolható is. A rekurzív elnevezés onnan ered, hogy a rekurzív függvények azok a függvények, melyek bizonyos egyszerű függvényekkel rekurzió segítségével felépíthetők. A rekurzív felsorolható kifejezés arra utal, hogy a nyelv szavai egy alkalmas eljárással felsorolhatók. Church-Turing-tézis:

Ami algoritmussal – azaz véges eljárással – kiszámítható (eldönthető), az Turing értelemben kiszámítható (eldönthető). Nevezetesen: • Egy f:I*→I* parciális függvény kiszámítható f parciálisan rekurzív • Egy f:I*→I* (teljes) függvény kiszámítható f rekurzív • Egy L I* nyelvre a nyelvbe tartozás problémája algoritmussal eldönthető L

A következő két tétel a Cantor-féle átlós módszerrel bizonyítható: Van olyan L' I* nyelv, amely nem rekurzíve felsorolható. Létezik olyan f:I*→I* parciális függvény, amely nem parciálisan rekurzív. Az R, RE, coR és coRE nyelvosztályok kapcsolata:

R = coR: Biz.:


rekurzív

B06-02

TARTALOMJEGYZÉK

2007. március 12. 20:17

R = RE

coRE: Biz.:

Diagonális nyelv: Azon TG kódok, amikhez tartozó TG nem fogadja el a saját kódját:

Tétel: Ld nem rekurzíve felsorolható. Biz.: Ha a tétel ellenkezőjét tesszük fel mindkét irányban, akkor arra jutunk, hogy M akkor és csak akkor ismeri fel a saját kódját, ha nem ismeri fel a saját kódját, ami képtelenség:

Univerzális nyelv: Azon (kód, input) párok, ahol a kódolt TG elfogadja az inputot.

Tétel: Lu egy rekurzíve felsorolható, de nem rekurzív nyelv.


B06-03

TARTALOMJEGYZÉK

2007. március 12. 20:50

Megállási nyelv: A megállási probléma kérdése az, hogy egy (a kódjával adott) Turing-gép adott bementtel egyáltalán megáll-e. A vonatkozó nyelv:

Tétel: Lh egy rekurzíve felsorolható, de nem rekurzív nyelv. • є RE: ez igaz, mivel egy módosított univerzális TG jó lesz. Ha létezik M w, akkor futassuk Mw-t s-en univerzális TG-ként és ha megáll, akkor IGEN-t modnunk •

R:

Dominó probléma: Dominó alatt egy olyan egységnyi élű négyzet alakú lapot értünk, melynek a négy élére egy-egy jel van írva. A dominó típusa az e jelekből álló rendezett négyes. A kérdés, hogy ha adott a dominó-típusok egy véges F halmaza, akkor a sík lefedhető-e hézagtalanul szabályosan illeszkedő F-beli típusú dominókkal. Az egyes típusokból végtelen sok példány használható, és elforgatni nem szabad őket. A megfelelő nyelv és tétel a következő: D={F є {0,1,*,#}+; a sík lefedhető F-típusú dominókkal#: az egyes oldalak elválasztójele *: az egyes dominók elválasztójele

Tétel: A D nyelv nem rekurzíve felsorolható. Post megfeleltetési feladata:

Véges sok szópár van: (s1, t1), …, (sk , tk ) A problémát megoldhatónak nevezzük, ha vannak olyan (nem feltétlenül különböző) P-beli (s,t) párok, hogy azok első komponenseinek összeolvasásával adódó szó megegyezik a második komponensek egymás után fűzésével kapott szóval. Például P=,(iz,riz),(kar,ka),(ma,ma)- egy lehetséges megoldása a karizma szó. PCP jelöli a megfeleltetési feladat megoldható példányainak leírásaiból álló nyelvet. PCP nem rekurzív, de rekurzíve felsorolható.


B06-04 2007. március 21. 13:16

Környezetfüggetlen nyelvtanokkal kapcsolatos eldönthetetlen feladatok: Nem eldönthetők a következő problémák: • Két CF képes-e ugyanazokat a mondatokat generálni. • Adott E véges abc mellett az abc felett képzett nyelvtan képes-e generálni az összes E* mondatot. • Egyértelmű-e a CF nyelvtan. • L1 CF nyelvtan tartalmazza-e L2 CF nyelvtant • L1 CF nyelvtan egyenlő-e L2 CF nyelvtannal.


B07-01

TARTALOMJEGYZÉK

2007. március 12. 21:19

Kolmogorov-bonyolultság: adott Turing-gépre vett bonyolultság: A Kolmogorov-bonyolultság segítségével tanulmányozhatjuk, hogy véges sorozatok mennyire nyomhatók össze valamilyen algoritmussal. Tehát segítségével megadható, hogy egy I*-beli szó mennyire tömören írható le, vagy másképp, milyen rövid, milyen kevés jelből álló kóddá nyomható össze optimálisan. Ha a matematikai képlettel tömören leírható számokat hatékonyan szeretnénk kódolni, akkor a leírást kibontó gépnek „értenie” kell az egyszerű aritmetikai képleteknél általánosabban az algoritmusokat is. Ilyen gépek az univerzális Turing-gépek. Legyen továbbra is I=,0,1-. Olyan Turing-gépekre szorítkozunk, amelyeknek a bemenő abc-je I, és a számításaik eredménye is I-beli betűkből áll. Egy ilyen M gép az fM: I*→I* parciális függvényt számolja ki. Jelöljük CM (x)-el annak a legrövidebb bemenő szónak a hosszát, mellyel elindítva M az x szót adja eredményül:

A CM (x) szám méri, hogy x mennyire nyomható össze akkor, ha a kibontást, vagyis az összenyomott szó visszafejtését az M algoritmus végzi, azaz CM(x) a legtömörebb kódszó hossza, mely az M algoritmus számára x-et kódolja. Az x ismeretében könnyen szerkeszthetünk olyan M1 gépet, mely az üres bemeneten x-et számolja ki. Olyan M2 gép is van, amely sosem adja eredményül x-et. Ekkor CM1(x)=0 és CM2(x)= .

Rögzítsünk tehát egy U univerzális Turing-gépet, és értelmezzük az x є I* szó bonyolultságát mint a legrövidebb y#z input szó hosszát, melyre U az x szót számítja ki. Invariancia-tétel: Legyen U egy univerzális Turing-gép. Ekkor tetszőleges M Turing-gépre létezik egy (csak M-től függő) CM є Z+ állandó, mellyel minden x є I* szóra teljesül a következő egyenlőtlenség:

Cu(x)

CM(x)+CM

A CM =|w#| választás tehát megfelel a követelményeknek. Az invariancia-tétel szerint a Cu(x) érték csak legfeljebb egy x-től független állandóval haladhatja meg CM (x) értékét. Ezt úgy is értelmezhetjük, hogy az U-hoz tartozó összenyomhatóság mértéke nem marad el számottevően semelyik másik M gép szerinti összenyomhatóságtól sem. Kolmogorov-bonyolultság definíciója, a definíció értelmessége: Legyen x є I*. A C(x) := Cu(x) mennyiség az x szó Kolmogorov-bonyolultsága. Nem adtuk meg U-t elég pontosan ahhoz, hogy számolni tudjunk vele, tehát a C(x) kiszámítása nehéz feladat, hiszen C nem rekurzív. Ezért a C(xn) alakú sorozatok növekedési rendjét érdemes vizsgálni, ahol x 1, x 2, ... növekvő hosszúságú I*-beli szavak sorozata. Például az n=2k -10 alakú számokra C(n)=log2log2n+c' teljesül alkalmas c’ állandóval. Összenyomhatatlanság, összenyomhatatlan szavak létezése: Legyen x є I*. Ekkor C(x) |x|+k , ahol k egy x-től független állandó. Egy I*-beli szó Kolmogorov-bonyolultsága nem haladja meg lényegesen a szó hosszát. Az x є I* szó összenyomhatatlan, ha C(x) x| .



B07-02

TARTALOMJEGYZÉK

2007. március 12. 23:02

Legyen k є Z+. Legfeljebb 2k+1 x є I* szó van, amelyre C(x) k . Következésképpen minden n 1 egészre létezik n hosszúságú összenyomhatatlan szó. Ha n>8, akkor az n hosszú I*-beli szavak több, mint 99 százalékának a Kolmogorov-bonyolultsága nagyobb, mint n-8. A C függvény bonyolultsága: A C: I*→I* függvény nem rekurzív. Mivel C nem rekurzív, ezért kiszámítása nehéz feladat.


B08-01

TARTALOMJEGYZÉK

2007. március 12. 23:06

Idő- és tárkorlátos Turing-gépek: Jelölje TM(n) az M gép maximális számolási idejét az n jelből álló bemeneteken. Az n hosszú szavakon a maximális tárigényt SM(n)-nel jelöljük.

Számolási idő a megállásig végrehajtott lépések száma. Tárigény pedig a felhasznált (olvasott) szalagcellák száma. Ha az input szalag csak olvasható és/vagy az output szalag csak írható, akkor értelmezhető úgy a tárigény, hogy ezek ne számítsanak bele abba. Ha pontos fogalmat szeretnénk alkotni egy algoritmus gyorsaságáról, illetve tárkezelésének hatékonyságáról, akkor az idő- és tárfelhasználást az input hosszának függvényében vizsgáljuk.

Legyen t: Z+→Z+ egy függvény, melyre n є Z+ esetén t(n) n teljesül. Az M Turing-gép t(n) idő korlátos, ha n hosszú inputokon legfeljebb t(n) lépést tesz (azaz TM(n

t(n)

t(n) n azt a feltevést tartalmazza, hogy a gép az inputot legalább végigolvashatja. Az M algoritmust (TG-t) akkor tekinthetjük gyorsnak, ha t(n) egy lassan növekedő függvény.

TIME(t(n)) :={ L

I* | L felismerhető egy O(t(n)) idő korlátos M Turing-géppel-

Lényeges rész, hogy az n hosszú x inputon a számítás mindig befejeződik legfeljebb ct(n) lépésben, tekintet nélkül arra, hogy x є L igaz-e. Azaz TIME(t(n)) nyelvosztály rekurzív nyelvekből áll. Legegyszerűbb példánya a TIME(n), a lineáris időben felismerhető nyelvek.

Legyen s: Z+→Z+ egy függvény, melyre n є Z+ esetén s(n) log2n teljesül. Az M Turing-gép s(n) tárkorlátos, ha n hosszú inputokon legfeljebb s(n) tárcellát használ a munkaszalagon (azaz SM(n s(n) Itt s(n) log2n azért van, mert ennyi hely kell, hogy az n cellából álló szalagrészt címezni tudjuk. SPACE(s(n)) :={ L

I* | L felismerhető egy O(s(n)) tárkorlátos M Turing-géppel-

A nyelvekhez hasonló módon kaphatunk idő-, illetve tárkorlátokkal meghatározott függvényosztályokat. A definíciókban a nyelveket felismerő TG-k helyett függvényeket kiszámító TG-ket kell szerepeltetni. A SPACE(s(n)) nyelvosztály rekurzív nyelvekből áll. Tár-idő-tétel:

Ha L є SPACE(s(n)) , akkor van olyan L-től függő c konstans, mellyel L є TIME(cs(n)) teljesül. Tehát ha egy nyelv felismerésére van tárkorlátos algoritmus, akkor van idő korlátos is. Nevezetes nyelvosztályok: P, PSPACE, EXPTIME, ezek kapcsolata:

P= U TIME( nk) , a polinom időben felismerhető nyelvek osztálya. k

Ha az L nyelv nlogn-nél rövidebb időben nem ismerhető fel, akkor L P . k

EXPTIME= U TIME(2n ), az exponenciális időben felismerhető nyelvek osztálya. k

EXPTIME osztály a gyakorlatban elő forduló nyelvek univerzuma. Nemigen van olyan praktikus feladat, ami ezen kívül levő, még nehezebb nyelvhez vezetne. EXPTIME R. PSPACE= U SPACE(nk) , a polinom tárhasználattal felismerhető nyelvek osztálya. k


B08-02

TARTALOMJEGYZÉK

2007. március 13. 0:15

P

PSPACE Biz.:

EXPTIME: P

PSPACE: mert c*nl idő alatt max k*c*nl tárat tud egy k-szalagos TG használni

Valamint:


B09-01

TARTALOMJEGYZÉK

2007. március 13. 20:22

Nemdeterminisztikus Turing-gépek, idő és tárbonyolultságuk: A nemdeterminisztikus Turing-gép (röviden NTG) abban tér el a TG-t l, hogy a átmenetfüggvény nem egyértékű. A a lehetséges lépések olykor egynél több elemű véges halmazát jelöli ki: M = (Q, T, ü, I, q0, F, ) ,

(q,a)

QxTx{jobb, bal, helyben}

Ennek megfelelően a gép esetleg több lehetőségből választhat. A q állapotban az a szalagjel mellett a következő lépést a (q,a) halmazból kell választani. Az N NTG elfogadja az x є I* inputot, ha az M-et x bemenettel a kiinduló helyzetből indítva van legalább egy számítási út, ami mentén azt elfogadja.

Az NTG-k számításait néha hasznos egy gyökeres irányított faként elképzelni. A fa csúcsait a gép pillanatnyi helyzeteivel címkézhetjük. Egy csúcsnak annyi fia van, ahány lépés megengedett a csúcsnak megfelelő pillanatnyi helyzetből.

Egy N nemdeterminisztikus Turing-gép t(n) időkorlátos, ha minden n hosszúságú inputra N minden számítási út mentén legfeljebb t(n) lépést téve megáll. Úgy is fogalmazhatunk, hogy egy tetszőleges n hosszúságú x є I* input esetén a számításhoz rendelt fa magassága legfeljebb t(n)+1. Egy időkorlátos NTG semmilyen számítási úton nem kerülhet végtelen ciklusba. Az NTG nem valósághű számítási modell, nem ismert olyan tényleges fizikai megvalósítás, mely egy t(n) időkorlátos NTG működését t(n)-nel arányos időben szimulálni tudná. NTIME(t(n)):={az O(t(n)) időkorlátos NTG-k által elfogadott nyelvekNP és coNP nyelvosztály, ezek kapcsolata P-vel és R-rel: Az NTG-k segítségével fogalmazható meg kényelmesen a számításelmélet egyik legérdekesebb nyelvosztályának a definíciója: NP= U NTIME(nk), a NTG-el polinom időben felismerhető nyelvek osztálya. k

Az NP nyelvosztály ugyanúgy épül fel az NTIME(nk) alakú nyelvhalmazokból, mint a P a TIME(nk) alakúakból. A definíciók közötti nyilvánvaló formai hasonlóság alapján az NP osztályt a P nemdeterminisztikus megfelelőjének tekinthetjük. P

NP

Az NP nyelvosztály tartalmazza P-t. A két osztály közötti analógia azonban korántsem teljes. Nem ismert például, hogy az NP osztály megegyezik-e a coNP nyelvosztállyal ( coNP=L I*; I* \L є NP ), azaz (NP=coNP?). A (P=NP?) kérdés a számításelmélet egyik legfontosabb megoldatlan problémája.

P

NP

coNP: Biz.:


B09-02

TARTALOMJEGYZÉK

2007. március 13. 21:16

Tanú-tétel: Egy L

I* nyelvre a következő két állítás egyenértékű:

• L є NP • létezik olyan c>0 állandó, továbbá egy L1 є P nyelv, hogy ○ L1 (x,y) є (I*) 2 párokból áll, azaz (eldöntendő input, súgás) párokból ○ |y| |x|c minden L1-beli párra ○ x є L akkor és csak akkor, ha létezik y, hogy (x,y) є L1

Példák NP és coNP-beli nyelvekre:

Legyen 3-SZÍN a 3 színnel színezhető gráfok kódjaiból álló nyelv. Ekkor 3-SZÍN є NP. A bizonyítás során elég megmutatni, hogy a három színnel való színezhetőségnek van rövid és hatékonyan ellenőrizhető tanúja. Egy n szögpontú 3 színnel színezhet G gráf jó színezése alkalmas tanú lesz. A G irányítatlan gráf egy köre Hamilton-kör, ha abban G minden csúcsa pontosan egyszer szerepel. Legyen H a Hamilton-kört tartalmazó gráfokból álló nyelv. Ekkor H є NP. Az állítás rövid tanúja egy Hamilton-kör. Egy gráf síkba rajzolható, ha a pontjainak kölcsönösen egyértelműen megfeleltethetőek síkbeli pontok, és az élek olyan szakaszoknak, amelyek legfeljebb csak a végpontjaikban találkozhatnak. Legyen SÍK a síkba rajzolható gráfok nyelve. Ekkor SÍK є coNP. Az állítás igazolásához azt kell megmutatni, hogy G SÍK ténynek is van hatékonyan ellenőrizhető tanúja. Ez pedig következik Kuratowski nevezetes tételéből: a G gráf nem síkba rajzolható akkor és csak akkor, ha G topologikusan tartalmaz teljes ötszöget vagy 3ház-3kút gráfot (K5, K3,3).


B10-01

TARTALOMJEGYZÉK

2007. március 13. 21:36

Karp-redukció: L1 Karp-redukálható L2-re, ha:

L1

L2 jelöli azt a tényt, hogy L1 Karp-redukálható L2-re.

Az első követelmény azt fejezi ki, hogy f hűségesen transzformálja a nyelvbe tartozást. A második pedig azt, hogy f gyorsan kiszámítható: van olyan csak az f-től függ c>0 állandó, hogy az f(x) szó |x| c lépésben megkapható x-ből. Ennek folyománya pl., hogy |f(x)| |x|c Egy Karp-redukcióval az L1 felismerésének problémáját visszavezetjük L2 felismerésének problémájára. A jellemző alkalmazási helyzetben egy eddig ismeretlen L’ nyelvet hasonlítunk össze egy már megismert L nyelvvel. Egy L L' Karp-redukció arra enged következtetni, hogy L’ nehéz nyelv, feltéve, hogy ez igaz L-re. L1 L2 esetén L1 hatékonyan felismerhető ha van hatékony módszerünk L2 felismerésére. Bizonyítható redukciók:

A Karp-redukció tranzitivitása: Ha L1

L2 és L2

L3, akkor L1

L3 is teljesül.

Biz.:


B10-02

TARTALOMJEGYZÉK

2007. március 13. 22:05

NP-teljesség: Az L

I* nyelv NP-teljes, ha:

• akkor és csak akkor, ha minden NP-beli nyelvhez képest legalább olyan nehéz • akkor és csak akkor, ha bármelyik NP-beli nyelv visszavezethető rá Egy NP-teljes nyelv tehát legalább olyan nehéz, mint bármely más NP-beli nyelv. Az NP-teljes nyelveket szokás univerzális kereső feladatoknak is nevezni. Az a sejtés, hogy P NP, azaz az NPteljes nyelvekre nem léteznek polinom idejű felismerő módszerek. Ez nem azt jelenti, hogy megoldhatatlanok, mert NP PSPACE EXPTIME azaz a legnehezebb példányok is legyűrhetők exponenciális idejűnél nem rosszabb algoritmussal.

Cook-Levin-tétel (SAT nyelv): Boole-formula: 0,1 logikai konstansokból, 0-1 értékű változókból és a változók negáltjaiból az „és” illetve a „vagy” műveleti jelekkel és zárójelekkel felépített kifejezés.

Egy Boole-formula változóinak logikai értéket adhatunk. A változók ilyen kiértékelése után a kézenfekvő módon beszélhetünk a formula értékéről, ami 0 vagy 1 lesz. Egy Boole-formula kielégíthető, ha van a változóinak olyan kiértékelése, melynél a formula értéke 1. A SAT nyelv a kielégíthető Boole-formulák nyelve. Cook-Levin-tétele szerint a SAT egy NP-teljes nyelv. 3-SAT: A Boole-formula konjunktív normálformájú, ha 1 m alakú, ahol a i formulákban literálok (változó ill. annak ponáltja) szerepelnek kizárólag V jelekkel összekapcsolva. A i formulákat tagjainak nevezzük. Ha a i formulákban legfeljebb k literál szerepel, akkor -t k-konjunktív normálformájú formulának (k-CNFnek) nevezzük.

Jelölje k-SAT a kielégíthető k-CNF-ekből álló nyelvet. A 3-SAT nyelv NP-teljes. 3-SZÍN: 3-SZÍN a három színnel színezhet gráfok nyelve. A 3-SZÍN nyelv NP-teljes. MAXFTLEN:

MAXFTLEN= ,(G,k) |G egy gráf, k є Z+, és G-nek van k elemű független csúcshalmazaMAXFTLEN nyelv NP-teljes. Tanúnak jó a k db független pont. Ezt röviden, gyorsan ellenőrizni tudjuk, hogy teljesül-e. Valamint 3-SZÍN Karp-redukálható az MAXFTLEN-re.


B10-03

TARTALOMJEGYZÉK

2007. március 13. 22:40

Biz.:

X3C: A pontos fedés hármasokkal nyelve. Van egy U halmazunk, és egy halmazunk, ami az U néhány 3-elemű részhalmaza. A kérdés: U lefedhető-e -beliekkel egyszeresen

Tanúnak jó a megoldás. Ekkor 3DH Karp-redukálható az X3C-re. Így az X3C nyelv NP-teljes. H: H = ,Azon gráfok, melyekben van Hamilton-körA H nyelv NP-teljes.


B10-04

TARTALOMJEGYZÉK

2007. március 13. 23:33

RH: Hátizsák feladat: adottak az s1, …, sm>0 súlyok, ezek v1, …, vm>0 értékei, valamint a b megengedett maximális összsúly. Tegyük fel hogy ezek a számok egészek. A feladat az, hogy találjunk egy olyan I ,1, …, m- részhalmazt, melyre iєIsi b ugyanakkor iєIvi a lehető legnagyobb. Polinom idejű extra munka erejéig azonos nehézségű NP-beli feladatot kapunk, ha bevezetünk még egy k>0 értékkorlátot és egy adott s1, …, sm ; v1, …, vm inputra azt kérdezzük, hogy van-e olyan kímélő kitöltése a hátizsáknak, melynek értéke legalább k. Az így kapott döntési feladat neve Hát. Ez a nyelv NP-teljes, amit egy speciális esete szemléltet:

Részhalmazösszeg probléma: a tárgyak súlya és értéke azonos, valamint a súlykorlát megegyezik az értékkorláttal: si=vi és b=k Az RH nyelv NP-teljes.

Ládapakolás: Ládapakolás feladat: adottak s1, …, sm súlyú tárgyak, 0 si 1 racionális és k>0 egész. Eldöntendő, hogy a tárgyakat bele lehet-e pakolni legfeljebb k számú egységnyi súlykapacitású ládába. A Ládapakolás feladat nyelve NP-teljes.


B11-01

TARTALOMJEGYZÉK

2007. március 15. 21:08

Dinamikus programozás: elve, példák a korábbi algoritmusok közül: A dinamikus programozás módszere gyakran használatos valamilyen numerikus paraméterektől függő érték optimumának a meghatározására. Lényege, hogy az optimumot alkalmas kisebb részfeladatok optimumából próbálja előállítani. A dinamikus algoritmusok vezérlési szerkezete gyakran hasonlít egy táblázat szisztematikus kitöltésére. A kitöltést gyakran egy rekurzív összefüggés teszi lehetővé, ami alapján a bejárási sorrend szerint korábbi elemekből meghatározhatók a későbbiek. A kapott módszer költségét többnyire a kitöltendő táblázat mérete határozza meg. A rekurzív összefüggés megtalálásában sokszor segítségünkre van az optimalitás elve, amivel a Bellman-Ford és Floyd-módszernél már találkoztunk. Korábbi példák: • Bellman-Ford: amikor meghatároztuk a n utak közül a minimálisat • Floyd: minimális út, ami átmegy a k indexű ponton • CYK elemző A hátizsák probléma megoldása kis súlyok esetén, az algoritmus lépésszáma: Adottak az s1, …, sm>0 súlyok, a b súlykorlát, a v1, …, vm>0 értékek és a k értékkorlát. A kérdés, hogy van-e olyan I 1, …, m-- részhalmaz, melyre teljesül, hogy iєI si b és iєI vi k. Feltesszük még, hogy a szereplő mennyiségek mind pozitív egészek.

Tekintsük az m és b paramétereket változónak, és engedjük őket egy értelmes tartományban futni. Pontosabban fogalmazva legyen v(i,a) a maximális elérhető érték az s1, …, si súlyokkal, v1, …, vi értékekkel és az a súlykorláttal megadott feladatra. Ekkor v(0,a)=v(i,0)=0 tetszőleges a és i természetes számokra fennáll, és célunk a v(m,b) mennyiség meghatározása, illetve annak eldöntése, hogy fennáll-e a v(m,b) k egyenlőtlenség. A táblázat egyes elemeinek értéke a következő: v(i,a)=max{ v(i-1,a) ; vi+v(i-1,a-si) } v(i,a): mennyi a maximális érték, amit elérhetünk, ha s 1, …, si-ből választhatunk és a hátizsák súlykorlátja "a". A jobb oldalon az első mennyiség az i-dik súlyt nem tartalmazó választások optimális értéke, a második pedig az i-edik súlyt tartalmazó választások optimális értéke (mindkét esetben a súlykorlát mellett). Az összefüggés alapján a táblázat kitölthető úgy, hogy vesszük rendre az 1,2,…,m index sorokat, ezeken pedig az a indexet növelve haladunk. A táblázatnak mb eleme van. A módszer logaritmikus költsége O(bL), ahol L az input hossza. A Hátizsák probléma apró súlykorlát esetén megoldható polinom időben. Igazolásul elég annyi, hogy L b , tehát a futási idő az input hosszának polinomjával becsülhető: O(L2).

Közelít algoritmusok: elv, algoritmus a ládapakolási feladatra:

Nehéz algoritmikus problémák esetén előfordulhat, hogy elegendő a megoldás elég jó közelítése. Ládapakolás (Bin Packing): Inputként adottak az s1, …, sm (racionális) súlyok, 0 si 1.A cél a súlyok elhelyezése minél kevesebb 1 súlykapacitású ládába.


B11-02

TARTALOMJEGYZÉK

2007. március 15. 21:19

Igen egyszerű és természetes közelítő algoritmus az ff-módszer (Fist Fit, elsőalkalmas). Vegyünk először üres ládákat, és számozzuk meg őket az 1, 2, …, k egészekkel. Tegyük fel, hogy az s 1, …, si-1 súlyokat már elhelyeztük. Ekkor si kerüljön az első (legkisebb sorszámú) olyan ládába, amelybe még befér. Jelölje a Ládapakolás probléma egy I inputjára OPT(I) az optimális, FF(I) pedig az ff-módszer által eredményezett ládaszámot. A probléma tetszőleges inputjára teljesül, hogy FF(I) 2OPT(I). Pontosabban: a probléma tetszőleges I inputjára teljesül, hogy FF(I)


17/10*OPT(I)

B12-01

TARTALOMJEGYZÉK

2007. március 14. 17:35

Véges automata: A reguláris nyelveket elfogadó automataosztály a véges automaták osztálya. A véges automatát, mint matematikai objektumot egy ötös jellemzi:

M(Q, , , q0, F) • Q: az automata állapotainak véges halmaza • az elemzendő jelsorozat alfabetája • az automata mozgási szabályainak halmaza, amely szintén véges • q0: az induló állapot • F: az elfogadó állapotok halmaza A (A,a)=B mozgási szabály akkor alkalmazható, ha az automata az A állapotban van, és az olvasott karakter a. Az új állapot B lesz. Ha minden állapot-karakter párhoz maximum egy mozgási szabály tartozik, akkor az automata működése determinisztikus. Ha minden állapot-karakter pár esetében van mozgási szabály, akkor az automata teljesen specifikált.

Az automaták mozgási folyamatát mint konfigurációk egy sorozatát követhetjük nyomon. Valamely automata konfigurációja pillanatfelvétel az automata működéséről, amely mindazt az információt tartalmazza, amelynek alapján az automata további működése meghatározható. Véges automaták esetében egy konfiguráció: k=(q,w) • q egy automata állapot, q є Q • w pedig tetszőleges jelsorozat w є

*

Az automata L(M) nyelve azon jelsorozatok halmaza, amelyeket az automata elfogad.

Véges automaták determinizálása és teljesen specifikálása: Egy automata akkor fogad el egy jelsorozatot, ha létezik olyan mozgássorozat, amelynek során az automata a teljes jelsorozatot elolvassa és utána elfogadó állapotban áll meg. A nemdeteminisztikus automatáknál minden mozgási lehetőséget egyidejűleg kell figyelemmel kísérnünk, mert nem tudhatjuk, hogy végül melyik vezet eredményre. A determinisztikus automaták nyelvei felfoghatók a nemdeterminisztikus automaták nyelvei részhalmazaként. Viszont ez nem valódi részhalmaz, mivel minden nemdeterminisztikus automatához konstruálható olyan determinisztikus ekvivalens, ami pontosan ugyanazt a nyelvet fogadja el. Determinizálás: A gyakorlatban úgy járhatunk el, hogy az eredeti nemdeterminisztikus automatát elemezve meghatározzuk az állapottér azon részhalmazait, amelyek előfordulhatnak mint egyidejűen elérhető állapotok. Ezeket és csakis ezeket a részhalmazokat vesszük aztán bele az új automata állapotterébe. Az egész folyamat kezdete az új automata kezdőállapota lesz, amely egyedül az eredeti automata kezdőállapotát tartalmazó részhalmaz. Ebből kiindulva állapíthatjuk meg, milyen részhalmazok figyelembevételére van szükség. A teljesen specifikált automata készítéséhez bevezetünk egy T csapda állapotot. Ha valamelyik állapotkarakter párhoz nincsen mozgási szabály rendelve, akkor egészítsük ki szabályainkat egy olyan mozgással, amely erre az állapot-karakter párra az automatát a csapda állapotba viszi át. A csapda állapotban bármilyen karakter beolvasására újra a csapba állapotba megyünk át.


B12-02

TARTALOMJEGYZÉK

2007. március 14. 19:03

Nézzünk egy-egy példát ezekre: Teljesen specifikálás:

Determinizálás:

Minimálautomata, konstrukciója, unicitása:

Az előzőek értelmében minden automatából készíthetünk determinisztikus teljesen specifikált automatát. Ezek közül keressük a legegyszerűbbet azaz a legkevesebb állapottal rendelkezőt. Mivel az állapotok száma véges ezért szükségképpen van minimális állapotszámú. Konstrukció: Olyan diszjunkt ekvivalenciaosztályokra osztjuk az automata állapotait, hogy az A és B állapot akkor van ugyanabban az osztályban, ha nincsen olyan jelsorozat, amely különbséget tudna tenni a két állapot között. Ezért logikus megoldás a minimál automata konstrukciójára az, amely csak egyetlen állapotot alkalmaz a teljes ekvivalencia osztály helyett. Ez csak elvben működik, mert ahhoz hogy a definíció szerint ekvivalencia osztályokat tudjunk elkülöníteni, az összes lehetséges megszámlálhatóan végtelen jelsorozatot végig kéne próbálnunk az egyes állapotokra. Ezért bevezetjük az i ekvivalencia fogalmat ami szerint két állapot i ekvivalens, ha legfeljebb i hosszúságú jelsorozattal nem különböztethető meg. Így az eredeti ekvivalencia az i ekvivalenciából az átmenettel el őállítható. A 0 ekvivalenciaosztályból kiindulva venni kell az i+1 ekvivalenciaosztályokat, amíg nem tudjuk már tovább osztani az állapotokat. Ez úgy derül ki, hogy ami nem volt i ekvivalens az nem lesz i+1 ekviva lens sem.

Tetszőleges automatához megszerkeszthetjük a hozzátartozó minimálautomatát. Az ily módon megszerkesztett automata lényegében – izomorfiától eltekintve – unikális, azaz ez az egyetlen ilyen kis állapotszámmal bíró, az adott nyelvet elfogadó és teljesen specifikált automata. Nézzünk egy példát erre:


B12-03

TARTALOMJEGYZÉK

2007. március 14. 19:20

Kétirányban mozgó véges automata, kapcsolata az egyirányban mozgó véges automatával: A kétirányban mozgó automatánál nem mindig előre (jobbra) halad a fej a szalag felett hanem megengedett olyan átmenete is, amikor visszalép (balra). Itt is az az elfogadás feltétele, hogy végig legyen olvasva a szöveg. Az ilyen automaták ekvivalensek az egyirányba (csak jobbra haladva) mozgó automatákkal. Minden kétirányúhoz szerkeszthető egyirányú automata, ami nyomon követi, hogy amikor a kétirányú visszalépve elkezd kalandozni, akkor milyen állapotban tér vissza az eredeti betűhöz, ha egyáltalán visszatér és átlép-e rajta (a falon).


B13-01

TARTALOMJEGYZÉK

2007. március 14. 19:35

Generatív nyelvtanok: Jelölje a nyelv karakterkészletének véges halmazát (~alfabeta). Legyen * a alfabetájából alkotott véges, de nem korlátos hosszúságú jelsorozatok halmaza ( véges, de nem üres halmaz). ia

pontosan i hosszúságú jelsorozat. Ha i=0, akkor a nulla hosszúságú üres jelsorozatról beszélünk, jele: .

Egy adott alfabeta felett értelmezett L nyelv a * halmaz tetszőleges részhalmaza, tehát L Az L0-val jelölt üres nyelvnek egyetlen mondata sincs. Az L nyelv egyetlen mondata az üres jelsorozat.

*.

A generatív nyelveket (a nyelvtan által generált nyelvek) grammatikák segítségével jellemezhetjük. Formálisan a grammatikát egy négyes határozza meg G (N, , P, S), • N: a grammatikai szimbólumok véges halmaza, a nemterminális szimbólumok • az alfabeta, a nyelv karakterkészletének véges halmaza, a terminális szimbólumok • P: az úgynevezett levezetési szabályok összességének véges halmaza • S: a mondatszimbólum (az angol sentence-ből) A terminális és nemterminális szimbólumok közötti különbségtétel nagyon fontos. Éppen ezért a két halmaznak – az N és a halmaznak – diszjunktnak kell lennie, tehát N =0 . A nyelvtanok, grammatikák azért alkalmasak egy nyelv definiálására, mert segítségükkel egy nyelv mondatai levezethetőek, generálhatóak. Egy levezetés mondatszerű formáknak nevezett jelsorozatok egymásutánja. A levezetések sorozatában az egyik mondatszerű formából a következőt a levezetési szabályok segítségével származtathatjuk.

A levezetési szabályok a következő alakúak: → ahol a nyíl a szabály bal-, illetve jobboldalát elválasztó szimbólum. A szabály baloldala legalább egy grammatikai (nemterminális) szimbólumot kell, hogy tartalmazzon, a jobboldali tetszőleges jelsorozat. A levezetés akkor ért véget, ha terminalizálódott, azaz csak nyelvi szimbólumokat tartalmaz.

A nemterminális szimbólumokat a latin ábécé elejéről vett nagybetűk jelölik: A, B, C, stb. A terminális szimbólumokra a latin ábécé elejéről vett kisbetűket használjuk: a, b, c, stb. A terminális szimbólumokból álló jelsorozatokat az ábécé végéről vett latin kisbetűk: x, y, z, stb. Az olyan jelsorozatokat, amelyek tartalmazhatnak mind terminális, mind nemterminális szimbólumokat is görög kisbetűk jelölik: , , , stb. Egy G grammatika által definiált nyelv jelölése L(G), és ez a nyelv a * azon elemit tartalmazza, amely jelsorozatok a G grammatika segítségével tetszőleges számú lépésben generálhatóak:

A véges nyelvtannal megadott nyelveket generatív nyelveknek nevezzük. Chomsky-nyelvosztályok: A grammatikákat meghatározó helyettesítési szabályokra bonyolultsága alapján Chomsky a nyelveket osztályokba sorolta.


B13-02

TARTALOMJEGYZÉK

2007. március 14. 20:30

Chomsky négy nyelvosztályt definiált. Ezeket számokkal jelölte, így van 0-ás, 1-es, 2-es és 3-as nyelvosztály. • A 3-as nyelvosztály nyelvtanaiban csak kétféle szabálytípus engedélyezett. Ezek: A → a illetve A → aB ahol A, B nemterminálisok, a terminális szimbólum, amely lehet is Az ilyen alakú grammatikákat reguláris nyelvtanoknak nevezzük. jobbreguláris: A → a ill. A → aB balreguláris: A → a ill. A → Ba

• A 2-es nyelvosztály helyettesítési szabályainak alakja: A→ ahol

tetszőleges, mind terminális mind nemterminális szimbólumokat tartalmazható jelsorozat

Az A nemterminális mindig helyettesíthető az jelsorozattal, függetlenül attól, hogy mi a nemterminális környezete. Ennek a nyelvosztálynak a nyelveit környezetfüggetlen, vagy CF nyelveknek nevezzük.

• Az 1-es nyelvosztály helyettesítési szabályainak alakja: A → A szabály csakis a környezetében alkalmazható. Ez az értelmezés magyarázza a nyelvosztály elnevezését, ezek a nyelvek a környezetfüggő, vagy CS nyelvek.

• A 0-ás nyelvosztályban alkalmazható szabályokra nézve nincs megkötés. A generatív nyelvek számossága: Megszámlálhatóan végtelen sok generatív nyelv van. Biz.:

• van legalább ennyi generatív nyelv, hiszen az egy szóból álló nyelvek mind generatívak (triviális módon), ezekből viszont megszámlálhatóan végtelen sok van.

• Megmutatjuk, hogy nincsen több, mint megszámlálhatóan végtelen sok generatív nyelv. Ezt úgy tesszük, hogy felsoroljuk a generatív nyelveket nyelvtanaik szerint. Ha egy nyelv generatív, akkor van hozzá egy nyelvtan. Ezt a nyelvtant alakítsuk át úgy, hogy ha k darab nemterminális van benne, akkor azokat nevezzük N1, …, Nk-nak. Ezek után soroljuk fel a nyelvtanokat úgy, hogy el őször felso-roljuk valamilyen sorrendben azon nyelvtanokat, melyek leírása 1 hosszúságú, majd azokat, melyek hossza 2, aztán 3, 4, 5, stb. A nyelvtan hosszúsága a szabályok leírásához szükséges karakterek száma, például N1→aN1b|abnyelvtan hossza 8. (Nem kell megadni, hogy ki terminális és ki nem az, mert a terminális ábécé adott és azt sem kell megadni, hogy ki az S, mert az az S, aki elöl áll.) Világos, hogy egy adott l hosszúságra csak véges sok nyelvtan van, melynek hossza l (hiszen csak véges sok karakter fordulhat elő: a terminálisok, maximum l darab nemterminális meg még pár jel), ezért a fenti felsorolás lehetséges. Így minden generatív nyelvet felsorolunk legalább egyszer (persze, lehet, hogy többször is, ha több nyelvtan is előállítja), vagyis legfeljebb csak megszámlál-ható sok ilyen nyelv van.


B13-03

TARTALOMJEGYZÉK

2007. március 14. 20:51

Bal- és jobb-reguláris nyelvtanok és kapcsolatuk: Jobbreguláris nyelvtannak hívjuk azokat a reguláris nyelvtanokat, amelyben a levezetési szabály jobb oldalán lévő nemterminális szimbólum a terminális szimbólumtól jobbra helyezkedik el, míg balreguláris esetben attól balra. jobbreguláris: A → a ill. A → aB balreguláris: A → a ill. A → Ba A jobb és balreguláris nyelvtanok ugyanazt a nyelvosztályt generálják. Reguláris nyelvek, véges automaták és reguláris nyelvek kapcsolata: A reguláris nyelveket a 3-as nyelvosztályba tartozó grammatikák generálják. Az ilyen nyelveket elfogadó, a tartalmazás kérdésére választ adó automataosztály a véges automaták osztálya, azaz a véges automaták azokat a nyelveket fogadják el, amelyeket a reguláris nyelvtanok generálnak. Ha adva van egy nyelvtanunk, akkor a következőképpen tudunk hozzá véges automatát készíteni. Az automata minden mozgási szabályai a következőképpen alakuljanak: ha

A→aB

akkor

(A,a)=B

Minden nemterminálisnak megfeleltettünk egy automataállapotot, a mondatszimbólum állapota legyen a kezdő állapot. Az automata állapotok között azok lesznek az elfogadó állapotok, amelyek -szabállyal bíró nemterminálisnak felelnek meg (pl. A→ ). Amennyiben a nyelvtan segítségével levezethető a wA mondatszerű forma, akkor létezik az automatának olyan mozgássorozata, amely a w bemenet hatására az automatát az A állapotba viszi át. Ennek az állításnak a megfordítása is igaz, vagyis ha az automata a w jelsorozat elolvasása után az A állapotba kerül, akkor a mondatszimbólumból a nyelvtan segítségével levezethető a wA mondatszerű forma. Ezt a következő képpen írhatjuk le formális módon:

Biz. (teljes indukcióval): Tételezzük fel, hogy a fenti összefüggés az n hosszúságú jelsorozatokra igaz. Legyen n+1 hosszúságú jelsorozat alakja w=va, ahol |v|=n, és a a jelsorozat utolsó karaktere. Minthogy feltételezésünk szerint az n hosszúságú v jelsorozatra állításunk igaz, így ha ennek hatására az automata a B állapotba mehet át, akkor a nyelvtan képes a vB mondatszerű forma generálására. Ha most a következő karakter olvasásakor az automata az A állapotba kerül, vagyis létezik (B,a)=A alakú mozgási szabálya, akkor a ha

(A,a)=B

akkor

A→aB

megfeleltetés miatt a nyelvtan képes a B→aA helyettesítésre és így generálhatja a vaA mondatszerű formát. Fordítva, ha a nyelvtan alkalmas a vB mondatszerű formából a vaA mondatszerű forma származtatására, akkor a ha

A→aB

akkor

(A,a)=B

megfeleltetés miatt az automata a va jelsorozat után felveheti az A állapotot.


B13-04

TARTALOMJEGYZÉK

2007. március 14. 21:30

Az, hogy ez a feltételezés igaz n=1 esetére, triviális. Amennyiben az automata állapota elfogadó, azaz a beolvasott jelsorozat az automata nyelvének egy mondata, akkor ennek az állapotnak megfelel ő nemterminális elemészthető, és így a nyelvtan ugyanazt a mondatot képes generálni. Ez az okfejtés visszafelé is helytálló, így a két nyelv, a reguláris nyelvtan által generált és a véges automata által elfogadott azonos.


B14-01

TARTALOMJEGYZÉK

2007. március 14. 23:04

Reguláris nyelvek zártsági tulajdonságai: A nyelvek matematikai objektumok amikre szokás szerint műveleteket értelmezhetünk. A nyelvek jelsorozatok halmazai így vannak olyan műveletek, amelyek forrása a halmazelmélet (komplemens képzés, unió, metszet), és vannak olyanok, amelyeket a jelsorozat jelleg (konkatenáció, tranzitív lezárás) határoz meg. Alapvető kérdés, hogy mennyiben zártak az egyes nyelvosztályok a különböző műveletekre. Mivel a reguláris nyelvtanok generálta és a véges automaták által elfogadott nyelvek halmaza megegyezik, ezért a kérdésre választ adó bizonyításokat végezhetjük akár a nyelvtanok akár a véges automaták segítségével. Unió: Unióképzésre a reguláris nyelvek zártak. Komplementer: Az automata elfogadó és elutasító állapotainak jellegét fel kell cserélni. Előtte determinisztikussá és teljesen specifikálttá kell tenni az automatát különben előfordulhat, hogy van két olyan mozgássorozat amelyikből az egyik visszautasító a másik elfogadó állapotba vezet (ekkor definíció szerint az utóbbit kell alapul venni) vagy az automata nem tudja végigolvasni a szöveget (ez definíció szerint visszautasítást jelent). Zártak a reguláris nyelvek erre a műveletre.

Metszet: Mivel a komplementer képzés és az unióképzés zárt, ezérta de Morgan szabályra hivatkozva lehet(ne) azt mondani, hogy a két másik művelettel kifejezhető metszetképzés is az. Konstruktív bizonyítás: legyen adott két nyelv az automatájával. A metszet elfogadására olyan automatát kell szerkeszteni, amely egyidejűen figyelemmel kíséri, mi történik a két eredeti automatában és a jelsorozatot csak akkor fogadja el, ha mindkét eredeti automata elfogadja azt. Ehhez olyan automatát kell készíteni, amelynek állapothalmaza a két eredeti automata állapotterének direkt szorzata, pontosabban ennek alkalmas részhalmaza. Kezdőállapot a két kezdőállapot szorzata lesz míg az elfogadó állapotok azok az állapotpárok lesznek, amelyek két elfogadó állapotból származnak. Ha a két eredeti automata determinisztikus volt, akkor az új is az lesz. Konkatenált: L1 és L2 nyelv ebben a sorrendben (nem kommutatív a művelet) vett L1 L2 konkatenáltján azon jelsorozatok halmazát értjük, amelyeket (nem feltétlenül egyértelműen) ketté lehet vágni úgy, hogy a sorozat eleje az L1, másik fele az L2 nyelv mondata. Az L önmagával vett konkatenáltja L2, és akárhányszoros hatványt is értelmezhetünk. A nulladik hatvány az a nyelv amelynek egyetlen eleme az üres jelsorozat. A konkatenáltképzéshez először el kell érni, hogy a két nyelvtan nemterminális szimbólumaiból alkotott két halmaz diszjunkt legyen. Ezután az első nyelvtan második típusú szabályait, vagyis azokat ahol a jobboldalon nincsen nemterminális szimbólum átírjuk úgy, hogy a terminális szimbólum után odaírjuk a második nyelvtan mondatszimbólumait (azaz pl. A→a-ból A→aS2 lesz). Ha az első nyelvtan tartalmaz A→ alakú szabályokat, akkor ezekből alakú A→S2 lesz, amit a Chomsky-féle előírás nem ismer, ezért a jobboldal helyére kell írni azoknak a szabályoknak a jobboldalát, ahol a baloldalon S2 szerepel. Véges automatáknál egy elfogadó állapot esetén (L1-nél) tudunk konkatenáltat képezni. Ilyen alakra könnyen át tudjuk alakítani az automatát. Ekkor az L1 végállapotát összekötjük L2 minden kezdőállapotával.


B14-02

TARTALOMJEGYZÉK

2007. március 14. 23:32

Tranzitív lezárt: L nyelv L* tranzitív lezártja a nyelv valamennyi hatványának uniója. Az unióképzés a nulladik hatványnál kezdődik, tehát a nyelv tranzitív lezártjának mindig eleme Zárt.

Pumpálási lemma reguláris nyelvekre: Egy reguláris nyelv minden kellő hosszúságú w mondata felbontható három jelsorozat xyz egymásutánjára úgy, hogy y-t tetszőlegesen sokszor megismételve megint a nyelv mondatát kapjuk. Arra jó, hogy belássuk egy nyelvről, hogy nem reguláris.

Reguláris halmazok, kapcsolatuk a reguláris nyelvekkel: Legyen

egy adott alfabeta.

felett értelmezett reguláris halmaz az üres halmaz, az egyedül az üres jelsorozatot tartalmazó halmaz és egy halmazbeli karakter, mint egy egyetlen jelsorozatot tartalmazó halmaz. Legyen P és Q két reguláris halmaz. Ekkor P+Q, PQ és P* is reguláris halmaz. Precedenciaszabály ugyanolyan mint az aritmetikában: hatványozás (tranzitív lezárt), szorzás(konkatenáció), unióképzés. Zárójelezés itt is alkalmazható. Az üres halmaz a nulla, az üres jelsorozatot tartalmazó halmaz pedig az egységelem szerepét játssza.

A reguláris halmazokra bevezetett jelölések segítségével ugyanúgy lehet halmazegyenleteket illetve egyenletrendszereket felírni (és utána Gauss-eliminálni) mint a számokkal az aritmetikában. A reguláris nyelvtanok éppen a reguláris halmazokat generálják.


B15-01

TARTALOMJEGYZÉK

2007. március 15. 14:37

Környezetfüggetlen nyelvek: Azokat a nyelveket nevezzük környezetfüggetlen nyelveknek, amelyeket a 2-es nyelvosztályba tartozó nyelvtanok generálnak. Az ilyen nyelvtanoknak csak A→ alakú levezetési szabályai lehetnek. A környezetfüggetlen jelző arra utal, hogy egy mondatszerű formában a fenti helyettesítési szabály az A nemterminális környezetétől függetlenül, bárhol alkalmazható. Példa:

A nemterminális szimbólumok jele jelentést hordoz, adott esetben a számítástechnikában használt angol nyelven (E - expression, T - term, F - factor). A fenti nyelvtan az additív + és egy multiplikatív * operátort tartalmazó, és a zárójelezést megengedő aritmetikai kifejezéseket generálja. A nyelvnek nyilvánvalóan eleme az a+a*a. Ezt az alábbi levezetés igazolja:

Azonban a mondatot másképp is le lehet vezetni:

Ábrázoljuk a levezetést egy rendezett, irányított gráffal, fával (~levezetési fa). A rendezettség itt annyit jelent, hogy az egy csomópontból kiinduló élek sorrendje kötött. Minden csomópontból annyi él és abban a sorrendben fut ki, amennyi a szabály jobboldalán található szimbólumok száma és a kifutó élek végén sorban a jobboldal megfelelő szimbólumai helyezkednek el. Minden levezetésnek egy és csakis egy levezetési fa felel meg, ugyanakkor egy levezetési fához több levezetés is tartozhat. Az a+a*a mondathoz tartozó levezetési fa: A fában az egyes csomópontokhoz tartozó részfákat szintaktikai egységeknek nevezzük. Ilyen minden terminális szimbólum (levél) önmagában is. Azokat a levezetéseket, amelyek levezetési fája azonos, tehát ahol a jelsorozat felbontása szintaktikai egységekre megegyező, nem tekintjük lényegesen különböző levezetéseknek.

Az olyan nyelvtanokat, ahol minden mondathoz egy és csakis egy levezetési fa tartozik, egyértelmű nyelvtanoknak mondjuk. Természetesen ez nem zárja ki, hogy egy mondatnak több levezetése legyen, azonban azok nem lehetnek lényegesen különbözűek. A levezetések között vannak nevezetesek. Amikor a levezetés során mindig a mondatszerű forma legbaloldalibb nemterminális szimbólumát helyettesítjük, baloldali levezetésről beszélünk. Ugyanígy jobboldali levezetés esetében mindig a mondatszerű forma legjobboldalibb nemterminális szimbólumát bontjuk fel a következő lépésben.


B15-02

TARTALOMJEGYZÉK

2007. március 15. 14:57

Környezetfüggetlen nyelvtanok jólfésült alakra hozása: Célszerűségi szempontból támaszthatunk igényeket a nyelvtan külalakjával, helyettesítési szabályok külalakjával kapcsolatban. A jólfésülés lépései: • -szabályok eltüntetése (A→ ) • láncszabályok kiküszöbölése (A→B) • felesleges szimbólumok kiküszöbölése (nem generálható a mondatszimbólumból vagy nem generál csupa terminális sorozatot)

A felesleges szimbólumok kiküszöbölése: Egy nemterminális szimbólum akkor felesleges, ha nincs a nyelvnek olyan mondata, amelynek a levezetésében található mondatszerű formák legalább egyikében az illető nemterminális előfordulna. Legyenek valamely nyelvtanban érvényesek a következő levezetések:

Amennyiben a fenti levezetések lehetségesek, akkor sem az a terminális, sem az A nemterminális szimbólum nem felesleges. Bottom-Up fésülés (miből vezethető le mondat?): Legyen adott egy G grammatika. Képezzünk egy halmazsorozatot az alábbi szabályszerűség szerint:

Ezek szerint a következő halmazt úgy kapjuk, hogy az előző halmazhoz hozzávesszük azokat a nemterminális szimbólumokat, amelyeknek létezik olyan levezetési szabálya, ahol a jobboldalon minden szimbólum az előző halmaz eleme. Jelölje B az ilymódon kapott legnagyobb számosságú halmazt. Amennyiben kiindulásul a terminális szimbólumok halmazát választjuk, akkor a B halmaz a terminális szimbólumokon kívül azokat és csakis azokat a nemterminálisokat fogja tartalmazni, amelyekből kiindulva a helyettesítési szabályok alkalmazásával egy pusztán terminális szimbólumokból álló jelsorozat állítható el . Ez egy alulról felfelé, bottom up fésülés. Top-Down fésülés (mi vezethető le a mondatszimbólumból?): Vegyünk ismét egy halmazsorozatot és válasszunk a következő képzési szabályt:

Az új képzésekor tehát az eredeti halmazhoz hozzá kell venni azon helyettesítési szabályok jobboldalán található terminális és nemterminális szimbólumokat, amely szabályok baloldala az eredeti halmazhoz tartozó nemterminális szimbólum. Ha a kiindulásként választott halmaz egyedül a mondatszimbólumot tartalmazza, akkor a T halmaz azokat és csakis azokat a terminális és nemterminális szimbólumokat tartalmazza majd, amelyek egy, a mondatszimbólumból kiinduló levezetés mondatszerű formáiban szerepelnek. Ezzel az algoritmussal felülről lefelé, top down fésüljük meg a grammatika szabályait. Fontos: először Bottom-Up, aztán Top-Down fésülés kell, a sorrend fontos!


B15-03

TARTALOMJEGYZÉK

2007. március 15. 15:59

Példa:

A nyelvtant alulról felfelé megfésülve a következő halmazsorozatot kapjuk:

A B nemterminális szimbólum feleslegesnek bizonyult, ebből következően az ekvivalens nyelvtan:

Ezt a nyelvtant felülről lefelé fésülve a következő halmazsorozatot kapjuk:

A C nemterminális szimbólum feleslegesnek bizonyult, ebből következően az ekvivalens nyelvtan:

-szabályok eltüntetése: A következő algoritmus az A→ alakú ún. epszilon szabályok kiküszöbölését valósítja meg. Fésüljük meg az eredeti nyelvtant, válasszuk induló halmaznak az üres jelsorozatot:

Abban az esetben, amikor a nyelv tartalmazza az üres jelsorozatot (ha a mondatszimbólum elenyészhet), állítsuk elő a nyelvet két nyelv uniójaként. Az első mondatai az üres jelsorozat kivételével megegyeznek az eredeti nyelv mondataival, míg a másodiknak komponensnek egyetlen eleme lesz, az üres jelsorozat . Jelölje Le azt a nyelvet, amelynek egyetlen mondata az üres jelsorozat. Az L nyelv, amely tartalmazza az üres jelsorozatot is tehát:

L=(L-Le) Le Az Le nyelvtana csak egyetlen szabályt tartalmaz:

Q→

Az L=(L-Le) Le nyelv mondatszimbólumát jelöljük P-vel, ekkor az eredeti nyelv szabályait a következő szabályokkal kell kiegészítenünk: P→Q Q→ P→S Ezek után hagyjuk el az összes epszilon szabályt, de ugyanakkor az olyan levezetési szabályokat, ahol a jobboldalon szerepelnek elenyésző nemterminálisok, az összes lehetséges konfigurációban hagyjuk el ezeket a nemterminálisokat.

Példa:


B15-04

TARTALOMJEGYZÉK

2007. március 15. 16:36

Láncszabályok kiküszöbölése: Mint már említettük egyszereseknek nevezzük az (A→B) alakú szabályokat. Az egyszeres szabályok megléte zavaró lehet, ha ciklicitás van bennük, mint például az A→B, B→C,C→A szabályok esetén. Emeljük ki a nyelvtanból az egyszeres szabályokat, és a továbbiakban azt a nyelvtant vizsgáljuk, amely csak ezekből az egyszeres szabályokból áll. Megnézzük, hogy ebben a nyelvtanban hány nemterminális szimbólum van. Ezután alkalmazzuk a felülről lefelé való fésülést oly módon, hogy kiinduló halmazként rendre egy-egy ilyen nemterminálist választunk. Az egyes fésülések eredményeként kapott záróhalmaz nyilván azokat a nemterminálisokat tartalmazza, amelyek a kiindulásul választott nemterminális szimbólumból az egyszeres szabályok útján elérhet őek. Az egyszeres szabályok elhagyáskor ennek megfelelően a nyelvtant új szabályokkal kell kiegészíteni. Ezen szabályok baloldala a kiindulásul választott nemterminális szimbólum lesz, jobboldala pedig megegyezik azon szabályok jobboldalával, amelyeknek baloldala a záróhalmazban található valamelyik nemterminális. Példa:

Chomsky-normálformára hozás: Ebben a normálalakban csak kétféle alakú helyettesítési szabály engedélyezett: A→AB illetve A→a A fenti formát nem teljesítő szabályokat alakítsuk át a következő elvek alapján: a terminális szimbólumok helyett vezessünk be (ál)nemterminálisokat , és egészítsük ki a szabályainkat -val. Ezzel a Chomsky megkötéseknek eleget nem tévő helyettesítési szabályok alakja csakis a következő lehet (legalább két nemterminális tartalmaznak a jobboldalon, ugyanis az eredeti jólfésült nyelvtanban nincsenek egyszeres szabályok): C→C1C2…Cn ezeket alakítsuk át a következő módszer segítségével:

Ezt ismételve a jobboldalt is kettőre tudjuk redukálni. A CNF nem egyedi ugyanis tetszőleges sorrendben vezethetjük be Ci-k helyett az új nemterminálisokat.


B15-05

TARTALOMJEGYZÉK

2007. március 15. 16:54

Greibach-normálforma: A Greibach normálalakban a helyettesítési szabályok alakja A→aW, ahol W tetszőleges, csak nemterminálisokból álló sorozat. A GNF jelentősége, hogy az így felírt nyelvtanok nem balrekurzívak, ami azért lényeges, mert bizonyos egyszerű szintaktikus elemző módszerek nem alkalmazhatóak, ha a nyelvtan balrekurzív. Rekurzió és balrekurzió kiküszöbölhetősége: Egy nemterminális szimbólumot rekurzívnak mondunk, ha származtatható belőle olyan jelsorozat, amely az eredeti szimbólumot tartalmazza. Egy nyelvtan akkor rekurzív, ha tartalmaz rekurzív nemterminálist. Balrekurzívnak mondunk egy nyelvtant akkor, ha van olyan a rekurzivitásért felelős nemterminális szimbólum, amelyből kiinduló levezetés során a szóban forgó nemterminális a legbaloldalibb pozícióban jelenik meg újból: Közvetlen balrekurzió: Legyen A egy közvetlen balrekurziót okozó nemterminális. Soroljuk az A levezetési szabályait két halmazba aszerint, hogy közvetlen balrekurziót okoznak-e vagy sem.

Vezessük be a reguláris halmazoknál már alkalmazott jelöléseket, és legyen Ekkor:

Alakítsuk át a nyelvtant a következők szerint:

Példa:


B16-01

TARTALOMJEGYZÉK

2007. március 15. 17:44

Veremautomaták: A 2-es nyelvosztály helyettesítési szabályainak alakja: A→

Itt tetszőleges, mind terminális mind nemterminális szimbólumokat tartalmazható jelsorozat. Minthogy a szabályok alkalmazása a környezettől független ezért az osztály nyelveit környezetfüggetlen (CF) nyelveknek nevezzük. A környezetfüggetlen nyelvek felismerésére a veremautomaták szolgálnak, melyek a véges automata LIFO szervezés memóriával ellátott változatai. Definíció szerint a veremből olvasás egyben a veremből való kivételt is jelenti.

A veremautomata formális leírására egy hetes szolgál: P(Q, , , , q0, Z0, F) • • • • • • •

Q: az automata állapotainak véges halmaza az elemzendő jelsorozat alfabetája a verem alfabetája, vagyis azon szimbólumok halmaza, amelyek a veremben lehetnek az automata mozgási szabályainak halmaza, amely szintén véges q0: az induló állapot Z0: a memória kezdeti tartalma. F: az elfogadó állapotok halmaza

A P jelölés a push-down automaton angol elnevezésre utal. Az összes említett halmaz véges. Az automata csak akkor mozgásképes, ha a verem nem üres, ezért szerepel benne induláskor Z0. A veremautomata mozgását az automata állapota, az olvasott karakter és a verem tetején található szimbólum határozza meg. A mozgás hatására az automata új, esetleg az eredetivel megegyező állapotot vesz fel, és a verem tetejére egy véges jelsorozatot ír be. Ha egy mozgásnál a verembe beírt jelsorozat hossza 0, akkor azt mondjuk, hogy az karaktert írtuk a verembe. Léteznek ún. epszilon mozgások is, amiket csak az automata állapota és a veremtető határoz meg. Az olvasófej alatti karakter itt nem játszik szerepet, el sem olvassuk és így a szalag sem továbbítódik. Epszilon mozgás akkor is lehetséges, ha az olvasófej alatt már nincs is karakter. A veremautomata akkor fogadja el a bemeneti jelsorozatot, ha az elolvasás után elfogadó állapotba kerül. Megengedett, hogy az automata az elolvasás után epszilon mozgásokkal kísérelje meg az elfogadó állapot elérését. A mozgási szabályok leírásánál a sorrend: automata állapot, olvasott szimbólum és a verem teteje illetve az új állapot és a verembe beírt jelsorozat. Amennyiben epszilon mozgásról van szó az olvasott karakter helyén epszilon áll. Amennyiben egynél több szimbólumot írunk be a verembe, akkor a sorozat legbaloldalibb eleme kerül a verem legeslegtetejére. A mozgási szabály alakja: (qi є Q, a є , z є )

A veremautomata egy konfigurációja:

K=(w, q, )

• w a még el nem olvasott jelsorozat • q az automata állapota • a verem tartalma

A konvenció szerint a még elolvasásra váró jelsorozat legbaloldalibb eleme van az olvasófej alatt és a verem tartalmának legbaloldalibb eleme a verem teteje.


B16-02

TARTALOMJEGYZÉK

2007. március 15. 18:21

A veremautomata akkor determinisztikus, ha minden szituációhoz legfeljebb egy mozgás tartozik. Ezen felül kikötjük, hogy ha valamely automata állapot és veremtető pár esetében lehetséges epszilon mozgás, akkor csakis ez a mozgás legyen lehetséges. Nemdeterminisztikus automatával lehetséges pl. a ww -1 nyelv felismerése. Állapottal és üres veremmel elfogadó veremautomaták, ezek kapcsolata: A veremautomata elfogadási feltételét köthetjük a verem üres voltához is. Az elfogadó-állapotok hiánya még azzal az előnnyel is jár, hogy a már ismert konvenciókat alkalmazva, pusztán a mozgási szabályok megadása teljesen specifikálja az automatát. Az állapottal illetve üres veremmel elfogadó automaták osztálya egyenértékű. Biz.:

Az állapottal elfogadó automatában bevezetünk egy új veremürítő állapotot és kiegészítjük az eredeti szabályokat két szabályhalmazzal: •

(qi, , X)=(qe, X) szabályt valamennyi elfogadó állapotra és valamennyi veremszimbólumra felírjuk, illetve a • (qe, , X)=(qe, ) mozgási szabály minden veremszimbólumra lesz érvényes.

Az üres veremmel elfogadó automatából állapottal elfogadót pedig úgy készíthetünk, hogy az elemzés előtt a verem legaljára teszünk egy új szimbólumot (kibéleljük) és csak akkor visszük elfogadó állapotba az automatát ha az elemzés végén ez az egyetlen szimbólum maradt bent a veremben. Mélységbe látó veremautomata, kapcsolata a nem mélységbe látó veremautomatával: Megkísérelhetjük az automata erejét növelni azzal, hogy a veremből nyerhető információt nem korlátozzuk csupán a verem legfelső szimbólumára hanem megengedjük, hogy a mozgás eldöntésénél bizonyos mélységig belelásson a verembe. Mivel azonban a mozgási szabályok száma véges – ami azt jelenti, hogy a belelátási mélység korlátos –, minden mélységbe látó automatához konstruálható olyan veremautomata ami vele ekvivalens és csak a legfelső veremszimbólumot veszi figyelembe. Környezetfüggetlen nyelvtanok és veremautomaták kapcsolata: CF nyelvtanok pont azokat a nyelveket generálják amiket a veremautomaták elfogadnak Környezetfüggetlen nyelvtanból veremautomata konstruálása: Legyen adott egy környezetfüggetlen nyelvtan levezetési szabályaival és definiáljunk egy üres veremmel elfogadó automatát úgy, hogy a verem alfabetája a nyelvtan terminális és nemterminális szimbólumainak uniója legyen, a verem kiinduló tartalma pedig a mondatszimbólum. Az állapothalmaz egyetlen elemet tartalmaz, jelölje ezt q. A mozgási szabályok kétfélék: egyik fajta független a nyelvtan szabályaitól a másik nem. Alakok a következők:

•

(q, a, a)=(q, ) tehát, ha a verem tetején terminális elem van, akkor az a verem tetejéről leemelhető. Arra az esetre, amikor a verem tetején lévő terminális nem azonos a beolvasott karakterrel nincs kádencia, az elemzés ezen az úton zsákutcába jutott. • (q, , A)=(q, ) ezek a szabályok a nyelvtant és így a nyelvet tükrözik. Minden levezetési szabálynak megfelel egy ilyen mozgási szabály. Tehát valahányszor egy nemterminális kerül a verem tetejére, azt egy olyan szabály jobboldalával helyettesítjük, amelynek baloldala éppen a szóban forgó nemterminális.


B16-03

TARTALOMJEGYZÉK

2007. március 15. 19:28

Ez az automata a baloldali elemzést valósítja meg, de nem ez az egyetlen ami a nyelvtani szabályok által generált mondatokat elfogadja. Konstruálható pl. olyan automata is, ami jobboldali elemzést hajt végre: a generált mondatból indul ki és a levezetési szabályok jobboldalát megkeresve, azokat a baloldallal helyettesítve halad mondatszerű formáról mondatszerű formára visszafelé, mindaddig, míg a végén az eredeti mondatot a mondatszimbólumra nem redukálta.


B17-01

TARTALOMJEGYZÉK

2007. március 15. 19:29

Pumpálási lemma környezetfüggetlen nyelvekre: A környezetfüggetlen nyelvek egy fontos tulajdonsága a kettős pumpálás, amely a reguláris nyelvek pumpálásához hasonló jelenség, a szakirodalom vwxyz tételnek nevezi. Legyen adott egy környezetfüggetlen nyelvtan. Amennyiben sikerül ezen nyelvtan segítségével egy kellő hosszúságú q mondatot generálni, akkor ez a mondat felbontható öt részsorozatra q=vwxyz oly módon, hogy a vwi xyi z jelsorozat is mondata a nyelvnek. A környezetfüggetlen nyelvek zártsági tulajdonságai: Metszet: Definiáljunk két nyelvet. A mondataiknak alakja: aibick aibkck Mindkét nyelv (determinisztikus) környezetfüggetlen nyelv. Könnyű belátni, hogy a két nyelv metszete aibici, amiről tudjuk, hogy nem környezetfüggetlen nyelv, hiszen nem tud kettősen pumpálni. Ezek szerint a környezetfüggetlen (és ezen belül a determinisztikus környezetfüggetlen) nyelvek nem zártak a metszet műveletére. Azonban találhatók olyan környezetfüggetlen nyelvek, amelyek metszete nem lép ki a környezetfüggetlen nyelvek halmazából. Például egy környezetfüg getlen nyelvet önmagával metszünk el, akkor az eredmény nyilván az eredeti nyelv lesz. Egy másik triviális példa, hogy ha két környezetfüggetlen nyelv diszjunkt, akkor metszetük az üres nyelv.

Unió: Legyen adott két környezetfüggetlen nyelv nyelvtanával. Amennyiben a két nyelvtan nemterminális szimbólumai nem alkotnak diszjunkt halmazokat, akkor ezt a nemterminálisok átnevezésével érjük el. Legyenek S1 és S2 a két nyelvtan mondatszimbólumai. A két nyelvtan valamennyi levezetési szabályából alkossunk egy új nyelvtant, fosszuk meg az eredeti mondatszimbólumokat ettől a rangjuktól, végül vezessünk be egy új S mondatszimbólumot, és két új levezetési szabályt:

S→S1 ill. S→S2 Triviális, hogy az így konstruált új környezetfüggetlen nyelvtan a két nyelv unióját generálja. A környezetfüggetlen nyelvek tehát zártak az unióképzésre. Komplementer: A környezetfüggetlen nyelvek nem zártak a komplementer műveletre (de Morgan szabályok alapján, tudva hogy a metszet képzésre nem zártak). Konkatenált: Legyen a két nyelv nyelvtanával adott. Gondoskodjunk arról, hogy a két nyelvtan nemterminálisai diszjunkt halmazt alkossanak. Fosszuk meg mondatszimbólum címétől a két nyelv S1 és S2 eredeti mondatszimbólumait, vezessünk be egy új S mondatszimbólumot, egyesítsük a két nyelvtan levezetési szabályait, végül adjuk hozzá az S→S1S2 levezetési szabályt. A nyelvtan valóban a konkatenált nyelvet generálja. Ezek szerint a környezetfüggetlen nyelvek zártak a konkatenáció műveletre.

Tranzitív lezárt: Legyen a környezetfüggetlen nyelv nyelvtanával adott, és mondatszimbóluma legye S. Egészítsük ki a nyelvtan levezetési szabályait két új szabállyal: S→ ill. S→SS


B17-02

TARTALOMJEGYZÉK

2007. március 15. 19:56

Az első szabály gondoskodik arról, hogy az üres jelsorozat eleme legyen a nyelvnek, a második szabály segítségével viszont olyan hosszú, csak a mondatszimbólumból álló mondatszerű formát generálhatunk, amilyen hosszút csak szeretnénk. Ezek mindegyikéből pedig generálható az eredeti nyelvnek egy mondata. El kell érnünk, hogy a mondatszimbólum ne szerepeljen levezetési szabály jobb oldalán. A módszer – új mondatszimbólum bevezetése, és a régihez tartozó szabályok multiplikálása – betűre megegyezik a reguláris nyelvtanoknál követettel.

Determinisztikus környezetfüggetlen nyelvek: Determinisztikusak azokat a környezetfüggetlen nyelvek, amelyekre determinisztikus veremautomatát lehet szerkeszteni. Egy veremautomata akkor determinisztikus, éspedig mind a valódi, mind az epszilon mozgásokra nézve, ha minden esethez, tehát állapothoz, beolvasott karakter, veremtető hármashoz, illetve epszilon mozgások esetében állapot-veremtető párhoz legfeljebb egy mozgási szabály tartozik. A valódi és epszilon mozgások között sem lehet átfedés.

A determinisztikus környezetfüggetlen nyelvek zártsági tulajdonságai: Metszet: az előzőekben bizonyítottuk, hogy nem zártak rá. Komplementer: Nagy nehezen lehet determinisztikus veremautomatából olyan determinisztikus automatát építeni, ami épp az eredeti automata nyelvének komplemensét fogadja el. Tehát erre a műveletre igaz a zártság. Unió: Ha zártak lennének rá, akkor felhasználva, hogy a komplementerképzésre zártak, azok volnának a metszetre is, ami viszont nem helytálló. Tehát nem zártak.

Ebből következik, hogy a csak nemdeterminisztikus veremautomatával elfogadható környezetfüggetlen nyelvek halmaza nem üres, hiszen kell, hogy legyen két olyan determinisztikus környezetfüggetlen nyelv, amelynek az uniója nemdeterminisztikus. A determinisztikus környezetfüggetlen nyelvek halmaza a környezetfüggetlen nyelvek halmazának valódi részhalmaza.


B18-01

TARTALOMJEGYZÉK

2007. március 15. 20:13

A fordítás fogalma: Legyen adott két véges alfabeta ( és ) illetve az ezekből képzett véges, de nem korlátos jelsorozatok halmazai. A fordítás ennek a két megszámlálhatóan végtelen számosságú halmaz keresztszorzatának egy T részhalmaza. A részhalmaz elemei jelsorozatpárok lesznek, ahol az első jelsorozat a * a második pedig a * halmaz eleme. Ha T( , ) akkor az jelsorozat egy fordítása. Összhangban a fordítási köznapi értelmezésével sem az egyértelműségre sem a teljességre nincs semmiféle kikötés. A fordítás egyszerűsége/bonyolultsága nem ad semmilyen felvilágosítást a fordítandó nyelv bonyolultságáról. Pl. egy görög betűkkel leírt szöveget átírni latin betűkre az egyik legegyszerűbb fordítás (izomorfizmus) annak ellenére, hogy a görög 0-ás nyelvosztályú nyelv.

Véges fordító:

Annyiban tér el a véges automatától, hogy nem csak bemeneti, hanem kimeneti berendezése is van. Ha egy véges fordító egy mozgás során kiírt jelsorozatainak maximális hossza k, akkor a mozgások az alábbi leképezést adják: Qx Qx k • Q az állapotok halmaza, • és a bemenő illetve kimenő alfabetát jelenti. Nem a fordító feladata eldönteni, hogy az inputján értelmes szöveg van-e, ezért nincsenek megkülönböztetett állapotok. A közbenső állapotokban a fordító nem állhat meg. Reguláris és környezetfüggetlen nyelvek zártsági tulajdonságai a véges fordítás esetén: A fordító automatákkal végzett műveletet felfoghatjuk olyan nyelvi műveletként, amely egy nyelvhez egy másikat rendel. Amennyiben a fordító automata egy véges fordító, akkor az automatával végrehajtott transzformációra mind a reguláris, mind a környezetfüggetlen nyelvek zártak. Utóbbi állítás bizonyításához a bemenő nyelvből és a véges fordítóból megszerkesztjük a kimenet nyelvét elfogadó automatát. Annyi kikötést/átalakítást teszünk, hogy a fordító a mozgás során vagy csak egyetlen szimbólumot olvas vagy csak egyetlen szimbólumot ír ki illetve a bemenő nyelv veremautomatája egyetlen állapottal bír és üres veremmel fogad el. A veremben most is a fordítandó szöveget generáljuk de ezt nem a bemenettel vetjük össze, hanem követjük, milyen állapotváltozásokon megy át ezt olvasva a véges fordító, hiszen veremautomatánk állapottere azonos a véges fordítóéval. Amikor a fordító a fordított mondat valamilyen szimbólumát készülne kiírni, akkor ezt összevetjük a bemeneten található szimbólummal. Ha a bemeneten levő jelsorozat megegyezik a fordításként kiadni szándékolt jelsorozattal, akkor az automata elfogadja azt.

Veremfordító: Ugyanúgy ahogy a véges automatának van fordító változata, a veremautomatának is van fordító változata, kiegészítve egy output egységgel és a következő mozgási szabályokkal: Qx (

)x

Qx

kx

i

• Q az állapotok halmaza, • , , a bemenet, a verem és a kimenet alfabetája • k és i a mozgások során a verembe beírt illetve a kimeneten megjelenő jelsorozat legnagyobb hossza


B18-02

TARTALOMJEGYZÉK

2007. március 15. 21:02

Szintaxis vezérelt fordítási séma, kapcsolat a veremfordítókkal: A fordításoknak a véges fordítónál lényegesen nagyobb osztálya jellemezhető szintaxis vezérelt fordítási sémákkal. Itt nem a kész szöveg alapján készül el a fordítás, hanem a két mondat, a fordítandó és a fordított egyidejűen generálódik. A levezetés során párhuzamosan lépünk mondatszerű formapárról mondatszerű formapárra. A szintaxis vezérelt fordítási sémák elemei a helyettesítési szabályoknak megfelelő konstrukciók. A szabályok környezetfüggetlen jellegűek. Alakjuk: A→ 2. A pár első tagja a fordítandó szöveget generálja, a második pedig a fordítottat. A sémaelemeknek ugyanolyanoknak kell lenniük, aminek a feltétele, hogy a két mondatszerű formában ugyanazok a nemterminálisok és ugyanannyiszor szerepeljenek. Ez csak úgy biztosítható, ha a sémák elemeihez tartozó két jobboldalban a nemterminálisok nemben és számban megegyeznek. A párt alkotó formulában minden nemterminálisnak egy és csakis egy párja lehet a másik mondatszerű formában. Ha nem csak nemben és számban egyeznek meg a nemterminálisok hanem sorrendben is, akkor a séma neve egyszerű szintaxis vezérelt fordítási séma. Utóbbiakat veremfordítóval lehet realizálni.

Pár példa jellemző nyelvtanokra:


B19-01

TARTALOMJEGYZÉK

2007. március 15. 21:08

Levezetési fa környezetfüggetlen nyelvtanok esetén: Környezetfüggetlen nyelvtanok esetén ábrázolhatjuk a levezetést egy rendezett, irányított gráffal, fával (~levezetési fa). A rendezettség itt annyit jelent, hogy az egy csomópontból kiinduló élek sorrendje kötött. Minden csomópontból annyi él és abban a sorrendben fut ki , amennyi a szabály jobboldalán található szimbólumok száma és a kifutó élek végén sorban a jobboldal megfelelő szimbólumai helyezkednek el. Minden levezetésnek egy és csakis egy levezetési fa felel meg, ugyanakkor egy levezetési fához több levezetés is tartozhat. Példa: Legyen a

nyelvtan. Az a+a*a mondathoz tartozó levezetési fa:

Azokat a levezetéseket, amelyek levezetési fája azonos, tehát ahol a jelsorozat felbontása szintaktikai egységekre megegyező, nem tekintjük lényegesen különböző levezetéseknek. Az olyan nyelvtanokat, ahol minden mondathoz egy és csakis egy levezetési fa tartozik, egyértelmű nyelvtanoknak mondjuk. Természetesen ez nem zárja ki, hogy egy mondatnak több levezetése legyen, azonban azok nem lehetnek lényegesen különbözőek. A levezetések között vannak nevezetesek. Amikor a levezetés során mindig a mondatszerű forma legbaloldalibb nemterminális szimbólumát helyettesítjük, baloldali levezetésről beszélünk. Ugyanígy jobboldali levezetés esetében mindig a mondatszerű forma legjobboldalibb nemterminális szimbólumát bontjuk fel a következő lépésben. Példa: Legyen a nyelvtanunk a következő: Ezzel a nyelvtannal is lehet generálni az a+a*a mondatot. Ehhez a mondathoz tartozó jobboldali levezetés:

A baloldali levezetés:

És a levezetési fák:

Környezetfüggetlen nyelvtanok és nyelvek egyértelműsége: Léteznek olyan nyelvek, amelyről bizonyítható, hogy nem lehet egyértelmű nyelvtannal generálni. Ez esetben tehát a többértelműség nyelvi tulajdonság. Más szóval nincsen minden környezetfüggetlen nyelvnek egyértelmű nyelvtana.


B19-02

TARTALOMJEGYZÉK

2007. március 15. 21:47

Példa: Nem egyértelmű nyelv:

Ez a nyelvtan az

nyelvet generálja.

Az triviális, hogy az adott nyelvtan az aibici alakú mondatot két lényegesen különböző levezetéssel állítja elő. A környezetfüggetlen nyelvtanok elemzésének célja: Nincs olyan módszer, amelynek a segítségével általánosan, minden esetben alkalmazhatóan meg lehetne állapítani egy nyelv vagy egy nyelvtan egyértelmű voltát. Ez azonban nem jelenti azt, hogy egyes konkrét esetekben ne lehetne erre az algoritmikusan eldönthetetlen kérdésre választ kapni. Például az nyelv mondatait alkotó jelsorozatokat elkezdhetjük felbontani egyre kisebb egységekre, majd ezeket újabb egységekre mindaddig, amíg a szintaktikai egységek egyetlen terminális szimbólumból nem állnak és be tudjuk látni, hogy ez a felbontás mindig egyértelmű lesz. Az nyelv esetében pedig nem nehéz pl. az a+a*a kifejezéshez két eltérő felbontást mutatni, ami a többértelműség bizonyítéka.

A gyakorlatban nem mindig sikerül a nyelvtan egyedi tulajdonságait vagy egy szerencsés ötletet felhasználva a nyelvtan egy- vagy többértelműségét bizonyítanunk. Ilyenkor a kérdés megválaszolatlan marad. A szintaktikus elemzés célja egy olyan automata készítése és felhasználása, amelynek feladata minden mondatnak vélt jelsorozat levelezési fájának előállítása. Az elemzés igénye majdnem mindig egyértelmű nyelvtanok esetén lép fel de vannak olyan elemzők amelyek általánosan használhatók. Ilyenek a CYK és az Earley-algoritmusok. Cocke-Younger-Kasami algoritmusa: Az eljárás megköveteli, hogy a nyelvtan Chomsky normálalakban legyen felírva. Az eredeti nyelvtan helyettesítési szabályainak alkalmazását egy sorozat Chomsky szabály végrehajtásával modellezzük. A Chomsky normálalak felírásánál úgy járunk el, hogy a helyettesítési szabályoknak sorszámot adunk, mind az eredeti, mind a Chomsky normálforma esetén. Ha most az eredeti nyelvtan szabályának sorszámát adjuk az őt modellező Chomsky sorozat egyik szabályának, a sorozat többi szabályának pedig nagyobb, az eredeti nyelvtanban nem szereplő sorszámokat adunk, akkor lehetőség van arra, hogy a normálforma szabályaival felírt levezetésből megkapjuk az eredeti nyelvtan levezetését. Az elemzés alulról felfelé halad. Az elemzés során kapott eredmények egy alsó háromszögként rajzolt mátrix mezőit töltik ki. A mezőkbe a Chomsky normálforma nemterminális szimbólumai kerülnek. A mátrix tjk mezejébe akkor kerül egy nemterminális, ha a szóban forgó nemterminális képes a vizsgált mondat j számú konszekutív karakterének generálására, mégpedig éppen a k sorszámú szimbólummal kezdve. A mátrixot alulról felfelé kell kitölteni, vagyis a legalsó, tehát a fenti konvenció értelmében az első sorral kell kezdenünk.


B19-03

TARTALOMJEGYZÉK

2007. március 15. 22:22

Ide olyan nemterminálisok kerülnek, amelyek egyetlen karakterből álló jelsorozatokat képesek generálni. Itt tehát a Chomsky normálalakban engedélyezett A→a alakú szabályokat kell alkalmaznunk. Elképzelhető, hogy egy mezőbe egynél több nemterminális kerül, sőt előfordulhat, hogy egy nemterminális több okból írható be ugyanabba a mezőbe.

A második és az azt követő sorok megszerkesztésekor már a második szabálytípus szerinti levezetési szabályokat kell figyelembe venni. A második sor kitöltésekor azt vizsgáljuk, hogy van-e olyan levezetési szabály, amelynek jobboldala két, az első sorban szomszédos szimbólumból áll. Ha igen, akkor annak a baloldalát kell beírnunk a második sor megfelelő mezejébe. A generált részsorozat hosszának növekedésével az eljárás bonyolódik, hiszen egy hosszabb részsorozat már többféleképpen osztható fel. Így például ha a t43 mezőt kívánjuk kitölteni, ahová definíciónk szerint azok a nemterminálisok kerülnek, amelyek a 3 pozícióval kezdőd , és a 6 pozícióval végződő sorozat négy szimbólumát generálják, akkor a t13-t34, a t23-t25 és a t33-t16 mező párokat kell megvizsgálnunk, ami megfelelő a négy szimbólumból álló jelsorozat 1-3, 2-2 illetve 1-3 arányban történő felosztásának. Példa:

Az Earley-algoritmus: Az algoritmus felülről lefelé fésül. Alapgondolata a következő. Induljunk ki a mondatszimbólumból, és valamennyi lehetséges levezetést tegyük vizsgálat tárgyává. Amennyiben a levezetés során a mondatszerű forma elejére egy terminális szimbólum generálódik, akkor ellenőrizzük, hogy ez a terminális szimbólum megegyezik-e az elemzett mondatjelölt első terminális szimbólumával. Eltérés esetén nyilvánvaló, hogy ezen az úton a szóban forgó jelsorozatot nem lehet levezetni, éppen ezért ezeket a levezetési próbálkozásokat abbahagyjuk. Csak abban az esetben érdemes továbbvinni az elemzést, ha a generált terminális megegyezik a mondatjelölt megfelelő helyén álló terminálisával. Ekkor viszont a levezetéseket minden lehetséges módon tovább kell folytatnunk.


B19-04

TARTALOMJEGYZÉK

2007. március 15. 22:57

Az algoritmus gyakorlati megvalósításakor úgynevezett elemekből csoportokat alakítunk ki. A csoportok számozottak, és sorszámuk azt fejezi ki, hogy a mondatjelöltből már hány szimbólumot vettünk figyelembe. Amennyiben a jelsorozat n karakterből áll, akkor a csoportok számozása 0 és n között változik. A 0 sorszámú csoport azt az állapotot tükrözi amikor még egyetlen karakter sem vettünk figyelembe. Egy k sorszámú csoportban levő elem alakja legyen a következő:

Az elem alakjából következik, hogy a nyelvtanban kell lennie egy A→

1 2

alakú levezetési szabálynak.

Ez a szabály felhasználható a jelsorozat levezetésekor, mégpedig oly módon, hogy a jelsorozatnak az i sorszámú szimbólumától a k sorszámúig terjedő fragmense – nem beleértve az i, de beleértve a k sorszámút – a levezetési szabály 1 részéből levezethető. Új elemeket háromféle módon származtathatunk. • Tekintsük a k-1 sorszámú csoportot, és vizsgáljuk azokat az elemeket, amelyekben a pont után álló terminális megegyezik a jelsorozat következő, tehát k sorszámú karakterével, akkor ezt a szimbólumot a pont elé helyezve a születendő k sorszámú csoport elemét kapjuk. Formálisan,ha a elem a k-1 sorszámú csoport tagja, és a mondatjelölt k sorszámú karaktere b, akkor a

tagja az alapító tagja az új k sorszámú csoportnak. A k-1 sorszámú csoportnak azok az elemei tehát, amelyekben a pont után a mondatjelölt k sorszámú terminálisa áll. Amennyiben a pont mögött „rossz” terminális áll, úgy azok a levezetések, amelyeket ezek az elemek képviselnek a további elemzésben nem vesznek részt. Az így kapott alapító tagok sorsa más és más, aszerint, hogy most a pont után terminális, nemterminális vagy semmi sem áll. Amennyiben az alapító elemekben a pont után terminális található, akkor pillanatnyilag ezen elemek szerepe befejeződött. Rájuk majd akkor kerül újra sor, ha a következő k+1 sorszámú csoport alapító tagjait keressük.

• Tételezzük fel, hogy a k sorszámú csoport alapító tagjai között szerepel a következő elem:

és a nyelvtannak van egy

alakú helyettesítési szabálya.

Ekkor az alábbi elemeket is be kell vennünk ebbe a csoportba:

Amennyiben az új csoportba így bevezetett új elemekben a pont után megint csak nemterminális áll, akkor a fenti származtatást rekurzív módon mindaddig folytatni kell, amíg új, eddig nem szerepelt elemeket fűzhetünk hozzá a csoporthoz. • Vegyük végül azt az esetet, amikor a pont után már nem áll semmi, vagyis egy levezetési szabály jobboldalát teljesen felhasználtuk. Legyen például az újonnan kapott k csoportbeli elem


B19-05

TARTALOMJEGYZÉK

2007. március 15. 23:22

Ekkor vissza kell mennünk ahhoz a csoporthoz, ahol a szóban forgó helyettesítési szabály bekap csolódott a mondat levezetésébe. Ez nyilván a j sorszámú csoport lesz, hiszen az említett sorszámú szimbólumtól kezdve generálja a mondat egy fragmensét. Könnyű belátni, hogy a j sorszámú csoportban kell legyen legalább egy olyan elem amely a fenti összefüggésben szereplő helyettesítési szabályt inicializálta, vagyis ahol a pont után A nemterminális szerepel. Legyen a j sorszámú csoport egy elemének alakja:

Ennek alapján az új, k sorszámú csoportba a következő elemet kell felvennünk:

Az első, sorszám szerint 0 csoport alapító elemeit azok a levezetési szabályok alkotják, amelyek baloldala a mondatszimbólum, hiszen minden levezetésnek ebből kell kiindulnia. Így az összes S→ alakú helyettesítési szabály a formában jelenik meg a legelső csoport elemi között. Az alapító elemek birtokában aztán meg kell kezdeni a csoport felépítését az ismertetett módon. Egy jelsorozatot akkor fogadunk el, ha az a mondatszimbólumból teljes egészében generálható. Ezt úgy ismerhetjük fel, hogy az utolsó csoportban kell legyen egy alakú elem.


B20-01

TARTALOMJEGYZÉK

2007. március 16. 14:41

Balelemzés: Szintaktikus elemző tágabb értelemben minden olyan automata, amelynek feladata a mondat, pontosabban minden mondatnak vélt jelsorozat levezetési fájának előállítása. Így szintaktikus elemzők azok a veremfordítók, amelyek a mondatra mint bemenetre a levezetési fa leírását adják meg mint fordítást. Szűkebb értelemben csak azokat az automatákat tekintjük szintaktikus elemzőknek, amelyeknek működése determinisztikus. Legtöbbször a szintaktikus elemző szerkesztésekor feltételezzük, és megköveteljük, hogy a nyelvtan egyértelmű legyen. Baloldali elemzésnél mindig a mondatszimbólumból indulunk ki, és mindig a mondatszerű forma legbaloldalibb nemterminálisát bontjuk fel a következő lépésben. Azaz a mondatot az elemzés során addig olvastuk el, ameddig az élen álló terminálisokat generálni tudtuk. A következő lépésben a legbaloldalibb nemterminálist úgy kell felbontanunk, hogy a mondat további terminálisai kiadódjanak. Általában a felbontandó nemterminális szimbólum több levezetési szabály baloldalán állhat, vagyis a felbontásnak több alternatívája van. Ezek közül kell a megfelelőt kiválasztani, hiszen egyértelmű nyelvről lévén szó, csak egyetlen felbontás vezethet eredményre. Ennek érdekében az LL(k) elemzők k szimbólumot előre néz és ezekből a terminálisokból igyekszik eldönteni, melyik alternatívát kell választania a helyes folytatáshoz. LL(k) az jelenti, hogy balról jobbra történik az olvasás és az elemzés baloldali, miközben k szimbólumot nézünk előre. Az LL(k)-elemzés algoritmusa (erős és gyenge): Az elemző lényegi része az elemzési tábla, amely a nyelvtan alapján írható fel. A vízszintes fejléc az előretekintés során kapható jelsorozatokat tünteti fel, a függőleges fejléc a verem tetejére kerülő szimbólumokat adja, a tábla mezői a szükséges intézkedésekre tartalmaznak utasításokat. A verem kiinduló tartalma mindig a mondatszimbólum. • Ha a veremtetőn nemterminális van, akkor az elemzési táblából az inputon látottak alapján kinézzük, hogy melyik szabályt kell alkalmazni a megfelelő helyettesítéshez. Ha nincs ilyen szabály akkor hibával leállunk. Ha van, akkor megtörténik a helyettesítés és az outputra íródik a szabály száma. • Ha a veremtetőn terminális van, akkor összehasonlításra kerül az olvasófej alatti terminálissal. Ha megegyeznek, akkor az input elejéről és a verem tetejéről is törlődik a karakter. Ha nem egyeznek meg, akkor az elemzendő sztring nem eleme a nyelvtannak. Ha épp akkor ürül ki a verem amikor a sztring végére értünk, akkor sikeres volt az elemzés. Legyen adott egy G grammatika és legyen adott egy tetszőleges jelsorozat. Jelölje FIRSTkG( )azt a terminálisokból álló és legfeljebb k hosszúságú jelsorozatokat tartalmazó véges nyelvet, amelyet úgy kapunk, hogy vesszük az jelsorozatból a G grammatika segítségével nyerhető összes jelsorozatot, illetve ha azok hosszabbak, mint k, akkor azok első k szimbólumát. Egyszerűbben: -ból generálható terminális sor első k karaktere Valamely nyelvtan egyik A nemterminálisának összes lehetséges levezetési szabálya legyen A→ 1| 2|…| n . A nyelvtan csakis akkor lehet LL(k) nyelvtan, ha a FIRST kG( i) véges nyelvek diszjunktak. Ez a megkötés nem csak szükséges hanem elégséges is abban az esetben, ha A utódai mindenkor legalább k szimbólumot generálnak. Legyen A a nyelvtan egyik nemterminálisa. Ekkor FOLLOWkG(A) jelentse azon, legfeljebb k hosszúságú jelsorozatok halmaza, amelyet az adott nyelvtan az A utódait követve generálhat. Ezt a nyelvet nevezzük az A nemterminális követő nyelvének.


B20-02

TARTALOMJEGYZÉK

2007. március 16. 15:14

Egyszerűbben: A-ból generált terminálisokat kovető k db terminális Ezzel a definícióval az elemző által vizsgált jelsorozatok az alábbi összefüggéssel írhatóak le: FIRSTk(FIRSTk( i) FOLLOWk(A)). Itt a konkatenálás operátora. Amennyiben ezek a kifejezések a különböző alternatívákra diszjunktak az elegendő feltétel arra, hogy ennek alapján a helyes felbontás egyértelműen eldönthető legyen. A nyelvtan tehát LL(k) nyelvtan, mégpedig erősen LL(k) nyelvtan. A feltétel nem szükséges (pl. S→aAbaS|bAabS| ; A→a|b| nyelv esetén az első két szabályban az A-kat különböző nemterminálisoknak tekintve LL(2) elemző készíthető) Amennyiben a produkciós szabályok jobboldalai nem képesek minden esetben generálni a szükséges k karkert, akkor figyelembe kell venni, milyen terminális sorozat származhat a mondatszerű formának az A nemterminálist követő részéből. Erre szolgál a FOLLOW függvény. Így viszont nem vesszük figyelembe azt az információt amelyet a már elolvasott szövegből nyerhetünk. Egy adott levezetésnél ugyanis az A nemterminális előtt álló szöveg olyan kontextust jelenthet, amely bekorlátozhatja az A nemterminális derivátumai után álló jelsorozatokat. Ezt figyelembe véve pontosabb disztinkciót biztosíthatunk. Erről van szó az előző megjegyzésben szereplő LL(2) elemezhető nyelvtan esetében. Felismertük ugyanis, hogy ha megkülönböztetjük az első két szabály generálta A nemterminálist, akkor a két úton nyert kontextus a kettéhasítással született két nemterminálishoz két különböző úgynevezett lokális követő nyelvet rendel. Amennyiben az eredeti nyelvtan valamely nemterminális szimbólumát fel tudjuk bontani olymódon több nemterminálisra, hogy a születésükkor meghatározott követő nyelvek eltérőek legyenek és ennek segítségével a FIRSTk(FIRSTk(Ai) FOLLOWk(Ai)) FIRSTk(FIRSTk(Aj) FOLLOWk(Aj )) 0kifejezéseket diszjunkttá tudjuk tenni, akkor gyengén LL(k) nyelvtanról beszélünk. Itt A iAj az eredeti nyelvtan A nemterminálisának különböző lokális FOLLOW függvénnyel bíró példányai.

Ezt a felbontást célszerű már az induláskor megtenni. Ez bonyolultabb elemző táblához vezet. A nagy tábla minden rovatát egy kisebb tábla alapján szerkesztjük meg, amelynek három oszlopa van, megadva az adott szituációban az előretekintéssel kapható jelsorozatokat, az egyes esetekben szükséges intézkedéseket és ha a verembe új nemterminális(oka)t írunk be, akkor annak(/azoknak) a követő nyelvét. Ha a nagy táblában az indexszel megkülönböztetett újként bevezetett nemterminálisokhoz tartozó sorok között nincsenek ellentétes utasításokat tartalmazók, akkor azok összevonhatók és kiderülhet, hogy erős LL(k) elemzés is elegendő. Viszont mégis értelmes lehet a megkülönböztetés, mert a finomabb felosztású elemző hamarabb jelzi a hibát egy rossz mondatban. Két elemző erősen ekvivalens, ha bármely jelsorozatnál az esetleges hibát ugyanannál az elemzési lépésnél fedezik fel. Két elemző gyengén ekvivalens, ha a jelsorozatnak ugyanannál a szimbólumánál állnak meg, de ebben a helyzetben különböző számú elemzési lépést tesznek meg. Két elemző nem ekvivalens, ha van olyan – szükségképpen hibás – jelsorozat, ahol a két elemző a hibát más-más karakternél detektálja. Egy fontos megjegyzés: A balrekurzív nyelvek nem balelemezhetők ezért a következők szerint kell átírni őket:

LL(k) nyelvtanok és nyelvek: Egy nyelvtanról nem lehet megállapítani, hogy balelemezhető-e, csak azt, hogy egy nyelvtan egy rögzített k esetében LL(k) nyelvtan-e.


B20-03

TARTALOMJEGYZÉK

2007. március 16. 15:40

Vannak olyan nyelvek amelynek egyik nyelvtana nem balelemezhető, de van olyan nyelvtana ami igen. Általánosságban igaz, hogy a balelemezhetőség a nyelvtanhoz kötött tulajdonság. Vannak viszont nem balelemezhető nyelvek is. Ezeknek nincs balelemezhető nyelvtanuk. Egy nyelvet akkor nevezünk LL(k) nyelvnek, ha van LL(k) elemezhető nyelvtana, de nincs k-1 előretekintéssel elemezhető nyelvtana.

Nézzünk egy komplexebb példát:


B21-01

TARTALOMJEGYZÉK

2007. március 16. 16:41

Jobbelemzés: A jobbelemzés során a mondatjelölt szimbólumait olvasva azokat rendre a verembe helyezzük el. Közben minden alkalommal megvizsgáljuk, hogy nem alakult-e ki a veremben egy olyan fragmens, amely egy levezetési szabály jobboldala, és így egy potenciális nyél. Amennyiben ez a fragmens valóban nyélnek bizonyul, akkor ezt letörjük, vagyis helyébe a szabály baloldalán álló nemterminálist írjuk. Az alulról felfelé történő elemzésnek tulajdonképpen ez a lényege. A következő szimbólumot átcsúsztatjuk a verembe, megvizsgáljuk, hogy keletkezett-e nyél, ha igen letörjük, redukáljuk, ha nem, akkor áttérünk a következő szimbólumra.

Az LR(k)-elemzés algoritmusa:

Az algoritmus angol elnevezése shift-reduce. Az egész algoritmus kritikus pontja a nyél létének megállapítása, hiszen a jobboldallal való azonosság még nem feltétlenül jelenti azt, hogy a karaktersorozat nyél. Ezen kívül, ha több levezetési szabálynak azonos a jobboldala, vagy jobboldaluk azonosan végződik, akkor azt is el kell döntenünk, hogy melyik szabály szerint végezzük el a letörést Ezen kérdések eldöntésében segít, ha kissé előre lapozunk, előretekintünk, és ezt az információt felhasználjuk. Az LR(k) nyelvtanok esetében k szimbólummal előretekintve döntünk nyéljelölt ügyében. A jobboldali elemzés fordított irányban halad végig a jobboldali levezetésen . Adott esetben azt, hogy a A→ levezetési szabály jobboldalával azonos fragmenst nyélnek tekintsünk-e vagy sem, és azt az A nemterminálissá törjük-e le, a FIRSTk(k) alapján döntjük el. LR(k) nyelvtanok és nyelvek:

Egy nyelvtan akkor LR(k), ha a vélelmezett nyél után álló k terminális szimbólum alapján egyértelműen eldönthető valódi nyélről van-e szó, és ha igen, melyik szabályt alkalmazva kell azt letörni. Legyen egy nyelvtan két levezetési szabálya: Legyen továbbá két lehetséges jobboldali levezetés:

ekkor LR(k) nyelvtan esetén a azonosságból következik, hogy Az elemzés során egy adott szituációban a követendő eljárás a prefixumtól és az előretekintéssel nyert jelsorozattól függ. Ennek megfelelően az elemező tábla vízszintes fejlécében az előretekintéssel kapott jelsorozatok állnak. Az egyes rovatok, vagyis a függőleges fejléc az életképes prefixumoknak felelnek meg. Lehetnek olyan prefixumok, amelyek esetében az elemzés során követendő eljárás azonos. Tekintsük ezeket az életképes prefixumokat ekvivalensek. Ennek megfelelően az életképes prefixumokat ekvivalencia osztályokba sorolhatjuk, és ekvivalencia osztályonként csak egy rovatot alkalmazunk. Minden életképes prefixumhoz, pontosabban ekvivalencia osztályhoz elemeket fogunk rendelni. Valamely életképes prefixumhoz, illetve ekvivalencia osztályhoz tartozó elem alakja:

Ahol az A→ 1 2 a nyelvtan egy produkciós szabálya, L pedig egy legfeljebb k hosszúságú jelsorozatokból álló véges nyelv.


B21-02

TARTALOMJEGYZÉK

2007. március 16. 18:14

Az adott prefixum néhány utolsó, közelebbről meg nem határozott számú szimbólumát az 1 jelsorozat generálhatja és a mondataiban az A→ 1 2 szabály által generált fragmenst követő első k terminális az L nyelv valamelyik szava. Tételezzük fel, hogy egy adott életképes prefixumhoz valamilyen módon sikerült megszerkesztenünk az összes hozzátartozó elemet. Ekkor két kérdés merül fel: Hogyan állapíthatjuk meg, hogy milyen életképes prefixumokat kell még figyelembe vennünk? Illetve hogyan következtethetünk az elemekből az elemzés során követendő lépésekre. A prefixum csakis olyan szimbólummal folytatódhat – terminális vagy nemterminális –, amely a prefixumhoz tartozó elemekben közvetlenül a pont után áll. Ez megadja milyen új prefixumot kell számításba vennünk. Az új prefixumokhoz rendelt csoportoknak éppen ezek az elemek lesznek alapító tagjai, természetesen azzal az eltéréssel, hogy a pont itt eggyel tovább kerül, vagyis átugorja az őt követő szimbólumot. Amennyiben az így származtatott elemekben a pont után nemterminális áll, akkor ezen nemterminálisok valamennyi levezetési szabályából új elemet kell képeznünk, a pontot a jobboldal elé helyezve, és megállapítva a követő nyelvet.

Egy prefixumot követően azokat a terminálisokat csúsztathatjuk, amely a prefixumhoz tartozó csoport elmeiben a pont után áll. Ez annyit jelent, hogy csak akkor csúsztathatunk, ha az ily módon kialakuló prefixum továbbra is életképes marad. Amennyiben a pontot sikerült átvinni a teljes jobboldalon, és így most már a levezetési szabály után áll, akkor ez annyit jelent, hogy a prefixum nyélben végződik, ami letörhető, feltéve, hogy az előretekintéssel nyert jelsorozat eleme az L követő nyelvnek.

A fentiek alapján haladhatunk prefixumról prefixumra. Az eljárás garantálja, hogy a prefixumok mindig életképesek lesznek. Amennyiben két különböző prefixum csoportja megegyezik, akkor ez annak a jele, hogy a két prefixum azonos ekvivalencia osztályba tartozik, és nem kell az elemző táblában új rovatot nyitnunk A csoport elemei azt is megmondják milyen terminálisokat van jogunk a verembe átcsúsztatni, és mikor és milyen szabály alapján lehet az adott nyelet letörni.

Az indulás és az elfogadás megkönnyítése érdekében vezessünk be egy új mondatszimbólumot, és egy új 0 sorszámú produkciós szabályt: Ahol S az eredeti, míg Skalap az új mondatszimbólum. Minthogy ez a szabály áll minden levezetés elején, ha a jobboldali felvezetés során eljutunk ehhez a szabályhoz és letörjük, akkor ez annyit jelent, hogy a jelsorozatot el kell fogadnunk. Ezen szabály szerinti letörés lesz tehát az akceptálás jele. Az első, vagyis a 0 sorszámhoz tartozó csoport első, alapító eleme az új mondatszimbólum egyetlen produkciós szabálya lesz, végül az L követő nyelv nyilván szintén az üres jelsorozat, hiszen induláskor semmi sem áll a mondatszimbólum után. A világ kezdete minden nyelvtannál:

Magyarázós példa: Építsünk LR(1) elemzőt a posztfix lengyel jelülést generáló nyelvtanhoz (ez azt is demonstrálja, hogy balrekurzív nyelvtanok is jobbelemezhetőek):


B21-03

TARTALOMJEGYZÉK

2007. március 16. 18:36

Az életképes prefixumokat az irodalom a T betűvel és megkülönböztet indexszel jelöli. Ezek szerint első prefixumunk: A többi prefixum, pontosabban prefixum osztály esetében azt a jelölést alkalmazzuk, hogy a származtató prefixumhoz hozzáfűzzük az új szimbólumot. A T0 prefixumhoz tartozó csoport alapítóeleme: Minthogy az E nemterminális előtt pont áll, ehhez hozzá kell fűzzük az alábbi elemeket is:

Minthogy ezek az elemek az alapító elem utolsó szimbóluma, az E nemterminális helyére kerülnek, így követő nyelveik megegyeznek. Ezekben az új elemekben az E nemterminális előtt ismét pontot találunk, így további elemeket fűzhetünk hozzá a csoporthoz. Persze ezekben az új elemekben is ugyanazok a levezetési szabályok szerepelnek majd, más lesz azonban a követőnyelv. Itt ugyanis a felbontható nemterminális, vagyis az első E után egy második E áll, amely végső soron az a terminális szimbólumot generálja.

Ezekben az elemekben megint találhatunk a pont után nemterminális szimbólumot. Természetesen rekurzívan ismét új elemeket vezethetünk, illetve csak vezethetnénk be, hiszen kiderül, hogy a bevezetendő elemek már benne vannak a csoportban. Egyszerűsítve a jelölést, ha azokat az elemeket, amelyek ugyanabból a levezetési szabályból származnak, és ráadásul a pont helyzete is azonos, akkor összevonjuk. Az összevont elemben a követő nyelv a két nyelv uniója lesz. Ennek szellemében megszerkeszthetjük a prefixum osztályokhoz tartozó csoportokat, és majd ennek alapján az elemző táblát.


B21-04

TARTALOMJEGYZÉK

2007. március 16. 19:15

Az életképes prefixumokhoz tartozó elemek alapján az elemző megszerkeszthető. Ez két részből áll. Az első az úgynevezett tevékenységi tábla – action – mondja meg, hogy egy adott szituációban, adott életképes prefixum és adott előretekintés mellet mi a teendő.

Négyféle tevékenység lehetséges, csúsztatás, letörés, akceptálás és hibajelzés. A csúsztatást és az elfogadást az S és A – shift, accept – a letörést a levezetési szabály sorszáma, míg a hibajelzést az üres mező jelenti. A tábla második fele az úgynevezett ugró tábla – go to table. Ez megmondja, hogy az érvényes életképes prefixumhoz egy újabb szimbólumot fűzve, milyen sorszámú prefixumot kapunk. Az elemzés következő lépését aztán ezen prefixum sora alapján kell meghatároznunk. Mindezek után az adott nyelvtan jobboldali elemző táblája a következő:

Prefix tulajdonságú nyelvek, kapcsolatuk az LR(k)-elemzéssel:

Minden determinisztikus CF nyelvhez szerkeszthető LR(1) elemző. A prefix tulajdonságú determinisztikus környezetfüggetlen nyelvekhez készíthető LR(0) elemző. Ez annyit jelent, hogy az elemző előretekintés nélkül el tudja dönteni a helyes folytatást.


B22-01

TARTALOMJEGYZÉK

2007. március 16. 19:34

A precedenciaelemzés fogalma: Az LR(k) elemzők előnye, hogy az esetleges hibát azonnal észreveszik, viszont nagyon terjedelmesek. A hely- és időigény csökkentésére sok módszer született. A precedencia elemzés lényege, hogy a következő karakterre lépés illetve a letörés között csak a prefixum néhány utolsó karaktere alapján dönt. Ha csak egyetlen karaktert veszünk figyelembe a prefixumból miközben az előretekintés is egyetlen karakter, akkor egyszerű precedencia elemzőről beszélünk. Ilyen elemző készítéséhez vizsgáljuk meg a prefixum utolsó és az el nem olvasott szöveg első karakteréből álló szimbólum párokat. Ezek a csúsztatás/letörés tekintetében a következő ún. Wirth-Weber relációkban lehetnek: 1. 2. 3. 4.

az első szimbólummal záródik egy nyél (jele: < ) a két szimbólum egy nyél két szomszédos eleme (=) a második szimbólum egy nyél kezdő karaktere ( >) nincs olyan mondatszerű forma amelyben a két szimbólum egymás mellett állhatna (nil).

E relációkat egy mátrixban szokás ábrázolni. A sor- és oszlopfejlécekben a nyelvtani szimbólumok vannak. Az egyes mezőkbe a megfelelő sorhoz és oszlophoz tartozó szimbólumok egymásutánjaiból képzett párok közötti Wirth-Weber relációk jele kerül (nil helye üresen marad). Mindkét fejlécben szerepel az . Az - pár jelenti az elfogadást.

A jelsorozat olvasásakor állandóan figyeljük a szimbólumpároknak megfelelő mezőket. Ha a reláció nyél eleje vagy nyél közepe, akkor csúsztatunk. A nyél vége reláció esetében letörünk. Ha a potenciális nyél mégsem nyél (egyik levezetési szabály jobboldalával sem egyezik), akkor hibát jelzünk. Ha pedig két levezetési szabály jobboldalán is ugyanez a nyél van, akkor azt mondjuk, hogy a nyelvtan nem egyértelműen invertálható. Ekkor precedencia módszerrel nem elemezhető.

Erős és gyenge precedencia-nyelvtanok: A visszatekintés és az előretekintés hossza alapján (m,n) precedencia nyelvtanokról illetve elemzőkről beszélünk. Az (m,n) precedencia nyelvtanok az LR(n) nyelvtanok általában valódi részhalmazait alkotják – mivel LR(n)-nél a visszatekintés potenciálisan végtelen, míg (m,n) precedencia elemzésnél épp m korlátos. A prefix lengyel jelölés nyelvtana ( E→+EE|*EE|a ) nem egyszerű precedencia nyelvtan, mert ha (1,1) precedencia mátrixot akarunk felírni, akkor az E-a szimbólumpárnál konfliktus helyzet adódik – nem lehet ugyanis tudni, hogy a szóban forgó E az operátor utáni első szimbólum (nyél eleje van), vagy a második (nyél vége van). (2,1) elemző készítésekor a függ leges fejléc legfeljebb két szimbólumból álló jelsorozatokat tartalmaz. Az elemzés során akár nyél eleje akár nyél belseje relációt találunk mindkét esetben csúsztatnunk kell. Ha diszjunktak a precedencia relációk, akkor a nyél eleje és a nyél vége között csak nyél belseje relációk lehetnek. Amennyiben megengedjük a nyél eleje és nyél belseje relációk egyidejű jelenlétét, a letöréskor találkozhatunk olyan szimbólumpárokkal, amelynél nem tudjuk eldönteni, hogy innen számítsuk-e a nyél elejét vagy menjünk tovább új nyél elejét keresni. Ha a két reláció nem diszjunkt volta miatt kiadódó potenciális nyelek közül legfeljebb egy egyezik meg egy jobboldallal akkor ez nem jelent gondot az elemzésben. Ilyen esetekben gyenge precedencia nyelvtanokról beszélünk. Tehát:

A gyenge precedencia nyelvtanok esetében a három reláció közül a nyél eleje és nyél belseje esetében bizonyos feltételek mellett nem követeljük meg a két halmaz diszjunkt voltát.


B22-02

TARTALOMJEGYZÉK

2007. március 16. 19:47

Tovább bővíthetők az engedmények, ha feltesszük, hogy A és B között mind a nyél eleje mind a nyél belseje relációk érvényesek, akkor a verem tartalmazhat egy olyan AB fragmenst, hogy az előtt a nyél eleje, a jelsorozat után a nyél vége reláció áll. Ha még van a nyelvtannak C→ AB és D→ B alakú levezetési szabálya is, akkor nem teljesül az a megkötés, hogy a potenciálos nyelek közül legfeljebb egy jelent valóságos alternatívát. Viszont ha az A és D szimbólumok között semmilyen reláció nem érvé-nyes, akkor a rövidebb nyél letörésével olyan sorozat alakulna ki, amely nem lehet része egyetlen jobbol-dali levezetéssel előálló mondatszerűformának sem, és így szükségképpen zsákutca. Ha egy nyelvtan esetében a fenti feltételek teljesülnek és mindig csak a hosszabb nyéljelölt letörése vezethet eredményre, akkor ezt a nyelvtant is gyenge precedencia nyelvtannak tekintjük. Gyenge precedencia nyelvtan pl. az infix aritmetikai kifejezéseket generáló nyelvtan. Erősen és gyengén precedencia-elemezhető nyelvek kapcsolata: A gyenge precedencia nyelvtanokhoz mindig szerkeszthető olyan erős precedencia nyelvtan amely ugyanazt a nyelvet generálja. Az operátor precedencia elemzés:

Az operátor precedencia elemzés a precedencia elemzőnél is gyorsabb és kisebb hely-és időigényű. Egy nyelvtan akkor operátor nyelvtan, ha a levezetési szabályok jobboldalán sehol nem áll két nemterminális szombólum egymás mellett. Pl. az infix nyelvtan. Az elemzés lényege, hogy a precedencia relációkat csak a terminális szimbólumok között értelmezzük (a precedenciamátrix fejléceiben csak terminálisok vannak). A terminálisok közé beékelődő esetleges egyetlen nemterminális szimbólumot nem vesszük tudomásul és a bal- illetve jobboldalán álló terminálisokat mint szomszédokat kezeljük. A továbbiakban szabályszerű precedencia elemzést végzünk, csak az igényel néha megfontolást, hogy letörés esetén a szélső nemterminálist beleértsük-e a nyélbe vagy sem. Ezzel a stratégiával elegendő egyetlen nemterminális szimbólumot használni a nyelvtanban ugyanis minden precedenciára vonatkozó információ közvetlenül kiolvasható a precedencia mátrixból.


Számításelmélet Szigorlat

Recommend Documents