Számítástudomány | mateking
 
12 témakör, 120 rövid és szuper érthető epizód
Ezt a nagyon laza Számítástudomány kurzust úgy terveztük meg, hogy egy csapásra megértsd a lényeget. Tudásszinttől függetlenül, teljesen az alapoktól magyarázzuk el a tananyagot, a saját ritmusodban lépésről lépésre. Így tudjuk a legbonyolultabb dolgokat is elképesztően egyszerűen elmagyarázni.
3 450 Ft fél évre

Tartalomjegyzék: 

A kurzus 12 szekcióból áll: Gráfelméleti alapok, Kuratowski gráfok, síkbarajzolhatóság, Gráfalgoritmusok, Kromatikus szám, klikk, perfekt gráfok, Gráfparaméterek, párosítások, Hálózati folyamok, Menger tételei, többszörös összefüggőség, Páros gráfok, párosítások, Irányított gráfok, gráfalgoritmusok irányított gráfokban, Oszthatóság, Euklideszi algoritmus & Diofantoszi egyenletek, Kongruenciák

Gráfelméleti alapok

  • -

    A gráf egy csúcsának fokszáma a gráf e csúcsában összefutó élek száma.

  • -

    Egy gráf egyszerű, ha nincs benne sem többszörös él, sem hurokél.

  • -

    Ha egy gráfban nincs kör, de maga a gráf összefüggő, akkor fának nevezzük.

  • -

    A gráf csúcsokból és azokat összekötő élekből áll.

  • -

    Egy gráfban körnek nevezünk egy olyan utat, amely csupa különböző csúcsokon és éleken haladva visszavezet a kiinduló csúcsába.

  • -

    Egy gráf összefüggő, ha bármelyik csúcsából el lehet jutni bármelyik másik csúcsába élek mentén.

  • -

    Azokat a gráfokat, ahol minden csúcs mindegyikkel össze van kötve, teljes gráfnak hívjuk.

  • -

    Két szám akkor kongruensek mod m, ha m osztja a két szám különbségét.

  • -

    Kongruenciák szorzása és osztása egy egész számmal.

  • -

    Egy gráf Euler-köre olyan zárt élsorozat, amely a gráf összes élét pontosan egyszer tartalmazza.

Kuratowski gráfok, síkbarajzolhatóság

  • -

    Minden gráfban a csúcsok fokszámainak összege az élek számának a kétszerese.

  • -

    A $G$ gráf egy $( V(G), E(G) )$ rendezett pár, ahol $V(G)$ egy nem üres halmaz, $E(G)$ pedig a $V(G)$-ből képezhető párok egy halmaza.

  • -

    Ha egy élsorozat ugyanabból a csúcsból indul, mint ahova érkezik, akkor körsétának nevezzük.

  • -

    Azokat az élsorozatokat, amelyek a gráf semelyik pontján nem haladnak át többször, útnak nevezzük.

  • -

    A nem összefüggő körmentes gráfok neve erdő.

  • -

    Ha egy gráfban nincs kör, de maga a gráf összefüggő, akkor fának nevezzük.

  • -

    A Kuratowski-tétel szerint egy gráf pontosan akkor nem síkbarajzolható, ha tartalmaz $K_{3,3}$-mal vagy $K_5$-tel topológiailag izomorf részgráfot.

  • -

    Egy gráf síkbarajzolható, ha lerajzolható úgy, hogy élei csak a csúcspontokban találkozzanak.

  • -

    Ha egy gráf síkbarajzolható, akkor az élek számának kisebbnek vagy egyenlőnek kell lennie a csúcsok számának 3-szorosa minusz 6-nál.

  • -

    Az Euler-féle poliéder-tétel azt mondja, hogy egy konvex poliéder csúcsainak számának és lapjainak számának összege megegyezik az élek száma plusz kettővel.

  • -

    A síkbarajzolhatóság feltétele, ha egy egyszerű gráfban minden kör legalább k hosszú.

Gráfalgoritmusok

  • -

    Egy gráf feszítőfája a gráf minden csúcsát tartalmazó fa részgráf.

  • -

    A Kruskal algoritmus segítségével minimális feszítőfát lehet megtalálni.

  • -

    A minimális feszítőfa egy gráfban a legkisebb élsúlyú feszítőfa.

  • -

    Gráfok egy adott pontjából való feltérképezésére alkalmas módszer a szélességi keresés (BFS = Breadth-first search).

  • -

    A DFS algoritmus lényege, hogy elindulunk egy úton, és megyünk, amíg csak tudunk.

  • -

    A BFS és DFS algoritmusok végrehajtása során a gráfnak egy-egy feszítőfáját kapjuk. Ezeket nevezzük BFS és DFS fának.

Kromatikus szám, klikk, perfekt gráfok

  • -

    A legkevesebb színt, amivel egy gráf csúcsait kiszinezhetjük úgy, hogy a szomszédos csúcsok ne legyenek egyforma színűek, a gráf kromatikus számának nevezzük.

  • -

    Egy $G$ egyszerű gráfban klikknek nevezzük azokat a részgráfokat, amelyek teljes gráfok.

  • -

    Egy gráf klikkszáma a gráfban található maximális klikk elemszáma.

  • -

    A $G$ gráfban a $G'$ részgráf feszített részgráf, ha bármely két csúcs a $G'$ gráfban pontosan akkor szomszédos, ha $G$-ben is szomszédos.

  • -

    Ha egy gráf minden feszített részgráfája igaz, hogy azok kromatikus száma egyenlő a klikkszámával, akkor a gráf perfekt.

  • -

    Egy gráf kromatikus száma a gráf klikkszáma és a gráf maximális fokszáma plusz egy közé esik.

  • -

    A mohó színezés egy algoritmus a gráfok színezésére.

  • -

    A Brooks-tétel egy felső becslés a kromatikus számra.

  • -

    Egy $G$ gráfban azt a legkisebb számot, amire a gráfnak már van jó élszínezése, a $G$ gráf élkromatikus számának nevezzük.

  • -

    A Vizing-tétel a gráfok élkromatikus számára ad alsó és felső becslést.

  • -

    Az intervallumgráf egy olyan gráf, melynek csúcsai megfeleltethetőek a valós számok egy-egy intervallumának, és két csúcs között akkor vezet él, ha a nekik megfeleltethető két intervallum metszete nem üres.

  • -

    Egy gráfot páros gráfnak nevezünk, ha csúcsainak halmaza felbontható két diszjunkt részhalmazra, úgy hogy a két halmazon belül nem vezetnek élek, csak köztük.

  • -

    A Mycielski-gráfok olyan gráfok, amelyek klikkszáma 2, a kromatikus számuk pedig bármilyen nagy lehet.

Gráfparaméterek, párosítások

  • -

    A független ponthalmaz precíz definíciójára mindjárt kettő is van.

  • -

    Ha vesszük egy gráfban a maximális számú független pontokat és a minimális számú lefogó pontokat, akkor épp megkapjuk a gráf összes pontját.

  • -

    Egy $G$ gráfban a $T \subset V(G)$ ponthalmaz lefogó ponthalmaz, ha $G$ minden élének legalább az egyik végpontja $T$-ben van.

  • -

    Egy $G$ gráf éleinek $M$ részhalmaza független élhalmaz, ha $M$ semelyik két elemének nincs közös végpontja.

  • -

    Ha vesszük egy gráfban a minimális számú lefogó éleket, és a maximális számú független éleket, akkor a gráf minden pontjához pontosan egy él fog tartozni.

  • -

    Egy $G$ gráf éleinek $R$ részhalmaza lefogó élhalmaz, ha a gráf minden csúcsa valamelyik $R$-beli él végpontja.

  • -

    A lefogó élhalmaz mindig nagyobb vagy egyenlő, mint a független ponthalmaz. A lefogó ponthalmaz mindig nagyobb vagy egyenlő, mint a független élhalmaz.

  • -

    Egy $G$ gráfban az $E(G)$ élhalmaznak egy $M$ részhalmazát párosításnak nevezzük, ha $M$ semelyik két elemének nincs közös végpontja.

  • -

    Egy élsorozat akkor lesz egy párosítás javító útja, ha a következő 3 feltétel teljesül rá.

  • -

    Azokat a párosításokat nevezzük teljes párosításoknak, ami a gráf összes csúcsát lefedi.

  • -

    Egy $G$ gráf akkor és csak akkor páros, ha minden $G$-ben szereplő kör páros hosszúságú.

  • -

    Egy gráfban akkor és csakis akkor létezik teljes párosítás, ha bárhogyan hagyunk el a gráfból néhány pontot, a megmaradt gráfban a páratlan komponensek száma nem több az elhagyott pontok számánál.

Hálózati folyamok

  • -

    A Ford-Fulkerson algoritmus egy olyan algoritmus, amit a maximális folyam megkeresésére használunk.

  • -

    Legyen $X$ egy részhalmaza a gráfnak, ami tartalmazza $S$-t. Ekkor az $X$ és a többi csúcs alkotta részgráf (amik nincsenek benne az $X$-ben) közötti éleket vágásnak nevezzük.

  • -

    Egy vágás kapacitása a vágásban szereplő élek kapacitásainak összege.

  • -

    Irányított gráfban egy él kapacitása az a nem negatív valós szám, amit hozzá rendelünk az élhez.

  • -

    A hálózatban folyamnak nevezünk egy olyan függvényt, amely az élekhez rendel hozzá pozitív valós számokat és amire teljesül, hogy az egy csúcsba befolyó mennyiség megegyezik a csúcsból kifolyóval.

  • -

    A folyam értékén az S-ből kifolyó és S-be befolyó mennyiségek különbségét értjük.

  • -

    A Ford-Fulkerson tétel azt mondja ki, hogy egy hálózatban a maximális folyam mindig megegyezik a minimális vágással.

  • -

    A $(G, S, T, c)$ egy hálózat.

Menger tételei, többszörös összefüggőség

  • -

    Egy $G$ gráf $k$-szorosan élösszefüggő, ha bárhogyan hagyunk el belőle $k$-nál kevesebb élt, a maradék gráf összefüggő marad.

  • -

    Egy $G$ gráf $k$-szorosan pontösszefüggő, ha legalább $k+1$ pontja van és bárhogyan hagyunk el belőle $k$-nál kevesebb pontot, a maradék gráf összefüggő marad.

  • -

    Menger tételei egy G irányított gráfban lévő élidegen és pontidegen utak maximális számáról szólnak.

Páros gráfok, párosítások

  • -

    Hall tétele arról szól, hogy egy $G(A,B,E)$ páros gráfban mikor létezik $A$-t fedő párosítás.

  • -

    Frobenius tétele arról szól, hogy mikor létezik egy gráfban teljes párosítás.

Irányított gráfok, gráfalgoritmusok irányított gráfokban

  • -

    A DFS algoritmusnak az a lényege, hogy kiindulunk egy csúcsból, és megyünk ameddig tudunk.

  • -

    A DFS algoritmus eredményeként kapjuk a DFS-fát.

  • -

    A BFS-algoritmus lényege, hogy kiindulunk egy csúcsból, aztán megkeressük a közvetlen szomszédjait. Innen folytatódik az algoritmus, és az új csúcsoknak keressük meg a szomszédjait.

  • -

    A BFS algoritmus eredményeként kapjuk a BFS-fát.

  • -

    A Dijkstra algoritmus lényege, hogy kiválasztunk egy pontot, és ebből a pontból kiindulva csúcsról csúcsra haladva felderítjük az egész gráfot.

Oszthatóság

  • -

    Két számok legnagyobb közös osztója az a szám, amelyik mindkét számot osztja és ezek közül a legnagyobb.

  • -

    Néhány izgalmas oszthatósági szabály.

  • -

    Két szám relatív prímek, ha a legnagyobb közös osztójuk 1.

  • -

    A nullától és az egységszorzóktól különböző összes $n$ egész szám felbontható prímek szorzatára a sorrendtől és az egységszeresektől eltekintve egyértelműen.

  • -

    Egy $q$ szám felbonthatatlan, ha nem létezik olyan egységtől különböző $a$ és $b$ szám, hogy $q=ab$

  • -

    Egy $p$ szám akkor prím, ha $p$ oszt egy szorzatot, akkor csak az egyik szorzótényezőnek lehet osztója.

Euklideszi algoritmus & Diofantoszi egyenletek

  • -

    Az euklideszi algoritmus egy formányos módszer két szám legnagyobb közös osztójának kiszámolására.

  • -

    A Diofantoszi egyenletek olyan egész együtthatós kétismeretlenes egyenletek, amelyek megoldásait az egész számok halmazán keressük.

Kongruenciák

  • -

    Ha $a$ és $b$ ugyanazt a maradékot adja $m$-mel osztva, akkor azt mondjuk, hogy $a$ és $b$ kongruensek modulo $m$.

  • -

    A kongruencia reflexív, szimmetrikus és tranzitív.

  • -

    Két szám akkor kongruensek mod m, ha m osztja a két szám különbségét.

  • -

    Kongruenciák szorzása és osztása egy egész számmal.

  • -

    Egy adott $m$ modulus esetén az $a$-val kongruens elemek halmazát az $a$ által reprezentált maradékosztálynak nevezzük.

  • -

    Egy mod $m$ modulus esetén az $m$-hez relatív prím elemekből álló maradékosztályokat redukált maradékosztálynak nevezzük.

  • -

    Az euler féle $ \varphi$ függvény azt adja meg, hogy hány $m$-nél nem nagyobb, $m$-hez relatív prím pozitív szám létezik.

  • -

    A kis Fermat-tétel általánosítása.

  • -

    A kis Fermat-tétel szerint ha veszünk egy $a$ egész számot és azt $p$-edik hatványra emeljük, ahol $p$ prímszám, akkor ez a hatvány $p$-vel osztva $a$ maradékot ad.

  • -

    A lineáris kongruenciák olyan kongruenciák, amikben x is szerepel.

  • -

    Lineáris kongruenciák megoldásának lépései.

  • -

    Az RSA lényege, hogy a titkosítás kulcsa nyilvános, vagyis azt bárki ismerheti. Csak a dekódolás kulcsa az, ami titkos.