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

    Belépés
    címtáras azonosítással

    vissza a tantárgylistához   nyomtatható verzió    

    A számítástudomány alapjai

    A tantárgy angol neve: Elements of the Theory of Computing

    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
    VIMA2025 1 4/2/0/v 8 03.01.01
    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. Csákány Rita

    egyetemi adjunktus

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

    Dr. Katona Gyula

    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

    1. és 2. féléves matematika.

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

    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:


    Matematika II, kredit

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

    A villamosmérnöki tanulmányokhoz szükséges legfontosabb matematikai ismeretek elsajátítása, az algebra és diszkrét matematika szemléletmódjának kialakítása.

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

    A) Kombinatorikai alapfogalmak, leszámolások.

    B) Fejezetek a gráfelméletből

    1) Gráfelméleti alapfogalmak, út, kör, fa, irányított gráfok

    2) Síkbarajzolhatóság, dualitás, gyenge izomorfia

    3) Gráfok mátrixreprezentációi

    4) Párosítások, Kőnig tétel, magyar módszer, hálózati folyamok, Menger tételei

    5) Gráfelméleti algoritmusok. Legrövidebb út, párosítás, folyam, fakeresés, alapkör rendszer generálása, kritikus út módszere.

    C) Rendezési algoritmusok, adatstrukturák, számelméleti algoritmusok, a kriptográfia alapelemei.

    D) Algoritmusok komplexitása. P,NP,NP-teljes problémák.

    E) Az absztrakt algebra elemei. Csoportok, gyűrük, testek.

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

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

    Heti 4 óra előadás az egész évfolyamnak, és heti 2 óra kiscsoportos 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

    84

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

    42

    Felkészülés zárthelyire

    12

    Házi feladat elkészítése

    14

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

    Vizsgafelkészülés

    56

    Összesen

    208

    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