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 2009/2010
| Datum (vrijdag) |
Onderwerp |
Sheets |
Boek | Werkcollege
6 februari |
Introductie |
sheets1 |
1.1, 1.2, 1.4 (t/m graafrepresentaties) |
geen |
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.
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.
Vragen en/of opmerkingen kunnen worden gestuurd
naar: graaf@liacs.nl.
4 februari 2010 - http://www.liacs.nl/home/graaf/ALGO/