Complexiteit 2011/2012

Het tweedejaarsvak Complexiteit wordt in het voorjaar van 2012 (in principe eenmalig) verzorgd door Johan Kwisthout. Het vak is verplicht voor alle studenten Informatica en levert 6 EC op. Het vak bestaat uit hoorcolleges, werkcolleges, en huiswerkopgaven.

De colleges vinden op maandagen plaats van 11.15 uur tot 13.00 uur in zaal 174. De bijbehorende werkcolleges zijn op dinsdagen van 11.15 uur tot 13.00 uur, in zaal 312. Hierop zijn enkele uitzonderingen: op dinsdag 7 februari is er college in plaats van werkcollege (college op zowel maandag als dinsdag dus); op 9 april en 30 april is er geen college in verband met resp. Tweede Paasdag en Koninginnedag. 10 april en 1 mei zijn, afhankelijk van de doorlooptijd van de stof, hoor- of (waarschijnlijker) werkcollege; dit wordt later bepaald. Zie ook de studiegids of de roosters op internet (via www.liacs.nl). De werkcolleges worden verzorgd door Jurriaan Rot.

Materiaal

Er is een (losbladig) dictaat dat de inhoud van de gebruikte sheets bevat alsmede enige verbindende tekst, en bovendien een verzameling opgaven bij het hoorcollege. Het college zelf bestaat dus uit meer dan alleen de inhoud van het dictaat! Het dictaat (identiek aan dat van 2010/2011) is hier te vinden. Mochten er in de loop van het semester nog veranderingen/aanvullingen komen op dit dictaat, dan zullen die ook hier verschijnen. Overigens zullen eveneens de gebruikte sheets via deze website te raadplegen zijn. Zie hieronder voor het collegeschema.

Ter informatie: een van de door de docent regelmatig voor dit college geraadpleegde boeken is: Computer Algorithms: Introduction to Design & Analysis, S. Baase en A. Van Gelder, Third Edition, Addison Wesley. Dit boek hoeft niet gekocht te worden. Het is voldoende het dictaat en/of de sheets te bestuderen en de bijbehorende opgaven te oefenen.

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

(17-5-2012) De cijfers van opgave 5 zijn bekend. Helaas zijn er wat minder uitwerkingen ingeleverd dan voorgaande opdrachten.

(4-5-2012) De agenda voor maandag (herhalingscollege): beslissingsboom-argument (met opgave), adversary-argument (met opgave), recurrente betrekkingen (recursion tree, substitutie en inductie, Master Theorem), nog een NP-moeilijkheidsbewijs om te oefenen, en wat jullie ter plekke nog aandragen.

(2-5-2012) Hieronder vind je de abstract van de research talk van Todd en Iris.
Many computational models in cognitive science and artificial intelligence face the problem of computational intractability when assumed to operate for unrestricted input domains. Tractability may be achieved by restricting the input domain, but some degree of generality is typically required to model human-like intelligence. Moreover, it is often non-obvious which restrictions will render a model tractable or not. In this talk, we will give an overview of a methodology using mathematical techniques from computational complexity theory that can be used to identify sources of intractability in a model's input domain. We illustrate this methodology by discussing known results for Gentner's Structure-Mapping Theory of analogy derivation as well as the subsidiary processes of analogy-based exemplar retrieval and solution projection invoked in analogical problem solving.

(24-4-2012) Op maandag 14 mei is er vanaf 11.15 in zaal 174 een research talk van Todd Wareham (Memorial University Newfoundland, Canada) en Iris van Rooij (Radboud Universiteit Nijmegen) over het gebruik van complexiteitstheorie als analysemethode voor computationale modellen van cognitie. Titel: Identifying sources of intractability in models of cognition: Conceptual foundations and applications. Zie ook de tutorial die ik samen met Iris, Todd en anderen heb georganiseerd in Berlijn enkele weken geleden. Het herhalingscollege van 14 mei schuift een week op naar 21 mei. Huiswerkopgave 6 staat inmiddels ook online [let op: abusievelijk had ik hier de oude opgave van 2011 geplaatst, die nu opgave 5 is. Nu (27 april) staat hier de juiste versie].

(23-4-2012) Pointers naar het paper van Cook en een alternatief algemeen NP-moeilijkheidsbewijs voor Restricted Graph-coloring van Hans Bodlaender. Simulators van Turing machines kun je downloaden op deze website.

(23-4-2012) De cijfers voor de vierde huiswerkopdracht staan online.

(16-4-2012) Huiswerk 5 staat online. De leerstof van onderdeel a) behandelen we volgende week, b) t/m e) is al behandeld. De inleverdatum is een week later dan aanvankelijk gepland, maar je kunt alvast aan b) t/m e) beginnen als je wilt. Zie n.a.v. het college ook de lijst van Karp op Wikipedia.

(9-4-2012) De cijfers voor de derde huiswerkopdracht staan online.

(2-4-2012) Gerhard Woeginger houdt een lijst bij met pogingen om de relatie tussen P en NP te bewijzen. Wat mij betreft was de meest serieuze nummer 64 van Vinay Deolalikar.

(26-3-2012) Inmiddels werken de scripts weer en is de website up-to-date. Aangezien huiswerkopgave 4 (die nu online staat) de stof van het college van 2 april als voorkennis heeft, heb ik de deadline een week opgeschoven naar 10 april.

(23-3-2012) Jurriaan is op reis naar een conferentie in Estland, vandaar dat de beoordeling van het huiswerk iets langer zal duren...

(19-3-2012) Oefenen met het Master Theorem? Hier staan 22 opgaven en oplossingen om mee aan de slag te gaan. Zoals besproken op het college: omdat er op de huiswerkopgave zelf een foute inleverdatum stond mag je het huiswerk een week later inleveren als je anders planning-problemen krijgt. Denk er wel aan dat de eerstvolgende inlever-deadline al op 3 april op 10 april ligt (ik heb alle data alvast maar in het schema gezet).

(12-3-2012) De cijfers en uitwerkingen voor de tweede huiswerkopdracht staan online. Jurriaan bespreekt het huiswerk morgen (dinsdag 13-3) op het werkcollege.

(12-3-2012) Bijgaand twee artikelen over Merge Insertion sort oftewel het Ford-Johnson algoritme: A tournement problem en The Ford-Johnson algorithm still unbeaten for less than 47 elements.

(5-3-2012) Mocht je de uitleg over Merge sort, Quick sort of Shell sort niet goed begrepen hebben, dan kun je altijd nog een beroep doen op de Universiteit van Sapientia waar ze deze sorteeralgoritmen uitbeelden met behulp van volksdansen ;-)

(29-2-2012) Bij huiswerkopdracht 2 klopten enkele verwijzingen naar collegesheets niet, omdat ze verwezen naar de sheets van 2011. Mocht je de opgave al geprint hebben, pas dit dan even handmatig aan aan de hand van de nieuwe versie.

(29-2-2012) Naast het oefenen met een spel kaarten kan het ook leerzaam zijn om de applets op deze website te bekijken om een beeld te krijgen van de verschillende sorteeralgoritmen. We behandelen niet alle algoritmen op deze pagina, maar wel de belangrijkste.

(28-2-2012) De uitwerkingen en de cijfers voor de eerste huiswerkopgave staan online. Vrijwel iedereen heeft een uitwerking ingeleverd, prima, blijf dat vooral doen!

(27-2-2012) De tweede huiswerkopgave staat online. De deadline is volgende week dinsdag 6 maart. Bij de collegesheets staat ook het uitgewerkte bewijs voor de average complexity van Insertion Sort. Ik heb ook de rest van het voorlopige schema gevuld. Als er geen colleges uitvallen door ziekte of anderszins, hebben we ruimte in het schema om wat extra stof te behandelen. Suggesties van onderwerpen van mijn kant zijn bijvoorbeeld Amortized Analysis, Matrix Multiplication, en/of Order Statistics. Ik moet wel even controleren of er geen overlap is met leerstof uit latere vakken. Sowieso wordt dit geen tentamenstof, maar 'extra' en 'facultatief' voor zover de tijd het toelaat.

(22-2-2012) Er zijn 26 33 opgaven ingeleverd die momenteel nagekeken worden. Voor de volgende keer alvast een verzoekje als je de opdracht mailt: schrijf ook op de uitwerking zelf je naam en studentnummer, dat scheelt mij wat nazoekwerk.

(20-2-2012) Op het hoorcollege bekeken we Opgave 25c: gegeven twee gesorteerde arrays A en B met respectievelijk n en m elementen, geef een gecombineerde, gesorteerde array terug; geef een beslissingsboomargument voor de ondergrens voor het aantal arrayvergelijkingen. Ik ging de fout in bij de uitleg (en daarom was de vraag om verduidelijking meer dan terecht): weliswaar geeft een simpel algoritme in de worst case situatie (A en B overlappen elkaar geheel) m + n - 1 arrayvergelijkingen, maar dat wil niet zeggen dat er ook m + n - 1 mogelijke antwoorden zijn, en daarom klopt ook de gegeven beslissingsboom-ondergrens [ceil(lg (m + n - 1))] niet. Jurriaan zal morgen op het werkcollege deze opgave verder bespreken; de uitwerking zal ik morgen na het werkcollege ook online zetten. Een hint voor wie er vast zelf aan wil werken: laten we C de gecombineerde array noemen. Op welke posities kunnen de elementen van A in C terecht komen? En wat voor gevolgen heeft dit dan voor de elementen van B?

(20-2-2012) Voor wat meer achtergrond: het originele artikel van Blum et al. waarin de auteurs bewijzen dat Selectie in O(n) kan. Deze versie is alleen vanaf de universiteitscomputers vrij te downloaden. Je kunt ook het vrij beschikbare technisch rapport bekijken, maar dit is nog op een typemachine gemaakt en dus niet zo mooi opgemaakt (als gezegd: het algoritme is uit 1973). Als een extra opgave: stel dat we in plaats van groepjes van 5, groepjes van 3 of van 7 nemen. Kijk naar de recurrente betrekking die dan ontstaat. Kunnen we O(n) garanderen met groepjes van 3? En wat is er op tegen om groepjes van 7, 9 of nog groter te nemen?

(14-2-2012) De eerste huiswerkopgave staat online. Heb je het vak vorig jaar al gevolgd, en (een deel van) de huiswerkopgaven al gemaakt? Neem dan even contact met mij op.

(7-2-2012) Ik heb wat oefenopgaven online gezet, alsmede een nettere uitwerking van de recurrente betrekking die op het bord stond en wat voorbeelden van limieten. Mocht je dit vak volgen maar vandaag niet aanwezig zijn geweest of je naam en nummer niet hebben opgeschreven op de lijst die rond ging, wil je die dan emailen naar mij, zodat ik een beeld heb van de studenten die dit vak volgen?

(7-2-2012) Op deze website vond ik een zeer uitgebreide 'cheat sheet' van alle mogelijke formules die je in de theoretische informatica ooit nodig zult hebben. Het overgrote deel hiervan valt buiten het bestek van deze cursus, maar het kan nooit kwaad om er eens naar te kijken en als referentie ergens op te slaan.

Programma

Het programma voor het hoorcollege/werkcollege van het voorjaar 2012 zal hieronder worden bijgehouden. Voor elke week zal daarin vermeld staan 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 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 en 7 februari Inleiding, wiskundige achtergrond H1, H2 slides 1, slides 2 (verbeterd) extra oefenmateriaal en uitwerkingen
13 februari Beslissingsbomen, zoeken H3, H4 slides 3 (verbeterd) 1, 2, 3, 4, 5; HW1 online
20 februari Adversary argument, selectie H5, H6 slides 4 16, 18, 21, 24; HW1 inleveren
27 februari Recurrente betrekkingen, Insertion Sort, ondergrens sorteren H7.1 + 7.3 + sheets slides 5, uitwerking IS 9, 10, 11, 12, 13; HW2 online
5 maart Merge Sort, Quicksort, Shellsort H7.2 + 7.4 + 7.5 slides 6 31, 32, 34, 35, 37; HW2 inleveren
12 maart Restant sorteren H7.6 + 7.7 + sheets slides 7 33, 36, 37, 44, 45; HW3 online
19 maart Polynoom-evaluatie, Eulerkringen, Master theorem H8 + 9 + sheets slides 8 (verbeterd) 39, 40, 42, 43, 44, 45; HW3 inleveren
26 maart Amortized Analysis, Matrix Multiplication geen tentamenstof! slides 9 geen werkcollege, HW4 online
2 april Complexiteitsklassen P, NP, co-NP, EXP H10 + sheets slides 10 47, 48, 49, evt. Master Theorem
10 april geen college op maandag (Tweede Paasdag) ... ... 52, 53, 54, 55, HW4 inleveren
16 april NP-volledigheid, reducties, SAT, Karp's 21 H10.5 - 10.6 + sheets slides 11 59, 60, 61, 62, HW5 online
23 april Turingmachines, non-determinisme, Stelling van Cook H11 + sheets slides 12 geen werkcollege
30 april geen college op maandag (Koninginnedag) ... ... 62 en 63, TM programma, HW5 inleveren
7 mei Uitloop / Q & A / facultatieve extra stof ... ... geen werkcollege, HW6 online
14 mei Research talk Todd Wareham en Iris van Rooij ... achtergrond geen werkcollege, HW6 inleveren
21 mei Bespreken voorbeeldtentamen, Q & A ... ... geen werkcollege

Huiswerk

Vanaf studiejaar 2010/2011 is het vak 6 EC, waar dat voorheen 5 EC was. De extra EC zal terug te zien zijn in het feit het huiswerk nu serieuzer meetelt voor het eindcijfer. Het eindcijfer wordt bepaald als volgt: eindcijfer = 0,1 * gemiddeld huiswerkcijfer + 0,9 * tentamencijfer. Dat betekent enerzijds dat bijvoorbeeld een 5,3 voor het tentamen via een 7,3 (of hoger) kunt compenseren. Anderzijds levert een 5,9 voor het tentamen geen voldoende eindcijfer op als je geen huiswerk hebt ingeleverd. 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. Huiswerkopgaven dienen individueel ingeleverd te worden. Uiteraard mag je bij het maken van de opgaven met elkaar de problemen en de leerstof bespreken (graag zelfs - daar leer je alleen maar meer van), maar kopieren, overschrijven en dergelijke niet. 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.

24-4-2012 - Opgave 6: programma voor Turingmachine - inleveren uiterlijk 15-5-2012

16-4-2012 - Opgave 5: Two-SAT reductie - (inleveren uiterlijk 1-5-2012) - cijfers

26-3-2012 - Opgave 4: kleuringsprobleem - (inleveren uiterlijk 10-4-2012) - cijfers - model-uitwerking

12-3-2012 - Opgave 3: maximum vinden, recursie - (inleveren uiterlijk 27-3-2012) - cijfers

27-2-2012 - Opgave 2: selectie met bijzondere rijtjes - (inleveren uiterlijk 6-3-2012) - cijfers - model-uitwerking

13-2-2012 - Opgave 1: partiele array-som - (inleveren uiterlijk 21-2-2012) - cijfers - model-uitwerking

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 officiele uitwerking verschenen. Deze zijn t.z.t. hieronder te vinden ter referentie. Voor alle andere uitwerkingen van opgaven: bezoek het werkcollege en schrijf ze zelf!

22-4-2012 - Uitwerking opgave 61 en 64

13-3-2012 - Uitwerking opgave 33 en 37

6-3-2012 - Uitwerking opgave 31 en 34

21-2-2012 - Uitwerking opgave 25c

14-2-2012 - Uitwerking opgave 3e

Tentamen

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. Het tentamen is op dinsdag 19 juni 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 uigebreide (bedoeld om de antwoorden nog eens uitvoerig uit te leggen) uitwerkingen te vinden.

Vragen en/of opmerkingen kunnen worden gestuurd naar: kwisthou@liacs.nl.

Laatste wijziging 27 april 2012 - http://www.liacs.nl/home/kwisthou/COMP/