Hoofdstuk 5 Algorithms

Redacteuren: Groep 5

Wat is belangrijk?

  • 5.1: The Concept of an Algorithm. Hierin wordt beschreven wat een algoritme is. Er wordt globaal beschreven waar een algoritme aan moet voldoen en wat de grootste fouten zijn die je kunt maken. Verder wordt vermeld dat een algoritme een abstract gegeven is dat los staat van hetgeen dat het presenteert. Zo kan een algortime gepresenteerd worden in verschillende vormen.
  • 5.3: Algorithm Discovery: Helpt bij het leren herkennen van problemen en geeft manieren waarmee problemen kunnen worden opgelost. Voorbeelden zijn '''top-down method''' en '''bottum-up method''' ook heb je nog '''Stepwise refinement'''
  • 5.4: Iterative Structures: Deze paragraaf beschrijft hoe beslissingen en hoe herhalende structuren(iterative structures) in elkaar steken. Bij beslissingen heb je het if commando waarna je de conditie tussen haakjes doet. Gevolg door ‘then’ en soms daarachteraan ‘else’. Er zijn twee soorten herhalende structuren, de ‘While( conditie) do(actie)’ (pretest loop) en de ‘repeat(actie) until(conditie)’ (posttest loop). Het verschil tussen deze is dat je bij de repeat until de actie eerst onderneemt en dan kijkt of je em wil herhalen, bij de while do check je je conditie, en als de conditie true is, herhaal je de actie tot de conditie false wordt. Dit is tevens de termination conditie.
  • 5.5: Recursive Structures: Deze paragraaf gaat over recursive structures en binary search algoritms. Bij recursive structures gaat het erom dat een algoritme naar zichzelf verwijst. Binair zoeken: de lijst halveren en dan één van de twee zijden kiezen.

Wat is onbelangrijk?

  • 5.2: Algorithm Representation. Het eerste deel gaat over de manier van presenteren van een algoritme. In feite gaat het om de "taal" waarin geschreven wordt. Denk hierbij aan een stappenplan of een reeks plaatsen die doorlopen moeten worden. In de computer wetenschap wordt bij het genereren van algoritmes gebruik gemaakt van primitieven, kleine blokjes die samen het algoritme maken. Deze blokjes in combinatie met regels over hoe deze blokjes gecombineerd kunnen worden noemt men de programmeer taal. Een voorbeeld daarvan is de pseudocode.
  • 5.6: Efficiency and Correctness: de sequential search en de binary search worden vergeleken met een voorbeeld. Algoritmen kunnen in formules worden gezet. Verder wordt uitleg gegeven over de software verificatie, het controleren van de software.

Tien beste tentamenvragen (inclusief antwoorden)

  1. Wat is het verschil tussen een programmeertaal en een pseudocode? Antwoord: Een programmeertaal is een set van karakters (woorden, cijfers, symbolen) en grammatica (syntaxis) gebruikt om een binaire code te schrijven die vervolgens als programma kan worden uitgevoerd. Een pseudocode is een soort ruwe schets van een programma waarin de programmeur aangeeft wat zij willen dat de computer gaat doen, maar ze schrijven niet een werkelijke (binaire) code. (Martijn Baas)
  2. Geef een definitie van een algoritme. Antwoord: Een algoritme is een geordende reeks ondubbelzinnige, uitvoerbare stappen die een proces beschrijven. (Gelina Huissen)
  3. Is 'While(conditie)..do(actie)' een pretest- of een posttest loop? Verklaar je antwoord. Antwoord: 'While'(conditie)..do(actie)' is een pretest loop, want er wordt eerst gekeken naar de conditie voordat er een actie wordt uitgevoerd. Pas als deze conditie waar (true) is, wordt de actie uitgevoerd. Bij een 'Repeat(actie)..until(conditie)' wordt de actie eerst uitgevoerd, en wordt daarna pas gekeken of de actie dan wel of niet nogmaals moet worden uitgevoerd. (Hugo de Bruijn)
  4. Wanneer mag een constructie van procedures een constructie van primitieven worden genoemd? Antwoord: Wanneer de procedure zo goed gebouwd is dat deze als bouwsteen kan dienen voor grotere programma structuren zonder aangepast te worden. (Macy Sharoubim)
  5. Wat is stepwise refinement? Gebruik in je antwoord top-down methodology en bottum-up methodology. Antwoord: Een techniek waarbij nooit een hele taak (in alle detail) in één keer wordt uitgevoerd. Het is een top-down methodology wat betekend dat een taak van het algemene naar het specifieke wordt uitgevoerd. Een bottum-up methodology betekend echter dat een taak van het specifieke naar het algemene wordt uitgevoerd. (Michelle Emmen)
  6. Wat is het verschil tussen een pretest en een posttest loop, en wanneer kies je voor de posttest loop? Antwoord: Bij een pretest loop wordt eerst naar de conditie gekeken en bij een posttest loop wordt pas achteraf gekeken of de activiteit herhaald moet worden. De posttest loop gebruik je als je wilt dat de activiteit minstens een keer wordt uitgevoerd. (Laurence van Brenk)
  7. Wat is een 'termination condition' en waarin verschilt deze van de voorwaarde in bijvoorbeeld een while-loop (in bijvoorbeeld Java)? Antwoord: De 'termination condition' is de voorwaarde waaronder de herhaling van de body van een loop stopt. De voorwaarde in bijvoorbeeld een while-loop in bijvoorbeeld Java is de voorwaarde waaronder de body van een loop herhaalt wordt, dit is dus het omgekeerde van de 'termination condition'.(Olav Trauschke)
  8. Hoe werkt Binair zoeken en wat is het voordeel hiervan? Antwoord: Binair zoeken is een methode om een bepaalde waarde te vinden in een verzameling door de af te zoeken verzameling steeds te halveren. Dit heeft als voordeel dat de waarde (als hij niet helemaal in het begin van de lijst staat) veel sneller wordt gevonden dan bij sequential search algoritme, die de lijst van boven naar beneden afgaat. (Erica Wilthagen)
  9. Wat is het verschil tussen “loop paradigm” en “recursion structure”. Antwoord: bij een loop wordt een set instructies uitgevoerd. Als dit compleet is wordt het herhaalt, totdat een bepaalde conditie dit laat stoppen. Ook wel de terminating condition genoemd. Bij een recursion wordt binnen een set instructies, een set instructies herhaald. (Ricky Singh)
  10. Door welk systeem wordt de efficiëntie van algoritmes vergeleken en hoe ziet de notatie van dit systeem eruit? Antwoord: De efficiëntie van algoritmes wordt vergeleken door de big theta notation. Van ieder algoritme kan een grafiek worden gemaakt met als variabelen tijd en hoeveelheid input. De big theta notation bestaat uit de Griekse letter theta met daarachter tussen haakjes de vorm van deze grafiek. Bijvoorbeeld: Θ(n2). (Vincent Stangenberger)

Nieuwe Top 10 Beste Tentamenvragen (Inclusief Antwoorden)

  1. Voldoet het volgende stuk code aan de eisen van een algoritme? (Var = 10; while (Var != 10) do (Var = Var +3); Antwoord: Nee dit stuk voldoet niet aan de eisen van een algoritme, dit komt doordat in geen van de gevallen de Var 10 zal worden waardoor de code oneindig doorloopt. (Ton Koning)
  2. Wat betekenen de volgende algoritmische uitspraken (en beschrijf deze)? if/then/else/while/do. Antwoord: if-statement is een voorwaarde waaraan moet worden voldaan, then-statement wordt uitgevoerd als de if-conditie waar is, else-statement wordt uitgevoerd indien de if-conditie onwaar is, while-statement wordt uitgevoerd zolang de conditie waar is, do-statement voert een opdracht uit. (Martin van Kuik)
  3. Wat is een 'termination condition' en waarin verschilt deze van de voorwaarde in bijvoorbeeld een while-loop (in bijvoorbeeld Java)? Antwoord: De 'termination condition' is de voorwaarde waaronder de herhaling van de body van een loop stopt. De voorwaarde in bijvoorbeeld een while-loop in bijvoorbeeld Java is de voorwaarde waaronder de body van een loop herhaalt wordt, dit is dus het omgekeerde van de 'termination condition'. (Olav Trauschke)
  4. Welke vier fases zijn te onderscheiden bij het oplossen van een probleem? Antwoord: 1. Begrijp het probleem 2. Bedenk een plan of algoritme 3. Voer het plan uit of realiseer het algoritme 4. Beoordeel de oplossing op nauwkeurigheid en kijk of het potentie heeft om andere problemen op te lossen. (Gersom van Ginkel)
  5. Noem een situatie waarin binair zoeken weinig meerwaarde heeft t.o.v. sequentiëel zoeken. Antwoord: Als de te doorzoeken lijst erg kort is, levert binair zoeken amper tijdswinst op. Implementeren van een sequentiële zoekopdracht kan dan een simpelere oplossing zijn. (Gersom van Ginkel)
  6. De volgende pseudocode gebruikt een while statement. Herschrijf de while statement naar een repeat statement. a = 0; b = 0; while (a < 10) do (a = a+b; b = b+1) Antwoord: repeat(a = a+b; b = b+1) until(a=10). (Rutger de Graaf)
  7. Hoe werkt Binair zoeken en wat is het voordeel hiervan? Antwoord: Binair zoeken is een methode om een bepaalde waarde te vinden in een verzameling door de af te zoeken verzameling steeds te halveren. Dit heeft als voordeel dat de waarde (als hij niet helemaal in het begin van de lijst staat) veel sneller wordt gevonden dan bij sequential search algoritme, die de lijst van boven naar beneden afgaat. (Erica Wilthagen)
  8. Wat is het verschil tussen “loop paradigm” en “recursion structure”. Antwoord: bij een loop wordt een set instructies uitgevoerd. Als dit compleet is wordt het herhaalt, totdat een bepaalde conditie dit laat stoppen. Ook wel de terminating condition genoemd. Bij een recursion wordt binnen een set instructies, een set instructies herhaald. (Ricky Singh)
  9. Is 'While(conditie)..do(actie)' een pretest- of een posttest loop? Verklaar je antwoord. Antwoord: 'While'(conditie)..do(actie)' is een pretest loop, want er wordt eerst gekeken naar de conditie voordat er een actie wordt uitgevoerd. Pas als deze conditie waar (true) is, wordt de actie uitgevoerd. Bij een 'Repeat(actie)..until(conditie)' wordt de actie eerst uitgevoerd, en wordt daarna pas gekeken of de actie dan wel of niet nogmaals moet worden uitgevoerd. (Hugo de Bruijn)
  10. Wanneer mag een constructie van procedures een constructie van primitieven worden genoemd? Antwoord: Wanneer de procedure zo goed gebouwd is dat deze als bouwsteen kan dienen voor grotere programma structuren zonder aangepast te worden. (Macy Sharoubim)

Voorgestelde tentamenvragen (inclusief antwoorden)

Niet-redacteuren mogen hier tentamenvragen voorstellen.

  1. Welke vier fases zijn te onderscheiden bij het oplossen van een probleem? Antwoord: 1. Begrijp het probleem 2. Bedenk een plan of algoritme 3. Voer het plan uit of realiseer het algoritme 4. Beoordeel de oplossing op nauwkeurigheid en kijk of het potentie heeft om andere problemen op te lossen. (Gersom van Ginkel)
  2. Noem een situatie waarin binair zoeken weinig meerwaarde heeft t.o.v. sequentiëel zoeken. Antwoord: Als de te doorzoeken lijst erg kort is, levert binair zoeken amper tijdswinst op. Implementeren van een sequentiële zoekopdracht kan dan een simpelere oplossing zijn. (Gersom van Ginkel)
  3. Wat is een opmerkelijke bevinding over de Polya's fases? Antwoord: Dat men vaak met fase 2 begint in plaats van fase 1. Men gaat dus al een plan van aanpak maken terwijl het probleem nog niet helemaal is begrepen. (Sicco Chanier)
  4. Wat gebeurt er als men in fase 2 van de Polya's fases niet slaagt? Antwoord: Men gaat terug naar fase 1, beter begrijpen waar het precieze probleem ligt. (Sicco Chanier)
  5. Wat zijn de verschillen tussen een algoritme, een proces en een programma?Antwoord: Een algoritme is een set van instructies, een programma geeft een algoritme weer op een manier die geschikt is voor applicatie door een computer en een proces is het uitvoeren van een programma. (Carly Hill)
  6. De volgende pseudocode gebruikt een while statement. Herschrijf de while statement naar een repeat statement. a = 0; b = 0; while (a < 10) do (a = a+b; b = b+1)Antwoord: repeat(a = a+b; b = b+1) until(a=10). (Rutger de Graaf)
  7. Om een getal in een lijst met 200 getallen te vinden kun je een binaire zoekopdracht gebruiken. Hoe vaak moet daarbij minimaal en maximaal een element uit die lijst worden opgevraagd? Antwoord: minimaal 1 keer, maximaal 8 keer. (Rutger de Graaf)
  8. Wat betekenen de volgende algoritmische uitspraken (en beschrijf deze)? if/then/else/while/do. Antwoord: if-statement is een voorwaarde waaraan moet worden voldaan, then-statement wordt uitgevoerd als de if-conditie waar is, else-statement wordt uitgevoerd indien de if-conditie onwaar is, while-statement wordt uitgevoerd zolang de conditie waar is, do-statement voert een opdracht uit . (Martin van Kuik)
  9. Geef het verschil tussen het algoritme van een sequentiële zoekmethode en het algoritme van een binaire zoekmethode. Antwoord: Bij een sequentiële zoekmethode wordt er gezocht op volgorde (bv. alfabetisch, woonplaats van een persoon, lengte van een lijst) terwijl een binaire zoekmethode gebruik maakt van het verkleinen van het zoekgebied totdat het gezochte is (bv. het zoeken in een woordenboek). (Martin van Kuik)
  10. Wat is “Stepwise refinement” en waarvoor is het nodig? Antwoord: Stepwise refinement is het opsplitsen van een complexe taak in deeltaken. Het is nodig zodat ontwerpen, implementeren en onderhouden van programma's makkelijker worden. (Safira Wortel)
  11. Sommige programmeertalen gebruiken een interpreter in plaats van een compiler. Wat wordt er door een interpreter gedaan? Antwoord: Door een interpreter wordt een programma per instructie vertaald en uitgevoerd. (Safira Wortel)
  12. Voldoet het volgende stuk code aan de eisen van een algoritme? (Var = 10; while (Var != 10) do (Var = Var +3); Antwoord: Nee dit stuk voldoet niet aan de eisen van een algoritme, dit komt doordat in geen van de gevallen de Var 10 zal worden waardoor de code oneindig doorloopt. (Ton Koning)
  13. Wat is een oneindige loop en wat is een voorkomende reden voor een oneindige loop? Antwoord: Een oneindige loop is een loop die niet uit zichzelf stopt en alleen gestopt kan worden door het programma af te sluiten of de computer te restarten. Een belangrijke reden voor een oneindige loop is het vergeten van het aanpassen van de variable die de loop beheert. (Pierrette Bernadina) //
  14. Wat geeft de volgende code terug? 1 + generator.nextInt(6) //Antwoord: Een random getal tussen de 1 en de 5 (Pierrette Bernadina) //
  15. Wat zijn de 4 eisen waaruit een algoritme moet bestaan? //antwoord: een algoritme bestaat uit stappen die: geordend zijn, eenduidig zijn, uitvoerbaar zijn en die samen een eindig proces definiëren (Rodayna Aaliouli)
  16. Is de volgende pseudocode een algoritme? If student's grade is greater than or equal to 55% print "Passed" else Print "Failed"// antwoord: ja (Rodayna Aaliouli)
  17. Wat is een pseudocode? //Antwoord: Een pseudocode is een notatie systeem waarin ideeën informeel kunnen worden uitgedrukt tijdens het algoritme ontwikkeling proces. (Lakisha Helstone)
  18. Wat is een 'termination condition'? Antwoord: De 'termination condition' is de voorwaarde waaronder de herhaling van de body van een loop stopt. (Lakisha Helstone)
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License