SluitenHelpPrint
Switch to English
Cursus: KI3V12013
KI3V12013
Logische complexiteit
Cursus informatieRooster
CursuscodeKI3V12013
Studiepunten (ECTS)7,5
Categorie / Niveau3 (Bachelor Gevorderd)
CursustypeCursorisch onderwijs
VoertaalNederlands
Aangeboden doorFaculteit Geesteswetenschappen; BA Onderwijs Geesteswetenschappen; Ug School Filosofie en Religiewetenschap;
Contactpersoondr. R. Iemhoff
Telefoon+31 30 2535575
E-mailR.Iemhoff@uu.nl
Docenten
Docent
dr. R. Iemhoff
Overige cursussen docent
Docent
B.G. Rin
Overige cursussen docent
Blok
2  (14-11-2016 t/m 03-02-2017)
Aanvangsblok
2
TimeslotC: MA-middag/namiddag,DI-middag, DO-ochtend
Onderwijsvorm
Voltijd
Cursusinschrijving geopendvanaf 31-10-2016 09:00 t/m 01-11-2016 23:59
AanmeldingsprocedureOsiris
Inschrijven via OSIRISJa
Inschrijven voor bijvakkersJa
VoorinschrijvingNee
WachtlijstNee
Plaatsingsprocedure(Sub)school
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 minimaal één van de cursussen:
- Wiskunde voor AI (CK1W0006)
- Wiskunde voor AI (KI1V12002)
Verplicht materiaal
Boek
Introduction to the theory of Computation (second edition), Michael Sipser, Course Technology 2005, , ISBN 9788131517505
Kosten materiaal
EUR 84,00
Werkvormen (aanwezigheidsplicht)
Hoorcollege (Verplicht)

Werkcollege (Verplicht)

Algemeen
Dagcollege

Voorbereiding bijeenkomsten
Elke bijeenkomst voorbereiden door te zorgen dat de voorgaande stof beheerst wordt en eventuele vragen te formuleren om tijdens hoor- of werkcollege te stellen, en het huiswerk te maken.

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

Toetsen
Opdracht(en)
Weging10
Minimum cijfer-

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

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

Schriftelijk tentamen
Weging90
Minimum cijfer-

Beoordeling
Begrip van berekenbaarheidstheorie en complexiteitstheorie

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

SluitenHelpPrint
Switch to English