Diszkr´et matematika 2 (C) vizsgaanyag, 2012 tavasz A vizsga menete: a vizsga ´ır´asbeli ´es sz´obeli r´eszb˝ol ´all. Az ´ır´asbeli beugr´on az al´ abbi k´erd´esek k¨ oz¨ ul szerepel ¨osszesen 12 darab, mindegyik egy pontot ´er. Ezekre kell r¨ oviden v´ alaszolni, a sikeres beugr´ohoz 5 pontot kell megszerezni. Sikeres beugr´ o eset´en a sz´ obeli t´etelek (ld. k¨ ul¨on f´ajl) k¨oz¨ ul h´ uz egyet a vizsg´az´o, a jegyet a sz´ obeli vizsga alapj´an kapja.
Defin´ıci´ok, t´etelkimond´asok 1. Defini´ alja a gr´ af, cs´ ucsok, ´elek ´es illeszked´esi lek´epez´es fogalm´at. 2. Defini´ alja az ,,illeszkedik”, ,,v´egpontja” ´es ,,izol´alt cs´ ucs” fogalmakat. 3. Defini´ alja az u ¨res gr´ af ´es az illeszked´esi rel´aci´o fogalm´at. 4. Defini´ alja cs´ ucsok, illetve ´elek szomsz´edoss´ag´at. 5. Defini´ alja a hurok´el ´es a p´arhuzamos ´elek fogalm´at. 6. Defini´ alja az egyszer˝ u gr´af ´es a v´eges gr´af fogalm´at. 7. Defini´ alja gr´ afban a foksz´am ´es a regul´aris gr´af fogalm´at. 8. Mit mondhatunk gr´ afban a foksz´amok ¨osszeg´er˝ol? 9. Defini´ alja gr´ afok izomorfi´aj´at. 10. Mondjon el´egs´eges felt´etelt arra, hogy k´et gr´af ne legyen izomorf. 11. Mondjon el´egs´eges felt´etelt arra, hogy k´et egyszer˝ u gr´af izomorf legyen. 12. Defini´ alja a teljes gr´ af fogalm´at. 13. H´ any ´ele van egy teljes gr´afnak? 14. Defini´ alja a p´ aros gr´ af fogalm´at. 15. Adja meg a ,,h´ arom h´ az, h´arom k´ ut” gr´afot. 16. Defini´ alja a r´eszgr´ af ´es a fesz´ıtett r´eszgr´af fogalm´at. 17. Defini´ alja r´eszgr´ af komplementer´et. 18. Defini´ alja a s´eta ´es a s´eta hossza fogalm´at. 19. Defini´ alja a ny´ılt ´es a z´art s´et´at. 20. Defini´ alja az u ´t fogalm´at. 21. Mikor lesz egy nulla illetve egy hossz´ u s´eta u ´t? 22. Defini´ alja a vonal fogalm´at. 23. Defini´ alja a k¨ or fogalm´at. 24. Van-e egy illetve kett˝ o hossz´ u k¨or? 25. Hogyan kaphatunk s´et´ab´ol utat? Fogalmazza meg az ´all´ıt´ast. 26. Defini´ alja az ¨ osszef¨ ugg˝os´eg ´es a komponens fogalm´at. 27. Igaz-e, hogy egy gr´ af minden ´ele valamely komponenshez tartozik? 28. Mi a kapcsolat a komponensek ´es az ¨osszef¨ ugg˝os´eg k¨oz¨ott? 29. Defini´ alja a fa fogalm´ at.
30. Fogalmazzon meg k´et sz¨ uks´eges ´es el´egs´eges felt´etelt arra, hogy egy egyszer˝ u gr´ af fa legyen. 31. Egy v´eges gr´ afban nincs k¨or, de van ´el. Mit ´all´ıthatunk foksz´amokkal kapcsolatban? 32. Egy egyszer˝ u v´eges gr´afnak n cs´ ucsa van. Fogalmazzon meg k´et olyan sz¨ uks´eges ´es el´egs´eges felt´etelt amelyben szerepel az ´elek sz´ama, arra, hogy a gr´ af fa. 33. Defini´ alja a fesz´ıt˝ ofa fogalm´at. 34. Mit ´ all´ıthatunk fesz´ıt˝ ofa l´etez´es´er˝ol? 35. Mit ´ all´ıthatunk v´eges ¨ osszef¨ ugg˝o gr´afban a k¨or¨ok sz´am´ar´ol? 36. Mikor mondjuk, hogy egy cs´ ucshalmaz illetve ´elhalmaz elv´ag k´et cs´ ucsot? 37. Defini´ alja az elv´ ag´ o ´elhalmaz ´es a v´ag´as fogalm´at. 38. Mit ´ all´ıthatunk v´eges ¨ osszef¨ ugg˝o gr´afban a v´ag´asok sz´am´ar´ol? 39. Defini´ alja az erd˝ o fogalm´at. Mi az ¨osszef¨ ugg´es a f´akkal? 40. Defini´ alja az Euler-vonal fogalm´at. 41. Defini´ alja a Hamilton-´ ut illetve Hamilton-k¨or fogalm´at. 42. Defini´ alja a c´ımk´ezett gr´af fogalm´at. 43. Defini´ alja a s´ ulyozott gr´af fogalm´at ´es egy v´eges r´eszhalmaz s´ uly´at. 44. Fogalmazza meg a Kruskal algoritmust ´es a r´a vonatkoz´o t´etelt. 45. Mit ´ert¨ unk moh´ o algoritmuson? Mondjon p´eld´at, amikor egy moh´o algoritmus nem ad optim´ alis megold´ast. 46. Defini´ alja az ir´ any´ıtott gr´af, cs´ ucsok, ´elek ´es illeszked´esi lek´epez´es fogalm´ at. 47. Defini´ alja ir´ any´ıtott gr´afban a kezd˝opont ´es a v´egpont fogalm´at. 48. Hogyan kaphatunk ir´ any´ıtott gr´afb´ol ir´any´ıtatlan gr´afot? Mi´ert haszn´alhatjuk ir´ any´ıtott gr´ afokra az ir´any´ıtatlan gr´afokra defini´alt fogalmakat? 49. Defini´ alja a gr´ af ir´ any´ıt´asa illetve megford´ıt´asa fogalm´at. 50. Defini´ alja a szigor´ uan p´arhuzamos ´elek fogalm´at. 51. Defini´ alja az egyszer˝ u ir´any´ıtott gr´af ´es a v´eges ir´any´ıtott gr´af fogalm´at. 52. Defini´ alja cs´ ucs befok´ at ´es kifok´at. 53. Mit mondhatunk ir´ any´ıtott gr´afokra a foksz´amok ¨osszeg´er˝ol? 54. Hogyan szeml´eltethet¨ unk egy rel´aci´ot ir´any´ıtott gr´affal? 55. Defini´ alja ir´ any´ıtott gr´afok izomorfi´aj´at. 56. Defini´ alja az ir´ any´ıtott r´eszgr´af ´es a fesz´ıtett ir´any´ıtott r´eszgr´af fogalm´at. 57. Defini´ alja ir´ any´ıtott r´eszgr´af komplementer´et. 58. Defini´ alja az ´elhalmaz illetve cs´ ucshalmaz t¨orl´es´evel kapott ir´any´ıtott gr´afot. 59. Defini´ alja a ir´ any´ıtott s´eta ´es az ir´any´ıtott s´eta hossza fogalm´at. 60. Defini´ alja a ny´ılt ´es a z´art ir´any´ıtott s´et´at.
61. Defini´ alja az ir´ any´ıtott u ´t fogalm´at. 62. Defini´ alja az ir´ any´ıtott k¨or fogalm´at. 63. Defini´ alja az er˝ os ¨ osszef¨ ugg˝os´eg ´es az er˝os komponens fogalm´at. 64. Igaz-e, hogy egy ir´ any´ıtott gr´af minden ´ele valamely er˝os komponenshez tartozik? 65. Mi a kapcsolat az er˝ os komponensek ´es az er˝os ¨osszef¨ ugg˝os´eg k¨oz¨ott? 66. Defini´ alja az ir´ any´ıtott fa ´es gy¨okere fogalm´at. 67. Defini´ alja a ir´ any´ıtott fa szintjeit. 68. Defini´ alja ir´ any´ıtott f´ aban a leveleket. 69. Defini´ alja gr´ afok topologikus ekvivalenci´aj´at. 70. Fogalmazza meg Kuratowski t´etel´et s´ıkba rajzol´asr´ol. 71. Defini´ alja ir´ any´ıtott ´es ir´any´ıtatlan gr´af ´elm´atrix´at. 72. Defini´ alja ir´ any´ıtott ´es ir´any´ıtatlan gr´af cs´ ucsm´atrix´at. 73. Igaz-e hogy egy egys´egelemes integrit´asi tartom´any akkor ´es csak akkor test, ha minden nem nulla eleme egys´eg? 74. Defini´ alja gy˝ ur˝ u karakterisztik´aj´at. 75. Defini´ alja a Gauss-gy˝ ur˝ u fogalm´at. 76. Igaz-e hogy Gauss-gy˝ ur˝ uben minden irreducibilis elem pr´ım? 77. Defini´ alja az euklideszi gy˝ ur˝ u fogalm´at. 78. Fogalmazza meg az euklideszi gy˝ ur˝ uben az egys´egeket ´es az asszoci´altakat le´ır´ o t´etelt. 79. Mi a kapcsolat euklideszi gy˝ ur˝ uben a pr´ımelemek ´es az irreducibilis elemek k¨ oz¨ ott? 80. Fogalmazza meg euklideszi gy˝ ur˝ uben a faktoriz´aci´ora (irreducibilisek szorzat´ ara t¨ ort´en˝ o felbont´ as) vonatkoz´o t´etelt. 81. Defini´ alja az egyhat´ arozatlan´ u polinom fogalm´at. 82. Defini´ alja egyhat´ arozatlan´ u polinomok ¨osszead´as´at ´es szorz´as´at. 83. Defini´ alja polinom egy¨ utthat´oit, f˝oegy¨ utthat´oj´at ´es foksz´am´at. 84. Defini´ alja a line´ aris polinomokat. 85. Defini´ alja a monom fogalm´at egy hat´arozatlan eset´en. 86. Defini´ alja a f˝ opolinom fogalm´at. 87. Mit mondhatunk polinomok szorzat´anak f˝oegy¨ utthat´oj´ar´ol? 88. Mit mondhatunk polinomok szorzat´anak fok´ar´ol? 89. Defini´ alja polinom helyettes´ıt´esi ´ert´ek´et ´es gy¨ok´et. 90. Defini´ alja a polinomhoz tartoz´o polinomf¨ uggv´enyt. Tartozhat-e k¨ ul¨onb¨oz˝o polinomokhoz ugyanaz a polinomf¨ uggv´eny? 91. Fogalmazza meg a marad´ekos oszt´as t´etel´et polinomokra.
92. Milyen esetben alkotnak a polinomok euklideszi gy˝ ur˝ ut? Fogalmazza meg az ´ all´ıt´ ast. 93. Fogalmazza meg a gy¨ okt´enyez˝o lev´alaszt´as´ara vonatkoz´o ´all´ıt´ast. 94. Legfeljebb h´ any gy¨ oke van egy polinomnak? Fogalmazza meg a pontos all´ıt´ ´ ast. 95. Milyen esetben k¨ olcs¨ on¨osen egy´ertelm˝ u a megfeleltet´es a polinomok ´es a polinomf¨ uggv´enyek k¨ oz¨ott? Fogalmazza meg az ´all´ıt´ast. 96. Ismertesse a Horner-elrendez´est. 97. Mondjon p´eld´ at, amikor egy adott m´asodfok´ u polinomnak nulla, egy illetve k´et gy¨ oke van. 98. Defini´ alja polinom algebrai deriv´altj´at. 99. Milyen n´egy tulajdons´aggal jellemezhet˝o a polinomhoz az algebrai deriv´ altj´ at rendel˝ o lek´epez´es? 100. Defini´ alja polinom t¨ obbsz¨or¨os gy¨ok´et. 101. Mi a kapcsolat a polinom gy¨okei ´es a deriv´altj´anak a gy¨okei k¨oz¨ott? Fogalmazza meg az ´ all´ıt´ ast. 102. Lehet-e egy polinom n-szeres gy¨oke a deriv´altnak is legal´abb n-szeres gy¨ oke? 103. ´Irja le az egys´egeket test feletti polinomok k¨or´eben. 104. Hogyan kaphatunk v´eges testeket? Irjon le olyan elj´ar´ast, amely minden v´eges testet megad. 105. Fogalmazza meg a v´eges testek alapt´etel´et. 106. ´Irja le az irreducibilis polinomokat a C feletti polinomok k¨or´eben. 107. ´Irja le az irreducibilis polinomokat az R feletti polinomok k¨or´eben. 108. Mit tud a Q feletti irreducibilis polinomokr´ol? 109. Igaz-e, hogy Z[x] Gauss-gy˝ ur˝ u? 110. Fogalmazza meg Gauss t´etel´et egy´ertelm˝ u faktoriz´aci´os tartom´anyokr´ol. 111. Ismertesse a Lagrange-interpol´aci´ot. 112. Fogalmazza meg a parci´alis t¨ortekre bont´as t´etel´et 1/g alak´ u racion´alis f¨ uggv´enyre. 113. Defini´ alja a t¨ obbhat´ arozatlan´ u polinom fogalm´at. 114. Defini´ alja t¨ obbhat´ arozatlan´ u polinom egy¨ utthat´oit, tagjainak multifok´at ´es fok´ at. 115. Defini´ alja a t¨ obbhat´ arozatlan´ u monom fogalm´at. 116. Defini´ alja t¨ obbhat´ arozatlan´ u polinom fok´at. Milyen meg´allapod´asok mellett egy´ertelm˝ u egy t¨ obbhat´arozatlan´ u polinom fel´ır´asa? 117. Hogyan ´ırhatjuk fel k´et t¨obbhat´arozatlan´ u polinom ¨osszeg´enek, illetve szorzat´ anak az egy¨ utthat´oit? 118. Mit mondhatunk k´et t¨obbhat´arozatlan´ u polinom szorzat´anak a fok´ar´ol? 119. Defini´ alja az entr´ opia fogalm´at.
120. Ismertesse a bet˝ unk´enti k´odol´ast. 121. Defini´ alja a prefix, infix ´es szuffix fogalm´at. 122. Ismertesse a k´ od ´es a k´odfa kapcsolat´at. 123. Defini´ alja a prefix, egyenletes ´es vessz˝os k´odot. Mi a kapcsolatuk? 124. Adjon p´eld´ at nem dek´ odolhat´o k´odra. 125. Fogalmazza meg a McMillan-egyenl˝otlens´eget tartalmaz´o t´etelt. 126. Defini´ alja az ´ atlagos sz´ohossz´ us´ag ´es az optim´alis k´od fogalm´at. 127. Van-e mindig optim´ alis k´od bet˝ unk´enti k´odol´asn´al? 128. Fogalmazza meg Shannon t´etel´et zajmentes csatorn´ara. 129. Ismertesse egy optim´ alis k´od k´odf´aj´anak tulajdons´agait. 130. ´Irja le, hogyan konstru´alunk Huffman-k´odot. 131. Ismertesse a parit´ asbites k´odot. 132. Defini´ alja a t-hibajelz˝ o ´es pontosan t-hibajelz˝o k´od fogalm´at. 133. Defini´ alja k´ od t´ avols´ ag´at ´es s´ uly´at. 134. Mi a kapcsolat a k´ od t´avols´aga ´es hibajelz˝o k´epess´ege k¨oz¨ott? 135. Ismertesse a minim´ alis t´avols´ag´ u dek´odol´ast. 136. Defini´ alja a t-hibajav´ıt´o ´es pontosan t-hibajav´ıt´o k´od fogalm´at. 137. Mi a kapcsolat a k´ od t´avols´aga ´es hibajav´ıt´o k´epess´ege k¨oz¨ott? 138. Mi az ism´etl´eses k´ od? Mi a h´atr´anya? 139. Ismertesse a k´etdimenzi´os parit´asellen˝orz´est. 140. Defini´ alja a line´ aris k´ od fogalm´at ´es a kapcsol´od´o jel¨ol´eseket. 141. Ismertesse a CRC-t. 142. Defini´ alja a gener´ atorm´atrix, ellen˝orz˝o m´atrix ´es s szindr´oma fogalm´at. 143. Mi a Singleton-korl´ at? 144. Mi az MDS-k´ od ´es mi´ert h´ıvj´ak ´ıgy? 145. Adja meg Reed–Solomon-k´od eset´en a k´odol´ast. 146. Defini´ alja a sz´ am´ıt´ asi elj´ar´as fogalm´at. 147. Defini´ alja a szimul´ al´ ast. 148. Defini´ alja a nagy ord´ ot. 149. Defini´ alja a Turing-g´epet. 150. Defini´ alja Turing-g´ep bemenet´et ´es kimenet´et. 151. Fogalmazza meg a Turing-g´ep egyszalagos g´eppel t¨ort´en˝o szimul´al´as´ara vonatkoz´ o t´etelt. 152. Fogalmazza meg az univerz´alis Turing-g´epekkel kapcsolatban tanult t´etelt. 153. Ismertesse a RAM-g´epet.
154. Fogalmazza meg a Turing-g´ep RAM-g´eppel t¨ort´en˝o szimul´al´as´ara vonatkoz´ o t´etelt. 155. Fogalmazza meg a RAM-g´ep Turing-g´eppel t¨ort´en˝o szimul´al´as´ara vonatkoz´ o t´etelt. 156. Fogalmazza meg a Church–Turing-t´ezist.
