Het tweedejaarsvak Complexiteit wordt in het voorjaar van 2023 verzorgd door Jeannette de Graaf en Luc Edixhoven. De assistentie, waaronder de verzorging van de werkcolleges, wordt verleend door Andy Tatman, Perri van den Berg, Rachel de Jong en Sara Kooistra. Het vak is verplicht voor alle studenten Informatica en levert 6 EC op. Het vak bestaat uit hoorcolleges, werkcolleges, huiswerkopgaven en een afsluitend tentamen.
Hoorcolleges: dinsdag 09.00--10.45, zaal verschilt per week; zie het programma en MyTimetable.
Werkcolleges: dinsdag 11.00--12.45, computerzalen 302-304 en 303 op het Snellius.
Op 28 maart is er geen hoor- of werkcollege i.v.m. de tentamenweek.
Zie ook het rooster in MyTimetable en het programma hieronder.
Alle relevante informatie voor het vak komt in principe op deze website te staan. Brightspace wordt hoofdzakelijk gebruikt voor het inleveren van opdrachten en het geven van cijfers, en voor mededelingen.
Vragen kunnen worden gesteld in de Discordserver die schijnt te bestaan voor studenten (de assistenten zitten hier ook in), en op het forum op de pagina van het vak in Brightspace.
Jullie worden aangemoedigd om elkaars vragen te beantwoorden en de stof onderling te bespreken. Wees wel voorzichtig met al te stellige antwoorden als je het zelf ook niet zeker weet.
Vragen die niet passen op Discord of op Brightspace kunnen per e-mail naar l.j.edixhoven@liacs.leidenuniv.nl.
Er is een (losbladig) dictaat dat min of meer de inhoud van de gebruikte sheets bevat alsmede enige verbindende tekst, en bovendien een verzameling opgaven bij het hoorcollege. Zorg dat je de opgaven bij je hebt tijdens werkcolleges! Het college zelf bestaat overigens uit meer dan alleen de inhoud van het dictaat of de sheets! De versie van 2023 is beschikbaar. Mochten er in de loop van het semester extra veranderingen/aanvullingen komen op dit dictaat, dan zullen die veranderingen op deze website gemeld worden. Overigens zullen eveneens de gebruikte sheets via deze website te raadplegen zijn. Zie hieronder voor het collegeschema.
Heel globaal: (1) analyse van algoritmen, en (2) NP-volledigheid. Een greep uit de te behandelen onderwerpen: tijdcomplexiteit (worst/average/best case) van diverse algoritmen (zowel recursief als niet-recursief), enige wiskunde (O-notatie, recurrente betrekkingen), complexiteit van problemen, optimaliteit, beslissingsbomen, selectie/zoeken/sorteren, polynoomevaluatie, NP-volledige problemen (waaronder enkele bekende graafproblemen zoals het handelsreizigersprobleem) en reducties.
Hieronder staat het voorlopige programma aan hoor- en werkcolleges voor het semester. Voor elke week staat vermeld welke onderwerpen tijdens het hoorcollege worden besproken, met de bijbehorende hoofdstukken uit het dictaat, de gebruikte sheets en de opgaven voor het werkcollege. In principe worden de sheets de ochtend of de dag voor het college op de site gezet; direct na het college wordt dit zo nodig aangepast naar een definitieve versie.
In het programma staat ook welke opnamen van vorig jaar overeenkomen met de stof van de colleges van dit jaar. De opnamen zijn te vinden op Brightspace, onder Course Tools > Kaltura Media Gallery.
| # | Datum | Zaal | Onderwerp | § Dictaat | Sheets | Opnamen vorig jaar | Werkcollege: opgaven | |
|---|---|---|---|---|---|---|---|---|
| 1 | 7 | februari | C3 (Gorlaeus) | Inleiding | 1, 2 | college 1 | 8 februari 2022 9 februari 2022 (tot 1:27:40) |
1, 2, 3abcde, 4, 6 antwoorden |
| 2 | 14 | februari | C1 (Gorlaeus) | Zoeken | 3, 4 | college 2 | 15 februari 2022 | 6, 17, 8, 20, 19 antwoorden |
| 3 | 21 | februari | C1 (Gorlaeus) | Beslissingsbomen
Toernooimethode Adversary argument |
3, 5
6.1--6.5 |
college 3 | 22 februari 2022 1 maart 2022 (tot 58:00) |
20, 5d, 27, 22, 32 antwoorden |
| 4 | 28 | februari | C1 (Gorlaeus) | Selectie is O(n)
Insertion sort Recurrente betrekkingen |
6.6, 7.1 | college 4 | 1 maart 2022 (vanaf 58:00) 8 maart 2022 (tot 51:00) 9 februari 2022 (vanaf 1:27:40) |
32, 14, 15, 31, 18 antwoorden |
| 5 | 7 | maart | C1 (Gorlaeus) | Mergesort
Quicksort Ondergrens sorteren |
7.2, 7.3, 7.4 | college 5 | 8 maart 2022 (vanaf 1:02:00) 15 maart 2022 (tot 36:30) |
15, 16, 31, 23, 24, 18 antwoorden |
| 6 | 14 | maart | C1 (Gorlaeus) | Shellsort
Optimaal sorteren O(n) sorteren |
7.5, 7.6, 7.7 | college 6 | 15 maart 2022 (vanaf 52:45) 22 maart 2022 (tot 35:40) |
39 (minus Heapsort), 40, 41, 42, 43 antwoorden |
| 7 | 21 | maart | C3 (Gorlaeus) | Polynoomevaluatie
Matrixvermenigvuldiging Eulerkringen Hamiltonkringen |
8, 9 | college 7 | 22 maart 2022 (vanaf 49:50) 5 april 2022 (tot 1:22:10) |
49, 51, 52a, 47, 48 antwoorden |
| 28 | maart | --- | --- | --- | --- | --- | --- | |
| 8 | 4 | april | 412 (Snellius) | Inleiding complexiteitstheorie | 10.1, 10.2, 10.3 | college 8 | 5 april 2022 (vanaf 1:22:20) 12 april 2022 13 april 2022 (vanaf 38:15 tot 59:00) |
55, 10, 45, 46, 33 antwoorden |
| 9 | 11 | april | 412 (Snellius) | De klasse NP | 10.4, 10.5 | college 9 | 19 april 2022 | 54, 59, 61 antwoorden |
| 10 | 18 | april | 412 (Snellius) | Reducties
NP-volledigheid |
10.5, 10.6 | college 10
Two Dots (2016) |
26 april 2022 | 58, 63, 64, 65 antwoorden |
| 11 | 25 | april | 407-409 (Snellius) | Satisfiability | --- | college 11
Two Dots (2018) Cook (1971) |
3 mei 2022 (tot 1:17:00 en vanaf 1:34:10) | 66, 67, 68 antwoorden |
| 12 | 2 | mei | 407-409 (Snellius) | Benaderingsalgoritmen Herhaling colleges 1 t/m 7 |
--- | alle slides | --- | 21, 26, 28, 36, 60, 68 antwoorden |
| 13 | 9 | mei | 407-409 (Snellius) | Hendrik Jan Hoogeboom: Complexiteit en spellen |
--- | gastcollege | --- | 21, 26, 28, 36, 60, 68 antwoorden |
| 14 | 16 | mei | 407-409 (Snellius) | Herhaling colleges 8 t/m 11 | --- | alle slides | --- | 59ab, 63, 66bc, 68bc |
| 15 | 23 | mei | 407-409 (Snellius) | Oefententamen | --- | tentamen juni 2016 uitwerking |
--- | --- |
| 5 | juni | Tentamen | ||||||
| 10 | juli | Hertentamen | ||||||
Gedurende het semester zijn er vier huiswerkopdrachten om in te leveren, bestaande uit een mix van opdrachten op pen en papier, en programmeren. Deze hebben als doel om te zorgen voor een beter begrip van de stof, en tellen mee als bonus voor het eindcijfer voor dit vak.
De huiswerkopdrachten dienen individueel te worden gemaakt (in LaTeX!), en vervolgens ingeleverd op Brightspace. Uiteraard mag je elkaar helpen met de problemen en de samen leerstof bespreken, maar kopiëren, overschrijven en dergelijke zijn niet toegestaan. Geef elkaar bij het bespreken van de opgaven dus indien nodig een duwtje in de goede richting, tips en suggesties, maar geen panklare oplossing. Daar wordt niemand beter van.
Met de huiswerkopdrachten is maximaal 1 bonuspunt te verdienen. Indien je tentamencijfer minstens een 5,0 is, wordt hier een tiende van je gemiddelde huiswerkcijfer bij opgeteld. Als je tentamencijfer lager is dan een 5,0, is het eindcijfer gelijk aan je tentamencijfer. Zoals gebruikelijk wordt je eindcijfer afgerond op een geheel- of halftallig cijfer tussen 1 en 10. Niet-ingeleverde huiswerkopgaven tellen als 0.
Hieronder komen de huiswerkopgaven. T.z.t. volgt ook een LaTeX-template.
In het dictaat staan opgaven, die grotendeels op het werkcollege (of college) behandeld zullen worden. Soms zal er van een enkele opgave een officiële uitwerking verschijnen. Deze zijn t.z.t. hieronder te vinden ter referentie. Voor alle andere uitwerkingen van opgaven: bezoek het werkcollege en schrijf ze zelf!
Op dit moment staan hieronder de oude (uit 2017/2018) uitwerkingen. In de loop van dit semester zullen --- indien nodig --- de uitwerkingen worden bijgewerkt. Wanneer dit het geval is zal dit hieronder duidelijk worden aangegeven, zodat je weet dat het om de definitieve versie gaat. Tevens zal er hier en daar wellicht een extra uitwerking bijkomen.
Het tentamen Complexiteit bevat in elk geval zowel praktische vragen (zoals de werkcollege-opgaven) als meer theoretische (college). Ook kleine bewijsjes en eenvoudige recurrente betrekkingen zijn mogelijk. Op het tentamen kunnen vragen voorkomen over alle stof van colleges 1 tot en met 11, met uitzondering van:
Tentamen: maandag 5 juni 2023, 09u00--12u00, Snellius zalen 313, 403 en 407-409
Hertentamen: maandag 10 juli 2023, 09u00--12u00
Hieronder zijn een aantal oude tentamens Complexiteit beschikbaar om mee te oefenen (met enkele uitwerkingen). Deze zijn representatief voor het tentamen van dit jaar.
Let op! In een paar oude tentamens staan nog opgaven over Turingmachines (DTMs). Deze behoren niet meer tot de stof van dit vak. Je kan deze opgaven dus overslaan.
Vragen en/of opmerkingen kunnen worden gestuurd naar: l.j.edixhoven@liacs.leidenuniv.nl. Op maandagen en dinsdagen ook beschikbaar op het Snellius, kamer 131.
Laatste wijziging 22 juli 2023 https://liacs.leidenuniv.nl/~edixhovenlj/complexiteit/