Datastructuren en Algoritmen voor KI was een ontzettend lastig vak. In deze samenvatting staat vooral de informatie van de hoorcolleges. Informatie uit het boek zit erdoor verwerkt, als aanvulling op de hoorcollegestof of dingen waarvan de docent zei dat het echt belangrijk was. Dit is tentamenstof...
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.
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
Voordelen van het kopen van samenvattingen bij Stuvia op een rij:
Verzekerd van kwaliteit door reviews
Stuvia-klanten hebben meer dan 700.000 samenvattingen beoordeeld. Zo weet je zeker dat je de beste documenten koopt!
Snel en makkelijk kopen
Je betaalt supersnel en eenmalig met iDeal, creditcard of Stuvia-tegoed voor de samenvatting. Zonder lidmaatschap.
Focus op de essentie
Samenvattingen worden geschreven voor en door anderen. Daarom zijn de samenvattingen altijd betrouwbaar en actueel. Zo kom je snel tot de kern!
Veelgestelde vragen
Wat krijg ik als ik dit document koop?
Je krijgt een PDF, die direct beschikbaar is na je aankoop. Het gekochte document is altijd, overal en oneindig toegankelijk via je profiel.
Tevredenheidsgarantie: hoe werkt dat?
Onze tevredenheidsgarantie zorgt ervoor dat je altijd een studiedocument vindt dat goed bij je past. Je vult een formulier in en onze klantenservice regelt de rest.
Van wie koop ik deze samenvatting?
Stuvia is een marktplaats, je koop dit document dus niet van ons, maar van verkoper sinievdben. Stuvia faciliteert de betaling aan de verkoper.
Zit ik meteen vast aan een abonnement?
Nee, je koopt alleen deze samenvatting voor €4,49. Je zit daarna nergens aan vast.
