Algoritmuselmélet - ZH, 2013.04.03. - Laptörténet

Deák Zsolt: /* 4. Feladat (Van megoldás) */

2015-04-08T12:22:07Z

4. Feladat (Van megoldás)

← Régebbi változat		A lap 2015. április 8., 14:22-kori változata
92. sor:		92. sor:
	::::::::::[[File:Algel zh 2013tavasz Csucs suly.png\|300px\|G gráf]][[File:Algel zh 2013tavasz El suly.png\|400px\|F gráf]]		::::::::::[[File:Algel zh 2013tavasz Csucs suly.png\|300px\|G gráf]][[File:Algel zh 2013tavasz El suly.png\|400px\|F gráf]]

			Talán egyszerűbben: mivel 0 az utazási idő (élsúlyok) és bármerre megyünk egy csúcsból, ugyanannyit kell várni, ezért tekinthetjük a csúcsból kimenő élek súlyának a csúcsban töltött időt (A-ból 0, mivel itt nem várakozunk, B-ből nem megyünk tovább...). Így az eredeti gráfon (az élsúlyok beírása után) alkalmazható a Dijkstra algo.
			--[[Szerkesztő:Deák Zsolt\|Deák Zsolt]] ([[Szerkesztővita:Deák Zsolt\|vita]]) 2015. április 8., 12:22 (UTC)
	}}		}}

Kálmán Tibor: /* 5. Feladat */

2015-04-07T21:06:21Z

5. Feladat

← Régebbi változat		A lap 2015. április 7., 23:06-kori változata
96. sor:		96. sor:

	===5. Feladat===		===5. Feladat===
	~~TODO~~		Adjacencia-mátrixá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 a városok közti távolságot adja meg. (Feltehetjük, hogy a távolságok egészek.)
			Adjon egy O(n<sup>6</sup>) lépésszámú algoritmust, ami eldönti, hogy lehetséges-e úgy kiválasztani öt várost, hogy ezektől bármely más város legfeljebb 50 kilométerre van. ''(Ezekbe a városokba lenne érdemes hókoztrókat telepíteni.)''
	{{Rejtett		{{Rejtett
	\|mutatott=<big>'''Megoldás'''</big>		\|mutatott=<big>'''Megoldás'''</big>
	\|szöveg=		\|szöveg=
			*A megoldáshoz először Floyd algoritmussal páronként meghatározzuk az összes város távolságát, ez O(n<sup>3</sup>).<br>
	~~TODO~~		*A város irányítatlan gráfként van megadva, de ezen könnyen segíthetünk úgy, hogy a jelenlegi élek helyett felveszünk két irányítottat, azonos súllyal. Ez O(n<sup>2</sup>).<br>
			*Ezek után brute force módszerrel az összes csúcsötösre ellenőrizzük, hogy azok öten lefedik-e (legfeljebb 50 km-re vannak) az összes várost.<br>
			*n<sup>5</sup> városötös van, mindegyikre le kell ellenőrizni, hogy jók-e. Az ellenőrzés során végignézzük, az összes csúcsra (n db.), hogy el lehet-e érni. Ez tehát O(n<sup>5</sup>n)=O(n<sup>6</sup>).<br>
			*Összességében ezért O(n<sup>6</sup>) lépésszámú az algoritmus.
	}}		}}

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

2013-12-19T05:46:00Z

← Régebbi változat		A lap 2013. december 19., 07:46-kori változata
46. sor:		46. sor:
	*A keresett <math> k,l </math> párost pedig folyamat nyilván tartjuk: ha <math> B[i,j] \geq aktmax \Rightarrow k=i, l=j, aktmax = B[i,j] </math>. ''(ez <math>\Rightarrow n^2-1=O(n^2)</math> lépés)''		*A keresett <math> k,l </math> párost pedig folyamat nyilván tartjuk: ha <math> B[i,j] \geq aktmax \Rightarrow k=i, l=j, aktmax = B[i,j] </math>. ''(ez <math>\Rightarrow n^2-1=O(n^2)</math> lépés)''
	*<math> 1+2O(n)+ 3O(n^2)=O(n^2)</math> lépésszámú algoritmusunk van, tehát jók vagyunk.		*<math> 1+2O(n)+ 3O(n^2)=O(n^2)</math> lépésszámú algoritmusunk van, tehát jók vagyunk.
	:::::::::::::::::[[File:~~A_B_matrix~~.PNG\|400px]]		:::::::::::::::::[[File:Algel zh 2013tavasz A B matrix.PNG\|400px]]

	}}		}}
73. sor:		73. sor:
	**Az 5. sorban a gyökér a 6 lesz, így azt berajzoljuk a 9-es bal fiának. És itt látszik is, hogy hiba van, hiszen <math> < > < </math> sorrend van, ebből következik, hogy ilyen fa nem létezhet.		**Az 5. sorban a gyökér a 6 lesz, így azt berajzoljuk a 9-es bal fiának. És itt látszik is, hogy hiba van, hiszen <math> < > < </math> sorrend van, ebből következik, hogy ilyen fa nem létezhet.

	::::::::::[[File:~~post_tabla~~.png\|400px]] [[File:~~graf~~.png\|300px]]		::::::::::[[File:Algel zh 2013tavasz Post tabla.png\|400px]] [[File:Algel zh 2013tavasz Graf.png\|300px]]
	}}		}}

90. sor:		90. sor:
	**A Dijkstra-algoritmus <math> O(n^2) </math> lépésben keres legrövidebb utat, ebben az esetben <math> O((2n)^2)=4O(n^2)=O(n^2)</math>.		**A Dijkstra-algoritmus <math> O(n^2) </math> lépésben keres legrövidebb utat, ebben az esetben <math> O((2n)^2)=4O(n^2)=O(n^2)</math>.
	*Így a feladat ezzel meg is oldva.		*Így a feladat ezzel meg is oldva.
	::::::::::[[File:~~csucs_suly~~.png\|300px\|G gráf]][[File:~~el_suly~~.png\|400px\|F gráf]]		::::::::::[[File:Algel zh 2013tavasz Csucs suly.png\|300px\|G gráf]][[File:Algel zh 2013tavasz El suly.png\|400px\|F gráf]]

Arklur: /* 6. Feladat */

2013-06-18T09:45:35Z

6. Feladat

← Régebbi változat		A lap 2013. június 18., 11:45-kori változata
104. sor:		104. sor:
	}}		}}

	===6. Feladat===		===6. Feladat (Van megoldás)===
	~~TODO~~		Egy tömbben adott <math>n</math> darab 0-tól különböző egész szám (lehetnek negatívak is köztük) és adott egy <math>k</math> egész szám is. Adjon <math>O(n \cdot logn)</math> lépésszámú algoritmust, ami eldönti, hogy melyik az a <math>k</math> elem a tömbben, melyek szorzata maximális.
	{{Rejtett		{{Rejtett
	\|mutatott=<big>'''Megoldás'''</big>		\|mutatott=<big>'''Megoldás'''</big>
	\|szöveg=		\|szöveg=

	~~TODO~~		*Első lépésben csökkenő sorrendbe rendezzük az elemeket azok '''abszolút értéke''' szerint. <math> (O(n \cdot logn) </math> pl. összefésüléses rendezéssel. <math>)</math>
			*Vesszük az első <math>k</math> szám szorzatát.
			**Ha ez pozitív, akkor jók vagyunk, nincs más dolgunk. [[File:algel_zh_2013tavasz_6_1.PNG\|250px]]
			**Ha ez negatív, akkor kiválasztjuk a listából a legkisebb pozitív <math>(A^+)</math> és negatív <math>(A^-)</math> elemet, a maradék listából pedig a legnagyobb pozitív <math>(B^+)</math> és negatív <math>(B^-)</math> elemet. Most meg kell nézni, hogy mit éri meg lecserélni? A pozitívat negatívra, vagy a negatívat pozitívra?
			***Ha <math> (A^- \cdot B^-) < (A^+ \cdot B^+) </math>, akkor a listából kivesszük <math> A^- </math>-t, és berakjuk <math> B^+ </math>-t
			***Ha <math> (A^+ \cdot B^+) < (A^- \cdot B^-) </math>, akkor a listából kivesszük <math> A^+ </math>-t, és berakjuk <math> B^- </math>-t<br>[[File:algel_zh_2013tavasz_6_2.PNG\|500px]]
			***Ha nincs a listában pozitív szám, akkor kivesszük a <math>A^-</math>-t, és berakjuk <math>B^+</math>-t<br>[[File:algel_zh_2013tavasz_6_3.PNG\|500px]]
			***Ha nincs az egész listában pozitív szám, akkor a legnagyobb számot akkor kapjuk, ha a <math>k</math> darab utolsó elemet vesszük be.<br>[[File:algel_zh_2013tavasz_6_4.PNG\|500px]]

	}}		}}

Arklur: /* 1. Feladat Van megoldás) */

2013-06-17T18:59:51Z

1. Feladat Van megoldás)

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

	==2013.04.03. ZH megoldásai==		==2013.04.03. ZH megoldásai==
	===1. Feladat Van megoldás)===		===1. Feladat (Van megoldás)===
	Mi az a legkisebb ''r'' racionális szám, melyre teljesül, hogy <math>\sqrt{1} + \sqrt{2} + \sqrt{3} + ...+\sqrt{n} = O(n^{r}) ?</math>		Mi az a legkisebb ''r'' racionális szám, melyre teljesül, hogy <math>\sqrt{1} + \sqrt{2} + \sqrt{3} + ...+\sqrt{n} = O(n^{r}) ?</math>
	{{Rejtett		{{Rejtett

Arklur: /* 1. Feladat */

2013-06-17T18:59:37Z

1. Feladat

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

	==2013.04.03. ZH megoldásai==		==2013.04.03. ZH megoldásai==
	===1. Feladat===		===1. Feladat Van megoldás)===
	Mi az a legkisebb ''r'' racionális szám, melyre teljesül, hogy <math>\sqrt{1} + \sqrt{2} + \sqrt{3} + ...+\sqrt{n} = O(n^{r}) ?</math>		Mi az a legkisebb ''r'' racionális szám, melyre teljesül, hogy <math>\sqrt{1} + \sqrt{2} + \sqrt{3} + ...+\sqrt{n} = O(n^{r}) ?</math>
	{{Rejtett		{{Rejtett

Arklur: /* 1. Feladat */

2013-06-17T18:58:30Z

1. Feladat

← Régebbi változat		A lap 2013. június 17., 20:58-kori változata
3. sor:		3. sor:
	==2013.04.03. ZH megoldásai==		==2013.04.03. ZH megoldásai==
	===1. Feladat===		===1. Feladat===
	~~TODO~~		Mi az a legkisebb ''r'' racionális szám, melyre teljesül, hogy <math>\sqrt{1} + \sqrt{2} + \sqrt{3} + ...+\sqrt{n} = O(n^{r}) ?</math>
	{{Rejtett		{{Rejtett
	\|mutatott=<big>'''Megoldás'''</big>		\|mutatott=<big>'''Megoldás'''</big>
	\|szöveg=		\|szöveg=
			*Először megpróbáljuk felülről becsülni:
			**Felülről becsüljük a sorozatot, ha az elemeket rendre <math>\sqrt{n}</math>-nek tekintjük, vagyis:<br><br>
			**<math>\sqrt{n} + \sqrt{n} + \sqrt{n} + ...+\sqrt{n}=n\cdot\sqrt{n}=n^{1.5}=O(n^{1.5}) \Rightarrow r=1.5</math><br><br>
			*Most pedig megpróbáljuk alulról becsülni: <br><br>
			**Alulról becsüljük a sorozatot: <br><br>
			**<math> \frac{n}{2 } \cdot \sqrt{1}+\frac{n}{2} \cdot \sqrt{n} \leq \sqrt{1} + \sqrt{2} + \sqrt{3} \dots \sqrt{n} </math> <br><br>
			**<math> \frac{n}{2 } \cdot \sqrt{1}+\frac{n}{2} \cdot \sqrt{n} = O(n^{1.5}) \Rightarrow r=1.5. </math> <br><br>
			*A kettőt együttvéve látszik, hogy <math> r = 1.5 .</math>

	~~TODO~~
	}}		}}

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

2013-06-14T08:08:02Z

3. Feladat (Van megoldás)

← Régebbi változat		A lap 2013. június 14., 10:08-kori változata
55. sor:		55. sor:
	*Szokásos rendezést használó bináris keresőfa: <math>bal(x) < x < jobb(x)</math>		*Szokásos rendezést használó bináris keresőfa: <math>bal(x) < x < jobb(x)</math>
	*Postorder:		*Postorder:
	**Rekurzívan <math> bal(x) \rightarrow jobb(x) \rightarrow x </math>. Magyarul előbb meglátogatja a gyökérnél kisebbeket, utána a nagyobbakat, és ezután jön csak a gyökér.		**Rekurzívan <math> bal(x) \rightarrow jobb(x) \rightarrow x </math>.''(Magyarul: előbb meglátogatja a gyökérnél kisebbeket, utána a nagyobbakat, és ezután jön csak a gyökér.)''
	**Egyik fontos tulajdonsága, hogy a '''gyökér''' az mindig a ''(figyelt)'' '''lista végén van'''.		**Egyik fontos tulajdonsága, hogy a '''gyökér''' az mindig a ''(figyelt)'' '''lista végén van'''.
	}}		}}

Hryghr, 2013. június 13., 21:20-n

2013-06-13T21:20:11Z

← Régebbi változat		A lap 2013. június 13., 23:20-kori változata
1. sor:		1. sor:
			{{Vissza\|Algoritmuselmélet}}

	==2013.04.03. ZH megoldásai==		==2013.04.03. ZH megoldásai==
	===1. Feladat===		===1. Feladat===
160. sor:		162. sor:
	*Nem. A gyökérnek feketének kell lennie.		*Nem. A gyökérnek feketének kell lennie.
	}}		}}

			[[Kategória:Infoalap]]

Hryghr: Hryghr átnevezte a(z) Algoritmuselmélet 2013.04.03. ZH megoldásai lapot a következő névre: Algoritmuselmélet - ZH, 2013.04.03.

2013-06-13T21:18:12Z

Hryghr átnevezte a(z) Algoritmuselmélet 2013.04.03. ZH megoldásai lapot a következő névre: Algoritmuselmélet - ZH, 2013.04.03.

← Régebbi változat		A lap 2013. június 13., 23:18-kori változata
(Nincs különbség)