Algoritmiek 2006/2007

Het eerstejaarsvak Algoritmiek wordt in het voorjaar van 2007 verzorgd door Jeannette de Graaf. Assistentie bij de werkgroep en het practicum wordt verleend door drs. Jeroen Laros en Frank Takes. 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.

De colleges zijn op vrijdagen van 11.15 tot 13.00 uur in zaal 174. Dit is anders dan in de studiegids vermeld. De bijbehorende werkcolleges vinden plaats op donderdagen van 9.00 uur tot 10.45 uur, in zaal 312 of een van de computerzalen. Het eerste college is op vrijdag 9 februari 2007; het eerste werkcollege is op donderdag 15 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.

Voor eventuele aanvullende informatie over werkgroep (practicum) en programmeeropdrachten, zie ook de betreffende webpagina van Jeroen Laros.

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) en een beetje complexiteit (om de efficientie van algoritmen te beschrijven en te vergelijken).

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

Materiaal

In het studiejaar 2006/2007 zal gebruik worden gemaakt van het volgende boek: Anany Levitin, Introduction to The Design and Analysis of Algorithms, second edition (Addison-Wesley, 2007).

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 zal hieronder worden bijgehouden. Voor elke week staat daarin welke onderwerpen aan de orde zijn gekomen met de bijbehorende hoofdstukken uit het boek. In het schema staat de week aangegeven door middel van de maandag uit die betreffende week.

PROGRAMMA 2006/2007

Datum (maandag) Onderwerp Sheets Boek Werkcollege
5 februari Introductie sheets1 1.1, 1.2, 1.4 (t/m grafen) geen
12 februari Bomen, toestand-actie-ruimte sheets2 1.4 (bomen) + sheets opgaven1
19 februari Kannen en complexiteit sheets3 sheets + 2.1 t/m 2.4 opgaven2
26 februari Brute force en exhaustive search sheets4 3.1 t/m 3.4 opgaven3
5 maart Backtracking sheets5 12.1 + sheets programmeeropdracht 1
12 maart Backtracking en Verdeel & Heers sheets6 sheets + 4.1, 4.2 programmeeropdracht 1
19 maart Verdeel & Heers sheets7 4.3 t/m 4.6 (deels), 5.1, 5.5 (deels) opgaven6
26 maart Decrease & Conquer (rest), Dynamisch Programmeren sheets8 sheets + 8.1 opgaven7
2 april Geen college: Goede Vrijdag --- --- ---
9 april Dynamisch programmeren sheets9 sheets + 8.4 programmeeropdracht 2
16 april Gretige algoritmen sheets10 sheets + intro 9.1 + 9.3 opgaven9
23 april Branch and bound sheets11 12.2 opgaven10
30 april Geen college: meivakantie --- --- ---
7 mei Heapsort sheets12 6.4 programmeeropdracht 3
14 mei Geen college: Hemelvaart --- --- ---
21 mei Proeftentamen --- --- 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. Ook zal drie keer een werkcollege gewijd zijn aan de programmeeropdrachten. Van de opdrachten over binaire bomen (werkcollege 2) is een uitwerking beschikbaar. Er is inmiddels ook een uitwerking van de opgaven van werkcollege 6 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). 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 worden ingeleverd. Anders gaat er in principe per week te laat inleveren een punt af.

LET OP: de uiterste inleverdatum voor de derde programmeeropdracht is verplaatst naar 21 mei! Verder zijn hier wat tips en opmerkingen te vinden bij deze opdracht.

Tentamen

Om een idee te krijgen van het soort vragen dat op het tentamen kan worden gesteld, is er een proeftentamen beschikbaar. Dit is bij het college van vrijdag 25 mei besproken.

Het juni-tentamen is nagekeken en de cijfers kun je alhier aantreffen. Het juni-tentamen zelf is hieronder te vinden. Er is ook een (wel heel erg) uitgebreide uitwerking van beschikbaar. Deze is bedoeld om een en ander nog eens duidelijk uit te leggen. Er wordt niet verwacht dat je zelf zoveel opschrijft bij het tentamen. De resultaten van het hertentamen zijn inmiddels ook bekend. Het tentamen zelf is hieronder te vinden.


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

21 augustus 2007 - http://www.liacs.nl/home/graaf/ALGO/algo2007.html