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: 2022. június 10.

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

    Villamosmérnök Bsc

    kötelező közös tárgy

    Tantárgykód Szemeszter Követelmények Kredit Tantárgyfélév
    VISZAA07 1 3/2/0/v 5  
    3. A tantárgyfelelős személy és tanszék Dr. Fleiner Tamás,
    A tantárgy tanszéki weboldala www.cs.bme.hu/sza
    4. A tantárgy előadója

    Fleiner Tamás, egyetemi tanár, SzIT

    Katona Gyula, egyetemi docens, SzIT

    Kaszanitzky Viktória, egyetemi adjunktus, SzIT

    Recski András, egyetemi tanár, SzIT

    Sali Attila, egyetemi docens, SzIT

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

    A tantárgy célkitűzése a villamosmérnöki tanulmányokhoz szükséges és a mérnöki alapműveltséghez tartozó egyes alapvető matematikai ismeretek elsajátítása, azok szemléletmódjának kialakítása. Ezen belül a tantárgy a lineáris algebra és a gráfelmélet egyes területeire nyújt bevezetést.

    A tantárgyat sikeresen teljesítő hallgató képes lesz:

    ·      érteni és alkalmazni a tárgyban előkerülő fogalmakat és ismereteket;

    ·      önállóan megoldani az anyaghoz kapcsolódó gyakorlati feladatokat;

    ·      alkalmazni a tárgyban szereplő algoritmusokat;

    a későbbi tanulmányok során felismerni azokat a helyzeteket, ahol a tárgyban tanult ismeretek szerephez jutnak és sikerrel alkalmazni a tanultakat.

    8. A tantárgy részletes tematikája
    1. Gráfelméleti alapfogalmak. Gráfok fokszámösszege, komponensek, utak, séták, élsorozatok, izomorfia. Fák és erdők, azok egyszerűbb tulajdonságai.
    2. Feszítőfa, alapkörrendszer (fundamentális körrendszer), fundamentális vágásrendszer. Minimális költségű feszítőfa, Kruskal algoritmusa.
    3. Gráfbejárás fogalma, élek osztályozása, BFS. Legrövidebb utak és a BFS tulajdonságai, legrövidebb utak fája. Élmenti javítás, Dijkstra algoritmusa.
    4. Ford és Floyd algoritmusai. Mélységi keresés, irányított körök keresése, aciklikus gráfok jellemzése. 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áf síkba, illetve gömbre rajzolhatósága. Az Euler-féle poliédertétel és következményei egyszerű, síkbarajzolható gráfokra. Kuratowski gráfok, soros bővítés, 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.
    7. Lineáris egyenletrendszerek megoldása Gauss-eliminációval. Elemi sorekvivalens lépés, lépcsős alak és redukált lépcsős alak fogalma. Kapcsolat az
      egyenletek és ismeretlenek száma, illetve a megoldás egyértelműsége között.
    8. Rn és Rn alterének fogalma. Lineáris kombináció, generált altér (és ennek altér volta), generátorrendszer. Lineáris függetlenség (ennek kétféle definíciója és ezek ekvivalenciája). Az újonnan érkező vektor lemmája. F-G egyenlőtlenség.
    9. Bázis és dimenzió fogalma, a dimenzió egyértelműsége. Standard bázis, Rn dimenziója. Koordinátavektor fogalma és annak egyértelműsége. Bázis létezése Rn tetszőleges alterében.
    10. Determináns definíciója. Permutációk inverziószáma. A determináns alaptulajdonságai. Determináns kiszámítása Gauss-eliminációval. A kifejtési tétel.
    11. Műveletek mátrixokkal (összeadás, skalárral szorzás, szorzás, transzponálás), ezek tulajdonságai. A transzponált determinánsa. Determinánsok szorzástétele (biz. nélkül). Lineáris leképezések.
    12. Mátrix inverze, létezésének szükséges és elégséges feltétele, az inverz kiszámítása. Mátrix rangja, a rangfogalmak egyenlősége, a rang meghatározása. Az n × n-es lineáris egyenletrendszerek egyértelmű megoldhatóságának jellemzése a determináns segítségével. Kapcsolat a lineáris egyenletrendszerek, az Rn-beli generált altérhez tartozás kérdése, illetve a mátrixszorzáson alapuló mátrixegyenletek között. Kapcsolat négyzetes mátrix determinánsa, illetve a sorok és az oszlopok lineáris függetlensége között.
  • A tematika kialakítása a Matematika Intézettel egyeztetve történt.
  • 9. A tantárgy oktatásának módja (előadás, gyakorlat, laboratórium) A tárgyból heti 3 óra előadás és heti 2 órás kiscsoportos gyakorlat van.

    Az előadásokon az új elmélet kerül bemutatásra, ennek gyakorlása és feladatokban való alkalmazása zajlik a gyakorlatokon. A gyakorlatok mindig szorosan kapcsolódnak a megfelelő előadás anyagához, ezért azokon az előadáson tanult anyag ismerete elvárás a hallgatóktól. Az előadásokon tárgyalt fogalmak és ismeretek begyakorlása, elmélyítése a gyakorlatokon zajlik, az itt zajló munka (beleértve a házi feladatok megoldását is) a tanulási folyamat alapvető fontosságú része. Az előadások a legtöbb esetben szorosan épülnek a korábbi hetek anyagára, ezek ismerete nélkül az új anyag általában nem követhető.

    A gyakorlatokon az előadáson elhangzott elméletet felhasználó feladatokat oldunk meg, ösztönözve a hallgatók aktív részvételét egyéni és csoportos munkában egyaránt.

    10. Követelmények

    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 40% -os teljesítmény.

    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:

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

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

     Vizsgaidőszakban: Vizsgára az jelentkezhet, aki érvényes aláírással rendelkezik. A vizsga ebből a tárgyból szóbeli.

    A vizsgajegyet a két zárthelyi eredményéből és a vizsgán nyújtott szóbeli teljesítmény súlyozott átlaga, amiben a zárthelyik súlya 2, a szóbeli vizsgáé pedig 3. 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 vizsgán kapott végső jegyet meghatározó pontszámot az alábbi képlettel számítjuk ki. (zh1 és zh2 az első, illetve második zárthelyin, v pedig a szóbeli vizsgán szerzett pontszám.)

    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.

    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ővizsgát nem tartunk.
    11. Pótlási lehetőségek Mindkét zárthelyihez biztosítunk egy-egy pótlási alkalmat (a szorgalmi időszakban vagy a pótlási héten). Ezeket fel lehet használni a megfelelő zárthelyi dolgozat pótlására vagy az eredményének a javítására. Az utóbbi esetben mindenképpen az új pontszám lesz érvényes, akkor is, ha az rosszabb, mint az eredeti. Ez alól egy kivétel van: a már megszerzett aláírást és az adott zárthelyin a megszerzéséhez tartozó minimális pontszámot egy balsikerű javítási kísérlettel nem lehet elveszíteni. Ha valaki egy pótzárthelyin megjelenik (és a feladatsort átveszi), azt úgy tekintjük, hogy az illető kísérletet tett a dolgozat megírására (és így rá a fenti feltételek vonatkoznak).
    Akinek nincs aláírása, és a pótlási alkalmakon sem sikerült aláírást szereznie, ám egyetlen zárthelyi eredményes megírásával az aláírás megszerezhető, az jogosult részt venni a díjköteles pótlási alkalmon. Erre a neptunban kell jelentkezni, és különeljárási díjat kell érte fizetni. A díjköteles pótlás egy, a megfelelő zárthelyi anyagából, az adott zárthelyivel azonos feltételek szerint íratott számonkérés, de azon IMSC pont már nem szerezhető.
    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ábor: Gráfelméleti feladatok, TypoTEX Kiadó 2006.

    Szeszlér Dávid: Bevezetés a számításelméletbe: http://cs.bme.hu/bsz1/jegyzet/bsz1_jegyzet.pdf

    Fleiner Tamás: A számítástudomány alapjai: http://www.cs.bme.hu/~fleiner/jegyzet/NESZ.pdf

    14. A tantárgy elvégzéséhez átlagosan szükséges tanulmányi munka
    Kontakt óra70
    Félévközi készülés órákra28
    Felkészülés zárthelyire14
    Házi feladat elkészítése6
    Kijelölt írásos tananyag elsajátítása
    Vizsgafelkészülés32
    Összesen150
    15. A tantárgy tematikáját kidolgozta Fleiner Tamás, egyetemi tanár, SzIT
    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.
    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 = min(25, 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.