Complexiteit 2017/2018

Het tweedejaarsvak Complexiteit wordt in het voorjaar van 2018 verzorgd door Jeannette de Graaf. 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 12872). Je bent dan meteen aangemeld voor het tentamen. Ga hiertoe naar de faculteitswebsite (NL) en daarvandaan Informatie voor studenten > Administratie > Inschrijven voor vakken en tentamens en dan kiezen voor het tabblad Wiskunde en Natuurwetenschappen.

De colleges vinden plaats op dinsdagen van 11.00 uur tot 12.45 uur in zaal 174. De bij de colleges behorende werkcolleges (in twee groepen) zijn op dinsdagmiddagen van 13.30 uur tot 15.15 uur, in zaal 402 en zaal 403. Let op: dinsdag 6 februari 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 12 maart 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 2018 is inmiddels verkrijgbaar. Deze verschilt nauwelijks van de versie van 2017 (alleen een opgave toegevoegd). 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

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

09-07-2018 - Het (her)tentamen Complexiteit vindt morgen, 10 juli, plaats in Snellius zaal B2. Tijd: 14-17 uur.

09-07-2018 - De uitwerking van het juni-tentamen is nu volledig.

06-07-2018 - Er is nu ook een uitwerking van het juni-tentamen beschikbaar. Opgave 5 ontbreekt, maar staat uiterlijk maandagochtend ook in de uitwerking. Tevens is in de uitwerking van het tweede huiswerk een kleine verbetering aangebracht. Daar was een andere (niet foute) beginconditie gebruikt dan voor de hand ligt. Dat is nu hersteld. De oplossing blijft gewoon hetzelfde.

02-07-2018 - De mails met het eindcijfer zijn intussen verstuurd. Mocht je je tentamen willen inzien, kom dan bij voorkeur donderdag 5 juli of vrijdagmiddag 6 juli langs. Woensdag ben ik er in elk geval niet.

02-07-2018 - Het tentamen is bijna nagekeken. Vandaag zal ik er de laatste hand aan leggen, en zodra ik alles heb nagekeken zal ik iedereen individueel een mail sturen (via je umail-adres) met daarin het eindcijfer en je gemiddelde huiswerkcijfer. In het eindcijfer zal het huiswerkcijfer al verwerkt zijn.

12-06-2018 - Het tentamen van donderdag 14 juni 2018 (10.00-13.00) zal plaatsvinden in Snellius zalen B2 en B3.

11-06-2018 - Het vragenuur zal op dinsdag 12 juni gehouden worden in Snellius zaal 405. Aanvang: 11.00 uur.

04-06-2018 - Huiswerk 5 is nu ook nagekeken en alle huiswerkuitwerkingen zijn compleet.

29-05-2018 - Er is nu ook een uitgebreide uitwerking van Huiswerk 3 beschikbaar. Zie verderop op deze pagina. In de komende tijd zullen meer uitwerkingen op de site verschijnen. Ik kondig ze niet meer telkens aan in Nieuws / updates, dus houd zelf deze website in de gaten.

28-05-2018 - Huiswerk 4 is nu wel nagekeken. Het nagekeken werk kan bij de docent (Snellius, kamer 151) worden afgehaald. Tevens is nu een uitgebreide uitwerking van Huiswerk 2 beschikbaar. Zie verderop op deze pagina.

24-05-2018 - Huiswerk 4 is nog niet nagekeken/beschikbaar. Zodra dat wel het geval is zal dat op deze website onder Nieuws / updates worden gemeld. Hetzelfde geldt voor Huiswerk 5.

22-05-2018 - Indien je je niet kon inschrijven voor het tentamen .... de capaciteit is inmiddels opgehoogd, dus iedereen kan zich weer aanmelden.

18-05-2018 - Huiswerk 4 zal vermoedelijk nagekeken zijn op 22 mei, en kan bij college worden afgehaald, of op enig moment bij de docent zelf (kamer 151). Dit geldt ook voor de andere nagekeken huiswerken. Wanneer huiswerk 5 is nagekeken zal ik dat op via de website laten weten. Cijfers mogen niet meer via internet worden bekendgemaakt, dus de huiswerkcijfers zullen niet op deze website komen te staan. Sowieso is het nuttig om je nagekeken huiswerk terug te hebben, dus kom gewoon langs.

18-05-2018 - Het college van dinsdag 22 mei zal besteed worden aan het (voor)maken van enkele oude tentamenopgaven. Mocht je voorkeur voor een bepaalde som of een bepaald soort opgave hebben, laat dat dan even weten. In elk geval doen we opgave 4 van het tentamen van juli 2017. Er is op 22 mei geen werkcollege meer.

08-05-2018 - Er zullen nog (bijtijds) uitwerkingen op de website komen van de huiswerkopgaven.

08-05-2018 - Volgende week is het laatste gewone college. Het college bevat het restant NPC (en beyond) en nog wat losse eindjes. Zo is het mijn bedoeling is om daar -naar aanleiding van huiswerk 3- nog even het beslissingsboomargument door te nemen en wellicht gezamenlijk een oude tentamenopgave over dit onderwerp te maken. Als daar behoefte aan is kan op 22 mei nog een college worden besteed aan het voormaken van (sommen uit) een oud tentamen. Verder kunnen we, als daar belangstelling voor bestaat, een datum/tijd voor een vragenuur voor het tentamen van 14 juni afspreken.

08-05-2018 - De derde huiswerkopgave is nagekeken en kan worden afgehaald bij de docent (niet op woensdagen).

30-04-2018 - De vijfde huiswerkopgave staat online.

30-04-2018 - Er is een kleine verandering aangebracht in het dictaat. Op pagina 46 (stelling onderaan) en pagina 47 (bovenaan; reductiemethode) zijn de rollen van P en Q verwisseld. Dit is geen inhoudelijke verandering, maar is wellicht wat consequenter.

19-04-2018 - De vierde huiswerkopgave is inmiddels beschikbaar. Hij gaat over Turingmachines, zoals bij college 11 en in hoofdstuk 11 van het dictaat behandeld. Zie verderop op deze website. Bij het werkcollege van 24 april zal ook nog een Turingmachine-opgave worden gemaakt. Aan te raden als voorbereiding op de huiswerkopgave.

16-04-2018 - Bij onderdeel e. werd verwezen naar de ondergrens uit b., en deze werd daar opnieuw genoemd. Daar had ik de 2 nog niet in een 4 veranderd. Nu wel. Voor de vraag bij e. maakt dat verder niet uit, maar nu staat het er in elk geval goed. Nog een waarschuwing bij b: merk op dat 2*(\lceil \lg n \rceil) niet gelijk is aan \lceil 2*(\lg n) \rceil.

12-04-2018 - Let op! Nog een foutje in de derde huiswerkopgave ontdekt. Bij onderdeel b. heb ik een nare overtypfout gemaakt. Er stond dat je moest aantonen dat er ten minste 2lg n - 2 arrayvergelijkingen moeten worden gedaan. Dat moet zijn: 2lg n - 4. Zie de aangepaste opgave verderop op deze pagina. Met dank aan de opmerkzaamheid van Sylvester.

06-04-2018 - In de derde huiswerkopgave stond bij onderdeel b. beslissingsargument. Dit moet natuurlijk beslissingsboomargument zijn. Ik heb dit verbeterd in de opgave die op deze website staat.

05-04-2018 - De derde huiswerkopgave is inmiddels beschikbaar. Zie verderop op deze website.

03-04-2018 - De derde huiswerkopgave zal uiterlijk donderdag 5 april op deze website te vinden zijn.

03-04-2018 - De eerste huiswerkopgave is nagekeken. Het nagekeken werk (met cijfer) kan bij de docent worden afgehaald. Er komt nog een uitwerking op de website.

19-03-2018 - De tweede huiswerkopgave staat inmiddels online. Deze gaat over inversies en er moet een recurrente betrekking worden opgelost.

27-02-2018 - Verderop, bij de huiswerkopgave zelf, is een kleine toelichting op de vraagstelling bij 1c van de eerste huiswerkopgave toegevoegd. Ter illustratie is daar ook een extra voorbeeldopgave met uitwerking te vinden. Zie verder voor meer voorbeelden de sommen die op het werkcollege worden gemaakt.

27-02-2018 - Let op! Voor degenen die de papieren versie van huiswerkopgave 1 hebben: bij onderdeel d. moet gelden dat n>2. Voor n=2 worden namelijk altijd 2 arrayvergelijkingen gedaan, dus daarvoor is 2 vergelijkingen wel haalbaar.

26-02-2018 - In het sommengedeelte van het dictaat is een kleine verandering aangebracht. Opgave 21 is een klein beetje veranderd; verder is alles als voorheen. De uitwerking van 21 zal ook nog aangepast worden. De uiteindelijke, bij de nieuwe formulering passende, versie zal herkenbaar zijn aan het jaar 2018. Nu staat er nog (versie 2016).

26-02-2018 - De eerste huiswerkopgave is inmiddels beschikbaar. Uiterste inleverdatum is vrijdag 9 maart. Stuur je uitwerking (in LaTex) naar j.m.de.graaf@liacs.leidenuniv.nl en begin het onderwerp met [COMP], zodat de huiswerkmails voor jullie docent makkelijk te herkennen zijn. Bezoek het werkcollege voor nog wat extra oefening met soortgelijke opgaven als die van het huiswerk.

19-02-2018 - De bedoeling is dat volgende week de eerste huiswerkopgave wordt uitgedeeld. Die gaat over het analyseren van een algoritme (basisoperatie, worst case, best case) dat deze en volgende week ook tijdens het werkcollege zal worden geoefend.

12-02-2018 - De indeling voor de werkgroepen gaat op achternaam. Studenten van wie de achternaam begint met A t/m K gaan naar zaal 402; de rest naar zaal 403. Het is de bedoeling dat in beide zalen ongeveer evenveel studenten zitten.

19-12-2017 - Het eerste college is op dinsdag 6 februari van 11.00 tot 12.45 uur. Het tweede college is op dezelfde dag van 13.30 tot 15.15 uur. Zowel 's morgens als 's middags is het college in zaal 174.

Programma

Hieronder zal het programma voor het hoorcollege/werkcollege van het voorjaar 2018 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.


Datum (hoorcollege) Onderwerp Dictaat Sheets Werkcollege: opgaven
6 februari Inleiding, wiskundige achtergrond 1.1 t/m 2.2, 2.3 deels college1, college2 college i.p.v. werkcollege
13 februari Restant, zoeken 2.3 rest, 4.1-4 college3 1,2,4,7(,6)
20 februari Restant, beslissingsbomen Opgave 5, 3.1-3 college4 8,9,10,20
27 februari 28bc, Selectie, toernooimethode, adversary argument 6.1-4, 5.1-2 college5 18,22,14b,21
6 maart Adversary min&max, selectie is O(n), Insertion sort 6.5-6, 7.1 college6 15,16,14a,23
13 maart geen college --- --- geen werkcollege
20 maart Mergesort, ondergrens sorteren, Quicksort (deels) 7.2-4 college7 24,26,27,extra
27 maart Restant, Shellsort, optimaal sorteren 7.4-6 college8 31,33,29,34,35
3 april Merge Insertion sort, O(n)-sorteren, polynoomevaluatie 7.6-7, 8.1-3 college9 (34,35,)38,39,40,41
10 april Matrixvermenigvuldiging, Euler- en Hamiltonkringen, .. 8.4, 9.1-2 college10 41cd,42,43,44,45(,46)
17 april NP-volledigheid I 10.1-3.1, 11 college11 restant,47,48bc,56,57
24 april NP-volledigheid II 10.3.2, 10.4 college12 restant, extra2, 53,54,59bc
1 mei NP-volledigheid III 10.5, 10.6.1 college13 58,59 restant,61,65
8 mei NP-volledigheid IV Stelling van Cook,10.6.2,10.6.4 college14 63,64,67,60
15 mei NP-volledigheid V 10.6.3 college15 66,68,67bc,opgave 4 juli 2017
22 mei Oude tentamenopgaven --- --- geen werkcollege


Huiswerk

Gedurende het semester moet regelmatig huiswerk worden ingeleverd. Er zullen in 2018 vijf 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.

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 worden ingeleverd (per e-mail (j.m.de.graaf@liacs.leidenuniv.nl) of persoonlijk).

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. Eindcijfer = (gemiddeld huiswerkcijfer)/10 + tentamencijfer indien het tentamencijfer >= 5,0. 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,0 en 10,0.

Hieronder staan de huiswerkopgaven van 2018:

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!


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 donderdag 14 juni van 10.00 tot 13.00 uur. Dinsdag 12 juni is er een vragenuur. Aanvang: 11.00 uur. Het vragenuur zal plaatsvinden in het Snellius, zaal 405.
Op dinsdag 10 juli is de herkansing (van 14.00 tot 17.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 9 juli 2018 liacs.leidenuniv.nl/~graafjmde/COMP/