Prospectus

nl en

Computability

Course
2024-2025

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

Na afloop van dit vak zijn studenten in staat om

  • Turingmachines voor een gegeven taal, functie of taak te ontwerpen en Turingmachines te interpreteren

  • unrestricted grammars voor een gegeven taal te ontwerpen en unrestricted grammars te interpreteren

  • met behulp van reducties aan te tonen dat bepaalde beslissingsproblemen onbeslisbaar zijn

    • behandelde definities te reproduceren en toe te passen,
    • de codering van Turingmachines als bitstrings te beschrijven en toe te passen,
    • de Church Turing these te beargumenteren
    • constructies tussen Turingmachines en unrestricted grammars te beschrijven en toe te passen,
    • eenvoudige resultaten te reproduceren, te bewijzen en toe te passen

Rooster

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

In MyTimetable 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, nadat je bent ingelogd.

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 MyTimetables samen te voegen om een volledig rooster te zien. Deze video legt 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.
Deelcijfers voor huiswerk of tentamen uit een eerder jaar kunnen niet worden meegenomen naar het nieuwe jaar.

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

Als student ben je zelf verantwoordelijk voor het tijdig inschrijven via MyStudyMap.

In deze korte video zie je stap voor stap hoe je je kunt inschrijven voor cursussen in MyStudyMap.
Uitgebreide informatie over de werking van MyStudyMap vind je hier.

Er zijn twee inschrijfperiodes per jaar:

  • de inschrijving voor het najaar opent in juli

  • de inschrijving voor het voorjaar opent in december

Zie deze pagina voor meer informatie over deadlines en inschrijven voor vakken en tentamens.

Let op:

  • Het is verplicht om je in te schrijven voor alle activiteiten die je gaat volgen van een vak.

  • Je inschrijving is pas voltooid wanneer je je cursusplanning indient in het tabblad ‘Klaar voor inschrijving’ door op ‘indienen’ te klikken.

  • Niet ingeschreven zijn voor een (her)tentamen betekent dat je niet mag deelnemen aan het (her)tentamen.

Contact

Onderwijscoördinator LIACS bachelors

Website

Computability

Opmerkingen

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.

Software
Vanaf collegejaar 2024/2025 werkt de faculteit Wiskunde en Natuurwetenschappen met het software distributieplatform Academic Software. Via het platform kun je toegang krijgen tot de software die je nodig hebt voor bepaalde vakken in je studie. Voor sommige software moet je laptop aan bepaalde systeemeisen voldoen. Dit staat aangegeven bij de software. Belangrijk is dat je de software installeert voor de start van het vak. Meer informatie over het laptopprofiel vind je op de studentenwebsite.