Skip to main content

Specialisering i Algoritmer

På SDU er algoritmer et fokusområde med en usædvanlig stor og stærk forskningsgruppe med mere end 9 forskere og et stort udvalg af kurser.

Ud over at give dig ekspertise inden for konkrete applikationsområder gør en solid baggrund i algoritmer det nemt at sætte sig ind i andre datalogiske fagområder. I et fag som datalogi, som er i rivende udvikling, er evnen til at tilpasse sig konstant forandring vigtig for en vellykket karriere. 

Portræt af Joan Boyar

De fleste af vores algoritmekurser har fokus på disse stofområder:

  • Organisering af store datasæt, der letter hurtige søgninger og beregninger
  • Ressourceoptimering
  • Områdespecifikke algoritmer og applikationer

Portræt af Lene Monrad Favrholdt

Kurser

I studieåret 2021/2022 udbyder vi følgende kurser inden for algoritmer:

Datastrukturer er et af de emner, der er helt centralt i både teoretisk såvel som mere anvendelsesorienteret datalogi. Algoritmen med den bedst mulige tidskompleksitet udvikles ofte i samspil med, at en datastruktur med præcis de rigtige egenskaber findes. Ligeledes er valg eller design af en passende datastruktur ofte det, som kan gøre forskellen mellem et stort program, der kører alt for langsomt, og et, der kan tilfredsstille brugernes behov.

Formålet med kurset er at give dig et solidt kendskab til avancerede datastrukturer, sådan at disse fremover vil indgå som en naturlig del af kompliceret problemløsning og programmering.

Ansvarlig underviser: Kim Skak Larsen

Formålet med dette kursus er at sætte dig i stand til at løse en bred vifte af ikke-trivielle diskrete beregningsmæssige problemer inden for datalogi ved at anvende avancerede algoritmiske ideer, grafteoretiske tilgange, viden fra beslægtede områder af diskret matematik og kompleksitetsteori på problemer motiveret fra eller opstået i kemi.

Kurset giver et videnskabeligt grundlag for at skrive et speciale, der har til formål at anvende kernedatalogiske tilgange til relevante spørgsmål i kemi, biologi, fysik eller matematik.

Ansvarlig underviser: Daniel Merkle

Læs hele kursusbeskrivelsen

Dette kursus giver dig en introduktion til diskret optimering og fokuserer på to af dets løsningsparadigmer: constraint-programmering og optimeringheuristik og metaheuristik.

Constraint-programmering forsøger at løse problemer ved at modellere dem ved hjælp af et deklarativt programmeringssprog og derefter bruge standarddeduktionsregler, der svarer til logisk ræsonnement, for at reducere det rum, hvor der søges efter løsninger.

Optimeringsheuristik og metaheuristik er de generelle principper for at finde næsten optimale løsninger. De er den sidste udvej, hvis et problem viser sig at være beregningsmæssigt for svært til at blive løst nøjagtigt. De er ofte inspireret af naturen. For eksempel er lokale søgeteknikker baseret på forsøg-fejl-princippet, hvilket er en mulig måde, hvorpå mennesker løser problemer.

For at få succes skal de generelle principper tilpasses det specifikke problem. Derfor giver kurset dig også praktisk erfaring gennem programmeringsopgaver.

Ansvarlig underviser: Marco Chiarandini

Læs hele kursusbeskrivelsen

Formålet med kurset er at studere kryptologi, som består af kryptografi og kryptanalyse – konstruktion af hemmelige koder og teknikker til at bryde dem. Vi vil også studere kryptografiske protokoller i forbindelse med informationssikkerhed. Mange af de nyere kryptosystemer og kryptografiske protokoller er baseret på talteoretiske problemer, så disse problemer og algoritmer for dem vil også blive diskuteret sammen med den algebra, der er nødvendig for at forstå dem.

Kryptologi har mange anvendelser, blandt andet private meddelelser, internethandel (kryptering af kreditkortnumre, elektronisk pengeforsendelse, sikre metoder med hensyn til elektroniske underskrifter på dokumenter etc.), autenticitet (pålideligheden af PIN-koder til betalingskort og logins) og "secret sharing" (hvor et bestemt antal ud af en gruppe personer skal deltage, før en transaktion kan udføres).

Faglige forudsætninger: Studerende, der følger kurset, forventes at have kendskab til lineær algebra, kunne forstå og lave beviser, bruge grundlæggende sandsynlighed og analysere algoritmer.

Ansvarlig underviser: Joan Boyar

Læs hele kursusbeskrivelsen

Kurset har til formål at sætte dig i stand til at:

  • anvende teori og metoder fra kombinatorisk optimering til at ræsosnere om problemer af kombinatorisk natur
  • udvikle effektive algoritmer til løsning af praktiske problemer, som i natur ligner dem, der behandles i kurset
  • kunne argumentere for, at et kombinatorisk optimeringsproblem er NP-hårdt, og foreslå metoder til at opnå approksimative løsninger ved hjælp af de metoder, man lærer i kurset
  • udvikle ny teori og metoder for kombinatoriske optimeringsproblemer, som er beslægtede med dem, man møder i kurset

Faglige forudsætninger: Studerende, der følger kurset, forventes at have kendskab til basale datastrukturer og grafalgoritmer,  problemkompleksitet, basale approksimationsalgoritme. Kendskab til lineær programmering og basal teori for strømning i netværk er en fordel, men ikke en forudsætning.

Ansvarlig underviser: Jørgen Bang-Jensen

Læs hele kursusbeskrivelsen


Lineær og heltalsprogrammering er et felt i skæringspunktet mellem matematik og datalogi, der har set en stor udvikling i de sidste 60 år. Det giver de værktøjer, der er kernen i operationsanalyse – den disciplin, der giver analysemetoder til at hjælpe at træffe bedre beslutninger.'

Det primære fokus for lineær og heltalsprogrammering er på ressourcebegrænsede optimeringsproblemer, der kan beskrives ved hjælp af lineære uligheder og en lineær objektivfunktion. Disse problemer kan opstå i beslutningsprocessen i flere sammenhænge, såsom produktionsindustri, logistik, sundhedssektor, uddannelse, finans, energiforsyning og med flere. Indholdet af kurset har derfor en høj praktisk relevans.

Kursets formål er at sætte dig i stand til at anvende matematisk modellering til at løse praktiske optimeringsproblemer, og arbejde med matematiske softwaresystemer til at finde numeriske løsninger på disse problemer.

Faglige forudsætninger: Studerende, der følger kurset, forventes at have kendskab til lineær algebra.

Ansvarlig underviser: Marco Chiarandini

Læs hele kursusbeskrivelsen

Kursets fokus er på avancerede løsningsteknikker til matematiske optimeringsproblemer, der opstår fra konkrete anvendelser i skedulering og ruteplanlægning.

Eksempler på anvendelser er: flow shop og jobshop skedulering i produktion, ressourcebegrænset aktivitetsplanlægning, bemanding og arbejdshold planlægning, tidsplanlægning og køretøj ruteplanlægning med tidsvinduer.

Kurset sigter på at give teorien bag løsningsmetoderne og frem for alt praktisk erfaring med at implementere dem på numeriske instanser af disse optimeringsproblemer.

Faglige forudsætninger: Studerende, der følger kurset, forventes at have kendskab til lineær og heltalsprogrammering, for eksempel fra kurset DM871.

Ansvarlig underviser: Marco Chiarandini

Læs hele kursusbeskrivelsen

Kryptografi giver algoritmer, der er afgørende for sikkerheden (for eksempel fortrolighed, integritet og autenticitet) af vores moderne meddelelser.

Disse algoritmer udgør dog kun én søjle af sikkerhed; det er også vigtigt, at implementeringen af algoritmerne er effektiv og sikker. Dette kursus har fokus på, hvordan man opnår høj ydeevne selv for små embeddede systemer ved implementering af kryptografiske (dvs. matematiske) algoritmer, og hvordan man beskytter en implementering mod sidekanalangreb, der ikke leder efter svagheder i algoritmer eller deres implementering, men i de fysiske egenskaber af computerplatforme.

Undervisningen ledsages af praktiske tutorials om effektiv implementering, sidekanalanalyse og modforanstaltninger.

Faglige forudsætninger: Studerende, der følger kurset, forventes at have kendskab til grundlæggende kryptologi, for eksempel fra kurset DM557: Netværk og sikkerhed.

Ansvarlig underviser: Ruben Niederhagen

Dette kursus svarer fagligt til den første halvdel af MM856.

Faglige forudsætninger: Studerende, der følger kurset, forventes at have basal kendskab til grafteori og diskret matematik

Ansvarlig underviser: Anders Yeo

Læs hele kursusbeskrivelsen

Kurset giver en introduktion til grafteori og andre mere avancerede emner inden for dette område. Vi vil dække emner inden for både orienterede og ikke-orienterede  grafer.

Faglige forudsætninger: Studerende, der følger kurset, forventes at have basal kendskab til grafteori og diskret matematik.

Ansvarlig underviser: Anders Yeo

Læs hele kursusbeskrivelsen

Alle kurserne forudsætter forudgående kendskab til algoritmer og datastrukturer, såvel som grundlæggende diskret matematik. Nogle af kurserne har yderligere faglige forudsætninger, for eksempel inden for lineær algebra og kompleksitetsteori.

Anbefalet studieforløb
Efterår 2021
DM840 DM854 MM856
Forår 2022
DM803 DM867 valgfrit

Som valgfri specialiseringskurser kan du tage enten DM871 og DM872 eller DM8xx: Cryptographic Engineering.

Specialeprojekter

Nedenfor kan du se eksempler på specialetitler inden for algoritmer:

  • European football placement problems - complexities and exact solutions
  • On-line graph colouring
  • Aircraft routing
  • Lattice-based cryptography
  • Nearest neighbour search in high-dimensional spaces
  • Theoretical aspects of computer-aided chemical synthesis design
Studievejlederne Det Naturvidenskabelige Fakultet Syddansk Universitet
  • Campusvej 55
  • Odense M - DK-5230
  • Telefon: +45 6550 4387

Sidst opdateret: 19.02.2021