NDAB15008U Diskret matematik og algoritmer (DMA)

Årgang 2016/2017
Engelsk titel

Discrete Mathematics and Algorithms (DMA)

Uddannelse

Bacheloruddannelsen i datalogi

Kursusindhold

Kurset giver en introduktion til diskret matematik, algoritmer og datastrukturer. Fokus i den matematiske del af kurset er matematisk metode og matematiske værktøjer som bruges i løsningen af datalogiske problemstillinger. Vidensemnerne i målbeskrivelsen introduceres, og der arbejdes med emnerne for at opbygge de forventede færdigheder og kompetencer.

Målbeskrivelser

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
  • sorteringsalgoritmer


Færdigheder i at

  • formulere simple matematiske argumenter og beviser, herunder knytte forbindelse mellem kursets matematiske emner og datalogiske problemstillinger, samt identificere relevante matematiske værktøjer blandt kursets emner til løsning af datalogiske problemstillinger
  • 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
  • bestemme køretid og pladsforbrug herunder
    • gøre brug af asymptotisk notation til at angive størrelsesordenen af en funktion
  • analysere fordele og ulemper ved udvalgte algoritmer og datastrukturer
  • præsentere løsninger skriftligt

 

Kompetencer til selvstændigt at

  • løse problemer inden for udvalgte videnspunkter fra listen ovenfor herunder identificere relevante algoritmer
  • udvikle simple algoritmer og datastrukturer
     

Offentliggøres på kursets hjemmeside ved kursusstart

Kompetencer svarende til at kurset "Programmering og problemløsning" følges senest samtidigt.
Kurset vil blande forelæsninger, klasseundervisning, gruppeøvelser og individuelle opgaver.
  • Kategori
  • Timer
  • Forberedelse
  • 124
  • Forelæsninger
  • 54
  • Projektarbejde
  • 144
  • Øvelseshold
  • 90
  • I alt
  • 412
Point
15 ECTS
Prøveform
Løbende bedømmelse
Kurset organiseres ud fra en ugentlig cyklus med obligatoriske opgaver (ialt 12-14), som alle på nær en skal bestås for at bestå kurset. Der vil være mulighed for genaflevering. Størrelsen af opgaverne vil variere og vil blive offentliggjort ved kursusstart. Opgaveaflevering sker i Absalon.
Bedømmelsesform
bestået/ikke bestået
Censurform
Ingen ekstern censur
Flere interne bedømmere
Reeksamen

30 minutters mundtlig eksamen inklusive votering (uden forberedelse) i fuldt pensum. Skriftlige hjælpemidler (notater og bøger mv.) er tilladt.

Kriterier for bedømmelse

Den studerende skal på tilfredsstillende måde godtgøre, at han/hun lever op til fagets målbeskrivelse.