Complexiteit 2024/2025

Het tweedejaarsvak Complexiteit (officieel: Complexity) wordt in het voorjaar van 2025 verzorgd door Jeannette de Graaf en Mark van den Bergh. De assistentie, waaronder de begeleiding van de werkcolleges, wordt verleend door Pjotr Beerens, Perri van den Berg, Angela van Delft en Niels Heslenfeld. Complexiteit is verplicht voor alle studenten Informatica en levert 6 EC op. Het vak bestaat uit hoorcolleges, werkcolleges, huiswerkopgaven en een afsluitend tentamen.
Studenten die deel gaan nemen aan Complexiteit wordt verzocht zich voor alle onderdelen van het vak in te schrijven via MyStudyMap. Schrijf je ook meteen in voor het tentamen! Overigens vind je in de e-studiegids bij de algemene beschrijving van elk vak meer informatie over het inschrijven voor vakken en tentamens. Ook meer over inschrijven voor vakken en tentamens op de Brightspacepagina van de bachelor Informatica onder de tegel Studiezaken.
Let op: het vak Complexiteit in de huidige vorm wordt dit jaar voor het laatst gegeven. Het is dus aan te raden dat je dit vak actief volgt en het huiswerk serieus maakt, zodat je het tentamen straks haalt.

De hoorcolleges vinden plaats op vrijdagen van 11.00 uur tot 12.45 uur in het Gorlaeusgebouw, zaal BW.0.40. Het bij de colleges behorende werkcollege is aansluitend op vrijdagmiddagen van 13.15 uur tot 15.00 uur in zalen BW.0.29 en BW.0.30 van het Gorlaeusgebouw. Op 28 maart (hertentamenweek, week 13) is er geen college en geen werkcollege. Hetzelfde geldt voor 18 april (Goede Vrijdag, week 16). Zie ook het globale rooster of kijk in MyTimeTable.

Informatievoorziening

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 (extra) belangrijke mededelingen. Ook kun je daar, via het discussieforum vragen stellen. Vragen stellen in persoon of per mail worden ook beantwoord (en misschien zelfs sneller).

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 2025 is reeds beschikbaar. Deze verschilt niet essentieel van de versie van 2024. Hoofdstuk 2 (wiskundige achtergrond) wordt niet expliciet op college behandeld. Het is de bedoeling dat je dat hoofdstuk zelf bestudeert. 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, in 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 2025 bijgehouden worden. Voor elke week zal daarin vermeld staan welke onderwerpen aan de orde zijn gekomen met de bijbehorende stukken 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 deze site gezet; direct na het college wordt dit zonodig aangepast naar de definitieve versie. Na het werkcollege zullen in onderstaand schema tevens antwoorden van de gemaakte opgaven worden geplaatst. Van sommige opgaven is een uitgebreidere uitwerking te vinden verderop op deze pagina, onder het kopje Werkcollege-opgaven.


# Datum Zaal Onderwerp Dictaat Sheets Werkcollege: opgaven
1 7 februari BW.0.40 Inleiding ... ... ...

Huiswerk

Gedurende het semester zijn er (maximaal) vier huiswerkopdrachten om in te leveren. 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 belangrijkste functie van het huiswerk is echter 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.

De huiswerkopdrachten dienen individueel te worden gemaakt (in LaTeX!), en vervolgens ingeleverd op Brightspace. Uiteraard mag je bij het maken van de opgaven met elkaar de problemen en de leerstof bespreken, maar kopieren, overschrijven en dergelijke zijn niet toegestaan. 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.

Met de huiswerkopdrachten is maximaal 1 bonuspunt te verdienen. 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 op dit moment nog de huiswerkopgaven van 2024.


Werkcollege-opgaven

In het dictaat staan opgaven, die grotendeels op het werkcollege (of college) behandeld zullen worden. Soms is er van een enkele opgave een uitgebreidere uitwerking beschikbaar. Deze uitwerkingen zijn hieronder te vinden ter referentie. Voor alle andere uitwerkingen van opgaven: bezoek het werkcollege en schrijf ze zelf!

Op dit moment staan hieronder nog de uitwerkingen van 2024. In de loop van dit semester zullen ---indien nodig--- die 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 woensdag 28 mei 2024 van 09:00 tot 12:00 uur.
Op dinsdag 1 juli 2025 is de herkansing (van 09:00 tot 12: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. 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: j.m.de.graaf@liacs.leidenuniv.nl.

Laatste wijziging 30 december 2024 liacs.leidenuniv.nl/~graafjmde/COMP/