AlgElmeletiKerdesekKidolgozas

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 $X\subset V$ 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 $L\subseteq I^{*}$ nyelv NP-teljes, ha $L\in NP$, és minden $L'\in NP$ nyelv esetén létezik $L'\prec L$ Karp-redukció.

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

H nyelv: A H Hamilton-kört tartalmazó gráfokból álló nyelv. NP-teljes, mert IH $\prec$ 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:

$m_{1}$

$s_{1}$

$m_{2}$

$s_{2}$

$m_{3}$

$m_{1}$

$s_{1}$

$m_{2}$

A kulcsokra fennáll, hogy $s_{1}<s_{2}$, valamint $m_{1}$ minden kulcsa kisebb, mint $s_{1}$, $m_{2}$-ben $s_{1}$ a legkisebb kulcs, $m_{3}$-ban $s_{2}$ 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 $L_{1}\in P$ és $L_{2}\prec L_{1}$, akkor $L_{2}\in P$.

Az $f:I^{*}\rightarrow I^{*}$ leképezés az $L_{1}\subseteq I^{*}$ nyelv Karp-redukciója az $L_{2}\subseteq I^{*}$ nyelvre, ha

• Tetszőleges $x\in I^{*}$ szóra $x\in L_{1}$ akkor és csak akkor, ha $f(x)\in L_{2}$.

• $f\in FP$, azaz $f$ (leképezés) polinom időben számolható.

$L_{1}\prec L_{2}\circeq$ $L_{1}$-nek van Karp-redukciója $L_{2}$-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 $L_{2}$-t. Először kiszámoljuk $f(x)$-et. Definíció b pontja szerint, ennek időigénye max. $c_{1}n^{k}$. Ezután el kell döntenünk, hogy $f(x)\in L_{1}$ igaz-e? Mivel $L_{1}\in P$, ezért ez polinom idejű, vagyis összességében $c_{2}(c_{1}n^{k})^{l}$ ideig tart. A definíció a pontja szerint annak az eldöntése, hogy $x\in L_{2}$ azonos annak az eldöntésével, hogy $f(x)\in L_{1}$, ezt pedig $O(n^{kl})$ idő alatt eldöntöttük, vagyis $L_{2}\in P$.

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ú $K_{n}$ 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 $\forall 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 $K_{n}$ 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: $u-v$ élből $u\rightarrow v,v\rightarrow u$ é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=v_{1},v_{2},\dots ,v_{2n-2},v_{2n-1}=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 ($v_{k}$, 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:

• $\forall$ 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
• $\forall$ csúcs piros vagy fekete
• a gyökér és a levelek feketék
• egy piros csúcs mindkét gyereke fekete
• $\forall 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 $m_{f}(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 $\forall v$ csúcsra teljesül, hogy ${\frac {m(v)}{2}}\leq m_{f}(v)\leq m(v).$

Bizonyítás: $m_{f}(v)\leq 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 $x\rightarrow y$ é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 $n-1$-szer futnak le, tehát összességében $O(n^{2})$ 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)\log n)$-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Ó$(U_{i},U_{j})$ 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(\log n)$, 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 $\forall 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 $\exists k>0$ konstans és $L_{p}\in P$ nyelv, valamint

$x\in L\Leftrightarrow \exists y,|y|=O(|x|^{k}),(x,y)\in L_{p}.$

Viszonyuk: $P\subseteq NP$. 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=L_{p})$

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

Összeállította: Csaba - 2009.01.26.