Enkeltfag 5 ECTS

Computational Discrete Mathematics

Overordnede kursusmål

Dette kursus handler om opfindsomme og effektive metoder til at løse algebraiske spørgsmål, såsom at faktorisere et polynomium 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.

See course description in English

Læringsmål

  • 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.
  • Faktorisere et polynomium over et endeligt legeme med en effektiv metode.
  • 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. Algoritmer til faktorisering. Idealer i Noeterske ringe, især multivariate polynomiumsringe, Gröbner baser og Buchbergers algoritme.

Anbefalede forudsætninger

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.

Undervisningsform

Forelæsninger, grupperegning, assignments

Fakultet

Pladsbegrænsning

Minimum 5.

Vær opmærksom på, at dette enkeltfagskursus har et minimumskrav for antal deltagere for at kunne oprettes. Du får besked om, hvorvidt kurset oprettes senest 8 dage før kursusstart.

Se kurset i kursusbasen

Tilmelding

Sprog
Varighed

13 uger

Institut

Compute

Sted

DTU Lyngby Campus

Kursus ID 01415
Kursustype Kandidat
Semesterstart Uge 35
Semester slut Uge 48
Dage ons 13-17
Pris

7.500,00 kr.

Vær opmærksom på dette kursus har deltager begrænsninger. Læs mere

Tilmelding