Dette er et matematik-kursus der udspringer fra ingeniør-anvendelsen Fejlrettende Koder. De faglige værktøjer vi beskæftiger os med er diskret matematik, algebra og algoritmisk algebra.

Fejlrettende Koder er, trods dens anonyme rolle, i brug overalt: det handler ikke om "koder" som i "programmering", men derimod om repræsentation (kodning) af digital information således at det bliver robust overfor fejl. Tænk fx på en DVD der stadig kan spille selvom den har en ridse, eller mobiltelefonsamtaler der stadig fungerer i stormvejr på trods af atmosfærisk støj. Det er ikke overdrevet at sige, at informationsalderen var umulig uden Fejlrettende Koder, helt på linje med kryptografi.

Mange af de bedste fejlrettende koder vi kender udspringer fra dybsindig algebra. Dette kursus er en introduktion til den fundamentale matematiske model i kodningsteori og til matematikken bag disse algebraiske koder. For at modtageren kan rette fejl der måtte opstå har han brug for effektive algoritmer til at jonglere med de algebraiske objekter; det beskæftiger vi os med både teoretisk algebra og med proof-of-concept implementationer i et computer-algebra system.

Kort sagt: vi vil bruge algebra og udvikle algebraiske værktøjer til at finde gode løsninger på matematiske problemstillinger der er inspireret af anvendelser af Fejlrettende Koder. En studerende, der fuldt ud har opfyldt kursets mål, vil kunne:

• Forklare den matematiske model i fejlrettende koder og dens relevans i kommunikation.
• Udlede, med en konstruktiv metode, at der eksisterer koder med gode parameter.
• Give en (eksponentialtids) algoritme til maximum likelihood afkodning.
• Definere Reed-Solomon koder ved hjælp af polynomier i én variabel og udlede deres grundlæggende parametre.
• Bevise matematisk korrektheden af en afkodningsalgoritme for Reed-Solomon-koder, og implementere denne i et computer-algebra system.
• Definere Reed-Muller koder ved hjælp af polynomier i flere variable og udlede deres grundlæggende parametre.
• Bevise Bézout's sætning om skæringspunkter af algebraiske kurver, og forklare dens rolle i Algebraisk Geometri-koder
• Definere Algebraiske Geometri-koder ved hjælp af algebraiske kurver, udlede deres grundlæggende parametre, og beskrive en afkodningsalgoritme for dem.
• Udføre et projekt om algebraiske koder og evaluer deres effektivitet
• Arbejde effektivt i en gruppe på et projekt med en matematisk og algoritmisk kerne.
• Skrive en rapport om et emne i diskret matematik og computer algebra.

Kurset forløber med forelæsninger og grupperegninger. Vi lægger ud med at introducere den matematiske model indenfor lineær algebra over endelige legemer, og vi undersøger de overordnede rammer indenfor den: Gilbert-Varshamov grænsen og eksponentialtids-afkodning. Dernæst introduceres væsentlige algebraiske koder, Reed-Solomon-koder, hvor univariate polynomier benyttes som algebraisk værktøj. Vi ser på en effektiv afkodningsalgoritme til disse koder, som skal implementeres i computer-algebra-systemet SageMath. Dernæst generaliserer vi til Reed-Muller-koderne vha. multivariate polynomier. Dette motiverer brugen af algebraiske kurver som fører til Algebraiske-Geometri koder, hvor Bézouts sætning er et væsentligt værktøj til analyse. Noter, online kilder, forskningsartikler og/eller uddrag af lærebøger efter behov. Se også Algebra-forskningsgruppens hjemmeside: http:/​/​algebra.compute.dtu.dk 25. april, 2019