Az eddig leadott anyag Diszkrét matematika II tárgyhoz 2011. tavasz A (+)-szal jelzett tételek bizonyítással együtt, a (-)-szal anélkül értendők! A tételek esetleges neve, vagy száma a fóliákkal van szinkronban, bár a nyomtatott jegyzetben is megtalálhatóak.
6. Számelmélet 6.1 Osztahtóság Fogalmak, definíciók: Osztó, egység, asszociáltak, triviális osztó, felbonthatatlan és prím elem egységelemes integritási tartományban, összetett szám Z-ben, legnagyobb közös osztó, relatív prímek, páronként relatív prímek, legkisebb közös többszörös egységelemes integritási tartományban, páros számok, páratlan számok, prímek száma, prímek közti „szakadék”, (módosított) kanonikus alak, lnko és lkkt-re vonatkozó észrevételek, Erathosztenész szitája, kongruencia,
Tételek(-): Kongruencia tulajdonságai
Tételek(+): Prím és felbonthatatlan elem kapcsolata az egész számok gyűrűjében, a számelmélet alaptétele egész számokra, Euklidész tétele
6.2 Kongruenciák Fogalmak, definíciók: Kongruencia, m szerinti maradékosztály, m szerinti redukált maradékosztály, teljes maradékrendszer modulo m, redukált maradékrendszer modulo m, Euler-féle függvény, lineáris kongruencia megoldása
Tételek(-): Kínai maradéktétel
Tételek(+): Nullosztók Zm-ben (Zm mikor test), omnibusz tétel, Euler-Fermat tétel, (kis) Fermat-tétel
6.3 Számelméleti függvények Fogalmak, definíciók: Additív és multiplikatív számelméleti függvények, totalitás (teljesség),
Tételek(-): Additív és multiplikatív számelméleti függvények kiszámítása
Tételek(+):
multiplikatív, φ kiszámolása
7. Gráfelmélet
7.1. Alapfogalmak, összefüggőség Fogalmak, definíciók: Gráf (egyszerű, véges, reguláris, teljes, összefüggő) / él (hurok, párhuzamos, szomszédos, szeparáló) / csúcs (izolált, szomszédos, fokszám, illeszkedés, szeparáló) / gráfok izomorfiája / részgráf (telített) / komplementer gráf / (zárt, nyílt) élsorozat(séta) / út, vonal / kör / fa / feszítőfa / alapkörrendszer / vágás / (feszítő)erdő / nullitás / rang Gráf súlya / Kruskalalgoritmus / Euler-gráf / Euler-kör / Hamilton-gráf / Hamilton-kör.
Tételek(+): Fokszám-élszám / út létezése / zárt vonal gráfban / 4 ekvivalens feltétel egyszerű gráfra(7.1.11)
/ elsőfokú pont fában / fa éleinek száma(7.1.13) / feszítőfa létezése. /
nullitás(7.1.16) / rang(7.1.19) / Kruskal algoritmusa / Euler-formula / Euler-gráfok(7.1.22).
7.2. Irányított gráfok, síkbarajzolhatóság Fogalmak, definíciók: Kifok, befok, forrás nyelő / (szigorúan) párhuzamoos élek / irányított élsorozat (zárt, nyílt) / út / kör / fa / irányított gráfok izomorfiája / erős összefüggőség / összefüggő és erősen összefüggő komponensek / irányított fa, gyökér, levél, szint magasság, szülő, gyerek, testvér / síkbarajzolhatóság, tartomány / Kuratowski-gráfok / topologikus izomorfia / csúcsmátrix (szomszédsági mátrix) / illeszkedési mátrix (élmátrix).
Tételek(+): Síkgráf éleinek száma / síkgráf fokszámai / Kuratowski gráfok.
Tételek(-): Irányítot gráf fokszámai / irányított gráf erős összefüggősége / síkba-gömbre rajzolás / külsőbelső tartomány / Kuratowski-tétel.
8. Algebra 8.1. Csoportok Fogalmak, definíciók: Algebrai struktúrák, izomorfiájuk / n-ér művelet / additív és multiplikatív írásmód / morfizmusok / hommorf kép / műveleti tulajdonságok: asszociativitás, regularitás, kommutativitás, invertálhatóság, típusok / grupoid, félcsoport, csoport Abel-csoport / ntényezős szorzat / egységelemmel és inverzzel kapcsolatos fogalmak / komplexus / komplexus szorzás / részcsoport / generátum / véges, végtelen ciklikus csoport / elem, csoport rendje / jobb és bal oldali mellékosztály / reprezentánsrendszer / részcsoport indexe / triviális (rész)csoport / invariáns részcsoport (normálosztó) / belső automorfizmus / faktor csoport / természetes homomorfizmus és tulajdonságai / homomorfizmus magja / direkt szorzat / szimmetrikus csoport.
Tételek(+): Egységelem unicitása / inverz unicitása / csoportdefiníciók ekvivalenciája / regularitás / komplexusok félcsoportja / ekvivalens állítások részcsoportokra / részcsoportok metszete és uniója / generátum elemei / ciklikus csoport részcsoportja ciklikus / ciklikus csoportok izomorfiája(8.1.20) / véges ciklikus csoport részcsoportjai(8.1.23) / Lagrange-tétel és következményei / prímszámrendű csoport / homomorfizmus-tétel / Cayley tétele.
Tételek(-): Asszociativitási törvény / ciklikus csoport homomorf képe / véges Abel-csoportok alaptétele / homomorf invariánsok félcsoportban / invariáns részcsoportokra vonatkozó ekvivalens állítások.
8.2. Gyűrűk
Fogalmak, definíciók: Gyűrű, kommutatív gyűrű, integritási tartomány, test / nullelem, egységelem / nullgyűrű, zérógyűrű / nullosztó / karakterisztika / Bool-gyűrű / gyűrűhomomorfizmus / asszociáltak / legnagyobb közös osztó, / részgyűrű, (triviális, valódi, fő) ideál / egyszerű gyűrű / főideálgyűrű / ideál szerinti mellékosztályok / faktorgyűrű / homomorfizmus magja / oszthatóság, egységek / asszociált / felbonthatatlan, prím / részgyűrű, (triviális, valódi, fő) ideál, egyszerű gyűrű / faktorgyűrű / prímideál, maximális ideál / euklidészi gyűrű / oszthatóság, egységek / Gauss-egészek / triviális euklidészi gyűrű / Gauss-gyűrű ((egyértelmű) faktorizációs tartomány, UFD) / főideál / főideálgyűrű / hányadostest / gyűrűhierarchia felrajzolása.
Tételek(+): Észrevételek(előjelszabály, véges integritási tartomány, nullosztó testben, szorzás a nullelemmel) / nullosztó és regularitás / gyűrű karakterisztikája / gyűrű homomorf képe / felbonthatatlan és prím integritási tartományban / felbonthatatlan és prím Gauss-gyűrűben) / egység és egységelem integritási tartományban / egységek euklidészi gyűrűben(8.2.30) / euklidészi gyűrű fõideálgyűrű (2.8.35) / irreducibilitás és főideál
kapcsolata euklidészi
gyűrűben / Szükséges és elégséges feltétel, hogy R/I test, illetve integritási tartomány legyen + következmény / triviális ideálok és testek kapcsolata.
Tételek(-): homomorfizmus-tétel / főideálokról szóló állítások(8.2.25, 8.2.26) / bővített euklidészi algoritmus / számelmélet alaptétele eukl. gyűrűben(8.2.34) / fõideálgyűrű Gauss-gyűrű. 8.3. Poinomok Fogalmak, definíciók: Polinom és kapcsolódó fogalmak / polinom műveletek / változó / polinom foka, konstans polinom, monom, főpolinom, primitív polinom / helyettesítési érték, gyök / polinomfüggvény / Horner-elrendezés / gyökök száma / polinom algebrai deriváltja / többszörös gyök / irreducibilis polinomok különböző számhalmazok felett / hányadostest / racionális függvénytest / polinomgyűrűk hierarchiája.
Tételek(+): Polinomok maradékos osztása / test feletti polinomgyűrű / gyöktényező leválasztása / többszörös gyök és derivált polinom kapcsolata / parciális törtekre bontás. . Tételek(-): Polinom gyökeinek száma + következmények(8.3.7, 8.3.8) / Schönemann- Eisenstein-tétel / Gauss-tétel.
