Bevezetés a számításelméletbe II.

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

Adatlap utolsó módosítása: 2006. július 1.

Tantárgy lejárati dátuma: 2015. január 31.

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

Műszaki Informatika Szak

Tantárgykód Szemeszter Követelmények Kredit Tantárgyfélév
VIMA1236 1 2/2/0/v 5 1/2
3. A tantárgyfelelős személy és tanszék Dr. Csákány Rita,
4. A tantárgy előadója

Név:

Beosztás:

Tanszék, Int.:

Dr. Sali Attila

egyetemi docens

Számítástudományi és Információelméleti Tanszék

Dr. Simonyi 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

Bevezetés a számításelméletbe I. című tárgy anyaga.

6. Előtanulmányi rend
Kötelező:
TárgyEredmény( "BMEVIMA1235" , "aláírás" , _ ) >0 VAGY TárgyEredmény( "BMEVIMA1205" , "aláírás" , _ ) >0 VAGY TárgyEredmény( "BMEVIMA1601" , "aláírás" , _ ) >0 VAGY TárgyEredmény( "BMEVIMA1602" , "aláírás" , _ ) >0

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ó.

Ajánlott:

Bevezetés a számításelméletbe I. tárgyból aláírás megszerzése.

7. A tantárgy célkitűzése

Az informatikusmérnöki tanulmányokhoz szükséges legfontosabb diszkrét matematikai ismeretek elsajátítása, szemléletmódjának kialakítása.

8. A tantárgy részletes tematikája

Gráfok pont- és élszínezése, Mycielsky konstrukciója, perfekt gráfok. Négy- és ötszíntétel. Euler- és Hamilton-tételkör. Szélességi és mélységi keresés, legrövidebb út kereső algoritmusok. Párosítások, Hall és Tutte tételei. Gallai tételei. Hálózati folyamok. Menger-tételkör, magasabb összefüggőség. A mélységi keresés alkalmazásai, topológiai rendezés, PERT-módszer. Számelmélet (oszthatóság, a számelmélet alaptétele, euklideszi algoritmus, kongruencia, maradékosztályok, Euler-Fermat tétel, lineáris kongruenciák megoldása, prímtesztelés, nyilvános kulcsú titkosírások) Absztrakt algebra (félcsoport, csoport, rend, nevezetes csoportok, részcsoport, normálosztó, faktorcsoport, gyűrű, test, nevezetes példák pl. kvaterniók, testbővítések)

9. A tantárgy oktatásának módja (előadás, gyakorlat, laboratórium)

(előadás, gyakorlat, laboratórium):

Előadás és gyakorlat.

10. Követelmények

a. A szorgalmi időszakban:

A félév folyamán két zárthelyit iratunk.

A félévvégi aláírás megszerzésének (vagyis a vizsgára bocsátásnak) feltétele, hogy mindkét zárthelyinek külön-külön legalább elégségesre kell sikerülnie. A két zárthelyihez van egy-egy pótlási lehetőség a félév utolsó hetében: ilyenkor az elégtelen(-ek) kijavítható(-ak), illetve az esetleges hiányzás(-ok) pótolható(-ak). A pótzárthelyin gyenge, de nem elégtelen 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 rosszabb, mint az eredeti. (Ez alól egy kivétel van: a már megszerzett aláírás egy javítónak szánt, de elégtelenre megírt pótzárthelyivel nem vész el, viszont leviszi a zárthelyikből származó pontszámot az elégségeshez szükséges minimális pontszám szintjére.)

Amennyiben a pótlás sem sikerül, már csak ismétlő vizsga (gyakIV) jelleggel lehet megszerezni az aláírást, és így a vizsgázás jogát. Ennek módja, hogy a vizsgaidőszakban egy újabb zárthelyit kell legalább elégségesre megírni. (Ez a zárthelyi a félév teljes anyagához kapcsolódó feladatokat tartalmazhat függetlenül attól, hogy a szorgalmi időszakban melyik zárthelyi nem sikerült.) A vizsgaidőszakban két gyakIV alkalmat hirdetünk meg (ezek közül az egyiket várhatóan az első héten), de a két alkalom közül mindenki csak az egyiken próbálkozhat. Így ha valaki az első alkalommal megpróbált aláírást szerezni, de ez nem sikerült, annak sajnos a második alkalommal már nem lesz lehetősége erre. A gyakIV-kre a Neptunban jelentkezni kell.

Ha a gyakIV jelleggel megírt zárthelyi eléri a legalább elégséges szintet, akkor egy későbbi vizsgaalkalommal lehet vizsgázni. Ha valaki az aláírást gyakIV-vel szerzi meg, akkor ezt a vizsgán úgy számítjuk be, mintha mindkét zárthelyin az elégségeshez szükséges minimális pontszámot érte volna el. Ha a gyakIV sem sikerül, akkor a félév sajnos sikertelen.

b. A vizsgaidőszakban:

A tárgyból szóbeli vizsga van.

A vizsga úgy zajlik, hogy a tételsoron szereplő tételek közül a vizsgázó egyet kap, ezt kidolgozza, majd szóban felel belőle. Számítani kell arra is, hogy a vizsgáztató néhány definíció, vagy tétel kimondása erejéig a többi tételbe is belekérdez. A vizsgán az elégséges megszerzésének feltétele, hogy a vizsgázó az anyagban szereplő minden definíciót, illetve tételt ki tudjon mondani, illetve tudjon értelmezni. A vizsgatétel kidolgozására a hallgatónak felkészülési idő áll rendelkezésére. Negyvenöt perc felkészülési idő letelte után a vizsgáztató abban az esetben is elkezdheti a vizsgáztatást, ha a hallgató még nem jelezte, hogy elkészült.

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).

Aki elégtelenre vizsgázik, egy ízben ismétlő vizsgát tehet. Ez a pótlási lehetőség szükség esetén az olyan hallgatót is megilleti, aki az aláírást gyakIV-vel szerezte meg. Ismétlő vizsga esetén a zárthelyikből származó eredmények változatlanul érvényesek.

  1. Elővizsga: nincs rá lehetőség.
11. Pótlási lehetőségek

lásd a 10. pontot.

12. Konzultációs lehetőségek

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

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

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

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

(a tantárgyhoz tartozó tanulmányi idő körülbelüli felosztása a tanórák, továbbá a házi feladatok és a zárthelyik között (a felkészülésre, ill. a kidolgozásra átlagosan fordítandó/elvárható idők félévi munkaórában, kredit x 30 óra, pl. 5 kredit esetén 150 óra)):

Kontakt óra

60

Félévközi készülés órákra

15

Felkészülés zárthelyire

10

Házi feladat elkészítése

15

Kijelölt írásos tananyag elsajátítása

0

..

Vizsgafelkészülés

50

Összesen

150

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

Név:

Beosztás:

Tanszék, Int.:

Dr. Recski András

egyetemi tanár, tanszékvezető

Számítástudományi és Információelméleti Tanszék