Studiegids

nl en

Computability

Vak
2023-2024

Toegangseisen

Aanbevolen voorkennis: Foundations of Computer Science, Automata Theory.

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.

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:

In MyTimetable (login) kun je alle vak- en opleidingsroosters vinden, waarmee jij je persoonlijke rooster kunt samenstellen. Onderwijsactiviteiten waarvoor je je via MyStudymap hebt 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. Je kunt notificaties aanzetten bij Instellingen, na login.

Vragen? Bekijk de video, lees de instructie of neem contact op met de ISSC helpdesk. Let op: Joint Degree studenten Leiden/Delft dienen de informatie uit de Leidse en Delftse MyTimetable's samen te voegen om een volledig rooster te zien. Deze video leg uit hoe dat werkt.

Onderwijsvorm

Per week twee uur hoorcollege en twee uur werkcollege. Daarnaast wordt er eenmalig een huiswerkopgave opgegeven.

Toetsing en weging

Een huiswerkopgave in de loop van de collegeperiode, en schriftelijk tentamen na afloop van de colleges. De huiswerkopgave is niet verplicht, maar telt wel mee voor het eindcijfer. Het minimumcijfer voor de huiswerkopgave is 0, het minimumcijfer voor het tentamen is 1. Het eindcijfer van het vak is gelijk aan het tentamencijfer + maximaal 0.4 bonuspunt van de huiswerkopgave. Als dit minstens 5.5 is, heb je het vak gehaald.

De docent zal de studenten informeren hoe de inzage en de nabespreking van de tentamens 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

Met ingang van het collegejaar 2022-2023 ben je als student zelf verantwoordelijk om je tijdig, dat wil zeggen 14 of 28 dagen voor aanvang van het vak, in te schrijven. Dat kan via Mystudymap. Dit doe je twee keer per jaar: één keer voor de vakken die je wilt volgen in semester 1 en één keer voor de vakken die je wilt volgen in semester 2.

Inschrijven voor vakken in het eerste semester is mogelijk vanaf juli; inschrijven voor vakken in het tweede semester is mogelijk vanaf december. Zie voor meer informatie deze pagina (tab Wiskunde en Natuurwetenschappen)

Daarnaast is het voor alle studenten, inclusief eerstejaars bachelorstudenten, verplicht om zich in te schrijven voor tentamens via My Studymap. Zonder geldige voorinschrijving in My Studymap kun je niet deelnemen aan het tentamen.

Uitgebreide informatie over de werking van MyStudymap vind je hier.

Contact

Onderwijscoördinator LIACS bachelors

Website

Computability

Opmerkingen

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.