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

Fejlrettende Koder er, trods dens anonyme rolle, i brug overalt: begrebet dækker bredt over repræsentationer 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 satellit-overførsel 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.

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 og med proof-of-concept implementationer i computer-algebra systemet Sage.

Fejlrettende Koder har vist sig at være et fundamentalt koncept i computervidenskab, og det har mange overraskende anvendelser udenfor fejlfri kommunikation. Vi vil løbende motivere modellen og matematikken med sådanne anvendelser. En studerende, der fuldt ud har opfyldt kursets mål, vil kunne:

• Forklare den matematiske model i fejlrettende koder og dens relevans i kommunikation.
• Eksemplificére anvendelser hvor algebraiske koder bliver brugt og forklare kodernes rolle i løsningerne
• Sammenligne forskellige koder i brug i anvendelser baseret på deres grundlæggende parametre.
• Definere Reed-Solomon koder og udlede deres grundlæggende parametre.
• Forklare og implementere en afkodningsalgoritme for Reed-Solomon-koder.
• Grundigt teste en implementation af en algebraisk baseret algoritme.
• Udføre et projekt henover flere uger omhandlende algebraiske koder i en større sammenhæng, eller analyse af egenskaber af algebraiske koder.
• Forklare indholdet af en forskningsartikel eller et afsnit af en PhD-niveau lærebog om diskret matematik og algoritmer.
• Evaluere en kodnings-baseret løsning til et specifikt ingeniørproblem, eller bevise teoretiske egenskaber ved algebraiske koder.
• Arbejde effektivt i en gruppe på et projekt med en matematisk og algoritmisk kerne.
• Planlægge en tidslinje for projektet og sammenfatte fremskridt under ugentlige møder for en projekt-interessent.
• Skrive en rapport om et emne i diskret matematik og computer algebra.

Kurset består af en fælles del og en projektdel.

I den fælles del introduceres metodologien Fejlrettende Koder samt begrebet lineære koder, deres grundlæggende parametre og hvilken indflydelse det har på fejlretnings-egenskaber. Derefter introduceres Reed-Solomon koder og en effektiv afkodningsalgoritme til dem. Denne del afsluttes med et projekt hvor Reed-Solomon koderne og afkodning beskrives og implementeres.

I projektdelen arbejder grupperne med valgfri emner, inspireret af en liste af foreslåede problemer. Fokus kan være teoretisk (dvs. analyse eller udvikling af gode koder) eller anvendt (dvs. løsning af ingeniørmæssige problemer vha. kodningsteori). Udfaldet bliver en rapport med et matematisk og evt. algoritmisk indhold samt evt. proof-of-concept implementation. Noter udleveret i starten af kurset. Online kilder, forskningsartikler og lærebøger efter behov. Se også Algebra-forskningsgruppens hjemmeside: http:/​/​algebra.compute.dtu.dk 28. november, 2016