Datalogiens teoretiske grundlag

2018/2019

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. kapitel 3

Omfang og forventet arbejdsindsats

Det forventes at den studerende bruger 30 timer per ECTS, hvilket for denne aktivitet betyder 150 timer.

Eksamen

Prøver

Prøvens navnDatalogiens teoretiske grundlag
Prøveform
Skriftlig
ECTS5
Bedømmelsesform7-trins-skala
CensurIntern prøve
VurderingskriterierSom angivet i Fakultets vurderingskriterier
http:/​/​www.tech.aau.dk/​digitalAssets/​337/​337434_vurderingskriterier.pdf

Yderligere informationer

Kontakt: Studienævn for datalogi via cs-sn@cs.aau.dk eller 9940 8854

 

Fakta om modulet

Engelsk titelThe Theoretical Foundations of Computer Science
ModulkodeDSNDATFB103
ModultypeKursus
Varighed1 semester
SemesterEfterår
ECTS5
TompladsJa
UndervisningsstedCampus Aalborg
Modulansvarlig

Organisation

StudienævnStudienævnet for Datalogi
FakultetDet Tekniske Fakultet for IT og Design