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...
Je kan de runtme an recursie e algoritmen analyseren. Recursie e algoritmen roepen telkens
opnieuw een methode aan.
Recursi iteit: het optreden an constructe als onderdeel an de identeke soort constructe . en
erschillen doorgaans in waarde. Je herhaalt als het ware een constructee e roept hem opnieuw
aan. Om een gege en probleem op te lossen, roepen algoritmen zichzelf opnieuw aan om zo om te
kunnen gaan met gerelateerde subproblemen. Dit is een di ide-and-conquer benadering: het
probleem wordt opgebroken in subproblemen die li ken op het originele probleem maar dan kleiner.
ls e de oplossingen an de subproblemen combineert heb e de oplossing oor het gehele originele
probleem.
In de informate is er een methode waar de oplossing an een probleem afangt an de oplossingen
an kleinere identeke problemen. Dus geen iteratee
We willen weten hoe eel t d een zeker recursief algoritme kost als functe an in oergroote n.
- Te berekenen door ‘operatess tellen? Je weet niet hoe eel een recursie e aanroep koste
Het optellen an doubles
Torens an Hanoi
R is de rand oorwaarde/basis/bodem
,V is de oortgangs ergeli king
Recurrente betrekking:
Defnieert de waarde an de functe in termen an de functewaardenn oor kleinere parameters.
Ieder getal uit de ri hangt af an zi n directe oorganger en dus indirect an al zi n oorgangers. De
Fibonacci ri is hier een goed oorbeeld an.
De oplossing an een recurrente betrekking geef de waarde rechtstreeks, dus niet in termen an
andere functewaarden.
Een recurrente betrekking exact oplossen
Soms werkt ‘guess and pro es. Dit kun e dus proberen te gokken en er olgens te bewi zen met
inducte.
Voor Merge-Sort kun e dit niet exact oplossen
,Recurrente betrekkingen asymptotscc oplossen
ls e asymptotsch ki kt, negeer e bepaalde aspecten.
- De rand oorwaarde is meestal niet belangri k
- fronden bi delen is niet belangri ke asymptotsch geef dit hetzelfde resultaat
- De waarde an constanten in extra termen is niet belangri k
- Maar: constanten an recursie zi n heel belangri keee Het maakt natuurli k een erschil hoe
aak e de recursie ingaat.
3 metcodes:
Substtutemethode
Je gokt het uiste antwoord en e bewi st dat dit klopt. Dit doe e op een asymptotsche manier, want
de constanten ind e in e bewi s.
Recursieboom
Een analyse an een recursieboom. Dit kun e gebruiken om e ‘guesss te ormen. Je ki kt hoe eel
werk er per ni eau wordt uitge oerd.
Master methode
Voor een speciale orm an een recurrente betrekking
T ( n )=a x T ¿
Maximum subarray probleem
Recursieboom
- Ga per in oer n een ast aantal a keer in recursie
- Op een in oer die een aste fracte /b an de in oer n is
- Doe per ni eau nog fnn werk oor het combineren
, Dan kri g e een recurrente betrekking: T ( n )=a x T ¿
Een recursieboom helpt deze op te lossen door de waarde an Tnn uit te drukken als:
Zie oorbeeld Merge-sort op papiere
Construeren recursieboom: elke knoop representeert de t d die nodig is oor het oplossen an een
deelprobleem op een bepaald ni eau
- In de knoop staat de t d oor het erdelen en combineren fnn
- Tel daarbi op de t d oor a deelproblemen an om ang n/b op een ni eau dieper
- epaal de rekent d recursief totdat e op het ni eau an problemen an om ang bent
gekomen: Tn = fn
i Merge sort: de input op ni eau i is n/2 i, want input n is i keer door 2 gedeeld.
Wanneer is n/2i = ?
- 2i=n
- i = 2 log n = lg n
Er is erdubbeling op elk ni eau an de knopen. Dus het aantal knopen op het laagste ni eau is 2 lg n =
n.
Dus wat is M(n)?
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.81. You're not tied to anything after your purchase.
