Vakomschrijving

In de cursus «Logische Complexiteit» worden de grondbeginselen van berekenbaarheid en complexiteit behandeld. Het vak bestaat uit drie delen.

  1. Eindige automaten, reguliere talen en context-vrije grammatica's;
  2. Turing machines, beslisbare en onbeslisbare talen, non-determinisme en het Halting probleem;
  3. Tijd- en ruimtecomplexiteit, complexiteitsklassen, polynomiale reduceerbaarheid, NP-volledigheid, het satisfiability probleem, het traveling salesman probleem en cryptografie.

Dit vak wordt gegeven door Jeroen Goudsmit. Je kan de website van vorig jaar bekijken voor extra oefeningen.

Nieuws

Hieronder een lijst van dingen die recentelijk aangepast zijn op de website.

Dinsdag 22 mei 2012
De herkansingen zijn nagekeken. Een aangepaste cijferlijst staat online, de aangepaste cijfers zullen spoedig in Osiris staan.
Woensdag 2 mei 2012
De eindtoets en haar uitwerkingen zijn beschikbaar. Als je fouten ziet in de uitwerkingen, mail dan de docent.
Vrijdag 20 april 2012
De cijferlijst is bijgewerkt. Mail de docent om (scans van) je tentamen in te zien.
Donderdag 4 april 2012
De cijferlijst is bijgewerkt. Als je scans van je opgaven wilt inzien, mail dan de docent.
Woensdag 3 april 2012
Rosalie Iemhoff heeft uitwerkingen van opgaven in Sipser gemaakt, deze staan online. Het betreft opgaven 4.10, 4.12, 5.1, 7.14, 7.19, 7.20b, 7.21, 7.23 en nog een paar voorbeelden van reducties.
Woensdag 3 april 2012
Uitgebreidere uitwerkingen van opgave 8 beschikbaar.
Dinsdag 3 april 2012
Bijgewerkte cijferlijst online. Ook de herkansing van 2010–2011 kun je alvast maken. Deze behandelen we donderdag.
Dinsdag 3 april 2012
Slides voor het zestiende hoorcollege online. Let op, er is een extra college op aanstaande donderdag, in Drift 21 zaal 0.05 van 09:00 tot 12:45.
Maandag 2 april 2012
De planning is bijgewerkt met extra locatieinformatie van de eindtoets en een aankondiging van de herkansing. De eindtoets van 2010-2011 kun je alvast thuis maken.
Vrijdag 30 maart 2012
De laatste inleveropgave staat online.
Donderdag 29 maart 2012
Slides voor het vijftiende hoorcollege online.
Dinsdag 27 maart 2012
Slides voor het veertiende hoorcollege online en de cijferlijst is bijgewerkte met cijfers van de zesde inleveropgave.
Maandag 26 maart 2012
Typefouten verbeterd in de zevende inleveropgaven.
Donderdag 22 maart 2012
De cijferlijst is bijgewerkt met cijfers van de vijfde inleveropgave. Als je ze in wilt zien voor dinsdag, mail dan de docent.
Donderdag 22 maart 2012
Slides voor het dertiende hoorcollege online, zie de planning.
Dinsdag 20 maart 2012
De zevende inleveropgave is bekend gemaakt.
Dinsdag 20 maart 2012
Slides van het twaalfde college online, en de planning gaat een week verder. De nieuwe inleveropgave volgt voor het volgende hoorcollege.
Maandag 19 maart 2012
Fout verbeterd in bewijs Rice's Stelling. Merk op: opgave 5.28 geeft een formulering van Rice's stelling, en de volgende twee opgaven oefenen er verder mee. Er zijn uitwerkingen van 5.28 en 5.30a in het boek. De cijferlijst is ook aangepast, sommigen hebben nu meer punten voor de eerste vraag van de vierde inleveropgave.
Donderdag 15 maart 2012
Slides van het elfde hoorcollege online.
Dinsdag 13 maart 2012
Slides van het tiende hoorcollege online. De zesde inleveropgave is beschikbaar en de planning is bijgewerkt.
Zaterdag 10 maart 2012
Correctie in de vijfde inleveropgave; de automaat overschrijft nu cijfers door *, dit stond eerst verkeerd.
Donderdag 8 maart 2012
Slides voor het negende hoorcollege staan online, zie de planning.
Woensdag 7 maart 2012
De vijfde inleveropgave is bekend gemaakt en een kleine fout in de slides is gecorrigeerd. Zie de planning.
Dinsdag 6 maart 2012
De cijfers van de derde inleveropgave staat online en de planning is bijgewerkt. Bij ieder komend hoorcollege staan nu opgaven die je direct erna maken kan.
Zondag 4 maart 2012
De vierde inleveropgave is gecorrigeerd, de automaat in de tweede opgave was onjuist.
Donderdag 1 maart 2012
De deeltoets en haar uitwerkingen staan online. Verder staat de vierde inleveropgave op de planning.
Dinsdag 28 februari 2012
Aantal correcties in de uitwerkingen van de deeltoets 2010-2011.
Dinsdag 28 februari 2012
Uitwerkingen deeltoets 2010-2011 beschikbaar. Ook de slides van het zevende hoorcollege staan online.
Maandag 27 februari 2012
Stof eerste deeltoets duidelijker aangegeven op de planning. Ook een kleine correcte in de derde inleveropgave over waar «u» vandaan komt in opgave 3.
Maandag 27 februari 2012
Cijfers tweede inleveropgave online beschikbaar, zie beoordeling.
Zaterdag 25 februari 2012
Een typefout in inleveropgave 3 is verbeterd, er stond «w is een rijtje palindromen», nu «w is een palindroom».
Vrijdag 24 februari 2012
Merk op dat er een paar nare fouten staat in het bewijs van Stelling 2.34 in het boek. Zie de errata, en houdt er rekening mee dat de paginanumers daar soms pagina's achter lopen (pagina 127 in het boek correspondeert met pagina 125 daar).
Vrijdag 24 februari 2012
Cijferlijst online beschikbaar, zie beoordeling.
Donderdag 23 februari 2012
Kleine foutjes in slides van het zesde hoorcollege verbeterd.
Donderdag 23 februari 2012
Slides van het zesde hoorcollege online.
Woensdag 22 februari 2012
Fouten verbeterd in Slides voor het vijfde hoorcollege. Om het verhaal rond PDA's wat te verduidelijken is er ook een aantekening over context-vrije grammatica's beschikbaar. De planning is bijgewerkt voor volgende week, en de deeltoets 2010-2011 is online beschikbaar. De derde inleveropgave is ook bekend gemaakt.
Dinsdag 21 februari 2012
Slides voor het vijfde hoorcollege online, zie de planning.
Dinsdag 21 februari 2012
Fouten verbeterd in Slides voor het vierde hoorcollege.
Donderdag 16 februari 2012
Slides voor het vierde hoorcollege online, zie de planning.
Dinsdag 14 februari 2012
Slides voor het derde hoorcollege verbeterd, tweede inleveropgave bekend gemaakt op planning.
Dinsdag 14 februari 2012
Planning voor de derde week en slides derde hoorcollege online.
Vrijdag 10 februari 2012
Deeltoets en eindtoets aangegeven op planning en rooster.
Donderdag 9 februari 2012
Slides voor het tweede hoorcollege online.
Dinsdag 7 februari 2012
Planning voor de tweede week online, eerste inleveropgave bekend gemaakt.
Maandag 6 februari 2012
Planning voor de eerste week online.

Inleveropgaven

Elke week is er een inleveropgave die aan het begin van het hoorcollege op dinsdag ingeleverd dient te worden bij de hoorcollegedocent. Indien je het hoorcollege niet bij kunt wonen, mail de opgave dan (in PDF-formaat) de avond voor het hoorcollege naar Jeroen Goudsmit. Het ontvangst van de e-mail wordt uiterlijk twee uur voor het hoorcollege bevestigd, zonder bevestiging kun je er van uit gaan dat je e-mail niet aangekomen is. Te laat ingeleverde opgaven worden niet nagekeken.

Rooster

Zie de roosterpagina voor een volledig overzicht van het rooster voor periode 3. Let wel, de cursuskrant is niet volkomen betrouwbaar. In Osiris kun je de meest actuele officiële informatie vinden.

Dag Tijd Type Locatie
Dinsdag 13:15 – 15:00 Hoorcollege Drift 21, zaal 003
Dinsdag 15:15 – 17:00 Werkcollege Drift 25, zaal 301 & 302
Donderdag 11:00 – 12:45 Hoorcollege Drift 21, zaal 105
Donderdag 11:00 – 13:00 Deeltoets Drift 21, zaal 032
Dinsdag 13:30 – 16:30 Eindtoets Achter de Dom, zaal 2.02
Dinsdag 17:00 – 20:00 Herkansing Drift 21, zaal 1.05

Literatuur

Bij dit vak wordt het boek «Introduction to the theory of Computation (second edition), Michael Sipser, Course Technology 2005, ISBN 0-619-21764-2» gebruikt. Er zijn errata beschikbaar voor dit boek.

Beoordeling

Dit vak heeft een tussentoets en een eindtoets. Daarnaast zijn er wekelijkse inleveropgaven. Om te slagen voor het vak moeten alle inleveropgaven inleveropgaven ingeleverd zijn, en moet het gemiddelde van de opdrachten minstens een vier zijn. Dusver bekende cijfers zijn in te zien, kijk vooral of je cijfers kloppen. Het eindcijfer wordt berekend volgens de formule:

eindcijfer = 0,45*tussentoets + 0,45*eindtoets + 0,1*(gemiddelde zes beste inleveropgaven).

Er bestaat de mogelijkheid om in mei een herkansing te doen als het eindcijfer zoals hierboven berekend tussen de vier en de zes ligt. In dit geval wordt het eindcijfer als volgt berekend:

eindcijfer = 0,9*herkansing + 0,1*(gemiddelde zes beste inleveropgaven).