Hoofdstuk 12 Theory of Computation

Redacteuren: Groep 12

Wat is belangrijk?

  • 12.1 Het is belangrijk om te weten wat de grenzen van een computer zijn.
  • 12.2 Je moet weten dat functies binair omgezet worden en kunnen worden.
  • 12.3 Je moet verschillende programmeertalen kennen, maar hoeft ze niet toe te passen.
  • 12.5 Je moet verschillende problemen begrijpen en beoordelen.
  • 12.6 Je moet weten wat voor verschillende sleutels er zijn en wat ze inhouden.

Wat is onbelangrijk?

  • 12.4 Voorbeelden van problemen die onoplosbaar zijn.

De nieuwe tien beste tentamenvragen (inclusief antwoorden)

  1. Waarvoor staat NP-problem? Antwoord: Nondeterministic polynomial problem (Sicco Chanier)
  2. Het RSA algoritme heeft zijn naam te danken aan zijn 3 bekende bedenkers. Wie waren dat? (Enkel de achternamen zijn voldoende) Antwoord: R.Rivest, A.Shamir, L.Adleman (Sicco Chanier)
  3. Leg uit wat een universal programming language karakteriseert. Antwoord: Met deze taal zijn alle berekenbare problemen op te lossen. Wanneer dit in de toekomst niet zou lukken, kan je stellen dat er geen algoritme voor dit probleem is te vinden. (Gersom van Ginkel)
  4. Leg uit wat time complexity is. Antwoord: Hierbij meet je de complexiteit van een probleem aan de hand van de tijd die het berekenen van iedere mogelijke oplossing kost. (Gersom van Ginkel)
  5. Wat is een functie in zijn wiskundige betekenis? Antwoord: Een overeenstemming tussen een collectie van mogelijke input waardes en een collectie van output waardes, zo dat elke mogelijke input één output toegekend krijgt. (Rolien Lucker)
  6. Welke collectie van problemen wordt gerepresenteerd met de letter “P”? Antwoord: Polynomial problemen. (Rolien Lucker)
  7. Wat zijn computable en noncomputable functions? Antwoord: Computable functions zijn functies waarvan hun output algoritmisch berekend kan worden door middel van de input. Noncomputable functions zijn funcites waarvan de berekening te moeilijk is om algoritmisch op te lossen.(Tijmen Henrich)
  8. Berekeningen(computions) van een turing machine bevat een aantal stappen die uitgevoerd worden door de control unit, welke stappen? Antwoord: Observatie van een karakter in een "tape cell", een karakter plaatsen in deze "tape cell", verplaatsen van de "Read/Write cell", en het veranderen van "States".(Tijmen Henrich)
  9. Geef een korte omschrijving van het stopprobleem (beter bekend als 'halting problem')? Antwoord: Dit is het probleem of het wel mogelijk is vast te stellen of een algoritme bij een eindige invoer eindigt in een eindig aantal stappen of eindeloos blijft doorgaan. (Martin van Kuik)
  10. Wat wordt er bedoeld met de Θ, ook wel de big O notation genoemd? Antwoord: Daarmee wordt aangegeven wat men weet over de complexiteit van een probleem. (Martin van Kuik)

Voorgestelde tentamenvragen (inclusief antwoorden)

Niet-redacteuren mogen hier tentamenvragen voorstellen.

  1. Waarvoor staat NP-problem? Antwoord: Nondeterministic polynomial problem (Sicco Chanier)
  2. Het RSA algoritme heeft zijn naam te danken aan zijn 3 bekende bedenkers. Wie waren dat? (Enkel de achternamen zijn voldoende) Antwoord: R.Rivest, A.Shamir, L.Adleman (Sicco Chanier)
  3. Leg uit wat een universal programming language karakteriseert. Antwoord: Met deze taal zijn alle berekenbare problemen op te lossen. Wanneer dit in de toekomst niet zou lukken, kan je stellen dat er geen algoritme voor dit probleem is te vinden. (Gersom van Ginkel)
  4. Leg uit wat time complexity is. Antwoord: Hierbij meet je de complexiteit van een probleem aan de hand van de tijd die het berekenen van iedere mogelijke oplossing kost. (Gersom van Ginkel)
  5. Wat is een functie in zijn wiskundige betekenis? Antwoord: Een overeenstemming tussen een collectie van mogelijke input waardes en een collectie van output waardes, zo dat elke mogelijke input één output toegekend krijgt. (Rolien Lucker)
  6. Welke collectie van problemen wordt gerepresenteerd met de letter “P”? Antwoord: Polynomial problemen. (Rolien Lucker)
  7. Wat zijn computable en noncomputable functions? Antwoord: Computable functions zijn functies waarvan hun output algoritmisch berekend kan worden door middel van de input. Noncomputable functions zijn funcites waarvan de berekening te moeilijk is om algoritmisch op te lossen.(Tijmen Henrich)
  8. Berekeningen(computions) van een turing machine bevat een aantal stappen die uitgevoerd worden door de control unit, welke stappen? Antwoord: Observatie van een karakter in een "tape cell", een karakter plaatsen in deze "tape cell", verplaatsen van de "Read/Write cell", en het veranderen van "States".(Tijmen Henrich)
  9. Geef een korte omschrijving van het stopprobleem (beter bekend als 'halting problem')? Antwoord: Dit is het probleem of het wel mogelijk is vast te stellen of een algoritme bij een eindige invoer eindigt in een eindig aantal stappen of eindeloos blijft doorgaan. (Martin van Kuik)
  10. Wat wordt er bedoeld met de Θ, ook wel de big O notation genoemd? Antwoord: Daarmee wordt aangegeven wat men weet over de complexiteit van een probleem. (Martin van Kuik)
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License