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

A Bevezetés a számításelméletbe 1. tárgy anyaga.

A kötelező előtanulmányi rend az adott szak honlapján és képzési programjában található.

A műszaki informatika tanulmányokhoz szükséges és a mérnöki alapműveltséghez tartozó egyes alapvető matematikai ismeretek elsajátítása, azok szemléletmódjának kialakítása.

1)      Kombinatorikai alapismeretek: permutációk, variációk, kombinációk ismétlés nélkül és ismétléssel. Összefüggések a binomiális együtthatók között, Pascal-háromszög, binomiális tétel.

2)      Gráfelméleti alapfogalmak: gráf, egyszerű gráf, fokszám, élsorozat, út, kör, összefüggő gráf, összefüggő komponens, fa, feszítőfa. Az összefüggőség eldöntése, legrövidebb út keresése (élsúlyozatlan, irányítatlan gráfban): a szélességi bejárás (BFS).

3)      Minimális összsúlyú feszítőfa keresése: a Kruskal algoritmus. Síkbarajzolható gráf fogalma, ekvivalencia a gömbre rajzolhatósággal, Euler-féle poliédertétel.

4)      Reláció egyszerű síkgráf éleinek és csúcsainak a száma között. A K₅ és K_3,3 gráfok síkba nem rajzolhatósága, Kuratowski tétele. Síkgráf duálisa, megfelelések a csúcsok/élek/tartományok száma között, kör és vágás képe.

5)      Euler-út és Euler kör fogalma, ezek létezésének szükséges és elégséges feltétele. Hamilton-út és Hamilton-kör fogalma. Szükséges feltételek ezek létezésére: a k pont törlése után keletkező komponensek maximális száma. Elégséges feltételek: Dirac és Ore tételei.

6)      Páros gráf fogalma, azok karakterizációja páratlan körökkel. A kromatikus szám fogalma. Mohó színezés, felső becslés a kromatikus számra a maximális fokszám függvényében. Maximális klikkméret fogalma, reláció a kromatikus számmal, Mycielski-konstrukció.

7)      Intervallumgráfok optimális színezése. Párosítás, lefogó ponthalmaz, független ponthalmaz, lefogó élhalmaz fogalmai. Reláció a maximális párosítás és a minimális lefogó ponthalmaz mérete között. Gallai tételei.

8)      Maximális párosítás keresése páros gráfokban, a javító utas algoritmus, annak optimalitása. Kőnig tétele a maximális párosítás és a minimális lefogó ponthalmaz méretének egyenlőségéről. Tutte tétele.

9)      Élkromatikus szám fogalma, reláció a maximális fokszámmal, Vizing tétele, Kőnig tétele páros gráfok optimális élszínezéséről. A maximális folyam feladata: hálózat, folyam és folyam értékének fogalma, a javító utas algoritmus maximális folyam keresésére.

10)  Hálózat st-vágásának fogalma, annak kapacitása. Ford-Fulkerson tétel, Edmonds-Karp tétel. Egészértékűségi lemma. Az éldiszjunkt, irányított s-t utak problémája, Menger vonatkozó tétele.

11)  Az éldiszjunkt, irányítatlan s-t utak problémája, a pontdiszjunkt s-t utak problémája irányított és irányítatlan esetben is, Menger vonatkozó tételei. Többszörös pont- és élösszefüggőség fogalmai, Menger vonatkozó tételei.

12)  A legrövidebb út keresésének problémája pozitív élsúlyokkal irányított és irányítatlan gráfban, illetve valós élsúlyokkal irányított gráfban, Dijkstra, Ford és Floyd algoritmusai.

13)  Mélységi bejárás (DFS) irányítatlan és irányított gráfban, az irányított körök felismerése. Aciklikus irányított gráfok, topologikus rendezés. Legrövidebb és leghosszab út keresése aciklikus irányított gráfban.

14)  Ismétlés, összefoglalás, a tanult anyagrészek rendszerezett áttekintése. A szóbeli vizsgára vonatkozó aktuális vizsgatételsor és az egyes vizsgatételekkel kapcsolatos részletes elvárások ismertetése.

Heti 2 óra előadás és heti 2 órás kiscsoportos gyakorlat.

A szorgalmi időszakban: A félév folyamán két 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árthelyiken külön-külön legalább 30% -os teljesítmény és a két zárthelyi átlagában legalább 40%-os teljesítmény.

Az érvényes TVSz-nek megfelelően a tárgyból korábban megszerzett aláírás 3 évig érvényes. (Részletesebben ez azt jelenti, hogy az aláírás megszerzését követő hatodik félév vizsgaidőszakának végéig az aláírás még érvényes.) Azok a hallgatók, akik egy korábbi félévből érvényes aláírással rendelkeznek, megkísérelhetik újból megírni a zárthelyiket, hogy a korábbi zárthelyik eredményein javítsanak. Erre az esetre az alábbi feltételek vonatkoznak:

• Ha sikerül újra teljesíteni az aláíráshoz szükséges feltételeket, akkor a vizsgajegybe (lásd lentebb) az így kapott eredmény számít bele (akkor is, ha ez rosszabb).

• Ha nem sikerül újra teljesíteni az aláíráshoz szükséges feltételeket, akkor az aláírás nem vész el, de a vizsgajegybe csak az aláírás megszerzéséhez szükséges minimális pontszámot számítjuk be.

Ha egy érvényes aláírással rendelkező hallgató az aktuális félévben legalább egy zárthelyin megjelenik, azt úgy tekintjük, hogy az illető kísérletet tett az aláírás feltételeinek újbóli teljesítésére (és rá a fenti feltételek vonatkoznak). Ellenkező esetben a legutolsó olyan félévbeli teljesítményt vesszük figyelembe, amikor a hallgató megkísérelte az aláírás feltételeinek teljesítését.

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 megszerzésének feltétele, hogy a vizsgázó az anyagban szereplő minden definíciót és tételt ki tudjon mondani, illetve tudjon értelmezni.

A vizsgajegyet a két zárthelyi eredményéből és a vizsgán nyújtott szóbeli teljesítményből alakítjuk ki olyan módon, hogy abba a zárthelyik átlaga 40 százalék erejéig, a szóbeli vizsga 60 százalék erejéig számít bele. 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 származó eredmények változatlanul érvényesek.

A tárgyhoz tartozó vizsgatételsor félévről félévre változik, az aktuális félévre érvényes vizsgatételsor a tárgy tanszéki weboldaláról tölthető le a szorgalmi időszak utolsó hetétől.

Elővizsga: nem lehetséges

A két zárthelyin kívül a szorgalmi időszakban pótzárthelyi írható, melyen bármelyik (de nem mindkettő) zárthelyi eredménye javítható vagy a hiányzás pótolható. 

A pótzárthelyin 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 a hallgató az aláírás feltételeit már teljesítette, de a javítónak szánt zárthelyi új pontszámával a feltételek valamelyikét nem teljesíti , akkor a hallgató az aláírást megkapja, de a zárthelyikből származó pontszáma az elégségeshez szükséges minimális pontszám lesz.)

Amennyiben a zárthelyik és a pótzárthelyi segítségével sem sikerül a feltételeket teljesíteni, a vizsgaidőszak előtti "pótlási héten" lehetőség nyílik az egyik (szabadon választott) zárthelyinek az újbóli pótlására, illetve javítására a feltételek teljesítése érdekében. Ennek a második pótzárthelyi alkalomnak a neve “aláíráspótló vizsga” (de ez természetesen nem helyettesíti a szóbeli vizsgát).

A vizsgák előtt konzultációs lehetőséget biztosítunk.

Bevezetés a számításelméletbe – digitális jegyzet, a tárgy tanszéki weboldaláról letölthető

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.