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
The benefits of buying summaries with Stuvia:
Guaranteed quality through customer reviews
Stuvia customers have reviewed more than 700,000 summaries. This how you know that you are buying the best documents.
Quick and easy check-out
You can quickly pay through credit card or Stuvia-credit for the summaries. There is no membership needed.
Focus on what matters
Your fellow students write the study notes themselves, which is why the documents are always reliable and up-to-date. This ensures you quickly get to the core!
Frequently asked questions
What do I get when I buy this document?
You get a PDF, available immediately after your purchase. The purchased document is accessible anytime, anywhere and indefinitely through your profile.
Satisfaction guarantee: how does it work?
Our satisfaction guarantee ensures that you always find a study document that suits you well. You fill out a form, and our customer service team takes care of the rest.
Who am I buying these notes from?
Stuvia is a marketplace, so you are not buying this document from us, but from seller sinievdben. Stuvia facilitates payment to the seller.
Will I be stuck with a subscription?
No, you only buy these notes for $4.88. You're not tied to anything after your purchase.
