Algoritmiek 2008/2009

Het eerstejaarsvak Algoritmiek wordt in het voorjaar van 2009 verzorgd door Jeannette de Graaf. Het vak is verplicht voor alle studenten Informatica en voor studenten die een dubbele propedeuse Wiskunde/Informatica doen. Het vak levert 7 EC-punten op.

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 6 februari 2009; het eerste werkcollege is op donderdag 12 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), heapsort en -indien de tijd dat toelaat- depth first search en breadth first search.

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

Materiaal

In het studiejaar 2007/2008 zal, evenals in voorgaande jaren, gebruik worden 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 zullen ook via deze website beschikbaar komen. In de week van elk college zullen de bijbehorende sheets hier geplaatst worden, eventueel aangepast (!!) tot de definitieve versie na het betreffende college.

Programma

Het programma voor het college 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 maandag van de betreffende week voor. Bovendien kan men hier de bij het werkcollege behandelde opgaven vinden.
Voorlopig staat hier nog het programma van het vorige studiejaar. Dit om alvast een idee te krijgen van de behandelde stof.

PROGRAMMA 2007/2008

Werkcollege

Datum (maandag)	Onderwerp	Sheets	Boek
4 februari	Introductie	sheets1	1.1, 1.2, 1.4 (tot graafrepresenties)	geen
11 februari	Grafen, bomen en toestand-actie-ruimte	sheets2	1.4 (grafen, bomen) + sheets	opgaven1, graafrepresentaties
18 februari	Kannen en complexiteit	sheets3	sheets + 2.1 t/m 2.4	opgaven2
25 februari	Brute force en exhaustive search	sheets4	hoofdstuk 3	opgaven3
3 maart	Backtracking	sheets5	12.1 + sheets	programmeeropdracht 1
10 maart	Backtracking en Verdeeel en heers	sheets6	12.1 + H4 t/m 4.2	opgaven5
17 maart	Goede Vrijdag: geen college	...	...	programmeeropdracht 1
24 maart	geen college	...	...	geen werkcollege
31 maart	Verdeel en heers	sheets7	4.3 t/m 4.5 (deels), 4.6 (deels), 5.1, 5.5 (deels)	programmeeropdracht 2
7 april	Restant decrease & conquer, dynamisch programmeren	sheets8	5.5 (rest), Inl. H8, sheets	opgaven8
14 april	Dynamisch programmeren	sheets9	8.1, 8.4, sheets	programmeeropdracht 2
21 april	Gretige algoritmen	sheets10	9 inleiding, 9.3, sheets	opgaven10
28 april	geen college	...	...	geen werkcollege
5 mei	Dijkstra en branch & bound	sheets11	12.2 tot TSP	opgaven11
12 mei	Branch & bound en heapsort	sheets12	12.2 TSP, 6.4	programmeeropdracht 3
19 mei	Oud tentamen	...	...	werkcollege op vrijdag: 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). Het eindcijfer voor het vak is het behaalde tentamencijfer, mits de programmeeropdrachten voldoende zijn beoordeeld. In tegenstelling tot bij Programmeermethoden telt het cijfer voor het programmeerwerk dus niet mee voor het eindcijfer. 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 van het afgelopen studiejaar zijn alle drie hieronder nog te vinden. Ook de opmerkingen daarover horen bij voorjaar 2008. T.z.t. komen hier de programmeeropdrachten voor voorjaar 2009 te staan.

De uiterste inleverdatum van opdracht 1 is 28 maart. De deadline voor opdracht 2 is op vrijdag 25 april. Tijdens het werkcollege op 3 april zal een begin met de opdracht worden gemaakt. De deadline voor de derde programmeeropdracht is op maandag 19 mei. Zie ook de webpagina van Jeroen Laros voor meer informatie en testcases bij de programmeeropdrachten.

Programmeeropdracht 1 (brute force).

Programmeeropdracht 2 (backtracking).

Programmeeropdracht 3 (dynamisch programmeren).

Tentamen

Het tentamen zal plaatsvinden op dinsdag 2 juni 2009, 10.00-13.00 uur.

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

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

Tentamen van juni 2007. Een zeer uitgebreide uitwerking, bedoeld om een en ander nog eens uit te leggen, is eveneens beschikbaar. Er wordt overigens niet verwacht dat je zelf zo veel opschrijft bij het tentamen, maar je moet je antwoorden wel duidelijk toelichten (maar dan dus wat korter).

Tentamen van augustus 2007.

Tentamen van juni 2008, met uitgebreide uitwerking en bijbehorende toestandactieruimte

Tentamen van augustus 2008.

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

13 januari 2009 - http://www.liacs.nl/home/graaf/ALGO/