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. Det abstrakte algebra, du tidligere har lært, vil blive konkret og "hands-on" ved at forstå, hvordan vi faktisk regner med objekterne.

Hvis du er vild med algoritmer og datastrukturer, så vil du kunne lide dette kursus, fordi algoritmerne er geniale, kompakte og tvinger dig til forene algebra og datalogi i en højere enhed.

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 SageMath, et computer-algebra-system hvor man programmerer i høj-niveau sproget Python. Et element af kurset er, at du skal implementere dit eget bibliotek med avancerede algoritmer for polynomier. 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.
• Beskrive hurtig matrix 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.
• Implementere et bibliotek i Python med algoritmer til at løse 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, med heltal, og med matricer over endelige legemer og heltal. Algoritmer til faktorisering. Multivariate polynomier og deres idealer, Gröbner baser og Buchbergers algoritme. SageMath og Python, og generelt set computer-algebra-systemer. J. von zur Gathen, J. Gerhard, Modern Computer Algebra, 3rd ed. 05. maj, 2020