IN2010 Algoritmer og datastrukturer | Interaktiv Matematikkbok | Skolesaga

IN2010 Algoritmer og datastrukturer

Bygget på sju eksamenssett fra 2018 til 2024 — hvert kapittel er kalibrert mot det som faktisk gis til eksamen. Se hele kildegrunnlaget

asymptotisk analysesorteringhashingsøketrærgrafalgoritmerNP-teori

Se læringsmål Flashcards (513 definisjoner)Eksamenstrening Kildegrunnlag

Kapittel 0: Eksamenskart

1 delkapittel · ca. 35 min

0.1Eksamenskartet — slik testes IN2010

Kapittel 1: Asymptotisk analyse og kjøretidsfakta

5 delkapitler · ca. 5 t 50 min

1.1Asymptotisk notasjon — O (og kort Ω, Θ)

1.2Kjøretidsanalyse fra kode — løkketelling

1.3DRILL — Kode → O-notasjon

1.4Kjøretids- og teori-fakta — sant/usant og antigjettings-strategi

1.PPrøver til del 1: Asymptotisk analyse og kjøretidsfakta

Kapittel 2: Sortering og stabilitet

5 delkapitler · ca. 5 t 50 min

2.1Sammenligningsbaserte sorteringer og invarianter

2.2Effektive sorteringer og nedre grense

2.3Lineær sortering — bucket, counting og radix

2.4DRILL — Sorteringsegenskaper, invarianter og valg

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

Kapittel 3: Hashing og søk

5 delkapitler · ca. 5 t 55 min

3.1Hashtabeller og lukket hashing (linear probing)

3.2Load-faktor, rehashing og hashmap/-set som verktøy

3.3DRILL — Linear-probing håndkjøring og insert-pseudokode

3.4Søk i pseudokode — binærsøk, finn duplikat og finn par

3.PPrøver til del 3: Hashing og søk

Kapittel 4: Trær: søketrær, balanserte trær og heap

6 delkapitler · ca. 7 t

4.1Binære søketrær (BST)

4.2Tre-algoritmer i pseudokode — beskjæring og lineær rekursjon

4.3Balanserte trær — AVL og rød-svart

4.4Heap og prioritetskø

4.5DRILL — Håndkjøring av heap og AVL

4.PPrøver til del 4: Trær: søketrær, balanserte trær og heap

Kapittel 5: Grafer: representasjon, traversering og komponenter

6 delkapitler · ca. 6 t 55 min

5.1Grafrepresentasjon og grunnbegreper

5.2BFS og DFS — traversering

5.3Komponenter, 2-fargelegging og sykeldeteksjon

5.4SCC og komponentgraf (kondensasjon) — UiO-signatur

5.5DRILL — Grafalgoritmer i pseudokode: mønstergjenkjenning

5.PPrøver til del 5: Grafer: representasjon, traversering og komponenter

Kapittel 6: Korteste vei, spenntrær og grådighet

6 delkapitler · ca. 6 t 45 min

6.1Topologisk sortering og DAG-egenskaper

6.2Korteste vei — BFS, Dijkstra, DAG og reversert graf

6.3Minimale spenntrær — Prim, Kruskal, Borůvka

6.4Huffman-koding

6.5DRILL — Korteste-vei-matrisen og MST-modellering

6.PPrøver til del 6: Korteste vei, spenntrær og grådighet

Kapittel 7: Datastruktur-design, drøfting og NP-teori

4 delkapitler · ca. 4 t 30 min

7.1ADT-design — mediankø, bøttekø og trie

7.2Drøft to strategier

7.3NP-kompletthet — og hva som IKKE er IN2010-pensum

7.PPrøver til del 7: Datastruktur-design, drøfting og NP-teori

Kapittel 8: Eksamenstrening

4 delkapitler · ca. 13 t 30 min

8.1DRILL — Del 2-strategi: velg lavest kjøretid (poengtrappen) og skriv presis pseudokode

8.2Øvingseksamen 1 — bredt ordinært sett (epoke 3)

8.3Øvingseksamen 2 — håndkjørings- og hashing-tungt sett

8.4Øvingseksamen 3 — grafmodellerings-tungt topp-sett

Uavhengig læringsressurs: Skolesaga er ikke tilknyttet, godkjent av eller utarbeidet i samarbeid med Universitetet i Oslo. 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.