Algoritmuselmélet - PZH, 2013.04.24. - Laptörténet

Geriboss: elírások javítva

2014-03-30T16:34:12Z

elírások javítva

← Régebbi változat		A lap 2014. március 30., 18:34-kori változata
21. sor:		21. sor:

	===2. Feladat (Van megoldás)===		===2. Feladat (Van megoldás)===
	Adott egy teljes bináris fa, a csúcsaiba egész számok vannak írva, összesen ''n'' darab (a fa nem feltétlenül bináris keresőfa). Adjon algoritmust, ami <math>O(n)</math> lépésben megkeres egy olyan csúcsot a fában, aminek a részfája kupac, és aminek a magassága a ~~legető~~ legnagyobb az összes ilyen csúcs közül.		Adott egy teljes bináris fa, a csúcsaiba egész számok vannak írva, összesen ''n'' darab (a fa nem feltétlenül bináris keresőfa). Adjon algoritmust, ami <math>O(n)</math> lépésben megkeres egy olyan csúcsot a fában, aminek a részfája kupac, és aminek a magassága a lehető legnagyobb az összes ilyen csúcs közül.
	{{Rejtett		{{Rejtett
	\|mutatott=<big>'''Megoldás'''</big>		\|mutatott=<big>'''Megoldás'''</big>
31. sor:		31. sor:
	*Továbbá a teljes bináris fára azért van szükség, mert így "jóval egyszerűbb" a feladat, és nem kell szívózni annak vizsgálatával, hogy az adott részfa teljes bináris fa-e (ugyebár ez a kupac egyik fontos tulajdonsága).		*Továbbá a teljes bináris fára azért van szükség, mert így "jóval egyszerűbb" a feladat, és nem kell szívózni annak vizsgálatával, hogy az adott részfa teljes bináris fa-e (ugyebár ez a kupac egyik fontos tulajdonsága).
	}}		}}
	Minden csúcsban 3 adatot fogunk számon tartani: Érték (ez persze adott már), részfa magassága (~~jelüljük~~ M-mel), és egy bool érték (IGAZ/HAMIS, jelöljük B-vel), hogy igaz-e a részfájára, hogy az kupac.		Minden csúcsban 3 adatot fogunk számon tartani: Érték (ez persze adott már), részfa magassága (jelöljük M-mel), és egy bool érték (IGAZ/HAMIS, jelöljük B-vel), hogy igaz-e a részfájára, hogy az kupac.
	*Első lépésben a legalsó szinteken lévő csúcsok esetén <math>M:=1, B:=IGAZ</math>.		*Első lépésben a legalsó szinteken lévő csúcsok esetén <math>M:=1, B:=IGAZ</math>.
	*Legyen egy változónk, amiben tároljuk, hogy melyik csúcsra igaz, hogy a részfája a "legnagyobb" kupac (kezdeti értéke legyen mondjuk az egyik legalsó szinten lévő csúcs).		*Legyen egy változónk, amiben tároljuk, hogy melyik csúcsra igaz, hogy a részfája a "legnagyobb" kupac (kezdeti értéke legyen mondjuk az egyik legalsó szinten lévő csúcs).
44. sor:		44. sor:
	Kukori és Kotkoda egy-egy bináris fára gondolnak (nem feltétlenül bináris keresőfákra). Következik-e, hogy a két fa azonos, ha		Kukori és Kotkoda egy-egy bináris fára gondolnak (nem feltétlenül bináris keresőfákra). Következik-e, hogy a két fa azonos, ha

	'''(a)''' inorder bejárással ~~kilolvasva~~ a két fát ugyanazt a számsorozatot kapják?		'''(a)''' inorder bejárással kiolvasva a két fát ugyanazt a számsorozatot kapják?

	'''(b)''' preorder bejárással kiolvasva a két fát ugyanazt a számsorozatot kapják?		'''(b)''' preorder bejárással kiolvasva a két fát ugyanazt a számsorozatot kapják?
67. sor:		67. sor:

	===4. Feladat===		===4. Feladat===
	Éllistával adott n csúcsú, ~~élsúlyzott~~, irányítatlan gráfként ismerjük egy ország úthálózatát (a csomópontok a városok, az élek a közvetlen összeköttetések a városok között). Az élek súlya azt adja meg, hogy hány (egész) perc alatt tudjuk megtenni az adott útszakaszt. Nagy havazás várható, de szerencsére pontosan tudjuk a ~~követekző~~ k percre, hogy mely élek (utak) mikortól nem lesznek járhatóak. Ha egyszer járhatatlanná válnak, akkor úgy is maradnak, ezután már az úton nem lehet közlekedni, és ha épp az adott élen vagyunk, amikor az járhatatlanná válik, akkor elakadunk.		Éllistával adott n csúcsú, élsúlyozott, irányítatlan gráfként ismerjük egy ország úthálózatát (a csomópontok a városok, az élek a közvetlen összeköttetések a városok között). Az élek súlya azt adja meg, hogy hány (egész) perc alatt tudjuk megtenni az adott útszakaszt. Nagy havazás várható, de szerencsére pontosan tudjuk a következő k percre, hogy mely élek (utak) mikortól nem lesznek járhatóak. Ha egyszer járhatatlanná válnak, akkor úgy is maradnak, ezután már az úton nem lehet közlekedni, és ha épp az adott élen vagyunk, amikor az járhatatlanná válik, akkor elakadunk.
	Adjon O(k(n+e)) lépést használó algoritmust, ami az adatok ismeretében el tudja dönteni, hogy el lehet-e jutni A városból B városba, ha most azonnal elindulunk!		Adjon O(k(n+e)) lépést használó algoritmust, ami az adatok ismeretében el tudja dönteni, hogy el lehet-e jutni A városból B városba, ha most azonnal elindulunk!
	{{Rejtett		{{Rejtett
122. sor:		122. sor:

	===7. Feladat===		===7. Feladat===
	Adott egy n és egy k elemet tartalmazó kupac. Adjon olyan O(n + k) összehasonlítást használó algoritmust, ami létrehoz egy olyan kupacot, ami a két kupacban tárolt elemek halmazának ~~únióját~~ tartalmazza. (TFH a két kupacban csupa különböző számocska áll.)		Adott egy n és egy k elemet tartalmazó kupac. Adjon olyan O(n + k) összehasonlítást használó algoritmust, ami létrehoz egy olyan kupacot, ami a két kupacban tárolt elemek halmazának unióját tartalmazza. (TFH a két kupacban csupa különböző számocska áll.)
	{{Rejtett		{{Rejtett
	\|mutatott=<big>'''Megoldás'''</big>		\|mutatott=<big>'''Megoldás'''</big>

Ewsd: /* 7. Feladat */

2014-03-30T15:29:21Z

7. Feladat

← Régebbi változat		A lap 2014. március 30., 17:29-kori változata
122. sor:		122. sor:

	===7. Feladat===		===7. Feladat===
	~~TODO~~		Adott egy n és egy k elemet tartalmazó kupac. Adjon olyan O(n + k) összehasonlítást használó algoritmust, ami létrehoz egy olyan kupacot, ami a két kupacban tárolt elemek halmazának únióját tartalmazza. (TFH a két kupacban csupa különböző számocska áll.)
	{{Rejtett		{{Rejtett
	\|mutatott=<big>'''Megoldás'''</big>		\|mutatott=<big>'''Megoldás'''</big>

Ewsd: /* 4. Feladat */

2014-03-30T14:56:13Z

4. Feladat

← Régebbi változat		A lap 2014. március 30., 16:56-kori változata
67. sor:		67. sor:

	===4. Feladat===		===4. Feladat===
	~~TODO~~		Éllistával adott n csúcsú, élsúlyzott, irányítatlan gráfként ismerjük egy ország úthálózatát (a csomópontok a városok, az élek a közvetlen összeköttetések a városok között). Az élek súlya azt adja meg, hogy hány (egész) perc alatt tudjuk megtenni az adott útszakaszt. Nagy havazás várható, de szerencsére pontosan tudjuk a követekző k percre, hogy mely élek (utak) mikortól nem lesznek járhatóak. Ha egyszer járhatatlanná válnak, akkor úgy is maradnak, ezután már az úton nem lehet közlekedni, és ha épp az adott élen vagyunk, amikor az járhatatlanná válik, akkor elakadunk.
			Adjon O(k(n+e)) lépést használó algoritmust, ami az adatok ismeretében el tudja dönteni, hogy el lehet-e jutni A városból B városba, ha most azonnal elindulunk!
	{{Rejtett		{{Rejtett
	\|mutatott=<big>'''Megoldás'''</big>		\|mutatott=<big>'''Megoldás'''</big>

Hryghr: /* 8. Feladat (Van megoldás) */

2014-02-15T14:49:34Z

8. Feladat (Van megoldás)

← Régebbi változat		A lap 2014. február 15., 16:49-kori változata
135. sor:		135. sor:
	\|szöveg=		\|szöveg=

	*Összesen 5 felállás lehet: [[File:~~algel_pzh_2012tavasz_8_1~~.png\|400px]]		*Összesen 5 felállás lehet: [[File:algel_pzh_2013tavasz_8_1.png\|400px]]
	**Ebből az 1. és a 4. jó is ''(a 4. persze csak akkor, ha X az nem a főgyökér)''.		**Ebből az 1. és a 4. jó is ''(a 4. persze csak akkor, ha X az nem a főgyökér)''.
	**A 3. - kis módosítással - látszik, hogy szintén fenn állhat gond nélkül: [[File:Algel pzh 2013tavasz 8 2.png\|100px]]		**A 3. - kis módosítással - látszik, hogy szintén fenn állhat gond nélkül: [[File:Algel pzh 2013tavasz 8 2.png\|100px]]

Kiskoza, 2013. december 19., 05:52-n

2013-12-19T05:52:28Z

← Régebbi változat		A lap 2013. december 19., 07:52-kori változata
137. sor:		137. sor:
	*Összesen 5 felállás lehet: [[File:algel_pzh_2012tavasz_8_1.png\|400px]]		*Összesen 5 felállás lehet: [[File:algel_pzh_2012tavasz_8_1.png\|400px]]
	**Ebből az 1. és a 4. jó is ''(a 4. persze csak akkor, ha X az nem a főgyökér)''.		**Ebből az 1. és a 4. jó is ''(a 4. persze csak akkor, ha X az nem a főgyökér)''.
	**A 3. - kis módosítással - látszik, hogy szintén fenn állhat gond nélkül: [[File:~~algel_pzh_2012tavasz_8_2~~.png\|100px]]		**A 3. - kis módosítással - látszik, hogy szintén fenn állhat gond nélkül: [[File:Algel pzh 2013tavasz 8 2.png\|100px]]
	**Egyedül a 2. és az 5. problémás. Ezek viszont rosszak is, hiszen mindkét esetben elmondható, hogy X-nek a fekete magassága jobbra 1, balra viszont legalább 2, mert az Y csúcsnak legalább 1-1 levél fia van. Tehát belső csúcsnál ilyen állapot nem állhat fent.		**Egyedül a 2. és az 5. problémás. Ezek viszont rosszak is, hiszen mindkét esetben elmondható, hogy X-nek a fekete magassága jobbra 1, balra viszont legalább 2, mert az Y csúcsnak legalább 1-1 levél fia van. Tehát belső csúcsnál ilyen állapot nem állhat fent.

Kiskoza, 2013. december 19., 05:39-n

2013-12-19T05:39:25Z

← Régebbi változat		A lap 2013. december 19., 07:39-kori változata
54. sor:		54. sor:
	*'''a)'''		*'''a)'''

	[[File:~~egyik~~.png\|200px]] [[File:~~masik~~.png\|200px]]		[[File:Algel_pzh_2013tavasz_Egyik.png\|200px]] [[File:Algel_pzh_2013tavasz_Masik.png\|200px]]

	Mindkét gráfot A-B-C-D-E sorrendben olvassuk ki, de mégsem egyeznek meg, tehát nem következik.		Mindkét gráfot A-B-C-D-E sorrendben olvassuk ki, de mégsem egyeznek meg, tehát nem következik.
60. sor:		60. sor:
	*'''b)'''		*'''b)'''

	[[File:~~egyik_1~~.png\|200px]] [[File:~~masik_2~~.png\|200px]]		[[File:Algel_pzh_2013tavasz_Egyik_1.png\|200px]] [[File:Algel_pzh_2013tavasz_Masik_2.png\|200px]]

	Mindkét gráfot F-G-H-J-K sorrendben olvassuk ki, de mégsem egyeznek meg, tehát nem következik.		Mindkét gráfot F-G-H-J-K sorrendben olvassuk ki, de mégsem egyeznek meg, tehát nem következik.

Arklur: /* 5. Feladat (Van megoldás) */

2013-06-18T15:45:32Z

5. Feladat (Van megoldás)

← Régebbi változat		A lap 2013. június 18., 17:45-kori változata
95. sor:		95. sor:
	***Majd újra növekvőbe a maradék számpárokat.		***Majd újra növekvőbe a maradék számpárokat.
	*Így az algoritmus <math>O(n)</math> lépéssel rendezi a számpárokat a 2. oszlop szerint.		*Így az algoritmus <math>O(n)</math> lépéssel rendezi a számpárokat a 2. oszlop szerint.
	[[File:algel_pzh_2013tavasz_5_1.PNG\|400px]]		:::::::::::::::::[[File:algel_pzh_2013tavasz_5_1.PNG\|400px]]
	}}		}}

Arklur: /* 5. Feladat */

2013-06-18T15:44:54Z

5. Feladat

← Régebbi változat		A lap 2013. június 18., 17:44-kori változata
75. sor:		75. sor:
	}}		}}

	===5. Feladat===		===5. Feladat (Van megoldás)===
	~~TODO~~		Egy <math>n</math> soros és kettő oszlopos táblázatban adott <math>n</math> számpár (egy sor egy számpárt tartalmaz, a számok mind különböző egész számok a táblázatban). Szeretnénk a táblázat sorait úgy átrendezni, hogy a 2. oszlop szerint növekvő sorrendben legyenek a sorok (számpárok). Egy fajta műveletet hajthatunk végre: kijelölhetünk néhány egymást alatti sort (számpárt) és ezeket rendezhetjük az első oszlop szerint növekvően vagy csökkenően. Adjon algoritmust, ami csak ezt a fajta műveletet használva <math>O(n)</math> lépésben megoldja a feladatot!
	{{Rejtett		{{Rejtett
	\|mutatott=<big>'''Megoldás'''</big>		\|mutatott=<big>'''Megoldás'''</big>
	\|szöveg=		\|szöveg=

	~~TODO~~		*Rendezzük a tömböt az 1. oszlop szerint növekvően.
			*A továbbiakban minden <math>i.</math> lépésben megkeressük az <math>i.</math> legkisebb elemet, és a helyére tesszük.
			**Megkeressük a 2. oszlopban az <math>i.</math> legkisebbet, az ő helye a tömbben legyen <math>k</math>
			**Mivel az 1. oszlop szerint növekvően vannak a számpárok, így ahhoz, hogy a <math>k.</math> elem az <math>i.</math> helyre kerüljön, a számokat csökkenő sorrendbe kell rendezni az <math>[i \rightarrow k] </math> intervallumon.
			**Ha ezt megcsináltuk, akkor az első <math>i</math> helyen már rendezve lesz a tömb.
			**Az <math>[i+1 \rightarrow n]</math> intervallumon rendezzük a számokat növekvő sorrendben.
			**Ezt addig folytatjuk, míg nincs minden számpár a helyén.

			*A műveletet minden lépésben <math>\approx 2n</math> alkalommal használjuk:
			**Először növekvő sorrendbe rendeztük az egész tömböt.
			**Utána minden <math>i.</math> lépésben 2x:
			***Egyszer a helyére rakjuk az elemet azzal, hogy csökkenő sorrendbe rakjuk a számpárokat (persze csak a megfelelőket).
			***Majd újra növekvőbe a maradék számpárokat.
			*Így az algoritmus <math>O(n)</math> lépéssel rendezi a számpárokat a 2. oszlop szerint.
			[[File:algel_pzh_2013tavasz_5_1.PNG\|400px]]
	}}		}}

Arklur: /* 2. Feladat (Van megoldás) */

2013-06-15T20:49:18Z

2. Feladat (Van megoldás)

← Régebbi változat		A lap 2013. június 15., 22:49-kori változata
33. sor:		33. sor:
	Minden csúcsban 3 adatot fogunk számon tartani: Érték (ez persze adott már), részfa magassága (jelüljük M-mel), és egy bool érték (IGAZ/HAMIS, jelöljük B-vel), hogy igaz-e a részfájára, hogy az kupac.		Minden csúcsban 3 adatot fogunk számon tartani: Érték (ez persze adott már), részfa magassága (jelüljük M-mel), és egy bool érték (IGAZ/HAMIS, jelöljük B-vel), hogy igaz-e a részfájára, hogy az kupac.
	*Első lépésben a legalsó szinteken lévő csúcsok esetén <math>M:=1, B:=IGAZ</math>.		*Első lépésben a legalsó szinteken lévő csúcsok esetén <math>M:=1, B:=IGAZ</math>.
	*Legyen egy változónk, amiben tároljuk, hogy melyik csúcsra igaz, hogy az részfája a "legnagyobb" kupac (kezdeti értéke legyen mondjuk az egyik legalsó szinten lévő csúcs).		*Legyen egy változónk, amiben tároljuk, hogy melyik csúcsra igaz, hogy a részfája a "legnagyobb" kupac (kezdeti értéke legyen mondjuk az egyik legalsó szinten lévő csúcs).
	*Minden további szinten az a feladatunk, hogy megnézzük az adott csúcs (x) bal, és jobb fiát <math>(JOBB(x), BAL(x))</math>.		*Minden további szinten az a feladatunk, hogy megnézzük az adott csúcs (x) bal, és jobb fiát <math>(JOBB(x), BAL(x))</math>.
	**Megnézzük, hogy nagyobbak-e, mint x, majd megnézzük, hogy kupac tulajdonsággal bírnak-e:		**Megnézzük, hogy nagyobbak-e, mint x, majd megnézzük, hogy kupac tulajdonsággal bírnak-e:

Arklur: /* 6. Feladat */

2013-06-15T20:32:14Z

6. Feladat

← Régebbi változat		A lap 2013. június 15., 22:32-kori változata
84. sor:		84. sor:
	}}		}}

	===6. Feladat===		===6. Feladat (Van megoldás)===
	~~TODO~~		Adott egy <math> n </math> hosszú tömb. Tudjuk, hogy a tömb első néhány (<math> k </math> darab) elem 0, a többi 1, de <math> k </math> értékét nem ismerjük. Adjon <math> O(logk) </math> (nem <math> O(logn) </math> )<sup>1</sup> összehasonlítást használó algoritmust, ami meghatározza <math> k </math> értékét.

			''<sup>1</sup> A feladatban <math> O(logk) </math> szerepel, de az csak elgépelés.''
	{{Rejtett		{{Rejtett
	\|mutatott=<big>'''Megoldás'''</big>		\|mutatott=<big>'''Megoldás'''</big>
	\|szöveg=		\|szöveg=

	~~TODO~~		*Először nézzük meg, hogy az első 2 elem <math>0-1</math>-e, ha igen, akkor <math> k=1 </math>.
			*Ha nem, akkor minden további lépésnél ugorjunk a 2x annyiadik cellába (ez legyen <math> m </math>), ha pedig túl lépnénk a tömböt ezzel, akkor az utolsóba.
			*Vizsgáljuk meg, hogy "hol vagyunk": ''(az aktuális cellát, és a 2 szomszédját)''
			**Ha <math>0-0-0</math>-t látunk, akkor ugrunk megint 2x akkorát ''(ugyanazzal a kritériummal, mint előbb)''.
			**Ha <math>0-0-1</math>-t látunk, akkor <math> k=m </math>.
			**Ha <math>0-1-1</math>-t látunk, akkor <math> k=m-1 </math>.
			**Ha <math>1-1-1</math>-t látunk, akkor egy bináris keresés segítségével<sup><big>(1)</big></sup> a 2 legutóbbi vizsgált elem közötti cellákban megkeressük a <math>0-1-1</math>, vagy <math>0-0-1</math> felállást, és a <math>k</math> értékét a látottak alapján beállítjuk <math>( k=m-1 </math> vagy <math> k=m )</math>.

			<sup><big>(1)</big></sup> '' Ha <math>0-0-0</math>-t lát, jobbra lép, ha <math>1-1-1</math>-t, akkor balra, másik 2 esetben pedig találatunk van.''
			:::::::::::[[File:algel_pzh_2013tavasz_6_1.PNG\|400px]]

			*Az algoritmus működése alapján belátható, hogy <math> O(logk) </math> időben fut.
	}}		}}