Datastructuren
De rest staat opgeschreven op een kladblok.
College 1
Hoe sla je data op in je programma?
Bv: Arrays
Het verschil tussen een list en een array is dat in een list verschillende types kunnen ziten maar in
een array moet het per se hetzelfde type zijn.
‘A data structure is a way to store and organize data in order to facilitate access and modifcatonss
- De manier waarop je je data opslaat heef consequentes voor het gemak waarmee je
bepaalde operates erop kunt uitvoeren. Zo kan je programma sneller of langzamer worden
of juist heel ingewikkeld.
Geen enkele datastructuur werkt goed voor alle data, dus moet je goed kijken met wat voor data je
te maken hebt. Datastructuren zijn er om dingen snel uit te rekenen.
Lineair zoeken: bij het begin beginnen en doorgaan tot het eind of tot je x hebt gevonden.
Voorbeld:
Een algoritme is abstract, niet hetzelfde als een implementate.
,Belangrijk van een datastructuur:
1. Slimme manier om gegevens op te slaan
2. Helpt het algoritme sneller te maken
3. Datastructuren bestaan voor het opslaan van verschillende gegevens.
Algoritmische vragen:
- Sorteren van rij getallen
- Wiskundige stellingen bewijzen
- Oplossen logische puzzels
- Kortste route routeplanner
- Advertentes selecteren
Belangrijke vragen:
1. Is het algoritme correct? (geef bewijs, bijvoorbeeld door de invariant)
2. Hoe lang duurt het? (gemeten in stappen en gebruik O-notate)
3. Hoeveel geheugen gebruikt het?
Als je kan bewijzen of een while-loop invariant is, dan blijf een uitspraak altjd waar.
Hoe lang duurt het?
1. In het slechtste geval n vergelijkingen
2. In het beste geval 1 vergelijking
3. Gemiddeld: n/2 vergelijkingen ; als x erbij zit en het hangt ervan af hoevaak x erbij zit.
Binary search
Een zoekalgoritme dat de posite van een doelwaarde vindt in een gesorteerde array. Halverwege de
gesorteerde array beginnen met zoeken.
Je bekijk het middelste element.
1. Als x kleiner is dan gooi je de rechterhelf weg.
2. Als x groter is gooi je de linkerhelf weg.
3. De groote van de lijst wordt dus constant gehalveerd(ongeveer).
,Bewijs voor de correctheid van een algoritme
Een invariant is een eigenschap P(i) van een loop zodanig dat:
- Initialisatie: P aanvankelijk het geval is: dus P(0) is waar
- Maintenance: als de invariant geldt voor een iterate k, dan geldt de invariant ook na de
iterate dus voor k ꆠ 1(maar niet noodzakelijk tjdens de stap!): (P(k) B) P(kꆠ1)
- Termination: als het itereren stopt, dus wanneer de condite niet meer geldt, P(n) kan
gebruikt worden om de correctheid van het algoritme te bewijzen: (P(n)C) correctheid
Het proces van de wite en de zwarte knikkers eindigt omdat je er telkens 1 uithaalt. Het is dus niet
oneindig. De wite knikkers zullen door de opgestelde regels altjd in een oneven aantal blijven en
dus nooit bij 0 uitkomen; desda als er 1 knikker overblijf is dit de wite.
Oefenen met algoritmes en de
invarianten vinden:
, College 2
Algoritme A
Gegeneraliseerd beeld van een datastructuur
Bewijzen met inducte
De rest staat opgeschreven op een kladblok.
College 1
Hoe sla je data op in je programma?
Bv: Arrays
Het verschil tussen een list en een array is dat in een list verschillende types kunnen ziten maar in
een array moet het per se hetzelfde type zijn.
‘A data structure is a way to store and organize data in order to facilitate access and modifcatonss
- De manier waarop je je data opslaat heef consequentes voor het gemak waarmee je
bepaalde operates erop kunt uitvoeren. Zo kan je programma sneller of langzamer worden
of juist heel ingewikkeld.
Geen enkele datastructuur werkt goed voor alle data, dus moet je goed kijken met wat voor data je
te maken hebt. Datastructuren zijn er om dingen snel uit te rekenen.
Lineair zoeken: bij het begin beginnen en doorgaan tot het eind of tot je x hebt gevonden.
Voorbeld:
Een algoritme is abstract, niet hetzelfde als een implementate.
,Belangrijk van een datastructuur:
1. Slimme manier om gegevens op te slaan
2. Helpt het algoritme sneller te maken
3. Datastructuren bestaan voor het opslaan van verschillende gegevens.
Algoritmische vragen:
- Sorteren van rij getallen
- Wiskundige stellingen bewijzen
- Oplossen logische puzzels
- Kortste route routeplanner
- Advertentes selecteren
Belangrijke vragen:
1. Is het algoritme correct? (geef bewijs, bijvoorbeeld door de invariant)
2. Hoe lang duurt het? (gemeten in stappen en gebruik O-notate)
3. Hoeveel geheugen gebruikt het?
Als je kan bewijzen of een while-loop invariant is, dan blijf een uitspraak altjd waar.
Hoe lang duurt het?
1. In het slechtste geval n vergelijkingen
2. In het beste geval 1 vergelijking
3. Gemiddeld: n/2 vergelijkingen ; als x erbij zit en het hangt ervan af hoevaak x erbij zit.
Binary search
Een zoekalgoritme dat de posite van een doelwaarde vindt in een gesorteerde array. Halverwege de
gesorteerde array beginnen met zoeken.
Je bekijk het middelste element.
1. Als x kleiner is dan gooi je de rechterhelf weg.
2. Als x groter is gooi je de linkerhelf weg.
3. De groote van de lijst wordt dus constant gehalveerd(ongeveer).
,Bewijs voor de correctheid van een algoritme
Een invariant is een eigenschap P(i) van een loop zodanig dat:
- Initialisatie: P aanvankelijk het geval is: dus P(0) is waar
- Maintenance: als de invariant geldt voor een iterate k, dan geldt de invariant ook na de
iterate dus voor k ꆠ 1(maar niet noodzakelijk tjdens de stap!): (P(k) B) P(kꆠ1)
- Termination: als het itereren stopt, dus wanneer de condite niet meer geldt, P(n) kan
gebruikt worden om de correctheid van het algoritme te bewijzen: (P(n)C) correctheid
Het proces van de wite en de zwarte knikkers eindigt omdat je er telkens 1 uithaalt. Het is dus niet
oneindig. De wite knikkers zullen door de opgestelde regels altjd in een oneven aantal blijven en
dus nooit bij 0 uitkomen; desda als er 1 knikker overblijf is dit de wite.
Oefenen met algoritmes en de
invarianten vinden:
, College 2
Algoritme A
Gegeneraliseerd beeld van een datastructuur
Bewijzen met inducte
