Halveren zonder randfout
De geordende array is [2, 4, 7, 9, 13, 18, 25, 31]. Gebruik [l,r).
- aVolg binair zoeken naar 13 en naar 8. Geef l, r en m na elke stap.
- bFormuleer de invariant en verklaar waarom m+1 nodig is in de rechterhelft.
EExpert · deel E7 · Informatica
Werkboek · hoofdstuk 34Algoritmen en complexiteit
Een correct programma wordt pas bruikbaar als zijn werk binnen het budget past
Je begint met bewerkingen tellen, bewijst daarna algoritmen en ontwerpt tot slot een controleerbare routeplanner.
Hoe lees je een opdracht?
Drie tredenOefenen Toepassen Uitdagen
Elk hoofdstuk bouwt op: eerst oefenen (één stap, direct toepassen), dan toepassen (meerdere stappen, in een context), dan uitdagen (transfer, open problemen, andere leerlijnen erbij).
De StemExpert-schaal5
Eén moeilijkheidsschaal van 1 tot 9 over de drie niveaus heen: Fundamental loopt van 1 tot 4, Intermediate van 3 tot 7, Expert van 6 tot 9. Zo zie je dat de uitdaging van het ene niveau de oefening van het volgende is.
Oefenen
Oefenen
één stap, direct toepassenGroeiklasse kiezen
Een programma doet stappen; een ander .
- aGeef de scherpste O-klasse en leg uit waarom één tijdmeting de klasse niet bewijst.
Verschuivingen tellen
Invoegsorteren krijgt 1000 records in omgekeerde volgorde.
- aBereken het aantal verschuivingen en de verhouding tot 2000 records.
Toepassen
Toepassen
meerdere stappen, in een contextEen zoekfunctie schrijven
Schrijf zelf binair zoeken; de uitvoer is de eerste index bij dubbele sleutels.
- aGeef code of precieze pseudocode en tests voor lege lijst, één element, afwezig en [2,2,2].
Een recursie herstellen
Faculteit wordt recursief gedefinieerd met alleen n == 1 als basisgeval.
- aToon waarom n = 0 faalt; herstel het contract en beschrijf tijd en geheugen.
Een blokkade in de kaart
Gebruik de volledige graaf uit het handboek. De kant C–D is geblokkeerd.
- aBereken de nieuwe route Laad–E en rijtijd bij 0,20 m/s. Leg uit waarom een groot gewicht minder goed is dan verwijderen.
Uitdagen
Uitdagen
transfer, open problemen, leerlijnen combinerenEen eerlijke tijdmeting
Je vergelijkt twee sorteerders op een laptop.
- aOntwerp een meetprotocol dat invoervorm, n, herhalingen en geheugen omvat. Geef een analyse die toevallige ruis van groei onderscheidt.
Zo wordt dit beoordeeld
| reproduceerbaarheid | Vaste invoer, omgeving, ruwe tijden en script. |
|---|---|
| interpretatie | Groei en spreiding afzonderlijk besproken. |
Een routeplanner met terugweg
De voorbeeldgraaf heeft meetpunten A, C en E. De robot moet terug naar Laad. Elke meting kost 5 s; een beurt mag 120 s duren.
- aBereken een korte ronde en totaalduur; ontwerp het contract tussen Pi-planner en robot en de reactie op obstakels of netwerkuitval.
Zo wordt dit beoordeeld
| berekening | Afstand, meettijd en reserve gescheiden. |
|---|---|
| correctheid | Alle meetpunten en terugweg gecontroleerd. |
| veilig gedrag | Actuele blokkades en communicatieverlies begrensd. |
Een negatieve energiekant
Bij afdalen zou een robot energie terugwinnen. Iemand voert negatieve kantgewichten in Dijkstra in.
- aVerklaar het probleem en geef twee bruikbare alternatieven, inclusief een beperking.
ZelfevaluatieKleur per doel: lukt al / bijna / nog niet
- Ik kan lineair en binair zoeken uitvoeren en hun voorwaarden verklaren.
- Ik kan sorteeralgoritmen vergelijken met een bewerkingsmodel en O-notatie.
- Ik kan recursieve functies volgen en een basisgeval en voortgang bewijzen.
- Ik kan Dijkstra uitvoeren en een pad reconstrueren.
- Ik kan een algoritme kiezen op basis van tijd, geheugen en worst-case eisen.