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álisWikiszöveges
David14 (vitalap | szerkesztései)
4 081 szerkesztés
Szikszayl (vitalap | szerkesztései)
4 274 szerkesztés
aNincs szerkesztési összefoglaló
 
(3 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==


379. 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===
389. 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==
455. 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==
563. 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”