IN2010

Studieguide

God oversikt over pensum med forklaringer, formler, vanlige feil og eksamenstips.

Introduksjon

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 (ca. 20-30 poeng), og (3) storre oppgaver der du skriver pseudokode og argumenterer for korrekthet og kjoretid (ca. 40-50 poeng). Totalt ca. 66-78 poeng.

Viktige tips: Les oppgaveteksten svart noye. Alle implementasjonsoppgaver skal besvares med pseudokode som er lett forstaelig, entydig og presis. Lavere kjoretidskompleksitet gir mer poeng. Du kan anta at algoritmer og datastrukturer fra pensum er tilgjengelig, med mindre noe annet er spesifisert. Det lonner seg a svare pa alle flervalgsoppgaver -- det gjores ingen forskjell mellom ubesvart og feil svar.

Grafalgoritmer

Graftraversering med BFS og DFS, topologisk sortering, sterkt sammenhengende komponenter og syklusdeteksjon. Grunnlaget for nesten alle grafoppgaver pa eksamen.

Oversikt

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 (bredde-forst-sok)

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 (dybde-forst-sok)

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|).

Topologisk sortering

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|).

Syklusdeteksjon

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.

Grafegenskaper

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), tre (sammenhengende asyklisk graf), isomorfi (to grafer har samme struktur). Pa H2022 ble det gitt to grafer og spurt om egenskaper som antall kanter, grader, og om grafene er isomorfe.

Eksempel 1: BFS med dybdegrense (H2024-stil)

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 result

Eksempel 2: Syklusdeteksjon med DFS (H2023-stil)

Procedure 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

Nøkkelformler

•BFS kjoretid: O(|V| + |E|) -- bruker ko (FIFO)
•DFS kjoretid: O(|V| + |E|) -- bruker stakk/rekursjon
•TopSort kjoretid: O(|V| + |E|) -- kun for DAG-er
•Naboliste: O(|V| + |E|) plass, O(grad(v)) for a finne naboer
•Nabomatrise: O(|V|^2) plass, O(1) for a sjekke kant

Vanlige feil

⚠️Glemme a markere noder som besokt i BFS/DFS, noe som gir uendelig lokke i grafer med sykler.
⚠️Forveksle BFS og DFS: BFS bruker ko og finner korteste sti i uvektede grafer, DFS bruker stakk og er grunnlag for syklusdeteksjon.
⚠️Tro at topologisk sortering finnes for alle grafer -- den finnes kun for rettede asykliske grafer (DAG-er).
⚠️Bruke DFS uten farger (kun visited-mengde) for syklusdeteksjon i rettede grafer -- du trenger tre tilstander for a skille mellom back-edges og cross-edges.

Eksamenstips

💡Nar oppgaven sier 'forst naermeste, deretter lenger ut' eller 'nivavis', er det BFS som gjelder (H2024: venner innen k ledd).
💡Nar oppgaven spor om sykliske avhengigheter eller om en graf er en DAG, bruk DFS med tre farger.
💡Oppgi alltid kjoretidskompleksiteten nar du bruker en grafalgoritme -- det gir ekstra poeng.

Laster...

Introduksjon

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 result

Procedure 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