Diszkrét matematika 2 tételsor (B szakirány)

Gráfok

Irányítatlan gráfok: egyszerű gráf; izomorfia; \(K_n\), \(C_n\), \(P_n\), \(S_n\), \(H_n\); gráfok direkt szorzata; részgráf, feszített részgráf; séta; vonal; út; kör; összefüggőség; komponensek; fák, éleinek száma és ekvivalens definíciók; erdők feszítőfa, feszítőerdő; körök száma (alapkörrendszer); vágások száma;
Euler vonalak és Hamilton utak: Zárt Euler vonal létezése egy gráfban, és páratlan fokszámú csúcsokat tartalmazó gráfok dekompozíciója éldiszjunkt vonalakra; Hamilton út; Hamilton kör; Ore tétel; Dirac tétel.
Címkézett és irányított gráfok: címkézett gráfok; Kruskal algoritmus; irányított gráfok; gráfok éllistás reprezentációja; erős összefüggőség; irányított fák; Dijkstra algoritmusa; síkba rajzolható gráfok; Euler formula; jól színezés; kromatikus szám.

Csoportok: rész(fél)csoportok; homomorfizmusok; reprezentáció; csoportok ekvivalens definíciója; egyszerűsítési szabály; részcsoportok metszete; generátum, generátor rendszer. ciklikus csoport homomorf képe; csoport és emelem rendje; ciklikus csoportok jellemzése; ciklikus csoport részcsoportjai.
Mellékosztályok: mellékosztályok (jobb és baloldali); Lagrange tétel; normálosztó; faktorcsoport; homomorfizmus tétel; csoportok direkt szorzata; véges Abel–csoportok alaptétele.
Gyűrűk: karakterisztika és az ide tartozó állítás; részgyűrű; ideál; ideál szerinti mellékosztályok; faktorgyűrű; (gyűrű) homomorfizmus tétel; direkt szorzata; főideálok kommutatív egységelemes gyűrűben illetve egységelemes integritás tartományban;
Gauss gyűrűk: Gauss gyűrű; osztók, lnko, lkkt meghatározása Gauss gyűrűben; példa egységelemes integritásra ami nem Gauss gyűrű; Euklideszi gyűrű; Euklideszi és Gauss gyűrű kapcsolata; bővített Euklideszi algoritmus Euklideszi gyűrűben; hányadostest.

Polinomok: polinomok; polinomfüggvény; maradékos osztás tétel polinomgyűrűben; gyöktényező leválasztása és következményei; Horner elrendezés; algebrai derivált; többszörös gyökök;
Irreducibilis polinomok: \(\mathbb{C}\), \(\mathbb{R}\), \(\mathbb{Q}\) és \(\mathbb{Z}\) feletti Irreducibilis polinomok; testbővítések; véges testek alaptétele; Gauss tétel; Schönemann-Eisenstein tétel; Lagrange interpoláció, titok megosztás.

Forrás kódolás: Egyedi információ mennyiség; entrópia; betűnkénti kódolás; prefix, egyenletes, vesszős kód; McMillan egyenlőtlenség; Shannon tétele zajmentes csatornákra és Shannon kód létezéséről szóló tétel; Huffman kód.
Hiba korlátozó kódok: \(t\) hiba jelző és pontosan \(t\) hiba jelző kód; Hamming távolság; kód távolság; minimális távolságú dekódolás; \(t\) hiba javító és pontosan \(t\) hiba javító kód; szeparábilis kód; szisztematikus kód; Hamming korlát; tökéletes kód; Singleton korlát; MDS kód.
Lineáris kód: generátor mátrix; hibaellenőrző mátrix; szindróma dekódolás; polinom kód; generátor polinom; CRC kód.