Læringsmål

Oversikt over læringsmål dekket i TDT4120 Algoritmer og datastrukturer

Kilde: Læringsmålene er utformet av Skolesaga på grunnlag av emnets eksamensoppgaver, sensorveiledninger og emnebeskrivelse. De er ikke institusjonens offisielle læringsutbyttebeskrivelser.

166 kompetansemål45 av 45 kapitler har kompetansemål

Alle kompetansemål

•kunne gjøre rede for eksamensformen i TDT4120 og hva hjelpemiddelkode E betyr for hvordan du forbereder deg
0.1Eksamenskartet — slik testes TDT4120
•kunne bruke temafrekvensene til å prioritere lesingen, og forklare hvorfor ingen del av pensum kan velges bort
0.1Eksamenskartet — slik testes TDT4120
•kunne kjenne igjen de ni oppgavetypene og si hvilken svarform hver av dem krever
0.1Eksamenskartet — slik testes TDT4120
•kunne legge en realistisk leseplan ut fra tiden du faktisk har
0.1Eksamenskartet — slik testes TDT4120
•kunne skrive ned de formelle definisjonene av $O$, $\Omega$, $\Theta$, $o$ og $\omega$ uten hjelpemidler
1.1Asymptotisk notasjon — de fem symbolene
•kunne avgjøre hvilke av de fem symbolene som gjelder mellom to gitte funksjoner, og begrunne svaret med konkrete verdier for $c$ og $n_0$
1.1Asymptotisk notasjon — de fem symbolene
•kunne rangere standardfunksjonene etter vekst og bruke rangeringen til å velge det strammeste symbolet
1.1Asymptotisk notasjon — de fem symbolene
•kunne forklare hva likhetstegnet i $f(n) = O(g(n))$ betyr, og hvorfor påstanden ikke kan snus
1.1Asymptotisk notasjon — de fem symbolene
•kunne forenkle en sum av asymptotiske ledd til det strammeste enkeltuttrykket
1.2Forenkling av asymptotiske uttrykk
•kunne oppgi nedre og øvre grense hver for seg når ett uttrykk ikke fanger begge
1.2Forenkling av asymptotiske uttrykk
•kunne avgjøre når et ledd fjerner den øvre grensen for hele uttrykket
1.2Forenkling av asymptotiske uttrykk
•kunne løse et sammensatt brøkuttrykk ledd for ledd ved å bytte teller og nevner med sin ekstremverdi
1.2Forenkling av asymptotiske uttrykk
•kunne skrive ned de formelle definisjonene av O, Omega, Theta, o og omega med konstantene c og n_0, uten hjelpemidler
1.3DRILL — Asymptotisk forenkling og notasjon
•kunne klassifisere en konkret funksjon mot en oppgitt sammenligningsfunksjon ved hjelp av forholdstesten
1.3DRILL — Asymptotisk forenkling og notasjon
•kunne forenkle en sum av asymptotiske ledd til det strammeste enkeltuttrykket, og avgjøre når summen mangler øvre grense
1.3DRILL — Asymptotisk forenkling og notasjon
•kunne regne ut et sammensatt brøk- og produktuttrykk ledd for ledd ved å sette inn ekstremverdier i teller og nevner
1.3DRILL — Asymptotisk forenkling og notasjon
•kunne lese av a, b og f(n) fra en rekurrens og regne ut sammenligningsuttrykket n opphoeyd i logaritmen til a med grunntall b
1.4Rekurrenser — masterteoremet
•kunne velge riktig tilfelle i masterteoremet og oppgi svaret med riktig antall logaritmefaktorer
1.4Rekurrenser — masterteoremet
•kunne sjekke regularitetsbetingelsen i tilfelle 3 og skrive begrunnelsen paa en linje
1.4Rekurrenser — masterteoremet
•kunne avgjoere naar en rekurrens faller utenfor masterteoremet, og si hvorfor
1.4Rekurrenser — masterteoremet
•kunne løse en rekurrens med iterasjonsmetoden og oppgi et eksakt uttrykk, ikke en asymptotisk grense
1.5Rekurrenser — iterasjon, substitusjon og splitt-og-hersk
•kunne verifisere et gjettet svar med substitusjonsmetoden ved å føre induksjonssteget
1.5Rekurrenser — iterasjon, substitusjon og splitt-og-hersk
•kunne sette opp rekurrensen til en splitt-og-hersk-algoritme og si hvor mange nivåer rekursjonstreet har
1.5Rekurrenser — iterasjon, substitusjon og splitt-og-hersk
•kunne velge riktig metode ut fra hva oppgaven ber om, og navngi metoden i svaret
1.5Rekurrenser — iterasjon, substitusjon og splitt-og-hersk
•kunne avgjøre på ett blikk hvilken av de tre metodene en gitt rekurrens skal løses med
1.6DRILL — Rekurrensløsning med navngitt metode
•kunne løse en rekurrens med masterteoremet og oppgi hvilket tilfelle som gjelder, inkludert riktig antall logaritmefaktorer
1.6DRILL — Rekurrensløsning med navngitt metode
•kunne kjenne igjen en rekurrens som faller utenfor pensumvarianten av masterteoremet, og si hvorfor
1.6DRILL — Rekurrensløsning med navngitt metode
•kunne definere de fem asymptotiske symbolene presist med begge konstantene, og avgjøre om en gitt funksjon tilhører en gitt klasse
1.PPrøver til del 1: Asymptotisk analyse og rekurrenser
•kunne forenkle et sammensatt asymptotisk uttrykk til det strammeste enkeltuttrykket, også når det inneholder en brøk eller blandede operatorer
1.PPrøver til del 1: Asymptotisk analyse og rekurrenser
•kunne løse en rekurrens med masterteoremet, oppgi hvilket av de tre tilfellene som gjelder, og se når rekurrensen faller utenfor teoremet
1.PPrøver til del 1: Asymptotisk analyse og rekurrenser
•kunne velge mellom iterasjon, substitusjon og masterteoremet, og levere svaret på den formen oppgaven ber om — eksakt eller asymptotisk
1.PPrøver til del 1: Asymptotisk analyse og rekurrenser
•kunne gjengi beste, verste og forventet kjøretid for de fire sammenligningsbaserte sorteringene, og si hvilken input som utløser hvert tilfelle
2.1Sammenligningsbaserte sorteringer
•kunne forklare hva en løkkeinvariant er, og bruke den til å begrunne at en sortering faktisk sorterer
2.1Sammenligningsbaserte sorteringer
•kunne sette opp rekurrensen for en splitt-og-hersk-sortering og løse den med masterteoremet
2.1Sammenligningsbaserte sorteringer
•kunne begrunne hvorfor ingen sortering som bare sammenligner elementer kan komme under n ganger lg n i verste tilfelle
2.1Sammenligningsbaserte sorteringer
•kunne definere hva det vil si at en sortering er stabil, og avgjøre om en gitt sortering er det
2.2Lineær sortering og stabilitet
•kunne oppgi kravene `Counting-Sort` stiller til nøklene, og kjøretiden som følger av dem
2.2Lineær sortering og stabilitet
•kunne forklare hvorfor `Radix-Sort` bryter sammen hvis delsorteringen ikke er stabil
2.2Lineær sortering og stabilitet
•kunne begrunne hvorfor lineær sortering ikke er i strid med den nedre grensen for sammenligningssortering
2.2Lineær sortering og stabilitet
•kunne håndkjøre `Partition` med siste element som pivot og oppgi arrayet og pivotens sluttindeks
2.3Utvelgelse — Partition, Randomized-Select og Select
•kunne forklare hvorfor utvelgelse kan gjøres i lineær tid mens sortering ikke kan det
2.3Utvelgelse — Partition, Randomized-Select og Select
•kunne skille forventet fra garantert kjøretid for de to utvelgelsesalgoritmene, og oppgi begge riktig
2.3Utvelgelse — Partition, Randomized-Select og Select
•kunne håndkjøre `Counting-Sort` og `Partition` mekanisk og levere nøyaktig det svarformatet oppgaven ber om
2.4DRILL — Sortering: håndkjøring, kjøretid og kombinasjon
•kunne hente fram kjøretiden til hver av de sju sorteringene med riktig skille mellom beste, verste og forventet
2.4DRILL — Sortering: håndkjøring, kjøretid og kombinasjon
•kunne avgjøre hvilken rekkefølge to sorteringer må kjøres i for at totalen skal bli så billig som mulig, og begrunne det
2.4DRILL — Sortering: håndkjøring, kjøretid og kombinasjon
•kunne oppgi beste, verste og forventede kjøretid for de sju sorteringene i delen, og si hvilke av dem som er stabile og hvilke som sorterer på stedet
2.PPrøver til del 2: Sortering og utvelgelse
•kunne håndkjøre Counting-Sort og Partition på et array med indeks fra 1, og levere nøyaktig den sluttilstanden oppgaven ber om
2.PPrøver til del 2: Sortering og utvelgelse
•kunne avgjøre når lineær sortering er mulig, og begrunne hvorfor den nedre grensen for sammenligningsbasert sortering ikke rammer den
2.PPrøver til del 2: Sortering og utvelgelse
•kunne skille en forventet kjøretid fra en garantert, og bruke skillet riktig på Quicksort, Randomized-Select og Select
2.PPrøver til del 2: Sortering og utvelgelse
•kunne regne ut forelder- og barneindeksene i en maks-haug som ligger som array med indeks fra 1, og avgjøre om et gitt array oppfyller haugegenskapen
3.1Hauger og Heapsort
•kunne håndkjøre siving, bygging, uthenting av maksimum og sortering med haug, og oppgi sluttilstanden som hele arrayet
3.1Hauger og Heapsort
•kunne begrunne hvorfor det å bygge en maks-haug tar lineær tid og ikke n ganger lg n, ved å telle arbeidet nivå for nivå
3.1Hauger og Heapsort
•kunne gjengi kjøretidene og egenskapene til haugoperasjonene, inkludert at haugsortering går på stedet og ikke er stabil
3.1Hauger og Heapsort
•kunne avgjøre om et gitt tre oppfyller søketreegenskapen, og skille den fra haugegenskapen
3.2Binære søketrær
•kunne sette inn en rekke nøkler i et tomt søketre for hånd og oppgi inorder-utskriften
3.2Binære søketrær
•kunne gjengi kjøretidene til søketreoperasjonene som funksjoner av høyden, og si når høyden blir lineær
3.2Binære søketrær
•kunne utføre Build-Max-Heap, Heap-Extract-Max og en Heapsort-iterasjon for hånd på et gitt array, og oppgi sluttilstanden i det formatet oppgaven ber om
3.3DRILL — Håndkjøring av hauger og BST
•kunne bygge et binært søketre ved innsetting i gitt rekkefølge og lese av inorder-utskriften, minimum og maksimum
3.3DRILL — Håndkjøring av hauger og BST
•kunne utføre en haugoperasjon mekanisk også når arrayet ikke oppfyller haugegenskapen, uten å reparere det først
3.3DRILL — Håndkjøring av hauger og BST
•kunne holde haugregelen og søketreregelen adskilt, og kontrollere et svar mot begge
3.3DRILL — Håndkjøring av hauger og BST
•kunne sette inn nøkler i en hashtabell med kjeding ved hjelp av divisjonsmetoden, og lese av innholdet i hver bøtte
3.4Hashing
•kunne definere kollisjon, kjeding og lastfaktor med egne ord, og regne ut lastfaktoren for en gitt tabell
3.4Hashing
•kunne oppgi forventet og verste søketid med kjeding, med antakelsen som kreves for forventningen
3.4Hashing
•kunne begrunne hva som gjør en hashfunksjon god, og hvorfor valget av antall bøtter betyr noe
3.4Hashing
•kunne håndkjøre en sirkulær FIFO-kø og oppgi hele tabellen med døde celler pluss head og tail
3.5Køer, stakker, amortisert analyse og disjunkte mengder
•kunne forklare hva amortisert kjøretid betyr, og hvorfor en dobling gir amortisert konstant innsetting
3.5Køer, stakker, amortisert analyse og disjunkte mengder
•kunne kjøre `Union` og `Find-Set` med rangheuristikk for hånd og oppgi hvilke mengder som finnes til slutt
3.5Køer, stakker, amortisert analyse og disjunkte mengder
•kunne håndkjøre Build-Max-Heap, Heap-Extract-Max og Heapsort på et array med indeks fra 1, og levere sluttilstanden i det formatet eksamen ber om
3.PPrøver til del 3: Datastrukturer: hauger, søketrær og hashing
•kunne håndkjøre Tree-Insert og Inorder-Tree-Walk, og bruke at inorder-utskriften er sortert som kontroll på eget svar
3.PPrøver til del 3: Datastrukturer: hauger, søketrær og hashing
•kunne skille haugegenskapen fra søketre-egenskapen, og oppgi kjøretidene for begge strukturene med riktig valg av notasjon
3.PPrøver til del 3: Datastrukturer: hauger, søketrær og hashing
•kunne håndkjøre hashing med kjeding, en FIFO-kø med wraparound og en sekvens av Union-operasjoner, og levere hele tilstanden
3.PPrøver til del 3: Datastrukturer: hauger, søketrær og hashing
•kunne velge mellom nabomatrise og naboliste ut fra hvor tett grafen er, og begrunne valget med plassforbruk og kjøretid
4.1Grafrepresentasjon, traversering og topologisk sortering
•kunne kjøre `BFS` og `DFS` for hånd og oppgi avstander, discover- og finish-tider og kantklassifiseringen
4.1Grafrepresentasjon, traversering og topologisk sortering
•kunne finne en topologisk sortering av en rettet asyklisk graf ved synkende finish-tid, og forklare hvorfor det virker
4.1Grafrepresentasjon, traversering og topologisk sortering
•kunne avgjøre om en rettet graf har en sykel ved hjelp av dybde-først-søk, og oppgi kjøretiden
4.1Grafrepresentasjon, traversering og topologisk sortering
•kunne definere spenntre og minimalt spenntre, og avgjøre om en gitt kantmengde er et spenntre
4.2Minimale spenntrær — Prim og Kruskal
•kunne formulere snittegenskapen med betingelsen om at snittet respekterer valgene, og forklare hva en trygg kant er
4.2Minimale spenntrær — Prim og Kruskal
•kunne kjøre `MST-Kruskal` og `MST-Prim` for hånd og oppgi kantene i den rekkefølgen de velges
4.2Minimale spenntrær — Prim og Kruskal
•kunne begrunne kjøretiden $O(E\lg V)$ for begge algoritmene, og si hvilket steg som dominerer
4.2Minimale spenntrær — Prim og Kruskal
•kunne slakke en kant for hånd og gjøre rede for hva d- og pi-verdiene står for underveis
4.3Korteste vei fra én kilde — Dijkstra, Bellman-Ford, DAG
•kunne velge riktig algoritme for korteste vei fra én kilde ut fra om grafen har negative kantvekter og om den er syklusfri
4.3Korteste vei fra én kilde — Dijkstra, Bellman-Ford, DAG
•kunne oppgi kjøretiden til Dijkstra, Bellman-Ford og DAG-Shortest-Path og begrunne hver av dem i én setning
4.3Korteste vei fra én kilde — Dijkstra, Bellman-Ford, DAG
•kunne håndkjøre Dijkstra og Bellman-Ford og levere d-verdien for hver node i eksamensformatet
4.3Korteste vei fra én kilde — Dijkstra, Bellman-Ford, DAG
•kunne utføre én runde av `Floyd-Warshall` for hånd og oppdatere både avstandsmatrisen og forgjengermatrisen
4.4Alle-til-alle korteste vei
•kunne regne ut en celle i min-pluss-produktet og forklare hvorfor det ikke er vanlig matriseprodukt
4.4Alle-til-alle korteste vei
•kunne velge riktig algoritme for alle-til-alle korteste vei ut fra grafens tetthet og fortegnet på kantvektene
4.4Alle-til-alle korteste vei
•kunne kjøre `Kruskal` mekanisk og oppgi kantene i den rekkefølgen de legges til, med de forkastede merket
4.5DRILL — Håndkjøring av grafalgoritmer
•kunne føre `BFS` og `DFS` på papir og lese av avstander, discover- og finish-tider og en topologisk rekkefølge
4.5DRILL — Håndkjøring av grafalgoritmer
•kunne utføre én runde av `Floyd-Warshall` og ett min-pluss-produkt uten å blande sammen reglene
4.5DRILL — Håndkjøring av grafalgoritmer
•kunne håndkjøre BFS og DFS på en graf gitt som nabolister, og utlede en topologisk sortering fra synkende finish-tid
4.PPrøver til del 4: Grafalgoritmer: traversering, spenntrær og korteste vei
•kunne håndkjøre MST-Kruskal og formulere snittegenskapen med betingelsen som gjør den sann
4.PPrøver til del 4: Grafalgoritmer: traversering, spenntrær og korteste vei
•kunne velge riktig algoritme for korteste vei fra én kilde ut fra kravene grafen stiller, og oppgi kjøretiden for hver av dem
4.PPrøver til del 4: Grafalgoritmer: traversering, spenntrær og korteste vei
•kunne håndkjøre Floyd-Warshall for en gitt runde og regne ut en celle med min-pluss-produktet i Slow-APSP
4.PPrøver til del 4: Grafalgoritmer: traversering, spenntrær og korteste vei
•kunne avgjøre om en gitt tildeling av tall til kantene er en lovlig flyt, og lese av flytverdien
5.1Flytnett, restnett og snitt
•kunne bygge restnettet til en flyt med ryggkantene, og finne en forøkende sti med flaskehals
5.1Flytnett, restnett og snitt
•kunne regne ut snittkapasitet og snittflyt for et gitt snitt, og bruke et snitt som øvre grense for flytverdien
5.1Flytnett, restnett og snitt
•kunne forklare hva heltallsteoremet garanterer, og hvorfor det gjør maks-flyt brukbart til tilordning
5.1Flytnett, restnett og snitt
•kunne kjøre Ford-Fulkerson-metoden for hånd og oppgi både maksimal flytverdi og et min-snitt
5.2Ford-Fulkerson, Edmonds-Karp og maks-flyt/min-snitt
•kunne forklare hva maks-flyt/min-snitt-teoremet sier, og bruke det til å bevise at en flyt er maksimal
5.2Ford-Fulkerson, Edmonds-Karp og maks-flyt/min-snitt
•kunne skille pseudopolynomisk fra polynomisk, og si hvorfor Edmonds-Karp er polynomisk mens den generelle metoden ikke er det
5.2Ford-Fulkerson, Edmonds-Karp og maks-flyt/min-snitt
•kunne kjøre `Edmonds-Karp` for hånd, føre restnettet underveis og oppgi både flytverdi og min-snitt
5.3DRILL — Håndkjøring av maks-flyt og flyt-modellering
•kunne kjenne igjen et fordelingsproblem som maks-flyt og et barriereproblem som min-snitt
5.3DRILL — Håndkjøring av maks-flyt og flyt-modellering
•kunne bygge flytnettet i en modelleringsoppgave og lese tildelingen ut av den ferdige flyten
5.3DRILL — Håndkjøring av maks-flyt og flyt-modellering
•kunne definere restkapasitet, restnett, forøkende sti og snitt presist, og regne ut snittkapasitet og nettoflyt for et gitt snitt
5.PPrøver til del 5: Maksimal flyt
•kunne håndkjøre Edmonds-Karp og levere både maksimal flytverdi og et minimalt snitt, med restnettet tegnet ferdig
5.PPrøver til del 5: Maksimal flyt
•kunne forklare hvorfor Ford-Fulkerson er pseudopolynomisk mens Edmonds-Karp er polynomisk, uten å blande det med NP-hardhet
5.PPrøver til del 5: Maksimal flyt
•kunne modellere et fordelings- eller barriereproblem som maksimal flyt, og rekonstruere selve løsningen fra flyten eller fra snittet
5.PPrøver til del 5: Maksimal flyt
•kunne avgjøre om et problem har optimal substruktur og overlappende delproblemer, og dermed om dynamisk programmering er riktig verktøy
6.1Dynamisk programmering — mekanikk
•kunne skrive den samme rekurrensen både som memoisert rekursjon og som tabellutfylling nedenfra og opp, og begrunne at de har samme asymptotiske kjøretid
6.1Dynamisk programmering — mekanikk
•kunne hente ut selve løsningen og ikke bare optimalverdien, ved å lagre valgene underveis, og forklare hvorfor det ikke øker kjøretiden
6.1Dynamisk programmering — mekanikk
•kunne skille et avgjørelsesproblem fra et optimeringsproblem og oversette mellom de to variantene av samme problem
6.1Dynamisk programmering — mekanikk
•kunne sette opp rekurrensen og grunntilfellene for stavkapping, lengste felles delsekvens og 0-1-ryggsekk ved å se på ett valg om gangen
6.2DP-klassikere — stavkapping, LCS og ryggsekk
•kunne fylle en DP-tabell for hånd og lese av både optimalverdien og selve løsningen fra de lagrede valgene
6.2DP-klassikere — stavkapping, LCS og ryggsekk
•kunne begrunne kjøretidene og forklare hvorfor 0-1-ryggsekkens uttrykk er pseudopolynomisk og ikke polynomisk
6.2DP-klassikere — stavkapping, LCS og ryggsekk
•kunne gjenkjenne et sekvens- eller utvalgsproblem i ny innpakning og peke på hvilken av de tre malene som passer
6.2DP-klassikere — stavkapping, LCS og ryggsekk
•kunne kjenne igjen et problem som løses med dynamisk programmering, og definere delproblemet presist
6.3DRILL — DP-design og rekonstruksjon
•kunne skrive rekurrensen med grunntilfeller og oppgi fylleorden og kjøretid
6.3DRILL — DP-design og rekonstruksjon
•kunne rekonstruere selve løsningen fra lagrede valg, og begrunne at det ikke øker den asymptotiske kjøretiden
6.3DRILL — DP-design og rekonstruksjon
•kunne bygge et Huffman-tre fra gitte frekvenser og oppgi kodelengden for hvert tegn
6.4Grådighet — Huffman og aktivitetsutvelgelse
•kunne begrunne hvorfor det å velge aktiviteten som slutter først gir flest mulig aktiviteter
6.4Grådighet — Huffman og aktivitetsutvelgelse
•kunne forklare et bytteargument, altså at et lokalt valg kan inngå i en optimal løsning
6.4Grådighet — Huffman og aktivitetsutvelgelse
•kunne avgjøre når grådighet virker, og når problemet i stedet krever dynamisk programmering
6.4Grådighet — Huffman og aktivitetsutvelgelse
•kunne definere et blokkerende par og avgjøre om en gitt matching er stabil
6.5Stabil matching — Gale-Shapley
•kunne kjøre `Gale-Shapley` for hånd og oppgi den ferdige matchingen sammen med hvilken orientering som ble kjørt
6.5Stabil matching — Gale-Shapley
•kunne avgjøre om to bestemte parter kan være paret i en stabil matching, ved å kjøre begge orienteringene
6.5Stabil matching — Gale-Shapley
•kunne avgjøre om et problem har overlappende delproblemer og optimal substruktur, og begrunne valget mellom memoisering og utfylling nedenfra og opp
6.PPrøver til del 6: Dynamisk programmering, grådighet og stabil matching
•kunne sette opp en DP-rekurrens med grunntilfeller, fylle tabellen og hente ut selve løsningen fra lagrede beslutninger
6.PPrøver til del 6: Dynamisk programmering, grådighet og stabil matching
•kunne bygge et Huffman-tre fra frekvenser og oppgi kodelengden per tegn og totalt antall bits
6.PPrøver til del 6: Dynamisk programmering, grådighet og stabil matching
•kunne kjøre Gale-Shapley i begge orienteringer og avgjøre om en gitt matching har et blokkerende par
6.PPrøver til del 6: Dynamisk programmering, grådighet og stabil matching
•kunne definere klassene P og NP presist, og forklare at NP handler om å verifisere et foreslått svar raskt, ikke om å finne det
7.1P, NP og co-NP — sertifikat og verifikasjon
•kunne oppgi et sertifikat og en verifikasjonsalgoritme for et konkret problem og begrunne at verifikasjonen er polynomisk
7.1P, NP og co-NP — sertifikat og verifikasjon
•kunne skille et avgjørelsesproblem fra et optimeringsproblem og skrive om fra det ene til det andre med en terskelverdi
7.1P, NP og co-NP — sertifikat og verifikasjon
•kunne gjøre rede for hva som er kjent og hva som er åpent om forholdet mellom P, NP og co-NP
7.1P, NP og co-NP — sertifikat og verifikasjon
•kunne forklare hva en polynomisk reduksjon er, og hvilke tre krav den må oppfylle
7.2Polynomiske reduksjoner og reduksjonsretning
•kunne avgjøre hvilken vei en reduksjon må gå for å vise at et problem er vanskelig, og si hva den motsatte veien beviser
7.2Polynomiske reduksjoner og reduksjonsretning
•kunne skille NP-hardt fra NP-komplett, og pseudopolynomisk fra polynomisk
7.2Polynomiske reduksjoner og reduksjonsretning
•kunne skrive den formelle definisjonen av CIRCUIT-SAT, SAT, 3-CNF-SAT, CLIQUE, VERTEX-COVER, HAM-CYCLE, TSP og SUBSET-SUM som avgjørelsesproblemer
7.3NP-komplette problemer
•kunne forklare hovedideen i at CIRCUIT-SAT er NP-komplett, altså at kretsen simulerer verifikasjonsalgoritmen og at sertifikatet er kretsens input
7.3NP-komplette problemer
•kunne skille CLIQUE fra VERTEX-COVER på både ulikhetstegn og hva kravet gjelder
7.3NP-komplette problemer
•kunne bruke reduksjonskjeden til å forklare hvordan et nytt problem vises NP-komplett, og hvilke to deler et slikt bevis alltid har
7.3NP-komplette problemer
•kunne avgjøre hvilken vei en reduksjon må gå for å vise at et problem er vanskelig, og skrive retningen presist
7.4DRILL — Reduksjonsretning og NP-argumenter
•kunne skille de tre påstandene i NP, NP-hardt og NP-komplett, og vite hvilket bevis hver av dem krever
7.4DRILL — Reduksjonsretning og NP-argumenter
•kunne vurdere om et ferdig NP-argument holder, ved å kontrollere polynomisk konstruksjonstid, lovlig instans og svarbevaring begge veier
7.4DRILL — Reduksjonsretning og NP-argumenter
•kunne skille en pseudopolynomisk kjøretid fra et utsagn om at problemet er vanskelig
7.4DRILL — Reduksjonsretning og NP-argumenter
•kunne definere P, NP og co-NP presist, og forklare hva et sertifikat og en verifikasjonsalgoritme er
7.PPrøver til del 7: NP-kompletthet og reduksjoner
•kunne avgjøre hvilken vei en reduksjon må gå for å vise at et problem er vanskelig, og si hva den ikke beviser
7.PPrøver til del 7: NP-kompletthet og reduksjoner
•kunne definere de navngitte NP-komplette problemene som avgjørelsesproblemer og skille NP-hardt fra NP-komplett
7.PPrøver til del 7: NP-kompletthet og reduksjoner
•kunne skille en pseudopolynomisk kjøretid fra et NP-hardhetsargument
7.PPrøver til del 7: NP-kompletthet og reduksjoner
•kunne avgjøre hva en eksamensoppgave faktisk ber om, og levere svaret i den formen oppgaven krever
8.1Kortsvarssjangeren — å skrive presise, korte svar
•kunne skrive en definisjon der hovedpoenget står i første setning, slik at et avbrutt svar likevel gir uttelling
8.1Kortsvarssjangeren — å skrive presise, korte svar
•kunne budsjettere fire timer over tjue likt vektede oppgaver, og vite når en oppgave skal forlates
8.1Kortsvarssjangeren — å skrive presise, korte svar
•kunne skrive om et langt og upresist utkast til det korte svaret som treffer ferdigheten oppgaven tester
8.1Kortsvarssjangeren — å skrive presise, korte svar
•kunne kjenne igjen hvilket klassisk problem en innpakket oppgave egentlig er, og navngi paradigmet eksplisitt
8.2DRILL — Åpen algoritmedesign via reduksjon
•kunne bygge konstruksjonen — nettet, rekurrensen eller grafen — og oppgi kjøretiden i problemets egne størrelser
8.2DRILL — Åpen algoritmedesign via reduksjon
•kunne rekonstruere selve løsningen og ikke bare optimalverdien, og si at det ikke øker kjøretiden
8.2DRILL — Åpen algoritmedesign via reduksjon
•kunne gjennomføre et komplett firetimers kortsvarssett på egen hånd og kjenne igjen hvilken svarform hver oppgave krever
8.3Øvingseksamen 1 — bredt ordinært sett (kode E)
•kunne gi det strammeste asymptotiske uttrykket for en kjøretidsfunksjon og navngi metoden du løser en rekurrens med
8.3Øvingseksamen 1 — bredt ordinært sett (kode E)
•kunne håndkjøre en maks-haug og korteste vei fra én kilde, og levere sluttilstanden i det formatet eksamen ber om
8.3Øvingseksamen 1 — bredt ordinært sett (kode E)
•kunne skrive en åpen designbesvarelse som navngir paradigmet, rekonstruerer selve løsningen og oppgir en begrunnet kjøretid
8.3Øvingseksamen 1 — bredt ordinært sett (kode E)
•kunne håndkjøre Build-Max-Heap, Tree-Insert, MST-Kruskal og Floyd-Warshall feilfritt og levere sluttilstanden i den formen oppgaven ber om
8.4Øvingseksamen 2 — datastruktur- og graftungt sett
•kunne føre en FIFO-kø i et array gjennom en operasjonssekvens med wraparound og oppgi hele tabellen med begge pekerne
8.4Øvingseksamen 2 — datastruktur- og graftungt sett
•kunne avgjøre hvilken vei en reduksjon må gå for å vise at et nytt problem er vanskelig, og si hva den ikke beviser
8.4Øvingseksamen 2 — datastruktur- og graftungt sett
•kunne modellere et tilordningsproblem som maksimal flyt og hente ut selve tilordningen, ikke bare flytverdien
8.4Øvingseksamen 2 — datastruktur- og graftungt sett
•kunne gjennomføre et komplett firetimers sett på tid, uten hjelpemidler, med riktig svarform i hver sjanger
8.5Øvingseksamen 3 — designtungt topp-sett
•kunne skrive fem fullstendige designsvar med alle de fem obligatoriske leddene, inkludert rekonstruksjonen
8.5Øvingseksamen 3 — designtungt topp-sett
•kunne argumentere for reduksjonsretning tre ganger på rad uten å snu pilen
8.5Øvingseksamen 3 — designtungt topp-sett

Kapitler med kompetansemål

0Eksamenskart

0.1Eksamenskartet — slik testes TDT4120
  • kunne gjøre rede for eksamensformen i TDT4120 og hva hjelpemiddelkode E betyr for hvordan du forbereder deg
  • kunne bruke temafrekvensene til å prioritere lesingen, og forklare hvorfor ingen del av pensum kan velges bort
  • kunne kjenne igjen de ni oppgavetypene og si hvilken svarform hver av dem krever
  • kunne legge en realistisk leseplan ut fra tiden du faktisk har

1Asymptotisk analyse og rekurrenser

1.1Asymptotisk notasjon — de fem symbolene
  • kunne skrive ned de formelle definisjonene av $O$, $\Omega$, $\Theta$, $o$ og $\omega$ uten hjelpemidler
  • kunne avgjøre hvilke av de fem symbolene som gjelder mellom to gitte funksjoner, og begrunne svaret med konkrete verdier for $c$ og $n_0$
  • kunne rangere standardfunksjonene etter vekst og bruke rangeringen til å velge det strammeste symbolet
  • kunne forklare hva likhetstegnet i $f(n) = O(g(n))$ betyr, og hvorfor påstanden ikke kan snus
1.2Forenkling av asymptotiske uttrykk
  • kunne forenkle en sum av asymptotiske ledd til det strammeste enkeltuttrykket
  • kunne oppgi nedre og øvre grense hver for seg når ett uttrykk ikke fanger begge
  • kunne avgjøre når et ledd fjerner den øvre grensen for hele uttrykket
  • kunne løse et sammensatt brøkuttrykk ledd for ledd ved å bytte teller og nevner med sin ekstremverdi
1.3DRILL — Asymptotisk forenkling og notasjon
  • kunne skrive ned de formelle definisjonene av O, Omega, Theta, o og omega med konstantene c og n_0, uten hjelpemidler
  • kunne klassifisere en konkret funksjon mot en oppgitt sammenligningsfunksjon ved hjelp av forholdstesten
  • kunne forenkle en sum av asymptotiske ledd til det strammeste enkeltuttrykket, og avgjøre når summen mangler øvre grense
  • kunne regne ut et sammensatt brøk- og produktuttrykk ledd for ledd ved å sette inn ekstremverdier i teller og nevner
1.4Rekurrenser — masterteoremet
  • kunne lese av a, b og f(n) fra en rekurrens og regne ut sammenligningsuttrykket n opphoeyd i logaritmen til a med grunntall b
  • kunne velge riktig tilfelle i masterteoremet og oppgi svaret med riktig antall logaritmefaktorer
  • kunne sjekke regularitetsbetingelsen i tilfelle 3 og skrive begrunnelsen paa en linje
  • kunne avgjoere naar en rekurrens faller utenfor masterteoremet, og si hvorfor
1.5Rekurrenser — iterasjon, substitusjon og splitt-og-hersk
  • kunne løse en rekurrens med iterasjonsmetoden og oppgi et eksakt uttrykk, ikke en asymptotisk grense
  • kunne verifisere et gjettet svar med substitusjonsmetoden ved å føre induksjonssteget
  • kunne sette opp rekurrensen til en splitt-og-hersk-algoritme og si hvor mange nivåer rekursjonstreet har
  • kunne velge riktig metode ut fra hva oppgaven ber om, og navngi metoden i svaret
1.6DRILL — Rekurrensløsning med navngitt metode
  • kunne avgjøre på ett blikk hvilken av de tre metodene en gitt rekurrens skal løses med
  • kunne løse en rekurrens med masterteoremet og oppgi hvilket tilfelle som gjelder, inkludert riktig antall logaritmefaktorer
  • kunne kjenne igjen en rekurrens som faller utenfor pensumvarianten av masterteoremet, og si hvorfor
1.PPrøver til del 1: Asymptotisk analyse og rekurrenser
  • kunne definere de fem asymptotiske symbolene presist med begge konstantene, og avgjøre om en gitt funksjon tilhører en gitt klasse
  • kunne forenkle et sammensatt asymptotisk uttrykk til det strammeste enkeltuttrykket, også når det inneholder en brøk eller blandede operatorer
  • kunne løse en rekurrens med masterteoremet, oppgi hvilket av de tre tilfellene som gjelder, og se når rekurrensen faller utenfor teoremet
  • kunne velge mellom iterasjon, substitusjon og masterteoremet, og levere svaret på den formen oppgaven ber om — eksakt eller asymptotisk

2Sortering og utvelgelse

2.1Sammenligningsbaserte sorteringer
  • kunne gjengi beste, verste og forventet kjøretid for de fire sammenligningsbaserte sorteringene, og si hvilken input som utløser hvert tilfelle
  • kunne forklare hva en løkkeinvariant er, og bruke den til å begrunne at en sortering faktisk sorterer
  • kunne sette opp rekurrensen for en splitt-og-hersk-sortering og løse den med masterteoremet
  • kunne begrunne hvorfor ingen sortering som bare sammenligner elementer kan komme under n ganger lg n i verste tilfelle
2.2Lineær sortering og stabilitet
  • kunne definere hva det vil si at en sortering er stabil, og avgjøre om en gitt sortering er det
  • kunne oppgi kravene `Counting-Sort` stiller til nøklene, og kjøretiden som følger av dem
  • kunne forklare hvorfor `Radix-Sort` bryter sammen hvis delsorteringen ikke er stabil
  • kunne begrunne hvorfor lineær sortering ikke er i strid med den nedre grensen for sammenligningssortering
2.3Utvelgelse — Partition, Randomized-Select og Select
  • kunne håndkjøre `Partition` med siste element som pivot og oppgi arrayet og pivotens sluttindeks
  • kunne forklare hvorfor utvelgelse kan gjøres i lineær tid mens sortering ikke kan det
  • kunne skille forventet fra garantert kjøretid for de to utvelgelsesalgoritmene, og oppgi begge riktig
2.4DRILL — Sortering: håndkjøring, kjøretid og kombinasjon
  • kunne håndkjøre `Counting-Sort` og `Partition` mekanisk og levere nøyaktig det svarformatet oppgaven ber om
  • kunne hente fram kjøretiden til hver av de sju sorteringene med riktig skille mellom beste, verste og forventet
  • kunne avgjøre hvilken rekkefølge to sorteringer må kjøres i for at totalen skal bli så billig som mulig, og begrunne det
2.PPrøver til del 2: Sortering og utvelgelse
  • kunne oppgi beste, verste og forventede kjøretid for de sju sorteringene i delen, og si hvilke av dem som er stabile og hvilke som sorterer på stedet
  • kunne håndkjøre Counting-Sort og Partition på et array med indeks fra 1, og levere nøyaktig den sluttilstanden oppgaven ber om
  • kunne avgjøre når lineær sortering er mulig, og begrunne hvorfor den nedre grensen for sammenligningsbasert sortering ikke rammer den
  • kunne skille en forventet kjøretid fra en garantert, og bruke skillet riktig på Quicksort, Randomized-Select og Select

3Datastrukturer: hauger, søketrær og hashing

3.1Hauger og Heapsort
  • kunne regne ut forelder- og barneindeksene i en maks-haug som ligger som array med indeks fra 1, og avgjøre om et gitt array oppfyller haugegenskapen
  • kunne håndkjøre siving, bygging, uthenting av maksimum og sortering med haug, og oppgi sluttilstanden som hele arrayet
  • kunne begrunne hvorfor det å bygge en maks-haug tar lineær tid og ikke n ganger lg n, ved å telle arbeidet nivå for nivå
  • kunne gjengi kjøretidene og egenskapene til haugoperasjonene, inkludert at haugsortering går på stedet og ikke er stabil
3.2Binære søketrær
  • kunne avgjøre om et gitt tre oppfyller søketreegenskapen, og skille den fra haugegenskapen
  • kunne sette inn en rekke nøkler i et tomt søketre for hånd og oppgi inorder-utskriften
  • kunne gjengi kjøretidene til søketreoperasjonene som funksjoner av høyden, og si når høyden blir lineær
3.3DRILL — Håndkjøring av hauger og BST
  • kunne utføre Build-Max-Heap, Heap-Extract-Max og en Heapsort-iterasjon for hånd på et gitt array, og oppgi sluttilstanden i det formatet oppgaven ber om
  • kunne bygge et binært søketre ved innsetting i gitt rekkefølge og lese av inorder-utskriften, minimum og maksimum
  • kunne utføre en haugoperasjon mekanisk også når arrayet ikke oppfyller haugegenskapen, uten å reparere det først
  • kunne holde haugregelen og søketreregelen adskilt, og kontrollere et svar mot begge
3.4Hashing
  • kunne sette inn nøkler i en hashtabell med kjeding ved hjelp av divisjonsmetoden, og lese av innholdet i hver bøtte
  • kunne definere kollisjon, kjeding og lastfaktor med egne ord, og regne ut lastfaktoren for en gitt tabell
  • kunne oppgi forventet og verste søketid med kjeding, med antakelsen som kreves for forventningen
  • kunne begrunne hva som gjør en hashfunksjon god, og hvorfor valget av antall bøtter betyr noe
3.5Køer, stakker, amortisert analyse og disjunkte mengder
  • kunne håndkjøre en sirkulær FIFO-kø og oppgi hele tabellen med døde celler pluss head og tail
  • kunne forklare hva amortisert kjøretid betyr, og hvorfor en dobling gir amortisert konstant innsetting
  • kunne kjøre `Union` og `Find-Set` med rangheuristikk for hånd og oppgi hvilke mengder som finnes til slutt
3.PPrøver til del 3: Datastrukturer: hauger, søketrær og hashing
  • kunne håndkjøre Build-Max-Heap, Heap-Extract-Max og Heapsort på et array med indeks fra 1, og levere sluttilstanden i det formatet eksamen ber om
  • kunne håndkjøre Tree-Insert og Inorder-Tree-Walk, og bruke at inorder-utskriften er sortert som kontroll på eget svar
  • kunne skille haugegenskapen fra søketre-egenskapen, og oppgi kjøretidene for begge strukturene med riktig valg av notasjon
  • kunne håndkjøre hashing med kjeding, en FIFO-kø med wraparound og en sekvens av Union-operasjoner, og levere hele tilstanden

4Grafalgoritmer: traversering, spenntrær og korteste vei

4.1Grafrepresentasjon, traversering og topologisk sortering
  • kunne velge mellom nabomatrise og naboliste ut fra hvor tett grafen er, og begrunne valget med plassforbruk og kjøretid
  • kunne kjøre `BFS` og `DFS` for hånd og oppgi avstander, discover- og finish-tider og kantklassifiseringen
  • kunne finne en topologisk sortering av en rettet asyklisk graf ved synkende finish-tid, og forklare hvorfor det virker
  • kunne avgjøre om en rettet graf har en sykel ved hjelp av dybde-først-søk, og oppgi kjøretiden
4.2Minimale spenntrær — Prim og Kruskal
  • kunne definere spenntre og minimalt spenntre, og avgjøre om en gitt kantmengde er et spenntre
  • kunne formulere snittegenskapen med betingelsen om at snittet respekterer valgene, og forklare hva en trygg kant er
  • kunne kjøre `MST-Kruskal` og `MST-Prim` for hånd og oppgi kantene i den rekkefølgen de velges
  • kunne begrunne kjøretiden $O(E\lg V)$ for begge algoritmene, og si hvilket steg som dominerer
4.3Korteste vei fra én kilde — Dijkstra, Bellman-Ford, DAG
  • kunne slakke en kant for hånd og gjøre rede for hva d- og pi-verdiene står for underveis
  • kunne velge riktig algoritme for korteste vei fra én kilde ut fra om grafen har negative kantvekter og om den er syklusfri
  • kunne oppgi kjøretiden til Dijkstra, Bellman-Ford og DAG-Shortest-Path og begrunne hver av dem i én setning
  • kunne håndkjøre Dijkstra og Bellman-Ford og levere d-verdien for hver node i eksamensformatet
4.4Alle-til-alle korteste vei
  • kunne utføre én runde av `Floyd-Warshall` for hånd og oppdatere både avstandsmatrisen og forgjengermatrisen
  • kunne regne ut en celle i min-pluss-produktet og forklare hvorfor det ikke er vanlig matriseprodukt
  • kunne velge riktig algoritme for alle-til-alle korteste vei ut fra grafens tetthet og fortegnet på kantvektene
4.5DRILL — Håndkjøring av grafalgoritmer
  • kunne kjøre `Kruskal` mekanisk og oppgi kantene i den rekkefølgen de legges til, med de forkastede merket
  • kunne føre `BFS` og `DFS` på papir og lese av avstander, discover- og finish-tider og en topologisk rekkefølge
  • kunne utføre én runde av `Floyd-Warshall` og ett min-pluss-produkt uten å blande sammen reglene
4.PPrøver til del 4: Grafalgoritmer: traversering, spenntrær og korteste vei
  • kunne håndkjøre BFS og DFS på en graf gitt som nabolister, og utlede en topologisk sortering fra synkende finish-tid
  • kunne håndkjøre MST-Kruskal og formulere snittegenskapen med betingelsen som gjør den sann
  • kunne velge riktig algoritme for korteste vei fra én kilde ut fra kravene grafen stiller, og oppgi kjøretiden for hver av dem
  • kunne håndkjøre Floyd-Warshall for en gitt runde og regne ut en celle med min-pluss-produktet i Slow-APSP

5Maksimal flyt

5.1Flytnett, restnett og snitt
  • kunne avgjøre om en gitt tildeling av tall til kantene er en lovlig flyt, og lese av flytverdien
  • kunne bygge restnettet til en flyt med ryggkantene, og finne en forøkende sti med flaskehals
  • kunne regne ut snittkapasitet og snittflyt for et gitt snitt, og bruke et snitt som øvre grense for flytverdien
  • kunne forklare hva heltallsteoremet garanterer, og hvorfor det gjør maks-flyt brukbart til tilordning
5.2Ford-Fulkerson, Edmonds-Karp og maks-flyt/min-snitt
  • kunne kjøre Ford-Fulkerson-metoden for hånd og oppgi både maksimal flytverdi og et min-snitt
  • kunne forklare hva maks-flyt/min-snitt-teoremet sier, og bruke det til å bevise at en flyt er maksimal
  • kunne skille pseudopolynomisk fra polynomisk, og si hvorfor Edmonds-Karp er polynomisk mens den generelle metoden ikke er det
5.3DRILL — Håndkjøring av maks-flyt og flyt-modellering
  • kunne kjøre `Edmonds-Karp` for hånd, føre restnettet underveis og oppgi både flytverdi og min-snitt
  • kunne kjenne igjen et fordelingsproblem som maks-flyt og et barriereproblem som min-snitt
  • kunne bygge flytnettet i en modelleringsoppgave og lese tildelingen ut av den ferdige flyten
5.PPrøver til del 5: Maksimal flyt
  • kunne definere restkapasitet, restnett, forøkende sti og snitt presist, og regne ut snittkapasitet og nettoflyt for et gitt snitt
  • kunne håndkjøre Edmonds-Karp og levere både maksimal flytverdi og et minimalt snitt, med restnettet tegnet ferdig
  • kunne forklare hvorfor Ford-Fulkerson er pseudopolynomisk mens Edmonds-Karp er polynomisk, uten å blande det med NP-hardhet
  • kunne modellere et fordelings- eller barriereproblem som maksimal flyt, og rekonstruere selve løsningen fra flyten eller fra snittet

6Dynamisk programmering, grådighet og stabil matching

6.1Dynamisk programmering — mekanikk
  • kunne avgjøre om et problem har optimal substruktur og overlappende delproblemer, og dermed om dynamisk programmering er riktig verktøy
  • kunne skrive den samme rekurrensen både som memoisert rekursjon og som tabellutfylling nedenfra og opp, og begrunne at de har samme asymptotiske kjøretid
  • kunne hente ut selve løsningen og ikke bare optimalverdien, ved å lagre valgene underveis, og forklare hvorfor det ikke øker kjøretiden
  • kunne skille et avgjørelsesproblem fra et optimeringsproblem og oversette mellom de to variantene av samme problem
6.2DP-klassikere — stavkapping, LCS og ryggsekk
  • kunne sette opp rekurrensen og grunntilfellene for stavkapping, lengste felles delsekvens og 0-1-ryggsekk ved å se på ett valg om gangen
  • kunne fylle en DP-tabell for hånd og lese av både optimalverdien og selve løsningen fra de lagrede valgene
  • kunne begrunne kjøretidene og forklare hvorfor 0-1-ryggsekkens uttrykk er pseudopolynomisk og ikke polynomisk
  • kunne gjenkjenne et sekvens- eller utvalgsproblem i ny innpakning og peke på hvilken av de tre malene som passer
6.3DRILL — DP-design og rekonstruksjon
  • kunne kjenne igjen et problem som løses med dynamisk programmering, og definere delproblemet presist
  • kunne skrive rekurrensen med grunntilfeller og oppgi fylleorden og kjøretid
  • kunne rekonstruere selve løsningen fra lagrede valg, og begrunne at det ikke øker den asymptotiske kjøretiden
6.4Grådighet — Huffman og aktivitetsutvelgelse
  • kunne bygge et Huffman-tre fra gitte frekvenser og oppgi kodelengden for hvert tegn
  • kunne begrunne hvorfor det å velge aktiviteten som slutter først gir flest mulig aktiviteter
  • kunne forklare et bytteargument, altså at et lokalt valg kan inngå i en optimal løsning
  • kunne avgjøre når grådighet virker, og når problemet i stedet krever dynamisk programmering
6.5Stabil matching — Gale-Shapley
  • kunne definere et blokkerende par og avgjøre om en gitt matching er stabil
  • kunne kjøre `Gale-Shapley` for hånd og oppgi den ferdige matchingen sammen med hvilken orientering som ble kjørt
  • kunne avgjøre om to bestemte parter kan være paret i en stabil matching, ved å kjøre begge orienteringene
6.PPrøver til del 6: Dynamisk programmering, grådighet og stabil matching
  • kunne avgjøre om et problem har overlappende delproblemer og optimal substruktur, og begrunne valget mellom memoisering og utfylling nedenfra og opp
  • kunne sette opp en DP-rekurrens med grunntilfeller, fylle tabellen og hente ut selve løsningen fra lagrede beslutninger
  • kunne bygge et Huffman-tre fra frekvenser og oppgi kodelengden per tegn og totalt antall bits
  • kunne kjøre Gale-Shapley i begge orienteringer og avgjøre om en gitt matching har et blokkerende par

7NP-kompletthet og reduksjoner

7.1P, NP og co-NP — sertifikat og verifikasjon
  • kunne definere klassene P og NP presist, og forklare at NP handler om å verifisere et foreslått svar raskt, ikke om å finne det
  • kunne oppgi et sertifikat og en verifikasjonsalgoritme for et konkret problem og begrunne at verifikasjonen er polynomisk
  • kunne skille et avgjørelsesproblem fra et optimeringsproblem og skrive om fra det ene til det andre med en terskelverdi
  • kunne gjøre rede for hva som er kjent og hva som er åpent om forholdet mellom P, NP og co-NP
7.2Polynomiske reduksjoner og reduksjonsretning
  • kunne forklare hva en polynomisk reduksjon er, og hvilke tre krav den må oppfylle
  • kunne avgjøre hvilken vei en reduksjon må gå for å vise at et problem er vanskelig, og si hva den motsatte veien beviser
  • kunne skille NP-hardt fra NP-komplett, og pseudopolynomisk fra polynomisk
7.3NP-komplette problemer
  • kunne skrive den formelle definisjonen av CIRCUIT-SAT, SAT, 3-CNF-SAT, CLIQUE, VERTEX-COVER, HAM-CYCLE, TSP og SUBSET-SUM som avgjørelsesproblemer
  • kunne forklare hovedideen i at CIRCUIT-SAT er NP-komplett, altså at kretsen simulerer verifikasjonsalgoritmen og at sertifikatet er kretsens input
  • kunne skille CLIQUE fra VERTEX-COVER på både ulikhetstegn og hva kravet gjelder
  • kunne bruke reduksjonskjeden til å forklare hvordan et nytt problem vises NP-komplett, og hvilke to deler et slikt bevis alltid har
7.4DRILL — Reduksjonsretning og NP-argumenter
  • kunne avgjøre hvilken vei en reduksjon må gå for å vise at et problem er vanskelig, og skrive retningen presist
  • kunne skille de tre påstandene i NP, NP-hardt og NP-komplett, og vite hvilket bevis hver av dem krever
  • kunne vurdere om et ferdig NP-argument holder, ved å kontrollere polynomisk konstruksjonstid, lovlig instans og svarbevaring begge veier
  • kunne skille en pseudopolynomisk kjøretid fra et utsagn om at problemet er vanskelig
7.PPrøver til del 7: NP-kompletthet og reduksjoner
  • kunne definere P, NP og co-NP presist, og forklare hva et sertifikat og en verifikasjonsalgoritme er
  • kunne avgjøre hvilken vei en reduksjon må gå for å vise at et problem er vanskelig, og si hva den ikke beviser
  • kunne definere de navngitte NP-komplette problemene som avgjørelsesproblemer og skille NP-hardt fra NP-komplett
  • kunne skille en pseudopolynomisk kjøretid fra et NP-hardhetsargument

8Eksamenstrening

8.1Kortsvarssjangeren — å skrive presise, korte svar
  • kunne avgjøre hva en eksamensoppgave faktisk ber om, og levere svaret i den formen oppgaven krever
  • kunne skrive en definisjon der hovedpoenget står i første setning, slik at et avbrutt svar likevel gir uttelling
  • kunne budsjettere fire timer over tjue likt vektede oppgaver, og vite når en oppgave skal forlates
  • kunne skrive om et langt og upresist utkast til det korte svaret som treffer ferdigheten oppgaven tester
8.2DRILL — Åpen algoritmedesign via reduksjon
  • kunne kjenne igjen hvilket klassisk problem en innpakket oppgave egentlig er, og navngi paradigmet eksplisitt
  • kunne bygge konstruksjonen — nettet, rekurrensen eller grafen — og oppgi kjøretiden i problemets egne størrelser
  • kunne rekonstruere selve løsningen og ikke bare optimalverdien, og si at det ikke øker kjøretiden
8.3Øvingseksamen 1 — bredt ordinært sett (kode E)
  • kunne gjennomføre et komplett firetimers kortsvarssett på egen hånd og kjenne igjen hvilken svarform hver oppgave krever
  • kunne gi det strammeste asymptotiske uttrykket for en kjøretidsfunksjon og navngi metoden du løser en rekurrens med
  • kunne håndkjøre en maks-haug og korteste vei fra én kilde, og levere sluttilstanden i det formatet eksamen ber om
  • kunne skrive en åpen designbesvarelse som navngir paradigmet, rekonstruerer selve løsningen og oppgir en begrunnet kjøretid
8.4Øvingseksamen 2 — datastruktur- og graftungt sett
  • kunne håndkjøre Build-Max-Heap, Tree-Insert, MST-Kruskal og Floyd-Warshall feilfritt og levere sluttilstanden i den formen oppgaven ber om
  • kunne føre en FIFO-kø i et array gjennom en operasjonssekvens med wraparound og oppgi hele tabellen med begge pekerne
  • kunne avgjøre hvilken vei en reduksjon må gå for å vise at et nytt problem er vanskelig, og si hva den ikke beviser
  • kunne modellere et tilordningsproblem som maksimal flyt og hente ut selve tilordningen, ikke bare flytverdien
8.5Øvingseksamen 3 — designtungt topp-sett
  • kunne gjennomføre et komplett firetimers sett på tid, uten hjelpemidler, med riktig svarform i hver sjanger
  • kunne skrive fem fullstendige designsvar med alle de fem obligatoriske leddene, inkludert rekonstruksjonen
  • kunne argumentere for reduksjonsretning tre ganger på rad uten å snu pilen
Tilbake til TDT4120 Algoritmer og datastrukturer