Studiegids

nl en

Computability

Vak
2020-2021

Toegangseisen

Niet van toepassing.

Beschrijving

Computers kunnen gebruikt worden voor het uitvoeren van vele soorten berekeningen. Toch zijn hier ook grenzen aan. Bij dit vak onderzoeken we de mogelijkheden en onmogelijkheden van een computer.
We doen dit onder andere door een theoretisch model van de computer te bestuderen.

Onderwerpen die aan de orde komen zijn: De Turingmachine als algemeen model voor berekenbaarheid: accepteren, beslissen en rekenen met Turingmachines, niet-determinisme, universele Turingmachines, Church-Turing these. Recursief opsombare en recursieve talen, algemene grammatica’s. Het stopprobleem, (on)beslisbare problemen.

Aanbevolen voorkennis: Fundamentele Informatica 1 en Automata Theory

Leerdoelen

Verwerven van inzicht in de mogelijkheden en beperkingen van computers (algoritmes). Kennismaken met fundamentele inzichten die ten grondslag liggen aan de informatica als wetenschappelijke discipline.

Rooster

De meest recente roosters zijn te vinden op de Studenten-website:

Onderwijsvorm

Hoorcollege, werkcollege en een huiswerkopgave.

Toetsing en weging

Schriftelijk tentamen na afloop van de colleges. Het eindcijfer van het vak is gelijk aan het tentamencijfer + maximaal 0.4 bonuspunt van de huiswerkopgave.

De docent zal de studenten informeren hoe de inzake en de nabespreking van de tentamen zal plaatsvinden.

Literatuurlijst

John C. Martin, Introduction to Languages and the Theory of Computation, 4th edition, McGraw-Hill, 2011, ISBN: 978-007-128942-9.

Inschrijven

Aanmelding voor vakken verloopt via uSis. Hiervoor is de uSis-code van het vak nodig, die te vinden zijn in de Studiegids. Meer info over het inschrijven voor vakken of tentamens is hier te vinden.

MyTimetable

In MyTimetable kun je alle vak- en opleidingsroosters vinden, waarmee jij je persoonlijke rooster kunt samenstellen. Onderwijsactiviteiten waarvoor je in uSis staat ingeschreven, worden automatisch in je rooster getoond. Daarnaast kun je My Timetable gemakkelijk koppelen aan een agenda-app op je telefoon en worden roosterwijzigingen automatisch in je agenda doorgevoerd; bovendien ontvang je desgewenst per e-mail een notificatie van de wijziging.

Vragen? Bekijk de video-instructie, lees de instructie of neem contact op met de ISSC helpdesk.

Brightspace

Inschrijving voor vakken verloopt via uSis. Wanneer je je hier inschrijft voor een bepaald vak krijg je automatisch ook toegang tot de omgeving van dit vak via Brightspace.

Voor meer informatie over Brightspace kun je op deze link klikken om de handleidingen van de universiteit te bekijken. Bij overige vragen of problemen kan contact opgenomen worden met de helpdesk van de universiteit Leiden.

Contact

Onderwijscoördinator Informatica, Riet Derogee

Website

Computability