SluitenHelpPrint
Switch to English
Cursus: CK3W3071
CK3W3071
Logische complexiteit
Cursus informatieRooster
CursuscodeCK3W3071
Studiepunten (ECTS)7,5
Categorie / Niveau3 (Bachelor Gevorderd)
CursustypeCursorisch onderwijs
VoertaalEngels, Nederlands
Aangeboden doorFaculteit Geesteswetenschappen; Cognitieve Kunstmatige Intelligentie;
Contactpersoondr. R. Iemhoff
Telefoon+31 30 2535575
E-mailR.Iemhoff@uu.nl
Docenten
Docent
dr. R. Iemhoff
Overige cursussen docent
Contactpersoon van de cursus
dr. R. Iemhoff
Overige cursussen docent
Blok
Onbekend
Aanvangsblok
1
TimeslotC: MA-middag/namiddag,DI-middag, DO-ochtend
Onderwijsvorm
Voltijd
Inschrijven via OSIRISJa
Inschrijven voor bijvakkersJa
VoorinschrijvingNee
WachtlijstNee
Cursusdoelen
Begrip van grondslagen computatietheorie en complexiteit. Toepassingen in de cryptografie.
Inhoud

Part1. Basic formal language theory Finite automata, regular languages, context-free languages.

Part 2. Basic computation theory  Turing machines, computable functions Church-Turing thesis, Entscheidungsproblem Universal Turing machine Undecidability of the halting problem Decidable and undecidable logical theories, Goedel Theorem

Part 3. Basic complexity theory Time and space complexity measures. Classes P and PSPACE. Class NP, nondeterministic Turing machines. Satisfyiability problem. Clique and Hamiltonian path problems. Polynomial reducibility. NP-completeness. Cook's Theorem. PSPACE-completeness.

Part 4. Elements of cryptography Calculating modulo n. Ring Z_n. Inverible elements. Euclid algorithm. Euler function. Euler theorem and Fermat's little theorem. Pseudoprimes. Probabilistic polynomial algrothms for testing pseudoprimality and primality. Cryptosystems, one time pad cryptosystem, information-theoretic security Public key cryptosystems RSA cryptosystem Electronic signatures in RSA.

Ingangseisen
Er moet voldaan zijn aan minimaal één van de cursussen:
- Wiskunde voor AI (WB3069)
- Wiskunde voor AI (CK1W0006)
Verplicht materiaal
Boek
Michael Sipser, Introduction to the theory of computation, PWS Publishing Company, Boston, 1997.
Werkvormen
Hoorcollege 1

Hoorcollege 2

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
Toets
Weging100
Minimum cijfer5,5

Beoordeling
Actieve deelname (10 %)
Opdracht(en) (10 %)
Schriftelijk tentamen (80 %)

Begrip van de belangrijke noties van computionele en logische complexiteit.

Aspecten van academische vorming
Bestuderen en analyseren van informatie
Synthetiseren en structureren van informatie
Voorbereiden / opzetten van onderzoek
Hanteren van wetenschappelijk instrumentarium - vakspecifiek

SluitenHelpPrint
Switch to English