DM582: Avancerede algoritmer

Intern kursuskode

DM582

Indgangskrav

Kurset kan ikke følges af studerende, der har bestået MM541, DM538 eller DM551/MM851.

Faglige forudsætninger

Studerende, der følger kurset, forventes at

have kendskab til basale algoritmer og datastrukturer såvel som implementering af disse i et imperativt programmeringssprog, herunder stakke, køer, søgetræer og prioritetskøer, såvel som sorteringsmetoder og basale grafalgoritmer (eks. fra DM578),
have kendskab til algoritmedesignteknikker og være i stand til at analysere algoritmer ved hjælp af asymptotisk analyse og sammenligne asymptotiske resultater (eks. fra DM578),
være i stand til at anvende basal matematisk argumentation, herunder logiske udtryk, beviser ved induktion, modstridsargumenter og tælleteknikker (eks. fra DM549) og
være i stand til at anvende basal diskret sandsynlighedsteori (eks. fra AI501).

Formål

Kurset har til formål at sætte den studerende i stand til at anvende randomisering og probabilistiske metoder i design og analyse af algoritmer og gøre den studerende fortrolig med avancerede algoritmiske emner som f.eks. strømning i netværk og strengsøgning, samt generelle teknikker til etablering af øvre og nedre grænser for algoritmers tidskompleksitet, herunder amortiseret analyse.

Målbeskrivelse

Læringsmålet for kurset er, at den studerende demonstrerer evnen til at:

Anvende emner fra diskret sandsynlighedsteori til at estimere den forventede køretid for algoritmer
Udvikle og analysere basale randomiserede algoritmer
Anvende teknikker fra universel hashing til at vælge hashfunktioner med god forventet opførsel
Formulere en strømningsmodel for problemer, der ligner dem fra kurset
Vurdere hvilken strengsøgningsteknik, man skal anvende på et givent problem
Anvende teknikker fra kurset til at vurdere den amortiserede tidskompleksitet af operationer på en datastruktur
Etablere nedre grænser for tidskompleksiteten af algoritmiske problemer

Indhold

Kurset indeholder følgende hovedområder:

Randomiserede algoritmer
Probabilistiske analyser af algoritmer
Den probabilistiske metode
Universel og perfekt hashing
Strømning i netværk
Strengsøgning
Amortiseret analyse
Nedre grænser

Litteratur

Se pensum på itslearning.

Eksamensbestemmelser

Eksamenselement a)

Tidsmæssig placering

Forår og juni

Udprøvninger

Portfolio med mundtlig forsvar

EKA

N330070102

Censur

Ekstern prøve

Bedømmelse

7-trinsskala

Identifikation

Fulde navn og SDU brugernavn

Sprog

Følger, som udgangspunkt, undervisningssprog

Varighed

Mundtlig prøve, 25 minutter

Hjælpemidler

Alle almindelige hjælpemidler tilladt

Ved mundtlig prøve: Ingen hjælpemidler tilladt

ECTS-point

7.5

Uddybende information

Portfolio eksamen består af to elementer:

1.Multiple-choice test undervejs i kurset

2.Mundtlig prøve

Bedømmelsen af element 1 finder sted i forbindelse med afviklingen af element 2. Karakteren gives med udgangspunkt i element 2, men hvor element 1 kan trække karakteren op eller ned med et karaktertrin.

Reeksamen: mundtlig prøve (præcis som element 2 i den ordinære).

Vejledende antal undervisningstimer

70 timer per semester

Undervisningsform

Skemalagte undervisningstimer:

Antal undervisningstimer i alt: 70

Heraf:

Fællestimer i klasselokale/auditorium: 40

Holdtimer i klasselokale: 30

Strukturelt afvikles skematimerne med gennemgang af nyt stof cirka halvdelen af gangene og nærmere diskussion af egenskaber og varianter omkring stoffet i den anden halvdel. I den første del benyttes en modificeret udgave af klassisk forelæsning, hvor fagets grundbegreber og metoder præsenteres, med såvel teori som eksempler baseret på konkrete data. I disse timer er der mulighed for spørgsmål og diskussion. I den anden halvdel arbejdes der med opgaver og diskussionsemner, som relaterer sig til indholdet i de forudgående forelæsninger. I disse timer er der mulighed for at arbejde specifikt med særligt vanskelige emner. Også i denne forbindelse er der mulighed for at bringe spørgsmål op.

Andre planlagte undervisningsaktiviteter:
Løse opgaver, læse den tildelte litteratur, øve anvendelse af tilegnet viden.

Ansvarlig underviser

Navn	E-mail	Institut
Kim Skak Larsen	kslarsen@imada.sdu.dk	Algoritmer

Skemaoplysninger

Odense

Vis fuldt skema

Administrationsenhed

Institut for Matematik og Datalogi (datalogi)

Team hos Registratur

NAT

Udbudssteder

Odense

Anbefalede studieforløb

Profil	Uddannelse	Semester	Udbuds periode

Overgangsordninger

Overgangsordninger beskriver, hvordan et kursus erstatter et andet kursus, når der ændres i et studieforløb.

Hvis der er lavet en overgangsordning for et kursus vil den fremgå af oversigten.
Se overgangsordninger for alle kurser på Det Naturvidenskabelige Fakultet.