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.

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 2008/2009

Werkcollege

Datum (vrijdag)	Onderwerp	Sheets	Boek
6 februari	Introductie	sheets1	1.1, 1.2, 1.4 (t/m graafrepresentaties)	geen
13 februari	Grafen, bomen, toestand-actie-ruimte	sheets2	1.4 (grafen,bomen) + sheets	opgaven1
20 februari	Toestand-actie-ruimte, complexiteit	sheets3	sheets + 2.1	opgaven2
27 februari	Complexiteit, brute force, exhaustive search	sheets4	2.2-4, 3.1-3	opgaven3
6 maart	Exhaustive search, backtracking	sheets5	3.4 + sheets + 12.1 (deels)	programmeeropdracht 1 (302/304)
13 maart	Backtracking, Verdeel en heers	sheets6	12.1 + 4.1-2	opgaven5
20 maart	Verdeel en heers	sheets7	4.3-4, 4.5 (deels), 4.6 (deels), 5.1, 5.5	programmeeropdracht 1 (302/304)
3 april	Decrease and conquer, dynamisch programmeren	sheets8	sheets, intro H8	opgaven7
10 april	Goede vrijdag: geen college	...	...	programmeeropdracht 2 (302/304)
17 april	College uitgevallen	...	...	programmeeropdracht 2 (302/304)
24 april	Dynamisch programmeren, gretige algoritmen	sheets9 + sheets10	sheets, 8.1, 8.4, intro H9	opgaven10
1 mei	Algoritme van Dijkstra + branch & bound	sheets11	9.3 + 12.2 (deels)	geen werkcollege
8 mei	Branch & bound, heap(sort)	sheets12	12.2 (rest) + 6.4	opgaven11
15 mei	Oude tentamenopgaven	...	...	do: programmeeropdracht 3 (302/304); vr: opgaven (174): opgaven13

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.

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.

De programmeeropdrachten hieronder zijn van het afgelopen studiejaar 2008/2009. T.z.t. zullen op deze plek de nieuwe opdrachten komen te staan.

Programmeeropdracht 1 (brute force). Uiterste inleverdatum: vrijdag 20 maart.

Programmeeropdracht 2 (backtracking). Uiterste inleverdatum: vrijdag 17 april.

Programmeeropdracht 3 (dynamisch programmeren). Uiterste inleverdatum: vrijdag 15 mei.

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

Het tentamen vindt plaats op dinsdag 1 juni 2010, 10.00-13.00 uur.

Het hertentamen wordt gehouden op dinsdag 3 augustus 2008, 10.00-13.00 uur.

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

Tentamen van juni 2008, met uitgebreide uitwerking en bijbehorende toestandactieruimte

Tentamen van augustus 2008.

Tentamen van juni 2009, met uitgebreide uitwerking en bijbehorende toestandactieruimte

Tentamen van augustus 2009.

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

28 januari 2010 - http://www.liacs.nl/home/graaf/ALGO/