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: 2016. június 13.

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

    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
    VISZAA02 1 2/2/0/v 4  
    3. A tantárgyfelelős személy és tanszék Dr. Katona Gyula,
    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. Fleiner Tamás

    Egy. docens

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

    Dr. Katona Gyula

    Egy. docens

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

    Dr. Recski András

    Egy. tanár

     

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

    Dr. Mann Zoltán

    Egy. docens

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

    Dr. Sali Attila

    Egy. docens

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

    6. Előtanulmányi rend
    Kötelező:
    (Training.Code=("5N-A7") VAGY Training.Code=("5N-A7H")) ÉS

    NEM ( TárgyEredmény( "BMEVISZA105", "jegy" , _ ) >= 2
    VAGY TárgyEredmény("BMEVISZA105", "FELVETEL", AktualisFelev()) > 0
    VAGY TárgyEredmény( "BMEVISZAA05", "jegy" , _ ) >= 2
    VAGY TárgyEredmény("BMEVISZAA05", "FELVETEL", AktualisFelev()) > 0
    VAGY TárgyEredmény( "BMEVISZAA05" , "aláírás" , _ ) = -1)

    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

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

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

    1.      Leszámlálási alapfogalmak, permutációk, variációk és kombinációk (ismétlés nélkül és ismétléssel), példákkal, kiszámításuk, binomiális együtthatók közti egyszerű összefüggések, a binomiális tétel

    2.      Gráfelméleti alapfogalmak. Gráfok fokszámösszege, fák egyszerűbb tulajdonságai. Minimális költségű feszítőfa, Kruskal algoritmus, helyességének bizonyítása, normál fák definíciója, megkeresésének módja.

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

    4.      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 feladat, megoldásnak algoritmusa.

    5.      Euler-séta és körséta, létezésének szükséges és elégséges feltétele (összefüggő gráf esetén). Hamilton-kör és út  fogalma. Szükséges, illetve elégséges feltételek Hamilton-kör létezésére: Dirac és Ore tételei ill. komponensszám pontelhagyások esetén.

    6.      Gráfok színezése, klikkméret és kromatikus szám viszonya. Páros gráf fogalma. Hálózati folyamok, Ford-Fulkerson tétel, algoritmus maximális folyam keresése, egészértékűségi lemma.

    7.      Többtermelős, többfogyasztós hálózatok, csúcskapacitások és irányítatlan élek visszavezetése szokásos hálózatra. Él- és pontidegen utak, minden st utat lefogó él- ill. ponthalmaz. Menger négy tétele, gráfok többszörös él- ill. pontösszefüggősége, kapcsolata a Menger tételekkel.

    8.      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. Síkbarajzolhatóság, gömbre rajzolhatóság.

    9.      Az Euler-féle poliédertétel és következményei egyszerű, síkbarajzolható gráfokra. Kuratowski gráfok, topologikus izomorfia, Kuratowski tétele. Síkbarajzolt gráf duálisa. Elvágó él, soros élek, vágás. A duális gráf tulajdonságai (élszám, csúcsszám, összefüggőség, kör-vágás dualitás, annak speciális esetei). Síkgráfok kromatikus száma, négyszíntétel.

    10.  Algoritmusok bonyolultsága (input mérete, algoritmus lépésszáma az inputméret függvényében, polinomidejű algoritmus), döntési problémák. P, NP, coNP bonyolultsági osztályok fogalma, feltételezett viszonyuk, példa ilyen problémákra.

    11.  Polinomiális visszavezethetőség (Karp-redukció), NP-teljesség, Cook-Levin tétel, nevezetes NP-teljes problémák: SAT, HAM, 3-SZÍN, k-SZÍN, MAXFTN, MAXKLIKK}, HAMÚT

    12.  Oszthatóság, maradékos osztás. Euklideszi algoritmus,  prímek, számelmélet alaptétele,  osztók száma. Tételek a prímek eloszlásáról.

    13.  Kongruenciák,  maradékrendszerek, Euler-Fermat-tétel, lineáris kongruenciák és diofantoszi egyenletek megoldása.

    14.  Számelméleti algoritmusok: alapműveletek, (modulo m) hatványozás és az euklideszi algoritmus lépésszáma. Prímtesztelés, Fermat-teszt. Nyilvános kulcsú titkosírás, digitális aláírás. Az RSA titkosítási módszer.

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

    2 óra előadás + 2 óra gyakorlat/ hét

    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évvégi aláírás megszerzésének (vagyis a vizsgára bocsátásnak) feltétele a zárthelyiken külön-külön legalább 30% -os teljesítmény és a két zárthelyi átlagában legalább 40%-os teljesítmény.

    Az érvényes TVSz-nek megfelelően a tárgyból korábban megszerzett aláírás 3 évig érvényes. (Részletesebben ez azt jelenti, hogy az aláírás megszerzését követő hatodik félév vizsgaidőszakjának végéig az aláírás még érvényes.) 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árthelyiket, hogy a korábbi zárthelyik eredményein 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ételeket, 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ételeket, 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 legalább egy zá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.

      

    A vizsgaidőszakban: Vizsgára az jelentkezhet, aki érvényes aláírással rendelkezik.

    A vizsga ebből a tárgyból szóbeli. A vizsga megkezdésekor a vizsgázó a tárgyhoz tartozó tételsorból egyetlen tételt kap, amelynek a kidolgozására (vagyis a szóbeli felelethez egy bő jegyzet készítésére) legalább 45 perc áll rendelkezésre. A felelet abból áll, hogy egyrészt a vizsgázó a jegyzeteire támaszkodva részletesen beszámol a húzott tételről, másrészt a vizsgáztató néhány szúrópróbaszerű, az anyag többi részével kapcsolatos kérdésére válaszol. (A vizsga sikerességéhez tehát nem elég a kihúzott tétel ismertetése, az imént említett további kérdésekre is kell tudni válaszolni.) 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 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). Ismétlő vizsga esetén a zárthelyikből származó eredmények változatlanul érvényesek.

    A tárgyhoz tartozó vizsgatételsor félévről félévre változik, az aktuális félévre érvényes vizsgatételsor a tárgy tanszéki weboldaláról tölthető le a szorgalmi időszak utolsó hetétől.

    Elővizsga: nem lehetséges

    11. Pótlási lehetőségek

    lásd a 10. pontot

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

    A zárthelyik és 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.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 óra56
    Félévközi készülés órákra14
    Felkészülés zárthelyire10
    Házi feladat elkészítése 
    Kijelölt írásos tananyag elsajátítása 
    Vizsgafelkészülés40
    Összesen120
    15. A tantárgy tematikáját kidolgozta

    Név:

    Beosztás:

    Tanszék, Int.:

    Dr. Fleiner Tamás

    egy. docens

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

    Dr. Katona Gyula

    egy. docens

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

    Dr. Recski András

    egy. tanár

    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  más feladatokat dolgozunk fel, mint a többi kurzuson. Kevesebb bevezető, rutin, gyakorló feladat szerepel és több nehezebb, gondolkodtatóbb feladat lesz.
    IMSc pontozás
    Mindkét zárthelyin és a szóbeli vizsgán is 60 pontot lehet elérni. Az IMSc pontokat az alábbi képlettel számítjuk ki, ahol zh1 és zh2 az első, illetve második zárthelyin, v pedig a szóbeli vizsgán szerzett pontszám.

    IMSc_pont = max(20, max(0,zh1-50) + max(0,zh2-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 10. pontban leírtaknak megfelelően történik, ezt az IMSc pontok nem befolyásolják. A vizsgán kapott végső jegyet meghatározó pontszámot az alábbi képlettel számítjuk ki.

    végső_pont = 0,4*(min(50,zh1) + min(50,zh2)) + 1,2*min(50,v).

    A végső jegy a végső pontszám alapján: 0-39: elégtelen, 40-54: elégséges, 55-69: közepes, 70-84: jó, 85-100: jeles.
    Egyéb megjegyzések NEM (TárgyTeljesítve("BMEVISZA105") )