MA21x2a - Matematika és programozás alapjai szigorlat
2004/05

A

  1. 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.
  2. Í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.
  3. 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.
  4. 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.
  5. 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.
  6. 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.
  7. 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

  1. 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.
  2. Mátrixok, műveletek mátrixokkal. Mátrix rangja. Négyzetes mátrix inverze, determinánsa, kiszámításuk.
  3. 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.
  4. 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.
  5. 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.
  6. 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

  1. Elágazások, ciklusok, alprogramok és fájlok szerepe a programozásban.
  2. Hogyan lesz a feladat megfogalmazásából program? Adatszerkezetekből kiinduló algoritmuskészítés (Jackson).
  3. Rendező algoritmusok – mondatszerkezeti leírással és folyamatábrával (struktogram) bemutatva.
  4. 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.
  5. 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.
  6. 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.