Datalogiens teoretiske grundlag

2020/2021

Modulets indhold, forløb og pædagogik

FORMÅL          
At den studerende tilegner viden, færdigheder og kompetencer inden for grundlæggende matematiske discipliner, som er væsentlige i mange datalogiske sammenhænge. Formålet er endvidere at bibringe disse færdigheder på en måde, som har en klar relevans, og tydelige anvendelser, inden for algoritmer, datastrukturer og programudvikling.

BEGRUNDELSE    
Der er mange fagligheder i datalogi/software som kræver et solidt matematisk fundament.

Læringsmål

Viden

  • Mængdelære
    • Begreberne mængde, element i mængde; notation, Venn diagram
    • Mængdebyggernotation
    • Inklusion, lighed mellem mængder, tom mængde, potensmængde, kartesisk produkt
    • Mængdeoperationer
      • Foreningsmængde, fællesmængde, komplementærmængde
    • Mængderne af naturlige tal, rationelle tal og reelle tal
  • Relationer
    • Binære relationer, transitiv afslutning
    • Ækvivalensrelationer(refleksiv, symmetrisk, transitiv), ækvivalensklasser, klassedeling
    • Ordningsrelation (antisymmetri)
  • Funktioner
    • Definitionsmængde, værdimængde
    • Injektiv, surjektiv, bijektiv funktion
    • Specielle funktioner
      • Polynomier, exponential- og logaritme-funktioner
  • Udsagnslogik
    • Basal definition af operatorer
    • Ækvivalens mellem udsagn, distributive love, de Morgans love, m.m.
    • Sandhedstabeller
    • Konjunktiv og disjunktiv normalformer
  • Prædikatlogik
    • Prædikater, alkvantor, eksistenskvantor
    • Ækvivalens, de Morgans love
    • Normalformer i prædikatlogik
  • Bevisteknikker
    • Bevis ved modstrid, slutningsregler
    • Bevis ved induktion på de naturlige tal
  • Grundlæggende talteori
    • Divisibilitet, modulær aritmetik, Euklids algoritme
  • Grundlæggende kombinatorik
    • Permutationer, kombinationer, binomialformlen
  • Store-O notation med anvendelser på tidskompleksitet
  • Rekursion og induktion
    • Rekursiv definition af funktioner
    • Rekursiv definition af mængder og simple strukturer: strenge og træer
    • Ræsonnementer om rekursivt definerede strukturer, strukturel induktion

Færdigheder

  • kunne gennemføre beviser for resultater indenfor kursets emner ved hjælp af de i kurset behandlede bevisteknikker
  • kunne estimere tidskompleksiteten af simple algoritmer
  • kunne gøre brug af de fornødne skriftlige færdigheder i disse sammenhænge

Kompetencer

  • kunne identificere og anvende relevante matematiske teorier og teknikker, som er nødvendig til analyse af virkelige problemer
  • kunne anvende matematiske teknikker som basis for udvikling af algoritmiske løsninger af et givet problem

Undervisningsform

Undervisningen tilrettelægges i henhold til de generelle undervisningsformer for uddannelsen, jf. § 17

Omfang og forventet arbejdsindsats

Kursusmodulets omfang er 5 ECTS svarende til 137,5 timers studieindsats.

Eksamen

Prøver

Prøvens navnDatalogiens teoretiske grundlag
Prøveform
Skriftlig eller mundtlig
ECTS5
Bedømmelsesform7-trins-skala
CensurIntern prøve
VurderingskriterierVurderingskriterierne er angivet i Universitetets eksamensordning

Yderligere informationer

 

 

Fakta om modulet

Engelsk titelThe Theoretical Foundations of Computer Science
ModulkodeB-MAT1-DTGC
ModultypeKursus
Varighed1 semester
SemesterEfterår
ECTS5
UndervisningssprogDansk
TompladsJa
UndervisningsstedCampus København
Modulansvarlig

Organisation

StudienævnStudienævn for Matematiske Fag
InstitutInstitut for Matematiske Fag
FakultetDet Ingeniør- og Naturvidenskabelige Fakultet