Budapest University of Technology and Economics, Faculty of Electrical Engineering and Informatics

Alapvető gráfelméleti, kombinatorikai fogalmak, algoritmusok. 

Elemi leszámlálások, fák, Euler és Hamilton utak, körök, folyamok, párosítások, síkgráfok. 

1. Perfekt gráfok, intervallumgráfok, egyéb példák, Gyenge perfekt gráf tétel, erős perfekt gráf tétel 

2. Részbenrendezett halmazok, Dilworth tétel, duális Dilworth tétel 

3. Síkgráfok, súlyátrendező módszer, Ackerman-Tardos tétel, geometriai és absztrakt dualitás, Whitney tételei  

4. Listaszínezési szám, viszonya a kromatikus számhoz, Kőnig tétel, Galvin tétel, síkgráfok listaszínezési száma, Thomassen és Voigt tételei 

5. Ramsey tétel gráfokra, felső becslés R(k, l)–re (Erdős–Szekeres tétel), Erdős–féle alsó becslés, valószínűségi módszer  

6. Ramsey tétel hipergráfokra (biz nélkül) Schur, Van der Waerden tételek 

7. Turán tétel, Erdős–Stone (biz. nélkül), Erdős–Simonovits (Ex(n, H) kapcsolata χ(H)–val)),  

8. C4–mentes gráfok maximális élszáma, Erdős–Kővári–Sós–Turán tétel  

9. Hipergráfok, Erdős–Ko–Rado tétel, Fisher egyenlőtlenség, Ray-Chaudhuri–Wilson tétel 

10. Sperner tétel, LYM egyenlőtlenség 

11. Duális hipergráf, De Bruijn–Erdős tétel, véges projektív síkok

A tárgyból heti 2 óra előadás és heti 2 óra gyakorlat van. 

Az előadásokon az új elmélet kerül bemutatásra, ennek gyakorlása és feladatokban való alkalmazása zajlik a gyakorlatokon. A gyakorlatok mindig szorosan kapcsolódnak a megfelelő előadás anyagához, ezért azokon az  előadáson tanult anyag ismerete elvárás a hallgatóktól. Az előadásokon tárgyalt fogalmak és ismeretek begyakorlása, elmélyítése a gyakorlatokon zajlik, az itt zajló munka (beleértve a házi feladatok megoldását is) a tanulási folyamat alapvető fontosságú része. Az előadások a legtöbb esetben felhasználják a korábbi hetek anyagát, ezek ismerete nélkül az új anyag általában nem, vagy nehezen követhető. 

A szorgalmi időszakban: A félév folyamán egy zárthelyit íratunk. A félévvégi aláírás megszerzésének (vagyis a vizsgára bocsátásnak) feltétele a zárthelyin legalább 40% -os teljesítmény. Ezen kívül minden héten adunk házi feladatot, ezek beadása nem kötelező. 

A vizsgaidőszakban:Vizsgára az jelentkezhet, aki érvényes aláírással rendelkezik.  

A vizsga ebből a tárgyból szóbeli. A vizsga megkezdésekor a vizsgázó a tárgyhoz tartozó tételsorból egyetlen tételt kap, amelynek a kidolgozására (vagyis a szóbeli felelethez egy bő jegyzet készítésére) legalább 45 perc áll rendelkezésre. A felelet abból áll, hogy egyrészt a vizsgázó a jegyzeteire támaszkodva részletesen beszámol a húzott tételről, másrészt a vizsgáztató néhány szúrópróbaszerű, az anyag többi részével kapcsolatos kérdésére válaszol. (A vizsga sikerességéhez tehát nem elég a kihúzott tétel ismertetése, az imént említett további kérdésekre is kell tudni válaszolni.) Az elégséges eléréséhez nem szükséges a bizonyításokat, de az alapvető definíciókat, tételeket, összefüggéseket tudni kell.  

A vizsgajegyet a zárthelyi eredményéből, a házi feladatokból szerzett pontokból  és a vizsgán nyújtott szóbeli teljesítményből alakítjuk ki olyan módon, hogy abba a zárthelyi 25 százalékot, a hazi feladatokból kapott pontok 25 százalékot,  a szóbeli vizsga 50 százalékot számít. Ha a szóbeli vizsga elégtelen, akkor a vizsgajegy is elégtelen (függetlenül a zárthelyik eredményétől). Ismétlő vizsga esetén a zárthelyikből és házi feladatokból származó eredmények változatlanul érvényesek. 

A szorgalmi időszakban egyetlen pótzárthelyi alkalom lesz, amelyen a zárthelyi eredménye javítható vagy a hiányzás pótolható. 

A pótzárthelyin tehát a korábban megírt, eredményes zárthelyi javítása is megkísérelhető, de csak azzal a feltétellel, hogy ilyenkor mindenképpen az új pontszám lesz érvényes, akkor is, ha az rosszabb, mint az eredeti. Ez alól egy kivétel van: ha egy hallgató a normál zárthelyin legalább 40%-os teljesítményt ért el és így az aláírás feltételeit már teljesítette, de a javítónak szánt pótzárthelyin 40% alatti teljesítményt ér el, akkor a hallgató az aláírást megkapja, de a zárthelyiből származó pontszáma a 40%-os eredménynek megfelelő, minimális pontszám lesz. 

A vizsgaidőszak előtti pótlási héten lehetőség nyílik a zárthelyi újbóli pótlására illetve javítására. 

Amennyiben a zárthelyi és a pótzárthelyi segítségével sem sikerül az aláírás feltételeit teljesíteni,  ennek a második pótzárthelyi alkalomnak a neve “díjköteles pótlás”. Sikeres díjköteles pótlás esetén a  zárthelyiből származó pontszám a 40%-os eredménynek megfelelő, minimális pontszám lesz. 

Amennyiben a zárthelyi és a pótzárthelyi segítségével sikerült megszerezni az aláírást, ez a második pótzárthelyi javításra is felhasználható, a feltételek ugyanazok, mint az első pótzárthelyi esetén. 

Katona Y. Gyula - Recski András - Szabó Csaba: A számítástudomány alapjai, TypoTeX Kiadó, 2003. 

Friedl Katalin - Recski András - Simonyi Gábor: Gráfelméleti feladatok, TypoTeX Kiadó, 2006. 

Fleiner Tamás: A számítástudomány alapjai, digitális jegyzet 

Az IMSc pontokat az alábbi képlettel számítjuk ki, ahol zh a zárthelyin, h a házi feladatokból, v pedig a szóbeli vizsgán elmondott felelettel szerzett pontszám. (zh és h maximuma 25, v maximuma 50.) 

IMSc_pont = max(0, h-15)+max(0,zh-20) + max(0,v-40). 

Az IMSc pontok megszerzése a programban nem résztvevő hallgatók számára is biztosított. Az aláírás és a vizsgajegy megszerzése mindenki számára egységes követelmények szerint történik, ezt az IMSc pontok nem befolyásolják.