TDT4120 Algoritmer og datastrukturerTilbake

1.P Prøver til del 1: Asymptotisk analyse og rekurrenser

Alle fag for Høyskole

1.P Prøver til del 1: Asymptotisk analyse og rekurrenser

Fire prøver som dekker del 1 (asymptotisk analyse og rekurrenser) på eksamensnivå, med fulle løsningsforslag.

120 min

0 oppgaver

Prøver til del 1Asymptotisk analyserekurrenser

Din fremgang i kapitlet

0 / 0 oppgaver

Kapitlets plass i kurset

Bygger på

1.6DRILL — Rekurrensløsning med navngitt metode

Fire prøver à ~25–35 min: prøve 1.A (25 min), 1.B (30 min), 1.C (30 min) og 1.D (35 min) — 120 minutter i alt. Prøvene kan trygt deles over flere kvelder; én prøve per økt er den rytmen som fungerer best, fordi hver prøve trener én ferdighet ferdig.

Dekning. Asymptotisk notasjon er telt i 17 av de 17 settene i grunnlaget (100 %), ofte med to–tre oppgaver i samme sett. Det er de billigste og sikreste poengene faget har, og derfor får notasjonen to hele prøver: 1.A på definisjonene og klassifiseringen, 1.B på forenklingen. Rekurrenser er telt i 13 av de 17 settene (76 %) og får prøve 1.C. Splitt-og-hersk og binærsøk er telt i 12 av de 17 settene (71 %) og inngår i den blandede prøven 1.D sammen med iterasjons- og substitusjonsmetoden. Alt dette er høyeste prioritet — det må sitte.

Sjangrene du møter her, skrevet ut i klarspråk:

- sjanger A — asymptotisk forenkling: du oppgir ett uttrykk, det strammeste du kan gi, og ikke noe mer.
- sjanger B — rekurrens: du navngir metoden (masterteoremet, iterasjonsmetoden eller substitusjonsmetoden), oppgir svaret på riktig form, og sier hvilket masterteorem-tilfelle du brukte.
- sjanger D — definisjon med egne ord: én presis setning, med hovedpoenget først.
- sjanger F — «stemmer dette?»: ja eller nei først, deretter én setning som begrunner.

Hvor flervalget bor. De statiske flervalgsoppgavene står inline i prøveteksten under, med alternativer merket a)–d) og fasitbokstaven i løsningsforslaget. De interaktive flervalgsspørsmålene — dem du klikker deg gjennom og får rettet automatisk — ligger i quizen til kapitlene i Del 1, ikke her. Bruk prøvene til å skrive svar for hånd; bruk quizen til å pugge fakta.

Én ting om formen. Eksamen i TDT4120 er en firetimers skoleeksamen uten hjelpemidler — NTNU kaller det hjelpemiddelkode E — med rundt 20 korte frisvarsoppgaver som teller likt. Symbolene og masterteoremets tre tilfeller må derfor kunnes utenat. Prøvene her er skrevet i den formen, og løsningsforslagene viser hva som gir uttelling, med delpoeng-notat der oppgaven har flere ledd.

Tidsbudsjett. Minuttallene er arbeidstid med penn og papir. Legger du til lesing av oppgaveteksten og gjennomlesing av eget svar, bruker du i praksis litt mer — det er normalt, og det er nettopp tempoferdigheten eksamen også måler.

Forkunnskaper

Prøvene her hviler på hele Del 1, og på ingenting annet:

- kap. 1.1 — de fem asymptotiske symbolene
- kap. 1.2 — forenkling av asymptotiske uttrykk
- kap. 1.3 — drillen på notasjon og forenkling
- kap. 1.4 — masterteoremet
- kap. 1.5 — iterasjon, substitusjon og splitt-og-hersk
- kap. 1.6 — drillen på rekurrensløsning

Dette er det du trenger å ha friskt før du setter deg ned:

- De fem symbolene er mengder. $O$ er øvre grense, $\Omega$ nedre grense, $\Theta$ begge deler samtidig, $o$ strengt mindre og $\omega$ strengt større. Skrivemåten $f(n) = O(g(n))$ har likhetstegn, men leses « $f$ tilhører mengden $O(g(n))$ ».
- Skillet mellom «for en $c$ » og «for alle $c$ » er hele forskjellen mellom $O$ og $o$ , og mellom $\Omega$ og $\omega$ .
- Standard vekstordning: $1 < \lg n < n < n\lg n < n^2 < n^3 < 2^n < n!$ . Her er $\lg n$ det samme som $\log_2 n$ .
- Masterteoremet gjelder rekurrenser på formen $T(n) = aT(n/b) + f(n)$ med $a \ge 1$ og $b > 1$ , og sammenligner $f(n)$ med $n^{\log_b a}$ . I tilfelle 2 er $f(n) = \Theta(n^{\log_b a}\lg^{k} n)$ med $k \ge 0$ — null er lov.
- Iterasjonsmetoden gir eksakte svar. Blir du bedt om et eksakt uttrykk, skal svaret ikke inneholde asymptotisk notasjon i det hele tatt.
- Antall nivåer i rekursjonstreet til $T(n) = aT(n/b) + f(n)$ er $\Theta(\log_b n)$ .

Har du ikke lest kapitlene ennå, er prøvene fortsatt lesbare — men da leser du dem som fasitskriver, ikke som kandidat.

Prøve 1.A — De fem symbolene og klassifisering (25 min)

Prøve 1.B — Forenkling av sammensatte uttrykk (30 min)

Prøve 1.C — Rekurrenser med masterteoremet (30 min)

Prøve 1.D — Iterasjon, substitusjon og splitt-og-hersk (35 min)

Dette kapitlet er skrevet av Anthropics toppmodeller (Claude Opus og Claude Fable) og er foreløpig ikke manuelt gjennomgått — kvalitetskontrollen gjøres av uavhengige KI-agenter, og innmeldte feil rettes fortløpende. Funnet en feil? Meld fra, så retter vi den. Les mer om hvordan innholdet lages.

Skolesaga er en uavhengig læringsressurs og er ikke tilknyttet eller godkjent av Norges teknisk-naturvitenskapelige universitet. Dette er ikke offisielt studiemateriell. Les mer.