Fundamenten Meerkeuze PDF

Fundamenten Meerkeuze Online studeren bij https://quizlet.com/_b5bh97 1. Een string heeft steeds een eindige lengte. 1 2. Een taal bevat steeds een eindig aantal strings. 0 3. De verzameling van alle strings die gevormd kunnen 1 worden met bepaald alfabet, is...

Fundamenten Meerkeuze Online studeren bij https://quizlet.com/_b5bh97 1. Een string heeft steeds een eindige lengte. 1 2. Een taal bevat steeds een eindig aantal strings. 0 3. De verzameling van alle strings die gevormd kunnen 1 worden met bepaald alfabet, is een taal over dat alfa- bet. 4. Voor eender welke twee talen S en T, regulier of niet, 0 is TS*T een reguliere taal. 5. {a}* bevat oneindig veel strings. 1 6. Niet - deterministische automaten kunnen meer talen 0 herkennen dan deterministische. 7. Niet-deterministische eindige automaten kunnen 0 dezelfde talen herkennen als deterministische, maar som efficiënter in tijd (d.w.z. strings worden soms herkend met minder toestandstransities). 8. Niet-deterministische turingmachines kunnen meer 0 talen herkennen dan deterministische. 9. Als L α T en L is een element van de klasse P, dan 0 geldt steeds T is een element van P. 10. We weten zeker dat P een deelverzameling is van NP 0 en dat NP een deelverzameling is van NPC. 11. We weten zeker dat P een deelverzameling is van NPC 0 en dat NPC een deelverzameling is van NP. 12. Elke vlakke graaf voldoet aan v - e + f = 2 met v 0 het aantal knopen, e het aantal bogen en f het aantal zijvlakken. 13. In een samenhangende graaf bestaat er een pad 1 tussen elke twee knopen. 1 / 16  Fundamenten Meerkeuze Online studeren bij https://quizlet.com/_b5bh97 14. K2,2 is homeomorf met K3. 1 15. Als twee grafen isomorf zijn, hebben ze evenveel 1 knopen. 16. Als twee grafen homeomorf zijn, hebben ze evenveel 0 bogen. 17. Bepalen of een gewogen graaf een Hamiltoniaanse 0 kring met gewicht kleiner dan 100 heeft is zeker in P. 18. Bepalen of een graaf een Eureliaanse kring heeft, is 1 zeker in NP. 19. Bepalen of het korste pad tussen twee gegeven 0 knopen in een gewogen graaf en een gewicht kleiner dan 100, is zeker NP-compleet. 20. Een boom met n knopen heeft steeds n-1 bogen. 1 21. Elke samenhangende graaf heeft precies 1 opspan- 0 nende boom. 22. Het algoritme van Kruskal en het algoritme van Prim 1 zijn twee verschillende manieren om hetzelfde prob- leem op te lossen. 23. Het algoritme van Kruskal en het Algoritme van Prim 0 geven steeds dezelfde uitkomst. 24. Elke boom heeft een twee-kleuring. 1 25. Elke eindige taal is regulier. 1 26. Elke reguliere taal is eindig. 0 27. Elke reguliere taal bevat de lege string. 0 28. De lege taal is een reguliere taal. 1 29. 0 2 / 16  Fundamenten Meerkeuze Online studeren bij https://quizlet.com/_b5bh97 Voor elke reguliere taal L geldt: als x en y een element is van L, dan is xy ook een element van L. 30. Voor elke reguliere taal bestaat er een eindige au- 1 tomaat die die taal herkent. 31. De verzameling van {(ab)^n | n element van de natu- 1 urlijke getallen} is een reguliere taal. 32. De verzameling van {a^m b^n | n,m element van de 1 natuurlijke getallen} is een reguliere taal. 33. De verzameling van {a^n b^n | n element van de 0 natuurlijke getallen} is een reguliere taal. 34. De verzameling van alle wiskundige uitdrukkingen 0 gevormd met +,-,/,x en haakjes is een reguliere taal. 35. De klasse van talen herkend door eindige toestand- 1 sautomaten is dezelfde als de klasse herkend door niet-determinitische eindige automaten. 36. Voor elk java-programma bestaat er een Turningma- 1 chine die voor eender welke input dezelfde output geeft als dat programma. 37. Voor elke binaire booleaanse operator f: BxB ->, met B 1 = {0,1} bestaat er een eindige automaat die f berekent. 38. Voor elke functie f: N -> N bestaat er een eindige 0 automaat die f berekent. 39. Voor elke functie f: N -> N bestaat er een TM die f 0 berekent. 40. Uit de stelling van Cook volgt SAT is een element van 1 NPC 41. Uit de stelling van Cook volgt SAT is geen element 0 van P. 3 / 16  Fundamenten Meerkeuze Online studeren bij https://quizlet.com/_b5bh97 42. ? Het algoritme van Dijkstra heeft complexiteit 0(n^3) 1 (met n het aantal knopen) 43. Het algoritme van Dijkstra is assymptotisch equiva- 0 lent met n^3. (met n het aantal knopen) 44. Het algoritme van Dijkstra kan door een determinis- 1 tische TM uitgevoerd worden. 45. Een graaf met een euleriaanse kring heeft nooit 1 knopen met oneven graad. 46. Elke samenhangende vlakke graaf heeft een Euleri- 0 aanse kring. 47. De tweeledige grafen K3,4 en K4,3 zijn isomorf. 1 48. Elke tweeledige graaf heeft een tweekleuring. 1 49. Elke tweeledige graaf is vlak. 0 50. Elke vlakke graaf heeft een vierkleuring. 1 51. K3,3 is vlak. 0 52. K3,3 heeft een vierkleuring. 1 53. Elke niet-vlakke graaf heeft minstens een kring. 1 54. Uit de stelling van Kuratowski volgt dat elke graaf die 0 geen subgraaf bevat die isomorf is met K5 of K3,3 vlak is. 55. Van elke vlakke graaf kan een boom gemaakt worden 0 door k bogen weg te halen met k het aantal kringen. 56. De tijdscomplexiteit van het algoritme van Prim is 0 linear in het aantal knopen. 57. 0 4 / 16  Fundamenten Meerkeuze Online studeren bij https://quizlet.com/_b5bh97 De tijdscomplexiteit van het algoritme van Prim is linear in het aantal bogen. 58. Om een opspannende boom te hebben moet een 0 graaf samenhangend en vlak zijn. 59. Een eindige taal is steeds regulier. 1 60. Een reguliere taal bevat steeds de lege string. 0 61. Voor elke reguliere taal L en voor elke string s kan in 1 tijd O(n) beslist worden of s is element van L, met n de lengte van s 62. Elke eindige automaat A beslist of s is element van 0 L(A) in een aantal stappen O(m), met m het aantal toestanden van A. 63. De verzameling {a^n b^n | n is element van N} is een 0 reguliere taal over {a,b,c,0,...,9}. 64. Voor elke binaire booleaanse operator f bestaat er 1 een eindige automaat die f berekent. 65. Een graaf met een Euleriaanse kring heeft nooit 1 knopen met oneven graad. 66. Elke graaf met enkel knopen met even graad heeft 0 een Euleriaanse kring. 67. Elke graaf die K5 bevat heeft zeker geen 4-kleuring. 1 68. Elke graaf met minder dan n componenten heeft een 0 n-kleuring. 69. Elke vlakke graaf voldoet aan v - e + f = 2 (met v 0 het aantal knopen, e het aantal bogen, en f het aantal zijvlakken). 70. 1 5 / 16  Fundamenten Meerkeuze Online studeren bij https://quizlet.com/_b5bh97 Bepalen of een graaf een Euleriaanse kring heeft, is zeker in NP 71. Als L1 L2 en L1 P, dan geldt steeds L2 P. 0 72. We weten zeker dat P † NP † NPC. 0 73. Een boom met n knopen heeft steeds n 1 bogen. 1 74. Elke graaf met enkel knopen met even graad heeft 0 een Euleriaanse kring 75. Voor elke reguliere taal L bestaat er een n e N zo dat 0 V s e L : |s| R, is er een constante c element van R, zodat voor alle natuurlijke getallen n geldt dat f(n) < c*g(n) 115. Als f is O(n^3) en n^3 is O(f), dan is f een veel- 0 termfunctie 116. Het aantal knopen met even graad in een graaf is 0 steeds even 117. De buurmatrix van een enkelvoudige graaf heeft op 1 de diagonaal enkel nullen 118. Voor een samenhangende, kringvrije graaf geven het 1 algoritme van Kruskal en dat van Prim gegarandeerd hetzelfde eindresultaat 119. De capaciteit van elke snede is niet kleiner dan een- 1 der welke stroming. 120. Elke monotone operator T heeft de eigenschap dat a 0 een vast punt is als en slechts als T(T(a)) = a 121. Voor elke reguliere taal bestaat er een getal nN zodat 0 alle string in die taal ten hoogste n tekens bevatten 122. Voor elke reguliere taal bestaat er een Turingmachine 1 die de taal herkent 123. NPC is een strikte deelverzameling van NP 1 124. Als L1 L2 en L2 L3, dan geldt L1 L3 1 125. Als twee grafen homeomorf zijn, hebben ze evenveel 0 knopen 9 / 16  Fundamenten Meerkeuze Online studeren bij https://quizlet.com/_b5bh97 126. Een tweeledige graaf kan geen deelgraaf hebben die 1 isomorf is met K3 127. Een vlakke graaf G(V,E) waarvoor v-e+f=2 waar is, is 0 enkelvoudig 128. Een vlakke graaf G(V,E) waarvoor v-e+f=2 waar is, is 1 samenhangend 129. Er bestaat een taal die door geen enkele Turing ma- 1 chine beslist wordt 130. Elke taal die beslist wordt door een algoritme met 1 complexiteit O(n^2), wordt ook beslist door een algo- ritme met complexiteit O(n^3) 131. Een minimaal opspannende boom van een graaf is 1 enkelvoudig 132. Als een graaf een Euleriaans pad heeft, dan is de 0 graaf vlak 133. Elk transportnetwerk heeft een maximale snede 1 134. Op geen enkel complete tralie bestaat een niet-mo- 1 notone continue afbeelding 135. Indien P = NP dan volgt daaruit dat NPC = de lege 0 verzameling 136. De verzameling van alle functies van N naar N is 0 aftelbaar 137. Als L een reguliere taal is en A ‚ L, dan is A ook regulier0 138. Als L een reguliere taal is en L ‚ A, dan is A ook regulier0 139. N bevat niet-aftelbaar veel getallen 0 140. N bevat een niet-aftelbare deelverzameling 0 10 / 16  Fundamenten Meerkeuze Online studeren bij https://quizlet.com/_b5bh97 141. Voor een samenhangende graaf (zonder bogen met 0 unieke gewichten) geven het algoritme van Kruskal en dat van Prim gegarandeerd hetzelfde eindresultaat 142. Eindige talen zijn regulier 1 143. Reguliere talen zijn eindig 0 144. De concatenatie van twee reguliere talen is een reg- 1 uliere taal 145. Elke deelverzameling van een taal is een taal 1 146. Elke deelverzameling V van een reguliere taal R (V † R)0 is een reguliere taal 147. Elke verzameling V die een reguliere taal R omvat (R †0 V ) is een reguliere taal. 148. De verzameling van reguliere expressies over een 0 gegeven alfabet £is zelf een regulieretaal. 149. Voor elke niet-deterministische eindige automaat is 1 er ook een deterministische eindigeautomaat die dezelfde taal herkent. 150. Sommige niet-deterministische eindige automaten 0 herkennen niet-reguliere talen. 151. Als er voor een bepaalde string x £een pad is van de 1 begintoestand naar eenaanvaardbare eindtoestand zodat de concatenatie van de labels van de gevolgde pijlende string x oplevert, dan wordt x aanvaard. 152. Als er voor een bepaalde string x £een pad is van de 0 begintoestand naar eenniet-aanvaardbare eindtoes- tand zodat de concatenatie van de labels van de gevolgdepijlen de string x oplevert, dan wordt x niet aanvaard. 11 / 16  Fundamenten Meerkeuze Online studeren bij https://quizlet.com/_b5bh97 153. Er bestaan niet-deterministische eindige automat- 1 en zonder »- pijlen en zonder meer-dere pijlen vanuit dezelfde toestand met hetzelfde label, die toch geen deterministischeeindige automaten zijn. 154. Er zijn oneindig veel Turingmachines. 1 155. Het aantal Turingmachines met n toestanden en m 0 symbolen is eindig. 156. f is O(g) Ò n N: f (n) d g(n) 0 157. f is O(n^2) en g is ook O(n^2) Ò f g is O(n^4). 1 158. f is O(g) Ò f is O(g + h). 1 159. g : N ’ R+ : n 7 ’ f (n + 1) is asymptotisch equivalent met0 f. 160. Als f en g asymptotisch equivalent zijn en h is O(g), 1 dan zijn f en g + h asymptotischequivalent. 161. f is niet O(g) Ò g is O(f ). 0 162. Als f asymptotisch equivalent is met n^2, dan is f een 0 veeltermfunctie. 163. De partieel geordende verzameling L, d met L het ges-1 loten interval [a, b] ) Z, is eencomplete tralie. 164. De partieel geordende verzameling L, d met L het ges-0 loten interval [a, b] ) Q is eencomplete tralie. 165. De partieel geordende verzameling L, d met L het ges-1 loten interval [a, b] ) R is eencomplete tralie 166. De partieel geordende verzameling L, d met L het open1 interval ]a, b[ ) N is een com-plete tralie. 167. 0 12 / 16  Fundamenten Meerkeuze Online studeren bij https://quizlet.com/_b5bh97 De partieel geordende verzameling L, d met L het open interval ]a, b[ ) R is een com-plete tralie. 168. Er zijn talen die in polynomiale tijd door een NDTM 1 beslist worden maar waarvoor geen DTM bestaat die de taal in polynomiale tijd beslist. (Als P != NP) 169. Er zijn talen die in polynomiale tijd door een NDTM 0 beslist worden maar waarvoor geen DTM bestaat die de taal in polynomiale tijd beslist. (Als P = NP) 170. Het aantal bogen in een graaf is steeds de helft van 1 de som van de graden. 171. De som van de graden van alle knopen in een graaf 1 is steeds even. 172. Het aantal knopen met oneven graad in een graaf is 1 altijd even. 173. Een graaf G heeft een Euleriaanse kring als en slechts 1 als de graaf samenhangend is en elke knoop een even graad heeft. 174. Een graaf G heeft een Euleriaans pad als en slechts 1 als de graaf samenhangend is en hoogstens 2 knopen een oneven graad hebben 175. Twee enkelvoudige grafen zijn isomorf als en slechts 1 als er een ordening van de knopen bestaat zodat hun buurmatrix gelijk is. 176. Twee grafen G en G' zijn isomorf als en slechts als 1 er een ordening van de knopen en bogen bestaat waarvoor de incidentiematrices van G en G' gelijk zijn. 177. Een enkelvoudige graaf G(V,E) is tweeledig als 1 en slechts als V kan opgedeeld worden in twee 13 / 16  Fundamenten Meerkeuze Online studeren bij https://quizlet.com/_b5bh97 deelverzamelingen V1 en V2, zo dat er enkel bogen bestaan tussen V1 en V2 maar nooit binnen V1 of V2. 178. Een enkelvoudige graaf G(V,E) is tweeledig als 0 en slechts als V kan opgedeeld worden in twee deelverzamelingen V1 en V2, zo dat er enkel bogen bestaan binnen V1 en V2 maar nooit tussen V1 of V2. 179. Het aantal turing machines met n toestanden en m 1 symbolen is eindig (op naamgeving na) 180. Voor een gegeven alfabet £geldt dat de klasse van de 1 reguliere talen op £precies samenvalt met de klasse van de reguliere verzamelingen. 181. Voor elke reguliere taal L bestaat er een n, zo dat, voor 1 elke string s element van L met |s| >= n, het volgende geldt: er bestaan strings x, y, z zo dat s = xyz met |y| > 0, |xy|