K-INFO
HU
EN
Belépés

A számítástudomány alapjai

Foundation of Computer Science
A tantárgyleírás hatályossága
Hatályosság kezdete:
2026. March 21.
Hatályosság vége:
—
Tantárgy neve (magyarul, angolul)
A számítástudomány alapjai
Foundation of Computer Science
Tantárgykód BMEVISZA105
Tantárgyjelleg —
Képzési szint —
Kurzustípusok és óraszámok (heti/féléves)
Kurzustípus elmélet gyakorlat laboratóriumi gyakorlat
óraszám (heti) 4 2 0
jelleg (kapcsolt/önálló) — kapcsolt —
Tanulmányi teljesítmény/értékelés típusa vizsga
Tantárgy kreditértéke 6
Tantárgyfelelős
DR. Katona Gyula
beosztás: egyetemi tanár
Tantárgyat gondozó oktatási szervezeti egység
Számítástudományi és Információelméleti Tanszék
Kar Villamosmérnöki és Informatikai Kar
Tantárgy weboldala www.cs.bme.hu/sza
Tantárgy elsődleges mintatantervi jellege —
Közvetlen előkövetelmények – Erős előkövetelmény nincs
Közvetlen előkövetelmények – Gyenge előkövetelmény nincs
Közvetlen előkövetelmények – Párhuzamos előkövetelmény nincs
Közvetlen előkövetelmények – Mérföldkő előkövetelmény nincs
Közvetlen előkövetelmények – Kizáró feltétel nincs

Célkitűzés

Tantárgyprogram

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

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.

Tanulmányi eredmények

Ez a tantárgy a KKK rendeletben meghatározott, következő kompetenciák fejlesztését szolgálja:

Tudás

Nincsenek rögzített tanulási eredmények.

Képességek

Nincsenek rögzített tanulási eredmények.

Attitűd

Nincsenek rögzített tanulási eredmények.

Autonómia és felelősség

Nincsenek rögzített tanulási eredmények.

Oktatási módszertan

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

Tanulástámogató anyagok

Online források
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.

A tantárgy teljesítéséhez ajánlott előzetes ismeretek

Tudás típusú kompetenciák
(azon előzetes ismeretek összessége, amelyek megléte nem kötelező, de a tantárgy eredményes teljesítését nagyban elősegíti)
nincs
Képesség típusú kompetenciák
(azon előzetes képességek és készségek összessége, amelyek megléte nem kötelező, de a tantárgy eredményes teljesítését nagyban elősegíti)
nincs
Ajánlott (nem kötelező) előzetesen megszerzendő kompetenciák
(azon ajánlott (nem kötelező) előzetesen megszerzendő kompetenciák összessége, amelyek jelentősen hozzájárulnak a tantárgy eredményes teljesítéséhez)
nincs
Általános szabályok
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.  Pótlási lehetőségek: lásd a 10. pontot
Teljesítményértékelési módszerek
Szorgalmi időszakban végzett teljesítményértékelések részletes leírása

Nincs megadva részletes értékelés.

Szorgalmi időszakban végzett teljesítményértékelések részaránya

Nincs megadva részarány.

Vizsgaidőszakban végzett teljesítményértékelések részletes leírása

Nincs megadva részletes értékelés.

Vizsgarészek részaránya

Nincs megadva részarány.

Érdemjegy megállapítása

Nincs megadva érdemjegy határ.

Jelenléti és részvételi követelmények

Nincs megadva jelenléti követelmény.

Javítás, ismétlés és pótlás különös szabályai

Nincs megadva.

Rövid leírás

Nincs megadva.

Részletes leírás

Nincs megadva.

Ajánlott tantárgyak

Nincs megadva.

A tantárgy elvégzéséhez szükséges tanulmányi munka

Nincs megadva munkaidő bontás.

Tantárgykövetelmények hatályossága
Tantárgykövetelmények hatályosságának kezdete:
—
Tantárgykövetelmények hatályosságának vége:
—
Tantervi elhelyezés

Nincsenek rögzített tantervi elhelyezések ehhez a tárgyverzióhoz.