DM/DMP82: Kompleksitetsteori over reelle tal og algoritmer i semi-algebraisk gemometri (7.5 ECTS)

STADS: 1506042

Niveau
PhD-kursus

Undervisningsperiode

Udbydes efter behov.

Ansvarlige undervisere
Email: meer@imada.sdu.dk

Skemaoplysninger
Der er ingen skemaoplysninger for den valgte periode.

Kommentar:
Kruset er et læsekursus.Valgfrit kursus.

Indgangskrav:
Ingen

Faglige forudsætninger:
Ingen. DM19 skal være fulgt.

Kursusintroduktion
Kurset vil give en introduktion til kompleksitetsteori over reelle tal og algoritmer, der er vigtige i forbindelse med semi-algebraisk geometri. Den grundlæggende model brugt i beregningsteori er Turing maskinen. Den bliver brugt til at beskrive algoritmer der behandler diskrete strukturer (f.eks. grafer, endelige alfabeter, o.l.). Men inden for de sidste 15-20 år har der været en stor interesse for alternative modeller til beregning. Velkendte eksempler er kvantecomputere, neurale netværk, DNA- computere og algebraiske modeller. For mange beregningsproblemer er en sådan alternativ model en mere naturlig ramme, for at fange visse aspekter af problemet. I dette kursus er den centrale beregningsmodel den reelle model introduceret af Blum, Shub og Smale i 1989. Her er reelle tal de basale elementer. Problemer man behandler i en sådan model har typisk en såkaldt semi-algebraisk struktur. Eksempler er:
- problemer i robotteori (f.eks. robot motion planning, piano movers problems, sti-finding o.l.)
- problemer i beregningsgeometri (f.eks. finde forbundne komponenter i mængder, teste for om mængden er tom, triangulaseringer o.l.)
- generelle problemer, der kan formaliseres via systemer af polynomielle (u-)ligheder (f.eks. kinematics, optimeringsteori, udvikling)
Målet med kurset er at give en præcis introduktion til BSS modellen. Vi definerer og studerer kompleksitetsklasser over reelle tal, og giver basale algoritmer relateret til dissse klasser. Blandt de centrale algoritmer der bliver studeret i kurset er Tarskis algoritme til eliminering af kvantorer over reelle tal, en af de mest vigtige algoritmer for problemer der involverer polynomier.

Forventet læringsudbytte


Emneoversigt
Alternative beregningsmodeller, algoritmer over reelle tal, NP komplethed over reelle tal, Tarskis algoritme.

Litteratur

• L. Blum, F. Cucker, M. Shub, S. Smale: Complexity and real computation.(Vi behandler kapitlerne 1-7, 16 og 21 (ca. 183 sider). Der vil bliv uddelt yderligere noter som K. Meer er i gang med at forberede. Disse vil fylde ca. 110 sider.) , Springer 1997, ISBN: 0-387-98281-7.

Pensum
Se pensumbeskrivelse.

Kursets hjemmeside
Dette kursus benytter e-learn (blackboard).

Forudsætningsprøver
Ingen

Eksamen- og censurform:
Mundtlig eksamen med ekstern censur. Karakter efter 13-skalaen. Obligatoriske opgaver skal beståes for at komme til eksamen.

Vejledende timetal
På naturvidenskab er undervisningen tilrettelagt efter trefasemodellen dvs. intro, trænings- og studiefasen.

Forelæsninger (30 timer), eksaminatorier (30 timer).
Aktiviteter i studiefasen

Sprog
Der er ikke registreret nogle oplysninger om undervisningssproget.

Bemærkninger
1.) Kurset passer godt sammen med kurset Avanceret Beregnelighed, som undervises sideløbende af M. Ziegler. Dette kursus omhandler endnu en alternativ beregningsmodel over reelle tal. Begge kurser sammen kaster lys over beregningsaspekter af problemer over reelle tal, men fra forskellige vinkler.
2.) Kurset kan være interessant også for matematik studerende. Især studerende der har fulgt kurset MM85 vil se en tæt sammenhæng med Godels Ufuldstændighedssætning. Tarskis algoritme viser at Godels Ufuldstændighedssætning ikke holder over strukturer som de reelle tal.

Kursustilmelding
Se tilmeldingsfrister.

Pris for åben uddannelse
Se priser for enkeltkurser.

Denne kursusbeskrivelse var gyldig fra 1. februar 2005 til 31. januar 2011.