100% satisfaction guarantee Immediately available after payment Both online and in PDF No strings attached
logo-home
Datastructuren tentamen 1 $4.81
Add to cart

Class notes

Datastructuren tentamen 1

1 review
 439 views  10 purchases
  • Course
  • Institution
  • Book

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...

[Show more]

Preview 4 out of 35  pages

  • May 16, 2018
  • 35
  • 2017/2018
  • Class notes
  • Unknown
  • All classes

1  review

review-writer-avatar

By: philippineolphen • 3 year ago

avatar-seller
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

The benefits of buying summaries with Stuvia:

Guaranteed quality through customer reviews

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

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

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.81. You're not tied to anything after your purchase.

Can Stuvia be trusted?

4.6 stars on Google & Trustpilot (+1000 reviews)

53068 documents were sold in the last 30 days

Founded in 2010, the go-to place to buy study notes for 14 years now

Start selling
$4.81  10x  sold
  • (1)
Add to cart
Added