VIK Wiki - Felhasználó közreműködései [hu]

Algoritmuselmélet - Vizsga, 2013.06.06.

2013-06-11T11:51:59Z

Subdiaz: /* 8. Feladat */

==2013.06.06. vizsga megoldásai==
===1. Feladat (Van megoldás) ===
Ebben a feladatban a mélységi bejárással kapcsolatos kérdésekre kell válaszolni.
* '''(a)''' Adja meg a keresztél definícióját!
* '''(b)''' A mélységi bejárás során hogyan lehet a mélységi és a befejezési számok alapján felismerni a keresztéleket? ''Vizsgán megjegyzést fűztek hozzá: irányított gráfokra kell gondolni.''
* '''(c)''' Bizonyítsa be, hogy irányítatlan gráf mélységi bejárásánál nincsenek keresztélek!
{{Rejtett
|mutatott=<big>'''Megoldás'''</big>
|szöveg=
'''a)''' 
Tekintsük a G irányított gráf egy mélységi bejárását és a kapott T mélységi feszítő erdőt. Ezen bejárás szerint G egy x → y éle keresztél, ha x és y nem leszármazottjai egymásnak.

'''b)''' 
msz - mélységi szám 
bsz - befejezési szám 
Ha <math> (msz[y] < msz[x]) </math> és <math>(bsz[y] > 0) </math>, akkor az x → y egy keresztél. 
[[Fájl:keresztel_1.png]] 
'''c)''' 
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. 
'''Másképpen mondva:''' Nem fejezhettük volna be y-t anélkül, hogy ne jártunk volna x-ben. 
[[Fájl:keresztel_2.PNG]] 
}}

===2. Feladat (Van megoldás)===
Milyen műveletek vannak a nyitott címzésű hash-elésnél? Hogyan kell megvalósítani a keresést, ha a nyitott címzésű hashelésnél kvadratikus maradék próbát használunk?

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

{{Rejtett
|mutatott=<big>'''Kiegészítések a feladat megértéséhez'''</big>
|szöveg=

'''Mi az a nyitott címzésű hash-elés?''' 
lásd: https://wiki.sch.bme.hu/Hash_t%C3%B6mb 

'''Mi az a kvadratikus maradék próba, nyitott címzésű hash-elésnél?''' 
todo 
}}
'''Nyitott címzésű hash-elés műveletei:''' 
Új elem beszúrása, elem keresése, elem törlése. 
A törlés speciális jelzéssel történik. 

'''Keresés megvalósítása nyitott címzésű hash-elés esetén kvadratikus maradék próbánál:''' 
A kvadratikus maradék próba egy álvéletlen próba, ezért másodlagos csomósodáshoz vezethet. 
Legyen M egy 4k + 3 alakú prímszám, ahol k egy pozitív egész. 
Ekkor a próbasorozat legyen 
<math> 0,1^2,(-1)^2, 2^2,(-2)^2,..,\left ( \frac{M-1}{2} \right )^{2}, -\left ( \frac{M-1}{2} \right )^{2} </math>

}}

===3. Feladat===
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!

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

{{Rejtett
|mutatott=<big>'''Kiegészítések a feladat megértéséhez'''</big>
|szöveg=

'''Mi az a Kruskal algoritmus?''' 
todo 
}}
'''UNIÓ-HOLVAN adatszerkezet definíciója: ''' 
todo 

'''Mikor és hogyan használjuk az UNIÓ és a HOLVAN műveleteket a Kruskal algoritmusban:''' 
todo 

}}

===4. Feladat===
Pista bácsi fel akar ugrálni egy n hosszú, fekete illetve fehér fokokból álló csigalépcsőn. Legfeljebb k fokot tud ugrani, de arra vigyáznia kell, hogy páros (>=2) sok foknyi ugrás után páratlan sokat és páratlan sok után mindig páros (>=2) sokat ugorjon. Adjon O(nk) lépésszámú algoritmust, amely megmondja, hogy fel tud-e úgy ugrálni a csigalépcső tetejére, hogy csak egyféle színű lépcsőfokot használ. (A lépcső fokai rendszertelenül vannak színezve, a színezést ismerjük.)
''Vizsgán megjegyzést fűztek hozzá: a talaj és a legteteje nem színes, csak a lépcsők; csak fölfele (előrefele) ugrál, visszafele nem. ''

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

todo

 

}}

===5. Feladat (Van megoldás)===
A hátizsák probléma órán tanult algoritmusát futtattuk egy konkrét inputon, melyben 3 tárgy szerepel. Mi lehetett ez a konkrét input, ha az alábbi táblázat keletkezett?

{| class="wikitable" border="5"
|-
!
! 0
! 1
! 2
! 3
! 4
! 5
! 6
! 7
|-
| 1
| 0
| 0
| 0
| 0
| 10
| 10
| 10
| 10
|-
| 2
| 0
| 0
| 5
| 5
| 10
| 10
| 15
| 15
|-
| 3
| 0
| 0
| 5
| 5
| 13
| 13
| 18
| 18
|}

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

Az egyszerűség kedvéért a súly legyen kg, az érték pedig €.

#Az első sor alapján az 1-es csomag értéke €10, súlya 4kg.
#A második sor alapján a 2-es csomag értéke €5, súlya 2kg.
#A 3. lépésben 2 lehetőségünk van, a 3. csomag értéke vagy 13-5=€8, vagy 13-0=€13.
##€8 nem lehet, mert akkor a súlya 2kg lenne, de akkor a [2,3] cellába 8 lenne, nem 5.
##Így csak a €13 jöhet szóba, súlya pedig 4kg, ami jó megoldás lesz.

{{Rejtett
|mutatott=''Avagy kicsit gépiesebb megoldás:''
|szöveg=
 
Jelölje <math> T[s,cs]</math> a táblázat <math>[s,cs]</math> celláját, továbbá <math> V_3</math> a 3. csomag értékét, <math> S_3</math> pedig a súlyát. 
Tudjuk, hogy <math> T[s,cs]=max\left \{ T[s,cs-1];V_i+T[s-S_i,cs-1] \right \}</math>, ami ebben az esetben: 
<math> T[4,3]=max\left \{ T[4,2];V_3+T[4-S_3,2] \right \} \rightarrow 13=max\left \{ 10;V_3+T[4-S_3,2] \right \}</math>, amiből következik, hogy: 
<math> 13=V_3+T[4-S_3,2] \rightarrow V_3 = 13-T[4-S_3,2]\Rightarrow\Rightarrow S_3=4, V_3=13</math> (Átgondolható, hogy a 3. csomag súlya nem lehet 1,2 vagy 3kg).
}}
Tehát végeredményben a megoldás:
*1-es csomag (€10, 4kg)
*2-es csomag (€5, 2kg)
*3-as csomag (€13, 4kg)

}}

===6. Feladat (Van megoldás)===
Egy irányítatlan, élsúlyozott gráf az alábbi éllistával adott (zárójelben az élsúlyok):

<math>A:B(1), D(3), E(2); B:A(1), C(3), D(y); D:A(3), C(y), E(x); E:A(2), B(1), D(x).</math>
* '''(a)''' Mi lehet x és y értéke, ha tudjuk, hogy az élsúlyok egész számok, és azt is tudjuk, hogy a B csúcsból indított Prim algoritmus az alábbi sorrendben vette be az értékeket: BE, ED, BA, BC. ''Vizsgán megjegyzést fűztek hozzá: az élsúlyok pozitív egész számok, a pozitív szót kifelejtették véletlenül.''
* '''(b)''' Mely éleket és milyen sorrendben választja ki a Kruskal algoritmus? (Ha több megoldás is van, akkor az összeset adja meg!)
{{Rejtett
|mutatott=<big>'''Megoldás'''</big>
|szöveg=
[[File:2013_06_06_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 fához hozzáadjuk a BE élt.
# Most az ED élt választottuk. Ez alapján x értéke csak 1 lehet, így <math>x = 1</math>. (Feladatból kihagyták, hogy pozitív egészekről van szó, amúgy <math>x \le 1</math> lehetne.)
# 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>.

'''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.

1 súlyú - AB, BE, ED

2 súlyú - AE

3 súlyú - BC, AD, EC (és DC, ha <math>y = 3</math>)

Az összes megoldás:

#Az 1 súlyú éleket <math>3! = 6</math> féleképpen veheti fel az algoritmus (nem lehet belőlük kört csinálni, így itt nincsen para).
#Utána megpróbálná felvenni az AE élt, de azzal egy kört kapna, így nem veszi fel. Az AD éllel szintén így járna (~ezeket kéne pirosra színezni, ha olyan lenne a feladat).
#Maradtak a BC, EC és DC oldalak.
##Ha <math>y = 3</math>, akkor ezeket szintén 6 féleképpen veheti fel, tehát összesen 36 féleképpen futhat az algoritmus.
##Ha <math>y \ge 3</math>, akkor a DC oldal kiesik, a maradék 2 élt 2 féleképpen veheti fel, így 12 féleképpen futhat az algoritmus.}}

===7. Feladat (Van megoldás)===
Létezik-e olyan X eldöntési probléma, amire X<big>∉</big>NP és X<big>≺</big>SAT egyszerre fennáll?

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

{{Rejtett
|mutatott=<big>'''Kiegészítések a feladat megértéséhez'''</big>
|szöveg=
<big>'''Eldöntési probléma osztályok? ''' </big>

 
[[File:bonyolultsag_elmelet.JPG|390px]]
 

A '''problémák'''nak lehet több típusú több bemenete, és több típusú több kimenete. Ezeket átfogalmazzuk olyanra, hogy a kimenete egyetlen bit legyen (IGEN / NEM), mert ezen algoritmusok felhasználásával is teljesen jól lehet dolgozni, ugyanakkor könnyebb őket nehézség / bonyolultság szerint osztályozni. Az ilyen 1 bites kimenetű problémákat nevezzük '''eldöntési problémák'''nak. 

Az eldöntési problémákat nehézség / bonyolultság szerint osztályokba soroljuk, ezen osztályok között olyan kapcsolatok vannak mint a halmazoknál; ez a fenti rajzon látszik. 

A '''P osztály'''ba olyan problémák tartoznak, amelyekre ismert olyan algoritmus, ami a bemenet polinomjával megadott idő alatt lefut. Vagyis ha a bemenet '''n''', akkor az algoritmusra azt mondjuk, hogy nagy_ordó(valami), ahol a valami '''n''' egy polinomja, például n négyzet, n köb, három n négyzet meg négy meg nyolc n köb, és ilyesmik. 

Az '''NP osztály'''ba olyan problémák tartoznak, amelyekre nem feltétlenül ismert polinom idejű (P-beli) algoritmus, de igen válasz esetén létezik hatékony tanúsítvány. Vagyis, adott egy nagy csomó bemenet és van egy kérdés. P-idő alatt nem tudjuk megmondani a választ, de ha valaki megsúgja hogy a válasz IGEN, akkor P-időben meg tudjuk mondani, hogy ez hülyeség vagy nem hülyeség. Ha azt súgják meg hogy NEM, akkor fogalmunk sincs, P-időben nem tudjuk eldönteni hogy hülyeség-e vagy sem. (''Ha így lenne, vagyis igen és nem válasz esetén is P-időben ellenőrizni tudnánk a válasz helyességét, akkor az egész probléma P-beli lenne, hiszen megsúgjuk saját magunknak hogy NEM és ha helyes akkor NEM egyébként igen. Persze ha az IGEN-ről P-időben kiderül hogy hülyeség attól még lehet hogy IGEN, csak éppen nem az a konkrét ami meg lett súgva, hanem egy másik.'') 

A '''coNP osztály''' lényegében ugyanaz mint az NP osztály, csak NEM válaszra. Vagyis (jelenleg) nem ismerünk rá P-beli algoritmust, de ha a válasz NEM, akkor P-időben (hatékonyan) ellenőrizni tudjuk, hogy ez-e a jó válasz vagy sem. Szintén, IGEN válasz esetén semmit sem tudunk mondani P-időben, a fenti okok miatt (ami a zárójelben van). 

Az '''NP nehéz''' osztályba tartozó eldöntési problémák közül bármelyik legalább olyan nehéz, mint bármelyik másik NP-beli eldöntési probléma. Itt jön képbe a Karp-redukció fogalma. Jó dolog sok NP nehéz problémát ismerni, mert akkor ha találunk egy problémát, akkor ha találunk olyan Karp-redukciót, ami azt mutatja, hogy ez a probléma visszavezethető egy közismert NP nehéz problémára, akkor a mi ismeretlen problémánk is NP nehéz lesz. Ez azért van, mert a Karp-redukció tranzitív művelet, továbbá a Karp-redukcónál használt f függvény P-beli, amit kétszer egymás után alkalmazva is még mindig P-beli lesz ez a dolog (az inputok átalakítása). 

Az '''NP teljes''' problémák azok, amik NP nehezek és NP-beliek is egyszerre. A fenti dolog ide is érvényes, vagyis jó dolog ha sok nevezetes NP teljes problémát ismerünk, mert ha egy ismeretlen problémához találunk egy olyan Karp-redukciót, ami alapján az ismeretlen problémánkat visszavezethetjük egy közismert NP teljes problémára, akkor az ismeretlen problémánkról is kiderült, hogy NP teljes. 

<big>'''Karp-redukció?''' </big>
Van egy olyan gépünk, ami kizárólag B problémát tudja megoldani. Nekünk viszont A problémánk van. Ekkor ha szerencsénk van, akkor fogunk találni egy olyan Karp-redukciót, hogy A<big>≺</big>B. Ennek persze vannak feltételei. Az A eldöntési probléma inputját át kell alakítani B eldöntési probléma inputjává, és meg is kell adni ezt a függvényt, nevezzük el ezt a függvényt f függvénynek. Feltétel, hogy f függvény polinom időben kiszámolható legyen, és ezt be is kell bizonyítani. Továbbá azt is be kell bizonyítani, hogy amennyiben a normális inputra A azt válaszolná, hogy IGEN, akkor az f(normális input)-ra a B szintén ugyanezt válaszolná (és ugyanezt be kell bizonyítani NEM válaszra is). Magyarul a B dolgot megoldó gépet megerőszakoljuk hogy A problémát is hajlandó legyen megoldani. 

Ebből következik néhány dolog. Például az, hogy B legalább olyan nehéz probléma, mint A. Ha például B NP-teljes, akkor A is az. Ha B NP-nehéz, akkor A is az. Ha B coNP-beli, akkor A is az. Ez miért van? Hát azért, mert polinom időben át lehet alakítani az A problémát B-vé. Ezt indirekten könnyen lehet bizonyítani. Indirekt tegyük fel, hogy annak ellenére hogy B probléma NP-teljes és létezik egy olyan Karp-redukció ami A problmémát átalakítja B-vé, szóval mindezek ellenére A probléma P-beli. Ekkor A problémát egy polinom idejű f függvénnyel simán átalakítjuk B problémává, erről szól ugye a Karp-redukció. Ezek után ha bármikor B problémát akarnánk megoldani, akkor az f-függvény fordítva végrehajtásával a B inputját átalakítjuk A inputjává, megoldjuk az A problémát polinom időben, és kész is. Ez ellentmondás mivel B-ről azt mondtuk hogy NP-teljes. A másik érdekesség, hogy ha például egy NP-teljes vagy NP-nehéz problémáról kiderülne hogy P-beli, akkor az összes NP-beliről kiderülne hogy P-beli, mivel az NP-nehéz definíciója az, hogy legalább olyan nehéz mint bármely tetszőleges NP-beli. 

Még egy fontos megjegyzés a Karp-redukcióhoz: ugye A problémát akarjuk megoldani, de csak B-t megoldó gépünk van. Az egyik gyakorlaton elhangzott, és fontos tudni, hogy a B-t megoldó gépet az A eldöntési probléma megoldásához csak EGYSZER használhatjuk. Azért mert a Karp-redukció az ilyen. 

<big>'''SAT probléma? ''' </big>
A SAT probléma NP-teljes. 
forrás:http://www.cs.bme.hu/algel/12elo-2012.pdf 
}}

<big>'''A feladat megoldása: ''' </big>
Tétel: Ha X ≺ Y és Y ∈ NP,akkor X ∈ NP 
Tétel: A SAT probléma NP teljes, tehát része NP-nek. 
A fentiek alapján, mivel X<big>∉</big>NP, a kérdéses X probléma nem létezhet.

}}

===8. Feladat===
P-ben van vagy NP-teljes az alábbi eldöntési probléma: 
*'''Input:''' irányítatlan G gráf 
*'''Kérdés:''' Igaz-e, hogy G-ben vagy van Hamilton-út vagy G 3 színnel színezhető? 

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

{{Rejtett
|mutatott=<big>'''Kiegészítések a feladat megértéséhez'''</big>
|szöveg=
<big>'''Eldöntési probléma osztályok? ''' </big>

 
[[File:bonyolultsag_elmelet.JPG|390px]]
 

A '''problémák'''nak lehet több típusú több bemenete, és több típusú több kimenete. Ezeket átfogalmazzuk olyanra, hogy a kimenete egyetlen bit legyen (IGEN / NEM), mert ezen algoritmusok felhasználásával is teljesen jól lehet dolgozni, ugyanakkor könnyebb őket nehézség / bonyolultság szerint osztályozni. Az ilyen 1 bites kimenetű problémákat nevezzük '''eldöntési problémák'''nak. 

Az eldöntési problémákat nehézség / bonyolultság szerint osztályokba soroljuk, ezen osztályok között olyan kapcsolatok vannak mint a halmazoknál; ez a fenti rajzon látszik. 

A '''P osztály'''ba olyan problémák tartoznak, amelyekre ismert olyan algoritmus, ami a bemenet polinomjával megadott idő alatt lefut. Vagyis ha a bemenet '''n''', akkor az algoritmusra azt mondjuk, hogy nagy_ordó(valami), ahol a valami '''n''' egy polinomja, például n négyzet, n köb, három n négyzet meg négy meg nyolc n köb, és ilyesmik. 

Az '''NP osztály'''ba olyan problémák tartoznak, amelyekre nem feltétlenül ismert polinom idejű (P-beli) algoritmus, de igen válasz esetén létezik hatékony tanúsítvány. Vagyis, adott egy nagy csomó bemenet és van egy kérdés. P-idő alatt nem tudjuk megmondani a választ, de ha valaki megsúgja hogy a válasz IGEN, akkor P-időben meg tudjuk mondani, hogy ez hülyeség vagy nem hülyeség. Ha azt súgják meg hogy NEM, akkor fogalmunk sincs, P-időben nem tudjuk eldönteni hogy hülyeség-e vagy sem. (''Ha így lenne, vagyis igen és nem válasz esetén is P-időben ellenőrizni tudnánk a válasz helyességét, akkor az egész probléma P-beli lenne, hiszen megsúgjuk saját magunknak hogy NEM és ha helyes akkor NEM egyébként igen. Persze ha az IGEN-ről P-időben kiderül hogy hülyeség attól még lehet hogy IGEN, csak éppen nem az a konkrét ami meg lett súgva, hanem egy másik.'') 

A '''coNP osztály''' lényegében ugyanaz mint az NP osztály, csak NEM válaszra. Vagyis (jelenleg) nem ismerünk rá P-beli algoritmust, de ha a válasz NEM, akkor P-időben (hatékonyan) ellenőrizni tudjuk, hogy ez-e a jó válasz vagy sem. Szintén, IGEN válasz esetén semmit sem tudunk mondani P-időben, a fenti okok miatt (ami a zárójelben van). 

Az '''NP nehéz''' osztályba tartozó eldöntési problémák közül bármelyik legalább olyan nehéz, mint bármelyik másik NP-beli eldöntési probléma. Itt jön képbe a Karp-redukció fogalma. Jó dolog sok NP nehéz problémát ismerni, mert akkor ha találunk egy problémát, akkor ha találunk olyan Karp-redukciót, ami azt mutatja, hogy ez a probléma visszavezethető egy közismert NP nehéz problémára, akkor a mi ismeretlen problémánk is NP nehéz lesz. Ez azért van, mert a Karp-redukció tranzitív művelet, továbbá a Karp-redukcónál használt f függvény P-beli, amit kétszer egymás után alkalmazva is még mindig P-beli lesz ez a dolog (az inputok átalakítása). 

Az '''NP teljes''' problémák azok, amik NP nehezek és NP-beliek is egyszerre. A fenti dolog ide is érvényes, vagyis jó dolog ha sok nevezetes NP teljes problémát ismerünk, mert ha egy ismeretlen problémához találunk egy olyan Karp-redukciót, ami alapján az ismeretlen problémánkat visszavezethetjük egy közismert NP teljes problémára, akkor az ismeretlen problémánkról is kiderült, hogy NP teljes. 

<big>'''Karp-redukció?''' </big>
Van egy olyan gépünk, ami kizárólag B problémát tudja megoldani. Nekünk viszont A problémánk van. Ekkor ha szerencsénk van, akkor fogunk találni egy olyan Karp-redukciót, hogy A<big>≺</big>B. Ennek persze vannak feltételei. Az A eldöntési probléma inputját át kell alakítani B eldöntési probléma inputjává, és meg is kell adni ezt a függvényt, nevezzük el ezt a függvényt f függvénynek. Feltétel, hogy f függvény polinom időben kiszámolható legyen, és ezt be is kell bizonyítani. Továbbá azt is be kell bizonyítani, hogy amennyiben a normális inputra A azt válaszolná, hogy IGEN, akkor az f(normális input)-ra a B szintén ugyanezt válaszolná (és ugyanezt be kell bizonyítani NEM válaszra is). Magyarul a B dolgot megoldó gépet megerőszakoljuk hogy A problémát is hajlandó legyen megoldani. 

Ebből következik néhány dolog. Például az, hogy B legalább olyan nehéz probléma, mint A. Ha például B NP-teljes, akkor A is az. Ha B NP-nehéz, akkor A is az. Ha B coNP-beli, akkor A is az. Ez miért van? Hát azért, mert polinom időben át lehet alakítani az A problémát B-vé. Ezt indirekten könnyen lehet bizonyítani. Indirekt tegyük fel, hogy annak ellenére hogy B probléma NP-teljes és létezik egy olyan Karp-redukció ami A problmémát átalakítja B-vé, szóval mindezek ellenére A probléma P-beli. Ekkor A problémát egy polinom idejű f függvénnyel simán átalakítjuk B problémává, erről szól ugye a Karp-redukció. Ezek után ha bármikor B problémát akarnánk megoldani, akkor az f-függvény fordítva végrehajtásával a B inputját átalakítjuk A inputjává, megoldjuk az A problémát polinom időben, és kész is. Ez ellentmondás mivel B-ről azt mondtuk hogy NP-teljes. A másik érdekesség, hogy ha például egy NP-teljes vagy NP-nehéz problémáról kiderülne hogy P-beli, akkor az összes NP-beliről kiderülne hogy P-beli, mivel az NP-nehéz definíciója az, hogy legalább olyan nehéz mint bármely tetszőleges NP-beli. 

Még egy fontos megjegyzés a Karp-redukcióhoz: ugye A problémát akarjuk megoldani, de csak B-t megoldó gépünk van. Az egyik gyakorlaton elhangzott, és fontos tudni, hogy a B-t megoldó gépet az A eldöntési probléma megoldásához csak EGYSZER használhatjuk. Azért mert a Karp-redukció az ilyen. 

<big>'''H-út? ''' </big>
todo 

<big>'''3 színnel színezhetőség problémája? ''' </big>
todo 
}}

<big>'''A feladat megoldása: ''' </big>
todo 

}}

Algoritmuselmélet - Vizsga, 2013.06.06.

2013-06-11T11:51:24Z

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

==2013.06.06. vizsga megoldásai==
===1. Feladat (Van megoldás) ===
Ebben a feladatban a mélységi bejárással kapcsolatos kérdésekre kell válaszolni.
* '''(a)''' Adja meg a keresztél definícióját!
* '''(b)''' A mélységi bejárás során hogyan lehet a mélységi és a befejezési számok alapján felismerni a keresztéleket? ''Vizsgán megjegyzést fűztek hozzá: irányított gráfokra kell gondolni.''
* '''(c)''' Bizonyítsa be, hogy irányítatlan gráf mélységi bejárásánál nincsenek keresztélek!
{{Rejtett
|mutatott=<big>'''Megoldás'''</big>
|szöveg=
'''a)''' 
Tekintsük a G irányított gráf egy mélységi bejárását és a kapott T mélységi feszítő erdőt. Ezen bejárás szerint G egy x → y éle keresztél, ha x és y nem leszármazottjai egymásnak.

'''b)''' 
msz - mélységi szám 
bsz - befejezési szám 
Ha <math> (msz[y] < msz[x]) </math> és <math>(bsz[y] > 0) </math>, akkor az x → y egy keresztél. 
[[Fájl:keresztel_1.png]] 
'''c)''' 
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. 
'''Másképpen mondva:''' Nem fejezhettük volna be y-t anélkül, hogy ne jártunk volna x-ben. 
[[Fájl:keresztel_2.PNG]] 
}}

===2. Feladat (Van megoldás)===
Milyen műveletek vannak a nyitott címzésű hash-elésnél? Hogyan kell megvalósítani a keresést, ha a nyitott címzésű hashelésnél kvadratikus maradék próbát használunk?

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

{{Rejtett
|mutatott=<big>'''Kiegészítések a feladat megértéséhez'''</big>
|szöveg=

'''Mi az a nyitott címzésű hash-elés?''' 
lásd: https://wiki.sch.bme.hu/Hash_t%C3%B6mb 

'''Mi az a kvadratikus maradék próba, nyitott címzésű hash-elésnél?''' 
todo 
}}
'''Nyitott címzésű hash-elés műveletei:''' 
Új elem beszúrása, elem keresése, elem törlése. 
A törlés speciális jelzéssel történik. 

'''Keresés megvalósítása nyitott címzésű hash-elés esetén kvadratikus maradék próbánál:''' 
A kvadratikus maradék próba egy álvéletlen próba, ezért másodlagos csomósodáshoz vezethet. 
Legyen M egy 4k + 3 alakú prímszám, ahol k egy pozitív egész. 
Ekkor a próbasorozat legyen 
<math> 0,1^2,(-1)^2, 2^2,(-2)^2,..,\left ( \frac{M-1}{2} \right )^{2}, -\left ( \frac{M-1}{2} \right )^{2} </math>

}}

===3. Feladat===
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!

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

{{Rejtett
|mutatott=<big>'''Kiegészítések a feladat megértéséhez'''</big>
|szöveg=

'''Mi az a Kruskal algoritmus?''' 
todo 
}}
'''UNIÓ-HOLVAN adatszerkezet definíciója: ''' 
todo 

'''Mikor és hogyan használjuk az UNIÓ és a HOLVAN műveleteket a Kruskal algoritmusban:''' 
todo 

}}

===4. Feladat===
Pista bácsi fel akar ugrálni egy n hosszú, fekete illetve fehér fokokból álló csigalépcsőn. Legfeljebb k fokot tud ugrani, de arra vigyáznia kell, hogy páros (>=2) sok foknyi ugrás után páratlan sokat és páratlan sok után mindig páros (>=2) sokat ugorjon. Adjon O(nk) lépésszámú algoritmust, amely megmondja, hogy fel tud-e úgy ugrálni a csigalépcső tetejére, hogy csak egyféle színű lépcsőfokot használ. (A lépcső fokai rendszertelenül vannak színezve, a színezést ismerjük.)
''Vizsgán megjegyzést fűztek hozzá: a talaj és a legteteje nem színes, csak a lépcsők; csak fölfele (előrefele) ugrál, visszafele nem. ''

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

todo

 

}}

===5. Feladat (Van megoldás)===
A hátizsák probléma órán tanult algoritmusát futtattuk egy konkrét inputon, melyben 3 tárgy szerepel. Mi lehetett ez a konkrét input, ha az alábbi táblázat keletkezett?

{| class="wikitable" border="5"
|-
!
! 0
! 1
! 2
! 3
! 4
! 5
! 6
! 7
|-
| 1
| 0
| 0
| 0
| 0
| 10
| 10
| 10
| 10
|-
| 2
| 0
| 0
| 5
| 5
| 10
| 10
| 15
| 15
|-
| 3
| 0
| 0
| 5
| 5
| 13
| 13
| 18
| 18
|}

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

Az egyszerűség kedvéért a súly legyen kg, az érték pedig €.

#Az első sor alapján az 1-es csomag értéke €10, súlya 4kg.
#A második sor alapján a 2-es csomag értéke €5, súlya 2kg.
#A 3. lépésben 2 lehetőségünk van, a 3. csomag értéke vagy 13-5=€8, vagy 13-0=€13.
##€8 nem lehet, mert akkor a súlya 2kg lenne, de akkor a [2,3] cellába 8 lenne, nem 5.
##Így csak a €13 jöhet szóba, súlya pedig 4kg, ami jó megoldás lesz.

{{Rejtett
|mutatott=''Avagy kicsit gépiesebb megoldás:''
|szöveg=
 
Jelölje <math> T[s,cs]</math> a táblázat <math>[s,cs]</math> celláját, továbbá <math> V_3</math> a 3. csomag értékét, <math> S_3</math> pedig a súlyát. 
Tudjuk, hogy <math> T[s,cs]=max\left \{ T[s,cs-1];V_i+T[s-S_i,cs-1] \right \}</math>, ami ebben az esetben: 
<math> T[4,3]=max\left \{ T[4,2];V_3+T[4-S_3,2] \right \} \rightarrow 13=max\left \{ 10;V_3+T[4-S_3,2] \right \}</math>, amiből következik, hogy: 
<math> 13=V_3+T[4-S_3,2] \rightarrow V_3 = 13-T[4-S_3,2]\Rightarrow\Rightarrow S_3=4, V_3=13</math> (Átgondolható, hogy a 3. csomag súlya nem lehet 1,2 vagy 3kg).
}}
Tehát végeredményben a megoldás:
*1-es csomag (€10, 4kg)
*2-es csomag (€5, 2kg)
*3-as csomag (€13, 4kg)

}}

===6. Feladat (Van megoldás)===
Egy irányítatlan, élsúlyozott gráf az alábbi éllistával adott (zárójelben az élsúlyok):

<math>A:B(1), D(3), E(2); B:A(1), C(3), D(y); D:A(3), C(y), E(x); E:A(2), B(1), D(x).</math>
* '''(a)''' Mi lehet x és y értéke, ha tudjuk, hogy az élsúlyok egész számok, és azt is tudjuk, hogy a B csúcsból indított Prim algoritmus az alábbi sorrendben vette be az értékeket: BE, ED, BA, BC. ''Vizsgán megjegyzést fűztek hozzá: az élsúlyok pozitív egész számok, a pozitív szót kifelejtették véletlenül.''
* '''(b)''' Mely éleket és milyen sorrendben választja ki a Kruskal algoritmus? (Ha több megoldás is van, akkor az összeset adja meg!)
{{Rejtett
|mutatott=<big>'''Megoldás'''</big>
|szöveg=
[[File:2013_06_06_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 fához hozzáadjuk a BE élt.
# Most az ED élt választottuk. Ez alapján x értéke csak 1 lehet, így <math>x = 1</math>. (Feladatból kihagyták, hogy pozitív egészekről van szó, amúgy <math>x \le 1</math> lehetne.)
# 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>.

'''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.

1 súlyú - AB, BE, ED

2 súlyú - AE

3 súlyú - BC, AD, EC (és DC, ha <math>y = 3</math>)

Az összes megoldás:

#Az 1 súlyú éleket <math>3! = 6</math> féleképpen veheti fel az algoritmus (nem lehet belőlük kört csinálni, így itt nincsen para).
#Utána megpróbálná felvenni az AE élt, de azzal egy kört kapna, így nem veszi fel. Az AD éllel szintén így járna (~ezeket kéne pirosra színezni, ha olyan lenne a feladat).
#Maradtak a BC, EC és DC oldalak.
##Ha <math>y = 3</math>, akkor ezeket szintén 6 féleképpen veheti fel, tehát összesen 36 féleképpen futhat az algoritmus.
##Ha <math>y \ge 3</math>, akkor a DC oldal kiesik, a maradék 2 élt 2 féleképpen veheti fel, így 12 féleképpen futhat az algoritmus.}}

===7. Feladat (Van megoldás)===
Létezik-e olyan X eldöntési probléma, amire X<big>∉</big>NP és X<big>≺</big>SAT egyszerre fennáll?

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

{{Rejtett
|mutatott=<big>'''Kiegészítések a feladat megértéséhez'''</big>
|szöveg=
<big>'''Eldöntési probléma osztályok? ''' </big>

 
[[File:bonyolultsag_elmelet.JPG|390px]]
 

A '''problémák'''nak lehet több típusú több bemenete, és több típusú több kimenete. Ezeket átfogalmazzuk olyanra, hogy a kimenete egyetlen bit legyen (IGEN / NEM), mert ezen algoritmusok felhasználásával is teljesen jól lehet dolgozni, ugyanakkor könnyebb őket nehézség / bonyolultság szerint osztályozni. Az ilyen 1 bites kimenetű problémákat nevezzük '''eldöntési problémák'''nak. 

Az eldöntési problémákat nehézség / bonyolultság szerint osztályokba soroljuk, ezen osztályok között olyan kapcsolatok vannak mint a halmazoknál; ez a fenti rajzon látszik. 

A '''P osztály'''ba olyan problémák tartoznak, amelyekre ismert olyan algoritmus, ami a bemenet polinomjával megadott idő alatt lefut. Vagyis ha a bemenet '''n''', akkor az algoritmusra azt mondjuk, hogy nagy_ordó(valami), ahol a valami '''n''' egy polinomja, például n négyzet, n köb, három n négyzet meg négy meg nyolc n köb, és ilyesmik. 

Az '''NP osztály'''ba olyan problémák tartoznak, amelyekre nem feltétlenül ismert polinom idejű (P-beli) algoritmus, de igen válasz esetén létezik hatékony tanúsítvány. Vagyis, adott egy nagy csomó bemenet és van egy kérdés. P-idő alatt nem tudjuk megmondani a választ, de ha valaki megsúgja hogy a válasz IGEN, akkor P-időben meg tudjuk mondani, hogy ez hülyeség vagy nem hülyeség. Ha azt súgják meg hogy NEM, akkor fogalmunk sincs, P-időben nem tudjuk eldönteni hogy hülyeség-e vagy sem. (''Ha így lenne, vagyis igen és nem válasz esetén is P-időben ellenőrizni tudnánk a válasz helyességét, akkor az egész probléma P-beli lenne, hiszen megsúgjuk saját magunknak hogy NEM és ha helyes akkor NEM egyébként igen. Persze ha az IGEN-ről P-időben kiderül hogy hülyeség attól még lehet hogy IGEN, csak éppen nem az a konkrét ami meg lett súgva, hanem egy másik.'') 

A '''coNP osztály''' lényegében ugyanaz mint az NP osztály, csak NEM válaszra. Vagyis (jelenleg) nem ismerünk rá P-beli algoritmust, de ha a válasz NEM, akkor P-időben (hatékonyan) ellenőrizni tudjuk, hogy ez-e a jó válasz vagy sem. Szintén, IGEN válasz esetén semmit sem tudunk mondani P-időben, a fenti okok miatt (ami a zárójelben van). 

Az '''NP nehéz''' osztályba tartozó eldöntési problémák közül bármelyik legalább olyan nehéz, mint bármelyik másik NP-beli eldöntési probléma. Itt jön képbe a Karp-redukció fogalma. Jó dolog sok NP nehéz problémát ismerni, mert akkor ha találunk egy problémát, akkor ha találunk olyan Karp-redukciót, ami azt mutatja, hogy ez a probléma visszavezethető egy közismert NP nehéz problémára, akkor a mi ismeretlen problémánk is NP nehéz lesz. Ez azért van, mert a Karp-redukció tranzitív művelet, továbbá a Karp-redukcónál használt f függvény P-beli, amit kétszer egymás után alkalmazva is még mindig P-beli lesz ez a dolog (az inputok átalakítása). 

Az '''NP teljes''' problémák azok, amik NP nehezek és NP-beliek is egyszerre. A fenti dolog ide is érvényes, vagyis jó dolog ha sok nevezetes NP teljes problémát ismerünk, mert ha egy ismeretlen problémához találunk egy olyan Karp-redukciót, ami alapján az ismeretlen problémánkat visszavezethetjük egy közismert NP teljes problémára, akkor az ismeretlen problémánkról is kiderült, hogy NP teljes. 

<big>'''Karp-redukció?''' </big>
Van egy olyan gépünk, ami kizárólag B problémát tudja megoldani. Nekünk viszont A problémánk van. Ekkor ha szerencsénk van, akkor fogunk találni egy olyan Karp-redukciót, hogy A<big>≺</big>B. Ennek persze vannak feltételei. Az A eldöntési probléma inputját át kell alakítani B eldöntési probléma inputjává, és meg is kell adni ezt a függvényt, nevezzük el ezt a függvényt f függvénynek. Feltétel, hogy f függvény polinom időben kiszámolható legyen, és ezt be is kell bizonyítani. Továbbá azt is be kell bizonyítani, hogy amennyiben a normális inputra A azt válaszolná, hogy IGEN, akkor az f(normális input)-ra a B szintén ugyanezt válaszolná (és ugyanezt be kell bizonyítani NEM válaszra is). Magyarul a B dolgot megoldó gépet megerőszakoljuk hogy A problémát is hajlandó legyen megoldani. 

Ebből következik néhány dolog. Például az, hogy B legalább olyan nehéz probléma, mint A. Ha például B NP-teljes, akkor A is az. Ha B NP-nehéz, akkor A is az. Ha B coNP-beli, akkor A is az. Ez miért van? Hát azért, mert polinom időben át lehet alakítani az A problémát B-vé. Ezt indirekten könnyen lehet bizonyítani. Indirekt tegyük fel, hogy annak ellenére hogy B probléma NP-teljes és létezik egy olyan Karp-redukció ami A problmémát átalakítja B-vé, szóval mindezek ellenére A probléma P-beli. Ekkor A problémát egy polinom idejű f függvénnyel simán átalakítjuk B problémává, erről szól ugye a Karp-redukció. Ezek után ha bármikor B problémát akarnánk megoldani, akkor az f-függvény fordítva végrehajtásával a B inputját átalakítjuk A inputjává, megoldjuk az A problémát polinom időben, és kész is. Ez ellentmondás mivel B-ről azt mondtuk hogy NP-teljes. A másik érdekesség, hogy ha például egy NP-teljes vagy NP-nehéz problémáról kiderülne hogy P-beli, akkor az összes NP-beliről kiderülne hogy P-beli, mivel az NP-nehéz definíciója az, hogy legalább olyan nehéz mint bármely tetszőleges NP-beli. 

Még egy fontos megjegyzés a Karp-redukcióhoz: ugye A problémát akarjuk megoldani, de csak B-t megoldó gépünk van. Az egyik gyakorlaton elhangzott, és fontos tudni, hogy a B-t megoldó gépet az A eldöntési probléma megoldásához csak EGYSZER használhatjuk. Azért mert a Karp-redukció az ilyen. 

<big>'''SAT probléma? ''' </big>
A SAT probléma NP-teljes. 
forrás:http://www.cs.bme.hu/algel/12elo-2012.pdf 
}}

<big>'''A feladat megoldása: ''' </big>
Tétel: Ha X ≺ Y és Y ∈ NP,akkor X ∈ NP 
Tétel: A SAT probléma NP teljes, tehát része NP-nek. 
A fentiek alapján, mivel X<big>∉</big>NP, a kérdéses X probléma nem létezhet.

}}

===8. Feladat===
P-ben van vagy NP-teljes az alábbi eldöntési probléma: 
*'''Input:''' irányítatlan G gráf 
*'''Kérdés:''' Igaz-e, hogy G-ben vagy van Hamilton-út vagy G 3 színnel színezhető? 

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

{{Rejtett
|mutatott=<big>'''Kiegészítések a feladat megértéséhez'''</big>
|szöveg=
<big>'''Eldöntési probléma osztályok? ''' </big>

 
[[File:bonyolultsag_elmelet.JPG|390px]]
 

A '''problémák'''nak lehet több típusú több bemenete, és több típusú több kimenete. Ezeket átfogalmazzuk olyanra, hogy a kimenete egyetlen bit legyen (IGEN / NEM), mert ezen algoritmusok felhasználásával is teljesen jól lehet dolgozni, ugyanakkor könnyebb őket nehézség / bonyolultság szerint osztályozni. Az ilyen 1 bites kimenetű problémákat nevezzük '''eldöntési problémák'''nak. 

Az eldöntési problémákat nehézség / bonyolultság szerint osztályokba soroljuk, ezen osztályok között olyan kapcsolatok vannak mint a halmazoknál; ez a fenti rajzon látszik. 

A '''P osztály'''ba olyan problémák tartoznak, amelyekre ismert olyan algoritmus, ami a bemenet polinomjával megadott idő alatt lefut. Vagyis ha a bemenet '''n''', akkor az algoritmusra azt mondjuk, hogy nagy_ordó(valami), ahol a valami '''n''' egy polinomja, például n négyzet, n köb, három n négyzet meg négy meg nyolc n köb, és ilyesmik. 

Az '''NP osztály'''ba olyan problémák tartoznak, amelyekre (jelenleg) nem ismert polinom idejű (P-beli) algoritmus, de igen válasz esetén létezik hatékony tanúsítvány. Vagyis, adott egy nagy csomó bemenet és van egy kérdés. P-idő alatt nem tudjuk megmondani a választ, de ha valaki megsúgja hogy a válasz IGEN, akkor P-időben meg tudjuk mondani, hogy ez hülyeség vagy nem hülyeség. Ha azt súgják meg hogy NEM, akkor fogalmunk sincs, P-időben nem tudjuk eldönteni hogy hülyeség-e vagy sem. (''Ha így lenne, vagyis igen és nem válasz esetén is P-időben ellenőrizni tudnánk a válasz helyességét, akkor az egész probléma P-beli lenne, hiszen megsúgjuk saját magunknak hogy NEM és ha helyes akkor NEM egyébként igen. Persze ha az IGEN-ről P-időben kiderül hogy hülyeség attól még lehet hogy IGEN, csak éppen nem az a konkrét ami meg lett súgva, hanem egy másik.'') 

A '''coNP osztály''' lényegében ugyanaz mint az NP osztály, csak NEM válaszra. Vagyis (jelenleg) nem ismerünk rá P-beli algoritmust, de ha a válasz NEM, akkor P-időben (hatékonyan) ellenőrizni tudjuk, hogy ez-e a jó válasz vagy sem. Szintén, IGEN válasz esetén semmit sem tudunk mondani P-időben, a fenti okok miatt (ami a zárójelben van). 

Az '''NP nehéz''' osztályba tartozó eldöntési problémák közül bármelyik legalább olyan nehéz, mint bármelyik másik NP-beli eldöntési probléma. Itt jön képbe a Karp-redukció fogalma. Jó dolog sok NP nehéz problémát ismerni, mert akkor ha találunk egy problémát, akkor ha találunk olyan Karp-redukciót, ami azt mutatja, hogy ez a probléma visszavezethető egy közismert NP nehéz problémára, akkor a mi ismeretlen problémánk is NP nehéz lesz. Ez azért van, mert a Karp-redukció tranzitív művelet, továbbá a Karp-redukcónál használt f függvény P-beli, amit kétszer egymás után alkalmazva is még mindig P-beli lesz ez a dolog (az inputok átalakítása). 

Az '''NP teljes''' problémák azok, amik NP nehezek és NP-beliek is egyszerre. A fenti dolog ide is érvényes, vagyis jó dolog ha sok nevezetes NP teljes problémát ismerünk, mert ha egy ismeretlen problémához találunk egy olyan Karp-redukciót, ami alapján az ismeretlen problémánkat visszavezethetjük egy közismert NP teljes problémára, akkor az ismeretlen problémánkról is kiderült, hogy NP teljes. 

<big>'''Karp-redukció?''' </big>
Van egy olyan gépünk, ami kizárólag B problémát tudja megoldani. Nekünk viszont A problémánk van. Ekkor ha szerencsénk van, akkor fogunk találni egy olyan Karp-redukciót, hogy A<big>≺</big>B. Ennek persze vannak feltételei. Az A eldöntési probléma inputját át kell alakítani B eldöntési probléma inputjává, és meg is kell adni ezt a függvényt, nevezzük el ezt a függvényt f függvénynek. Feltétel, hogy f függvény polinom időben kiszámolható legyen, és ezt be is kell bizonyítani. Továbbá azt is be kell bizonyítani, hogy amennyiben a normális inputra A azt válaszolná, hogy IGEN, akkor az f(normális input)-ra a B szintén ugyanezt válaszolná (és ugyanezt be kell bizonyítani NEM válaszra is). Magyarul a B dolgot megoldó gépet megerőszakoljuk hogy A problémát is hajlandó legyen megoldani. 

Ebből következik néhány dolog. Például az, hogy B legalább olyan nehéz probléma, mint A. Ha például B NP-teljes, akkor A is az. Ha B NP-nehéz, akkor A is az. Ha B coNP-beli, akkor A is az. Ez miért van? Hát azért, mert polinom időben át lehet alakítani az A problémát B-vé. Ezt indirekten könnyen lehet bizonyítani. Indirekt tegyük fel, hogy annak ellenére hogy B probléma NP-teljes és létezik egy olyan Karp-redukció ami A problmémát átalakítja B-vé, szóval mindezek ellenére A probléma P-beli. Ekkor A problémát egy polinom idejű f függvénnyel simán átalakítjuk B problémává, erről szól ugye a Karp-redukció. Ezek után ha bármikor B problémát akarnánk megoldani, akkor az f-függvény fordítva végrehajtásával a B inputját átalakítjuk A inputjává, megoldjuk az A problémát polinom időben, és kész is. Ez ellentmondás mivel B-ről azt mondtuk hogy NP-teljes. A másik érdekesség, hogy ha például egy NP-teljes vagy NP-nehéz problémáról kiderülne hogy P-beli, akkor az összes NP-beliről kiderülne hogy P-beli, mivel az NP-nehéz definíciója az, hogy legalább olyan nehéz mint bármely tetszőleges NP-beli. 

Még egy fontos megjegyzés a Karp-redukcióhoz: ugye A problémát akarjuk megoldani, de csak B-t megoldó gépünk van. Az egyik gyakorlaton elhangzott, és fontos tudni, hogy a B-t megoldó gépet az A eldöntési probléma megoldásához csak EGYSZER használhatjuk. Azért mert a Karp-redukció az ilyen. 

<big>'''H-út? ''' </big>
todo 

<big>'''3 színnel színezhetőség problémája? ''' </big>
todo 
}}

<big>'''A feladat megoldása: ''' </big>
todo 

}}

Algoritmuselmélet - Vizsga, 2013.06.06.

2013-06-07T16:55:04Z

Subdiaz: /* 8. Feladat */

==2013.06.06. vizsga megoldásai==
===1. Feladat (Van megoldás) ===
Ebben a feladatban a mélységi bejárással kapcsolatos kérdésekre kell válaszolni.
* '''(a)''' Adja meg a keresztél definícióját!
* '''(b)''' A mélységi bejárás során hogyan lehet a mélységi és a befejezési számok alapján felismerni a keresztéleket? ''Vizsgán megjegyzést fűztek hozzá: irányított gráfokra kell gondolni.''
* '''(c)''' Bizonyítsa be, hogy irányítatlan gráf mélységi bejárásánál nincsenek keresztélek!
{{Rejtett
|mutatott=<big>'''Megoldás'''</big>
|szöveg=
'''(a)''' 
Tekintsük a G irányított gráf egy mélységi bejárását és a kapott T mélységi feszítő erdőt. Ezen bejárás szerint G egy x → y éle keresztél, ha x és y nem leszármazottjai egymásnak.

'''(b)''' 
msz - mélységi szám 
bsz - befejezési szám 
Ha <math> (msz[y] < msz[x]) </math> és <math>(bsz[y] > 0) </math>, akkor az x → y egy keresztél. 
[[Fájl:keresztel_1.png]] 
'''(c)''' 
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.
Másképpen mondva: Nem fejezhettük volna be y-t anélkül, hogy ne jártunk volna x-ben. 
[[Fájl:keresztel_2.PNG]] 
}}

===2. Feladat===
Milyen műveletek vannak a nyitott címzésű hash-elésnél? Hogyan kell megvalósítani a keresést, ha a nyitott címzésű hashelésnél kvadratikus maradék próbát használunk?

{{Rejtett
|mutatott=<big>'''Megoldás'''</big>
|szöveg=
'''Nyitott címzésű hash-elés műveletei:''' 
todo 

'''(''Nem kérdezték, csak kieg.'') Mi az a nyitott címzésű hash-elés?''' 
todo 

'''(''Nem kérdezték, csak kieg.'') Mi az a kvadratikus maradék próba, nyitott címzésű hash-elésnél?''' 
todo 

'''keresés megvalósítása nyitott címzésű hash-elés esetén kvadratikus maradék próbánál:''' 
todo 

}}

===3. Feladat===
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!

{{Rejtett
|mutatott=<big>'''Megoldás'''</big>
|szöveg=
'''UNIÓ-HOLVAN adatszerkezet definíciója: ''' 
todo 

'''(''Nem kérdezték, csak kieg.'') Mi az a Kruskal algoritmus?''' 
todo 

'''Mikor és hogyan használjuk az UNIÓ és a HOLVAN műveleteket a Kruskal algoritmusban:''' 
todo 

}}

===4. Feladat===
Pista bácsi fel akar ugrálni egy n hosszú, fekete illetve fehér fokokból álló csigalépcsőn. Legfeljebb k fokot tud ugrani, de arra vigyáznia kell, hogy páros (>=2) sok foknyi ugrás után páratlan sokat és páratlan sok után mindig páros (>=2) sokat ugorjon. Adjon O(nk) lépésszámú algoritmust, amely megmondja, hogy fel tud-e úgy ugrálni a csigalépcső tetejére, hogy csak egyféle színű lépcsőfokot használ. (A lépcső fokai rendszertelenül vannak színezve, a színezést ismerjük.)
''Vizsgán megjegyzést fűztek hozzá: a talaj és a legteteje nem színes, csak a lépcsők; csak fölfele (előrefele) ugrál, visszafele nem. ''

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

todo

 

}}

===5. Feladat (Van megoldás)===
A hátizsák probléma órán tanult algoritmusát futtattuk egy konkrét inputon, melyben 3 tárgy szerepel. Mi lehetett ez a konkrét input, ha az alábbi táblázat keletkezett?

{| class="wikitable" border="5"
|-
!
! 0
! 1
! 2
! 3
! 4
! 5
! 6
! 7
|-
| 1
| 0
| 0
| 0
| 0
| 10
| 10
| 10
| 10
|-
| 2
| 0
| 0
| 5
| 5
| 10
| 10
| 15
| 15
|-
| 3
| 0
| 0
| 5
| 5
| 13
| 13
| 18
| 18
|}

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

Az egyszerűség kedvéért a súly legyen kg, az érték pedig €.

#Az első sor alapján az 1-es csomag értéke €10, súlya 4kg.
#A második sor alapján a 2-es csomag értéke €5, súlya 2kg.
#A 3. sornál kicsit rafkósnak kell lenni. Leírhatnám egyből a megoldást, de talán több értelme van, ha a logikai zsákutcákat is leírom.
##Először gondolhatnánk arra, hogy a [4,3]-as cella 10+3 formában áll elő, így a 3-as csomag értéke €3. Viszont így a súlyának 0kg-nak kéne lennie, ami nyílván fatal error.
##Második gondolatunk az lehetne, hogy akkor 5+8 formában áll elő, így a 3-as csomag értéke €8. Súlya ekkor 2kg kellene legyen, viszont akkor a [2,3]-as cellába 8-nak, és nem 5-nek kéne szerepelnie, tehát ez se jó megoldás.
##Harmadik ötletnek nagyon más nem jöhet szóba, hogy akkor a 3-as csomag értéke €13, súlya pedig 4kg. És ha leellenőrizzük, látszik, hogy ez lesz a jó megoldás.

Tehát végeredményben a megoldás:
*1-es csomag (€10, 4kg)
*2-es csomag (€5, 2kg)
*3-as csomag (€13, 4kg)

}}

===6. Feladat (Van megoldás)===
Egy irányítatlan, élsúlyozott gráf az alábbi éllistával adott (zárójelben az élsúlyok):

<math>A:B(1), D(3), E(2); B:A(1), C(3), D(y); D:A(3), C(y), E(x); E:A(2), B(1), D(x).</math>
* '''(a)''' Mi lehet x és y értéke, ha tudjuk, hogy az élsúlyok egész számok, és azt is tudjuk, hogy a B csúcsból indított Prim algoritmus az alábbi sorrendben vette be az értékeket: BE, ED, BA, BC. ''Vizsgán megjegyzést fűztek hozzá: az élsúlyok pozitív egész számok, a pozitív szót kifelejtették véletlenül.''
* '''(b)''' Mely éleket és milyen sorrendben választja ki a Kruskal algoritmus? (Ha több megoldás is van, akkor az összeset adja meg!)
{{Rejtett
|mutatott=<big>'''Megoldás'''</big>
|szöveg=
[[File:2013_06_06_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 fához hozzáadjuk a BE élt.
# Most az ED élt választottuk. Ez alapján x értéke csak 1 lehet, így <math>x = 1</math>. (Feladatból kihagyták, hogy pozitív egészekről van szó, amúgy <math>x \le 1</math> lehetne.)
# 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>.

'''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.

1 súlyú - AB, BE, ED

2 súlyú - AE

3 súlyú - BC, AD, EC (és DC, ha <math>y = 3</math>)

Az összes megoldás:

#Az 1 súlyú éleket <math>3! = 6</math> féleképpen veheti fel az algoritmus (nem lehet belőlük kört csinálni, így itt nincsen para).
#Utána megpróbálná felvenni az AE élt, de azzal egy kört kapna, így nem veszi fel. Az AD éllel szintén így járna (~ezeket kéne pirosra színezni, ha olyan lenne a feladat).
#Maradtak a BC, EC és DC oldalak.
##Ha <math>y = 3</math>, akkor ezeket szintén 6 féleképpen veheti fel, tehát összesen 36 féleképpen futhat az algoritmus.
##Ha <math>y \ge 3</math>, akkor a DC oldal kiesik, a maradék 2 élt 2 féleképpen veheti fel, így 12 féleképpen futhat az algoritmus.}}

===7. Feladat===
Létezik-e olyan X eldöntési probléma, amire X<big>∉</big>NP és X<big>≺</big>SAT egyszerre fennáll?

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

<big>'''(''Nem kérdezték, csak kieg.'') Eldöntési probléma osztályok? ''' </big>

 
[[File:bonyolultsag_elmelet.JPG|390px]]
 

A '''problémák'''nak lehet több típusú több bemenete, és több típusú több kimenete. Ezeket átfogalmazzuk olyanra, hogy a kimenete egyetlen bit legyen (IGEN / NEM), mert ezen algoritmusok felhasználásával is teljesen jól lehet dolgozni, ugyanakkor könnyebb őket nehézség / bonyolultság szerint osztályozni. Az ilyen 1 bites kimenetű problémákat nevezzük '''eldöntési problémák'''nak. 

Az eldöntési problémákat nehézség / bonyolultság szerint osztályokba soroljuk, ezen osztályok között olyan kapcsolatok vannak mint a halmazoknál; ez a fenti rajzon látszik. 

A '''P osztály'''ba olyan problémák tartoznak, amelyekre ismert olyan algoritmus, ami a bemenet polinomjával megadott idő alatt lefut. Vagyis ha a bemenet '''n''', akkor az algoritmusra azt mondjuk, hogy nagy_ordó(valami), ahol a valami '''n''' egy polinomja, például n négyzet, n köb, három n négyzet meg négy meg nyolc n köb, és ilyesmik. 

Az '''NP osztály'''ba olyan problémák tartoznak, amelyekre (jelenleg) nem ismert polinom idejű (P-beli) algoritmus, de igen válasz esetén létezik hatékony tanúsítvány. Vagyis, adott egy nagy csomó bemenet és van egy kérdés. P-idő alatt nem tudjuk megmondani a választ, de ha valaki megsúgja hogy a válasz IGEN, akkor P-időben meg tudjuk mondani, hogy ez hülyeség vagy nem hülyeség. Ha azt súgják meg hogy NEM, akkor fogalmunk sincs, P-időben nem tudjuk eldönteni hogy hülyeség-e vagy sem. (''Ha így lenne, vagyis igen és nem válasz esetén is P-időben ellenőrizni tudnánk a válasz helyességét, akkor az egész probléma P-beli lenne, hiszen megsúgjuk saját magunknak hogy NEM és ha helyes akkor NEM egyébként igen. Persze ha az IGEN-ről P-időben kiderül hogy hülyeség attól még lehet hogy IGEN, csak éppen nem az a konkrét ami meg lett súgva, hanem egy másik.'') 

A '''coNP osztály''' lényegében ugyanaz mint az NP osztály, csak NEM válaszra. Vagyis (jelenleg) nem ismerünk rá P-beli algoritmust, de ha a válasz NEM, akkor P-időben (hatékonyan) ellenőrizni tudjuk, hogy ez-e a jó válasz vagy sem. Szintén, IGEN válasz esetén semmit sem tudunk mondani P-időben, a fenti okok miatt (ami a zárójelben van). 

Az '''NP nehéz''' osztályba tartozó eldöntési problémák közül bármelyik legalább olyan nehéz, mint bármelyik másik NP-beli eldöntési probléma. Itt jön képbe a Karp-redukció fogalma. Jó dolog sok NP nehéz problémát ismerni, mert akkor ha találunk egy problémát, akkor ha találunk olyan Karp-redukciót, ami azt mutatja, hogy ez a probléma visszavezethető egy közismert NP nehéz problémára, akkor a mi ismeretlen problémánk is NP nehéz lesz. Ez azért van, mert a Karp-redukció tranzitív művelet, továbbá a Karp-redukcónál használt f függvény P-beli, amit kétszer egymás után alkalmazva is még mindig P-beli lesz ez a dolog (az inputok átalakítása). 

Az '''NP teljes''' problémák azok, amik NP nehezek és NP-beliek is egyszerre. A fenti dolog ide is érvényes, vagyis jó dolog ha sok nevezetes NP teljes problémát ismerünk, mert ha egy ismeretlen problémához találunk egy olyan Karp-redukciót, ami alapján az ismeretlen problémánkat visszavezethetjük egy közismert NP teljes problémára, akkor az ismeretlen problémánkról is kiderült, hogy NP teljes. 

<big>'''(''Nem kérdezték, csak kieg.'') Karp-redukció?''' </big>
Van egy olyan gépünk, ami kizárólag B problémát tudja megoldani. Nekünk viszont A problémánk van. Ekkor ha szerencsénk van, akkor fogunk találni egy olyan Karp-redukciót, hogy A<big>≺</big>B. Ennek persze vannak feltételei. Az A eldöntési probléma inputját át kell alakítani B eldöntési probléma inputjává, és meg is kell adni ezt a függvényt, nevezzük el ezt a függvényt f függvénynek. Feltétel, hogy f függvény polinom időben kiszámolható legyen, és ezt be is kell bizonyítani. Továbbá azt is be kell bizonyítani, hogy amennyiben a normális inputra A azt válaszolná, hogy IGEN, akkor az f(normális input)-ra a B szintén ugyanezt válaszolná (és ugyanezt be kell bizonyítani NEM válaszra is). Magyarul a B dolgot megoldó gépet megerőszakoljuk hogy A problémát is hajlandó legyen megoldani. 

Ebből következik néhány dolog. Például az, hogy B legalább olyan nehéz probléma, mint A. Ha például B NP-teljes, akkor A is az. Ha B NP-nehéz, akkor A is az. Ha B coNP-beli, akkor A is az. Ez miért van? Hát azért, mert polinom időben át lehet alakítani az A problémát B-vé. Ezt indirekten könnyen lehet bizonyítani. Indirekt tegyük fel, hogy annak ellenére hogy B probléma NP-teljes és létezik egy olyan Karp-redukció ami A problmémát átalakítja B-vé, szóval mindezek ellenére A probléma P-beli. Ekkor A problémát egy polinom idejű f függvénnyel simán átalakítjuk B problémává, erről szól ugye a Karp-redukció. Ezek után ha bármikor B problémát akarnánk megoldani, akkor az f-függvény fordítva végrehajtásával a B inputját átalakítjuk A inputjává, megoldjuk az A problémát polinom időben, és kész is. Ez ellentmondás mivel B-ről azt mondtuk hogy NP-teljes. A másik érdekesség, hogy ha például egy NP-teljes vagy NP-nehéz problémáról kiderülne hogy P-beli, akkor az összes NP-beliről kiderülne hogy P-beli, mivel az NP-nehéz definíciója az, hogy legalább olyan nehéz mint bármely tetszőleges NP-beli. 

Még egy fontos megjegyzés a Karp-redukcióhoz: ugye A problémát akarjuk megoldani, de csak B-t megoldó gépünk van. Az egyik gyakorlaton elhangzott, és fontos tudni, hogy a B-t megoldó gépet az A eldöntési probléma megoldásához csak EGYSZER használhatjuk. Azért mert a Karp-redukció az ilyen. 

<big>'''(''Nem kérdezték, csak kieg.'') SAT probléma? ''' </big>
todo 

<big>'''A feladat megoldása: ''' </big>
todo 

}}

===8. Feladat===
P-ben van vagy NP-teljes az alábbi eldöntési probléma: 
*'''Input:''' irányítatlan G gráf 
*'''Kérdés:''' Igaz-e, hogy G-ben vagy van Hamilton-út vagy G 3 színnel színezhető? 

 

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

<big>'''(''Nem kérdezték, csak kieg.'') Eldöntési probléma osztályok? ''' </big>

 
[[File:bonyolultsag_elmelet.JPG|390px]]
 

A '''problémák'''nak lehet több típusú több bemenete, és több típusú több kimenete. Ezeket átfogalmazzuk olyanra, hogy a kimenete egyetlen bit legyen (IGEN / NEM), mert ezen algoritmusok felhasználásával is teljesen jól lehet dolgozni, ugyanakkor könnyebb őket nehézség / bonyolultság szerint osztályozni. Az ilyen 1 bites kimenetű problémákat nevezzük '''eldöntési problémák'''nak. 

Az eldöntési problémákat nehézség / bonyolultság szerint osztályokba soroljuk, ezen osztályok között olyan kapcsolatok vannak mint a halmazoknál; ez a fenti rajzon látszik. 

A '''P osztály'''ba olyan problémák tartoznak, amelyekre ismert olyan algoritmus, ami a bemenet polinomjával megadott idő alatt lefut. Vagyis ha a bemenet '''n''', akkor az algoritmusra azt mondjuk, hogy nagy_ordó(valami), ahol a valami '''n''' egy polinomja, például n négyzet, n köb, három n négyzet meg négy meg nyolc n köb, és ilyesmik. 

Az '''NP osztály'''ba olyan problémák tartoznak, amelyekre (jelenleg) nem ismert polinom idejű (P-beli) algoritmus, de igen válasz esetén létezik hatékony tanúsítvány. Vagyis, adott egy nagy csomó bemenet és van egy kérdés. P-idő alatt nem tudjuk megmondani a választ, de ha valaki megsúgja hogy a válasz IGEN, akkor P-időben meg tudjuk mondani, hogy ez hülyeség vagy nem hülyeség. Ha azt súgják meg hogy NEM, akkor fogalmunk sincs, P-időben nem tudjuk eldönteni hogy hülyeség-e vagy sem. (''Ha így lenne, vagyis igen és nem válasz esetén is P-időben ellenőrizni tudnánk a válasz helyességét, akkor az egész probléma P-beli lenne, hiszen megsúgjuk saját magunknak hogy NEM és ha helyes akkor NEM egyébként igen. Persze ha az IGEN-ről P-időben kiderül hogy hülyeség attól még lehet hogy IGEN, csak éppen nem az a konkrét ami meg lett súgva, hanem egy másik.'') 

A '''coNP osztály''' lényegében ugyanaz mint az NP osztály, csak NEM válaszra. Vagyis (jelenleg) nem ismerünk rá P-beli algoritmust, de ha a válasz NEM, akkor P-időben (hatékonyan) ellenőrizni tudjuk, hogy ez-e a jó válasz vagy sem. Szintén, IGEN válasz esetén semmit sem tudunk mondani P-időben, a fenti okok miatt (ami a zárójelben van). 

Az '''NP nehéz''' osztályba tartozó eldöntési problémák közül bármelyik legalább olyan nehéz, mint bármelyik másik NP-beli eldöntési probléma. Itt jön képbe a Karp-redukció fogalma. Jó dolog sok NP nehéz problémát ismerni, mert akkor ha találunk egy problémát, akkor ha találunk olyan Karp-redukciót, ami azt mutatja, hogy ez a probléma visszavezethető egy közismert NP nehéz problémára, akkor a mi ismeretlen problémánk is NP nehéz lesz. Ez azért van, mert a Karp-redukció tranzitív művelet, továbbá a Karp-redukcónál használt f függvény P-beli, amit kétszer egymás után alkalmazva is még mindig P-beli lesz ez a dolog (az inputok átalakítása). 

Az '''NP teljes''' problémák azok, amik NP nehezek és NP-beliek is egyszerre. A fenti dolog ide is érvényes, vagyis jó dolog ha sok nevezetes NP teljes problémát ismerünk, mert ha egy ismeretlen problémához találunk egy olyan Karp-redukciót, ami alapján az ismeretlen problémánkat visszavezethetjük egy közismert NP teljes problémára, akkor az ismeretlen problémánkról is kiderült, hogy NP teljes. 

<big>'''(''Nem kérdezték, csak kieg.'') Karp-redukció?''' </big>
Van egy olyan gépünk, ami kizárólag B problémát tudja megoldani. Nekünk viszont A problémánk van. Ekkor ha szerencsénk van, akkor fogunk találni egy olyan Karp-redukciót, hogy A<big>≺</big>B. Ennek persze vannak feltételei. Az A eldöntési probléma inputját át kell alakítani B eldöntési probléma inputjává, és meg is kell adni ezt a függvényt, nevezzük el ezt a függvényt f függvénynek. Feltétel, hogy f függvény polinom időben kiszámolható legyen, és ezt be is kell bizonyítani. Továbbá azt is be kell bizonyítani, hogy amennyiben a normális inputra A azt válaszolná, hogy IGEN, akkor az f(normális input)-ra a B szintén ugyanezt válaszolná (és ugyanezt be kell bizonyítani NEM válaszra is). Magyarul a B dolgot megoldó gépet megerőszakoljuk hogy A problémát is hajlandó legyen megoldani. 

Ebből következik néhány dolog. Például az, hogy B legalább olyan nehéz probléma, mint A. Ha például B NP-teljes, akkor A is az. Ha B NP-nehéz, akkor A is az. Ha B coNP-beli, akkor A is az. Ez miért van? Hát azért, mert polinom időben át lehet alakítani az A problémát B-vé. Ezt indirekten könnyen lehet bizonyítani. Indirekt tegyük fel, hogy annak ellenére hogy B probléma NP-teljes és létezik egy olyan Karp-redukció ami A problmémát átalakítja B-vé, szóval mindezek ellenére A probléma P-beli. Ekkor A problémát egy polinom idejű f függvénnyel simán átalakítjuk B problémává, erről szól ugye a Karp-redukció. Ezek után ha bármikor B problémát akarnánk megoldani, akkor az f-függvény fordítva végrehajtásával a B inputját átalakítjuk A inputjává, megoldjuk az A problémát polinom időben, és kész is. Ez ellentmondás mivel B-ről azt mondtuk hogy NP-teljes. A másik érdekesség, hogy ha például egy NP-teljes vagy NP-nehéz problémáról kiderülne hogy P-beli, akkor az összes NP-beliről kiderülne hogy P-beli, mivel az NP-nehéz definíciója az, hogy legalább olyan nehéz mint bármely tetszőleges NP-beli. 

Még egy fontos megjegyzés a Karp-redukcióhoz: ugye A problémát akarjuk megoldani, de csak B-t megoldó gépünk van. Az egyik gyakorlaton elhangzott, és fontos tudni, hogy a B-t megoldó gépet az A eldöntési probléma megoldásához csak EGYSZER használhatjuk. Azért mert a Karp-redukció az ilyen. 

<big>'''(''Nem kérdezték, csak kieg.'') H-út? ''' </big>
todo 

<big>'''(''Nem kérdezték, csak kieg.'') 3 színnel színezhetőség problémája? ''' </big>
todo 

<big>'''A feladat megoldása: ''' </big>
todo 

}}

Algoritmuselmélet - Vizsga, 2013.06.06.

2013-06-07T16:54:16Z

Subdiaz: /* 8. Feladat */

==2013.06.06. vizsga megoldásai==
===1. Feladat (Van megoldás) ===
Ebben a feladatban a mélységi bejárással kapcsolatos kérdésekre kell válaszolni.
* '''(a)''' Adja meg a keresztél definícióját!
* '''(b)''' A mélységi bejárás során hogyan lehet a mélységi és a befejezési számok alapján felismerni a keresztéleket? ''Vizsgán megjegyzést fűztek hozzá: irányított gráfokra kell gondolni.''
* '''(c)''' Bizonyítsa be, hogy irányítatlan gráf mélységi bejárásánál nincsenek keresztélek!
{{Rejtett
|mutatott=<big>'''Megoldás'''</big>
|szöveg=
'''(a)''' 
Tekintsük a G irányított gráf egy mélységi bejárását és a kapott T mélységi feszítő erdőt. Ezen bejárás szerint G egy x → y éle keresztél, ha x és y nem leszármazottjai egymásnak.

'''(b)''' 
msz - mélységi szám 
bsz - befejezési szám 
Ha <math> (msz[y] < msz[x]) </math> és <math>(bsz[y] > 0) </math>, akkor az x → y egy keresztél. 
[[Fájl:keresztel_1.png]] 
'''(c)''' 
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.
Másképpen mondva: Nem fejezhettük volna be y-t anélkül, hogy ne jártunk volna x-ben. 
[[Fájl:keresztel_2.PNG]] 
}}

===2. Feladat===
Milyen műveletek vannak a nyitott címzésű hash-elésnél? Hogyan kell megvalósítani a keresést, ha a nyitott címzésű hashelésnél kvadratikus maradék próbát használunk?

{{Rejtett
|mutatott=<big>'''Megoldás'''</big>
|szöveg=
'''Nyitott címzésű hash-elés műveletei:''' 
todo 

'''(''Nem kérdezték, csak kieg.'') Mi az a nyitott címzésű hash-elés?''' 
todo 

'''(''Nem kérdezték, csak kieg.'') Mi az a kvadratikus maradék próba, nyitott címzésű hash-elésnél?''' 
todo 

'''keresés megvalósítása nyitott címzésű hash-elés esetén kvadratikus maradék próbánál:''' 
todo 

}}

===3. Feladat===
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!

{{Rejtett
|mutatott=<big>'''Megoldás'''</big>
|szöveg=
'''UNIÓ-HOLVAN adatszerkezet definíciója: ''' 
todo 

'''(''Nem kérdezték, csak kieg.'') Mi az a Kruskal algoritmus?''' 
todo 

'''Mikor és hogyan használjuk az UNIÓ és a HOLVAN műveleteket a Kruskal algoritmusban:''' 
todo 

}}

===4. Feladat===
Pista bácsi fel akar ugrálni egy n hosszú, fekete illetve fehér fokokból álló csigalépcsőn. Legfeljebb k fokot tud ugrani, de arra vigyáznia kell, hogy páros (>=2) sok foknyi ugrás után páratlan sokat és páratlan sok után mindig páros (>=2) sokat ugorjon. Adjon O(nk) lépésszámú algoritmust, amely megmondja, hogy fel tud-e úgy ugrálni a csigalépcső tetejére, hogy csak egyféle színű lépcsőfokot használ. (A lépcső fokai rendszertelenül vannak színezve, a színezést ismerjük.)
''Vizsgán megjegyzést fűztek hozzá: a talaj és a legteteje nem színes, csak a lépcsők; csak fölfele (előrefele) ugrál, visszafele nem. ''

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

todo

 

}}

===5. Feladat (Van megoldás)===
A hátizsák probléma órán tanult algoritmusát futtattuk egy konkrét inputon, melyben 3 tárgy szerepel. Mi lehetett ez a konkrét input, ha az alábbi táblázat keletkezett?

{| class="wikitable" border="5"
|-
!
! 0
! 1
! 2
! 3
! 4
! 5
! 6
! 7
|-
| 1
| 0
| 0
| 0
| 0
| 10
| 10
| 10
| 10
|-
| 2
| 0
| 0
| 5
| 5
| 10
| 10
| 15
| 15
|-
| 3
| 0
| 0
| 5
| 5
| 13
| 13
| 18
| 18
|}

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

Az egyszerűség kedvéért a súly legyen kg, az érték pedig €.

#Az első sor alapján az 1-es csomag értéke €10, súlya 4kg.
#A második sor alapján a 2-es csomag értéke €5, súlya 2kg.
#A 3. sornál kicsit rafkósnak kell lenni. Leírhatnám egyből a megoldást, de talán több értelme van, ha a logikai zsákutcákat is leírom.
##Először gondolhatnánk arra, hogy a [4,3]-as cella 10+3 formában áll elő, így a 3-as csomag értéke €3. Viszont így a súlyának 0kg-nak kéne lennie, ami nyílván fatal error.
##Második gondolatunk az lehetne, hogy akkor 5+8 formában áll elő, így a 3-as csomag értéke €8. Súlya ekkor 2kg kellene legyen, viszont akkor a [2,3]-as cellába 8-nak, és nem 5-nek kéne szerepelnie, tehát ez se jó megoldás.
##Harmadik ötletnek nagyon más nem jöhet szóba, hogy akkor a 3-as csomag értéke €13, súlya pedig 4kg. És ha leellenőrizzük, látszik, hogy ez lesz a jó megoldás.

Tehát végeredményben a megoldás:
*1-es csomag (€10, 4kg)
*2-es csomag (€5, 2kg)
*3-as csomag (€13, 4kg)

}}

===6. Feladat (Van megoldás)===
Egy irányítatlan, élsúlyozott gráf az alábbi éllistával adott (zárójelben az élsúlyok):

<math>A:B(1), D(3), E(2); B:A(1), C(3), D(y); D:A(3), C(y), E(x); E:A(2), B(1), D(x).</math>
* '''(a)''' Mi lehet x és y értéke, ha tudjuk, hogy az élsúlyok egész számok, és azt is tudjuk, hogy a B csúcsból indított Prim algoritmus az alábbi sorrendben vette be az értékeket: BE, ED, BA, BC. ''Vizsgán megjegyzést fűztek hozzá: az élsúlyok pozitív egész számok, a pozitív szót kifelejtették véletlenül.''
* '''(b)''' Mely éleket és milyen sorrendben választja ki a Kruskal algoritmus? (Ha több megoldás is van, akkor az összeset adja meg!)
{{Rejtett
|mutatott=<big>'''Megoldás'''</big>
|szöveg=
[[File:2013_06_06_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 fához hozzáadjuk a BE élt.
# Most az ED élt választottuk. Ez alapján x értéke csak 1 lehet, így <math>x = 1</math>. (Feladatból kihagyták, hogy pozitív egészekről van szó, amúgy <math>x \le 1</math> lehetne.)
# 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>.

'''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.

1 súlyú - AB, BE, ED

2 súlyú - AE

3 súlyú - BC, AD, EC (és DC, ha <math>y = 3</math>)

Az összes megoldás:

#Az 1 súlyú éleket <math>3! = 6</math> féleképpen veheti fel az algoritmus (nem lehet belőlük kört csinálni, így itt nincsen para).
#Utána megpróbálná felvenni az AE élt, de azzal egy kört kapna, így nem veszi fel. Az AD éllel szintén így járna (~ezeket kéne pirosra színezni, ha olyan lenne a feladat).
#Maradtak a BC, EC és DC oldalak.
##Ha <math>y = 3</math>, akkor ezeket szintén 6 féleképpen veheti fel, tehát összesen 36 féleképpen futhat az algoritmus.
##Ha <math>y \ge 3</math>, akkor a DC oldal kiesik, a maradék 2 élt 2 féleképpen veheti fel, így 12 féleképpen futhat az algoritmus.}}

===7. Feladat===
Létezik-e olyan X eldöntési probléma, amire X<big>∉</big>NP és X<big>≺</big>SAT egyszerre fennáll?

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

<big>'''(''Nem kérdezték, csak kieg.'') Eldöntési probléma osztályok? ''' </big>

 
[[File:bonyolultsag_elmelet.JPG|390px]]
 

A '''problémák'''nak lehet több típusú több bemenete, és több típusú több kimenete. Ezeket átfogalmazzuk olyanra, hogy a kimenete egyetlen bit legyen (IGEN / NEM), mert ezen algoritmusok felhasználásával is teljesen jól lehet dolgozni, ugyanakkor könnyebb őket nehézség / bonyolultság szerint osztályozni. Az ilyen 1 bites kimenetű problémákat nevezzük '''eldöntési problémák'''nak. 

Az eldöntési problémákat nehézség / bonyolultság szerint osztályokba soroljuk, ezen osztályok között olyan kapcsolatok vannak mint a halmazoknál; ez a fenti rajzon látszik. 

A '''P osztály'''ba olyan problémák tartoznak, amelyekre ismert olyan algoritmus, ami a bemenet polinomjával megadott idő alatt lefut. Vagyis ha a bemenet '''n''', akkor az algoritmusra azt mondjuk, hogy nagy_ordó(valami), ahol a valami '''n''' egy polinomja, például n négyzet, n köb, három n négyzet meg négy meg nyolc n köb, és ilyesmik. 

Az '''NP osztály'''ba olyan problémák tartoznak, amelyekre (jelenleg) nem ismert polinom idejű (P-beli) algoritmus, de igen válasz esetén létezik hatékony tanúsítvány. Vagyis, adott egy nagy csomó bemenet és van egy kérdés. P-idő alatt nem tudjuk megmondani a választ, de ha valaki megsúgja hogy a válasz IGEN, akkor P-időben meg tudjuk mondani, hogy ez hülyeség vagy nem hülyeség. Ha azt súgják meg hogy NEM, akkor fogalmunk sincs, P-időben nem tudjuk eldönteni hogy hülyeség-e vagy sem. (''Ha így lenne, vagyis igen és nem válasz esetén is P-időben ellenőrizni tudnánk a válasz helyességét, akkor az egész probléma P-beli lenne, hiszen megsúgjuk saját magunknak hogy NEM és ha helyes akkor NEM egyébként igen. Persze ha az IGEN-ről P-időben kiderül hogy hülyeség attól még lehet hogy IGEN, csak éppen nem az a konkrét ami meg lett súgva, hanem egy másik.'') 

A '''coNP osztály''' lényegében ugyanaz mint az NP osztály, csak NEM válaszra. Vagyis (jelenleg) nem ismerünk rá P-beli algoritmust, de ha a válasz NEM, akkor P-időben (hatékonyan) ellenőrizni tudjuk, hogy ez-e a jó válasz vagy sem. Szintén, IGEN válasz esetén semmit sem tudunk mondani P-időben, a fenti okok miatt (ami a zárójelben van). 

Az '''NP nehéz''' osztályba tartozó eldöntési problémák közül bármelyik legalább olyan nehéz, mint bármelyik másik NP-beli eldöntési probléma. Itt jön képbe a Karp-redukció fogalma. Jó dolog sok NP nehéz problémát ismerni, mert akkor ha találunk egy problémát, akkor ha találunk olyan Karp-redukciót, ami azt mutatja, hogy ez a probléma visszavezethető egy közismert NP nehéz problémára, akkor a mi ismeretlen problémánk is NP nehéz lesz. Ez azért van, mert a Karp-redukció tranzitív művelet, továbbá a Karp-redukcónál használt f függvény P-beli, amit kétszer egymás után alkalmazva is még mindig P-beli lesz ez a dolog (az inputok átalakítása). 

Az '''NP teljes''' problémák azok, amik NP nehezek és NP-beliek is egyszerre. A fenti dolog ide is érvényes, vagyis jó dolog ha sok nevezetes NP teljes problémát ismerünk, mert ha egy ismeretlen problémához találunk egy olyan Karp-redukciót, ami alapján az ismeretlen problémánkat visszavezethetjük egy közismert NP teljes problémára, akkor az ismeretlen problémánkról is kiderült, hogy NP teljes. 

<big>'''(''Nem kérdezték, csak kieg.'') Karp-redukció?''' </big>
Van egy olyan gépünk, ami kizárólag B problémát tudja megoldani. Nekünk viszont A problémánk van. Ekkor ha szerencsénk van, akkor fogunk találni egy olyan Karp-redukciót, hogy A<big>≺</big>B. Ennek persze vannak feltételei. Az A eldöntési probléma inputját át kell alakítani B eldöntési probléma inputjává, és meg is kell adni ezt a függvényt, nevezzük el ezt a függvényt f függvénynek. Feltétel, hogy f függvény polinom időben kiszámolható legyen, és ezt be is kell bizonyítani. Továbbá azt is be kell bizonyítani, hogy amennyiben a normális inputra A azt válaszolná, hogy IGEN, akkor az f(normális input)-ra a B szintén ugyanezt válaszolná (és ugyanezt be kell bizonyítani NEM válaszra is). Magyarul a B dolgot megoldó gépet megerőszakoljuk hogy A problémát is hajlandó legyen megoldani. 

Ebből következik néhány dolog. Például az, hogy B legalább olyan nehéz probléma, mint A. Ha például B NP-teljes, akkor A is az. Ha B NP-nehéz, akkor A is az. Ha B coNP-beli, akkor A is az. Ez miért van? Hát azért, mert polinom időben át lehet alakítani az A problémát B-vé. Ezt indirekten könnyen lehet bizonyítani. Indirekt tegyük fel, hogy annak ellenére hogy B probléma NP-teljes és létezik egy olyan Karp-redukció ami A problmémát átalakítja B-vé, szóval mindezek ellenére A probléma P-beli. Ekkor A problémát egy polinom idejű f függvénnyel simán átalakítjuk B problémává, erről szól ugye a Karp-redukció. Ezek után ha bármikor B problémát akarnánk megoldani, akkor az f-függvény fordítva végrehajtásával a B inputját átalakítjuk A inputjává, megoldjuk az A problémát polinom időben, és kész is. Ez ellentmondás mivel B-ről azt mondtuk hogy NP-teljes. A másik érdekesség, hogy ha például egy NP-teljes vagy NP-nehéz problémáról kiderülne hogy P-beli, akkor az összes NP-beliről kiderülne hogy P-beli, mivel az NP-nehéz definíciója az, hogy legalább olyan nehéz mint bármely tetszőleges NP-beli. 

Még egy fontos megjegyzés a Karp-redukcióhoz: ugye A problémát akarjuk megoldani, de csak B-t megoldó gépünk van. Az egyik gyakorlaton elhangzott, és fontos tudni, hogy a B-t megoldó gépet az A eldöntési probléma megoldásához csak EGYSZER használhatjuk. Azért mert a Karp-redukció az ilyen. 

<big>'''(''Nem kérdezték, csak kieg.'') SAT probléma? ''' </big>
todo 

<big>'''A feladat megoldása: ''' </big>
todo 

}}

===8. Feladat===
P-ben van vagy NP-teljes az alábbi eldöntési probléma: 
*'''Input:''' irányítatlan G gráf 
*'''Kérdés:''' Igaz-e, hogy G-ben vagy van Hamilton-út vagy G 3 színnel színezhető? 

 

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

<big>'''(''Nem kérdezték, csak kieg.'') Eldöntési probléma osztályok? ''' </big>

 
[[File:bonyolultsag_elmelet.JPG|390px]]
 

A '''problémák'''nak lehet több típusú több bemenete, és több típusú több kimenete. Ezeket átfogalmazzuk olyanra, hogy a kimenete egyetlen bit legyen (IGEN / NEM), mert ezen algoritmusok felhasználásával is teljesen jól lehet dolgozni, ugyanakkor könnyebb őket nehézség / bonyolultság szerint osztályozni. Az ilyen 1 bites kimenetű problémákat nevezzük '''eldöntési problémák'''nak. 

Az eldöntési problémákat nehézség / bonyolultság szerint osztályokba soroljuk, ezen osztályok között olyan kapcsolatok vannak mint a halmazoknál; ez a fenti rajzon látszik. 

A '''P osztály'''ba olyan problémák tartoznak, amelyekre ismert olyan algoritmus, ami a bemenet polinomjával megadott idő alatt lefut. Vagyis ha a bemenet '''n''', akkor az algoritmusra azt mondjuk, hogy nagy_ordó(valami), ahol a valami '''n''' egy polinomja, például n négyzet, n köb, három n négyzet meg négy meg nyolc n köb, és ilyesmik. 

Az '''NP osztály'''ba olyan problémák tartoznak, amelyekre (jelenleg) nem ismert polinom idejű (P-beli) algoritmus, de igen válasz esetén létezik hatékony tanúsítvány. Vagyis, adott egy nagy csomó bemenet és van egy kérdés. P-idő alatt nem tudjuk megmondani a választ, de ha valaki megsúgja hogy a válasz IGEN, akkor P-időben meg tudjuk mondani, hogy ez hülyeség vagy nem hülyeség. Ha azt súgják meg hogy NEM, akkor fogalmunk sincs, P-időben nem tudjuk eldönteni hogy hülyeség-e vagy sem. (''Ha így lenne, vagyis igen és nem válasz esetén is P-időben ellenőrizni tudnánk a válasz helyességét, akkor az egész probléma P-beli lenne, hiszen megsúgjuk saját magunknak hogy NEM és ha helyes akkor NEM egyébként igen. Persze ha az IGEN-ről P-időben kiderül hogy hülyeség attól még lehet hogy IGEN, csak éppen nem az a konkrét ami meg lett súgva, hanem egy másik.'') 

A '''coNP osztály''' lényegében ugyanaz mint az NP osztály, csak NEM válaszra. Vagyis (jelenleg) nem ismerünk rá P-beli algoritmust, de ha a válasz NEM, akkor P-időben (hatékonyan) ellenőrizni tudjuk, hogy ez-e a jó válasz vagy sem. Szintén, IGEN válasz esetén semmit sem tudunk mondani P-időben, a fenti okok miatt (ami a zárójelben van). 

Az '''NP nehéz''' osztályba tartozó eldöntési problémák közül bármelyik legalább olyan nehéz, mint bármelyik másik NP-beli eldöntési probléma. Itt jön képbe a Karp-redukció fogalma. Jó dolog sok NP nehéz problémát ismerni, mert akkor ha találunk egy problémát, akkor ha találunk olyan Karp-redukciót, ami azt mutatja, hogy ez a probléma visszavezethető egy közismert NP nehéz problémára, akkor a mi ismeretlen problémánk is NP nehéz lesz. Ez azért van, mert a Karp-redukció tranzitív művelet, továbbá a Karp-redukcónál használt f függvény P-beli, amit kétszer egymás után alkalmazva is még mindig P-beli lesz ez a dolog (az inputok átalakítása). 

Az '''NP teljes''' problémák azok, amik NP nehezek és NP-beliek is egyszerre. A fenti dolog ide is érvényes, vagyis jó dolog ha sok nevezetes NP teljes problémát ismerünk, mert ha egy ismeretlen problémához találunk egy olyan Karp-redukciót, ami alapján az ismeretlen problémánkat visszavezethetjük egy közismert NP teljes problémára, akkor az ismeretlen problémánkról is kiderült, hogy NP teljes. 

<big>'''(''Nem kérdezték, csak kieg.'') Karp-redukció?''' </big>
Van egy olyan gépünk, ami kizárólag B problémát tudja megoldani. Nekünk viszont A problémánk van. Ekkor ha szerencsénk van, akkor fogunk találni egy olyan Karp-redukciót, hogy A<big>≺</big>B. Ennek persze vannak feltételei. Az A eldöntési probléma inputját át kell alakítani B eldöntési probléma inputjává, és meg is kell adni ezt a függvényt, nevezzük el ezt a függvényt f függvénynek. Feltétel, hogy f függvény polinom időben kiszámolható legyen, és ezt be is kell bizonyítani. Továbbá azt is be kell bizonyítani, hogy amennyiben a normális inputra A azt válaszolná, hogy IGEN, akkor az f(normális input)-ra a B szintén ugyanezt válaszolná (és ugyanezt be kell bizonyítani NEM válaszra is). Magyarul a B dolgot megoldó gépet megerőszakoljuk hogy A problémát is hajlandó legyen megoldani. 

Ebből következik néhány dolog. Például az, hogy B legalább olyan nehéz probléma, mint A. Ha például B NP-teljes, akkor A is az. Ha B NP-nehéz, akkor A is az. Ha B coNP-beli, akkor A is az. Ez miért van? Hát azért, mert polinom időben át lehet alakítani az A problémát B-vé. Ezt indirekten könnyen lehet bizonyítani. Indirekt tegyük fel, hogy annak ellenére hogy B probléma NP-teljes és létezik egy olyan Karp-redukció ami A problmémát átalakítja B-vé, szóval mindezek ellenére A probléma P-beli. Ekkor A problémát egy polinom idejű f függvénnyel simán átalakítjuk B problémává, erről szól ugye a Karp-redukció. Ezek után ha bármikor B problémát akarnánk megoldani, akkor az f-függvény fordítva végrehajtásával a B inputját átalakítjuk A inputjává, megoldjuk az A problémát polinom időben, és kész is. Ez ellentmondás mivel B-ről azt mondtuk hogy NP-teljes. A másik érdekesség, hogy ha például egy NP-teljes vagy NP-nehéz problémáról kiderülne hogy P-beli, akkor az összes NP-beliről kiderülne hogy P-beli, mivel az NP-nehéz definíciója az, hogy legalább olyan nehéz mint bármely tetszőleges NP-beli. 

Még egy fontos megjegyzés a Karp-redukcióhoz: ugye A problémát akarjuk megoldani, de csak B-t megoldó gépünk van. Az egyik gyakorlaton elhangzott, és fontos tudni, hogy a B-t megoldó gépet az A eldöntési probléma megoldásához csak EGYSZER használhatjuk. Azért mert a Karp-redukció az ilyen. 

'''(''Nem kérdezték, csak kieg.'') H-út? ''' 
todo 

'''(''Nem kérdezték, csak kieg.'') 3 színnel színezhetőség problémája? ''' 
todo 

'''A feladat megoldása: ''' 
todo 

}}

Algoritmuselmélet - Vizsga, 2013.06.06.

2013-06-07T16:53:44Z

Subdiaz: /* 7. Feladat */

Algoritmuselmélet - Vizsga, 2013.06.06.

2013-06-07T16:50:54Z

Subdiaz: /* 7. Feladat */

{{Tantárgy
|nev=Fizika 2i
|targykod=TE11AX04
|kredit=4
|felev=3
|kereszt=van
|tanszék= TTK Fizika Tanszék
|kiszh=6 db
|vizsga=írásbeli és szóbeli
|nagyzh=1 db
|hf= nincs
|szak=info
|tad=https://www.vik.bme.hu/kepzes/targyak/TE11AX04/
|targyhonlap=http://fizipedia.bme.hu/index.php/Fizika_2i_-_M%C3%A9rn%C3%B6k_informatikus_alapszak
|levlista=ifizika2@sch.bme.hu
}}

==Követelmények==

=== Előtanulmányi rend ===

[[Fizika I.| Fizika 1i]] tárgyból kredit megszerzése szükséges a tárgy felvételéhez.

=== A szorgalmi időszakban ===
*Az '''aláírás''' feltételei:
**A '''gyakorlatok''' legalább 70%-án való részvétel. (Előadáson van katalógus, de csak statisztikai céllal illetve megajánlott jegyhez.)
**A '''kisZH-k''' sikeres megírása. Ehhez a 6 db kisZH-ból a legjobb 5-nek az átlaga kell, hogy min. 40% legyen.
**A '''nagyZH''' sikeres (min. 40%) megírása. Számológép használható, függvénytábla egyenesen igen, kereszten nem.
*'''Megajánlott jegy:''' egyenesen van, követelményei változóak. Legutóbb 90% feletti nagyZH és KisZH-átlag illetve 70% előadásjelenlét kellett a megajánlott 5-öshöz. Kereszten nincs.
*'''Pótlási lehetőségek:'''
**A kisZH-k egyenként kereszten nem pótolhatóak, egyenesen egy külön alkalommal igen.
**A nagyZH egyszer félév közben pótolható, a pótZH anyaga megegyezik a nagyZH-éval.
**Ha a két ZH-típus közül az egyik nincs meg, akkor a pótlási héten pótpótZH (aláíráspótló) írható (különeljárási díj fejében), és az aláírás ezzel is megszerezhető. Ennek a ZH-nak az anyaga már az egész féléves anyag!
*'''Elővizsga:''' nincs.

=== A vizsgaidőszakban ===
*'''Vizsga:''' két részből áll, írásbeli és szóbeli. Az írásbeli vizsga alapján egy megajánlott jegyet kapsz, minimum 40% kell az elégségeshez. Számológép használható, függvénytábla egyenesen igen, kereszten nem. Az írásbeli vizsgát szóbeli vizsga követheti. Elégtelen írásbeli vizsga szóbelivel nem javítható. Ha szóbelizel, a megajánlott jegyen javítani, de rontani is lehet.
**Előfeltétele: az aláírás megléte.

=== Félévvégi jegy ===
*A ZH-k eredménye nem számít bele a a félévvégi jegybe, azt tisztán a vizsgaeredményre (V) kapod.
*Ponthatárok:
:{| class="wikitable" align="center"
!V (%) !! Jegy
|-
|0 - 39 || 1
|-
|40 - 55 || 2
|-
|55 - 65 || 3
|-
|65 - 80 || 4
|-
|80 - 100 || 5
|}

==Tematika==
*Az előadás (3 óra/hét) az [[Alex Hudson - Rex Nelson: Útban a modern fizikához]] tankönyv fejezeteit követi. A gyakorlatokon (1 óra/hét) a tankönyvben szereplő feladatok alapján az előadásokon elhangzottak szemléltetésére és az ismeretek készségszintű begyakorlására kerül sor.
===Előadás===
[[Fizika_II.Tematika|Tematika]]

===Gyakorlat===
Kiscsoportos (tanköri) foglalkozás. Témája az előadáson elhangzott tananyagnak feladatmegoldásokon keresztüli megértése és elmélyítése. A gyakorlatokon a [[Alex Hudson - Rex Nelson: Útban a modern fizikához| Hudson-Nelson]] könyvben lévő kidolgozott "Példák" és kiválasztott "Feladatok" szerepelnek:
* [[FizikaKonyvFeladatok32|32. fejezet]]: 1, 3, 4, 5, 7, 8, 11,.14, 15, 17, 18, 19, 23, 25, 28, 33, 35, 41, 45
* [[FizikaKonyvFeladatok33|33. fejezet]]: 1, 3, 4, 7, 9
* [[FizikaKonyvFeladatok35|35. fejezet]]: 2, 4, 5, 8, 9, 11 .13, 15, 17, 18, 19, 21, 22, 25, 28, 30, 32
* [[FizikaKonyvFeladatok36|36. fejezet]]: 1, 3, 4, 5
* [[FizikaKonyvFeladatok37|37. fejezet]]: 2, 3, 6, 8, 9, 11, 13, 19, 22, 24, 26, 32, 38, 48, 56
* [[FizikaKonyvFeladatok38|38. fejezet]]: 3, 4, 8, 12, 15, 19, 20, 24, 27, 32, 41
* [[FizikaKonyvFeladatok39|39. fejezet]]: 1, 2, 4, 7, 10, 14, 18, 21, 25, 27, 28, 31, 40
* [[FizikaKonyvFeladatok40|40. fejezet]]: 2, 3, 7, 11, 13, 15, 24
* [[FizikaKonyvFeladatok42|42. fejezet]]: 1, 2, 4, 6, 7, 8, 10, 12, 15, 17, 19, 20, 22, 25, 33, 44
* [[FizikaKonyvFeladatok43|43. fejezet]]: 4, 6, 8, 10, 11, 14, 20, 23, 24, 25, 27, 29, 31, 36, 39
* [[FizikaKonyvFeladatok44|44. fejezet]]: 3, 5, 7, 8, 12, 14, 15, 18, 21, 22, 24, 26, 31, 36, 39
* [[FizikaKonyvFeladatok45|45. fejezet]]: 1, 2, 5, 7, 9, 12, 13, 14, 19, 20, 23, 25, 28, 32, 36, 40, 45

==Segédanyagok ==
*A tárgy előadásai és gyakorlatai a nagykönyv fejezeteit követik:
**[[Alex Hudson - Rex Nelson: Útban a modern fizikához]]
*[[VizsgaKepletTar|Vizsgán használható képletek]] (könnyen másolható, pl. feladatokhoz)
*[[Media:Fizika2i_KiskerdesekPacherALL.pdf | Kidolgozott (Pacher-féle) kiskérdések]]
*[[Media:Fizika2i_kifkerdesek_kidolgozva.pdf | Régebbi keresztes kifejtős kérdések kidolgozva]], nagyrészt órai jegyzetből (by Bálint Ferenc, Surman Dénes, Tóth Anett)
*[[Fizika 2i 2009-es gyakorlatanyag | 2009-es gyakorlatjegyzet]] (Vannak benne hibák!)
*[[Media:Fizika2i_eloadasjegyzet2008_v0.7.pdf | 2008-as előadásjegyzet]] (v.0.7.) Dr. Varga Gábor előadásai alapján. (Készítette Kőrösi Tamás, Kántor Tibor, Kiss Dávid - DicsőHetek Jegyzettár)
*[[Media:Fizika2i_jegyzet_csakgyak.pdf | 2007-es keresztféléves gyakorlatjegyzet]]
*2007 őszi, Dr. Pacher Pál 2. ZH utáni előadásainak diái:
**[[Media:Fizika2i_pacherea2007_valtakozo_aramu_aramkorok.pdf |Váltakozó áramú áramkörök]]
**[[Media:Fizika2i_pacherea2007_hullamtermeszet.pdf |Részecskék hullámtermészete]]
**[[Media:Fizika2i_pacherea2007_altalanos_relativitaselmelet.pdf |Általános relativitáselmélet]]
**[[Media:Fizika2i_pacherea2007_spec_rel.pdf |A speciális relativitáselmélet]]
**[[Media:Fizika2i_pacherea2007_szilfizbev.pdf |Bevezetés a szilárdtest-fizikába 1.]]
**[[Media:Fizika2i_pacherea2007_szilfizbev2.pdf |Bevezetés a szilárdtest-fizikába 2.]]
**[[Media:Fizika2i_pacherea2007_atomfizika.pdf |Atomfizika]]
**[[Media:Fizika2i_pacherea2007_kvantum_statisztika.pdf |Azonos részecskékből álló rendszerek, kvantumstatisztikák]]
**[[Media:Fizika2i_pacherea2007_kvantumos.pdf |A sugárzás kvantumos természete]]

==Kikérdező==
*[[Fizika 2i Igaz-hamis kikérdező | Igaz-hamis]]

==KisZH-k==
*[[Fizika_2i_KisZH-k_2013_tavasz | 2012-13 tavasz (kereszt)]]
*[[Fizika_2i_KisZH-k_2011_ősz | 2011-12 ősz]]

==NagyZH ==
*Előző évek ZH-i:
**2010-2011 tavasz (kereszt)
***[[Media:Fizika2i-2011tavasz-zh1mego.pdf | ZH feladatsor megoldással]] és [[Media:Fizika2i-2011tavasz-zh1.pdf |megoldás nélkül]]
**2008-2009 tavasz (kereszt)
***[[Media:Fizika2i_2009tavasz_zh1.pdf | 1. ZH feladatsor]] (Csak a számpéldák!)
***[[Media:Fizika2i_2009tavasz_zh2.pdf | 2. ZH feladatsor]]
***[[Fizika2PPZH20090520 | PótpótZH feladatsor]]
**2008-2009 ősz
***[[Media:Fizika2i_2008osz_zh2_mego.pdf | 2. ZH számolós feladatai megoldással]]
**2007-2008 tavasz (kereszt)
***[[VargaZH2008 | 1. ZH feladatsor megoldással]]
***[[VargaZH20080429 | 2. ZH feladatsor megoldással]]
**2007-2008 ősz
***[[Media:Fizika2i_ZH2_2007osz.jpg | 2. ZH feladatsor]]
**2006
***[[Fizika2HianyosMondatok|Elméleti rész - hiányos mondatok]]
***[[Fizika2Kifejtendo|Elméleti rész - kifejtendő kérdések]]
***[[Fizika2Feladatok|Gyakorlati rész - feladatok]]

==Vizsga==
*[[Media:Fizika_2i_igazhamis.pdf | Igaz-hamis feladatgyűjtemény]]
*[[Fizika2KiegeszitosGyujtemeny|Kiegészítős feladatgyűjtemény]]
*[[Media:Fizika_2i_keresztvizsga.pdf|Keresztféléves feladatgyűjtemény]] és a legtöbb feladat [[Media:Fizika_2i_keresztvizsga_mo.pdf|megoldása]]
*Előző évek vizsgái:
**2012-13 tavasz (kereszt)
***[[Media:Fizika2i_vizsga_20130531.pdf | 2013.05.31]]
****[[Media:Fizika2i_vizsga_20130531_megjegyzes.pdf‎ | megjegyzés]]
**2010-11 tavasz (kereszt)
***[[Fizika2Vizsga20110603|2011.06.03.]]
***[[Fizika2Vizsga20110527|2011.05.27]]
**2010-11 ősz
***[[Fizika2Vizsga20110113|2011.01.13.]]
**2009-10 ősz
***[[Fizika 2, 2010. január 21-e vizsga|2010.01.21.]]
***[[Media:Fizika2i_vizsga_20100114.pdf | 2010.01.14]]
***[[Media:Fizika2i_vizsga_20101223.pdf | 2010.12.23]]
**2008-09 tavasz (kereszt)
***[[Fizika2Vizsga20090605|2009.06.05.]]
***[[Fizika2Vizsga20090529|2009.05.29.]]
**2008-09 ősz
***[[Fizika2Vizsga20090121|2009.01.21.]]
**2007-08 tavasz (kereszt)
***[[Fizika2Vizsga20080613|2008.06.13.]]
***[[Fizika2Vizsga20080606|2008.06.06.]]
***[[Fizika2Vizsga20080528|2008.05.28.]]
**2007-08 ősz
***[[Media:Fizika2i_vizsga_20080117.pdf | 2008.01.17]]

==Angol kurzus (Bokor Nándor)==
*[[Angfiz2Elmelet|elméleti kérdések]] - fizika1 + fizika2
===Vizsga===
*[[Angfiz2Vizsga2007|2. Vizsga 2007]]
*[[Angfiz2Vizsga2002|Vizsga 2002.06.14]] - elmélet
*[[Angfiz2Vizsga2002e|Vizsga 2002/05/24]] - elmélet

==Kedvcsináló==
===Koza===
Érdemes az előadást Kornisnál felvenni, zh-knál, vizsgáknál elég jószívű. Év elején soha nem mondják, de az előadásokon való jelenlét ér valami bónuszt, így megéri legalább 5-6 előadásra bemenni még év elején. (Negatívum nem érhet az óra nem látogatásából). ZH és vizsga előtt érdemes ránézni a fizipédiára, sose tudhatja az ember mi lesz ismerős másnap számonkérésen. 
-- [[Szerkesztő:Kiskoza|Koza]]

===Masa===
* Kis JAVA programok segítségével szimulálhatjuk a kísérleteket:
* [http://www.walter-fendt.de/ph14hu/index.html weblap] (neten találtam, szerintem nagy segítség.) 
-- [[SomogyiPeter13|Masa]] - 2010.05.25.

==Kapcsolódó tárgyak==
===Előkövetelmény===
*[[Fizika I.]]: kredit megszerzése szükséges a tárgy felvételéhez.
===Ráépülő===
*[[Elektronika]]: leghamarabb a tárggyal együtt vehető fel.

=OLD=
{{Elavult}}
== Egyéb ==
Ezeket nem lenne szabad hagyni, hogy elvesszen, de nem most fogom rendberakni:
* [[Fizika_C2i_keresztfélév_Varga_féle_kurzus]]
[[Category:Infoalap]]

Fizika II.

2013-06-01T22:36:40Z

Subdiaz: /* Vizsga */

{{Tantárgy
|nev=Fizika 2i
|targykod=TE11AX04
|kredit=4
|felev=3
|kereszt=van
|tanszék= TTK Fizika Tanszék
|kiszh=6 db
|vizsga=írásbeli és szóbeli
|nagyzh=1 db
|hf= nincs
|szak=info
|tad=https://www.vik.bme.hu/kepzes/targyak/TE11AX04/
|targyhonlap=http://fizipedia.bme.hu/index.php/Fizika_2i_-_M%C3%A9rn%C3%B6k_informatikus_alapszak
|levlista=ifizika2@sch.bme.hu
}}

==Követelmények==

=== Előtanulmányi rend ===

[[Fizika I.| Fizika 1i]] tárgyból kredit megszerzése szükséges a tárgy felvételéhez.

=== A szorgalmi időszakban ===
*Az '''aláírás''' feltételei:
**A '''gyakorlatok''' legalább 70%-án való részvétel. (Előadáson van katalógus, de csak statisztikai céllal illetve megajánlott jegyhez.)
**A '''kisZH-k''' sikeres megírása. Ehhez a 6 db kisZH-ból a legjobb 5-nek az átlaga kell, hogy min. 40% legyen.
**A '''nagyZH''' sikeres (min. 40%) megírása. Számológép használható, függvénytábla egyenesen igen, kereszten nem.
*'''Megajánlott jegy:''' egyenesen van, követelményei változóak. Legutóbb 90% feletti nagyZH és KisZH-átlag illetve 70% előadásjelenlét kellett a megajánlott 5-öshöz. Kereszten nincs.
*'''Pótlási lehetőségek:'''
**A kisZH-k egyenként kereszten nem pótolhatóak, egyenesen egy külön alkalommal igen.
**A nagyZH egyszer félév közben pótolható, a pótZH anyaga megegyezik a nagyZH-éval.
**Ha a két ZH-típus közül az egyik nincs meg, akkor a pótlási héten pótpótZH (aláíráspótló) írható (különeljárási díj fejében), és az aláírás ezzel is megszerezhető. Ennek a ZH-nak az anyaga már az egész féléves anyag!
*'''Elővizsga:''' nincs.

=== A vizsgaidőszakban ===
*'''Vizsga:''' két részből áll, írásbeli és szóbeli. Az írásbeli vizsga alapján egy megajánlott jegyet kapsz, minimum 40% kell az elégségeshez. Számológép használható, függvénytábla egyenesen igen, kereszten nem. Az írásbeli vizsgát szóbeli vizsga követheti. Elégtelen írásbeli vizsga szóbelivel nem javítható. Ha szóbelizel, a megajánlott jegyen javítani, de rontani is lehet.
**Előfeltétele: az aláírás megléte.

=== Félévvégi jegy ===
*A ZH-k eredménye nem számít bele a a félévvégi jegybe, azt tisztán a vizsgaeredményre (V) kapod.
*Ponthatárok:
:{| class="wikitable" align="center"
!V (%) !! Jegy
|-
|0 - 39 || 1
|-
|40 - 55 || 2
|-
|55 - 65 || 3
|-
|65 - 80 || 4
|-
|80 - 100 || 5
|}

==Tematika==
*Az előadás (3 óra/hét) az [[Alex Hudson - Rex Nelson: Útban a modern fizikához]] tankönyv fejezeteit követi. A gyakorlatokon (1 óra/hét) a tankönyvben szereplő feladatok alapján az előadásokon elhangzottak szemléltetésére és az ismeretek készségszintű begyakorlására kerül sor.
===Előadás===
[[Fizika_II.Tematika|Tematika]]

===Gyakorlat===
Kiscsoportos (tanköri) foglalkozás. Témája az előadáson elhangzott tananyagnak feladatmegoldásokon keresztüli megértése és elmélyítése. A gyakorlatokon a [[Alex Hudson - Rex Nelson: Útban a modern fizikához| Hudson-Nelson]] könyvben lévő kidolgozott "Példák" és kiválasztott "Feladatok" szerepelnek:
* [[FizikaKonyvFeladatok32|32. fejezet]]: 1, 3, 4, 5, 7, 8, 11,.14, 15, 17, 18, 19, 23, 25, 28, 33, 35, 41, 45
* [[FizikaKonyvFeladatok33|33. fejezet]]: 1, 3, 4, 7, 9
* [[FizikaKonyvFeladatok35|35. fejezet]]: 2, 4, 5, 8, 9, 11 .13, 15, 17, 18, 19, 21, 22, 25, 28, 30, 32
* [[FizikaKonyvFeladatok36|36. fejezet]]: 1, 3, 4, 5
* [[FizikaKonyvFeladatok37|37. fejezet]]: 2, 3, 6, 8, 9, 11, 13, 19, 22, 24, 26, 32, 38, 48, 56
* [[FizikaKonyvFeladatok38|38. fejezet]]: 3, 4, 8, 12, 15, 19, 20, 24, 27, 32, 41
* [[FizikaKonyvFeladatok39|39. fejezet]]: 1, 2, 4, 7, 10, 14, 18, 21, 25, 27, 28, 31, 40
* [[FizikaKonyvFeladatok40|40. fejezet]]: 2, 3, 7, 11, 13, 15, 24
* [[FizikaKonyvFeladatok42|42. fejezet]]: 1, 2, 4, 6, 7, 8, 10, 12, 15, 17, 19, 20, 22, 25, 33, 44
* [[FizikaKonyvFeladatok43|43. fejezet]]: 4, 6, 8, 10, 11, 14, 20, 23, 24, 25, 27, 29, 31, 36, 39
* [[FizikaKonyvFeladatok44|44. fejezet]]: 3, 5, 7, 8, 12, 14, 15, 18, 21, 22, 24, 26, 31, 36, 39
* [[FizikaKonyvFeladatok45|45. fejezet]]: 1, 2, 5, 7, 9, 12, 13, 14, 19, 20, 23, 25, 28, 32, 36, 40, 45

==Segédanyagok ==
*A tárgy előadásai és gyakorlatai a nagykönyv fejezeteit követik:
**[[Alex Hudson - Rex Nelson: Útban a modern fizikához]]
*[[VizsgaKepletTar|Vizsgán használható képletek]] (könnyen másolható, pl. feladatokhoz)
*[[Media:Fizika2i_KiskerdesekPacherALL.pdf | Kidolgozott (Pacher-féle) kiskérdések]]
*[[Media:Fizika2i_kifkerdesek_kidolgozva.pdf | Régebbi keresztes kifejtős kérdések kidolgozva]], nagyrészt órai jegyzetből (by Bálint Ferenc, Surman Dénes, Tóth Anett)
*[[Fizika 2i 2009-es gyakorlatanyag | 2009-es gyakorlatjegyzet]] (Vannak benne hibák!)
*[[Media:Fizika2i_eloadasjegyzet2008_v0.7.pdf | 2008-as előadásjegyzet]] (v.0.7.) Dr. Varga Gábor előadásai alapján. (Készítette Kőrösi Tamás, Kántor Tibor, Kiss Dávid - DicsőHetek Jegyzettár)
*[[Media:Fizika2i_jegyzet_csakgyak.pdf | 2007-es keresztféléves gyakorlatjegyzet]]
*2007 őszi, Dr. Pacher Pál 2. ZH utáni előadásainak diái:
**[[Media:Fizika2i_pacherea2007_valtakozo_aramu_aramkorok.pdf |Váltakozó áramú áramkörök]]
**[[Media:Fizika2i_pacherea2007_hullamtermeszet.pdf |Részecskék hullámtermészete]]
**[[Media:Fizika2i_pacherea2007_altalanos_relativitaselmelet.pdf |Általános relativitáselmélet]]
**[[Media:Fizika2i_pacherea2007_spec_rel.pdf |A speciális relativitáselmélet]]
**[[Media:Fizika2i_pacherea2007_szilfizbev.pdf |Bevezetés a szilárdtest-fizikába 1.]]
**[[Media:Fizika2i_pacherea2007_szilfizbev2.pdf |Bevezetés a szilárdtest-fizikába 2.]]
**[[Media:Fizika2i_pacherea2007_atomfizika.pdf |Atomfizika]]
**[[Media:Fizika2i_pacherea2007_kvantum_statisztika.pdf |Azonos részecskékből álló rendszerek, kvantumstatisztikák]]
**[[Media:Fizika2i_pacherea2007_kvantumos.pdf |A sugárzás kvantumos természete]]

==Kikérdező==
*[[Fizika 2i Igaz-hamis kikérdező | Igaz-hamis]]

==KisZH-k==
*[[Fizika_2i_KisZH-k_2013_tavasz | 2012-13 tavasz (kereszt)]]
*[[Fizika_2i_KisZH-k_2011_ősz | 2011-12 ősz]]

==NagyZH ==
*Előző évek ZH-i:
**2010-2011 tavasz (kereszt)
***[[Media:Fizika2i-2011tavasz-zh1mego.pdf | ZH feladatsor megoldással]] és [[Media:Fizika2i-2011tavasz-zh1.pdf |megoldás nélkül]]
**2008-2009 tavasz (kereszt)
***[[Media:Fizika2i_2009tavasz_zh1.pdf | 1. ZH feladatsor]] (Csak a számpéldák!)
***[[Media:Fizika2i_2009tavasz_zh2.pdf | 2. ZH feladatsor]]
***[[Fizika2PPZH20090520 | PótpótZH feladatsor]]
**2008-2009 ősz
***[[Media:Fizika2i_2008osz_zh2_mego.pdf | 2. ZH számolós feladatai megoldással]]
**2007-2008 tavasz (kereszt)
***[[VargaZH2008 | 1. ZH feladatsor megoldással]]
***[[VargaZH20080429 | 2. ZH feladatsor megoldással]]
**2007-2008 ősz
***[[Media:Fizika2i_ZH2_2007osz.jpg | 2. ZH feladatsor]]
**2006
***[[Fizika2HianyosMondatok|Elméleti rész - hiányos mondatok]]
***[[Fizika2Kifejtendo|Elméleti rész - kifejtendő kérdések]]
***[[Fizika2Feladatok|Gyakorlati rész - feladatok]]

==Vizsga==
*[[Media:Fizika_2i_igazhamis.pdf | Igaz-hamis feladatgyűjtemény]]
*[[Fizika2KiegeszitosGyujtemeny|Kiegészítős feladatgyűjtemény]]
*[[Media:Fizika_2i_keresztvizsga.pdf|Keresztféléves feladatgyűjtemény]] és a legtöbb feladat [[Media:Fizika_2i_keresztvizsga_mo.pdf|megoldása]]
*Előző évek vizsgái:
**2012-13 tavasz (kereszt)
***[[Media:Fizika2i_vizsga_20130531.pdf | 2013.05.31]]
*****[[Media:Fizika2i_vizsga_20130531_megjegyzes.pdf‎ | megjegyzés]]
**2010-11 tavasz (kereszt)
***[[Fizika2Vizsga20110603|2011.06.03.]]
***[[Fizika2Vizsga20110527|2011.05.27]]
**2010-11 ősz
***[[Fizika2Vizsga20110113|2011.01.13.]]
**2009-10 ősz
***[[Fizika 2, 2010. január 21-e vizsga|2010.01.21.]]
***[[Media:Fizika2i_vizsga_20100114.pdf | 2010.01.14]]
***[[Media:Fizika2i_vizsga_20101223.pdf | 2010.12.23]]
**2008-09 tavasz (kereszt)
***[[Fizika2Vizsga20090605|2009.06.05.]]
***[[Fizika2Vizsga20090529|2009.05.29.]]
**2008-09 ősz
***[[Fizika2Vizsga20090121|2009.01.21.]]
**2007-08 tavasz (kereszt)
***[[Fizika2Vizsga20080613|2008.06.13.]]
***[[Fizika2Vizsga20080606|2008.06.06.]]
***[[Fizika2Vizsga20080528|2008.05.28.]]
**2007-08 ősz
***[[Media:Fizika2i_vizsga_20080117.pdf | 2008.01.17]]

==Angol kurzus (Bokor Nándor)==
*[[Angfiz2Elmelet|elméleti kérdések]] - fizika1 + fizika2
===Vizsga===
*[[Angfiz2Vizsga2007|2. Vizsga 2007]]
*[[Angfiz2Vizsga2002|Vizsga 2002.06.14]] - elmélet
*[[Angfiz2Vizsga2002e|Vizsga 2002/05/24]] - elmélet

==Kedvcsináló==
===Koza===
Érdemes az előadást Kornisnál felvenni, zh-knál, vizsgáknál elég jószívű. Év elején soha nem mondják, de az előadásokon való jelenlét ér valami bónuszt, így megéri legalább 5-6 előadásra bemenni még év elején. (Negatívum nem érhet az óra nem látogatásából). ZH és vizsga előtt érdemes ránézni a fizipédiára, sose tudhatja az ember mi lesz ismerős másnap számonkérésen. 
-- [[Szerkesztő:Kiskoza|Koza]]

===Masa===
* Kis JAVA programok segítségével szimulálhatjuk a kísérleteket:
* [http://www.walter-fendt.de/ph14hu/index.html weblap] (neten találtam, szerintem nagy segítség.) 
-- [[SomogyiPeter13|Masa]] - 2010.05.25.

==Kapcsolódó tárgyak==
===Előkövetelmény===
*[[Fizika I.]]: kredit megszerzése szükséges a tárgy felvételéhez.
===Ráépülő===
*[[Elektronika]]: leghamarabb a tárggyal együtt vehető fel.

=OLD=
{{Elavult}}
== Egyéb ==
Ezeket nem lenne szabad hagyni, hogy elvesszen, de nem most fogom rendberakni:
* [[Fizika_C2i_keresztfélév_Varga_féle_kurzus]]
[[Category:Infoalap]]

Fájl:Fizika2i vizsga 20130531 megjegyzes.pdf

2013-06-01T22:34:08Z

Subdiaz: Néhány megjegyzés a 2013.05.31. vizsgával kapcsolatban.

Néhány megjegyzés a 2013.05.31. vizsgával kapcsolatban.

Szociológia

2013-02-15T22:18:38Z

Subdiaz: /* Vélemények */

{{GlobalTemplate|Gazdhuman|SzocioLogia}}

Tárgyhonlap (2012 Tavasz): http://syi.hu/oktatas.html

Előadó (2008 szept.): Szakadát István 
Tanszék: BME Szociológia és Kommunikáció Tanszék 
Tárgykövetelmények lapja: http://mokk.bme.hu/hallgato/cselekveselmelet

Az előadáson nem volt katalógus. Két évközi ZH-t kell teljesíteni. A tananyagot egy, az előadó által írt könyvből lehet elsajátítani. A könyv ~250 oldalas, azaz ZH-nként ~125 oldalt kell elolvasnod. Az előző félévvel ellentétben ez az előadó kifejtős ZH-kat íratott (ami nyilván nehezebb, mint a feleletválasztós). Az első ZH-n főleg definíciók voltak, és 4-5 kérdést tartalmazott. Neptun kód alapján voltunk 4 csoportra bontva. Ehhez a ZH-hoz nem volt elég, ha csak egyszer átfutottad a jegyzetet, de sokkal több sem kellett hozzá. A második ZH anyaga már sokkal emberibb, és itt már tényleg elég volt egyszer elolvasni az anyagot.

Előadó (2008 feb.): Csigó Péter 
Tanszék: BME Szociológia és Kommunikáció Tanszék 
Tárgykövetelmények lapja: http://mokk.bme.hu/bsc

Az előadások anyaga mind felkerült a tárgy oldalára (http://mokk.bme.hu/bsc), katalógust nem vezettek. Az egyetlen ZH, amely a félévközi jegyet adta, 21 db. kérdésből állt ABCD lehetőségekkel, melynek egyik felét logikusan ki lehetett következtetni, másik felét pedig a kiadott segédanyagok teljes mértékben lefedték.

SzociologiaZH2008majus8

-- [[VeresSzentkiralyiAndras|dnet]] - 2008.05.26.

== régi zhk: ==
<a href="%ATTACHURLPATH%/szoci1.jpg">szoci1.jpg</a> 
<a href="%ATTACHURLPATH%/szoci2.jpg">szoci2.jpg</a> 
{{InLineFileLink|Gazdhuman|SzocioLogia|SzoczhA.doc|Kidolgozott ZH A csop}} 
{{InLineFileLink|Gazdhuman|SzocioLogia|SzoczhB.doc|Kidolgozott ZH B csop}} 
{{InLineFileLink|Gazdhuman|SzocioLogia|szociologia_eloadas_vazlatok.zip|előadás vázlat}} 

==első zh anyaga: ==
<a href="%ATTACHURLPATH%/szoc.zip">szoc.zip</a> 

==Vélemények==

===[[DonGatto|Liba]] - 2008.05.30.===

Az első órán tömött heringpartiba torkollott tolakodás az ST kicsi termébe, ahol vagy 150 ember egymáson nyomorog a padok között, levegőt alig kapva. Csigó elöl áll és megszeppenve nézi az egybegyűlt tömeget és nagy meghatódottsággal néz végig rajtunk csürhén, valószínűleg tudva, hogy az évben ezen kívül csak egy alkalom lesz, ahol ennyien fogunk ülni az óráján, márpedig az évzáró zéhá. (igen, csak EGY zéhá volt.)
Az első óra csupán 40 percig tartott, aholis elmondta azt, amibe annyira nem is volt biztos, egy zéhá blabla, majd egy srác erősen körülírva rákérdezett arra, hogy mennyire lesz katalógus, és mivel a tömeg annyira nem figyelt, a tanárúr megismételte a kérdést:

"Tehát a kollega arra kíváncsi, hogy be kell-e járni az órára. A válasz NEM! Mindenkivel jobbat tesznek akkor, ha csak beszélgetni jönnének be. A tananyagot derítsék majd ki, és tisztelettel megkérem azokat, akik csak beszélgetni jönnének be, hogy NE tegyék."

Észrevétel teljesen jogos, a halk morajlás erőteljesebbé válik. Következő órán 15-20-an voltunk.
Akit érdekel a tárgy valamilyen szinten, egy kis kúltúrtágításnak tökéletes, én szerettem bejárni, érdekes volt. A könyvek amiket feladott, egész tűrhetőek, kicsit sok bennük a "felesleges" statisztikai adat, dehát mindenki tud scrollozni. ZH-n a 2 elolvasandó könyv (50-70 oldal darabonként (csak az egyiket olvastam)) egykét fogalmára meg statisztikai adatára kérdeznek rá :-)
Ha elég a négyes (ahogy nekem) neveket nem kell tudnod, a többi meg ragad, ha egyszer elolvasod. iq-ból is el lehet menni, az olyan 2-3. Megbukni nem nagyon lehet. (ha nem felejted el mikor van a zh :) de rákövetkező héten (utolsó) van pótlási/javítási lehetőség)

Összességében tarisznyás kétkredit. És még érdekes is (szerintem). Érdekes témákról beszélgettünk órákon. Csak ajánlani tudom.

-- [[DonGatto|Liba]] - 2008.05.30.

===[[ismeretlen]] - 2013.02.15.===
Igazából megvárhatnám a félév végét, hogy akkor egy átfogóbb tapasztalatot osszak meg, de úgy érzem már most is szereztem olyan tapasztalatokat, ami hasznos lehet a későbbi tárgyfelvételek során, a döntések meghozatalában (hogy milyen tárgyat vegyünk vagy ne vegyünk fel). Ettől függetlenül remélem meglesz a tárgy, de másnak csak alapos megfontolás után ajánlanám, vagy még akkor se. Majd kiderül mennyire nehéz, elsőre ránézésre átlagos szabválnak tűnik, de amit eddig hallottam előadáson, az szerintem olyan élmény volt, amit ha más villamosmérnök / informatikus is hallana, sokuknak spontán agyvérzése / szívrohama lenne. Csak erős idegzetűeknek! Megtanuljuk hogy milyen fura dolog hogy a pénznek értéket tulajdonítunk pedig csak papír. Megtanuljuk hogy nem illik nők mellét fogdosni a villamoson. Megtanuljuk hogy 50-60 évvel ezelőtt a fiatalok szerettek az E épületben d...ni (így ezekkel a szavakkal), és még hasonló olyan dolgokat, ami 1) vagy nem érdekel senkit 2) vagy már két-három éves korunk óta tudjuk. De nem ez az ijesztő. Az ijesztő az, hogy van aki ilyen témákból írja a PhD-dolgozatát. Egy igazi villanyos fizika/matek szerű óra után beülni egy ilyenre nagyon furcsa érzés. Olyan mint egy nagy pofon, hogy örüljünk hogy villanyosok vagyunk, és új erőt ad az értelmes dolgok tanulásához :-) Talán ezért esetleg megéri felvenni, másért nem hiszem. Két kreditet nem ér egy szívroham.

==2010. őszi félév==
A mióta 4 darab kifejtős kérdés van a zh-n azóta a kérdések nem sokat változtak. Lentebb a kidolgozásuk is megtalálható. Plusz infó: az előadó Zh közben általában nem tart nagy szigort.

* {{InLineFileLink|Gazdhuman|SzocioLogia|szoc.zip|szoc.zip}}: Első ZH anyaga

* {{InLineFileLink|Gazdhuman|SzocioLogia|Szociolgia1Zhkidolozs.docx|Szociolgia1Zhkidolozs.docx}}: Szociológia 1. zh kidolgozva 2010 ősz

%META:FORM{name="GazdhumanForm"}%
%META:FIELD{name="Trgy" title="Tárgy" value="Szociológia"}%
%META:FIELD{name="Trgykd" title="Tárgykód" value="BMEGT43A002"}%
%META:FIELD{name="Tanszk" title="Tanszék" value="Szociológia és Kommunikáció Tanszék"}%
%META:FIELD{name="Elad" title="Előadó" value="Szakadát István dr."}%
%META:FIELD{name="Kreditszm" title="Kreditszám" value="2"}%
%META:FIELD{name="raszm" title="Óraszám" value="2"}%
%META:FIELD{name="Tmakr" title="Témakör" value="filozófia-szociológia-vallás"}%
%META:FIELD{name="raijelenlt" title="Órai jelenlét" value="nem kötelező"}%
%META:FIELD{name="Jegy" title="Jegy" value="zh"}%
%META:FIELD{name="Elvrtmin.munka" title="Elvárt min. munka" value="semmi"}%
%META:FIELD{name="Minimumrajrjegy" title="Minimumra járó jegy" value="3"}%
%META:FIELD{name="Elvrtmax.munka" title="Elvárt max. munka" value="kis utánaolvasás - kis munka"}%
%META:FIELD{name="Munkrajrjegy" title="Munkára járó jegy" value="5"}%

[[Category:Gazdhuman]]