MA21x2a - Matematika és programozás alapjai szigorlat
2004/05
A
- Reláció, leképezés
(függvény) fogalma. Szürjektív, injektív
és bijektív leképezések.
Relációk tulajdonságai, gráf
ábrázolása. Rendezés, parciális
rendezés, ekvivalenciarelációk,
ekvivalenciaosztályok.
- Ítéletek, logikai műveletek.
Ítéletkalkulus. Diszjunktív normálforma.
Boole-algebra. Boole függvények és
normálformák. Logikai áramkörök.
- Maradékos osztás tétele, az
oszthatóság legfontosabb tulajdonságai,
oszthatósági szabályok. Legnagyobb közös
osztó és tulajdonságai, legkisebb közös
többszörös és tulajdonságai.
Lineáris Diophantosi egyenletek. Prímszámok. A
számelmélet alaptétele. Osztók
prímtényezős alakja. Az osztók száma.
Prímszámokra vonatkozó tételek.
Kongruenciák és tulajdonságaik.
Maradékosztályok. Multiplikatív
számelméleti függvények.
- Irányított és közönséges
gráf. Adjacencia–mátrix. Egyszerű gráf,
részgráf, feszített részgráf.
Gráfvonal, út, kör, Euler–vonal, Euler–vonalat
előállító algoritmus, Hamilton kör.
Összefüggőség, komponensek. Gráfok
tárolása. Gráfok izomorfiája.
Síkbarajzolhatóság. Kuratowski tétele.
Síktérképek, gráfszínezés.
- Bináris fák, teljes bináris fák
és ezekre vonatkozó tételek. Feszítőfa.
Mélységben keresés és
széltében keresés módszere.
Minimális feszítőfa meghatározása. Kruskal
és Prim algoritmusa. Fabejárások. Preorder,
inorder, postorder bejárás. Aritmetikai
kifejezések reprezentálása bináris
fákkal. Infix, postfix és prefix forma. Fák
és rendező algoritmusok. Buborék rendezés,
rendezés összefésüléssel,
kiválasztásos rendezés, gyorsrendezés. A
rendező algoritmusok időbonyolultságának
vizsgálata.
- Hálózati folyamok. Maximális folyamot kereső
algoritmusok: Ford-Fulkerson javító út kereső
algoritmusa és előfolyam indító algoritmus.
Maximális folyam-minimális vágás
tétel. Párosítások. Hall-féle
házassági tétel. Maximális
párosítást-kereső algoritmus.
- Az algebrai struktúra fogalma. Csoport. A csoport
felbontása diszjunkt mellékosztályokra.
Faktorcsoportok. Permutációcsoport. Gyűrű. Ideál.
Euklideszi gyűrű. Polinomgyűrű. Test. Az algebra alaptétele
és következményei.
B
- A vektor, vektortér fogalma. Lineáris
kombináció. Vektorok lineáris
függetlensége. A lineárisan független és
a lineárisan összefüggő vektorhalmazok fontosabb
tulajdonságai. Generátorrendszer, bázis,
dimenzió. Alterek.
- Mátrixok, műveletek mátrixokkal. Mátrix
rangja. Négyzetes mátrix inverze, determinánsa,
kiszámításuk.
- Lineáris leképezés, magtér,
képtér, leképezés mátrixa fogalma.
Lineáris leképezés
sajátértéke, sajátvektora,
sajátaltere, a sajátértékek geometriai
és algebrai multiplicitása.
- Sorozat, sor fogalma. Sorozat korlátossága,
monotonitása, konvergenciája. Sor konvergenciája,
abszolút konvergenciája, hányados-, gyök-
és majoráns kritérium. Nevezetes sorozatok
és sorok határértéke.
- Egyváltozós függvény
differenciálhatósága. Differenciahányados,
differenciálhányados, derivált
függvény. Érintő definíciója.
Differenciálhatóság és folytonosság
kapcsolata. Deriválási szabályok. A
függvény intervallumbeli viselkedése és a
deriváltak kapcsolata (monotonitás, konvexitás).
Többváltozós függvény parciális
deriváltja és differenciálhatósága.
- Határozatlan integrál fogalma, azonosságok.
Riemann-integrál fogalma (beosztás, beosztás
finomsága, Riemann-féle közelítő összeg)
egy- és kétváltozós
függvényekre. Tulajdonságok. A
Riemann-integrál geometriai jelentése.
Newton-Leibniz-formula egy változóban, kettős
integrál kiszámítása téglalapon
és normáltartományon.
C
- Elágazások, ciklusok, alprogramok és
fájlok szerepe a programozásban.
- Hogyan lesz a feladat megfogalmazásából
program? Adatszerkezetekből kiinduló
algoritmuskészítés (Jackson).
- Rendező algoritmusok – mondatszerkezeti leírással
és folyamatábrával (struktogram) bemutatva.
- Az operációs rendszer fogalma, feladatai. Az
operációs rendszerek fejlődése. Az
operációs rendszerek szervezési módjai
(monolitikus, rétegelt, virtuális gép,
kliens-szerver). Az operációs rendszer alapfogalmai
(processzus, rendszerhívások). A processzus-modell.
Processzusok kommunikációja (IPC), versenyhelyzet,
kritikus szekció, holtpont és kölcsönös
kizárás fogalma). Klasszikus IPC problémák
(gyártó-fogyasztó, étkező
filozófusok, olvasók-írók, alvó
borbély) és megoldásaik.
- Processzusok ütemezése (round robin,
prioritásos, többszörös sorok, legrövidebbet
először, garantált ütemezés,
sorsjáték-ütemezés). Valós idejű
ütemezések (állandó arány,
legkorábbi határidőt először, legkisebb
lazaság). A kétszintű ütemezés. Az
operációs rendszer indítása (boot,
partíciós tábla, MBR).
Megszakításkezelés. I/O eszközök,
eszközvezérlők. IRQ, PnP, DMA, interleaving fogalma.
Eszközfüggetlenség megvalósítása,
eszközök megosztott és monopol használata.
- Memóriagazdálkodás (multiprogramozás
rögzített méretű partíciókkal, csere).
Szabad memóriaterület nyilvántartása
(bittérkép, láncolt lista, lyukkeresési
algoritmusok). Lapozás (MMU, többszintű
laptáblák, TLB, invertált
laptáblák.). Lapcserélési algoritmusok
(optimális, NRU, FIFO, második esély, óra,
LRU, NFU, öregedés). Szegmentálás fogalma.
Fájlrendszerek (FAT, i-csomó, NTFS). A
fájlrendszer konzisztenciájának
ellenőrzése, hibáinak javítása. Az
operációs rendszer védelme, biztonsági
kérdések.