DM/DMP83: Avanceret Beregnelighed (7.5 ECTS)

STADS: 1506242

Niveau
PhD-kursus

Undervisningsperiode

Udbydes efter behov.

Ansvarlige undervisere
Email: meer@imada.sdu.dk

Yderligere undervisere
www.physik.uni-paderborn.de/~ziegler

Skemaoplysninger
Der er ingen skemaoplysninger for den valgte periode.

Kommentar:
Valgfrit kursus.

Indgangskrav:
Ingen

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

Kursusintroduktion
En stor del af arbejdet inden for teoretisk datalogi bliver brugt til at finde effektive løsninger til datalogiske problemer. Inden man forsøger at finde en hurtig og effektiv løsning, er det dog vigtigt at sikre sig, at en løsning faktisk findes -- for en del problemer, herunder flere af praktisk betydning, kan man vise, at der ingen løsninger findes. Ved at kende de principielle grænser for beregnelighed undgår man at spilde tiden på nyttesløse forsøg på at finde algoritmer for uberegnelige problemer. Som et eksempel vil man i Software Verification gerne kunne tjekke et programs korrekthed og særligt hvorvidt programmet terminer vha. en computer (dvs. effektivt). Imidlertid viser dette problem sig som mange andre relaterede problemer at være beviseligt uafgørligt, ligegyldigt hvor meget tid og hukommelse vi ønsker at bruge på at finde en løsning. Beregninger, der involverer reelle tal, er i endnu højere grad begrænset af de principielle grænser for, hvad algoritmer kan gøre: Hvis det givne input for programmet kun er en approksimation (fx. hvis input kommer fra en fysisk måling og bliver givet med en hvis fejlmargin), bliver fortegnet og mere generelt enhver ikke-kontinuert reel funktion uberegnelig pga. numerisk ustabilitet. Selv under forudsætning af at man kan foretage beregninger med reelle tal eksakt (BSS-modellen), forbliver mange funktioner uberegnelige. Dette kursus giver en introduktion til dette område inden for beregnelighed.

Forventet læringsudbytte


Emneoversigt
Beregningsmodeller, beregningshierarki, uendelige ord, rekursiv analyse, algebraisk beregnelighed.

Litteratur

• M.Ziegler: Lecture Notes on "Advanced Computability, (52 sider).
• K.Weihrauch : "A Simple Introduction to Computable Analysis" Electronic Colloquium on Computational Complexity , 1995.
• L.Blum, M.Shub, S.Smale : "On a Theory of Computation and Complexity over the Real Numbers", pp.1-46 in Bulletin of the American Mathematical Society vol. 21(1) (46 sider).
• T.Chadzelek, G.Hotz : Analytic Machines", pp.151-167 in Theoretical Computer Science vol. 219 (17 sider), 1999.

Pensum
Se pensumbeskrivelse.

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

Forudsætningsprøver
Ingen

Eksamen- og censurform:
Mundtlig eksamen, intern censur, karakter efter 13-skalaen. Obligatorisk opgave, der skal bestås for at gå til eksamen.

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

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

Sprog
Der er ikke registreret nogle oplysninger om undervisningssproget.

Bemærkninger
Kurset passer fint sammen med kurset om algoritmer med reelle tal der undervises af Klaus Meer i samme semester. Dette andet kursus fokuserer på kompleksiteten i BSS-modellen. Således vil begge kurser tilsammen kaste lys over de beregningsmæssige aspekter for problemer med reelle tal fra forskellige synsvinkler.

Kursustilmelding
Se tilmeldingsfrister.

Pris for åben uddannelse
Se priser for enkeltkurser.

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