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

{{Vissza|A számítástudomány alapjai}}

__NOTOC__

* Binomiális tétel videó: [http://www.youtube.com/watch?v=1pSD8cYyqUo 1.], [http://www.youtube.com/watch?v=TeE-ypKj8ZI 2.]

* Ismétlés nélküli permutáció: <math>n</math> darab megkülönböztethető elem összes lehetséges sorba állításainak száma <math>n!</math>. Példa: 10 különböző színű golyó lehetséges sorba állításainak száma 10!.

* Ismétléses permutáció: <math>n</math> darab elem lehetséges sorba állításainak a száma, úgy, hogy az <math>n</math> elem <math>k_1</math> darab első típusú, <math>k_2</math> darab második típusú, ..., <math>k_m</math> darab <math>m.</math> típusú elemre osztható, és, ha csak ezeket a csoportokat tudjuk megkülönböztetni egymástól, a csoporton belül az egyes elemeket nem: <math> \frac{n!}{k_1! \cdot k_2! \cdot ... \cdot k_m!} </math>. Például: 6 darab piros és 4 darab kék golyó lehetésges sorba állításainak száma (egy piros golyót nem tudunk megkülönböztetni egy másik pirostól, mint ahogy egy kékset sem egy másik kéktől, csak a pirosat a kéktől): <math> \frac{10!}{4!6!} </math>.

* Ismétléses kombináció: <math>n</math> darab elemből hányféleképpen lehet <math>k</math> darabot kiválasztani, ha a sorrendjük nem számít, és egy elem többször is szerepelhet? <math> \binom{n+k-1}{k} </math>-féleképpen. Példa: 30 golyóból 10-et húzok ki visszatevéssel. Hányféle lehet a kihúzott golyók sorrendje? <math> \binom{30+10-1}{10} = \binom{39}{10} </math>-féle.

* Newton-féle binomiális tétel: tetszőleges valós <math>a</math>-ra és <math>b</math>-re és nemnegatív egész <math>n</math>-re <math> (a+b)^n = \sum_{i=0}^{n} \left[ \binom{n}{i} a^{n-i} b^i \right] </math>.

* Szita-formula: nem diszjunkt halmazok uniójának elemszámának számítására alkalmazható módszer.

* [http://www.youtube.com/watch?v=HmQR8Xy9DeM Alapfogalmak videó]

* [http://www.youtube.com/watch?v=OWfeZ9uDhdw Kruskal-algoritmus videó]

* [http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-046j-introduction-to-algorithms-sma-5503-fall-2005/video-lectures/lecture-16-greedy-algorithms-minimum-spanning-trees/ Teljes MIT előadás-videó: mohó algoritmus, minimális költségű feszítőfa keresése]

* Gráf: rendezett <math>G=(V,E)</math> pár, ahol <math>V</math> a pontok, <math>E</math> az élek halmaza.

* Pont: a gráfot részben alkotó nem üres halmaz.

* Prüfer-kód: egy fát egyértelműen reprezentáló számsorozat.

* Páratlan fokú pontok száma minden gráfban páros.

* <math>n</math> pontú teljes gráf éleinek száma

* Cayley tétele: <math>n</math> ponton <math>n^{n-2}</math> pont adható meg.

* Kruskal-algoritmus: minimális súlyú feszítőerdőt talál egy gráfban

* Prüfer-kód felírása

* [http://www.youtube.com/watch?v=REfC1-igKHQ Euler-út és -kör videó]

* Euler-út: olyan élsorozat, amely egyszer tartalmazza a gráf minden élét.

* Euler-kör: zárt Euler-út. Megjegyzés: az Euler-körök és -utak a neveik ellenére nem a korábbi definíciók szerinti körök, illetve utak.

* Hamilton-kör: azonos kezdő- és végpontú Hamilton-út.

* Euler-kör létezésének tétele: egy gráfban akkor és csak akkor van Euler-kör, ha a gráf minden pontjának fokszáma páros és a gráf összefüggő. ("Euleri grááááf, minden foka páros!")

* Euler-út létezésének tétele: egy gráfban akkor és csak akkor van Euler-út, ha a gráfban a páratlan fokú pontok száma 0 vagy 2 és a gráf összefüggő.

* Dirac tétele: ha egy <math>n</math> pontú gráfban minden font foka legalább <math>n/2</math>, akkor a gráfban van Hamilton-kör.

* [http://www.youtube.com/watch?v=or9xlA3YYzo BFS, DFS videó]

* [http://www.youtube.com/watch?v=8Ls1RqHCOPw Dijkstra videó]

* [http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-046j-introduction-to-algorithms-sma-5503-fall-2005/video-lectures/lecture-19-shortest-paths-iii-all-pairs-shortest-paths-matrix-multiplication-floyd-warshall-johnson/ Teljes MIT előadás-videó: Floyd-algoritmus]

* BFS: nem élsúlyozott esetben használjuk

* Dijkstra-algoritmus: élsúlyozott esetben használjuk

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

* Floyd-algoritmus: olyan esetben használjuk, ha a gráfban nincs negatív összsúlyú irányított kör.  

* [http://www.youtube.com/watch?v=OvM78wl3fUs Hall-tétel videó]

* Páros gráf: olyan gráf, melynek pontjai két halmazra oszthatók és minden élének az egyik végpontja az egyik halmazban, a másik végpontja a másik halmazban van.

* Teljes páros gráf: olyan páros gráf, melynek minden egyik halmazbeli pontja össze van kötve minden másik halmazbeli pontjával.

* Teljes párosítás: olyan párosítás, mely a gráf minden pontját lefedi.

* Egy gráf akkor és csak akkor páros gráf, ha minden benne lévő kör páros hosszúságú.

* Hall-tétel: egy páros gráfban akkor és csak akkor van az egyik ponthalmazt lefedő párosítás, ha a ponthalmaz minden részhalmazára igaz, hogy annak pontjainak száma kisebb, vagy egyenlő, mint annak szomszédos pontjainak a száma.

* Frobenius-tétel: egy páros gráfban akkor és csak akkor van teljes párosítás, ha a két halmaz elemszáma megegyezik és az egyikre igaz a Hall-tétel.   

* Független élek: semelyik két élnek nincs közös pontja.

* Független pontok: nincs benne két szomszédos pont.

* Lefogó pontok: minden élnek legalább az egyik végpontját tartalmazzák.

* Minden gráfra a független élek maximális száma kisebb, vagy egyenlő, mint a legofó pontok minimális száma.

* Minden gráfra a független pontok maximális száma kisebb, vagy egyenlő, mint a lefogó élek minimális száma.

* Tutte-tétel: egy gráfban akkor és csak akkor létezik teljes párosítás, ha akárhogy hagyunk el egy gráfból néhány pontot, a maradékban a páratlan komponensek száma ennél több nem lehet.

* Él kapacitása: a gráf éléhez rendelt nemnegatív valós szám.

* Hálózat: olyan irányított gráf, melyben az élekhez kapacitások vannak rendelve, valamint van a gráfban egy forrás és egy nyelő.

* Javító út: olyan (nem feltétlenül a gráf irányításának megfelelő) út s-ből t-be, amely mentén a folyamértékeket változtatva növelni tudjuk a teljes folyam értékét.

* Ford-Fulkerson-tétel: a maximális folyam értéke egyenlő a minimális vágás értékével.

* Edmonds-Karp-tétel: ha mindig a legrövidebb utat vesszük, akkor a maximális folyam meghatározásához szükséges lépések száma felülről becsülhető a pontok számának polinomjával.

* [http://www.youtube.com/watch?v=JJpWE0oKm2Y Menger tételei videó]

* Élidegen utak: olyan utak, melyekben nincs közös él.

* Pontidegen utak: olyan utak, melyekben nincs közös pont.

* k-szorosan pontösszefüggő gráf: legalább <math>k+1</math> pontja van és akárhogy hagyunk el belőle k-nál kevesebb pontot, a maradó gráf összefüggő marad.

* Menger tételek: irányított és irányítatlan gráfokra is igazak. Irányított gráfok esetében s és t forrás és nyelő, irányítatlan esetben pedig csak két kijelölt pontja a gráfnak.

** Az s-ből t-be vezető, páronként élidegen utak maximális száma egyenlő az s-t utakat lefogó élek maximális számával.

* Dirac-tétel: ha <math> k \leq 2 </math> és a gráf k-szorosan pontösszefüggő, akkor bármely k darab pontján át vezet kör.

* Kromatikus szám: megadja, hogy egy gráf csúcsai legkevesebb hány színnel színezhetők ki úgy, hogy bármely két szomszédos csúcs színe különböző legyen.

* Élkromatikus szám: megadja, hogy egy gráf élei legkevesebb hány színnel színezhetők ki úgy, hogy bármely két szomszédos él színe különböző legyen.

* Klikkszám: a gráfban található összes klikk közül a legnagyobb adja a gráf klikkszámát.

* Klikkszám és kromatikus szám összefüggése: minden gráfra igaz, hogy a kromatikus szám nagyobb, vagy egyenlő, mint a klikkszám.

* Korlátok a kromatikus számra: teljes gráfok esetében a kromatikus szám egyenlő a pontok számával, nem teljes gráf esetében értelemszerűen kevesebb.

* Brooks-tétel: egyszerű, összefüggő, nem teljes gráfokra és nem páratlan hosszúságú körökre igaz, hogy a kromatikus számuk nem nagyobb, mint a maximális fokszám.

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

* [http://www.youtube.com/watch?v=x6zPviKyykM Síkbarajzolhatóság, Euler-féle poliédertétel videó]

* [http://www.youtube.com/watch?v=YqEeaudxghE Bizonyítás, hogy K5 és K3,3 nem síkbarajzolhatók videó]

* Síkbarajzolható gráf: olyan gráf, amely lerajzolható a síkba úgy, hogy élei ne messék egymást.

* Tartomány: a síkbarajzolt gráfban az élek által határolt területek. A gráf tartományának számít az egészet körülölelő, külső végtelen tartomány is.

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

* Síkbarajzolhatóság feltétele: egy gráf akkor síkbarajzolható, ha gömbre rajzolható.

* Euler-féle poliédertétel: minden _n_ pontú, _e_ élű és _t_ tartománnyal (beleértve a külsőt is!) rendelkező összefüggő síkbarajzolható gráfra: <math>n+t=e+2</math>.

* Fáry-Wágner-tétel: minden egyszerű, síkbarajzolható gráfnak létezik olyan ábrázolása is, hogy minden élet egyenes vonalakkal rajzolunk.

* Sztereografikus projekció - síkgráf gömbre rajzolása.

* Gráf duálisa: a síkbarajzolható gráf duálisa úgy kezetkezik, hogy az eredeti gráf tartományaihoz pontokat rendelünk (a külső tartományhoz is) és két ilyen új pontot akkor kötünk össze, ha az eredeti gráfban a két tartománynak van közös határvonala.

* Gyenge izomorfia: két gráf gyengén izomorf, ha éleik között kölcsönösen egyértelmű, körtartó leképezés létesíthető.

* Absztrakt duális: két gráf egymás absztrakt duálisai, ha éleik között létesíthető olyan kölcsönösen egyértelmű leképezés, amely kört vágásba, vágást körbe visz.

* Whitney-tételei

** Ha egy _G_ gráf síkbarajzolható, akkor a vele gyengén izomorf _H_ is. Ezek duálisai egymással szintén gyengén izomorfak lesznek, a duálisaik duálisa pedig gyengén izomorf lesz az eredeti _G_ és _H_ gráfokkal.

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

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

* [http://www.youtube.com/watch?v=or9xlA3YYzo BFS, DFS videó]

* DFS-erdő: a gráf olyan feszítőerdője, amit a komponensek mélységi bejárásával hozunk létre.

* Előre-él: egy irányított gráf DFS-erdőjének létrehozásakor szisztematikusan, "emeletekbe" rendezzük a pontokat aszerint, hogy melyiket mikor látogattuk meg: ameddig "előre" haladunk a gráfban, lefelé bővítjük a fát, ha visszalépegettünk és egy korábban bejárt pontról indítjuk újra a bejárást, oda oldalágat rajzolunk és újfent lefelé bővítünk, amíg tudunk, stb. Az eredeti gráfnak azokat az éleit, amik nem kerültek a DFS-erdőbe, az előre-, a vissza-, és a kereszt-él csoportjába oszthatjuk. Az előre-élek a DFS-felbontásnak megfelelő élek irányába mutatnak.

* Alapkörrendszer: egy összefüggő gráf egy fájához ha hozzáveszünk még egy élt, akkor a keletkező gráfban egy kör lesz. Ha a fához minden lehetséges módon hozzáveszünk még egy élt, akkor a keletkező körök unióját a gráf adott fájához tartozó alapkörrendszerének nevezzük.

* Egy gráfban akkor és csak akkor van irányított kör, ha a mélységi bejárás során találunk vissza-élt.

* Egy irányított gráfban akkor és csak akkor van irányított kör, ha ponthalmaza nem bontható emeletekre.

* Mélységi keresés:  

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

* [http://www.youtube.com/watch?v=wNVCJj642n4 Lineáris és logaritmikus keresés videó]

* [http://www.youtube.com/watch?v=HmQR8Xy9DeM Szomszédsági tömb és mátrix videó (5.54-től)]

* [http://www.youtube.com/watch?v=t8g-iYGHpEA Rendezőalgoritmusok összehasonlítása videó]

* Lépésszám: ahány elemi műveletet igényel egy algoritmus végrehajtása. Hogy mit tekintünk elemi műveletnek, az alkalmazásfüggő.

* Illeszkedési mátrix: _n_ pontú, _e_ élű irányított gráf <math> n \times e </math> méretű illeszkedési mátrixának elemei

* 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

* Lineáris keresés: bármilyen rendezetlen tömbre működik, egyszerűen végigmegy a tömb elemein és mindegyiket komparálja a keresett elemmel. Ez a módszer olyan, mint bármi, ami szovjet. Egyszerű, mindig működik, nem lehet elrontani, cserébe lassú, nem éppen kifinomult, és kiröhögnek, ha használod. _n_ elemre általában kb. <math> n/2 </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

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

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

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

** Gyors, de kényes módszer, nem olyan egyszerű leprogramozni. Cserébe jó gyorsan tud működni.

* Eldöntési probléma: olyan probléma, aminek az inputja egy eldöntendő kérdés, a válasz pedig igen vagy nem.

* P-beli probléma: olyan probléma, mely az input méretének polinomiális függvényével felülről becsülhető időben megoldható.

* NP-teljes probléma: olyan NP-nehéz probléma, mely maga is NP-ben van.

* Bonyolultsági osztályok feltételezett viszonya: van három halmaz: az NP, a co-NP és az NP-nehéz.

** Az NP és co-NP metszetében van P halmaz, de nem tudunk olyan problémáról, ami az NP és co-NP metszetében lenne, de ne lenne P-ben is. Sejtés: NP és co-NP metszete, valamint P ugyanaz.

** Az NP és az NP-nehéz halmazok metszetében vannak az NP-teljes problémák.

* [http://www.youtube.com/watch?v=_0x7uCiC0Uc Euklideszi algoritmus legnagyobb közös osztó keresésére videó]

* [http://www.youtube.com/watch?v=4xANqGj7nnI Euklideszi algoritmus maradékos osztáshoz videó]  

* Oszthatóság: _a_ osztja _b_-t, ha van olyan _q_ egész szám, amelyre <math> b=aq </math>. (_a_ és _b_ is egészek.)

* Prímszám: nincsenek valódi osztóik.

* Relatív prímek: lnko-juk 1.

* Számelmélet alaptétele: minden pozitív egész szám előáll az őt osztó prímszámok szorzataként.

* Osztók száma: <math> d(n) = \prod_{i=1}^{k} (\alpha_i + 1) </math>, ahol <math> \alpha_i </math> az ''i.'' prímtényező kitevője.

* Relatív prím számok száma: egy _n_ számnál kisebb, hozzá relatív prímek száma: <math> n \prod_{i=1}^{k} \left( 1-\frac{1}{p_i} \right) </math>.

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

* [http://www.youtube.com/watch?v=U9Eo6Bsvm4M Kongruenciák megoldása videó]

* Kongruencia: _a_ kongruens _b_-vel az _m_ modulusra vonatkozólag, ha az _a_ és _b_ számok _m_-el osztva ugyanazt a maradékot adják.

* Maradékosztály: a kongruencia ekvivalenciareláció, amely osztályokba sorolja az egész számokat. Egy maradékosztályba tartoznak az _m_-el oszthatók, az _m_-el osztva 1 maradékot adók, stb.

* Redukált maradékrendszer: rögzített _m_ modulus mellett az _a_-val reprezentált maradékosztályt redukált maradékosztálynak nevezzük, ha _a_ és _m_ relatív prímek. Ha minden redukált maradékosztályt egy számmal reprezentálunk, akkor ezek redukált maradékrendszert alkotnak.

* <math> a \equiv b (\text{mod } m) \Leftrightarrow m | a-b </math>.

* Euler-Fermat-tétel: ha _a_ és _m_ relatív prímek, valamint <math>m>1</math>, akkor <math> a^{\varphi(m)} \equiv 1 (\text{mod } m) </math>.

* Wilson-tétel

* Lineáris kongruenciák megoldása

* n változós művelet: egy <math> f : H^n \rightarrow H </math> mindenütt értelmezett függvény _n_ változós művelet a _H_ halmazon.

* Kommutativitás: <math> a*b = b*a</math>.

* Elem rendje: az a legkisebb olyan _k_ szám, amelyre <math> a^k = 1 </math>. Ha nincs ilyen szám, akkor végtelen rendű a csoport.

* A hatványozás azonosságai: <math> a^{n+k} = a^n a^k </math> és <math> \left( a^n \right)^k = a^{nk} </math>.

* Azonos rendű ciklikus csoportok izomorfak.

* Ciklikus csoport részcsoportja is ciklikus.

* Részcsoport: _G_ csoport, ha _H_ valódi részhalmaza _G_-nek és _H_ is csoport _G_ műveletére, akkor _H_ egy részcsoportja _G_-nek.

* Triviális részcsoport: minden csoportnak részcsoportja az egész csoport és a csak az egységelemet tartalmazó egyelemű halmaz, ezek a triviális részcsoportok.

* Intgrálási tartomány: kommutatív, nullosztómentes gyűrű.

* Lagrange-tétel: ha _G_ véges, _H_ részcsoportja _G_-nek, akkor _H_ rendje osztja _G_ rendjét.

* Áruló: Fermat-prímtesztben, ha el akarjuk dönteni, hogy egy _n_ prím-e vagy sem, akkor ellenőrizzük, hogy egy _n_-hez relatív prím _t_-re igaz-e, hogy <math> t^{n-1} \equiv 1 (\text{mod } n) </math> (kis-Fermat-tétel). Ha ez nem igaz, akkor tudjuk, hogy _n_ nem prím, és _t_ volt az árulója.  

* Cinkos: Ha az előző pontban a kis-Fermat tétel igaz lett volna, holott _n_ összetett lett volna, akkor _t_ a cinkosa lett volna. Ekkor azt mondjuk, hogy _n_ a _t_ alapra álprím.

* Dekódoló függvény: a kulcspár titkos része. A kódoló és dekódoló függvény egymás inverzei.

* Eratoszthenész "szita-algoritmusa": írjuk fel a számokat 1-től _n_-ig, majd húzzuk ki közülük a 2-vel oszthatókat, kivéve a 2-t, majd a maradékból a 3-mal oszthatókat, kivéve a 3-at, satöbbi, így előbb-utóbb elő tudunk állítani bármilyen nagy prímeket.