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: Foundation of Computer Science

    Adatlap utolsó módosítása: 2012. június 18.

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

    Villamosmérnöki szak

    BSc képzés

    Tantárgykód Szemeszter Követelmények Kredit Tantárgyfélév
    VISZA105   4/2/0/v 6  
    3. A tantárgyfelelős személy és tanszék Dr. Katona Gyula, Számítástudományi és Információelméleti Tanszék
    A tantárgy tanszéki weboldala www.cs.bme.hu/sza
    4. A tantárgy előadója

    Név:

    Beosztás:

    Tanszék, Int.:

    Dr. Katona Gyula

    egyetemi docens

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

    Dr. Fleiner Tamás

    egyetemi docens

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

    Dr.Sali Attila

    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. Mann Zoltán

    egyetemi docens

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

    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

    1. hét

    leszámlálási alapfeladatok, permutáció, kombináció, variáció, binomiális tétel

     

    összetett leszámlálási feladatok, skatulya-elv, szita-formula

    2. hét

    alapvető adatstruktúrák: tömb, láncolt lista, bináris fa, kupac

     

    keresés lineárisan és binárisan, lépésszámok elemzése, minimum keresés, beszúrási feladat

    3. hét

    rendezési feladat, buborék-, kiválasztásos-, összefésüléses-, gyorsrendezés

     

    kupacos rendezés, rendezés bináris keresőfával, alsó korlát, ládarendezés

    4. hét

    gráfelméleti alapfogalmak, gráfok adatstruktúrái, szomszédossági mátrix, éllista, szomszédossági lista

     

    fák, alaptulajdonságaik, Prüfer-kód, minimális súlyú feszítőfa, Kruskal-algoritmus, normál-fák

    5. hét

    Euler- és Hamilton-körök, szükséges ill. elégséges feltételek létezésükre, legrövidebb utak keresése, BFS

     

    Dijkstra, Ford, Floyd algoritmusok, legszélesebb út keresése irányított és irányítatlan gráfban, legszélesebb legrövidebb és legrövidebb legszélesebb út

    6. hét

    hálózati folyamok, Ford-Fulkerson tétel, algoritmus maximális folyam keresésére

     

    folyamproblémák általánosításai, él- ill. pontidegen utak maximális száma, Menger tételei, többszörös összefüggőség

    7. hét

    páros gráfok, párosítások, Hall-tétel, algoritmus maximális párosítás keresésére páros gráfban

     

    független/lefogó pont-/élhalmazok, Kőnig és Gallai tételei, párosítás tetszőleges gráfban, Tutte-tétel

    8. hét

    gráfok színezése, klikkszám és kromatikus szám viszonya, Mycielski konstrukció, Brooks tétel, élszínezés, Vizing tétel

     

    síkbarajzolható gráfok, Euler-formula, Kuratowski tétel, dualitás

    9. hét

    gyenge izomorfia, Whitney tételei, síkgráfok színezése, 5- és 4-szín tétel

     

    mélységi keresés, irányított körök keresése, alapkörrendszer (=fundamentális körrendszer), fundamentális vágásrendszer, PERT

    10. hét

    algoritmusok bonyolultsága, P, NP, coNP osztályok


    NP-teljes problémák, módszerek nehéz problémák kezelésére

    11. hét

    oszthatóság, Euklideszi algoritmus, prímek, számelmélet alaptétele, osztók száma

     

    tételek a prímek eloszlásáról, maradékrendszerek, Euler-Fermat-tétel

    12. hét

    lineáris kongruenciák és diofantoszi egyenletek megoldása, Wilson-tétel

     

    absztrakt algebra: művelet, félcsoport, csoport, példák csoportokra

    13. hét

    izomorfia, részcsoport, ciklikus csoport, mellékosztály

     

    Lagrange tétel, gyűrűk, polinomgyűrűk, testek, véges testek, kvaterniók, hányadostest

    14. hét

    kriptográfiai módszerek, nyilvános kulcsú titkosítás, RSA kódolás

    9. A tantárgy oktatásának módja (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
    Az előadások és a gyakorlatok látogatása kötelező. Az előadásokon a jelenlétet azok kezdetén és végén is a félév folyamán minden alkalommal ellenőrizzük, aláírást nem kaphat az a hallgató, aki ezek alapján az alkalmak több, mint 30%-áról hiányzott (a viszonyítási alap a ténylegesen megtartott előadások száma). A gyakorlatokon a jelenlétet minden alkalommal ellenőrizzük, 30%-ot meghaladó hiányzás esetén a tantárgyból sem aláírás sem kreditpont nem szerezhető.

    A szorgalmi időszakban:
     
     A félév folyamán két zárthelyit íratunk. A félév vé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 zárthelyihez van egy pótlási lehetőség: ilyenkor az egyik elégtelen kijavítható, illetve az esetleges hiányzás pótolható. 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 a sikertelen 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. 

    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.Friedl Katalin – Recski András – Simonyi Gárbor: Gráfelméleti feladatok, TypoTEX Kiadó 2006.
    14. A tantárgy elvégzéséhez átlagosan szükséges tanulmányi munka
    Kontakt óra84
    Félévközi készülés órákra28
    Felkészülés zárthelyire12
    Házi feladat elkészítése
    Kijelölt írásos tananyag elsajátítása
    Vizsgafelkészülés56
    Összesen180
    15. A tantárgy tematikáját kidolgozta
    Dr. Recski Andrásegyetemi tanár 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