SluitenHelpPrint
Switch to English
Cursus: CK3W3071
CK3W3071
Logische complexiteit
Cursus informatieRooster
CursuscodeCK3W3071
Studiepunten (ECTS)7,5
Categorie / Niveau3 (Bachelor Gevorderd)
CursustypeCursorisch onderwijs
VoertaalNederlands
Aangeboden doorFaculteit Geesteswetenschappen; BA Onderwijs Geesteswetenschappen; Ug School Wijsbegeerte e Kunstmatige Intelligentie;
Contactpersoondr. R. Iemhoff
Telefoon+31 30 2535575
E-mailR.Iemhoff@uu.nl
Docenten
Docent
J.P. Goudsmit, MSc
Overige cursussen docent
Contactpersoon van de cursus
dr. R. Iemhoff
Overige cursussen docent
Docent
dr. R. Iemhoff
Overige cursussen docent
Blok
3  (06-02-2012 t/m 14-04-2012)
Aanvangsblok
3
TimeslotC: MA-middag/namiddag,DI-middag, DO-ochtend
Onderwijsvorm
Voltijd
Cursusinschrijving geopendvanaf 16-01-2012 t/m 17-01-2012
AanmeldingsprocedureOsiris
Inschrijven via OSIRISJa
Inschrijven voor bijvakkersJa
VoorinschrijvingNee
WachtlijstNee
Plaatsingsprocedureadministratie onderwijsinstituut
Cursusdoelen
Begrip van berekenbaarheidstheorie en complexiteitstheorie.
Inhoud
Deel I: Formele talen: eindige automaten, reguliere talen en grammatica's.

Deel II: Berekenbaarheidstheorie: Turing machines, berekenbare functies,
Church-Turing these, Universele Turing machine, niet-determinisme versus
determinisme, onbeslisbaarheid, Halting probleem, beslisbare en
onbeslisbare talen.

Deel III: Complexiteitstheorie: complexiteitsklassen, P, PSPACE, NP, EXP,
NL, satisfiability probleem, graafproblemen, traveling salesman probleem,
reduceerbaarheid, volledigheid, approximaties en cryptografie.

 

Ingangseisen
Er moet voldaan zijn aan de cursus:
- Wiskunde voor AI (CK1W0006)
Verplicht materiaal
Boek
Introduction to the theory of Computation (second edition), Michael Sipser, Course Technology 2005, ISBN 0-619-21764-2
Werkvormen
Hoorcollege

Werkcollege

Algemeen
Dagcollege

Voorbereiding bijeenkomsten
Elke bijeenkomst voorbereiden door 1-2 uur het boek te lezen en huiswerk opgaven te doen (problemen oplossen).

Bijdrage aan groepswerk
Samen aan de problemen in de werkgroepen werken, eigen oplossingen presenteren en beoordelen.

Toetsen
Opdracht(en)
Weging10
Minimum cijfer1

Beoordeling
Inleveropgaven (10%), schriftelijk tentamen (90%)
Begrip van berekenbaarheidstheorie en complexiteitstheorie.

Aspecten van academische vorming
Bestuderen en analyseren van informatie
Synthetiseren en structureren van informatie

Schriftelijk tentamen
Weging90
Minimum cijfer1

Beoordeling
Begrip van berekenbaarheidstheorie en complexiteitstheorie

Aspecten van academische vorming
Bestuderen en analyseren van informatie
Synthetiseren en structureren van informatie
Hanteren van wetenschappelijk instrumentarium

SluitenHelpPrint
Switch to English