Algoritmuselmélet - Vizsga, 2013.05.30. - Laptörténet

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

2015-06-18T17:22:55Z

2. Feladat (Van megoldás)

← Régebbi változat		A lap 2015. június 18., 19:22-kori változata
48. sor:		48. sor:

	<math>log_2n+1\leq m \leq log_3n+1</math>, ahol <math>m</math> a fa szintszáma.		<math>log_2n+1\leq m \leq log_3n+1</math>, ahol <math>m</math> a fa szintszáma.

			$$$ Ez nem pont fordítva van a dián? $$$

	''Bizonyítás:''		''Bizonyítás:''

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

2014-01-15T02:35:58Z

2. Feladat (Van megoldás)

← Régebbi változat		A lap 2014. január 15., 04:35-kori változata
44. sor:		44. sor:
	***A középső részfában az elemek nagyobb-egyenlőek, mint S1 (vagyis az 1. elem S1), de kisebbek, mint S2.		***A középső részfában az elemek nagyobb-egyenlőek, mint S1 (vagyis az 1. elem S1), de kisebbek, mint S2.
	***A jobb részfában az elemek nagyobb-egyenlőek, mint S2 (vagyis az 1. elem S2).		***A jobb részfában az elemek nagyobb-egyenlőek, mint S2 (vagyis az 1. elem S2).
	~~:::::::::::::::::[[File:2_3_pelda.png\|400px]]~~

	'''Adjon felső becslést a fa szintszámára n tárolt elem esetén, állítását bizonyítsa is!'''		'''Adjon felső becslést a fa szintszámára n tárolt elem esetén, állítását bizonyítsa is!'''

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

2013-12-19T05:48:14Z

← Régebbi változat		A lap 2013. december 19., 07:48-kori változata
37. sor:		37. sor:
	*A fa levelei a gyökértől egyenlő távolságra vannak (vagyis a levelek 1 szinten vannak).		*A fa levelei a gyökértől egyenlő távolságra vannak (vagyis a levelek 1 szinten vannak).
	*A belső csúcsokban mutatókat (M) és 1, vagy 2 kulcsot (S) tárolunk.		*A belső csúcsokban mutatókat (M) és 1, vagy 2 kulcsot (S) tárolunk.
	**Ha a csúcsnak 2 fia van, akkor 2 mutatót, és egy kulcsot tárol. [[File:~~2_3_2~~.png\|300px]]		**Ha a csúcsnak 2 fia van, akkor 2 mutatót, és egy kulcsot tárol. [[File:Algel vizsga 2013tavasz V1 2 2fia.png\|300px]]
	***A bal részfában az elemek kisebbek, mint S1.		***A bal részfában az elemek kisebbek, mint S1.
	***A jobb részfában az elemek nagyobb-egyenlőek, mint S1 (vagyis az 1. elem S1).		***A jobb részfában az elemek nagyobb-egyenlőek, mint S1 (vagyis az 1. elem S1).

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

2013-12-19T05:34:15Z

← Régebbi változat		A lap 2013. december 19., 07:34-kori változata
40. sor:		40. sor:
	***A bal részfában az elemek kisebbek, mint S1.		***A bal részfában az elemek kisebbek, mint S1.
	***A jobb részfában az elemek nagyobb-egyenlőek, mint S1 (vagyis az 1. elem S1).		***A jobb részfában az elemek nagyobb-egyenlőek, mint S1 (vagyis az 1. elem S1).
	**Ha a csúcsnak 3 fia van, akkor 3 mutatót, és 2 kulcsot tárol. [[File:~~2_3_3~~.png\|400px]]		**Ha a csúcsnak 3 fia van, akkor 3 mutatót, és 2 kulcsot tárol. [[File:Algel_vizsga_2013tavasz_V1_2_3fia.png\|400px]]
	***A bal részfában az elemek kisebbek, mint S1.		***A bal részfában az elemek kisebbek, mint S1.
	***A középső részfában az elemek nagyobb-egyenlőek, mint S1 (vagyis az 1. elem S1), de kisebbek, mint S2.		***A középső részfában az elemek nagyobb-egyenlőek, mint S1 (vagyis az 1. elem S1), de kisebbek, mint S2.

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

2013-12-19T05:32:09Z

← Régebbi változat		A lap 2013. december 19., 07:32-kori változata
44. sor:		44. sor:
	***A középső részfában az elemek nagyobb-egyenlőek, mint S1 (vagyis az 1. elem S1), de kisebbek, mint S2.		***A középső részfában az elemek nagyobb-egyenlőek, mint S1 (vagyis az 1. elem S1), de kisebbek, mint S2.
	***A jobb részfában az elemek nagyobb-egyenlőek, mint S2 (vagyis az 1. elem S2).		***A jobb részfában az elemek nagyobb-egyenlőek, mint S2 (vagyis az 1. elem S2).
	:::::::::::::::::[[File:2_3_pelda.~~PNG~~\|400px]]		:::::::::::::::::[[File:2_3_pelda.png\|400px]]

	'''Adjon felső becslést a fa szintszámára n tárolt elem esetén, állítását bizonyítsa is!'''		'''Adjon felső becslést a fa szintszámára n tárolt elem esetén, állítását bizonyítsa is!'''

Arklur: /* 1. Feladat */

2013-06-17T18:12:55Z

1. Feladat

← Régebbi változat		A lap 2013. június 17., 20:12-kori változata
3. sor:		3. sor:
	==2013.06.06. vizsga megoldásai==		==2013.06.06. vizsga megoldásai==
	===1. Feladat===		===1. Feladat===
	~~TODO~~		Ebben a feladatban a Floyd algoritmussal kapcsolatos kérdésekre kell válaszolnia. (A Floyd-algoritmus egy grában minden pontpárra meghatározza a köztük levő legrövidebb út hosszát.)

			'''(a)''' Mit jelöl az <math> F_k </math> mátrix <math> F_k[i,j] </math> eleme?

			'''(b)''' Hogyan kell kiszámolni az <math> F_{k-1} </math> mátrixból az <math> F_k </math> mátrixot?

			'''(c)''' Igazolja, hogy ez a kiszámítási mód helyes!

			'''(d)''' Mennyi a lépésszáma a '''(b)''' lépés egyszeri végrehajtásának? (A lépésszámot nem kell igazolni.)
	{{Rejtett		{{Rejtett
	\|mutatott=<big>'''Megoldás'''</big>		\|mutatott=<big>'''Megoldás'''</big>
	\|szöveg=		\|szöveg=

	~~TODO~~		'''a)''' <math> F_k[i,j] </math> azon <math> i \rightarrow j </math> utak legrövidebbjeinek a hosszát tartalmazza, amelyek közbülső pontjai <math>k</math>-nál nem nagyobb sorszámúak. ''(Magyarul: Az <math> F_k[i,j] </math> azt mondja meg, hogy <math>i</math>-ből <math>j</math>-be mennyi a legrövidebb út összsúlya, ha csak az első <math>k</math> darab csúcsot használtuk.)''

			'''b)''' <math> F_k[i,j]:=min\left \{ F_{k-1}[i,k]+F_{k-1}[k,j],F_{k-1}[i,j]\right \} </math> ''<math>(</math>Vagyis vagy az <math> i \rightarrow k \rightarrow j </math> lesz a legrövidebb út, vagy "marad a régi" <math> i \rightarrow j .)</math>''

			'''c)''' Tulajdonképpen az előzőből következik. Hiszen vagy nem változik az új csúccsal a legrövidebb út a 2 pont között <math> (i \rightarrow j) </math>, vagy ha igen, akkor az a <math> (i \rightarrow k) + (k \rightarrow j) </math> lesz az.

			'''d)''' <math> O(n^2) </math>. ''<math>(</math>Maga az algoritmus <math>O(n^3)</math>, de csúcsonként <math> O(n^2) </math>, vagyis <math> n \cdot O(n^2) = O(n^3) ).</math>''
	}}		}}

Arklur: /* 6. Feladat */

2013-06-17T17:25:04Z

6. Feladat

← Régebbi változat		A lap 2013. június 17., 19:25-kori változata
95. sor:		95. sor:
	}}		}}

	===6. Feladat===		===6. Feladat (Van megoldás)===
	Egy ország ''n'' kis szigetből áll. Szeretnénk néhány hajójáratot indítani a szigetek között úgy, hogy bárhonnan bárhova el lehessen jutni (esetleg átszállással). Ehhez ismerjük bármely két szigetre, hogy mennyibe kerül egy évben a hajójárat fenntartása közöttük, illetve azt, hogy mekkora az itt várható éves bevétel. Adjon algoritmust, ami ezen adatok ismeretében <math>O(n^2)</math> időben meghatározza, hogy hol indítsuk el a hajójáratokat, ha a lehető legnagyobb várható éves hasznot (vagy a lehető legkisebb veszteséget) szeretnénk elérni. (Egy szigeten egy hajóállomás van csak).		Egy ország ''n'' kis szigetből áll. Szeretnénk néhány hajójáratot indítani a szigetek között úgy, hogy bárhonnan bárhova el lehessen jutni (esetleg átszállással). Ehhez ismerjük bármely két szigetre, hogy mennyibe kerül egy évben a hajójárat fenntartása közöttük, illetve azt, hogy mekkora az itt várható éves bevétel. Adjon algoritmust, ami ezen adatok ismeretében <math>O(n^2)</math> időben meghatározza, hogy hol indítsuk el a hajójáratokat, ha a lehető legnagyobb várható éves hasznot (vagy a lehető legkisebb veszteséget) szeretnénk elérni. (Egy szigeten egy hajóállomás van csak).
	{{Rejtett		{{Rejtett
101. sor:		101. sor:
	\|szöveg=		\|szöveg=

	~~TODO~~		*Első lépésben az élsúly legyen a <math> Profit = -(Bevetel - Kiadas) .</math>
			*Vegyük fel az összes profitot termelő, vagy legalábbis veszteséget nem termelő éleket <math> (Profit \geq 0 )</math> <math> \Rightarrow O(n^2) </math> lépés. Ez legyen mondjuk a G gráf.
			*Két eshetőség áll fenn:
			**Ha a G gráf összefüggő, akkor jók is vagyunk, nincs további teendőnk, meg is vagyunk.
			**Ha nem összefüggő, akkor:
			***Az egyes komponenseket tekintsük egy pontnak. Minden olyan él, ami ebbe a komponensbe megy, menjen ebbe a pontba. Így kapunk egy F gráfot.
			***Erre az F gráfra hívunk meg egy Prim-algoritmust, ami <math> O(n^2) </math> időben keres az F gráfban egy minimális feszítőfát ''(vagyis a komponenseket - ami most jelenleg 1-1 pont a gráfban - a lehető legkisebb költségű élekkel köti össze)''.

			*Tehát Prim-algoritmussal, vagy anélkül <math> O(n^2) </math> időben megmondjuk, hogy mely hajójáratok indításával lesz az évi bevétel a legmagasabb.
	}}		}}

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

2013-06-16T06:46:35Z

4. Feladat (Van megoldás)

← Régebbi változat		A lap 2013. június 16., 08:46-kori változata
70. sor:		70. sor:
	[[File:algel_vizsga1_2013tavasz_4_N_M.PNG\|200px]]		[[File:algel_vizsga1_2013tavasz_4_N_M.PNG\|200px]]
	*Az <math> N </math> és <math> M </math> tömbök létrehozása <math> O(n) </math> és <math> O(m) </math> lépést igényel.		*Az <math> N </math> és <math> M </math> tömbök létrehozása <math> O(n) </math> és <math> O(m) </math> lépést igényel.
	*Nincs is más dolgunk, mint végigmenni az <math> N </math> és <math> M </math> tömbökön úgy, hogy az <math> i. </math> oszlopban vesszük a 2 szám különbségének abszolút értékét, vagyis az igazságtalansági faktort számoljuk, és mindig ~~elmentjók~~ egy változóba a minimumot, és a ehhez tartozó törésvonalat. Ez is <math> O(n) </math> és <math> O(m) </math> lépés.		*Nincs is más dolgunk, mint végigmenni az <math> N </math> és <math> M </math> tömbökön úgy, hogy az <math> i. </math> oszlopban vesszük a 2 szám különbségének abszolút értékét, vagyis az igazságtalansági faktort számoljuk, és mindig elmentjük egy változóba a minimumot, és a ehhez tartozó törésvonalat. Ez is <math> O(n) </math> és <math> O(m) </math> lépés.
	*Összesen tehát <math> O(nm)+O(nm)+O(n)+O(m)+O(n)+O(m)=O(nm) </math> lépéssel megoldottuk a feladatot.		*Összesen tehát <math> O(nm)+O(nm)+O(n)+O(m)+O(n)+O(m)=O(nm) </math> lépéssel megoldottuk a feladatot.
	:::::[[File:algel_vizsga1_2013tavasz_4_1.PNG\|400px]] [[File:algel_vizsga1_2013tavasz_4_2.PNG\|400px]]		:::::[[File:algel_vizsga1_2013tavasz_4_1.PNG\|400px]] [[File:algel_vizsga1_2013tavasz_4_2.PNG\|400px]]

Arklur: /* 4. Feladat */

2013-06-16T06:45:18Z

4. Feladat

← Régebbi változat		A lap 2013. június 16., 08:45-kori változata
52. sor:		52. sor:
	}}		}}

	===4. Feladat===		===4. Feladat (Van megoldás)===
	~~TODO~~		Van egy tábla <math> (n</math> <big>x</big> <math>m</math> kockákból álló<math> ) </math>. Az <math> A </math> <math> n</math> <big>x</big> <math>m</math>-es mátrixban adott, hogy az egyes kockákban hány mogyoró van (a mogyorók nem lógnak át egyik kockából a másikba). Két gyerek akar osztozkodni a csokin, úgy, hogy a csokit kéfelé törik (egyenes vonal mentén, párhuzamosan a tábla valamelyik szélével). Egy osztkozkodás igazságtalansági faktorát a következőképpen kaphatjuk: ha az egyik darabban <math> k_1 </math> kocka csoki, és <math> m_1 </math> darab mogyoró van, a másikban pedig <math> k_2 </math> kocka csoki és <math> m_2 </math> darab mogyoró, akkor az igazságtalansági faktor <math> \left \| \left ( k_1+m_1 \right ) -(k_2+m_2)\right \| </math>. Adjon <math> O(nm) </math> lépést használó algoritmust, ami eldönti, hogy melyik szétosztásnak a legkisebb az igazságtalansági faktora. (Egy lépésnek számít, ha kiolvasunk egy értéket az <math> A </math> mátrixból vagy ha összeadást, illetve kivonást hajtunk végre két számon.)

	{{Rejtett		{{Rejtett
	\|mutatott=<big>'''Megoldás'''</big>		\|mutatott=<big>'''Megoldás'''</big>
	\|szöveg=		\|szöveg=
			[[File:algel_vizsga1_2013tavasz_4_csoki.PNG\|200px]]
			Hozzunk létre egy <math> n </math> elemű <math> TN </math> tömböt, ahol az <math> i. </math> cellában az szerepel, hogy az <math> A </math> mátrix annyiadik oszlopában mennyi a <math> k+m </math>. ''(ez <math> nm </math> kiolvasás, és <math> n*(m-1) </math> összeadás, vagyis <math> \Rightarrow O(nm) </math>.
			Hozzunk létre egy <math> m </math> elemű <math> TM </math> tömböt, ahol az <math> i. </math> cellában az szerepel, hogy az <math> A </math> mátrix annyiadik sorában mennyi a <math> k+m </math>. ''(ez <math> mn </math> kiolvasás, és <math> m*(n-1) </math> összeadás, vagyis <math> \Rightarrow O(nm) </math>.
			[[File:algel_vizsga1_2013tavasz_4_tn_tm.PNG\|200px]]
			*Hozzunk létre egy <math> (n-1) </math> x <math> 2 </math>-es <math> N </math> tömböt, ahol az 1. sorban balról jobbra nézzük, mennyi a <math> k+m </math>, a 2. sorban pedig jobbról balra. ''<math>(</math>1. sor a <math> (k_1+m_1) </math>, 2. sor pedig a hozzá tartozó <math> (k_2+m_2) .)</math>
			**<math>N[1,1]= TN[1] </math> majd <math>N[i,1]= N[i-1,1]+TN[i] , i=2...(n-1)</math>.
			**<math>N[1,2]= \sum_{i=2}^{n}TN[i] </math> majd <math>N[i,2]= N[i-1,2]-TN[i] , i=2...(n-1)</math>.
			*Hozzunk létre egy <math> (m-1) </math> x <math> 2 </math>-es <math> M </math> tömböt, ahol az 1. sorban fentről lefele nézzük, mennyi a <math> k+m </math>, a 2. sorban pedig alulról felfele. ''<math>(</math>1. sor a <math> (k_1+m_1) </math>, 2. sor pedig a hozzá tartozó <math> (k_2+m_2) .)</math>
			**<math>M[1,1]= TM[1] </math> majd <math>M[i,1]= M[i-1,1]+TM[i] , i=2...(m-1)</math>.
			**<math>M[1,2]= \sum_{i=2}^{m}TM[i] </math> majd <math>M[i,2]= M[i-1,2]-TM[i] , i=2...(m-1)</math>.
			[[File:algel_vizsga1_2013tavasz_4_N_M.PNG\|200px]]
			*Az <math> N </math> és <math> M </math> tömbök létrehozása <math> O(n) </math> és <math> O(m) </math> lépést igényel.
			*Nincs is más dolgunk, mint végigmenni az <math> N </math> és <math> M </math> tömbökön úgy, hogy az <math> i. </math> oszlopban vesszük a 2 szám különbségének abszolút értékét, vagyis az igazságtalansági faktort számoljuk, és mindig elmentjók egy változóba a minimumot, és a ehhez tartozó törésvonalat. Ez is <math> O(n) </math> és <math> O(m) </math> lépés.
			*Összesen tehát <math> O(nm)+O(nm)+O(n)+O(m)+O(n)+O(m)=O(nm) </math> lépéssel megoldottuk a feladatot.
			:::::[[File:algel_vizsga1_2013tavasz_4_1.PNG\|400px]] [[File:algel_vizsga1_2013tavasz_4_2.PNG\|400px]]

	~~TODO~~
	}}		}}

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

2013-06-15T11:31:16Z

2. Feladat (Van megoldás)

← Régebbi változat		A lap 2013. június 15., 13:31-kori változata
22. sor:		22. sor:
	*Minden belső csúcsnak 2, vagy 3 fia lehet, se több, se kevesebb. ''(Kivéve, ha csak 1 elemet tárolunk a fában, mert akkor a gyökérnek csak 1 fia van.)''		*Minden belső csúcsnak 2, vagy 3 fia lehet, se több, se kevesebb. ''(Kivéve, ha csak 1 elemet tárolunk a fában, mert akkor a gyökérnek csak 1 fia van.)''
	*A fa levelei a gyökértől egyenlő távolságra vannak (vagyis a levelek 1 szinten vannak).		*A fa levelei a gyökértől egyenlő távolságra vannak (vagyis a levelek 1 szinten vannak).
	*A belső csúcsokban mutatókat (M) és 1, vagy 2 ~~elemet~~ (S) tárolunk.		*A belső csúcsokban mutatókat (M) és 1, vagy 2 kulcsot (S) tárolunk.
	**Ha a csúcsnak 2 fia van, akkor 2 mutatót, és egy ~~elememet~~ tárol. [[File:2_3_2.png\|300px]]		**Ha a csúcsnak 2 fia van, akkor 2 mutatót, és egy kulcsot tárol. [[File:2_3_2.png\|300px]]
	***A bal részfában az elemek kisebbek, mint S1.		***A bal részfában az elemek kisebbek, mint S1.
	***A jobb részfában az elemek nagyobb-egyenlőek, mint S1 (vagyis az 1. elem S1).		***A jobb részfában az elemek nagyobb-egyenlőek, mint S1 (vagyis az 1. elem S1).
	**Ha a csúcsnak 3 fia van, akkor 3 mutatót, és 2 ~~elemet~~ tárol. [[File:2_3_3.png\|400px]]		**Ha a csúcsnak 3 fia van, akkor 3 mutatót, és 2 kulcsot tárol. [[File:2_3_3.png\|400px]]
	***A bal részfában az elemek kisebbek, mint S1.		***A bal részfában az elemek kisebbek, mint S1.
	***A középső részfában az elemek nagyobb-egyenlőek, mint S1 (vagyis az 1. elem S1), de kisebbek, mint S2.		***A középső részfában az elemek nagyobb-egyenlőek, mint S1 (vagyis az 1. elem S1), de kisebbek, mint S2.