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 og algebra 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. En studerende, der fuldt ud har opfyldt kursets mål, vil kunne:

• Forklare hvordan man repræsenterer og regner med endelige legemer og med polynomier over endelige legemer.
• 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.

Eksakt algebraisk beregning. Aritmetik i endelige legemer, med polynomier over endelige legemer samt 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. A standard reference is J. von zur Gathen, J. Gerhard, Modern Computer Algebra, 3rd ed. 19. maj, 2025