A számítástudomány alapjai - Segédanyagok a vizsgához

← Vissza az előző oldalra – A számítástudomány alapjai

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!

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

Jegyzetek, videók

• 1. Tétel videó (2012/II tételsor) - magyar: Leszámlálások, Binomiális tétel, Skatulya-elv, Szita-formula
• Binomiális tétel videó: 1., 2.

Definíciók

• 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és nélküli variáció: [math]n[/math] darab elem ismétlés nélküli permutációi, de csak az első [math]k[/math] darab tag érdekel minket. Másképp: [math]n[/math] darab megkülönböztethető elemből az összes lehetséges sorrendben [math]k[/math] darab kiválasztása: [math] \frac{n!}{(n-k)!} [/math]. Példa: 30 futóból [math] \frac{30!}{(30-3)!} = \frac{30!}{27!} = 30 \cdot 29 \cdot 28 [/math]-féle lehet az 1.-2.-3. helyezettek sorrendje.
• Ismétléses variáció: [math]k[/math] darab elemet hányféleképpen sorolhatunk be [math]n[/math] darab csoportba, ha lehet olyan csoport, amelybe egy elem sem kerül? [math]n^k[/math]-féleképpen. Példa: 70 fős évfolyam elosztása 3 osztályba elméletileg [math]3^{70}[/math]-féleképpen történhet.
• Ismétlés nélküli 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, de egy elem nem szerepelhet kétszer? [math] \frac{n \cdot (n-1) \cdot ... \cdot (n-k+1)}{k!} = \binom{n}{k} [/math]-féleképpen. Példa: a lottószelvényen [math] \binom{90}{5} [/math]-féleképpen választhatjuk ki, hogy mely számokat jelöljük meg.
• 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.

Tételek és összefüggések

• 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].

Algoritmusok, eljárások és egyebek

• Szita-formula: nem diszjunkt halmazok uniójának elemszámának számítására alkalmazható módszer.
  1. Egyszerűen összegezzük az uniót képző halmazok elemszámait.
  2. De így kétszer számoltunk minden olyan elemet, ami a kettes metszetek valamelyikében van, tehát a kettes metszetek elemszámainak összegét le kell vonni a végeredményből.
  3. Az 1. pontban háromszor számoltuk a hármas metszetekben lévő elemeket, de a 2. pontban háromszor le is vontuk azokat, tehát most az eredményt korrigálni kell a hármas metszetek elemszámával.
  4. Satöbbi.

2. Gráfelméleti alapfogalmak, fák egyszerűbb tulajdonságai, Kruskal tétele (minimális költségű feszítőfa keresése), Cayley tétele (fák száma), Prüfer-kód

Jegyzetek, videók

• 4. Tétel videó (2012/II tételsor) - magyar: Gráfelméleti alapok
• 5. Tétel videó (2012/II tételsor) - magyar: Cayley-tétel, Prüfer-kód, Kruskal-algoritmus, Normál-fák
• Alapfogalmak videó
• Kruskal-algoritmus videó
• Teljes MIT előadás-videó: mohó algoritmus, minimális költségű feszítőfa keresése

Definíciók

• 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.
• Él: a pontokból képezhető párok halmaza.
• Végpont: egy él két végpontja a két pont, amikre illeszkedik.
• Hurokél: ha az él két végpontja azonos (vagyis az él önmagába visszatér).
• Párhuzamos élek: olyan élek, melyek mindegyike esetében azonos a két végpont (vagyis két pont között több él fut).
• Pont fokszáma: a hozzá csatlakozó élek száma.
• Egyszerű gráf: olyan gráf, melyben nincsenek hurokélek és többszörös élek.
• Szomszédos él: olyan élek, melyeknek egy végpontjuk közös.
• Szomszédos pont: olyan pontok, melyek egy élre illeszkednek.
• Izolált pont: olyan pont, melyre nem illeszkedik él.
• k-reguláris gráf: olyan gráf, melyben minden pont foka k.
• Teljes gráf: olyan gráf, melynek tetszőleges két pontja szomszédos (vagyis minden pont mindegyikkel össze van kötve.)
• Bijekció: egy-egy értelmű megfeleltetés.
• Izomorf gráfok: két gráf akkor izomorf, ha létezik közöttük olyan bijekció, hogy két pont akkor szomszédos az egyik gráfban, ha a másikban is az és a szomszédos pontok között ugyanannyi él fut. Másképpen: ha létezik olyan bijekció, hogy az egyik gráf tetszőleges két pontja között annyi él fut, mint a másik gráf azonos két pontja között. Megint másképp: két gráf akkor izomorf, ha ugyanazok, csak máshogy vannak lerajzolva.
• Részgráf: akkor keletkezik, ha egy gráfból bizonyos pontokat és éleket elhagyunk.
• Részgráf komplementere: vesszük az eredeti gráf összes pontját, illetve azokat az éleit, amiket a részgráf képzésekor elhagytunk.
• Gráf komplementere: azok a pontpárok vannak benne összekötve, melyek az eredeti gráfban nem voltak.
• Feszítő részgráf: olyan részgráf, mely az eredeti gráf összes pontját tartalmazza.
• Feszített részgráf: olyan részgráf, ami úgy keletkezik, hogy egy gráfból elhagyunk bizonyos pontokat, de nem hagyunk el éleket (természetesen azokat az élek törlődnek, amelyeknek az egyik pontját elhagytuk).
• Élsorozat: egy olyan (pont, él, pont, él, ..., pont, él, pont) sorozat, amelyre igaz, hogy benne minden él az elé és mögé írt pontokat köti össze. (Magyarul szépen folyamatosan megyek a gráfban és írom egymás után, hogy milyen pontokat és éleket érintettem.)
• Zárt élsorozat: olyan élsorozat, melynek első és utolsó pontja azonos.
• Út: olyan élsorozat, melyben minden pont különböző.
• Kör: olyan út, melynek első és utolsó pontja azonos, de első és második éle nem azonos.
• Ekvivalenciareláció: olyan reláció, amely egyszerre reflexít, szimmetrikus és tranzitív.
• Ekvivalenciaosztály: az ekvivalenciareláció által meghatározott részhalmazai az alaphalmaznak. Olyan elemek tartoznak egy ekvivalenciaosztályba, amelyek egymással ekvivalensek.
• Gráf komponense: a gráf olyan elkülöníthető részgráfja, amely a gráf többi részéhez nem kapcsolódik egy éllel sem.
• Összefüggő gráf: olyan gráf, amelynek egy komponense van.
• Elvágó él: olyan él, melynek elhagyásával nő a gráf komponenseinek a száma (szétesik).
• Elvágó élhalmaz: olyan élhalmaz, melynek elhagyásával nő a gráf komponenseinek a száma.
• Vágás: olyan minimális élhalmaz, melynek elhagyásával nő a gráf komponenseinek a száma.
• Irányított gráf: olyan gráf, melyben az élek nem a pontok rendezetlen, hanem rendezett párjai, vagyis az éleknek van kijelölt irányuk.
• Kezdőpont: az irányított élnek nem két végpontja van, hanem egy kezdő- és egy végpontja. A kezdőpont az élet definiáló rendezett pontpárból az első, a végpont ezesetben a második.
• Forrás: olyan pont, mely egy élnek sem végpontja.
• Nyelő: olyan pont, mely egy élnek sem kezdőpontja.
• Irányított út: olyan élsorozat, melyben minden élnek az elé írt pont a kezdőpontja és a mögé írt pont a végpontja.
• Irányított kör: olyan irányított út, amelynek kezdő és végpontja azonos.
• Erősen összefüggő gráf: olyan gráf, melynek minden két pontja között vezet irányított út.
• Fa: összefüggő körmentes gráf.
• Feszítőfa: olyan feszítő részgráfja egy gráfnak, ami fa.
• Erdő: körmentes gráf.
• Feszítőerdő: minden komponense feszítőfája az eredeti gráf megfelelő komponensének.
• Él súlya: az élhez rendelt szám, amelynek a jelentése az alkalmazástól függően változhat (pl. jelölhet két pont közötti távolságot, eljutási költésget, áteresztőképességet, prioritást, stb.).
• Részgráf súlya: a részgráfot alkotó élek súlyának összege.
• Mohó algoritmus: olyan algoritmus, melynek végrehajtása során mindig az aktuálisan legkedvezőbbnek tűnő lehetőséget választjuk.
• Prüfer-kód: egy fát egyértelműen reprezentáló számsorozat.

Tételek és összefüggések

• Páratlan fokú pontok száma minden gráfban páros.
• [math]n[/math] pontú teljes gráf éleinek száma
• Fokszámok összege az élszám kétszerese.
• [math]n[/math] pointú fa éleinek száma [math]n-1[/math].
• Cayley tétele: [math]n[/math] ponton [math]n^{n-2}[/math] pont adható meg.

Algoritmusok, eljárások és egyebek

• Kruskal-algoritmus: minimális súlyú feszítőerdőt talál egy gráfban
  1. Kiválasztjuk az összes él közül valamelyik legkisebb súlyút.
  2. Kiválasztjuk a maradék élek közül azt a legkisebb súlyút, ami a már kiválasztottakkal nem alkot kört.
  3. Addig ismételgetjük a 2. pontot, amíg minden pontját le nem fedtük a gráfnak.
• Prüfer-kód felírása
  1. Számozzuk meg a fa pontjait tetszőleges sorrendben.
  2. Töröljük le a fa elsőfokú pontjai közül azt, amelyiknek a legkisebb a száma és jegyezzük fel a szomszédja számát.
  3. Ezt ismételgessük addig, amíg csak tudjuk.

3. Euler-séta és -körséta (Euler-út, -kör) fogalma, szükséges és elégséges feltétel a létezésükre, Hamilton-kör és -út, szükséges, illetve, elégséges feltételek Hamilton-kör létezésére

Jegyzetek, videók

• 6. Tétel videó (2012/II tételsor) - magyar: Euler-kör, Euler-út, Hamilton-kör, Hamilton-út
• Euler-út és -kör videó

Definíciók

• 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-út: olyan út, amely a gráf minden pontját egyszer tartalmazza.
• Hamilton-kör: azonos kezdő- és végpontú Hamilton-út.

Tételek és összefüggések

• 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ő.
• Ore tétele: ha a gráfban nincs olyan szomszédos pontpár, melyre igaz lenne, hogy fokszámaik összege kevesebb, mint a gráf pontjainak a száma, akkor a gráfban van Hamilton-kör.
• 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.

4. Legrövidebb utakat kereső algoritmusok (BFS, Dijkstra, Ford, Floyd)

Jegyzetek, videók

• BFS, DFS videó
• Dijkstra videó
• Teljes MIT előadás-videó: bevezetés a legrövidebb út problémákba, Dijkstra-algoritmus, BFS
• Teljes MIT előadás-videó: Ford-algoritmus
• Teljes MIT előadás-videó: Floyd-algoritmus

Algoritmusok, eljárások és egyebek

• BFS: nem élsúlyozott esetben használjuk
  1. Kiválasztjuk a kezdőpontot és megjelöljük
  2. Meglátogatjuk az összes szomszédját, ahol még nem voltunk.
  3. 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.
  4. Az előbbi két pontot ismételgetjük, amíg csak tudjuk.
• Dijkstra-algoritmus: élsúlyozott esetben használjuk
  1. Kiválasztjuk a kezdőpontot.
  2. 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.
  3. 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.
  4. Az előző pontot ismételgetjük addig, amíg már egy pontból sem tudunk javítani.
• 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.
  1. Megszámozzuk az éleket tetszőleges sorrendben.
  2. Felírjuk, hogy a kiindulópontba 0 költségen, minden más pontba végtelen költségen juthatunk el.
  3. 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.
  4. 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.
• Floyd-algoritmus: olyan esetben használjuk, ha a gráfban nincs negatív összsúlyú irányított kör.
  1. 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.
  2. 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".)
  3. Majd rögzítsük, hogy az 1. pontból, az 1. ponton keresztül vezető utak hosszát keressük.
  4. 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ő?".
  5. 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.
  6. 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.
  7. Inkrementáljuk a "kiinduló állomást".
  8. Futtassuk le 1-től n-ig a célállomásokat.
  9. 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.
  10. 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)}}
  11. Mindig akkor javítunk, ha Költség(Kiinduló->Köztes) + Költség(Köztes->Cél) < Költség(Kiinduló->Cél).

5. Párosítások, König-Hall-tétel, Frobenius-tétel

Jegyzetek, videók

• Hall-tétel videó

Definíciók

• 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.
• Párosítás: olyan élhalmaz, amelyben semelyik két élnek sincs közös pontja.
• Teljes párosítás: olyan párosítás, mely a gráf minden pontját lefedi.

Tételek és összefüggések

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

6. König és Gallai tételei, Tutte-tétel (bizonyítás nélkül)

Definíciók

• Független élek: semelyik két élnek nincs közös pontja.
• Független pontok: nincs benne két szomszédos pont.
• Lefogó élek: minden pontot érintenek.
• Lefogó pontok: minden élnek legalább az egyik végpontját tartalmazzák.

Tételek és összefüggések

• 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.
• Minden hurokmentes gráfra a lefogó pontok minimális számának és a független pontok maximális számának összege a gráf pontjainak számával egyenlő.
• Minden izolált pont nélküli gráfra a lefogó élek minimális számának és a független élek maximális számának az összege a gráf pontjainak a számával egyenlő.
• König-tétel: páros gráfnál a független élek maximális száma egyenlő a lefogó pontok minimális számával, izolált pont nélküli gráfra pedig a független pontok maximális száma egyenlő a lefogó élek minimális számával.
• 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.

7. Hálózati folyamok, Ford-Fulkerson-tétel, Edmonds-Karp-tétel (bizonyítás nélkül)

Definíciók

• É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ő.
• Folyam: olyan függvény a hálózat minden élére, ami a hálózati reprezentáció alapján lehetséges, vagyis a folyam értéke egy él esetében sem haladja meg az él kapacitását, valamint a forrás és a nyelő kivételével minden pontra érvényes a Kirchhoff csomóponti törvény (a befelé és kifelé irányított folyamértékek összegei egyenlőek).
• Telített él: olyan él, amely esetében a lehető legnagyobb a folyam értéke.
• Folyamérték: a forrásból kifolyó értékek összege, ami egyenlő a nyelőbe befolyó értékek összegével.
• 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.

Tételek és összefüggések

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

8. Menger tételei, gráfok összefüggőségi számai, Dirac-tétel (bizonyítás nélkül)

Jegyzetek, videók

• Menger tételei videó

Definíciók

• Élidegen utak: olyan utak, melyekben nincs közös él.
• Pontidegen utak: olyan utak, melyekben nincs közös pont.
• k-szorosan élösszefüggő gráf: akárhogy hagyunk el belőle k-nál kevesebb élet, a maradó gráf összefüggő marad.
• 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.

Tételek és összefüggések

• 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.
  • Ha s és t nem szomszédosak, akkor az s-ből t-be vezető, végpontoktól eltekintve pontidegen utak maximális száma egyenlő az s-t utakat s és t használata nélkül lefogó pontok minimális számával.
• k-szoros élösszefüggőség feltétele: egy gráf akkor és csak akkor k-szorosan élösszefüggő, ha bármely két pontja között létezik k élidegen út.
• k-szoros pontösszefüggőség feltétele: egy gráf akkor és csak akkor k-szorosan pontösszefüggő, ha legalább [math]k+1[/math] pontja van és bármely két pontja között létezik k pontidegen út.
• Kétszeresen összefüggő gráf feltétele (Menger): a legalább 3 pontú gráf akkor és csak akkor kétszeresen pontösszefüggő, ha tetszőleges két pontján át vezet kör. Az is igaz, hogy akkor és csak akkor kétszeresen pontösszefüggő, ha bármelyik két élén át vezet kör.
• 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.

9. Pont- és élszínezés, korlátok a kromatikus számra, Mycielski-konstrukció, Brooks-tétel (bizonyítás nélkül)

Definíciók

• 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.
• Színosztályok: a gráf színezésekor az azonos színt kapott csúcsok halmazai.
• Klikk: a gráf egy teljes részgráfja.
• Klikkszám: a gráfban található összes klikk közül a legnagyobb adja a gráf klikkszámát.

Tételek és összefüggések

• 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.
• Mycielski-tétel: minden [math]k\leq 2[/math] egész számra van olyan gráf, amelynek a klikkszáma 2 de a kromatikus száma k.
• 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.

Algoritmusok, eljárások és egyebek

• 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:
  1. Rajzoljuk le az eredeti gráf [math]v_1,...,v_n[/math] pontjait a köztük lévő élekkel együtt.
  2. 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.
  3. 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.
  4. Állítás: ha [math]n\leq 2[/math], olyan gráfot rajzoltunk, ami megfelel a Mycielski-tételnek.

10. Síkbarajzolhatóság, Euler-féle poliédertétel, Kuratowski tétele (csak könnyű irányban bizonyítani), Fáry-Wagner-tétel (bizonyítás nélkül)

Jegyzetek, videók

• Síkbarajzolhatóság, Euler-féle poliédertétel videó
• Bizonyítás, hogy K5 és K3,3 nem síkbarajzolhatók videó

Definíciók

• 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:
  1. Egy él "közepére" egy pont beszúrása, vagyis egy él 2-hosszú úttal való helyettesítése.
  2. 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

• 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].
• Kuratowski-tétel: egy gráf akkor és csak akkor síkbarajzolható, ha nem tartalmaz olyan részgráfot, ami topologikusan izomorf a Kuratowski-gráfok valamelyikével.
• 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.

Algoritmusok, eljárások és egyebek

• Sztereografikus projekció - síkgráf gömbre rajzolása.
  1. Tegyük a gömböt a síkra.
  2. Ahol a gömb a síkkal érintkezik, legyen a déli pólus.
  3. Az északi pólust összekötjük a síkon a gráf pontjaival.
  4. Ahol az egyenesek metszik a gömb felszínét, azok a gömbre rajzolt gráf megfelelő pontjai.
  5. 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

Definíciók

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

Tételek és összefüggések

• 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:
    1. 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.
    2. 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.
    3. 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.
• 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.

12. Mélységi keresés és alkalmazásai (pl. irányított kör létezésének eldöntése), PERT-módszer, kritikus tevékenységek

Jegyzetek, videók

• BFS, DFS videó

Definíciók

• 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.
• Vissza-él: ezek a DFS-felbontáshoz képest ellentétes irányba mutatnak.
• Kereszt-él: ezek pedig "azonos szinten lévő" pontokat kötnek össze.
• Kritikus út: a PERT-módszer alkalmazása során talált leghosszabb út.
• 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.

Tételek és összefüggések

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

Algoritmusok, eljárások és egyebek

• Mélységi keresés:
  1. Kiválasztjuk a kiindulási pontot.
  2. Meglátogatjuk a legkisebb sorszámú olyan szomszédját, amit még nem látogattunk meg.
  3. Az előbbi lépést ismételgetjük, amíg tudjuk.
  4. 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.
  5. 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.
• PERT-módszer. Munkafolyamatok ütemezésére jó.
  1. 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.
  2. 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).
  3. 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.
  4. 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

Jegyzetek, videók

• 2. Tétel videó (2012/II tételsor) - magyar: Lineáris és Bináris keresés, Buborék-, Kiválasztásos-, Beszúrásos-, Összefésüléses-, és Gyorsrendezés
• 3. Tétel videó (2012/II tételsor) - magyar: Ládarendezés, Bináris keresőfa, Kupacrendezés
• Lineáris és logaritmikus keresés videó
• Szomszédsági tömb és mátrix videó (5.54-től)
• Beszúrásos rendezés videó
• Buborékrendezés videó
• Összefésüléses rendezés videó
• Rendezőalgoritmusok összehasonlítása videó

Definíciók

• 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
  • [math] b_{i,j} = 0 [/math], ha a j. él nem illeszkedik az i. ponthoz
  • [math] b_{i,j} = 1 [/math], ha a j. élnek az i. pont a kezdőpontja, illetve, ha a j. él az i. pontra illeszkedő hurokél
  • [math] b_{i,j} =-1 [/math], ha a j. élnek az i. pont a végpontja
• Szomszédsági mátrix: _n_ pontú gráf [math] n \times n [/math] méretű szomszédsági mátrixának elemei
  • [math] a_{i,j} = 0 [/math], ha az i. és j. pont nem szomszédos
  • [math] a_{i,j} = k [/math], ha az i. és j. pont között _k_ darab párhuzamos él halad
  • [math] a_{i,j} = l [/math], ha az [math] i=j [/math] és az i. ponthoz _l_ darab hurokél csatlakozik
• 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
  1. 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.)
  2. 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.)
  3. 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.

Algoritmusok, eljárások és egyebek

• 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
  1. Kiválasztjuk a tömb első elemét. Ez így egyedül egy rendezett tömböt alkot.
  2. 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.
  3. Vesszük a harmadikat. Ha nagyobb, mint a második, hagyjuk, ha kisebb, megcseréljük, majd összehasonlítjuk az elsővel is.
  4. 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].
• Összefésüléses rendezés
  1. 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.
  2. A kezdeti, rendezetlen, _k_ hosszú tömbre ezután úgy tekintünk, mint _k_ darab, rendezett, 1 hosszú tömbökre.
  3. 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].
• Buborék-rendezés
  1. 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.
  2. 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.
  3. 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].
• 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
  1. 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.
  2. Toszogassuk bele a létrehozott ládákba az elemeinket.
  3. A ládákon belül rendezzük az elemeket valami kényelmes módon.
  4. 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.

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

Definíciók

• 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-beli probléma: olyan probléma, mely esetében az igenlő válasz polinom időben bizonyítható.
• co-NP-beli probléma: olyan probléma, mely esetében a nemleges válasz polinom időben bizonyítható.
• Polinomiális visszavezethetőség: ha ismerem egy probléma megoldását és ennek az ismeretnek a birtokában meg tudok oldani egy másikat, akkor ezt a másikat visszavezettem az elsőre.
• NP-nehéz probléma: olyan probléma, melyre minden NP-beli visszavezethető.
• NP-teljes probléma: olyan NP-nehéz probléma, mely maga is NP-ben van.

Tételek és összefüggések

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

15. Oszthatóság, legnagyobb közös osztó, legkisebb közös többszörös, prímek, felbonthatatlanok, a számelmélet alaptétele, osztók száma, euklideszi algoritmus, nevezetes tételek prímszámokról

Jegyzetek, videók

• Euklideszi algoritmus legnagyobb közös osztó keresésére videó
• Euklideszi algoritmus maradékos osztáshoz videó

Definíciók

• 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.
• Felbonthatatlan: egyetlen módon alakítható egész számok szorzatára, mégpedig: [math]a = bc[/math] módon úgy, hogy _b_ és _c_ közül egyik egység, a másik pedig önmaga vagy ellentettje. A természetes számok körében a felbonthatatlanok a prímek.
• Legkisebb közös többszörös: két szám, _a_ és _b_ lkkt-e az a legkisebb szám, amelynek osztója _a_ és _b_.
• Legnagyobb közös osztó: két szám, _a_ és _b_ lnko-ja az a legnagyobb szám, amely még osztója _a_-nak és _b_-nek.
• Relatív prímek: lnko-juk 1.

Tételek és összefüggések

• 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.
• Osztók összege: [math] \sigma(n) = \prod_{i=1}^{k} \left( \frac{p_{i}^{\alpha_i + 1} - 1}{p_i -1} \right) [/math], ahol [math]p_i[/math] az i. prímtényező.
• 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].

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\gt b[/math], ekkor:
  1. 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].
  2. 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.
  3. 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

Jegyzetek, videók

• Kongruenciák megoldása videó

Definíciók

• 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.
• Teljes maradékrendszer: ha a mod _m_ maradékosztályokból kiválasztunk egy-egy tetszőleges elemet, akkor a mod _m_ teljes maradékrendszerét nyertük.
• 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.

Tételek és összefüggések

• [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\gt 1[/math], akkor [math] a^{\varphi(m)} \equiv 1 (\text{mod } m) [/math].
• Kis Fermat-tétel: tetszőleges _p_ prímre és _a_ egészre [math] a^p \equiv a (\text{mod } p) [/math].
• Wilson-tétel

Algoritmusok, eljárások és egyebek

• Lineáris kongruenciák megoldása

17. Félcsoportok, csoportok, példák, csoport rendje, elem rendje, szimmetrikus idomok egybevágósági transzformációinak csoportja, ciklikus csoport, az [math]S_n[/math] szimmetrikus csoport

Definíciók

• 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].
• Asszociativitás: [math] (a*b)*c = a*(b*c)[/math].
• Disztributivitás: [math] (a+b)*c = a*c+b*c[/math].
• Egységelem: [math] 1*a = a*1 = a[/math].
• Inverz: [math] a*a^{-1} = a^{-1}*a = 1 [/math], ekkor [math] a^{-1} [/math] az inverz.
• Félcsoport: halmaz és rajta értelmezett asszociatív művelet.
• Abel-féle félcsoport: olyan félcsoport, melyben a művelet kommutatív is.
• Csoport: halmaz, és a rajta értelmezett assziciatív művelet, létezik egységelem és inverz.
• Abel-féle csoport: olyan csoport, amiben teljesül a kommutativitás is.
• Csoport rendje: a csoport elemszáma.
• Diédercsoport: a szabályos _n_-szög egybevágósági transzformációinak csoportja (rendje 2n).
• n-ed fokú szimmetrikus csoport: _n_ elem permutációinak csoportja.
• Csoportok izomorfiája: két csoport akkor izomorf, ha van köztük kölcsönösen egyértelmű, művelettartó leképzés.
• Ciklikus csoport: az egy elem (_a_) által generált részcsoportok, melyek tartalmazzák _a_-t és hatványait.
• 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.

Tételek és összefüggések

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

18. Részcsoport, mellékosztály, Lagrange tétele, elem és csoport rendjének kapcsolata, gyűrűk, nullosztó, példák, testek, példák

Definíciók

• 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.
• Valódi részcsoport: a nem triviális részcsoportok.
• Generált részcsoport: _K_ legyen részhalmaza _G_ csoportnak. A _K_ által generált részcsoport a _K_-t tartalmazó legszűkebb részcsoport.
• Mellékosztály: _G_ részcsoportja _H_. _H_ szorzata _g_-vel, ami _G_ csoport eleme, a _H_ _g_ szerinti mellékosztálya.
• Reprezentáns: az előző definícióból _g_ a mellékosztály reprezentánsa.
• Normálosztó: legyen _N_ részcsoportja _G_-nek. _N_ normálosztó _G_-ben, ha _N_ jobb- és baloldali mellékosztályai megegyeznek.
• Nullelem: "additív egység", [math] 0+a = a+0 = a[/math].
• Gyűrű: halmaz, rajta értelmezett két művelettel (+, *), a következő tulajdonságokkal:
  • kommutatív a +-ra
  • asszociatív a +-ra
  • van nullelem
  • van additív inverz (minden _a_-hoz létezik olyan a', hogy [math] a+a' =0 [/math])
  • asszociatív a *-ra
  • disztributivitás a két művelet között
• Kommutatív gyűrű: olyan gyűrű, melyben a * is kommutatív.
• Egységelemes gyűrű: olyan gyűrű, melyben van a *-ra nézve egységelem.
• Kivonás: _a_ - _b_ = _a_ és _b_ additív inverzének összege.
• Ferdetest: olyan egységelemes gyűrű, mely a szorzásra balinverz.
• Test: olyan ferdetest, melyben a szorzás kommutatív.
• Nullosztó: gyűrű olyan nem 0 eleme, amelyet egy másik nem 0 elemmel összeszorozva 0-t kapunk.
• Intgrálási tartomány: kommutatív, nullosztómentes gyűrű.

Tételek és összefüggések

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

19. Számelméleti algoritmusok, prímtesztelés, nyilvános kulcsú titkosítás, bizonyítás információközlés nélkül

Definíciók

• Á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.
• Carmichael-szám: másnéven univerzális álprím, olyan összetett szám, mely minden alapra álprímként viselkedik.
• Nyilvános kulcsú titkosírás: olyan eljárás, ahol a felhasználó egy kulcspárral – egy nyilvános és egy titkos kulccsal rendelkezik. A titkos kulcs titokban tartandó, míg a nyilvános kulcs széles körben terjeszthető. A kulcsok matematikailag összefüggnek, ám a titkos kulcsot gyakorlatilag nem lehet meghatározni a nyilvános kulcs ismeretében. Egy, a nyilvános kulccsal kódolt üzenetet csak a kulcspár másik darabjával, a titkos kulccsal lehet visszafejteni.
• Kódoló függvény: a kulcspár nyilvános része.
• Dekódoló függvény: a kulcspár titkos része. A kódoló és dekódoló függvény egymás inverzei.

Algoritmusok, eljárások és egyebek

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