NDAB15008U Diskret matematik og algoritmer (DMA)

Årgang 2020/2021
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)
  • 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
     
Undervisningsmateriale

Offentliggøres på kursets Absalon-side 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
  • Forelæsninger
  • 54
  • Forberedelse (anslået)
  • 124
  • Øvelser
  • 90
  • Projektarbejde
  • 144
  • I alt
  • 412
Skriftlig
Individuel
Kollektiv
Løbende feedback i undervisningsforløbet
Point
15 ECTS
Prøveform
Løbende bedømmelse
Kurset organiseres ud fra en ugentlig cyklus med obligatoriske opgaver (ialt 11-13), 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

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

Kriterier for bedømmelse

Se målbeskrivelsen.