NDAB15008U Diskret matematik og algoritmer (DMA)

Viden om

• grundlæggende matematisk metode,
• logik, elementær talteori og tælleproblemer,
• mængder og relationer,
• funktioner,
• asymptotisk tids- og pladskompleksitet (herunder opstilling og løsning af rekursionsligninger) samt eksempler på deres anvendelser,
• abstrakt beregningsmodel (RAM),
• basale datastrukturer og operationer på disse (herunder lister, stakke, køer, binære søgetræer, hashing),
• grafer (herunder træer) og relaterede algoritmer (for eksempel dybde-først, bredde-først og deres anvendelser),
• sorteringsalgoritmer

Færdigheder i

• at løse problemer inden for udvalgte videnspunkter fra listen ovenfor herunder identificere relevante algoritmer,
• udvikling og implementering af simple algoritmer og datastrukturer,
• skriftlig problemformulering og præsentation af løsninger,
• studieteknik, projektstyring, og gruppearbejde

Kompetencer til selvstændigt at

• formulere simple matematiske argumenter og beviser
• knytte forbindelse mellem kursets matematiske emner og datalogiske problemstillinger herunder
  • identificere relevante matematiske værktøjer blandt kursets emner til løsning af datalogiske problemstillinger
  • implementere udvalgte algoritmer og datastrukturer
• udvælge metoder og teoridele til løsning af problemer inden for kursets vidensområde, herunder specielt
  • udføre formelle logiske operationer på matematiske udsagn,
  • analysere kombinatoriske problemstillinger såvel ved brug af tælleargumenter som algebraiske operationer,
  • genkende forskellige former for grafer og anvende centrale algoritmer knyttet til sådanne,
  • opstilling af rekursive ligninger og løsning af disse ved brug af rekursionstræer og substitutionsmetode
• bestemmelse af køretid og pladsforbrug herunder
  • gøre brug af asymptotisk notation til at angive størrelsesordenen af en funktion,
• kunne analysere fordele og ulemper ved udvalgte algoritmer og datastrukturer