TDT4120 Algoritmer og datastrukturer

Fra NablaWiki
Gå til: navigasjon, søk
TDT4120 Algoritmer og datastrukturer
Foreleser: Magnus Lie Hetland
Obligatorisk for: Industriell matematikk høsten 3. klasse.
Pop. forkortelser: Algdat
Øvinger: Teori- og praksisøvinger (programmering)
Evalueringsform: Skriftlig eksamen
Bøker: Cormen, Leiserson, Rivest, Stein: Introduction to algorithms
Nettside: http://www.idi.ntnu.no/emner/tdt4120/

Algoritmer og datastrukturer tar for seg en grunnleggende introduksjon til algoritmer for løsing av problemer på datamaskiner. Mye av pensum går ut på forskjellige metoder for søk gjennom datastrukturer sånn som trær og grafer (veldig mange problemer kan reduseres til en form for søk gjennom grafer). Viktige algoritmer er de som ser på korteste vei mellom to noder i en graf, maksimal flyt gjennom et nettverk, etc. Det blir også undersøkt hvilke strukturer for lagring av data som optimaliserer søk, innsetting av nye elementer, osv. Det blir lagt vekt på hvor fort en algoritme kjører som funksjon av problemstørrelsen.

Til slutt ser man på klassene P og NP, hvor P er klassen av problemer hvor man har funnet algoritmer som kjører i polynomiell tid, mens NP er en klasse av problemer hvor det ennå ikke finnes algoritmer som kjører i polynomiell tid, og at disse derfor er veldig tunge å beregne.

Øvingene er delt opp i teori- og praksisøvinger. Praksisøvingene innebærer ofte ganske mye jobbing. Det er ikke nødvendig å gjøre alle for å få nok poeng til å gå opp til eksamen, men det kan være lurt å prøve for å få en bedre forståelse av hva som foregår.