Algoritmuselmélet - PPZH, 2013.05.23.

← Vissza az előző oldalra – Algoritmuselmélet

2013.05.23 - PPZH megoldásai

1. Feladat (Van megoldás)

Tudjuk, hogy az Értelmezés sikertelen (ismeretlen „\textsc” függvény): {\displaystyle f(n), g(n) : \textsc{N} \rightarrow \textsc{N} } függvényekre igaz, hogy $f(n)=\mathrm{\Omega }(logn)$ és $g(n)=\mathrm{\Theta }(n^4).$ Lehetséges-e, hogy:

(a) $f(n)=\mathrm{\Theta }(g(n))?$

(b) $g(n)=O(f(n))?$

(Ez két, egymástól függetlenül megválaszolandó kérdés.)

kinyitMegoldás

a)

• Ha $f(n)=n^4,g(n)=n^4$
• Akkor igaz az, hogy:
  • $f(n)=\mathrm{\Omega }(logn)\Rightarrow n^4=\mathrm{\Omega }(logn)$
  • És az is, hogy $f(n)=\mathrm{\Theta }(g(n))\Rightarrow n^4=\mathrm{\Theta }(n^4)$
• Tehát lehetséges.

b)

• Ha $g(n)=n^4,f(n)=n^4$
• Akkor igaz az, hogy:
  • $g(n)=\mathrm{\Theta }(n^4)\Rightarrow n^4=\mathrm{\Theta }(n^4)$
  • És az is, hogy $g(n)=O(f(n))\Rightarrow n^4=O(n^4)$
• Tehát lehetséges.

2. Feladat (Van megoldás)

Távmunkában fogunk dolgozni mostantól n napon át. Nem kell minden nap bejárnunk, de at alábbi három feltételt be kell tartanunk:

• két egymást követő benti munkanap között legfeljebb k nap telhet elm
• az n nap során legfeljebb egyszer maradhatunk pontosan k napig távol,
• az első és a n. napon be kell mennünk.

Sajnos a kék metróval járunk dolgozni, ami hol jár, hol nem, de szerencsére megjósolták nekünk, hogy a kötvetkező n napoban mely napokon lesz üzemzavar, ezeken a napokon nem akarunk dolgozni menni (az első és az utolsó napon nem lesz üzemzavar). Adjon algoritmust, ami a jóslás eredmények ismeretében O(nk) lépésben meghatározza, hogy legkevesebb hány bemenéssel tudjuk megúszni ezt az n munkanapot.

kinyitMegoldás

A megoldást először a 2. feltétel figyelembevétele nélkül írom le, anélkül sokkal egyszerűbb.

Vegyünk fel egy n méretű tömböt. Ennek az i-edik eleme legyen az a szám, ahány napot muszáj bent lennünk, ha az i. napon be akarunk menni.

Ha az i. napon üzemzavar van, akkor a tömb i-edik eleme legyen végtelen. Ha nincs üzemzavar, akkor legyen a tömb előző legfeljebb k elemének a minimuma plusz egy (amikor az előző k elemet nézzük, ott k-1 kihagyást engedünk meg).

Pl, ha n = 7, k = 3, és a 2. és az 5. napon lesz üzemzavar:

nap	1	2	3	4	5	6	7
érték	1	végtelen	2	2	3	végtelen	3

A második feltétel figyelembevételéhez egy két soros táblázattá kell bővítenünk a tömböt. A második sorába tároljuk azt, hogy hány napot kötelező bent lennünk, ha az i. napon bent vagyunk, és kihasználjuk azt is, hogy egyszer pontosan k napot is lehetünk távol. Ennek az értéke vagy végtelen, vagy a minimuma két lehetőségnek:

• Ha most használtuk fel a k napos lógást, akkor k+1 nappal ezelőtti, első sorbeli elem + 1.
• Ha már korábban felhasználtuk a k napos lógást, akkor az előző k napban nézzük a második sor elemeinek a minimumát + 1.

Pl, ha n = 7, k = 2, és az 5. és a 6. napon lesz üzemzavar:

nap	1	2	3	4	5	6	7
első sor	1	2	2	3	végtelen	végtelen	végtelen
második sor	1	2	2	2	végtelen	végtelen	4

Az eredmény természetesen a második sor n-edik eleme. Az algoritmus O(n*k) lefut, hiszen 2*n mezőre kell k elem minimumát kiválasztani, ami - feltéve, hogy két elem minimimuma egy lépés - 2*n*k lépést jelent ami = O(n*k)

3. Feladat

TODO

kinyitMegoldás

TODO

4. Feladat

TODO

kinyitMegoldás

TODO

5. Feladat (Van megoldás)

Egy kupac elemeit preorder bejárás szerint kiolvasva az alábbi számsorozatot kapjuk: $1,17,19,21,22,31,37,2,8,3.$ Rekonstruálható-e ebből a kupac?

kinyitMegoldás

• A kupac egy teljes bináris fa, így tudjuk, hogy mi a fa alakja.
• Nincs is más dolgunk, mint felrajzolni, majd a preorder bejárás alapján beírni az elemeket a megfelelő csúcsokba, és ellenőrizni, hogy sérül-e valahol a kupac adatszerkezet egy tulajdonsága.

• Látszik, hogy minden rendben van, így a kupac rekonstruálható.

6. Feladat

TODO

kinyitMegoldás

TODO

7. Feladat

TODO

kinyitMegoldás

TODO

8. Feladat

TODO

kinyitMegoldás

TODO