„A számítástudomány alapjai - Segédanyagok a vizsgához” változatai közötti eltérés

## Kiválasztjuk a kezdőpontot és megjelöljük

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

## Az előbbi két pontot ismételgetjük, amíg csak tudjuk.

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

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

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

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

## 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".)

## 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ő?".

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

## Inkrementáljuk a "kiinduló állomást".

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

## 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).

 

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

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

 

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

## Tegyük a gömböt a síkra.

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

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

 

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

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

## Kiválasztjuk a kiindulási pontot.

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

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

## 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ő,

*** sör, bacon, vidámság, szánsájn, szikla és zsömle,

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

 

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

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

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

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

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

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

## Addig csinálgatjuk ezt, míg a hátulról növekvő hosszú rendezett szakasz a tömb elejéig nem ér.

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

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

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

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

 

 

 

[[Kategória:Villanyalap]]