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)?
Les avantages d'acheter des résumés chez Stuvia:
Qualité garantie par les avis des clients
Les clients de Stuvia ont évalués plus de 700 000 résumés. C'est comme ça que vous savez que vous achetez les meilleurs documents.
L’achat facile et rapide
Vous pouvez payer rapidement avec iDeal, carte de crédit ou Stuvia-crédit pour les résumés. Il n'y a pas d'adhésion nécessaire.
Focus sur l’essentiel
Vos camarades écrivent eux-mêmes les notes d’étude, c’est pourquoi les documents sont toujours fiables et à jour. Cela garantit que vous arrivez rapidement au coeur du matériel.
Foire aux questions
Qu'est-ce que j'obtiens en achetant ce document ?
Vous obtenez un PDF, disponible immédiatement après votre achat. Le document acheté est accessible à tout moment, n'importe où et indéfiniment via votre profil.
Garantie de remboursement : comment ça marche ?
Notre garantie de satisfaction garantit que vous trouverez toujours un document d'étude qui vous convient. Vous remplissez un formulaire et notre équipe du service client s'occupe du reste.
Auprès de qui est-ce que j'achète ce résumé ?
Stuvia est une place de marché. Alors, vous n'achetez donc pas ce document chez nous, mais auprès du vendeur sinievdben. Stuvia facilite les paiements au vendeur.
Est-ce que j'aurai un abonnement?
Non, vous n'achetez ce résumé que pour €4,49. Vous n'êtes lié à rien après votre achat.
