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