VIK Wiki

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

← Régebbi szerkesztés
Vizuális
David14 (vitalap | szerkesztései)
4 081 szerkesztés
Szikszayl (vitalap | szerkesztései)
4 274 szerkesztés
aNincs szerkesztési összefoglaló
 
(6 közbenső módosítás, amit egy másik szerkesztő végzett, nincs mutatva)
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==


281. sor: 289. 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: 300. 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==
313. sor: 320. 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.
341. sor: 348. 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==
381. sor: 387. 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===
391. sor: 397. 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==
457. sor: 462. 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==
565. sor: 569. sor:




 
[[Kategória:Villamosmérnök]]
 
[[Kategória:Villanyalap]]
A lap eredeti címe: „https://vik.wiki/A_számítástudomány_alapjai_-_Segédanyagok_a_vizsgához”