Algoritmuselmélet 2010.11.19. PZH megoldásai - Laptörténet

Ruzar: /* 1. Feladat (Van megoldás) */

2014-04-22T20:19:33Z

1. Feladat (Van megoldás)

← Régebbi változat		A lap 2014. április 22., 22:19-kori változata
17. sor:		17. sor:
	*<math> f_3(n)=4^{100+logn} = 4^{100} \cdot 4^{logn} = 4^{100} \cdot (2^2)^{logn} = 4^{100} \cdot (2^{logn})^2 = 4^{100} \cdot n^2</math><br><br>		*<math> f_3(n)=4^{100+logn} = 4^{100} \cdot 4^{logn} = 4^{100} \cdot (2^2)^{logn} = 4^{100} \cdot (2^{logn})^2 = 4^{100} \cdot n^2</math><br><br>

	*Első lépésben belátjuk, hogy <math> ~~f_3~~(n)=O(f_3(n)). </math><br><br>		*Első lépésben belátjuk, hogy <math> f_1(n)=O(f_3(n)). </math><br><br>
	**<math> 2010n \cdot log_3n \leq c \cdot 4^{100} \cdot n^2 </math><br><br>		**<math> 2010n \cdot log_3n \leq c \cdot 4^{100} \cdot n^2 </math><br><br>
	**<math> 2010 \cdot log_3n \leq c \cdot 4^{100} \cdot n </math><br><br>		**<math> 2010 \cdot log_3n \leq c \cdot 4^{100} \cdot n </math><br><br>

Arklur: /* 2010.11.19 - PZH megoldásai */

2013-06-20T09:12:36Z

2010.11.19 - PZH megoldásai

← Régebbi változat		A lap 2013. június 20., 11:12-kori változata
2. sor:		2. sor:

	== 2010.11.19 - PZH megoldásai==		== 2010.11.19 - PZH megoldásai==
	===1. Feladat===		===1. Feladat (Van megoldás)===
	Az alábbi függvényeket rendezze olyan sorozatba, hogy ha <math> f_i </math> után közvetlenül <math> f_j </math> következik a sorban, akkor <math> f_i(n) = O(f_j(n)) </math> teljesüljün!		Az alábbi függvényeket rendezze olyan sorozatba, hogy ha <math> f_i </math> után közvetlenül <math> f_j </math> következik a sorban, akkor <math> f_i(n) = O(f_j(n)) </math> teljesüljün!

Arklur: /* 1. Feladat */

2013-06-20T09:12:07Z

1. Feladat

← Régebbi változat		A lap 2013. június 20., 11:12-kori változata
3. sor:		3. sor:
	== 2010.11.19 - PZH megoldásai==		== 2010.11.19 - PZH megoldásai==
	===1. Feladat===		===1. Feladat===
	~~TODO~~		Az alábbi függvényeket rendezze olyan sorozatba, hogy ha <math> f_i </math> után közvetlenül <math> f_j </math> következik a sorban, akkor <math> f_i(n) = O(f_j(n)) </math> teljesüljün!

			*<math> f_1(n)=2010 \cdot log_3(n^n) </math><br><br>
			*<math> f_2(n)=n^{1+2+ \dots +loglogn} </math><br><br>
			*<math> f_3(n)=4^{100+logn} </math><br><br>

	{{Rejtett		{{Rejtett
	\|mutatott=<big>'''Megoldás'''</big>		\|mutatott=<big>'''Megoldás'''</big>
	\|szöveg=		\|szöveg=

	~~TODO~~		*<math> f_1(n)=2010 \cdot log_3(n^n) = 2010n \cdot log_3n </math><br><br>
			<math> f_2(n)=n^{1+2+ \dots +loglogn} </math> ezt alulról becsülhetjük <math> f_{2}^{}(n) = n^{logn} </math>-nel.<br><br>
			*<math> f_3(n)=4^{100+logn} = 4^{100} \cdot 4^{logn} = 4^{100} \cdot (2^2)^{logn} = 4^{100} \cdot (2^{logn})^2 = 4^{100} \cdot n^2</math><br><br>

			*Első lépésben belátjuk, hogy <math> f_3(n)=O(f_3(n)). </math><br><br>
			**<math> 2010n \cdot log_3n \leq c \cdot 4^{100} \cdot n^2 </math><br><br>
			**<math> 2010 \cdot log_3n \leq c \cdot 4^{100} \cdot n </math><br><br>
			**<math> log_3n \leq c \cdot \frac{4^{100}}{2010} \cdot n </math><br><br>
			**<math> c=\frac{2010}{4^{100}}, n \geq 1 </math><br><br>

			Második lépésben belátjuk, hogy <math> f_1(n)=O( f_{2}^{}(n)). </math> ''(Ha ezt belátjuk, akkor <math> f_1(n)=O( f_{2}(n)) </math> is igaz lesz.)'' <br><br>
			**<math> 4^{100} \cdot n^2 \leq c \cdot n^{logn} </math><br><br>
			**<math> n^2 \leq \frac{c}{4^{100}} \cdot n^{logn} </math><br><br>
			**<math> c = 4^{100} </math><br><br>
			**És a kitevők alapján pedig <math> n \geq 4 </math><br><br>

			*Tehát a megoldás <math> f_1(n) \rightarrow f_3(n) \rightarrow f_2(n) .</math>
	}}		}}

Arklur: /* 7. Feladat */

2013-06-19T20:29:29Z

7. Feladat

← Régebbi változat		A lap 2013. június 19., 22:29-kori változata
77. sor:		77. sor:
	}}		}}

	===7. Feladat===		===7. Feladat (Van megoldás)===
	~~TODO~~		Egy piros-fekete fa gyökerének mindkét gyereke fekete. A gyökér baloldali részfájában 14, a jobboldali részfájában 63 elemet tárolunk. Mennyi lehet a fa fekete-magassága?
	{{Rejtett		{{Rejtett
	\|mutatott=<big>'''Megoldás'''</big>		\|mutatott=<big>'''Megoldás'''</big>
	\|szöveg=		\|szöveg=

	~~TODO~~		*Először vizsgáljuk a jobboldali részfát:
			**Tudjuk, hogy <math> n \leq 2^m-1 \Rightarrow 63 \leq 2^m-1 \Rightarrow m \geq 6 </math>, vagyis a jobb oldali részfa magassága legalább 6.<br><br>
			**Továbbá <math> fm \geq \frac{m}{2} \Rightarrow fm \geq 3 </math> <br><br>
			*Most nézzük a baloldali részfát:
			**Ismert, hogy <math> b_v \geq 2^{fm(v)}-1 \Rightarrow 14 \geq 2^{fm(v)}-1 \Rightarrow fm \leq 3.907 \Rightarrow \Rightarrow fm < 4 </math>


			*A 2 korlátot összevetve jön ki, hogy a bal és jobb részfa esetén <math> fm = 3.</math>
			*Emiatt az eredeti fában pedig <math> fm = 4.</math>
	}}		}}

Arklur: /* 6. Feladat */

2013-06-19T19:47:52Z

6. Feladat

← Régebbi változat		A lap 2013. június 19., 21:47-kori változata
57. sor:		57. sor:
	}}		}}

	===6. Feladat===		===6. Feladat (Van megoldás)===
	~~TODO~~		Hajtsa végre az alábbi <math>F</math> bináris keresőfán a BESZÚR(13), TÖRÖL(10) műveleteket! Minden lépést jelezzen!

			[[File:algel_pzh_2010osz_6_f.PNG\|200px]]
	{{Rejtett		{{Rejtett
	\|mutatott=<big>'''Megoldás'''</big>		\|mutatott=<big>'''Megoldás'''</big>
	\|szöveg=		\|szöveg=

	~~TODO~~		*BESZÚR(13):
			**Egyszerű, mint az 1x1<br>
			[[File:algel_pzh_2010osz_6_1.png\|300px]]

			*TÖRÖL(10):
			**Töröljük a 10-t.
			**A '''BAL''' oldali részfából kiválasztjuk a '''LEGNAGYOBB''' elemet, és berakjuk a gyökérbe (ebben az esetben a 7).
			**A fát rendbe rakjuk (ez esetben a 6-t beírjuk a 7 régi helyére).<br>
			[[File:algel_pzh_2010osz_6_2.png\|300px]]

	}}		}}

Arklur: /* 4. Feladat */

2013-06-19T10:26:44Z

4. Feladat

← Régebbi változat		A lap 2013. június 19., 12:26-kori változata
31. sor:		31. sor:
	}}		}}

	===4. Feladat===		===4. Feladat (Van megoldás)===
	Dijkstra algoritmussal határozza meg a G gráfban az <math>A</math> pontból az összes többi pontba menő legrövidebb utak hosszát az <math>X</math> pozitív valós paraméter függvényében. Minden lépésnél írja fel a távolságokat tartalmazó D tömb állapotát, és a KÉSZ halmaz elemeit.		Dijkstra algoritmussal határozza meg a G gráfban az <math>A</math> pontból az összes többi pontba menő legrövidebb utak hosszát az <math>X</math> pozitív valós paraméter függvényében. Minden lépésnél írja fel a távolságokat tartalmazó D tömb állapotát, és a KÉSZ halmaz elemeit.

Arklur: /* 4. Feladat */

2013-06-19T10:26:21Z

4. Feladat

← Régebbi változat		A lap 2013. június 19., 12:26-kori változata
32. sor:		32. sor:

	===4. Feladat===		===4. Feladat===
	~~TODO~~		Dijkstra algoritmussal határozza meg a G gráfban az <math>A</math> pontból az összes többi pontba menő legrövidebb utak hosszát az <math>X</math> pozitív valós paraméter függvényében. Minden lépésnél írja fel a távolságokat tartalmazó D tömb állapotát, és a KÉSZ halmaz elemeit.

			[[File:algel_pzh_2010osz_4_f.PNG\|200px]]
	{{Rejtett		{{Rejtett
	\|mutatott=<big>'''Megoldás'''</big>		\|mutatott=<big>'''Megoldás'''</big>
	\|szöveg=		\|szöveg=

	~~TODO~~		*Egy egyszerű Dijkstra-s feladat.
			*Annyit kell megjegyezni hozzá, hogy:
			**Ha <math> X \leq 2 </math>, akkor az <math>X</math> élt <math>( D \rightarrow E )</math> veszi be.
			**Ha <math> X \geq 2 </math>, akkor a <math>C \rightarrow E </math> élt veszi be.

			:::::::::[[File:algel_pzh_2010osz_4_2.PNG\|200px]][[File:algel_pzh_2010osz_4_3.PNG\|200px]][[File:algel_pzh_2010osz_4_1.png\|200px]]

	}}		}}

Arklur: Új oldal, tartalma: „{{Vissza|Algoritmuselmélet}} == 2010.11.19 - PZH megoldásai== ===1. Feladat=== TODO {{Rejtett |mutatott='''Megoldás''' |szöveg= TODO }} ===2. Feladat=…”

2013-06-19T09:25:49Z

Új oldal, tartalma: „{{Vissza|Algoritmuselmélet}} == 2010.11.19 - PZH megoldásai== ===1. Feladat=== TODO {{Rejtett |mutatott=<big>'''Megoldás'''</big> |szöveg= TODO }} ===2. Feladat=…”

Új lap

{{Vissza|Algoritmuselmélet}}

== 2010.11.19 - PZH megoldásai==
===1. Feladat===
TODO
{{Rejtett
|mutatott=<big>'''Megoldás'''</big>
|szöveg=

TODO
}}

===2. Feladat===
TODO
{{Rejtett
|mutatott=<big>'''Megoldás'''</big>
|szöveg=

TODO

}}

===3. Feladat===
TODO
{{Rejtett
|mutatott=<big>'''Megoldás'''</big>
|szöveg=

TODO

}}

===4. Feladat===
TODO
{{Rejtett
|mutatott=<big>'''Megoldás'''</big>
|szöveg=

TODO
}}

===5. Feladat===
TODO
{{Rejtett
|mutatott=<big>'''Megoldás'''</big>
|szöveg=

TODO
}}

===6. Feladat===
TODO
{{Rejtett
|mutatott=<big>'''Megoldás'''</big>
|szöveg=

TODO
}}

===7. Feladat===
TODO
{{Rejtett
|mutatott=<big>'''Megoldás'''</big>
|szöveg=

TODO
}}

===8. Feladat===
TODO
{{Rejtett
|mutatott=<big>'''Megoldás'''</big>
|szöveg=

TODO
}}

[[Kategória:Infoalap]]