Algoritmiek 2007/2008

Het eerstejaarsvak Algoritmiek wordt in het voorjaar van 2008 verzorgd door Jeannette de Graaf. Het vak is verplicht voor studenten Informatica die de monodisciplinaire variant doen, voor studenten Informatica die een minor bedrijfskunde of psychologie of taalwetenschappen doen 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 Frank Takes en Jeroen Laros.

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 8 februari 2008; het eerste werkcollege is op donderdag 14 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).

In de jaren 2003 tot en met 2006 werd het vak nog gegeven door Erik de Vink. Zie alhier voor de betreffende college-informatie.

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 2007-2008 wordt men verwezen naar de algemene webpagina.

Materiaal

In het studiejaar 2007/2008 zal, evenals in 2006/2007, 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.

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. Er is een uitwerking beschikbaar van de opgaven over binaire (zoek)bomen. Zie hiervoor de betreffende webpagina van Jeroen Laros. Tevens is er alhier een uitwerking van de opgaven van werkcollege 5 (exhaustive search en backtracking) te vinden.

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 zijn alle drie hieronder te vinden. De uiterste inleverdatum van opdracht 1 is 28 maart. Let op: in de vorige versie waren bij opgave 2 en 3 (bij toestand-actie-ruimte) een aantal getallen verwisseld. De goede versie staat sinds 7 maart hieronder. Ook in het eerder verspreide DEEL I stond de opgave overigens correct. 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.

Tentamen

De twee tentamens van 2007 zijn hieronder te vinden, alsmede het juni-tentamen van 2008.


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

26 augustus 2008 - http://www.liacs.nl/home/graaf/ALGO/algo2008.html