I00016 (I00016)
Berekenbaarheid*
< 2006/2007 > 05-02-2007 t/m 01-07-2007 () L
Informatica - Bachelor (2003) Grondslagen (3 ec)
Informatica - Master na HBO Artificial Intelligence variant MT (2004) Schakelcursussen (3 ec)
Informatica - Master na HBO Artificial Intelligence variant O (2004) Schakelcursussen (3 ec)
Informatica - Master na HBO Computer Security variant MT (2003) Schakelcursussen (3 ec)
Informatica - Master na HBO Computer Security variant O (2004) Schakelcursussen (3 ec)
Informatica - Master na HBO Embedded Systems variant MT (2003) Schakelcursussen (3 ec)
Informatica - Master na HBO Embedded Systems variant O (2004) Schakelcursussen (3 ec)
Informatica - Master na HBO Information Systems variant MT (2003) Schakelcursussen (3 ec)
Informatica - Master na HBO Information Systems variant O (2004) Schakelcursussen (3 ec)
Informatica - Master na HBO Software Construction variant MT (2003) Schakelcursussen (3 ec)
Informatica - Master na HBO Software Construction variant O (2004) Schakelcursussen (3 ec)
omvang
3 ec (84 uur) : 36 uur plenair college, 0 uur groepsgewijs college, 0 uur computerpracticum, 0 uur 'droog' practicum, 0 uur gesprekken met de docent, 0 uur onderling overleg met medestudenten (werkgroepen, projectwerk e.d.), 48 uur zelfstudie
investering
3 ec * 28 u/ec + #std * (1 + 3ec * 0.75 u/student/ec)
inzet tentatief

examinator
afdeling
tijdbesteding

dr. Freek Wiedijk
sws
180u.

speciale web-site
/~freek/courses/t1b-2007/

 

Dit college gaat niet zozeer over concrete programma's en concrete machines waarop ze draaien, maar over klassen van programma's en machines. Deze worden op een wiskundige manier beschreven en met wiskundige methoden proberen we uitspraken hierover te doen.

Leerdoelen

Op een hoger (abstract) niveau inzicht krijgen in het "rekenen" van een computer. Een overzicht krijgen van wat er mogelijk ('berekenbaar', `beslisbaar') is maar ook van wat er onmogelijk ('onberekenbaar', `onbeslisbaar') is op een computer. Eenvoudige problemen kunnen classificeren in berekenbaar en onberekenbaar. Het Turing machine model begrijpen en kunnen hanteren. De klassen van primitief-recursieve en mu-recursieve functies begrijpen en kunnen hanteren.

Onderwerpen

aaTuringmachines. Turing berekenbaarheid. Turing beslisbaarheid. Recursieve functies (primitief recursief en mu-recursief). De universele machine. Church-Turing These. Halting probleem. Onbeslisbaarheid en onberekenbaarheid.

Werkvormen

Hoorcollege, werkcollege, geintegreerd. Wekelijkse toets

Vereiste voorkennis

T1a, DW

Tentaminering

Schriftelijk tentamen, 'gesloten boek'. Er worden schriftelijke deel-toetsen afgenomen die positief mee tellen in het eindresultaat.

Literatuur

Thomas A. Sudkamp, "Languages and Machines: An introduction to the theory of computer science", ISBN 020 182 13 62


Evaluatie: studentenquêtes ; geen docentevaluatie bekend Rendement: 30 begonnen, echt meegedaan, geslaagd met 1e kans, geslaagd totaal
Q: