A számítástudomány alapjai - Segédanyagok a vizsgához - Laptörténet

Szikszayl, 2014. március 13., 14:00-n

2014-03-13T14:00:44Z

← Régebbi változat		A lap 2014. március 13., 16:00-kori változata
569. sor:		569. sor:


			[[Kategória:Villamosmérnök]]

	[[Kategória:~~Villanyalap~~]]

David14, 2014. január 13., 15:46-n

2014-01-13T15:46:26Z

← Régebbi változat		A lap 2014. január 13., 17:46-kori változata
1. sor:		1. sor:
	{{Vissza\|A számítástudomány alapjai}}		{{Vissza\|A számítástudomány alapjai}}
	__NOTOC__		__NOTOC__

			Ezen az oldalon van összegyűjtve az egyes témakörökhöz szükséges alapismeretek - Definíciók, fogalmal és algoritmusok.

			'''FIGYELEM:''' Mivel itt nincsenek bizonyítások, így ez az ismeretanyag csupán az elégséges szintje! Valamint az érdemes előtte áttanulmányozni az aktuális tételsort, ami elérhető a tanszéki honlapon! Az évek során ugyanis kismértékben változhatott a tárgytematika.

	'''''A kidolgozásokban hibák előfordulhatnak!'''''		'''''A kidolgozásokban hibák előfordulhatnak!'''''

			Ha hibát találsz bátran javítsd! Ha időd engedi bővítsd!


	==1. Leszámlálási alapfogalmak (permutációk, variációk és kombinációk, ismétlés nélkül, vagy ismétléssel), binomiális tétel, szita-formula==		==1. Leszámlálási alapfogalmak (permutációk, variációk és kombinációk, ismétlés nélkül, vagy ismétléssel), binomiális tétel, szita-formula==

David14: /* Algoritmusok, eljárások és egyebek */

2014-01-13T15:41:46Z

Algoritmusok, eljárások és egyebek

← Régebbi változat		A lap 2014. január 13., 17:41-kori változata
454. sor:		454. sor:
	===Algoritmusok, eljárások és egyebek===		===Algoritmusok, eljárások és egyebek===
	* Euklideszi algoritmus: polinomrendű algoritmus két szám (_a_ és _b_) legnagyobb közös osztójának meghatározására. Tegyük fel, hogy <math>a>b</math>, ekkor:		* Euklideszi algoritmus: polinomrendű algoritmus két szám (_a_ és _b_) legnagyobb közös osztójának meghatározására. Tegyük fel, hogy <math>a>b</math>, ekkor:
	## Felírjuk a nagyobb számot, mint a kisebb számmal vett hányados és a kisebb szám sorzata, valamint az osztási maradék összegeként: <math> a = h_1 b + m_1 </math>.		*# Felírjuk a nagyobb számot, mint a kisebb számmal vett hányados és a kisebb szám sorzata, valamint az osztási maradék összegeként: <math> a = h_1 b + m_1 </math>.
	## Az egészet "balra shifteljük": <math> b = h_2 m_1 + m_2 </math>, majd megint: <math> m_1 = h_3 m_2 + m_m </math>, és így tovább.		*# Az egészet "balra shifteljük": <math> b = h_2 m_1 + m_2 </math>, majd megint: <math> m_1 = h_3 m_2 + m_m </math>, és így tovább.
	## Egészen addig, amíg az nem lesz, hogy <math> m_n = h_{n+2} m_{n+1} + 0 </math>. Ekkor <math> m_{n+1} </math> a lnko.		*# Egészen addig, amíg az nem lesz, hogy <math> m_n = h_{n+2} m_{n+1} + 0 </math>. Ekkor <math> m_{n+1} </math> a lnko.


	==16. Kongruencia fogalma, teljes és redukált maradékrendszer, <math>\varphi</math>-függvény, Euler-Fermat-tétel, kis-Fermat-tétel, lineáris kongruenciák megoldása, Wilson-tétel==		==16. Kongruencia fogalma, teljes és redukált maradékrendszer, <math>\varphi</math>-függvény, Euler-Fermat-tétel, kis-Fermat-tétel, lineáris kongruenciák megoldása, Wilson-tétel==

David14: /* 13. Keresési, beszúrási és rendezési algoritmusok (beszúrásos, buborék, összefésülés, láda), alsó korlátok a lépésszámokra, gráfok tárolása */

2014-01-13T15:41:28Z

13. Keresési, beszúrási és rendezési algoritmusok (beszúrásos, buborék, összefésülés, láda), alsó korlátok a lépésszámokra, gráfok tárolása

David14: /* Algoritmusok, eljárások és egyebek */

2014-01-13T15:39:10Z

Algoritmusok, eljárások és egyebek

David14: /* Tételek és összefüggések */

2014-01-13T15:38:05Z

Tételek és összefüggések

← Régebbi változat		A lap 2014. január 13., 17:38-kori változata
312. sor:		312. sor:
	** Egy gráfnak csak akkor létezik absztrakt duálisa, ha síkbarajzolható.		** Egy gráfnak csak akkor létezik absztrakt duálisa, ha síkbarajzolható.
	** Egy gráf akkor és csak akkor gyengén izomorf egy másikkal, ha az alábbi három lépés ismételgetésével vele izomorf gráfot tudunk létrehozni:		** Egy gráf akkor és csak akkor gyengén izomorf egy másikkal, ha az alábbi három lépés ismételgetésével vele izomorf gráfot tudunk létrehozni:
	### Ha a gráfnak van olyan pontja, aminek elhagyásával a gráf két komponensre esne, akkor ezt a pontot megkettőzve "húzzúk szét" a gráfot két komponensre.		**# Ha a gráfnak van olyan pontja, aminek elhagyásával a gráf két komponensre esne, akkor ezt a pontot megkettőzve "húzzúk szét" a gráfot két komponensre.
	### Az előbbi lépés inverze: kétkomponensű gráfban mindkét komponensből válasszunk ki egy-egy pontot és ezeknél fogva "ragasszuk össze" a két komponenst.		**# Az előbbi lépés inverze: kétkomponensű gráfban mindkét komponensből válasszunk ki egy-egy pontot és ezeknél fogva "ragasszuk össze" a két komponenst.
	### Ha a gráfnak van két olyan pontja, melyek elhagyásával a gráf két komponensre esne, akkor e pontokat megkettőzve "húzzúk szét" a gráfot két komponensre, gondolatban "tükrözzük" az egyik komponenst, majd a két pont mentén "ragasszuk össze" fordítva.		**# Ha a gráfnak van két olyan pontja, melyek elhagyásával a gráf két komponensre esne, akkor e pontokat megkettőzve "húzzúk szét" a gráfot két komponensre, gondolatban "tükrözzük" az egyik komponenst, majd a két pont mentén "ragasszuk össze" fordítva.
	* Ötszín-tétel: ha egy gráf síkbarajzolható, a kromatikus száma kisebb, vagy egyenlő, mint öt.		* Ötszín-tétel: ha egy gráf síkbarajzolható, a kromatikus száma kisebb, vagy egyenlő, mint öt.
	* Vizing-tétel: ha egy gráf egyszerű, akkor az élkromatikus száma kisebb, vagy egyenlő, mint a gráfban a legnagyobb előforduló fokszám plusz egy.		* Vizing-tétel: ha egy gráf egyszerű, akkor az élkromatikus száma kisebb, vagy egyenlő, mint a gráfban a legnagyobb előforduló fokszám plusz egy.

David14: /* 10. Síkbarajzolhatóság, Euler-féle poliédertétel, Kuratowski tétele (csak könnyű irányban bizonyítani), Fáry-Wagner-tétel (bizonyítás nélkül) */

2014-01-13T15:37:47Z

10. Síkbarajzolhatóság, Euler-féle poliédertétel, Kuratowski tétele (csak könnyű irányban bizonyítani), Fáry-Wagner-tétel (bizonyítás nélkül)

David14: /* Algoritmusok, eljárások és egyebek */

2014-01-13T15:37:21Z

Algoritmusok, eljárások és egyebek

← Régebbi változat		A lap 2014. január 13., 17:37-kori változata
265. sor:		265. sor:
	===Algoritmusok, eljárások és egyebek===		===Algoritmusok, eljárások és egyebek===
	* Mycielski-konstrukció: egy n pontú gráfhoz egy olyan gráfot rendel, amelyben feszített részgráfként szerepel az eredeti gráf és még <math>n+1</math> pont, a következők szerint:		* Mycielski-konstrukció: egy n pontú gráfhoz egy olyan gráfot rendel, amelyben feszített részgráfként szerepel az eredeti gráf és még <math>n+1</math> pont, a következők szerint:
	## Rajzoljuk le az eredeti gráf <math>v_1,...,v_n</math> pontjait a köztük lévő élekkel együtt.		*# Rajzoljuk le az eredeti gráf <math>v_1,...,v_n</math> pontjait a köztük lévő élekkel együtt.
	## Rajzuljunk további n darab, <math>u_1,...,u_n</math> pontot, úgy, hogy az <math>u_i</math> pontnak ugyanazok legyenek a szomszédai, mint amik a <math>v_i</math>-nek is szomszédai <math>\forall i</math>-re.		*# Rajzuljunk további n darab, <math>u_1,...,u_n</math> pontot, úgy, hogy az <math>u_i</math> pontnak ugyanazok legyenek a szomszédai, mint amik a <math>v_i</math>-nek is szomszédai <math>\forall i</math>-re.
	## Rajzoljunk továbbá egy w pontot, amelyiket kössünk össze minden <math>u_i</math> ponttal, de ne kössünk össze egy <math>v_i</math>-vel sem.		*# Rajzoljunk továbbá egy w pontot, amelyiket kössünk össze minden <math>u_i</math> ponttal, de ne kössünk össze egy <math>v_i</math>-vel sem.
	## Állítás: ha <math>n\leq 2</math>, olyan gráfot rajzoltunk, ami megfelel a Mycielski-tételnek.		*# Állítás: ha <math>n\leq 2</math>, olyan gráfot rajzoltunk, ami megfelel a Mycielski-tételnek.


	==10. Síkbarajzolhatóság, Euler-féle poliédertétel, Kuratowski tétele (csak könnyű irányban bizonyítani), Fáry-Wagner-tétel (bizonyítás nélkül)==		==10. Síkbarajzolhatóság, Euler-féle poliédertétel, Kuratowski tétele (csak könnyű irányban bizonyítani), Fáry-Wagner-tétel (bizonyítás nélkül)==

David14: /* Algoritmusok, eljárások és egyebek */

2014-01-13T15:36:30Z

Algoritmusok, eljárások és egyebek

David14: /* Algoritmusok, eljárások és egyebek */

2014-01-13T15:35:06Z

Algoritmusok, eljárások és egyebek

← Régebbi változat		A lap 2014. január 13., 17:35-kori változata
93. sor:		93. sor:
	===Algoritmusok, eljárások és egyebek===		===Algoritmusok, eljárások és egyebek===
	* Kruskal-algoritmus: minimális súlyú feszítőerdőt talál egy gráfban		* Kruskal-algoritmus: minimális súlyú feszítőerdőt talál egy gráfban
	## Kiválasztjuk az összes él közül valamelyik legkisebb súlyút.		*# Kiválasztjuk az összes él közül valamelyik legkisebb súlyút.
	## Kiválasztjuk a maradék élek közül azt a legkisebb súlyút, ami a már kiválasztottakkal nem alkot kört.		*# Kiválasztjuk a maradék élek közül azt a legkisebb súlyút, ami a már kiválasztottakkal nem alkot kört.
	## Addig ismételgetjük a 2. pontot, amíg minden pontját le nem fedtük a gráfnak.		*# Addig ismételgetjük a 2. pontot, amíg minden pontját le nem fedtük a gráfnak.
	* Prüfer-kód felírása		* Prüfer-kód felírása
	## Számozzuk meg a fa pontjait tetszőleges sorrendben.		*# Számozzuk meg a fa pontjait tetszőleges sorrendben.
	## Töröljük le a fa elsőfokú pontjai közül azt, amelyiknek a legkisebb a száma és jegyezzük fel a szomszédja számát.		*# Töröljük le a fa elsőfokú pontjai közül azt, amelyiknek a legkisebb a száma és jegyezzük fel a szomszédja számát.
	## Ezt ismételgessük addig, amíg csak tudjuk.		*# Ezt ismételgessük addig, amíg csak tudjuk.


	==3. Euler-séta és -körséta (Euler-út, -kör) fogalma, szükséges és elégséges feltétel a létezésükre, Hamilton-kör és -út, szükséges, illetve, elégséges feltételek Hamilton-kör létezésére==		==3. Euler-séta és -körséta (Euler-út, -kör) fogalma, szükséges és elégséges feltétel a létezésükre, Hamilton-kör és -út, szükséges, illetve, elégséges feltételek Hamilton-kör létezésére==

← Régebbi változat		A lap 2014. január 13., 17:41-kori változata
379. sor:		379. sor:
	* Szomszédossági tömb: a gráf csúcsainak a száma mellé egyszerűen felírjuk a szomszédos csúcsok számát.		* Szomszédossági tömb: a gráf csúcsainak a száma mellé egyszerűen felírjuk a szomszédos csúcsok számát.
	* Láncolt szomszédossági lista		* Láncolt szomszédossági lista
	## Felírjuk egy "szomszéd" listába a csúcsok ''szomszédainak'' a számát, tetszőleges sorrendben. (Egy pont többször is szerepelhet, ha jól csináltuk, akkor ebben a lépésben az élszám kétszerese darab számot írtunk fel.)		*# Felírjuk egy "szomszéd" listába a csúcsok ''szomszédainak'' a számát, tetszőleges sorrendben. (Egy pont többször is szerepelhet, ha jól csináltuk, akkor ebben a lépésben az élszám kétszerese darab számot írtunk fel.)
	## Felírjuk egy másik, "kezdés" listának ''n.'' helyére, hogy a gráf ''n.'' csúcsának szomszédainak felsorolása a "szomszéd" listában hanyadik helyen kezdődik. (Nem feltétlenül kell, hogy a "szomszéd" listában egymás mellett legyenek, csak, hogy hol az első, azt írjuk most fel.)		*# Felírjuk egy másik, "kezdés" listának ''n.'' helyére, hogy a gráf ''n.'' csúcsának szomszédainak felsorolása a "szomszéd" listában hanyadik helyen kezdődik. (Nem feltétlenül kell, hogy a "szomszéd" listában egymás mellett legyenek, csak, hogy hol az első, azt írjuk most fel.)
	## Felírjuk a harmadik, "folytat" lista ''n.'' helyére, hogy a "szomszéd" lista ''n.'' helyén álló sorszám után a "szomszéd" lista hanyadik helyére kell ugrani a következő szomszéd sorszámának kiolvasásához.		*# Felírjuk a harmadik, "folytat" lista ''n.'' helyére, hogy a "szomszéd" lista ''n.'' helyén álló sorszám után a "szomszéd" lista hanyadik helyére kell ugrani a következő szomszéd sorszámának kiolvasásához.

	===Tételek és összefüggések===		===Tételek és összefüggések===
389. sor:		389. sor:
	* Logaritmikus keresés: ez rendezett tömbre működik. Megnézi, hogy a keresett elem a tömb alsó, vagy felső felében van-e? Ha az alsóban, akkor a felső felét eldobja és megnézi, hogy az alsó fél alsó felében, vagy felső felében van-e? Satöbbi, amíg egy elem nem marad és azzal komparál. Előny: gyors, de nem működik mindig. _n_ elemre legrosszabb esetben is kb. <math> \log_2 n </math> lépés alatt lefut.		* Logaritmikus keresés: ez rendezett tömbre működik. Megnézi, hogy a keresett elem a tömb alsó, vagy felső felében van-e? Ha az alsóban, akkor a felső felét eldobja és megnézi, hogy az alsó fél alsó felében, vagy felső felében van-e? Satöbbi, amíg egy elem nem marad és azzal komparál. Előny: gyors, de nem működik mindig. _n_ elemre legrosszabb esetben is kb. <math> \log_2 n </math> lépés alatt lefut.
	* Beszúrásos rendezés		* Beszúrásos rendezés
	## Kiválasztjuk a tömb első elemét. Ez így egyedül egy rendezett tömböt alkot.		*# Kiválasztjuk a tömb első elemét. Ez így egyedül egy rendezett tömböt alkot.
	## Hozzávesszük a másodikat. Ha a második kisebb, mint az első, kicseréljük, ha nagyobb, békén hagyjuk. Így már van egy 2-hosszú rendezett tömbünk.		*# Hozzávesszük a másodikat. Ha a második kisebb, mint az első, kicseréljük, ha nagyobb, békén hagyjuk. Így már van egy 2-hosszú rendezett tömbünk.
	## Vesszük a harmadikat. Ha nagyobb, mint a második, hagyjuk, ha kisebb, megcseréljük, majd összehasonlítjuk az elsővel is.		*# Vesszük a harmadikat. Ha nagyobb, mint a második, hagyjuk, ha kisebb, megcseréljük, majd összehasonlítjuk az elsővel is.
	## Satöbbi. Mindig vesszök a következő elemet és a már rendezett részben leengedjük odáig, amíg egy nálánál kisebbet nem találunk.		*# Satöbbi. Mindig vesszök a következő elemet és a már rendezett részben leengedjük odáig, amíg egy nálánál kisebbet nem találunk.
	** Előny: kevesebb komparálást igényel, mint a buborék, illetve könnyűvé teszi egy új elem beszúrását bármikor. Átlagos lépésszám <math> ~n^2 </math>.		** Előny: kevesebb komparálást igényel, mint a buborék, illetve könnyűvé teszi egy új elem beszúrását bármikor. Átlagos lépésszám <math> ~n^2 </math>.
	* Összefésüléses rendezés		* Összefésüléses rendezés
	## Az összefésülési lépés, ami a kulcsa az egész dolognak, úgy néz ki, hogy fogunk egy _n_ hosszú és egy _m_ hosszú, rendezett tömböt, és ~~berakosgatjuk~~ az elemeiket egy <math>n+m</math> hosszú új tömbbe, úgy, hogy először összehasonlítjuk az első elemeiket, amelyik a kisebb, az megy előre, és ahonnan kivettük, lépünk egyet, újra komparálunk, stb., míg végül lesz egy <math> n+m </math> hosszú, rendezett tömbünk.		*# Az összefésülési lépés, ami a kulcsa az egész dolognak, úgy néz ki, hogy fogunk egy _n_ hosszú és egy _m_ hosszú, rendezett tömböt, és lerakosgatjuk az elemeiket egy <math>n+m</math> hosszú új tömbbe, úgy, hogy először összehasonlítjuk az első elemeiket, amelyik a kisebb, az megy előre, és ahonnan kivettük, lépünk egyet, újra komparálunk, stb., míg végül lesz egy <math> n+m </math> hosszú, rendezett tömbünk.
	## A kezdeti, rendezetlen, _k_ hosszú tömbre ezután úgy tekintünk, mint _k_ darab, rendezett, 1 hosszú tömbökre.		*# A kezdeti, rendezetlen, _k_ hosszú tömbre ezután úgy tekintünk, mint _k_ darab, rendezett, 1 hosszú tömbökre.
	## Ezeket összefésüljük <math> k/2 </math> darab, 2 hosszú tömbbé, majd azokat négyesekké, nyolcasokká, satöbbi, amíg meg nem kapjuk a _k_ hosszú rendezett tömböt.		*# Ezeket összefésüljük <math> k/2 </math> darab, 2 hosszú tömbbé, majd azokat négyesekké, nyolcasokká, satöbbi, amíg meg nem kapjuk a _k_ hosszú rendezett tömböt.
	** Előny: gyors és egyszerű. Hátrány: minden egyes összefésülési lépés újabb területet zabál fel a memóriából. Átlagos lépésszám: <math> ~n\log n </math>.		** Előny: gyors és egyszerű. Hátrány: minden egyes összefésülési lépés újabb területet zabál fel a memóriából. Átlagos lépésszám: <math> ~n\log n </math>.
	* Buborék-rendezés		* Buborék-rendezés
	## Párosával összehasonlítgatjuk a két legkisebb indexű elemet, majd második és a harmadik legkisebb indexű elemet, satöbbi, szépen előre haladva a tömbben párosával komparálunk. Minden lépésben ha kell, kicseréljük a két elemet. Amikor a tömb végére értünk, a legutolsó elem a legnagyobb.		*# Párosával összehasonlítgatjuk a két legkisebb indexű elemet, majd második és a harmadik legkisebb indexű elemet, satöbbi, szépen előre haladva a tömbben párosával komparálunk. Minden lépésben ha kell, kicseréljük a két elemet. Amikor a tömb végére értünk, a legutolsó elem a legnagyobb.
	## Ugyanazt megcsináljuk, mint az előbb, csak már nem kell elmennünk a tömb végéig, hiszen tudjuk, hogy az utolsó elem a legnagyobb.		*# Ugyanazt megcsináljuk, mint az előbb, csak már nem kell elmennünk a tömb végéig, hiszen tudjuk, hogy az utolsó elem a legnagyobb.
	## Addig csinálgatjuk ezt, míg a hátulról növekvő hosszú rendezett szakasz a tömb elejéig nem ér.		*# Addig csinálgatjuk ezt, míg a hátulról növekvő hosszú rendezett szakasz a tömb elejéig nem ér.
	** Egyszerű, de lassú, baromi sokat kell komparálni. Átlagos lépésszám: <math>~n^2</math>.		** Egyszerű, de lassú, baromi sokat kell komparálni. Átlagos lépésszám: <math>~n^2</math>.
	* Láda-rendezés - csak akkor működik, ha tudjuk, hogy csak egész számok jöhetnek és azt is tudjuk, hogy milyen intervallumból		* Láda-rendezés - csak akkor működik, ha tudjuk, hogy csak egész számok jöhetnek és azt is tudjuk, hogy milyen intervallumból
	## Hozzuk létre a ládákat. Hogy hányat, azt az intervallum és a várt elemszám dönti el. Például, ha 20 alatti mennyiségű 0 és 30 közti elemre számítok, akkor elég három láda a 0-9, 10-19, 20-30 közti számoknak, de ha mondjuk tudom, hogy ugyanebben az intervallumban 50 elemem lesz, akkor lehet, hogy 5-ösével pakolnám őket 6 ládába. Nyilván úgy célszerű, hogy egy ládába csak néhány elem jusson végül.		*# Hozzuk létre a ládákat. Hogy hányat, azt az intervallum és a várt elemszám dönti el. Például, ha 20 alatti mennyiségű 0 és 30 közti elemre számítok, akkor elég három láda a 0-9, 10-19, 20-30 közti számoknak, de ha mondjuk tudom, hogy ugyanebben az intervallumban 50 elemem lesz, akkor lehet, hogy 5-ösével pakolnám őket 6 ládába. Nyilván úgy célszerű, hogy egy ládába csak néhány elem jusson végül.
	## Toszogassuk bele a létrehozott ládákba az elemeinket.		*# Toszogassuk bele a létrehozott ládákba az elemeinket.
	## A ládákon belül rendezzük az elemeket valami kényelmes módon.		*# A ládákon belül rendezzük az elemeket valami kényelmes módon.
	## Sorrendben szedjük ki a ládákból az elemeket.		*# Sorrendben szedjük ki a ládákból az elemeket.
	** Gyors, de kényes módszer, nem olyan egyszerű leprogramozni. Cserébe jó gyorsan tud működni.		** Gyors, de kényes módszer, nem olyan egyszerű leprogramozni. Cserébe jó gyorsan tud működni.


	==14. Problémák bonyolultsága, polinomiális visszavezetés, P, NP, co-NP bonyolultsági osztályok fogalma, feltételezett viszonyuk, NP-teljesség, nevezetes NP-teljes problémák==		==14. Problémák bonyolultsága, polinomiális visszavezetés, P, NP, co-NP bonyolultsági osztályok fogalma, feltételezett viszonyuk, NP-teljesség, nevezetes NP-teljes problémák==

← Régebbi változat		A lap 2014. január 13., 17:39-kori változata
340. sor:		340. sor:
	===Algoritmusok, eljárások és egyebek===		===Algoritmusok, eljárások és egyebek===
	* Mélységi keresés:		* Mélységi keresés:
	## Kiválasztjuk a kiindulási pontot.		*# Kiválasztjuk a kiindulási pontot.
	## Meglátogatjuk a legkisebb sorszámú olyan szomszédját, amit még nem látogattunk meg.		*# Meglátogatjuk a legkisebb sorszámú olyan szomszédját, amit még nem látogattunk meg.
	## Az előbbi lépést ismételgetjük, amíg tudjuk.		*# Az előbbi lépést ismételgetjük, amíg tudjuk.
	## Ha már nem tudunk tovább menni, visszalépünk egyet, és újra megpróbáljuk a 2. lépést, ha még mindig nem jutunk előre, visszamegyünk mégegyet, stb.		*# Ha már nem tudunk tovább menni, visszalépünk egyet, és újra megpróbáljuk a 2. lépést, ha még mindig nem jutunk előre, visszamegyünk mégegyet, stb.
	## Ha a visszalépegetésekkel visszaérünk a kiindulási pontba, akkor a gráf minden pontját láttuk és végeztünk.		*# Ha a visszalépegetésekkel visszaérünk a kiindulási pontba, akkor a gráf minden pontját láttuk és végeztünk.
	* Emeletekre bontás: egy irányított gráf olyan ábrázolási módja, hogy az élek csak az irányuknak megfelelően, a forrástól a nyelő felé mutatnak.		* Emeletekre bontás: egy irányított gráf olyan ábrázolási módja, hogy az élek csak az irányuknak megfelelően, a forrástól a nyelő felé mutatnak.
	* PERT-módszer. Munkafolyamatok ütemezésére jó.		* PERT-módszer. Munkafolyamatok ütemezésére jó.
	## Hozzávalók egy személyre:		*# Hozzávalók egy személyre:
	*** egy élsúlyozott irányított gráf, amiben nincs irányított kör, viszont van benne egy forrás és egy nyelő,		# Egy élsúlyozott irányított gráf, amiben nincs irányított kör, viszont van benne egy forrás és egy nyelő,
	*** sör, bacon, vidámság, szánsájn, szikla és zsömle,		# Sör, bacon, vidámság, szánsájn, szikla és zsömle,
	*** számtud-tudás.		# Számtud-tudás.
	## A gráfot emeletekre bontjuk. Egyrészt, mert poén, másrészt, mert áttekinthetőbbé teszi a munkát, harmadrészt, mert ezzel ellenőrizzük, hogy tényleg nincs-e benne irányított kör (ha van, nem tudjuk emeletekre bontani).		*# A gráfot emeletekre bontjuk. Egyrészt, mert poén, másrészt, mert áttekinthetőbbé teszi a munkát, harmadrészt, mert ezzel ellenőrizzük, hogy tényleg nincs-e benne irányított kör (ha van, nem tudjuk emeletekre bontani).
	## A kritikus utat keressük, vagyis a leghosszabb utat. Ez nyilván úgy történik, hogy pontonként felírogatjuk, hogy oda honnan, összesen mennyi idő alatt tudunk jutni, és a nagyobbat választjuk.		*# A kritikus utat keressük, vagyis a leghosszabb utat. Ez nyilván úgy történik, hogy pontonként felírogatjuk, hogy oda honnan, összesen mennyi idő alatt tudunk jutni, és a nagyobbat választjuk.
	## Ha megvan a kritikus út, akkor igazából végeztünk. A kritikus úton található munkafolyamatok azok, amikkel, ha késünk, akkor késleltetjük a gráf által reprezentált egész projekt elkészültét. Persze a kritikus úton kívül eső folyamatokkal sem várhatunk a végtelenségig, de azok esetében néhány időegységnyi tűrés van.		*# Ha megvan a kritikus út, akkor igazából végeztünk. A kritikus úton található munkafolyamatok azok, amikkel, ha késünk, akkor késleltetjük a gráf által reprezentált egész projekt elkészültét. Persze a kritikus úton kívül eső folyamatokkal sem várhatunk a végtelenségig, de azok esetében néhány időegységnyi tűrés van.


	==13. Keresési, beszúrási és rendezési algoritmusok (beszúrásos, buborék, összefésülés, láda), alsó korlátok a lépésszámokra, gráfok tárolása==		==13. Keresési, beszúrási és rendezési algoritmusok (beszúrásos, buborék, összefésülés, láda), alsó korlátok a lépésszámokra, gráfok tárolása==

← Régebbi változat		A lap 2014. január 13., 17:37-kori változata
281. sor:		281. sor:
	* Kuratowski-gráf: az ötpontú teljes gráf <math>K_5</math> és a három-három pontú teljes páros gráf <math>K_{3,3}</math>.		* Kuratowski-gráf: az ötpontú teljes gráf <math>K_5</math> és a három-három pontú teljes páros gráf <math>K_{3,3}</math>.
	* Topologikus izomorfia: két gráf topologikusan izomorf, ha a következő két művelet alkalmazásával izomorf gráfok hozhatók létre belőlük:		* Topologikus izomorfia: két gráf topologikusan izomorf, ha a következő két művelet alkalmazásával izomorf gráfok hozhatók létre belőlük:
	## Egy él "közepére" egy pont beszúrása, vagyis egy él 2-hosszú úttal való helyettesítése.		*# Egy él "közepére" egy pont beszúrása, vagyis egy él 2-hosszú úttal való helyettesítése.
	## Egy pont "középről" való eltüntetése, vagyis egy 2-hosszú út éllel való helyettesítése.		*# Egy pont "középről" való eltüntetése, vagyis egy 2-hosszú út éllel való helyettesítése.

	===Tételek és összefüggések===		===Tételek és összefüggések===
292. sor:		292. sor:
	===Algoritmusok, eljárások és egyebek===		===Algoritmusok, eljárások és egyebek===
	* Sztereografikus projekció - síkgráf gömbre rajzolása.		* Sztereografikus projekció - síkgráf gömbre rajzolása.
	## Tegyük a gömböt a síkra.		*# Tegyük a gömböt a síkra.
	## Ahol a gömb a síkkal érintkezik, legyen a déli pólus.		*# Ahol a gömb a síkkal érintkezik, legyen a déli pólus.
	## Az északi pólust összekötjük a síkon a gráf pontjaival.		*# Az északi pólust összekötjük a síkon a gráf pontjaival.
	## Ahol az egyenesek metszik a gömb felszínét, azok a gömbre rajzolt gráf megfelelő pontjai.		*# Ahol az egyenesek metszik a gömb felszínét, azok a gömbre rajzolt gráf megfelelő pontjai.
	## Az eljárás megfordítható, ha az északi póluson nincs pont és nem is megy át él.		*# Az eljárás megfordítható, ha az északi póluson nincs pont és nem is megy át él.


	==11. Dualitás, gyenge izomorfia, Whitney tételei (bizonyítás nélkül), síkgráfok színezése, ötszíntétel==		==11. Dualitás, gyenge izomorfia, Whitney tételei (bizonyítás nélkül), síkgráfok színezése, ötszíntétel==

← Régebbi változat		A lap 2014. január 13., 17:36-kori változata
137. sor:		137. sor:
	===Algoritmusok, eljárások és egyebek===		===Algoritmusok, eljárások és egyebek===
	* BFS: nem élsúlyozott esetben használjuk		* BFS: nem élsúlyozott esetben használjuk
	## Kiválasztjuk a kezdőpontot és megjelöljük		*# Kiválasztjuk a kezdőpontot és megjelöljük
	## Meglátogatjuk az összes szomszédját, ahol még nem voltunk.		*# Meglátogatjuk az összes szomszédját, ahol még nem voltunk.
	## Miután elfogytak a megjelölt pont még meg nem látogatott szomszédai, áttérünk a meglátogatott szomszédok közül a legkisebb indexűre és megjelöljük.		*# Miután elfogytak a megjelölt pont még meg nem látogatott szomszédai, áttérünk a meglátogatott szomszédok közül a legkisebb indexűre és megjelöljük.
	## Az előbbi két pontot ismételgetjük, amíg csak tudjuk.		*# Az előbbi két pontot ismételgetjük, amíg csak tudjuk.
	* Dijkstra-algoritmus: élsúlyozott esetben használjuk		* Dijkstra-algoritmus: élsúlyozott esetben használjuk
	## Kiválasztjuk a kezdőpontot.		*# Kiválasztjuk a kezdőpontot.
	## Felírjuk, hogy a kezdőpont mely szomszédjaiba milyen áron lehet eljutni. Amely pontba nem tudunk egy lépésben eljutni, azt végtelen eljutási költségnek jelöljük.		*# Felírjuk, hogy a kezdőpont mely szomszédjaiba milyen áron lehet eljutni. Amely pontba nem tudunk egy lépésben eljutni, azt végtelen eljutási költségnek jelöljük.
	## Megnézzük, hogy a kiindulópontból hová juthatunk el a legolcsóbban, majd "felfedezzük" annak a pontnak a szomszédságát: felírjuk, hogy a '''kezdőpontból''' milyen költséggel juthatunk el ennek a pontnak a szomszédaihoz. Ha egy ponthoz olcsóbb eljutási lehetőséget találtunk, javítjuk. Ahol nem tudtunk javítani, változatlanul hagyjuk.		*# Megnézzük, hogy a kiindulópontból hová juthatunk el a legolcsóbban, majd "felfedezzük" annak a pontnak a szomszédságát: felírjuk, hogy a '''kezdőpontból''' milyen költséggel juthatunk el ennek a pontnak a szomszédaihoz. Ha egy ponthoz olcsóbb eljutási lehetőséget találtunk, javítjuk. Ahol nem tudtunk javítani, változatlanul hagyjuk.
	## Az előző pontot ismételgetjük addig, amíg már egy pontból sem tudunk javítani.		*# Az előző pontot ismételgetjük addig, amíg már egy pontból sem tudunk javítani.
	* Ford-algoritmus: olyan esetben használjuk, ha a gráfban nincs negatív összsúlyú irányított kör. Ez az algoritmus nagyjából úgy működik, mint a Dijkstra brute force üzemmódban.		* Ford-algoritmus: olyan esetben használjuk, ha a gráfban nincs negatív összsúlyú irányított kör. Ez az algoritmus nagyjából úgy működik, mint a Dijkstra brute force üzemmódban.
	## Megszámozzuk az éleket tetszőleges sorrendben.		*# Megszámozzuk az éleket tetszőleges sorrendben.
	## Felírjuk, hogy a kiindulópontba 0 költségen, minden más pontba végtelen költségen juthatunk el.		*# Felírjuk, hogy a kiindulópontba 0 költségen, minden más pontba végtelen költségen juthatunk el.
	## Számsorrendben, agyatlanul elkezdjük sorba venni az éleket és a Dijkstra-féle javítást próbáljuk elvégezni. Függetlenül attól, hogy mondjuk az adott él nagyon messze van a kiindulóponttól, és adott esetben egy olyan javítást akarunk elvégezni, hogy "ebbe a pontba végtelen költségen jutottam, tehát ennek a szomsédjába végtelen + 2-ért tudok". Ilyenkor belenyugszunk, hogy nem tudtunk javítani és vesszük a következő számú élt, hátha amentén tudunk.		*# Számsorrendben, agyatlanul elkezdjük sorba venni az éleket és a Dijkstra-féle javítást próbáljuk elvégezni. Függetlenül attól, hogy mondjuk az adott él nagyon messze van a kiindulóponttól, és adott esetben egy olyan javítást akarunk elvégezni, hogy "ebbe a pontba végtelen költségen jutottam, tehát ennek a szomsédjába végtelen + 2-ért tudok". Ilyenkor belenyugszunk, hogy nem tudtunk javítani és vesszük a következő számú élt, hátha amentén tudunk.
	## Az előbbi lépést ismételgetjük, addig, amíg a pontok számánál egyel kevesebbszer végig nem pörgettük az összes élt.		*# Az előbbi lépést ismételgetjük, addig, amíg a pontok számánál egyel kevesebbszer végig nem pörgettük az összes élt.
	* Floyd-algoritmus: olyan esetben használjuk, ha a gráfban nincs negatív összsúlyú irányított kör.		* Floyd-algoritmus: olyan esetben használjuk, ha a gráfban nincs negatív összsúlyú irányított kör.
	## Számozzuk meg a pontokat 1-től n-ig. Ez az algoritmus végigmegy minden ponton és ellenőrzi, hogy az adott ponton keresztül van-e rövidebb út bármely két pontpár között.		*# Számozzuk meg a pontokat 1-től n-ig. Ez az algoritmus végigmegy minden ponton és ellenőrzi, hogy az adott ponton keresztül van-e rövidebb út bármely két pontpár között.
	## Először rögzítsük, hogy az 1. ponton keresztül vezető utak hosszát keressük. (Ez legyen a "köztes állomás".)		*# Először rögzítsük, hogy az 1. ponton keresztül vezető utak hosszát keressük. (Ez legyen a "köztes állomás".)
	## Majd rögzítsük, hogy az 1. pontból, az 1. ponton keresztül vezető utak hosszát keressük.		*# Majd rögzítsük, hogy az 1. pontból, az 1. ponton keresztül vezető utak hosszát keressük.
	## Majd futtassuk végig, hogy az 1. pontból, az 1. ponton keresztül az 1., 2., 3., ... n. pontba milyen hosszúságú út vezet. Igen, a legelső lépésben az lesz az ellenőrzés tárgya, hogy "az 1. pontból az 1. pontba, majd az 1. pontból az 1. pontba vezető út rövidebb-e, mint az 1. pontból az 1. pontba vezető?".		*# Majd futtassuk végig, hogy az 1. pontból, az 1. ponton keresztül az 1., 2., 3., ... n. pontba milyen hosszúságú út vezet. Igen, a legelső lépésben az lesz az ellenőrzés tárgya, hogy "az 1. pontból az 1. pontba, majd az 1. pontból az 1. pontba vezető út rövidebb-e, mint az 1. pontból az 1. pontba vezető?".
	## Miután ez megvan, térjünk vissza ennek a felsorolásnak a 3. lépéséhez, és rögzítsük, hogy a 2. pontból, az 1. ponton keresztül vezető utak hosszát keressük.		*# Miután ez megvan, térjünk vissza ennek a felsorolásnak a 3. lépéséhez, és rögzítsük, hogy a 2. pontból, az 1. ponton keresztül vezető utak hosszát keressük.
	## Futtassuk végig a felsorolás 4. lépésének megfelelően a "célállomás" számát 1-től n-ig.		*# Futtassuk végig a felsorolás 4. lépésének megfelelően a "célállomás" számát 1-től n-ig.
	## Inkrementáljuk a "kiinduló állomást".		*# Inkrementáljuk a "kiinduló állomást".
	## Futtassuk le 1-től n-ig a célállomásokat.		*# Futtassuk le 1-től n-ig a célállomásokat.
	## Ismételgessük az előző kettőt, amíg csak tudjuk. Ekkor inkrementáljuk a köztes állomás számát, amin keresztül keressük az utakat és kezdjük újból futtatni a kiinduló és célállomásokat.		*# Ismételgessük az előző kettőt, amíg csak tudjuk. Ekkor inkrementáljuk a köztes állomás számát, amin keresztül keressük az utakat és kezdjük újból futtatni a kiinduló és célállomásokat.
	## Vegyük észre, hogy ez három egymásba ágyzott for-ciklus. Mind 1-től n-ig megy, és a következőképpen vannak egymásba ágyazva: Keresztül(1..n){Kiinduló(1..n){Cél(1..n)}}		*# Vegyük észre, hogy ez három egymásba ágyzott for-ciklus. Mind 1-től n-ig megy, és a következőképpen vannak egymásba ágyazva: Keresztül(1..n){Kiinduló(1..n){Cél(1..n)}}
	## Mindig akkor javítunk, ha Költség(Kiinduló->Köztes) + Költség(Köztes->Cél) < Költség(Kiinduló->Cél).		*# Mindig akkor javítunk, ha Költség(Kiinduló->Köztes) + Költség(Köztes->Cél) < Költség(Kiinduló->Cél).


	==5. Párosítások, König-Hall-tétel, Frobenius-tétel==		==5. Párosítások, König-Hall-tétel, Frobenius-tétel==