Komplett pensumoversikt for algoritmer og datastrukturer ved UiO — med forklaringer, sentrale begreper, eksamenstips og vanlige fallgruver. Eksamensoptimalisert basert på tidligere eksamener.
IN2010 Algoritmer og datastrukturer er et kjerneemne ved Institutt for informatikk, UiO. Kurset dekker avanserte algoritmer og datastrukturer som bygger videre pa IN1000/IN1010: grafalgoritmer, trestrukturer, hashing, sortering, graadige algoritmer, og kompleksitetsanalyse. Eksamen er en 4-timers skriftlig prove uten hjelpemidler, der du skriver pseudokode og resonnerer.
Eksamen folger et fast monster med tre deler: (1) en kort oppvarming (2 poeng) der du forklarer hva en algoritme og en datastruktur er, (2) en flervalg/sant-usant-del med sma oppgaver som rettes automatisk (ca. 22-32 poeng), og (3) storre oppgaver der du skriver pseudokode og argumenterer for korrekthet og kjoretid (ca. 40-60 poeng). Totalt ca. 66-100 poeng.
Viktig om sant/usant-delen: poengene skaleres for gjetning. Hvis du svarer riktig pa n av N pastander, far du typisk 2*max(n - N/2, 0) poeng. Gjetter du tilfeldig pa alt, far du i snitt null poeng; svarer du riktig pa alt, far du full uttelling. Du bor likevel svare pa alt -- det er ingen ekstra straff for feil utover gjettekorreksjonen, og alt du faktisk vet teller positivt.
Viktige tips: Les oppgaveteksten svart noye. Alle implementasjonsoppgaver skal besvares med pseudokode som er lett forstaelig, entydig og presis -- en klar forklaring med naturlig sprak kan gi like mye uttelling som tvetydig pseudokode. Lavere kjoretidskompleksitet gir mer poeng. Du kan anta at algoritmer og datastrukturer fra pensum er tilgjengelig, med mindre noe annet er spesifisert. Et gjennomgaende monster er at oppgavene er innpakkede historier (DNT-rundtur, Blindern-tunneler, dependency hell, Whops!-oppgjor) der den egentlige jobben er a kjenne igjen hvilken pensumalgoritme som loser problemet.
Graftraversering med BFS og DFS, topologisk sortering, sterkt sammenhengende komponenter og syklusdeteksjon. Grunnlaget for nesten alle grafoppgaver pa eksamen.
En graf G = (V, E) bestar av en mengde noder V og en mengde kanter E. Grafen kan vaere rettet (kanter har retning) eller urettet (kanter gar begge veier). Grafer kan representeres som nabolister (et array av lister, en per node) eller som en nabomatrise (en V x V matrise). Nabolister er mest minneeffektivt for sparse grafer (fa kanter), mens nabomatriser gir O(1)-oppslag for a sjekke om en kant finnes.
BFS utforsker grafen nivavis: forst alle naboer pa avstand 1, deretter avstand 2, osv. Algoritmen bruker en ko (FIFO) og en mengde med besoktenoder. BFS finner korteste sti i uvektede grafer (antall kanter). Kjoretid: O(|V| + |E|). Pa eksamen (H2024) ble BFS brukt til a finne venner innen k ledd -- en typisk anvendelse der du begrenser BFS til en gitt dybde.
DFS utforsker grafen ved a ga sa dypt som mulig for den snur. Algoritmen bruker en stakk (eksplisitt eller via rekursjon) og en mengde besoktenoder. DFS er grunnlaget for mange grafalgoritmer: syklusdeteksjon, topologisk sortering, og sterkt sammenhengende komponenter. Kjoretid: O(|V| + |E|).
En topologisk sortering av en rettet asyklisk graf (DAG) er en lineaer ordning av nodene slik at for hver kant (u, v) kommer u for v. Algoritmen bruker DFS eller en ko-basert tilnaerming (Kahns algoritme). Topologisk sortering finnes kun for DAG-er. Pa eksamen (H2022) ble det spurt om kjoretiden til TopSort -- den er O(|V| + |E|).
For a oppdage sykler i en rettet graf bruker vi DFS med tre farger: hvit (ubesokt), gra (pabesokt, pa rekursjonsstakken), svart (ferdig). Hvis vi under DFS treffer en gra node, har vi funnet en sykel. Pa H2023 (Dependency hell) ble det eksplisitt bedt om a sjekke om en avhengighetsgraf inneholder sykliske avhengigheter.
I en rettet graf er en sterkt sammenhengende komponent en maksimal mengde noder der det finnes en rettet sti begge veier mellom ethvert par. SCC finnes i O(|V| + |E|) med to DFS-gjennomloop (Kosarajus algoritme: DFS for a fa ferdig-rekkefølge, reverser grafen, DFS i synkende ferdig-rekkefølge) eller med Tarjans algoritme. Dette er et yndlingsverktoy pa eksamen for a finne rundturer/sykler: alle komponenter med mer enn en node utgjor en sykel. En graf der hver node inngar i hoyst en sykel kan handteres ved a kjore SCC og returnere alle komponenter av storrelse > 1. SCC brukes ogsa til a sjekke om en rettet graf er sterkt sammenhengende (da er det noyaktig en komponent som inneholder alle noder).
Du bor kjenne til sentrale begreper: grad (antall kanter til en node), inngrad/utgrad (i rettede grafer), sammenhengende (det finnes sti mellom alle par av noder), sterkt sammenhengende (rettet sti begge veier), DAG (rettet asyklisk graf), tre (sammenhengende asyklisk graf), 2-fargbar/bipartitt (nodene kan deles i to mengder uten kant innad), isomorfi (to grafer har samme struktur). Et tilbakevendende sporsmal er om en graf er et tre: en sammenhengende urettet graf med n noder er et tre hvis og bare hvis den har noyaktig n-1 kanter og er asyklisk -- dette kan sjekkes med en enkelt BFS/DFS som teller besokte noder og oppdager kanter tilbake til allerede besokte noder.
Procedure BFS_k(G, s, k):
queue = ny ko
visited = ny mengde
queue.enqueue((s, 0))
visited.add(s)
result = []
while queue er ikke tom:
(v, depth) = queue.dequeue()
if depth > k: break
result.append(v)
for each nabo u av v i G:
if u ikke i visited:
visited.add(u)
queue.enqueue((u, depth + 1))
return resultProcedure HasCycle(G):
color = ny ordbok (alle noder -> WHITE)
for each node v i G:
if color[v] == WHITE:
if DFS_Visit(G, v, color):
return true
return false
Procedure DFS_Visit(G, v, color):
color[v] = GRAY
for each nabo u av v:
if color[u] == GRAY:
return true // Sykel funnet!
if color[u] == WHITE:
if DFS_Visit(G, u, color):
return true
color[v] = BLACK
return false// Finn alle sykler/rundturer i en rettet graf:
// en rundtur er en sterkt sammenhengende komponent
// med mer enn en node.
Procedure FinnRundturer(G):
komponenter = SterktSammenhengendeKomponenter(G)
rundturer = ny mengde
for each komp i komponenter:
if |komp| > 1:
rundturer.add(komp)
return rundturer
// Kjoretid: O(|V| + |E|) -- SCC dominerer
// (Kosaraju: to DFS-pass + en grafreversering)Nøkkelformler
Vanlige feil
Eksamenstips
Laster...