Algoritmiek 2009/2010

Het eerstejaarsvak Algoritmiek wordt in het voorjaar van 2010 verzorgd door Jeannette de Graaf. Het vak is verplicht voor alle studenten Informatica, Informatica en Economie, en voor studenten die een dubbele propedeuse Wiskunde/Informatica doen. Het vak levert 7 EC-punten op. Assistentie bij de werkgroep en het practicum wordt verleend door Tijn Witsenburg en Wouter Duivesteijn.

De colleges zijn op vrijdagen van 11.15 tot 13.00 uur in zaal 174. De bijbehorende werkcolleges vinden plaats op donderdagen van 9.00 uur tot 10.45 uur, in zaal 174 of een van de computerzalen. Het eerste college is op vrijdag 5 februari 2010; het eerste werkcollege is op donderdag 11 februari.

LET OP: het voorlaatste college is op dinsdag 18 mei van 9.00-10.45 uur in zaal 412.

Voorkennis voor dit vak is het college Programmeermethoden. Het college dat op Algoritmiek aansluit heet Datastructuren; dit wordt gegeven in het najaar (derde semester van de studie Informatica).

Inhoud van het vak

Algoritmiek gaat uiteraard over algoritmen. Er zullen enkele belangrijke, veel gebruikte oplossingsmethoden worden besproken, compleet met voorbeelden. Besproken worden in elk geval: brute force, exhaustive search, backtracking, verdeel en heers, dynamisch programmeren, gretige algoritmen en branch and bound. Verder onder meer ook toestand-actie-ruimtes (als hulp bij het probleeemoplossen), een beetje complexiteit (om de efficientie van algoritmen te beschrijven en te vergelijken) en heapsort.

Voor globale informatie over het vak in studiejaar 2009-2010 wordt men verwezen naar de algemene webpagina.

Materiaal

In het studiejaar 2009/2010 wordt, evenals in voorgaande jaren, gebruik gemaakt van het volgende boek: Anany Levitin, Introduction to The Design and Analysis of Algorithms, second edition (Addison-Wesley, 2007). Of de internationale editie van hetzelfde boek.

De bij het college behorende sheets zijn ook via deze website beschikbaar. Meestal zullen de sheets al voor het college op deze webpagina verschijnen: er kunnen daarin dan nog kleine veranderingen worden aangebracht, afhankelijk van hoe ver we op college komen. Na afloop van het college wordt de definitieve versie van de sheets hieronder geplaatst.

Programma

Het programma van colleges en werkcolleges wordt hieronder bijgehouden. Voor elke week staat daarin welke onderwerpen aan de orde zijn gekomen, met de bijbehorende hoofdstukken uit het boek en de gebruikte sheets. De datum stelt de vrijdag van de betreffende week voor. Bovendien kan men hier de bij het werkcollege behandelde opgaven vinden.

PROGRAMMA 2009/2010

Datum (vrijdag) Onderwerp Sheets Boek Werkcollege
5 februari Introductie sheets1 1.1, 1.2, 1.4 (t/m graafrepresentaties) geen
12 februari Grafen en bomen sheets2 1.4 opgaven1
19 februari Toestand-actie-ruimte sheets3 sheets opgaven2
26 februari geen college -- -- geen werkcollege
5 maart Complexiteit, brute force sheets4 2.1-3; 3.1-3 opgaven3
12 maart Exhaustive search, backtracking sheets5 3.4; sheets; 12.1 Programmeeropdracht 1
19 maart Backtracking, verdeel en heers sheets6 12.1; 4.1-2 opgaven5
26 maart Verdeel en heers sheets7 4.3-6; 5.1; 5.5 opgaven6
2 april maart Goede Vrijdag: geen college ... ... Programmeeropdracht 2
9 april Rest decrease and conquer, dynamisch programmeren sheets8 sheets; 8 inl opgaven8
16 april Dynamisch programmeren sheets9 8.1; sheets; 8.4 geen werkcollege
23 april Gretige algoritmen sheets10 9 inl.; 9.3; sheets opgaven9
30 april Koninginnedag: geen college ... ... Programmeeropdracht 3
7 mei Dijkstra; branch & bound sheets11 9.3; 12.2 opgaven11
14 mei Henelvaart: geen college --- --- geen werkcollege
21 mei Branch & bound; heapsort sheets12 12.2; 6.4 opgaven12

Opgaven

Tijdens werkcolleges worden opgaven gemaakt, soms op papier en soms achter de computer. Deze opgaven kunnen via deze website worden verkregen, maar zullen ook tijdens (werk)college worden uitgedeeld. Zie voor informatie over het tweede werkcollege (binaire bomen en binaire zoekbomen) ook de Algoritmiek webpagina van Tijn Witsenburg. Daar is tevens een uitwerking te vinden. Van de opgaven van het werkcollege van 18 maart 2010 (exhaustive search en backtracking) zijn de antwoorden beschikbaar.

Programmeeropdrachten

Bij dit college moeten drie programmeeropdrachten (in C++) gemaakt worden, waarbij de nadruk ligt op het toepassen van de op college besproken probleemoplossingsmethoden. De opdrachten moeten alle drie voldoende zijn (>=6). Programmeerwerk mag in tweetallen worden gemaakt. De opdrachten dienen op de deadlines te worden ingeleverd. Anders gaat er in principe per week te laat inleveren een punt af.

Alle programmeeropdrachten voor dit studiejaar zijn inmiddels beschikbaar. Eventuele opmerkingen of tips daarbij zullen via deze plek worden bekendgemaakt.

Het is verstandig de opgave op te delen in iets kleinere stukken. Bijvoorbeeld zoals hierna aangegeven. Maak eerst een programma dat het spel tegen de computer kan spelen, waarbij de computer gewoon random zet. Schrijf daartoe een memberfunctie die zo'n randomzet bepaalt. Vervolgens gaan we het beste-zet-gedeelte toevoegen. Hiervoor moet een memberfunctie geschreven worden die recursief bepaalt of een stand winnend is en wat in dat geval een winnende zet is (zie de programmeeropdarcht). Schrijf ten slotte het deel van het programma dat een best lijkende zet uitvoert. Hierbij kun je overigens de functie die een random zet bepaalt, en die je al eerder geschreven hebt, goed gebruiken. Meer informatie, zoals over het schrijven van het verslag in LaTex, is te vinden op de reeds genoemde webpagina van Tijn Witsenburg.

Eindcijfer

Vanaf studiejaar 2009/2010 telt het programmeerwerk, net als bij Programmeermethoden, mee voor het eindcijfer. Het eindcijfer wordt voor twee derde bepaald door het tentamencijfer, en voor een derde door het programmeerwerk. Zowel programmeerwerk als tentamen moeten daarbij voldoende zijn.

Tentamen

De tentamens van 2008, 2009 en 2010 zijn hieronder te vinden, alsmede uitwerkingen van de juni-tentamens.


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

16 augustus 2010 - http://www.liacs.nl/home/graaf/ALGO/