01415 Computational Discrete Mathematics

2024/2025

Kursusinformation
Computational Discrete Mathematics
Engelsk
5
Kandidat
Kurset udbydes som enkeltfag
Generel retningskompetence (MSc), Mathematical Modelling and Computation
Retningsspecifikt kursus (MSc), Mathematical Modelling and Computation
Teknologisk specialisering (MSc), Mathematical Modelling and Computation
E5B (ons 13-17)
Campus Lyngby
Forelæsninger, grupperegning, hjemmeopgaver
13-uger
E5B
Skriftlig eksamen og bedømmelse af opgave(r)
Skriftlig eksamen: 4 timer
Alle hjælpemidler - uden adgang til internettet
7-trins skala , intern bedømmelse
01018 , Forståelse af begreber fra abstrakt algebra: lineær algebra, ringe, idealer, kvotientringe, isomorfisætningen, endelige legemer. Lidt erfaring med programmering og algoritmer. Studerende der ikke har taget 01018 men har 01017 og 01426 burde kunne følge kurset med, men skal forvente at læse ekstra op på ovenstående algebra.
Minimum 5
Peter Beelen , Lyngby Campus, Bygning 303B, Tlf. (+45) 4525 3022 , pabe@dtu.dk
Maria Montanucci , Lyngby Campus, Bygning 303B, Tlf. (+45) 4525 3047 , marimo@dtu.dk
01 Institut for Matematik og Computer Science
I studieplanlæggeren
Overordnede kursusmål
Dette kursus handler om opfindsomme og effektive metoder til at løse algebraiske spørgsmål, såsom at finde den største fælles divisor af polynomier med koefficienter i et endeligt legeme, eller at finde fælles nulpunkter af givne multivariate polynomier. Vi arbejder i en diskret og eksakt verden: heltal, brøker, endelige legemer og polynomier, og vi søger algoritmer der er hurtige for tilpas store input.

Hvis du er vild med diskret matematik så vil du kunne lide dette kursus, fordi vi dykker dybt ned i smukke og overraskende algebraiske egenskaber, der leder til konkrete opskrifter på at løse beregningsmæssige spørgsmål. Abstrakt algebra vil blive konkret og "hands-on" ved at forstå, hvordan man faktisk regner med objekterne.

Kurset har en matematisk stringent tilgang med beviser af algebraiske sætninger, af algoritmers korrekthed og af deres asymptotiske køretid. Til dette mix tilsætter vi eksperimentering med et computer-algebra-system.
Læringsmål
En studerende, der fuldt ud har opfyldt kursets mål, vil kunne:
  • Forklare hvordan man repræsenterer og regner med meget store heltal, med polynomier, og med polynomier over disse.
  • Beskrive hurtig multiplikation og anvendelser til andre beregninger.
  • Anvende modulære metoder og den kinesiske restklasse-sætning til algebraiske beregninger.
  • Udføre multivariat polynomiumsdivision med rest og beskrive hvilken rolle monomiums-ordenen har.
  • Beregne en Gröbner-basis og beskrive dens relevans for at afgøre medlemsskab i et ideal, samt relaterede problemer.
  • Repræsentere et praktisk problem som ikke-lineære polynomiumsligninger og relationen til idealer af multivariate polynomiumsringe.
  • Bruge et computer-algebra-system til eksperimentelt at arbejde med algebraiske problemer.
  • Analysere den asymptotiske køretid af en algoritme til algebraiske problemer i en realistisk beregningsmodel.
  • Bevise korrektheden af en algebraisk algoritme.
Kursusindhold
Eksakt algebraisk beregning. Aritmetik i endelige legemer, med polynomier over endelige legemer, med heltal, og med matricer over endelige legemer og heltal. Hurtige algoritmer til multiplikation. Idealer i Noeterske ringe, især multivariate polynomiumsringe, Gröbner baser og Buchbergers algoritme.
Litteraturhenvisninger
A standard reference is J. von zur Gathen, J. Gerhard, Modern Computer Algebra, 3rd ed.
Sidst opdateret
02. maj, 2024