AlgElmeletiKerdesekKidolgozas

A VIK Wikiből
A lap korábbi változatát látod, amilyen Unknown user (vitalap) 2012. október 21., 20:52-kor történt szerkesztése után volt. (Új oldal, tartalma: „{{GlobalTemplate|Infoalap|AlgElmeletiKerdesekKidolgozas}} * Lehet, hogy rossz. * Lehet, hogy nem ezt akarják válasznak. __TOC__ Cs. Cs. D., cc699 kukac hszk.bme.hu…”)
(eltér) ← Régebbi változat | Aktuális változat (eltér) | Újabb változat→ (eltér)

Ez az oldal a korábbi SCH wikiről lett áthozva.

Ha úgy érzed, hogy bármilyen formázási vagy tartalmi probléma van vele, akkor, kérlek, javíts rajta egy rövid szerkesztéssel!

Ha nem tudod, hogyan indulj el, olvasd el a migrálási útmutatót.


  • Lehet, hogy rossz.
  • Lehet, hogy nem ezt akarják válasznak.

Cs. Cs. D., cc699 kukac hszk.bme.hu, 2009. január, v0.2

Írja le a piros-kék algoritmust a piros és kék szabályokkal együtt!

Az algoritmust minimális súlyú feszítőfák keresésére használják. A G gráf éleit kiszínezzük pirosra, vagy kékre, úgy hogy közben a gráf végig takaros legyen. Végül, ha már minden élet kiszíneztünk, a kék élek összessége adja a keresett eredményt. f Takaros színezés: G gráf éleinek színezésére az algoritmus minden szakaszában igaz, hogy van olyan minimális költségű feszítőfája, ami az összes kék élet tartalmazza, és egyetlen piros élet sem tartalmaz.

Az alábbi két szabályt tetszőlegesen alkalmazzuk addig, míg van színezetlen él a gráfban:

  • Kék szabály: Kiválasztunk egy olyan nem üres XV csúcshalmazt, amiből nem vezet ki kék él. Ezután egy legkisebb súlyú X-ből kimenő (színtelen) élet fessünk kékre.
  • Piros szabály: Válasszunk G-ben egy egyszerű kört, amiben nincs piros él. Ezután a legnagyobb súlyú színtelen élet fessük pirosra.

A szabályok alkalmazása után mindig takaros színezést kapunk, és mindig tudjuk folytatni az algoritmust addig, míg minden élet ki nem színezünk.

Tk. 153. oldal

Definiálja, hogy mikor nevezünk egy nyelvet NP-teljesnek, és adjon meg két ismerten NP-teljes nyelvet a definíciójukkal együtt!

Az LI* nyelv NP-teljes, ha LNP, és minden LNP nyelv esetén létezik LL Karp-redukció.

3-SZÍN nyelv: A három színnel kiszínezhető gráfokból álló nyelv. NP-teljes, mert 3-SAT 3-SZIN, és 3-SAT NP-teljes.

H nyelv: A H Hamilton-kört tartalmazó gráfokból álló nyelv. NP-teljes, mert IH H és IH NP-terljes.

Tk. 271. oldal

Definiálja a közelítő algoritmus fogalmát maximalizálási problémákra! Írja le az általános gráfban maximális méretű párosítás keresésének problémájára adott 2-közelítő algoritmust, és bizonyítsa is be, hogy az adott algoritmus 2-közelítő!

TODO

Definiálja a 2-3 fákat. Írja le a BESZÚR művelet megvalósítását, és adja meg a lépésszámát is. Indoklás nem szükséges.

A 2-3 fa egy olyan keresőfa, amelyben a tárolni kívánt rekordok a fa leveleiben vannak, balról jobbra növekvő sorrendben. Egy belső csúcs kétféle lehet: 2 kulcsból és 3 mutatóból áll, vagy 1 kucsból és két mutatóból áll:

m1 s1 m2 s2 m3
m1 s1 m2

A kulcsokra fennáll, hogy s1<s2, valamint m1 minden kulcsa kisebb, mint s1, m2-ben s1 a legkisebb kulcs, m3-ban s2 a legkisebb kulcs.

A fa levelei a györkértől egyforma távolságra vannak.

BESZÚR: Először KERES(s,S)-t csinálunk, ha megtaláljuk s-t, akkor végeztünk, ha nem akkor, ha a legalsó belső csúcs a kereső út mentén:

  • 1 kulcsú: A megfelelő helyre beszúrjuk az s-t attól függően, hogy a másik két levélnél kisebb, nagyobb, vagy köztük van. A kulcsokat is eszerint módosítjuk.
  • 2 kulcsú: A csúcsvágás módszerét alkalmazzuk. A kétkulcsú rekordot szétbontjuk két darab egykulcsúra, kiegészítve s-el. A keletkező új csúcsot be kell jegyeznünk a régi (szétvágott) csúcs apjába ugyanezzel a módszerrel. Ha esetleg ez a folyamat felgyűrűzik a gyökérig, akkor egy új gyökeret veszünk fel és a mutatókat a két szétvágott részfára állítjuk.

Tk. 67. oldal

Definiálja a Karp-redukciót, és bizonyítsa be, hogy ha L1P és L2L1, akkor L2P.

Az f:I*I* leképezés az L1I* nyelv Karp-redukciója az L2I* nyelvre, ha

  • Tetszőleges xI* szóra xL1 akkor és csak akkor, ha f(x)L2.
  • fFP, azaz f (leképezés) polinom időben számolható.

L1L2 L1-nek van Karp-redukciója L2-re.

A kérdésben gonoszul meg vannak cserélve az indexek :-)

A definíciót használva célunk az, hogy polinom időben felismerjük L2-t. Először kiszámoljuk f(x)-et. Definíció b pontja szerint, ennek időigénye max. c1nk. Ezután el kell döntenünk, hogy f(x)L1 igaz-e? Mivel L1P, ezért ez polinom idejű, vagyis összességében c2(c1nk)l ideig tart. A definíció a pontja szerint annak az eldöntése, hogy xL2 azonos annak az eldöntésével, hogy f(x)L1, ezt pedig O(nkl) idő alatt eldöntöttük, vagyis L2P.

Tk. 270. oldal

Definiálja az euklideszi utazóügynok problémát, és vázlatosan írja le a megoldására szolgáló közelítő algoritmust. Adja meg az algoritmus approximációs tényezőjét is. Indoklás nem szükséges.

Probléma: Adott egy n pontú Kn teljes gráf, és egy éleihez rendelt nem negatív d súlyfüggvény. A súlyfüggvényre teljesül a háromszög-egyenlőtlenség, vagyis u,v,w-re d(u,w)<d(u,v)+d(v,w). Keressünk minimális összsúlyú Hamilton-kört! (Az ebből származó eldöntési probléma egyébként NP-teljes.)

Közelítő algoritmus:

  • Vegyük Kn gráf minimális összsúlyú feszítőfáját\footnote{Kruskal vagy Prim módszerrel könnyen megy.}(T), legyen az összsúlya s.
  • Tegyük irányítottá a T-t: uv élből uv,vu élek lesznek. (T)
  • Mivel T-ben minden pontnak a ki-foka megegyezik a be-fokával, így van benne Euler-séta(kör).
  • Az Euler-séta pontjai legyenek: u=v1,v2,,v2n2,v2n1=u. Ennek összsúlya 2s.
  • Ezután a Hamilton-kör-t az u-tól kezdjük és felveszünk hozzá pontokat úgy, hogy olyan pontokat vegyünk fel, amik az Euler-sétában legelőrébb vannak (vk, ahol k min.), de nem szerepelnek még a Hamilton-körben. Ha már nincs ilyen pont, akkor az u-t mégegyszer hozzávéve zárjuk a kört.
  • A Hamilton-kör súlya legfeljebb annyi, mint az Euler-séta súlya (felhasználva a háromszög-egyenlőtlenséget), tehát 2s. Bármely Hamilton-körből egy élet elhagyva Euler-sétát kapnánk, aminek a súlya min. s, tehát 2-szeres szorzó erejéig közelíti az algoritmus az optimálist.

Tk. 308. oldal

Definiálja a piros-fekete fákat. Mi a kapcsolat egy csúcs magassága és fekete magassága között? Állításait bizonyítsa is be!

A piros-fekete fa egy bináris fa, amelyre igazak az alábbi szabályok:

  • levél csúcsnak két fia van
  • elemeket a belső csúcsokban tárolunk, nem a levelekben
  • keresőfa tulajdonság érvényesül
  • csúcs piros vagy fekete
  • a gyökér és a levelek feketék
  • egy piros csúcs mindkét gyereke fekete
  • v csúcsra, az összes v-ből levélbe vezető úton ugyanannyi fekete csúcs van.

Legyen m(v) a v csúcs magassága, vagyis, hogy hány élből áll a v-ből levélbe vezető leghosszabb út (lefelé), ha v levél, akkor m(v)=0.

Legyen mf(v) a v csúcs fekete magassága, vagyis, hogy v-ből levélbe vezető utakon hány fekete csúcsot látunk (v-t kivéve).

Ekkor v csúcsra teljesül, hogy m(v)2mf(v)m(v).

Bizonyítás: mf(v)m(v) triv. igaz, valamint mivel piros csúcsok gyerekei feketék, és a levelek is feketék, a csúcsok legalább fele fekete.

Írja le a mélységi bejárás algoritmusát. (A pontok kétféle számozása és az élek osztályozása nem kell.) Mennyi az algoritmus lépésszáma mátrixos, illetve éllistás megadás esetén és miért?

Először addig megyünk előre az élek mentén, amíg olyan pontba nem érkezünk, ahonnan már nem tudunk még meg nem látogatott pontba menni. Ekkor visszalépünk az utolsó előtti pontra, és az ő szomszédait járjuk be, ha ott is végeztünk, akkor még egyet visszalépünk, s.í.t. Egy pontot akkor nevezünk befejezettnek, ha már minden szomszédját meglátogattuk. Ha a kezdőpontot is bejefeztük, akkor bejártuk a gráfot, vagy legalábbis egy komponensét.

Pszeudo kóddal:

procedure bejar
	begin
	for v:= 1 to n do
		bejarva[v] := false;
	for v:= 1 to n do
		if bejarva[v] = false then
			mb(v)
	end

procedure mb(v : node)
	var
		w: node;
	begin
	bejarva[v] = true;
	(*a szomszedok bejarasa*)
	for minden L[v]-beli w csucsra do 
		if bejarva[w] = hamis then
			mb(w)
	end

Éllistás bejárásnál a lépésszám O(n+e), mert minden csúcsra egyszer hívjuk meg az mb()-t, és ott minden csúcs szomszédját egyszer vizsgáljuk meg. Szerintem a mátrixos reprezentációnál is lineáris idejű az algoritmus, de egyébként TODO.

Tk. 129. oldal


TODO

  • Definiálja az univerzális és a megállási nyelvet.
  • Mi a vizsonyuk az RE osztályhoz? (Indoklás nem kell.)
  • Az univerzális nyelv benne van-e az R osztályban? Válaszát indokolja is!

Írja le a legrövidebb utak keresésére szolgáló Dijkstra-algoritmust. Mi az algoritmus alkalmazásának feltétele? (Az algoritmus helyességét nem kell bizonyítani.) Mennyi az algoritmus lépésszáma?

Az élsúlyok nem negatív számok. A KÉSZ halmazba tesszük azokat a csúcsokat, amelyek legrövidebb távolságát már ismerjük. D tömbben a csúcsok eddigi legrövidebb távolsága van, C[x,y] az xy él súlyát jelenti.

Pszeudo kód:

KESZ := {s}
for minden v in V csucsra do
	D[v] := C[s,v];
for i:= 1 to n-1 do begin
	x := az a csucs, V \ KESZ-bol, hogy D[x] min.;
	for minden w in V \ KESZ csucsra do
		D[w] := min(D[w], D[x] + C[x,w]);
end

Az első ciklus O(n) időt emészt fel, a második ciklusban a minimum keresés és a belső ciklus is O(n), és ezek n1-szer futnak le, tehát összességében O(n2) a lépésszám. Ezt éllistával, a D-tömb szerint kupacba rendezve a még nem kész csúcsúkat O((n+e)logn)-re vihető le, megfelelő d-kupaccal pedig akár O(e)-re is.

Definiálja az UNIÓ-HOLVAN adatszerkezetet. Mennyi az egyes műveletek lépésszáma tömbös illetve fás megvalósítás esetén? (Indoklás nem szükséges.)

Az UNIÓ-HOLVAN adatszerkezet egy véges S halmaz partícióit (egymással diszjunkt, de összegezve S-t kiadó halmazok) tárolja. Két műveletet értelmezünk ezzel kapcsolatban: az UNIÓ(Ui,Uj) egyesít két partíciót, a HOLVAN(v) visszadja, hogy v melyik partícióban van.

Az elemeket egy fában és egy tömbben tároljuk. A fa csúcsaiban tároljuk az adott halmaz elemeit, a halmaz neve az őt ábrázoló fa gyökerében van. Két halmaz UNIÓ-jakor a nagyobbik fa gyökeréhez hozzácsapjuk gyerekként a kisebbik fa gyökerét. A tömböt az S elemeivel indexeljük, ami tartalmaz egy pointert, ami a fában az adott indexű elemre mutat. A HOLVAN hívás során ez alapján a mutató alapján elindulva a szülő pointereket követve eljuthatunk a fa gyökeréig, és megtudhatjuk, hogy melyik halmazban van az adott elem. A HOLVAN költsége O(logn), az UNIÓ költsége O(1).

Tk. 163. oldal

Definiálja a P és az NP nyelvosztályt; mi az egymáshoz való viszonyuk? Válaszát indokolja is meg.

P azon nyelvek halmazát jelöli, amelyekhez van olyan algoritmus, ami x bemenetre eldönti, hogy Értelmezés sikertelen (formai hiba): {\displaystyle x \stackrel{\text{\tiny ?}}{\in} P} , és az algoritmus lépésszáma O(|x|k), k konstans pozitív számra.

NP azon L nyelvek halmaza, amelyre teljesül, hogy k>0 konstans és LpP nyelv, valamint

xLy,|y|=O(|x|k),(x,y)Lp.

Viszonyuk: PNP. Nyilvánvaló, hiszen tanú nélkül is eldönthető polinom időben, hogy Értelmezés sikertelen (formai hiba): {\displaystyle x \stackrel{\text{\tiny ?}}{\in} L} . (L=Lp)


Átalakítás LaTeX forrásból: aldaris - 2009.01.27.

Összeállította: Csaba - 2009.01.26.