A számítástudomány alapjai
A tantárgyleírás hatályossága
| 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) |
|
||||||||||||
| 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
elérhetőség:
katona.gyula@vik.bme.hu
|
||||||||||||
| 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
|
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 |
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
Tanulástámogató anyagok
Online források
A tantárgy teljesítéséhez ajánlott előzetes ismeretek
Általános szabályok
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
Tantervi elhelyezés
Nincsenek rögzített tantervi elhelyezések ehhez a tárgyverzióhoz.