Complexiteit 2016/2017

Het tweedejaarsvak Complexiteit wordt in het voorjaar van 2016 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 12151). Je bent dan meteen aangemeld voor het tentamen. Zie hier voor informatie over inschrijven voor vakken/tentamens.

De colleges vinden plaats op dinsdagen van 11:15 uur tot 13:00 uur in zaal 174. De bij de colleges behorende werkcolleges (in twee groepen) zijn op dinsdagmiddagen van 13:45 uur tot 15:30 uur, in zaal 405 en zaal 408. uitzonderingen. Let op:op dinsdag 31 januari is er 's middags college (in zaal 407-409) 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 13 maart geen college en geen werkcollege omdat er dan herkansingen 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! Inmiddels staat hier de goede versie van het dictaat, namelijk de versie van 2017. Mochten er in de loop van het semester veranderingen/aanvullingen komen op dit dictaat, dan zullen die veranderingen op deze website gemeld worden. Overigens zijn eveneens de gebruikte sheets via deze website te raadplegen. 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

16-07-2017 - Nu beschikbaar: de eindcijfers van het hertentamen Complexiteit van 4 juli.

14-07-2017 - Uiterlijk maandag 17 juli aanstaande zullen de cijfers van het hertentamen van 4 juli op deze website worden gezet. Uw docent is bijna klaar met nakijken.

29-06-2017 - Er is nu ook een uitwerking van het juni-tentamen. Zie verderop op deze pagina.

27-06-2017 - Inmiddels zijn beschikbaar een lijstje met de huiswerkcijfers en een lijstje met de eindcijfers van Complexiteit. Het hertentamen is op 4 juli.

25-06-2017 - Een paar uur later dan gehoopt, maar hier dan toch de beloofde resultaten van het tentamen Complexiteit van ruim twee weken geleden. Er staat alleen voor iedereen in of deze het vak gehaald heeft of niet. De definitieve tentamencijfers met eindcijfers volgen binnenkort, evenals een uitwerking van het tentamen.

23-06-2017 - Het tentamen van 8 juni is bijna nagekeken. Naar verwachting is het morgen (24 juni) helemaal klaar, en dan zal ik in elk geval een tussenstand op de website plaatsen waarin voor elke student staat of hij/zij het tentamen/vak gehaald heeft of niet. De definitieve cijfers, met verwerking van de huiswerkbonus komt dan begin volgende week.

06-06-2017 - Het tentamen van 8 juni is in zaal 412 en 312. Tijd: 10-13 uur.

02-06-2017 - Het vragenuur zal op 6 juni plaatsvinden in zaal 174. Aanvang: 11 uur.

29-05-2017 - Er staan uitgebreide uitwerkingen van de huiswerkopgaven online. Alle huiswerk is overigens nagekeken; nagekeken werken kunnen bij de docent worden afgehaald. Doe dit ook, zodat je weet wat je fout hebt gedaan. Een lijst met behaalde huiswerkcijfers zal t.z.t. nog verschijnen.

18-05-2017 - Er is op college een vragenuur vastgesteld voor het tentamen. Dit vragenuur zal zijn op dinsdag 6 juni. Het begint om 11 uur. De zaal zal nog bekend worden gemaakt via het mededelingenscherm en/of deze website.

01-05-2017 - Er is een uitgebreide uitwerking beschikbaar van de eerste huiswerkopgave (zie aldaar). Van de overige huiswerkopgaven zal t.z.t. ook een uitwerking op de site gezet worden.

01-05-2017 - Enige notatie aangepast in het dictaat. Geen inhoudelijke veranderingen.

25-04-2017 - Huiswerkopgave vijf is beschikbaar. Huiswerkopgave 2 is sinds vorige week nagekeken; huiswerk 3 sinds vanmiddag. Het nagekeken werk is bij de docent af te halen. De tweede en derde opgave zijn iets strenger beoordeeld dan huiswerk 1.

17-04-2017 - Huiswerkopgave vier is nu beschikbaar.

13-04-2017 - De vierde huiswerkopgave is nu nog niet af, maar het is wel de bedoeling die morgen of overmorgen gereed te hebben. Ik zal de opgave zodra die klaar is op de site zetten (hopelijk werkt alles nog steeds vanaf huis; zo niet, dan wordt het dinsdagochtend vroeg).

11-04-2017 - Er is vanmiddag gewoon werkcollege: zaal 405.

10-04-2017 - Er stond een klein foutje in de voetnoot van huiswerkopgave 3. Er stond de sommatie van i=0 tot l van niets, maar dat moet natuurlijk zijn: de sommatie van i=0 tot l van 3^i. Dit foutje is verbeterd; zie hieronder bij het huiswerk zelf.

28-03-2017 - De derde huiswerkopgave staat online. Zie verderop op deze pagina. Het staat altijd bovenaan het huiswerk zelf, maar graag benadruk ik nog een keer extra dat van je verwacht wordt dat je bij alle antwoorden duidelijk aangeeft hoe je eraan komt. Probeer ook precies te zijn.

24-03-2017 - De nagekeken eerste huiswerkopgaven kunnen worden afgehaald bij de docent, bijvoorbeeld op dinsdagen voor/na het college. Het is verstandig om te bekijken wat je fout hebt gedaan, dus haal je nagekeken werk zeker af. Een uitwerking van het huiswerk zal nog op de website worden geplaatst.

14-03-2017 - De tweede huiswerkopgave staat nu online. Zie verderop op deze pagina.

10-03-2017 - De tweede huiswerkopgave is nog niet gereed, maar zal maandag 13 of dinsdag 14 maart op deze website vershijnen. De uiterste inleverdatum zal dinsdag 28 maart zijn, dus er is meer dan genoeg tijd om de huiswerkopgave te maken. Doe dat ook, want het is een goede oefening.

27-02-2017 - Het dictaat van 2016 is inmiddels waar nodig verbeterd/uitgebreid, resulterend in de versie van 2017. Hierboven op de website te vinden.

24-02-2017 - Lever gemaakte huiswerkopgaven bij de docent in per e-mail (j.m.de.graaf@liacs.leidenuniv.nl) of overhandig dit persoonlijk.

17-02-2017 - De eerste huiswerkopgave is gepubliceerd en staat verderop op deze pagina. Probeer precies en gestructureerd te werken. Bekijk als voorbeelden uitwerkingen van soortgelijke sommen uit de opgaven of oude tentamens.

14-02-2017 - Er is een uitwerking van opgave 6 op de website gezet. Tevens is een aantal uitwerkingen gecontroleerd, eventueel aangepast/uitgebreid en voorzien van het label 2017.

06-02-2017 - Op dinsdag 7 februari is het eerste werkcollege. Dit vindt plaats in zaal 405 en zaal 408. De bedoeling is dat elke werkgroep ongeveer evenveel studenten bevat. Daarom worden studenten waarvan de achternaam begint met A t/m Maa geacht naar zaal 405 te gaan; de rest zit dan in 408. Zorg dat je de opgaven (zie dictaat) bij je hebt.

02-01-2017 - Het eerste college is op dinsdag 31 januari van 11:15 tot 13:00 uur. Het tweede college is op dezelfde dag van 13:45 tot 15:30 uur. 's Morgens is het college in zaal 174; 's middags in zaal 407-409.

Programma

Hieronder wordt het programma voor het hoorcollege/werkcollege van het voorjaar 2017 bijgehouden. 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
31 januari Inleiding, wiskundige achtergrond 1.1 t/m 2.2 college1, college2 college i.p.v. werkcollege
7 februari Restant wiskunde, zoeken 2.3, 4.1-3 college3 1, 2, 4, 7
14 februari Binair zoeken, beslissingsbomen 4.4, 3 college4 (6), 8, 9, 10, 20
21 februari Selectie, toernooimethode, adversary argument 5, 6.1-4 college5 20, 22, 18, 14.b.
28 februari Min & max, selectie is O(n), insertion sort 6.5-6, 7.1 college6 15, 16, (22), 23, 24
7 maart Mergesort, ondergrens sorteren 7.2-3 college7 26, 27, 31, extra
14 maart geen college --- --- geen werkcollege
21 maart Quicksort, Shellsort 7.4-5 college8 29, 33, 34, 35, 36
28 maart Optimaal sorteren, O(n)-sorteren, polynoomevaluatie 7.6-7, 8.1-3 college9 39, 40a,b,c, 41, 42, 43
4 april Matrixvermenigvuldiging, Euler- en Hamiltonkring 8.4, 9 college10 geen werkcollege
11 april NP-volledigheid I 10.1-2, 10.3.1, 11 college11 38, 44, 45, 47, 48b,c
18 april NP-volledigheid II 10.3-4 college12 56, 57, extra2, 49(, 50), 53, 54
25 april NP-volledigheid III 10.5.2, 10.6.1-2 college13 58, 59bc, 61, 64
2 mei NP-volledigheid IV 10.5.2-3, 10.6.4, stelling van Cook college14 60, 63, 65
9 mei NP-volledigheid V 10.6.5, co-NP, Pspace, ... college15 66, 67, 68
16 mei oud tentamen --- juli 2016 geen werkcollege


Huiswerk

Gedurende het semester moet regelmatig huiswerk worden ingeleverd. Er zullen in 2017 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. Mocht blijken dat 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 het vak te halen moet het cijfer (op 1 decimaal nauwkeurig) voor het tentamen 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 2017:

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 2015/2016) 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 donderdag 8 juni van 10:00 tot 13:00 uur. Dinsdag 6 juni is er een vragenuur. Aanvang: 11:00 uur. Het vragenuur vindt plaats in zaal 174
Op dinsdag 4 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 16 juli 2017 liacs.leidenuniv.nl/~graafjmde/COMP/