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

Nagy Marcell: autoedit v2: fájlhivatkozások egységesítése, az új közvetlenül az adott fájlra mutat

2017-07-12T13:49:21Z

autoedit v2: fájlhivatkozások egységesítése, az új közvetlenül az adott fájlra mutat

← Régebbi változat		A lap 2017. július 12., 15:49-kori változata
17. sor:		17. sor:
	bsz - befejezési szám<br>		bsz - befejezési szám<br>
	Ha <math> (msz[y] < msz[x]) </math> és <math>(bsz[y] > 0) </math>, akkor az x → y egy keresztél.<br>		Ha <math> (msz[y] < msz[x]) </math> és <math>(bsz[y] > 0) </math>, akkor az x → y egy keresztél.<br>
	[[~~Fájl~~:Algel vizsga 2013tavasz Keresztel 1.png]]<br>		[[Media:Algel vizsga 2013tavasz Keresztel 1.png]]<br>
	'''c)'''<br>		'''c)'''<br>
	A '''b)''' rész alapján könnyen belátható. Ha lenne keresztél, az azt jelentené, hogy van olyan x → y él, amire fennáll, hogy <math> (msz[y] < msz[x]) </math> és <math>(bsz[y] > 0) </math>, vagyis y-ban előbb jártunk, mint x-ben, és y-nak van befejezési száma. Ennél fogva nem lehet keresztél, hiszen ha lenne, akkor y-ból eljuthattunk volna még x-be, mielőtt befejeztük volna.<br>		A '''b)''' rész alapján könnyen belátható. Ha lenne keresztél, az azt jelentené, hogy van olyan x → y él, amire fennáll, hogy <math> (msz[y] < msz[x]) </math> és <math>(bsz[y] > 0) </math>, vagyis y-ban előbb jártunk, mint x-ben, és y-nak van befejezési száma. Ennél fogva nem lehet keresztél, hiszen ha lenne, akkor y-ból eljuthattunk volna még x-be, mielőtt befejeztük volna.<br>
	'''Másképpen mondva:''' Nem fejezhettük volna be y-t anélkül, hogy ne jártunk volna x-ben.<br>		'''Másképpen mondva:''' Nem fejezhettük volna be y-t anélkül, hogy ne jártunk volna x-ben.<br>
	[[~~Fájl~~:Algel vizsga 2013tavasz Keresztel 2.PNG]]<br>		[[Media:Algel vizsga 2013tavasz Keresztel 2.PNG]]<br>
	}}		}}

187. sor:		187. sor:
	\|mutatott=<big>'''Megoldás'''</big>		\|mutatott=<big>'''Megoldás'''</big>
	\|szöveg=		\|szöveg=
	[[~~File~~:Algel vizsga 2013tavasz V2 6.png]]		[[Media:Algel vizsga 2013tavasz V2 6.png]]

	'''a)''' Prim algoritmus - Ugyebár úgy dolgozik, hogy az aktuális fához a vele szomszédos élek közül a legkisebb súlyút veszi be. Prim: BE → ED → BA → BC		'''a)''' Prim algoritmus - Ugyebár úgy dolgozik, hogy az aktuális fához a vele szomszédos élek közül a legkisebb súlyút veszi be. Prim: BE → ED → BA → BC

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

2015-06-18T14:11:07Z

6. Feladat (Van megoldás)

← Régebbi változat		A lap 2015. június 18., 16:11-kori változata
197. sor:		197. sor:
	$$$ Észrevétel/kérdés $$$		$$$ Észrevétel/kérdés $$$

	Nem vagyok nagy algel tudós, de miért ne lehetne y>=1? Tudomásom szerint, a Prim az mindig a legkisebb olyan élt veszi be ami olyan csúcsba visz ami eddig nem volt a halmazba. Ha pedig nincs igazam, akkor meg y>=2 mivel (AE) súlya 2 és akkor azt kellene, (ha csak a sulyok szerint növekvőt nézzük.		Nem vagyok nagy algel tudós, de miért ne lehetne y>=1? Tudomásom szerint, a Prim az mindig a legkisebb olyan élt veszi be ami olyan csúcsba visz ami eddig nem volt a halmazba. Ha pedig nincs igazam, akkor meg y>=2 mivel (AE) súlya 2 és akkor azt kellene, (ha csak a sulyok szerint növekvőt nézzük).

	$$$$$$		$$$$$$

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

2015-06-18T14:10:10Z

6. Feladat (Van megoldás)

← Régebbi változat		A lap 2015. június 18., 16:10-kori változata
194. sor:		194. sor:
	# Most az AB élt adjuk hozzá, ez alapján <math>y \ge 1</math>.		# Most az AB élt adjuk hozzá, ez alapján <math>y \ge 1</math>.
	# Most a BC élt adjuk hozzá, ez alapján <math>y \ge 3</math>, így végül <math>y \ge 3</math>.		# Most a BC élt adjuk hozzá, ez alapján <math>y \ge 3</math>, így végül <math>y \ge 3</math>.

			$$$ Észrevétel/kérdés $$$

			Nem vagyok nagy algel tudós, de miért ne lehetne y>=1? Tudomásom szerint, a Prim az mindig a legkisebb olyan élt veszi be ami olyan csúcsba visz ami eddig nem volt a halmazba. Ha pedig nincs igazam, akkor meg y>=2 mivel (AE) súlya 2 és akkor azt kellene, (ha csak a sulyok szerint növekvőt nézzük.

			$$$$$$

	'''b)''' Kruskal algoritmus - Éleket nagyság szerint sorrendbe rakjuk, és növekvő sorrendben felvesszük a fához az éleket, vigyázva, hogy ne csináljunk kört.		'''b)''' Kruskal algoritmus - Éleket nagyság szerint sorrendbe rakjuk, és növekvő sorrendben felvesszük a fához az éleket, vigyázva, hogy ne csináljunk kört.

Soltész Balázs Péter: /* 3. Feladat */

2015-01-20T14:35:01Z

3. Feladat

← Régebbi változat		A lap 2015. január 20., 16:35-kori változata
53. sor:		53. sor:
	}}		}}

	===3. Feladat===		===3. Feladat (Van megoldás)===
	Adja meg az UNIÓ-HOLVAN adatszerkezet definícióját! (A fákkal való implementálást nem kell leírnia.) Mutassa meg, hogy mikor és hogyan használjuk az UNIÓ és a HOLVAN műveleteket a Kruskal algoritmusban!		Adja meg az UNIÓ-HOLVAN adatszerkezet definícióját! (A fákkal való implementálást nem kell leírnia.) Mutassa meg, hogy mikor és hogyan használjuk az UNIÓ és a HOLVAN műveleteket a Kruskal algoritmusban!

65. sor:		65. sor:

	'''Mi az a Kruskal algoritmus?'''<br>		'''Mi az a Kruskal algoritmus?'''<br>
	~~todo~~ <br><br>		A Kruskal algoritmust minimális költségű feszítőfák meghatározására használjuk. A piros-kék algoritmus egyik implementációja. <br>
			Lényege, hogy a gráf éleit súlyuk szerint nem csökkenő sorrendbe állítja, majd sorban megpróbálja kékre színezni őket. <br>
			Ennek az a feltétele, hogy az újonnan kékre színezendő él beszínezése után se legyen kör a kékre színezett élek által alkotott gráfban. <br>
			Ha ez mégis kört eredményezne, úgy az él nem kék, hanem piros lesz.<br>
			A kékre színezett élek egy minimális összsúlyú feszítőfát adnak.<br><br>
	}}		}}
	'''UNIÓ-HOLVAN adatszerkezet definíciója: '''<br><br>		'''UNIÓ-HOLVAN adatszerkezet definíciója: '''<br><br>
	~~todo~~ <br><br>		Adott egy véges S halmaz, amelynek egy felosztását (partícióját) akarjuk tárolni. <br>
			2 műveletünk van:<br>

			UNIÓ(U, V halmazok, amelyek S részhalmazai): S-ből kivesszük az U-t és a V-t, majd hozzáadjuk (unió) U és V unióját. <br><br>

			HOLVAN(v pont, v benne van S-ben): Azt az U halmazt adja meg, amelynek v eleme.<br><br>

	'''Mikor és hogyan használjuk az UNIÓ és a HOLVAN műveleteket a Kruskal algoritmusban:'''<br>		'''Mikor és hogyan használjuk az UNIÓ és a HOLVAN műveleteket a Kruskal algoritmusban:'''<br>
	~~todo~~ <br><br>		A Kruskal algoritmus lelke az UNIÓ-HOLVAN adatszerkezet. <br>
			Kezdetben a gráf minden pontja másik <math>U_i</math> részhalmazban van, tehát minden <math>U_i</math> egy pontot tartalmaz.<br>
			Az algoritmus elindul a legkisebb súlyú éleken. <br>
			Az élek két végpontjára (v és w) megvizsgálja, hogy HOLVAN(v) egyenlő-e HOLVAN(w)-vel. <br>
			Ha igen, akkor egy részhalmazban vannak, kört okoznának => piros él lesz.<br>
			Ha nem áll fenn az egyenlőség, akkor a (v,w) kék lesz, a két részhalmazt pedig nyugodtan egyesíthetjük (hozzávehetjük az új élet a kék gráfhoz):<br>
			UNIÓ(<math>U_v</math>,<math>U_w</math>).

	}}		}}

Jogaproger: /* 8. Feladat */

2014-06-04T21:42:55Z

8. Feladat

← Régebbi változat		A lap 2014. június 4., 23:42-kori változata
217. sor:		217. sor:
	\|mutatott=<big>'''Megoldás'''</big>		\|mutatott=<big>'''Megoldás'''</big>
	\|szöveg=		\|szöveg=
	~~TODO~~		Legyen az eldöntési probléma neve A<br>
			G ∈ A akkor, ha G∈3SZÍN vagy G∈H<br>
			Adjunk 3SZÍN < A Karp redukciót, ekkor mivel a 3SZÍN probléma NP-teljes az A is NP-teljes lesz.<br><br>

			G' legyen az a gráf, amelyet úgy kapunk, hogy G-t kiegészítünk egy 3 csúcsból álló körrel. Mivel G'-ben biztosan nincs Hamilton-út ( Nem összefüggő ), ezért G' ∈ A akkor és csakis akkor, ha G ∈ 3SZÍN
	}}		}}

	[[Kategória:Infoalap]]		[[Kategória:Infoalap]]

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

2013-12-19T05:53:34Z

← Régebbi változat		A lap 2013. december 19., 07:53-kori változata
172. sor:		172. sor:
	\|mutatott=<big>'''Megoldás'''</big>		\|mutatott=<big>'''Megoldás'''</big>
	\|szöveg=		\|szöveg=
	[[File:~~2013_06_06_V2_6~~.png]]		[[File:Algel vizsga 2013tavasz V2 6.png]]

	'''a)''' Prim algoritmus - Ugyebár úgy dolgozik, hogy az aktuális fához a vele szomszédos élek közül a legkisebb súlyút veszi be. Prim: BE → ED → BA → BC		'''a)''' Prim algoritmus - Ugyebár úgy dolgozik, hogy az aktuális fához a vele szomszédos élek közül a legkisebb súlyút veszi be. Prim: BE → ED → BA → BC

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

2013-12-19T05:47:34Z

← Régebbi változat		A lap 2013. december 19., 07:47-kori változata
17. sor:		17. sor:
	bsz - befejezési szám<br>		bsz - befejezési szám<br>
	Ha <math> (msz[y] < msz[x]) </math> és <math>(bsz[y] > 0) </math>, akkor az x → y egy keresztél.<br>		Ha <math> (msz[y] < msz[x]) </math> és <math>(bsz[y] > 0) </math>, akkor az x → y egy keresztél.<br>
	[[Fájl:~~keresztel_1~~.png]]<br>		[[Fájl:Algel vizsga 2013tavasz Keresztel 1.png]]<br>
	'''c)'''<br>		'''c)'''<br>
	A '''b)''' rész alapján könnyen belátható. Ha lenne keresztél, az azt jelentené, hogy van olyan x → y él, amire fennáll, hogy <math> (msz[y] < msz[x]) </math> és <math>(bsz[y] > 0) </math>, vagyis y-ban előbb jártunk, mint x-ben, és y-nak van befejezési száma. Ennél fogva nem lehet keresztél, hiszen ha lenne, akkor y-ból eljuthattunk volna még x-be, mielőtt befejeztük volna.<br>		A '''b)''' rész alapján könnyen belátható. Ha lenne keresztél, az azt jelentené, hogy van olyan x → y él, amire fennáll, hogy <math> (msz[y] < msz[x]) </math> és <math>(bsz[y] > 0) </math>, vagyis y-ban előbb jártunk, mint x-ben, és y-nak van befejezési száma. Ennél fogva nem lehet keresztél, hiszen ha lenne, akkor y-ból eljuthattunk volna még x-be, mielőtt befejeztük volna.<br>
	'''Másképpen mondva:''' Nem fejezhettük volna be y-t anélkül, hogy ne jártunk volna x-ben.<br>		'''Másképpen mondva:''' Nem fejezhettük volna be y-t anélkül, hogy ne jártunk volna x-ben.<br>
	[[Fájl:~~keresztel_2~~.PNG]]<br>		[[Fájl:Algel vizsga 2013tavasz Keresztel 2.PNG]]<br>
	}}		}}

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

2013-06-17T19:17:10Z

7. Feladat (Van megoldás)

@@ 203. sor: / 203. sor: @@
 |szöveg=
-{{Rejtett
+*'''Tétel:''' Ha X ≺ Y és Y ∈ NP,akkor X ∈ NP
-|mutatott=<big>'''Kiegészítések a feladat megértéséhez'''</big>
+*'''Tétel:''' A SAT probléma NP teljes, tehát része NP-nek.
-|szöveg=
+*A fentiek alapján, mivel X<big>∉</big>NP, a kérdéses X probléma nem létezhet.
 }}

Arklur: /* 8. Feladat */

2013-06-17T19:15:49Z

8. Feladat

@@ 253. sor: / 253. sor: @@
 |mutatott=<big>'''Megoldás'''</big>
 |szöveg=
+TODO
 }}
 [[Kategória:Infoalap]]

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

2013-06-13T21:20:08Z

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

	==2013.06.06. vizsga megoldásai==		==2013.06.06. vizsga megoldásai==
	===1. Feladat (Van megoldás) ===		===1. Feladat (Van megoldás) ===
293. sor:		295. sor:

	}}		}}

			[[Kategória:Infoalap]]