Nieuws: Het tentamen van 4 juni 2019 is geheel nagekeken, zie Blackboard.

 

Complexiteit 2018/2019

Het tweedejaarsvak Complexiteit wordt in het voorjaar van 2019 verzorgd door Jeannette de Graaf. De assistentie, waaronder de verzorging van de werkcolleges, wordt verleend door Ruben Turkenburg (RT) en Larissa Wolters (LW). Het vak is verplicht voor alle studenten Informatica en levert 6 EC op. Het vak bestaat uit hoorcolleges, werkcolleges en huiswerkopgaven. Verder uiteraard een afsluitend tentamen.
Studenten die deel gaan nemen aan Complexiteit wordt verzocht zich via uSis aan te melden. Je kunt dit het beste doen via het nummer van de studieactiviteit Complexiteit (dat is 12422; voor de herkansing is dit 9272). Je bent dan meteen aangemeld voor het tentamen. Voor de studieactiviteitennummers van alle vakken: ga naar de faculteitswebsite (NL) en daarvandaan Informatie voor studenten > Administratie > Inschrijven voor vakken en tentamens en dan kiezen voor het tabblad Wiskunde en Natuurwetenschappen. Overigens vind je in de e-studiegids bij de algemene beschrijving van elk vak ook een link naar de betreffende website waarop alle studieactiviteitennummers te vinden zijn.

De colleges vinden plaats op dinsdagen van 11.00 uur tot 12.45 uur in zaal 174. Het bij de colleges behorende werkcollege is op dinsdagmiddagen van 13.30 uur tot 15.15 uur, in zaal 174. Let op: dinsdag 5 februari (dit is uiteindelijk 12 februari geworden) is er 's middags college (in zaal 174) in plaats van werkcollege. In de eerste collegeweek is er dus zowel op dinsdagmorgen als op dinsdagmiddag college. Verder is er in de week van 11 maart (week 11) geen college en geen werkcollege omdat er dan herkansingen voor vakken uit het najaar zijn. Zie ook het rooster op internet.

Materiaal

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 2019 is beschikbaar. Deze verschilt niet veel van de versie van 2018. 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.

Inhoud van het vak

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 (niet recursief en 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.

Nieuws / updates

Programma

Hieronder zal het programma voor het hoorcollege/werkcollege van het voorjaar 2019 bijgehouden worden. Voor elke week staat daarin vermeld welke onderwerpen aan de orde zijn gekomen met de bijbehorende pagina's uit het dictaat, de gebruikte sheets en de opgaven die bij het werkcollege behandeld zijn. In principe worden de sheets de ochtend of de dag voor het college op de site gezet; direct na het college komt de definitieve versie hieronder te staan. De colleges worden vooralsnog gegeven door Hendrik Jan Hoogeboom (HJH) en Walter Kosters (WK).


Datum (hoorcollege)  Onderwerp Dictaat Sheets Werkcollege: opgaven
5 februari vervalt --- geen college geen werkcollege
12 februari Inleiding, wiskundige achtergrond  p. 1-8 college 1 (HJH),
college 2 (WK)
college i.p.v. werkcollege
19 februari Zoeken p. 8-12 college 3 (HJH) 1,2 4,6,7
26 februari Beslissingsbomen en selectie;
toernooimethode; adversary argument
p. 12-17 college 4 (WK) 7,8,9,10,20 (p. 56,57)
5 maart Selectie is O(n);
Insertion sort; Mergesort
p. 17-21 college 5 (HJH) 20,22,18,14,15 (p. 57-63)
12 maart tentamenweek --- geen college geen werkcollege
19 maart Mergesort, Ondergrens sorteren;
Quicksort, Shellsort
p. 17-25 college 6 (WK) 14,15,16,23,24 (p. 57-59,63)
26 maart Shellsort, optimaal sorteren;
Merge insertion sort, O(n)-sorteren
p. 26-29 college 7 (HJH) 23,24,26,27 (p. 63,64)
2 april Polynoomevaluatie;
matrixvermenigvuldiging;
Euler- en Hamiltonkringen
p. 29-35 college 8 (WK) 31,33,29,34,35 (p. 64,65)
9 april NP-volledigheid I 10.1-3.1, 11 college 9 (HJH) 38,39,40,41 (p. 66,67)
16 april NP-volledigheid II 10.3.2, 10.4, 10.5 college 10 (HJH) 41,42,43,44,45 (p. 67,68)
23 april NP-volledigheid III 10.5.3, 10.6 college 11 (WK) 46,47,48bc,56,57 (p. 68,69,71)
30 april --- --- geen college 53,54,59bc (p. 71,72)
7 mei NP-volledigheid IV Stelling van Cook 
en verder
college 12 (HJH) 58,59,61,65 (p. 72,73)
14 mei Oude tentamenopgaven   Tentamen van 4 juli 2017 (WK) 63,64,67,60 (p. 72-74)
21 mei Vragenuur --- vragenuur 66,68,67bc (p. 73-75)


Huiswerk

Gedurende het semester moet regelmatig huiswerk worden ingeleverd. Er zullen in 2019 vier huiswerkopgaven komen, die als bonus meetellen voor het eindcijfer voor dit vak. Er valt hiermee maximaal 1 bonuspunt te verdienen. Dit huiswerk bestaat uit speciaal uitgedeelde opgaven, dus NIET de opgaven uit het dictaat. De opgaven uit het dictaat worden (althans een groot deel daarvan) gemaakt tijdens de werkcolleges. De belangrijkste functie van het huiswerk is overigens dat het een goede voorbereiding op het tentamen is: heb je de opgaven serieus gemaakt en begrijp je de stof, dan zou je normaal gesproken het tentamen moeten kunnen halen. Huiswerk gemaakt in voorgaande jaren telt niet mee voor het huiswerkcijfer van het huidige studiejaar.

Huiswerkopgaven dienen individueel (in LaTeX!) gemaakt en ingeleverd te worden. Uiteraard mag je bij het maken van de opgaven met elkaar de problemen en de leerstof bespreken, maar kopieren, overschrijven en dergelijke niet. Dus, geef bij het bespreken van de opgaven elkaar indien nodig een duwtje in de goede richting, tips en suggesties, maar geen panklare oplossing. Daar wordt niemand beter van. Gemaakte huiswerkopgaven kunnen bij de docent (kamer 159) worden ingeleverd, of tijdens de (werk)colleges.

Om de bonus mee te kunnen laten tellen moet het cijfer voor het tentamen (op 1 decimaal nauwkeurig) ten minste een 5,0 zijn. Het eindcijfer voor Complexiteit wordt dan als volgt bepaald. Indien het tentamencijfer >= 5,0: eindcijfer = (gemiddeld huiswerkcijfer)/10 + tentamencijfer. Als het tentamencijfer lager dan 5,0 is, is het eindcijfer gelijk aan het tentamencijfer. Het eindcijfer wordt zoals gebruikelijk afgerond op een geheel- of halftallig cijfer tussen 1 en 10. Niet-ingeleverde huiswerkopgaven tellen als 0.

Hieronder staan de huiswerkopgaven:

Werkcollege-opgaven

In het dictaat staan opgaven, die grotendeels op het werkcollege (of college) behandeld zullen worden. Soms zal er van een enkele opgave een officiele 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.


Tentamen

Het tentamen Complexiteit bevat in elk geval zowel praktische vragen (zoals de werkcollege-opgaven en het huiswerk) als meer theoretische (college). Ook kleine bewijsjes en eenvoudige recurrente betrekkingen zijn mogelijk. Het tentamen is op dinsdag 4 juni van 10.00 tot 13.00 uur.
Op dinsdag 9 juli is de herkansing (van 10.00 tot 13.00 uur).
Er zijn enige oude tentamens Complexiteit beschikbaar om mee te oefenen. Deze zijn hieronder te vinden. Van de tentamens van juni zijn zeer uitgebreide (bedoeld om de antwoorden nog eens uitvoerig uit te leggen) uitwerkingen te vinden.



Vragen en/of opmerkingen kunnen worden gestuurd naar: j.m.de.graaf@liacs.leidenuniv.nl.

Laatste wijziging 4 februari 2019 liacs.leidenuniv.nl/~graafjmde/COMP/