Algoritmer og datastrukturerHjem

CMD + K

Manimo · TDT4120

Videoer

Animerte scener med fortellerstemme. Velg en scene for å spille av.

13 videoer · 14 minutter totalt

Kapittel 0 · Verktøykassa: notasjon og forkunnskaper

1 video·1m 04
1:04
verktøykassa

Rekursjonstre: arbeid på hvert nivå

Hvordan vet vi at en del-og-hersk-algoritme bruker n ganger log n? Vi bretter rekursjonen ut som et tre, leser av arbeidet i hver node, og oppdager at hver rad summerer til n. Roten gjør n arbeid. To barn med n delt på to. Fire barnebarn med n delt på fire. Helt ned til løvene på ett. Treet er log av n nivåer dypt — og hvert nivå koster n. Sum: n ganger log n. Det er motoren bak flettesortering, hurtigsort, og hver eneste splitt-og-hersk-algoritme i pensum.

Kapittel 1 · Algoritmer, kjøretid og asymptotisk notasjon

1 video·59s
0:59
kjøretid

Asymptotisk vekst: Stor O

Hvorfor styrer en 'O' og ikke stoppeklokka hvor lenge en algoritme bruker? Fem klassiske vekstrater — konstant, logaritmisk, lineær, lineær ganger logaritmisk, kvadratisk — tegnes på samme plott. En glidende n-markør viser hvordan kurver som lå tett i bunnen river seg fra hverandre når n vokser. Den kvadratiske skyter ut av rammen først, den logaritmiske beveger seg knapt. Det er nettopp dette stor O fanger.

Kapittel 3 · Splitt og hersk

1 video·1m 00
1:00
splitt og hersk

Flettesortering: del og hersk

Hvorfor kan vi sortere åtte tall — eller en million — så mye raskere enn å sammenligne alle par? Splitt og hersk: del lista i to igjen og igjen til hver bit er ett tall, og en liste på ett tall er allerede sortert. Flett så halvdelene tilbake med to pekere som beiter på hvert sitt minste tall. Rekursjonstreet vokser nedover, en nær-på flett fyller utlista celle for celle, og hele treet smelter oppover lag for lag — landingen er kjøretiden orden n log n.

Kapittel 4 · Sortering i lineær tid og utvalg

1 video·1m 03
1:03
sortering i lineær tid

Tellesortering: tall i bokser

Hvorfor kan vi sortere ti tall raskere enn n log n når tallene er små? Tellesortering sammenligner ingen par i det hele tatt — den gir hver mulig verdi sin egen boks, slipper input ned i riktig boks i én runde, og tømmer så boksene fra venstre mot høyre rett ut i utlista. Ti tall mellom én og seks faller en etter en ned i seks bokser, så strømmer ut igjen i sortert orden. Kjøretiden lander på orden n pluss k — lineær når k er liten.

Kapittel 5 · Hauger og binære søketrær

1 video·1m 04
1:04
hauger

Binærhaug: sift opp

En binærhaug er det samme objektet sett på to måter — som et tre der hver forelder er større enn barna, og som en flat liste der forelderen til celle i ligger på i minus en delt på to. Når vi setter inn nittitalls verdi nederst i lista, vandrer den oppover ved å bytte plass med forelderen sin så lenge den er større. Tre bytter senere står den på toppen. Hver innsetting koster orden log n fordi banen fra et blad til rota har høyden til treet — og treet har høyde log to av n.

Kapittel 6 · Dynamisk programmering

1 video·1m 11
1:11
dynamisk programmering

Dynamisk programmering: fyll tabellen

Hvorfor er rekursiv Fibonacci så treg, og hva fikser dynamisk programmering? Det rekursive treet for fib av fem eksploderer til femten kall — samme delproblem regnes igjen og igjen. Dynamisk programmering snur problemet på hodet: en tabell fylles nedenfra, hver celle pluss-er sammen de to forrige, hver delsvar lagres én gang. Femten kall mot seks celler — eksponentiell mot lineær. Vist med en levende rekursjonstre der duplikate fib-noder lyser rose, og en DP-tabell der pilene fra forrige to celler tegnes inn før hvert nytt svar dukker opp.

Kapittel 7 · Grådige algoritmer

1 video·1m 04
1:04
grådige algoritmer

Aktivitetsvalg: ta den som slutter først

Sju aktiviteter vil bruke det samme rommet på overlappende tider — hvor mange rekker du? Det grådige trikset er å sortere etter slutttid (ikke start, ikke lengde) og plukke den første som ikke kolliderer med det forrige valget. Søylene tegnes usortert på en tidslinje, glir på plass etter slutt, og en grense-strek vandrer høyrover mens fire aktiviteter lyser amber og de overlappende dimmes. Lander på sortering pluss ett gjennomløp, og at grådig faktisk er optimalt for dette problemet.

Kapittel 8 · Grafer og traversering

1 video·55s
0:55
grafer

Bredde-først søk: bølgen sprer seg

Hvordan finner du korteste antall skritt fra ett punkt til alle andre i en graf? En kø, og lag for lag. Bredde-først søk starter i S, putter naboene i en førstemann-inn-førstemann-ut kø og lar bølgen spre seg utover. Hver node får sin endelige avstand første gangen den dukker opp — fordi FIFO behandler de nærmeste først. Vist med ni levende noder, en pulserende frontbølge som vokser fra ett til to til tre nivåer, og en kø-stripe der bokstaver glir inn på enden og forsvinner fra fronten i takt med at bølgen utvider seg.

Kapittel 9 · Minimale spenntrær

2 videoer·1m 59
1:00
minimale spenntrær

Kruskals algoritme: trygge kanter først

Kruskals algoritme bygger det minimale spenntreet ved å sortere alle kantene etter vekt og så ta hver kant som ikke lager en sirkel. Vist på fem byer og seks veier: vi sorterer kantene fra lett til tung, sveiper ovenfra og ned i lista, og merker hver kant trygg eller sirkel. Fire kanter aksepteres med vekt én, to, tre og seks; to kanter hoppes over fordi de ville lukket en sirkel. Totalvekt tolv, og hele grafen henger sammen — sortér, og vær grådig.

0:59
minimale spenntrær

Prims algoritme: vokse treet utover

Samme minimale spenntre som Kruskal fant — men nå bygget på en helt annen måte. Prims algoritme starter i én by, lar trémengden vokse utover én by av gangen, og tar alltid den letteste kanten som krysser snittet mellom det vi har og det vi mangler. Vist på samme fem byer og seks veier som Kruskal: start i A, så er kantene over snittet AB med vekt én og AC med vekt fire — vi tar AB. Nytt snitt: vi tar BC med vekt tre. Igjen: CD med vekt to. Til slutt DE med vekt seks. Samme totalvekt tolv, samme MST — men her som en voksende klynge i stedet for en sortert liste.

Kapittel 10 · Korteste vei fra én kilde

1 video·1m 01
1:01
korteste vei

Dijkstra: slapp av avstandene

Korteste vei fra ett punkt til alt det kan nå — Dijkstras algoritme. Vi setter startnoden til null og alt det andre til uendelig, og trekker så ut den nærmeste ferskvaren én etter én. Hver gang en ny node trekkes ut, slappes naboene av: går den kjente avstanden ned, oppdateres tallet. Vist på en seks-node-graf med vektede kanter — to klare gevinster (B faller fra fem til tre, C fra ni til seks) og ett forsøk som ikke vinner (D mot E, ni mot sju).

Kapittel 11 · Korteste vei mellom alle par

1 video·1m 08
1:08
korteste vei mellom alle par

Floyd-Warshall: tillat én mellomstopp

Korteste vei fra hver node til hver eneste annen — på én gang. Floyd-Warshall bygger en n×n-tabell ved å tillate én og én mellomstopp: for hver runde k spør vi om veien fra i til j blir kortere hvis vi får lov til å bytte tog innom node k. Vist på fire noder og seks rettede kanter — sju oppdateringer fordelt over fire runder, med en sen vinner der tre til to faller fra fem til to via node fire. Recurrence D[i][j] = min(D[i][j], D[i][k] + D[k][j]) brytes ned til ett spørsmål per celle per runde.

Kapittel 12 · Maksimal flyt

1 video·1m 12
1:12
maksimal flyt

Ford-Fulkerson: send flyt langs forsterkende stier

Maksimal flyt fra kilde til sluk i en kapasitert graf. Ford-Fulkerson kjører i runder: så lenge det finnes en sti fra S til T der hver kant har plass igjen, send flyt lik flaskehalsen langs den stien. Vist på fire noder og fem rettede kanter — tre forsterkende stier på rad: S-A-T sender fire enheter og metter A-T, S-B-T sender seks og metter S-B, og til slutt S-A-B-T henter de to siste enhetene ved å snike forbi den mettede A-T-kanten. Total flyt blir tolv.