BME VIK - Bevezetés a számításelméletbe 2

vissza a tantárgylistához nyomtatható verzió

Bevezetés a számításelméletbe 2

A tantárgy angol neve: Introduction to the Theory of Computing 2

Adatlap utolsó módosítása: 2022. október 12.

Budapesti Műszaki és Gazdaságtudományi Egyetem
Villamosmérnöki és Informatikai Kar

Mérnök informatikus szak, BSc képzés

Tantárgykód	Szemeszter	Követelmények	Kredit	Tantárgyfélév
VISZAA04	2	2/2/0/v	5

3. A tantárgyfelelős személy és tanszék dr. Wiener Gábor,

A tantárgy tanszéki weboldala http://cs.bme.hu/bsz2

4. A tantárgy előadója

Név:	Beosztás:	Tanszék, Int.:
Dr. Csákány Rita	egyetemi docens	Számítástudományi és Információelméleti Tanszék
Dr. Fleiner Tamás	egyetemi tanár	Számítástudományi és Információelméleti Tanszék
Dr. Pach Péter Pál	egyetemi docens	Számítástudományi és Információelméleti Tanszék
Dr. Recski András	egyetemi tanár	Számítástudományi és Információelméleti Tanszék
Dr. Szeszlér Dávid	egyetemi docens	Számítástudományi és Információelméleti Tanszék
Dr. Wiener Gábor	egyetemi docens	Számítástudományi és Információelméleti Tanszék

5. A tantárgy az alábbi témakörök ismeretére épít Középiskolai matematikai ismeretek.

6. Előtanulmányi rend

Kötelező:

((TárgyEredmény( "BMEVISZAA00" , "aláírás" , _ ) = -1
VAGY
TárgyEredmény( "BMEVISZAA03" , "aláírás" , _ ) = -1
VAGY
TárgyEredmény( "BMEVISZA103" , "aláírás" , _ ) = -1
VAGY
TárgyEredmény( "BMEVISZAA06" , "aláírás" , _ ) = -1 )

ÉS NEM

(TargyEredmeny("BMEVISZA110", "jegy", _) >= 2
VAGY
TárgyEredmény("BMEVISZA110", "felvétel", AktualisFelev()) > 0
VAGY
TargyEredmeny("BMEVISZAA01", "jegy", _) >= 2
VAGY
TárgyEredmény("BMEVISZAA01", "felvétel", AktualisFelev()) > 0
VAGY
TárgyEredmény( "BMEVISZAA01" , "aláírás" , _ ) = -1) )

VAGY

(EgyenCsoportTagja("INFO - 2022 - MINTATANTERV HALLGATÓI") VAGY
EgyenCsoportTagja("INFO - 2022ENG - MINTATANTERV HALLGATÓI") )

ÉS (Training.Code=("5N-A8") VAGY Training.Code=("5NAA8"))
VAGY EgyenCsoportTagja("Kreditpótlás_2023/24/2")

A fenti forma a Neptun sajátja, ezen technikai okokból nem változtattunk.

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

7. A tantárgy célkitűzése Az informatikai 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. Ezen belül a tantárgy a gráfelmélet egyes területeire nyújt bevezetést és alapvető gráfelméleti algoritmusokat ismertet.
A tantárgyat sikeresen teljesítő hallgató képes lesz:
- (K3) érteni és alkalmazni a tárgyban előkerülő fogalmakat és ismereteket;
- (K3) önállóan megoldani az anyaghoz kapcsolódó gyakorlati feladatokat;
- (K2) alkalmazni a tárgyban szereplő algoritmusokat;
- (K2) egyes, az anyagba tartozó tételek bizonyítására, az anyagban szereplő algoritmusok helyességének igazolására;
- (K4) a későbbi tanulmányok során felismerni azokat a helyzeteket, ahol a tárgyban tanult ismeretek szerephez jutnak és sikerrel alkalmazni a tanultakat.

8. A tantárgy részletes tematikája 1) Gráfelméleti alapfogalmak: gráf, egyszerű gráf, fokszám, részgráf, feszített részgráf, komplementer, élsorozat, séta, körséta, út, kör, izomorfia.
2) Összefüggő gráf, összefüggő komponens. Fa és feszítőfa fogalma, feszítőfa létezése.
3) Gráfok tárolása: szomszédsági mátrix és szomszédsági lista. Irányított gráfok. Gráfelméleti algoritmusok hatékonysága. Az összefüggőség eldöntése, legrövidebb út keresése élsúlyozatlan gráfban: a szélességi bejárás (BFS).
4) Minimális összsúlyú feszítőfa keresése: a Kruskal algoritmus.
5) Euler-séta és -körséta 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áfok, karakterizációjuk 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, kapcsolata a kromatikus számmal, Zykov konstrukciója.
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.
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.
10) 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.Hálózat st-vágásának fogalma, annak kapacitása.
11) 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.
12) 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 fogalma, Menger vonatkozó tételei.
13) A legrövidebb utak keresésének problémája valós élsúlyokkal irányított gráfban, a Bellman-Ford algoritmus.
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.

9. A tantárgy oktatásának módja (előadás, gyakorlat, laboratórium) Heti 2 óra előadást heti 2 óra gyakorlat követ.
Az előadásokon az új elméleti anyag 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 szorosan épülnek a korábbi hetek anyagára, ezek ismerete nélkül az új anyag általában nem követhető.

10. Követelmények

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) a feltétele a zárthelyin megszerezhető 60 pontból legalább 24 pont elérése.
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árthelyit, hogy a korábbi eredményükön 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ételt, 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ételt, 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 a zárthelyin vagy a pótzá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.

Vizsgára az jelentkezhet, aki érvényes aláírással rendelkezik.
A vizsga szóbeli.
A vizsgajegyet a zárthelyi eredményéből és a vizsgán nyújtott teljesítményből alakítjuk ki olyan módon, hogy abba a zárthelyi eredménye 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árthelyi eredményétől). Ismétlő vizsga esetén a zárthelyiből származó eredmények változatlanul érvényesek. Részletesebben: a vizsgán kapott végső jegyet meghatározó pontszámot az alábbi képlettel számítjuk ki, ahol zh a zárthelyi pontszáma, v pedig a szóbeli vizsgán a felelettel szerzett pontszám (amelyeknek az értéke maximálisan 60).
végső_pont = 0,8min(50,zh) + 1,2min(50,v).
A végső jegy a végső pontszám alapján: 0-39,9: elégtelen, 40-54,9: elégséges, 55-69,9: közepes, 70-84,9: jó, 85-100: jeles.

Elővizsga nem lehetséges.

11. Pótlási lehetőségek A zárthelyi dolgozat pótlására egy pótzárthelyi alkalom (amelyen a zárthelyi eredménye javítható is), illetve egy díjköteles pótlás áll rendelkezésre.
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 24 pontos 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 24 pont alatti teljesítményt ér el, akkor a hallgató az aláírást megkapja, de a zárthelyiből származó pontszáma a 24 pontos eredménynek megfelelő, minimális pontszám lesz.

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

13. Jegyzet, tankönyv, felhasználható irodalom

A tárgy honlapján kifejezetten a tárgyhoz készült online jegyzet áll rendelkezésre: http://cs.bme.hu/bsz2/jegyzet/. A zárthelyikre való felkészülést az elmúlt több, mint 10 év zárthelyi példasorai és az azokhoz készült pontozási útmutatók segítik, melyek szintén a honlapról érhetők el.

14. A tantárgy elvégzéséhez átlagosan szükséges tanulmányi munka

Kontakt óra	56
Félévközi készülés előadásokra	8
Félévközi készülés gyakorlatokra	21
Felkészülés zárthelyire	15
Vizsgafelkészülés	50
Összesen	150

15. A tantárgy tematikáját kidolgozta

Név:	Beosztás:	Tanszék, Int.:
Dr. Wiener Gábor	egyetemi docens	Számítástudományi és Információelméleti Tanszék

IMSc tematika és módszer A plusz pontokat a hatékonyabb tanulásért és az anyag magasabb szintű, mélyebb elsajátításáért kapják a hallgatók. A gyakorlatokon részben más feladatokat dolgozunk fel, mint a többi kurzuson: kevesebb a bevezető és gyakorló jellegű, több a nehezebb, gondolkodtató feladat.

IMSc pontozás Az IMSc pontokat az alábbi képlettel számítjuk ki, ahol zh a zárthelyin, v pedig a szóbeli vizsgán elmondott felelettel szerzett pontszám. (Mindkettőnek az értéke maximálisan 60.)

IMSc_pont = min(25, 2max(0,zh-50) + max(0,v-50)).

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, a korábban leírtaknak megfelelően történik, ezt az IMSc pontok nem befolyásolják.

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

Bevezetés a számításelméletbe 2