Az előadás helye és ideje: Hétfő 10.15-13.00, Déli épület 0-822, Mogyoródi József terem
Előadáson való részvétel kötelező, legfeljebb 3 hiányzás megengedett.
A vizsga szóbeli, melyet írásbeli beugró előz meg. A beugró a Neptunban meghírdetett helyen lesz, kezdete 8.15, időtartalma 35 perc. A beugrón 7 kérdés kerül kitűzésre, melyből minimum 5-re helyes válasz kell adni. A beugrón egysoros számológép használható. A beugrón szereplő alapfogalmak (a lista végleges).
A sikeres beugrót szóbeli vizsga követi. A vizsgán szereplő tételek (a lista véglelges). A tételsor két részből áll. A vizsgán mindkét részből kap a vizsgázó egy-egy tételt. A szóbeli rész sikerességének feltétele, hogy a vizsgázó mindkét tételéről legalább elégséges szinten számot tudjon adni.
A gyakorlati jegy feltétele, a gyakorlaton való részvétel, legfeljebb 3 hiányzással. A gyakorlatok elején a gyakorlatvezető rövid tesztet írat az előadáson elhangzott egyszerű fogalmakból, definíciókból, tételekből, melyre +1/-1 eredményt lehet kapni (hiányzás esetén 0). A gyakorlati jegy további feltétele, hogy félév végén a tesztek összeredménye legalább 0 legyen.
A gyakorlati számonkérés 2 db zh (6-6 feladat, 2x60 pont) formájában történik, ezek a gyakorlatok időpontjában lesznek (80-90 perc). A feladatok a központi feladatsorok alapján lesznek válogatva (1. zh: márc. 24-28., 2. zh: máj. 12-16.). A ponthatárok: (zh-nként) 20-tól 2-es, 30-tól 3-as, 40-től 4-es, 50-től 5-ös. Az év végi jegy a két zh összpontszámja alapján kerül meghatározásra: 40-től 2-es, 60-tól 3-as, 80-tól 4-es, 100-tól 5-ös. Akinek mindkét zh-ja 1-es, a gyakorlati jegye automatikusan 1-es, akinek csak az egyik, az a vizsgaidőszak első hetében újraírhatja azt. Akinek nem sikerül javítani az 1-es zh-t azok szintén 1-es gyakorlati jegyet kapnak.
Minden gyakorlatvezető adhat maximum plusz 10 pontot a féléves munkára (szorgalmi feladatok megoldására).
A gyakorlathoz utóvizsga nincs.
A zárthelyi dolgozatokat 2014.05.19. (hétfő) napon a DT 0-805 teremben lehet pótolni, javítani.
Első dolgozat: 8.30-10.00
Második dolgozat: 10.15-11.45 8.30-10.00
Legfeljebb egy dolgozatot lehet pótolni, javítani. A feladatsorokat a gyakorlatvezetők állítják össze (nem lesz egységes feladatsor).
Járai Anral (szerk.): Bevezetés a Matematikába (Informatikai Alkalmazásokkal) c. könyv 7-10 fejezetei. A könyvben szereplő feladatok külön is letölthetőek.
1. előadás, 2014. 02. 10:
Gráfelmélet
Irányítatlan gráf, illeszkedés, párhuzamos élek, hurokélek, szomszédosság, véges gráf, fok, reguláris gráf,
páros gráf, példák (teljes gráf, teljes páros gráf, pl. három ház-három kút), izomorfizmus, részgráf. Séta, vonal, út, kör.
Távolság, összefüggőség, komponensek.
2. előadás, 2014. 02. 17:
Gráfelmélet
Feszített részgráf, komplementer. Fák, ekvivalens tulajdonságok. Feszítőfa, körök száma gráfokban. Elvágó csúcs- és élhalmaz,
vágások, vágások száma gráfokban. Euler-vonal.
3. előadás, 2014. 02. 24:
Gráfelmélet
Euler-volnal, szükséges és elégséges feltétel zárt Euler-vonal létezésére. Hamilton-út és kör. Ore és Dirac tétele
Hamilton-kör létezéséről. Címkézett és súlyozott gráfok, Kruskal algoritmusa minimális súlyú feszítőfa keresésére. Irányított gráfok,
alapfogalmak. Erősen összefüggő irányított gráfok, erős komponensek.
4. előadás, 2014. 03. 03:
Gráfelmélet, csoportok
Irányított fák. Síkba rajzolható gráfok. Euler tétele, példa nem síkba rejzolható gráfokra, Kuratowski tétele. 4-szín tétel.
Csoport fogalma, példák csoportokra, diéder csoportok.
5. előadás, 2014. 03. 10:
Csoportok, gyűrűk, polinomok
Generátorok, részcsoportok, ciklikus csoportok. Ciklikus csoportok karakterizációja, részcsoportjai, generátorai.
Gyűrűk fogalma, példák. Kommutatív, nullosztómentes, egységelemes gyűrűk, integritási tartomány, testek.
Polinomok fogalma, polinom foka, szorzat polinom fokára vonatkozó korlát.
6. előadás, 2014. 03. 17:
Polinomok
Polinomfüggvény. Maradékos osztás, gyöktényező kiemelhetősége, gyökök és fok közötti összefüggés és következményei.
Legnagyobb közös osztó, bővitett euklideszi algoritmus. Irreducibilis polinomok és polinomok felbontása irreducibilisek szorzatára.
Horner-elrendezés. Algebrai derivált és az azt leíró tulajdonságok. Többszörös gyökök és kapcsolatuk az algebrai deriválttal.
Irreducibilis polinomok komplex számtest fölött.
7. előadás, 2014. 03. 24:
Polinomok
Irreducibilis polinomok valós számtest fölött. Irreducibilitás az egészek fölött, primitív polinomok, Gauss tétele.
Schönemann-Eisenstein kritérium, racionális gyökteszt. Lagrange interpoláció és titokmegosztás.
Testek, testbővítések
Kongruencia polinomok között. Testbővítésre vonatkozó tétel.
8. előadás, 2014. 03. 31:
Testek, testbővítések
Testbővítésre vonatkozó tétel. Véges testek alaptétele. Véges testek struktúra tétele, additív és
(multiplikatív) rend fogalma.
Kódelmélet, üzenet kódolás.
Betűnkénti kódolás fogalma, felbontható, prefix, egyenletes, vesszős kód.
9. előadás, 2014. 04. 07:
Kódelmélet, üzenet kódolás.
Kódfa. Példák
Kódelmélet, hibajavító kódolás.
Példák: ISBN, paritásbit, kétdimenziós paritásbit. t-hibajelző kódok. Hamming távolság és tulajdonságai. Kódtávolság.
Minimális távolságú dekódolás. t-hibajavító kódok. Singleton és Hamming korlát.
10. előadás, 2014. 04. 14:
Kódelmélet, hibajavító kódolás.
Hamming korlát. Lineáris kódok. Szavak súlya, a súly kapcsolata a távolsággal. Generátormátrix, ellenörzőmátrix.
Ellenörzőmátrix és kódtávolság. Szisztematikus kódolás fogalma és ellenörzőmátrixsza. Hamming-kódok.
11. előadás, 2014. 04. 28:
Kódelmélet, hibajavító kódolás.
Szindróma dekódolás. Ciklikus kódok, polinomkódok, generátorpolinom, ellenörzőpolinom.
12. előadás, 2014. 05. 05:
Kódelmélet, hibajavító kódolás.
CRC kódok, Reed-Solomon-kód. Kódkombinációk
Kódelmélet, gazdaságos kódolás.
McMillan-egyenlőtlenség.
13. előadás, 2014. 05. 12:
Kódelmélet, gazdaságos kódolás.
Átlagos kódhossz. Entrópia. Shannon tételek az átlagos kódhossz és entrópia kapcsolatáról. Optimális kód.
Konstrukció optimális kódra, Huffman-kód.
Példa nem betűnkénti gadaságos kódolásra, LZW.