TDT4136 · NTNU

Studieguide for TDT4136 Introduksjon til kunstig intelligens

Komplett pensumoversikt for introduksjon til kunstig intelligens ved NTNU — med forklaringer, sentrale begreper, eksamenstips og vanlige fallgruver. Eksamensoptimalisert basert på tidligere eksamener.

Introduksjon

Denne studieguiden dekker hele pensum i TDT4136 Introduksjon til kunstig intelligens ved NTNU (7,5 stp). Faget er grunnkurset i kunstig intelligens for sivilingeniør- og masterstudenter ved IDI.

Eksamen er 4-timers skoleeksamen med hjelpemiddelkode D (kun enkel kalkulator — ingen trykte eller håndskrevne hjelpemidler). Oppgavesettet er på engelsk, men du kan svare på norsk. Du skal ikke skrive programkode. I stedet skal du kjøre algoritmer for hånd (trace), analysere egenskapene deres (fullstendighet, optimalitet, kompleksitet), modellere en tekstlig situasjon som et søkeproblem, et CSP, et planleggingsproblem eller et spill, og drøfte begreper presist.

Faste mønstre i oppgavesettene 2015–2023:

Logikk (ca. 25 %): oversett til utsagns-/predikatlogikk, konverter til CNF med hvert steg navngitt, og gjennomfør resolusjonsrefutasjon med eksplisitt unifisering.
Søk (ca. 20 % samlet): trace av BFS, DFS, UCS, greedy og A* på samme graf, med frontier og explored i hvert steg — og deretter analyse av admissibilitet og konsistens.
CSP (ca. 13 %): formulering fra tekst, constraint-graf, AC-3-trace og backtracking med MRV og LCV.
Planlegging (ca. 11 %): STRIPS/PDDL-aksjonsskjemaer, foroversøk og regresjon, partial-order planning og GRAPHPLAN.
Adversarielt søk (ca. 8 %): minimax-verdier i et gitt spilltre og alpha-beta-pruning med begrunnelse.
Intelligente agenter (ca. 8 %, stigende): PEAS, klassifisering av oppgavemiljø, valg av agenttype, belief states — samt AI-etikk.
Spillteori (ca. 6 %): payoff-matrise, dominans, Nash-likevekt, Pareto-optimalitet og sosial velferd.
Korte spørsmål (10–20 %): 10 småspørsmål à 2 poeng om lokalsøk, kunnskapsrepresentasjon, AI-historie og etikk. Fra 2015 til 2018 var disse sant/usant og flervalg med MINUSPOENG for gale svar; fra 2019 er de fritekst.

Merk: bayesianske nettverk, sannsynlighetsregning og maskinlæring er ikke pensum i TDT4136 — de hører til TDT4171 «Metoder i kunstig intelligens». De forekommer ikke på noen av eksamenssettene 2015–2023.

Søkealgoritmer

Eksamensrelevant

Uinformert søk: BFS, DFS, UCS og IDS. Forstå frontier, explored set, og de fire egenskapene fullstendighet, optimalitet, tids- og plasskompleksitet.

Problem-formulering

Et søkeproblem består av fem deler:

Initial state ( $s_0$ ) — utgangspunktet
Actions(s) — settet av tillatte aksjoner i tilstand $s$
Result(s, a) — overgangsmodell: hvilken tilstand $a$ fører til
Goal-Test(s) — sann hvis $s$ er en målstand
Step-Cost(s, a, s') — kostnad ved å ta aksjon $a$ fra $s$ til $s'$

En løsning er en aksjonssekvens fra $s_0$ til en målstand. En optimal løsning har lavest total kostnad blant alle løsninger.

Generisk søk-algoritme (AIMA Tree-Search)

function TREE-SEARCH(problem) returns solution or failure
  frontier ← {Node(problem.INITIAL)}
  loop do
    if frontier is empty then return failure
    node ← POP(frontier)
    if problem.GOAL-TEST(node.STATE) then return SOLUTION(node)
    for each action in problem.ACTIONS(node.STATE) do
      child ← CHILD-NODE(problem, node, action)
      add child to frontier

GRAPH-SEARCH legger til en explored-mengde for å hindre re-ekspansjon av allerede besøkte tilstander.

BFS — Breadth-First Search

FIFO-kø som frontier. Utvider noder i lag (alle dybde-1-noder før dybde-2 osv.).

Egenskaper for BFS

Fullstendig: Ja (hvis $b$ endelig)
Optimal: Ja, kun hvis alle steg-kostnader er like ( $c = 1$ )
Tidskompleksitet: $O(b^d)$ der $b$ = forgrening, $d$ = dybde av grunneste mål
Plasskompleksitet: $O(b^d)$ (alle noder på frontier samtidig)

DFS — Depth-First Search

LIFO-stack som frontier. Utvider deepest node først.

Egenskaper for DFS

Fullstendig: Nei (kan gå i loop på uendelig graf), Ja for endelig graf med graph-search
Optimal: Nei
Tidskompleksitet: $O(b^m)$ der $m$ = maks dybde
Plasskompleksitet: $O(bm)$ — KUN den aktive grenen lagres

UCS — Uniform-Cost Search

Priority queue på path-cost $g(n)$ . Utvider node med lavest $g$ først. Som BFS, men håndterer ulike kostnader.

Egenskaper for UCS

Fullstendig: Ja (hvis steg-kostnader $\ge \varepsilon > 0$ )
Optimal: Ja
Tidskompleksitet: $O(b^{1+\lfloor C^*/\varepsilon \rfloor})$
Plasskompleksitet: $O(b^{1+\lfloor C^*/\varepsilon \rfloor})$

IDS — Iterative Deepening Search

Kjør DFS med dybde-grense $\ell = 0, 1, 2, \ldots$ inntil mål funnet. Kombinerer BFS-fullstendighet og DFS-plassforbruk.

Egenskaper for IDS

Fullstendig: Ja
Optimal: Ja (hvis $c = 1$ )
Tidskompleksitet: $O(b^d)$ — samme orden som BFS
Plasskompleksitet: $O(bd)$ — bedre enn BFS

Selv om IDS gjentar arbeid for hvert dybdenivå, dominerer det siste nivået: $b^d + 2b^{d-1} + 3b^{d-2} + \ldots = O(b^d)$ .

Trace-eksempel: BFS

Eksempel — BFS på graf A→{B,C}, B→{D}, C→{D,E}, mål = E

Steg	Frontier (FIFO)	Pop / Explored
0	[A]	—
1	[B, C]	A
2	[C, D]	B
3	[D, D, E]	C — D dukker opp to ganger, men graph-search hindrer duplikat
4	[E]	D
5	—	E (mål funnet!)

Løsning: A → C → E (BFS finner kortest antall kanter, ikke lavest kostnad).

Bidireksjonell søk

Start søk samtidig fra $s_0$ og fra målet (hvis goal er kjent eksplisitt). Møtepunkt = løsning. Tidskompleksitet: $O(b^{d/2})$ — eksponentielt bedre, men krever invertibel handlingsmodell og dataeffektiv test av om frontier-1 møter frontier-2.

Sammenligningstabell (utenat til eksamen!)

Algoritme	Full?	Optimal?	Tid	Plass
BFS	Ja	Hvis $c=1$	$O(b^d)$	$O(b^d)$
UCS	Ja*	Ja	$O(b^{1+\lfloor C^*/\varepsilon \rfloor})$	$O(b^{1+\lfloor C^*/\varepsilon \rfloor})$
DFS	Nei	Nei	$O(b^m)$	$O(bm)$
IDS	Ja	Hvis $c=1$	$O(b^d)$	$O(bd)$
Bidirekt.	Ja	Hvis $c=1$	$O(b^{d/2})$	$O(b^{d/2})$

Nøkkelformler

•BFS tid og plass: $O(b^d)$
•DFS plass: $O(bm)$ — eneste fordel over BFS
•UCS: $O(b^{1+\lfloor C^*/\varepsilon \rfloor})$ der $C^*$ = optimal kostnad, $\varepsilon$ = minste steg-kostnad
•IDS plass: $O(bd)$ — kombinerer beste fra BFS og DFS
•Bidireksjonell: $O(b^{d/2})$ tid
•Generelt: $b$ = forgreningsfaktor, $d$ = grunneste mål-dybde, $m$ = maks dybde i tre

Vanlige feil

⚠️Forveksler BFS-optimalitet — BFS er KUN optimal når steg-kostnader er like ( $c = 1$ ). For ulike kostnader: bruk UCS
⚠️Glemmer at DFS med graph-search (explored-mengde) ER fullstendig på endelig graf — det er kun TREE-SEARCH-versjonen som kan loope
⚠️Bytter rolle på frontier og explored-mengde i trace-oppgaver — frontier = noder vi vil utvide, explored = ferdig utforsket
⚠️Tester GOAL-TEST når node legges TIL frontier i UCS — det er feil! UCS må teste GOAL-TEST når noden trekkes UT (pop), ellers mister vi optimalitet
⚠️Forveksler tre-søk vs. graf-søk — tre-søk kan ekspandere samme tilstand flere ganger; graf-søk har explored set
⚠️Glemmer at IDS gjentar arbeid, men dominerer siste lag — $\sum_{i=0}^{d} (d-i+1)b^i = O(b^d)$
⚠️Bruker BFS-kompleksitet ( $b^d$ ) på DFS — DFS er $O(b^m)$ , og $m$ kan være $\gg d$
⚠️Glemmer at UCS=BFS når alle kostnader er like, og UCS=Dijkstra på grafer (eneste forskjell: UCS jobber lazy)

Eksamenstips

💡Lag ALLTID en steg-for-steg tabell med kolonner: Steg, Frontier (med inkluderte path-costs), Pop, Explored — dette gir mest poeng selv ved feil i siste steg
💡Husk sammenligningstabellen utenat: BFS/DFS/UCS/IDS × {Full, Optimal, Tid, Plass} — kommer på ~80% av eksamener
💡Når oppgaven spør 'hvilken algoritme er best her' — sjekk: er kostnader like (BFS)? trenger vi optimalitet (UCS/A*)? har vi begrenset minne (DFS/IDS)?
💡Tegn søketreet for hånd OG marker numerisk rekkefølge for ekspansjon — sensor leter etter at du forstår algoritmens prioriteringer
💡Ved par dybder spør IDS-spørsmål: 'hvorfor IDS over BFS?' → minne. 'Hvorfor IDS over DFS?' → optimalitet/fullstendighet
💡På flervalg om kompleksitet: pass på om $d$ (grunneste mål) eller $m$ (maks dybde) brukes — DFS skiller seg her
💡Skriv ut Tree-Search/Graph-Search-pseudokoden eksplisitt hvis oppgaven ber om 'beskriv algoritmen' — AIMA-stil gir full poeng
💡Hvis to noder har samme prioritet i UCS, må du ha en tie-breaking regel (vanligvis FIFO eller alfabetisk) — oppgi den eksplisitt

Laster...

Laster…