🕸️TDT4120 Algoritmer og datastrukturer

Høyskole

Eksamensrettet

Eksamensrettet lærebok for TDT4120 ved NTNU

Bygget på 17 eksamenssett med løsningsforslag 2015–2023 — hvert kapittel er kalibrert mot det som faktisk gis til eksamen.

asymptotisk analysehåndkjøring av datastrukturerdynamisk programmeringmaksimal flytNP-reduksjoner

Se læringsmål Flashcards (609 definisjoner)Eksamenstrening

Kapittel 0: Eksamenskart

1 delkapittel · ca. 35 min

0.1Eksamenskartet — slik testes TDT4120

Kapittel 1: Asymptotisk analyse og rekurrenser

7 delkapitler · ca. 8 t

1.1Asymptotisk notasjon — de fem symbolene

1.2Forenkling av asymptotiske uttrykk

1.3DRILL — Asymptotisk forenkling og notasjon

1.4Rekurrenser — masterteoremet

1.5Rekurrenser — iterasjon, substitusjon og splitt-og-hersk

1.6DRILL — Rekurrensløsning med navngitt metode

1.PPrøver til del 1: Asymptotisk analyse og rekurrenser

Kapittel 2: Sortering og utvelgelse

5 delkapitler · ca. 5 t 45 min

2.1Sammenligningsbaserte sorteringer

2.2Lineær sortering og stabilitet

2.3Utvelgelse — Partition, Randomized-Select og Select

2.4DRILL — Sortering: håndkjøring, kjøretid og kombinasjon

2.PPrøver til del 2: Sortering og utvelgelse

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

6 delkapitler · ca. 6 t 50 min

3.1Hauger og Heapsort

3.2Binære søketrær

3.3DRILL — Håndkjøring av hauger og BST

3.5Køer, stakker, amortisert analyse og disjunkte mengder

3.PPrøver til del 3: Datastrukturer: hauger, søketrær og hashing

Kapittel 4: Grafalgoritmer: traversering, spenntrær og korteste vei

6 delkapitler · ca. 7 t 10 min

4.1Grafrepresentasjon, traversering og topologisk sortering

4.2Minimale spenntrær — Prim og Kruskal

4.3Korteste vei fra én kilde — Dijkstra, Bellman-Ford, DAG

4.4Alle-til-alle korteste vei

4.5DRILL — Håndkjøring av grafalgoritmer

4.PPrøver til del 4: Grafalgoritmer: traversering, spenntrær og korteste vei

Kapittel 5: Maksimal flyt

4 delkapitler · ca. 5 t 15 min

5.1Flytnett, restnett og snitt

5.2Ford-Fulkerson, Edmonds-Karp og maks-flyt/min-snitt

5.3DRILL — Håndkjøring av maks-flyt og flyt-modellering

5.PPrøver til del 5: Maksimal flyt

Kapittel 6: Dynamisk programmering, grådighet og stabil matching

6 delkapitler · ca. 6 t 55 min

6.1Dynamisk programmering — mekanikk

6.2DP-klassikere — stavkapping, LCS og ryggsekk

6.3DRILL — DP-design og rekonstruksjon

6.4Grådighet — Huffman og aktivitetsutvelgelse

6.5Stabil matching — Gale-Shapley

6.PPrøver til del 6: Dynamisk programmering, grådighet og stabil matching

Kapittel 7: NP-kompletthet og reduksjoner

5 delkapitler · ca. 6 t

7.1P, NP og co-NP — sertifikat og verifikasjon

7.2Polynomiske reduksjoner og reduksjonsretning

7.3NP-komplette problemer

7.4DRILL — Reduksjonsretning og NP-argumenter

7.PPrøver til del 7: NP-kompletthet og reduksjoner

Kapittel 8: Eksamenstrening

5 delkapitler · ca. 14 t 15 min

8.1Kortsvarssjangeren — å skrive presise, korte svar

8.2DRILL — Åpen algoritmedesign via reduksjon

8.3Øvingseksamen 1 — bredt ordinært sett (kode E)

8.4Øvingseksamen 2 — datastruktur- og graftungt sett

8.5Øvingseksamen 3 — designtungt topp-sett

Uavhengig læringsressurs: Skolesaga er ikke tilknyttet, godkjent av eller utarbeidet i samarbeid med Norges teknisk-naturvitenskapelige universitet. Emnekoden brukes kun for å identifisere hvilket emne stoffet er rettet mot. Dette er ikke offisielt studiemateriell — pensum og eksamensordning kan endres, så sjekk alltid emnets offisielle sider.

Les mer i vilkårene.