Diszkrét matematika 2 b szak­irány kérdések

Gráfok

  1. Definiálja a gráf, csúcsok, élek és illeszkedési leképezés fogalmát.
  2. Definiálja az "illeszkedik", "végpontja" és "izolált csúcs" fogalmakat.
  3. Definiálja az üres gráf és az illeszkedési reláció fogalmát.
  4. Definiálja csúcsok, illetve élek szomszédosságát.
  5. Definiálja a hurok­él és a párhuzamos élek fogalmát.
  6. Definiálja az egyszerű gráf és a véges gráf fogalmát.
  7. Definiálja gráfban a fok­szám és a reguláris gráf fogalmát.
  8. Mit mondhatunk gráfban a fok­számok összegéről?
  9. Definiálja gráfok izomorfiáját.
  10. Mondjon elégséges feltételt arra, hogy két gráf ne legyen izomorf.
  11. Mondjon elégséges feltételt arra, hogy két egyszerű gráf izomorf legyen.
  12. Definiálja a teljes gráf fogalmát.
  13. Hány éle van egy teljes gráfnak?
  14. Definiálja a páros gráf fogalmát.
  15. Adja meg a "három ház, három kút" gráfot.
  16. Definiálja a rész­gráf és a feszített rész­gráf fogalmát.
  17. Definiálja rész­gráf komplementerét.
  18. Definiálja az él­halmaz illetve csúcs­halmaz törlésével kapott gráfot.
  19. Definiálja a séta és a séta hossza fogalmát.
  20. Definiálja a nyílt és a zárt sétát.
  21. Definiálja az út fogalmát.
  22. Mikor lesz egy nulla illetve egy hosszú séta út?
  23. Definiálja a vonal fogalmát.
  24. Definiálja a kör fogalmát.
  25. Van­-e egy illetve kettő hosszú kör?
  26. Hogyan kaphatunk sétából utat? Fogalmazza meg az állítást.
  27. Fogalmazza meg a séták körök segítségével való előállítására vonatkozó állítást.
  28. Definiálja az össze­függőség és a komponens fogalmát.
  29. Igaz­-e, hogy egy gráf minden éle valamely komponenshez tartozik?
  30. Mi a kapcsolat a komponensek és az össze­függőség között?
  31. Definiálja a fa fogalmát.
  32. Fogalmazzon meg két szükséges és elégséges feltételt arra, hogy egy egyszerű gráf fa legyen.
  33. Egy véges gráfban nincs kör, de van él. Mit állíthatunk fok­számokkal kapcsolatban?
  34. Egy egyszerű véges gráfnak \(n\) csúcsa van. Fogalmazzon meg két olyan szükséges és elégséges feltételt amelyben szerepel az élek száma, arra, hogy a gráf fa.
  35. Definiálja a feszítő­fa fogalmát.
  36. Mit állíthatunk feszítő­fa létezéséről?
  37. Mit állíthatunk véges összefüggő gráfban a körök számáról?
  38. Mikor mondjuk, hogy egy csúcs­halmaz illetve él­halmaz elvág két csúcsot?
  39. Definiálja az elvágó él­halmaz és a vágás fogalmát.
  40. Mit állíthatunk véges összefüggő gráfban a vágások számáról?
  41. Definiálja az erdő fogalmát. Mi az összefüggés a fákkal?
  42. Definiálja a feszítő erdő fogalmát. Hány éle van egy véges gráf feszítő erdőjének?
  43. Definiálja az Euler­-vonal fogalmát.
  44. Fogalmazza meg a véges összefüggő gráfok vonalak egyesítéseként való előállítására vonatkozó tételt.
  45. Definiálja a Hamilton­-út illetve Hamilton­-kör fogalmát.
  46. Definiálja a címkézett gráf fogalmát.
  47. Definiálja a súlyozott gráf fogalmát és egy véges rész­halmaz súlyát.
  48. Fogalmazza meg a Kruskal algoritmust és a rá vonatkozó tételt.
  49. Mit értünk mohó algoritmuson? Mondjon példát, amikor egy mohó algoritmus nem ad optimális megoldást.
  50. Definiálja az irányított gráf, csúcsok, élek és illeszkedési leképezés fogalmát.
  51. Definiálja irányított gráfban a kezdő­pont és a végpont fogalmát.
  52. Hogyan kaphatunk irányított gráfból irányítatlan gráfot? Miért használhatjuk irányított gráfokra az irányítatlan gráfokra definiált fogalmakat?
  53. Definiálja a gráf irányítása illetve megfordítása fogalmát.
  54. Definiálja a szigorúan párhuzamos élek fogalmát.
  55. Definiálja az egyszerű gráf és a véges gráf fogalmát irányított gráf esetén.
  56. Definiálja csúcs be­fokát és ki­fokát.
  57. Mit mondhatunk irányított gráfokra a fok­számok összegéről?
  58. Hogyan szemléltethetünk egy relációt irányított gráffal?
  59. Definiálja irányított gráfok izomorfiáját.
  60. Definiálja az irányított rész­gráf és a feszített irányított rész­gráf fogalmát.
  61. Definiálja irányított rész­gráf komplementerét.
  62. Definiálja az él­halmaz illetve csúcs­halmaz törlésével kapott irányított gráfot.
  63. Definiálja a irányított séta és az irányított séta hossza fogalmát.
  64. Definiálja a nyílt és a zárt irányított sétát.
  65. Definiálja az irányított út fogalmát.
  66. Definiálja az irányított kör fogalmát.
  67. Definiálja az erős össze­függőség és az erős komponens fogalmát.
  68. Igaz­-e, hogy egy irányított gráf minden éle valamely erős komponenshez tartozik?
  69. Mi a kapcsolat az erős komponensek és az erős össze­függőség között?
  70. Definiálja az irányított fa és gyökere fogalmát.
  71. Definiálja a irányított fa szintjeit.
  72. Definiálja irányított fában a leveleket.
  73. Fogalmazza meg a Dijkstra algoritmust és a rá vonatkozó tételt.
  74. Mikor mondjuk, hogy egy gráf egy \(X\subset\mathbb{R}^n\) halmazban rajzolható?
  75. Mit mondhatunk a gráfok $\mathbb{R}3$-beli rajzolhatóságáról?
  76. Mi a kapcsolat a síkba és a gömbre rajzolható gráfok között?
  77. Fogalmazza meg az Euler formulát.
  78. Definiálja a jól színezés fogalmát.
  79. Definiálja a kromatikus számot.

Csoportok

  1. Definiálja egy művelet esetén a homomorfizmus és a homomorf kép fogalmát.
  2. Definiálja egy művelet esetén a monomorfizmus, az epimorfizmus és az izomorfizmus fogalmát.
  3. Definiálja egy művelet esetén az endomorfizmus és az automorfizmus fogalmát.
  4. Mit mondhatunk homomorfizmusnál fél­csoport, egység­elem, inverz és felcserélhető elemek esetén?
  5. Mi mondhatunk homomorfizmusnál csoport, kommutatív fél­csoport és Abel­-csoport esetén?
  6. Adjon meg szükséges és elégséges feltételeket arra, hogy egy fél­csoport csoport legyen.
  7. Fogalmazza meg csoportban az egyszerűsítési szabályt.
  8. Adjon példát invertálható műveletre, amellyel nem kapunk csoportot.
  9. Adja meg a szorzással mint művelettel tekintett egységnyi abszolút érték komplex számok csoportjának három valódi rész­csoportját.
  10. Mit értünk a Klein­-féle csoporton? Kommutatív­-e?
  11. Mit értünk diéder­csoporton?
  12. Definiálja a rész­csoport, triviális rész­csoport és valódi rész­csoport fogalmát.
  13. Adjon meg szükséges és elégséges feltételeket arra, hogy egy csoport egy rész­halmaza rész­csoport legyen.
  14. Mit mondhatunk rész­csoportok metszetéről és egyesítéséről?
  15. Definiálja a generátum és a generátor­rendszer fogalmát.
  16. Definiálja a ciklikus csoport és generátora fogalmát.
  17. Fogalmazza meg a generátumot leíró állítást.
  18. Mit mondhatunk ciklikus csoport homomorf képéről?
  19. Definiálja csoport és elem rendjét.
  20. Fogalmazza meg a ciklikus csoportok szerkezetét leíró tételt.
  21. Mi a kapcsolat elem és rész­csoport rendje között?
  22. Mit mondhatunk ciklikus csoport rész­csoportjairól?
  23. Mit mondhatunk véges ciklikus csoport rész­csoportjai generátorainak számáról?
  24. Definiálja a bal- és jobboldali mellék­osztályokat.
  25. Mi a kapcsolat a bal- és a jobboldali mellék­osztályok között?
  26. Definiálja rész­csoport indexét.
  27. Fogalmazza meg Lagrange tételét.
  28. Mi a kapcsolat elem rendje és a csoport rendje között?
  29. Fogalmazzon meg olyan tételt, amely lehetővé teszi, hogy egy csoport rendjéből a ciklikusságára következtessünk.
  30. Adjon meg szükséges és elégséges feltételt arra, hogy egy csoportnak ne legyen nem triviális rész­csoportja.
  31. Definiálja a normálosztó fogalmát.
  32. Adjon meg három olyan csoportot, amelyben minden rész­csoport normálosztó.
  33. Adjon meg szükséges és elégséges feltételeket arra, hogy egy rész­csoport normálosztó legyen.
  34. Mit mondhatunk normálosztók metszetéről és egyesítéséről?
  35. Fogalmazza meg kompatibilis osztályozások és a normálosztók közötti kapcsolatot leíró tételt.
  36. Definiálja a faktor­csoport fogalmát és fogalmazza meg a definícióban felhasznált tételt.
  37. Adjon meg három példát faktor­csoportra.
  38. Fogalmazza meg a homomorfizmus–tételt csoportokra.
  39. Definiálja csoportok direkt szorzatát.
  40. Fogalmazza meg a véges Abel–csoportok alap­tételét.

Gyűrűk és testek

  1. Igaz–e hogy egy egység­elemes integritási tartomány akkor és csak akkor test, ha minden nem nulla eleme egység?
  2. Igaz–e hogy egy véges integritási tartomány test?
  3. Definiálja a Gauss–egészek gyűrűjét. Igaz–e, hogy két egység van?
  4. Igaz–e, hogy egy adott halmazt egy testbe képez függvények gyűrűje is test?
  5. Definiálja két művelet esetén a homomorfizmus és a homomorf kép fogalmát.
  6. Definiálja két művelet esetén a monomorfizmus, az epimorfizmus és az izomorfizmus fogalmát.
  7. Definiálja két művelet esetén az endomorfizmus és az automorfizmus fogalmát.
  8. Mi mondhatunk homomorfizmusnál gyűrű képéről?
  9. Definiálja gyűrű karakterisztikáját. Milyen állítást használt?
  10. Fogalmazza meg a gyűrűk karakterisztikájára vonatkozó tételt.
  11. Definiálja a rész­gyűrű fogalmát.
  12. Definiálja a jobb­ideál, bal­ideál és ideál fogalmát.
  13. Definiálja a triviális ideál és a valódi ideál fogalmát.
  14. Definiálja az egyszerű gyűrű fogalmát.
  15. Definiálja a generált ideál és a fő­ideál fogalmát.
  16. Mondjon négy példát \(\mathbb{R}^\mathbb{R}\) rész­gyűrűjére.
  17. Mondjon példát $\mathbb{Z}$-ben ideálra. Fő­ideál–e?
  18. Definiálja gyűrűben a mellék­osztályokat.
  19. Fogalmazza meg kompatibilis osztályozások és az ideálok közötti kapcsolatot leíró tételt.
  20. Definiálja a faktor­gyűrű fogalmát és fogalmazza meg a definícióban felhasznált tételt.
  21. Fogalmazza meg a homomorfizmus–tételt gyűrűkre.
  22. Adjon példát \(\mathbb{Z}\) faktor­gyűrűjére.
  23. Fogalmazza meg egy kommutatív egység­elemes gyűrűben a fő­ideálokat leíró állítást.
  24. Fogalmazza meg egy egység­elemes integritási tartományban az oszthatóság és a generált fő­ideálok kapcsolatát leíró állítást.
  25. Definiálja a Gauss–gyűrű fogalmát.
  26. Gauss–gyűrűben hogyan olvashatók le a faktorizációból az osztók?
  27. Igaz–e hogy Gauss–gyűrűben létezik legnagyobb közös osztó és legkisebb közös többszörös?
  28. Igaz–e hogy Gauss–gyűrűben minden irreducibilis elem prím?
  29. Definiálja az euklideszi gyűrű fogalmát.
  30. Fogalmazza meg az euklideszi gyűrűben az egységeket és az asszociáltakat leíró tételt.
  31. Fogalmazza meg a bővített euklideszi algoritmust euklideszi gyűrűben.
  32. Mi a kapcsolat euklideszi gyűrűben a prím­elemek és az irreducibilis elemek között?
  33. Fogalmazza meg euklideszi gyűrűben a faktorizációra vonatkozó tételt.
  34. Definiálja a hányados­test fogalmát. Milyen állítást használt?
  35. Hogyan ágyazható be egy integritási tartomány a hányados­testébe?

Polinomok

  1. Definiálja az egy­határozatlanú polinom fogalmát.
  2. Definiálja egy­határozatlanú polinomok összeadását és szorzását.
  3. Hogyan azonosíthatjuk a gyűrű elemeit bizonyos polinomokkal? Hogy hívjuk ezeket a polinomokat?
  4. Definiálja polinom együtthatóit, fő­együtthatóját és fok­számát.
  5. Definiálja a lineáris polinomokat.
  6. Definiálja a monom fogalmát egy határozatlan esetén.
  7. Definiálja a fő­polinom fogalmát.
  8. Mit mondhatunk polinomok szorzatának fő­együtthatójáról?
  9. Mit mondhatunk polinomok szorzatának fokáról?
  10. Definiálja polinom helyettesítési értékét és gyökét.
  11. Definiálja a polinomhoz tartozó polinom­függvényt. Tartozhat–e különböző polinomokhoz ugyanaz a polinom­függvény?
  12. Fogalmazza meg a maradékos osztás tételét polinomokra.
  13. Fogalmazza meg a gyök­tényező leválasztására vonatkozó állítást.
  14. Legfeljebb hány gyöke van egy polinomnak? Fogalmazza meg az állítást.
  15. Milyen esetben kölcsönösen egyértelmű a megfeleltetés a polinomok és a polinom­függvények között? Fogalmazza meg az állítást.
  16. Milyen esetben alkotnak a polinomok euklideszi gyűrűt? Fogalmazza meg az állítást.
  17. Ismertesse a Horner–elrendezést.
  18. Mondjon példát, amikor egy adott másodfokú polinomnak nulla, egy illetve két gyöke van.
  19. Definiálja polinom algebrai deriváltját.
  20. Milyen négy tulajdonsággal jellemezhető a polinomhoz az algebrai deriváltját rendel leképezés?
  21. Az \(f, g\) polinomokra \(g^n \mid f\). Mit állíthatunk $f'$-ről? Fogalmazza meg az állítást.
  22. Hogyan kaphatunk egy polinomból négyzet­mentes polinomot? Fogalmazza meg az állítást.
  23. Definiálja polinom többszörös gyökét.
  24. Mi a kapcsolat a polinom gyökei és a deriváltjának a gyökei között? Fogalmazza meg az állítást.
  25. Lehet–e egy polinom $n$-szeres gyöke a deriváltnak is legalább $n$-szeres gyöke?
  26. Írja le az egységeket test feletti polinomok körében.
  27. Hogyan kaphatunk véges testeket?
  28. Fogalmazza meg a véges testek elem­számát leíró tételt.
  29. Fogalmazza meg a véges test nem nulla elemei multiplikatív csoportjának szerkezetét leíró tételt.
  30. Van–e minden prím­hatványhoz olyan elem­számú véges test?
  31. Írja le az irreducibilis polinomokat a \(\mathbb{C}\) feletti polinomok körében.
  32. Írja le az irreducibilis polinomokat az \(\mathbb{R}\) feletti polinomok körében.
  33. Mit tud a \(\mathbb{Q}\) feletti irreducibilis polinomokról?
  34. Igaz–e, hogy \(\mathbb{Z}[x]\) euklideszi gyűrű?
  35. Igaz–e, hogy \(\mathbb{Z}[x]\) Gauss–gyűrű?
  36. Fogalmazza meg Gauss tételét egyértelmű faktorizációs tartományokról.
  37. Ismertesse a Lagrange–interpoláiót.
  38. Ismertessen egy titok­megosztási eljárást.
  39. Ismertesse a Kroneker–eljárást.
  40. Fogalmazza meg a véges testek alap­tételét.
  41. Hogyan kaphatunk véges testeket? Írjon le olyan eljárást, amely minden véges testet megad.

Kódolás

  1. Definiálja a gyakoriság és a relatív gyakoriság fogalmát.
  2. Definiálja egyedi üzenet információ­tartalmát. Mi a bit?
  3. Definiálja az eloszlás és az entrópia fogalmát.
  4. Adja meg a pontos felső korlátot eloszlás entrópiájára. Mikor teljesül egyenlőség?
  5. Mi a forrás­kódolás? Mik a részei?
  6. Rajzolja fel az üzenet­átvitel részletes sémáját.
  7. Ismertesse a betűnkénti kódolást.
  8. Definiálja a prefix, infix és szufix fogalmát.
  9. Ismertesse a kód és a kód­fa kapcsolatát.
  10. Definiálja a prefix, egyenletes és vesszős kódot. Mi a kapcsolatuk?
  11. Adjon példát nem dekódolható kódra.
  12. Adjon példát fejthető, de nem prefix kódra.
  13. Fogalmazza meg a McMillan–egyenltlenséget tartalmazó tételt.
  14. Definiálja az átlagos szó­hosszúság és az optimális kód fogalmát.
  15. Van–e mindig optimális kód betűnkénti kódolásnál?
  16. Fogalmazza meg Shannon tételét zaj­mentes csatornára.
  17. Ismertesse egy optimális kód kódfá jának tula jdonságait.
  18. Fogalmazza meg azt a három állítást, amelynek alapján optimális kód konstruálható.
  19. Írja le, hogyan konstruálunk Huffman–kódot.
  20. Írja le, mit érhetünk el a kódolandó ábécé kiterjesztésével.
  21. Ismertesse a szótár­kódok alapgondolatát.
  22. Ismertesse a paritás­bites kódot.
  23. Definiálja a $t$-hiba jelző és pontosan $t$-hiba jelző kód fogalmát.
  24. Definiálja kód távolságát és súlyát.
  25. Mi a kapcsolat a kód távolsága és hiba jelző képessége között?
  26. Ismertesse a minimális távolságú dekódolást.
  27. Definiálja a $t$-hiba javító és pontosan $t$-hiba javító kód fogalmát.
  28. Mi a kapcsolat a kód távolsága és hiba javító képessége között?
  29. Definiálja a lineáris kód fogalmát és a kapcsolódó jelöléseket.
  30. Ismertesse a két­dimenziós paritás­ellenőrzést.
  31. Mi a Hamming–korlát?
  32. Mi a Singleton–korlát?
  33. Mi az MDS–kód és miért hívják így?
  34. Definiálja a lineáris kód fogalmát és a kapcsolódó jelöléseket.
  35. Definiálja a generátor­mátrix, ellenőrző mátrix és s szindróma fogalmát.
  36. Ismertesse a szindróma–dekódolást.
  37. Ismertesse a Fano–kódot.
  38. Ismertesse a polinom­kódokat.
  39. Ismertesse a CRC-t.

Author: Emil VATAI

Created: 2021-05-17 月 13:08

Validate