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: 2008. január 31.

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

Műszaki Informatika Szak

2.

Tantárgy kódjaSzemeszterKövetelményKreditNyelvTárgyfélév
 visza11012+2+0v4magyar1/2
Tantárgykód Szemeszter Követelmények Kredit Tantárgyfélév
VISZA110   2/2/0/v 4  
3. A tantárgyfelelős személy és tanszék Dr. Szeszlér Dávid, Számítástudományi és Információelméleti Tanszék
A tantárgy tanszéki weboldala www.cs.bme.hu/bsz2
4. A tantárgy előadója
Név:Beosztás:Tanszék, Int.:
Dr. Fleiner Tamásegyetemi docensSzámítástudományi és Információelméleti Tanszék
Dr. Recski Andrásegyetemi tanárSzámítástudományi és Információelméleti Tanszék
Dr. Simonyi Gáboregyetemi docensSzámítástudományi és Információelméleti Tanszék
Dr. Szeszlér Dávidegyetemi adjunktusSzá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( "BMEVISZA103" , "aláírás" , _ ) = -1
VAGY
TárgyEredmény( "BMEVIMA1235" , "aláírás" , _ ) = -1
VAGY
TárgyEredmény( "BMEVIMA1602" , "aláírás" , _ ) = -1 )

ÉS
(NEM ( TárgyEredmény( "BMEVISZAA01" , "jegy" , _ ) >= 2 )
VAGY
NEM (TargyEredmeny("BMEVISZAA01", "FELVETEL", AktualisFelev()) > 0))

ÉS Training.Code=("5N-A8")

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

A kötelező előtanulmányi rendek grafikus formában itt láthatók.

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 mérnökinformatikus 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

A) Fejezetek a gráfelméletből

            1) Gráfok pont- és élszínezése, Mycielsky konstrukciója, perfekt gráfok. Négy- és ötszíntétel.

            2) Euler- és Hamilton-tételkör.

            3) Párosítások, König, Hall és Tutte tételei. Gallai tételei.

            4) Hálózati folyamok. Menger-tételkör, magasabb összefüggőség.

            5) Aciklikus irányított gráfok, PERT-módszer.

            6) Gráfok mátrixai.

B) A számelmélet alapjai

            1) Oszthatóság, felbonthatatlan- és prímszámok, a számelmélet alaptétele, euklideszi algoritmus.

            2) Kongruencia, maradékosztályok, Euler-Fermat tétel.

            3) Lineáris kongruenciák megoldása.

            4) Prímtesztelés, nyilvános kulcsú titkosírás.

C) Az absztrakt algebra elemei

            1) Félcsoport, csoport fogalma.

            2) Nevezetes csoportok: ciklikus csoport, szimmetrikus csoport, diédercsoport.

            3) Csoportokkal kapcsolatos alapfogalmak: izomorfia, elem rendje, részcsoport, mellékosztály.

            4) Gyűrű és test fogalma, nevezetes példák.

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

 

Heti 2 óra előadás az egész évfolyamnak és heti 2 órás kiscsoportos gyakorlat..

10. Követelmények

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, 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: 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 az adott zárthelyit úgy tekintjük, mintha azon a hallgató  az elégségeshez szükséges minimális pontszámot érte volna el.)  Amennyiben a szorgalmi időszakban nem sikerült mindkét zárthelyin (vagy a megfelelő pótzárthelyin) legalább elégségest szerezni, akkor a pótlási héten az egyik zárthelyi pótlására még egy lehetőség van. (Ha egyik zárthelyi sem volt sikeres, akkor a pótlási időszakban már nem lehet aláírást szerezni.)

 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 és 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).  Javító (ismétlő) vizsga  a TVSz szerint tehető.   Javító vizsga esetén a zárthelyikből származó eredmények változatlanul érvényesek.  

Az aláírás a TVSz szerint 3 évig érvényes.

Amennyiben a hallgatónak már van aláírása korábbi félévből, akkor lehetősége van megkísérelni újból megszerezni az aláírást a zárthelyik újbóli megírásával.

        Ha sikerült újra teljesíteni a feltételeket, akkor a vizsgajegybe ezek az eredmények számítanak bele (akkor is ha ezek összességében gyengébbek).         Ha megkísérelte, de nem sikerült megszerezni az aláírást, 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ámmal számítjuk be.         Ha nem kísérelte meg (nem vett részt egyetlen zárthelyin vagy pótláson sem az adott félévben), akkor a legutolsó olyan félévbeli teljesítményét vesszük figyelembe,  amikor a hallgató megkísérelt aláírást szerezni.   Elővizsga: lehetséges a vizsgaidőszak előtti (pótlások céljára fenntartott) héten
11. Pótlási lehetőségek lásd a 10. pontot
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

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
Kontakt óra56
Félévközi készülés órákra8
Felkészülés zárthelyire6
Házi feladat elkészítése8
Kijelölt írásos tananyag elsajátítása0
Vizsgafelkészülés42
Összesen120

 

(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)):

15. A tantárgy tematikáját kidolgozta
Név:Beosztás:Tanszék, Int.:
Dr. Recski Andrásegyetemi tanár, tanszékvezetőSzámítástudományi és Információelméleti Tanszék