Algoritmen en Complexiteit

Algorithms and Complexity

Studiewijzer 2015/2016

Globale inhoud

Computers worden steeds sneller en krachtiger. Daar staat tegenover dat we steeds grotere en ingewikkelder problemen met computers willen aanpakken. Deze twee ontwikkelingen houden elkaar minstens in evenwicht, en de al dan niet objectieve ergernis over de traagheid van computers blijft onder ons. Niet alleen door betere, snellere en krachtigere hardware, maar vooral door beter doordachte meer op het probleem toegesneden software kunnen imposante besparingen op rekentijd en geheugengebruik worden bereikt. Vaak kunnen simpele observaties het verschil maken tussen dagen rekentijd en minuten. In dit college zullen we aandacht besteden aan een aantal van deze programmeermethoden die veelvuldig toepassing hebben gekregen. Voorbeelden hiervan zijn: greedy algoritmen, dynamisch programmeren, branch & bound en backtracking met geheugenfuncties. Sommige problemen zijn bewijsbaar zo moeilijk dat er geen snelle algoritmen voor bestaan. In dat geval is het toegestaan genoegen te nemen met oplossingen die een slechts een benadering geven van de juiste of de optimale oplossing, of met programma's die alleen gemiddeld snel zijn. In het tweede gedeelte van het college zullen we aandacht besteden aan deze bewijzen, en aan verschillende soorten van benaderingsalgoritmen.

Studiemateriaal

Syllabus

• 'Algoritmen & Complexiteit', Leen Torenvliet

Leerdoelen

A Kennis

Student heeft functionele kennis van de volgende begrippen:
complexiteitsmaten, complexiteitsklassen, optimalisatiealgoritmen, dynamisch programmeren, greedy algoritmen, reducties, complexe problemen (eind van het college).

B Toepassing

De student kan:

1. Bepalen van de tijdscomplexiteit van een gegeven algoritme. (+- week 2)
2. Ontwerpen van een algoritme met een van tevoren bepaalde bovengrens voor een gegeven probleem. (+- week 4)
3. Ontwerpen van een algoritme in een van de drie behandelde optimaliseringsstrategieën. (+- week 4)
4. Analyseren van een netwerkprobleem en vertalen van een gegeven probleem in een netwerk probleem. (+- week 5)
5. Toepassen van Discrete Fourier Transformatie op praktijkvoorbeelden. (+- week 5)
6. Vertalen van een probleem in een ander probleem door middel van tijdbegrensde reductie. (+- week 7)

C Analyse/synthese

De student kan algoritmische eigenschappen van een probleem analyseren
(bijvoorbeeld: heeft exhaustive search over een groot domein nodig, of is door constante ruimte begrensd) op grond waarvan voorspellingen kunnen worden gedaan over de (on)mogelijkheid tot het ontwerpen van efficiënte algoritmen.

Onderwijsvormen

• Hoorcollege
• Zelfstandig werken aan bijv. project/scriptie
• Werkcollege

Hoorcollege, huiswerk en programmeeropdrachten. Er zijn 6 series huiswerk en 6 toetsen. Bij de toetsen moet je wel aanwezig zijn (elke eerste les van de week een kwartier) anders kun je ze niet maken. Verder is er geen aanwezigheidsplicht maar is het eigen verantwoordelijkheid.

Verdeling leeractiviteiten

Aanwezigheid

Aanwezigheidseisen opleiding (OER-B):

• Voor practica en werkgroepbijeenkomsten met opdrachten geldt een aanwezigheidsplicht. Wanneer studenten niet voldoen aan deze aanwezigheidsplicht kan dit als gevolg hebben dat het onderdeel niet met een voldoende kan worden afgerond.
  

Aanvullende eisen voor dit vak:

Toetsing

Bij een onvoldoende score voor de wekelijkse toetsen is er de mogelijkheid tot herkansing na het college in de vorm van een tentamen.

Opdrachten

Groepsopdrachten

• programmeeropdrachten (huiswerk)

Onderstaande opdrachten komen aan bod in deze cursus:

•    Naam opdracht 1 : beschrijving 2
•    Naam opdracht 2 : beschrijving 1
•    ....

Fraude en plagiaat

Dit vak hanteert de algemene ‘Fraude- en plagiaatregeling’ van de UvA. Onder plagiaat of fraude wordt verstaan het overschrijven van het werk van een medestudent dan wel het kopiëren van wetenschappelijke bronnen (uit bijvoorbeeld boeken en tijdschriften en van het Internet) zonder daarbij de bron te vermelden. Uiteraard is plagiaat verboden. Hier wordt nauwkeurig op gecontroleerd en streng tegen opgetreden. Bij verdenking van plagiaat wordt de examencommissie van de opleiding ingeschakeld. Wanneer de examencommissie overtuigd is dat er plagiaat gepleegd is dan kan dit maximaal leiden tot een uitsluiting van al het onderwijs van de opleiding voor een heel kalenderjaar. Zie voor meer informatie over het fraude- en plagiaatreglement van de Universiteit van Amsterdam.www.uva.nl/plagiaat

Weekplanning

Rooster

Aanvullende informatie

Aanbevolen voorkennis: Enige programmeerervaring, met name in imperatieve talen is een must. Verder is kennis van grafen en grafeneigenschappen een voordeel. Basiskennis van wiskunde (bewijzen) is ook nuttig bij dit college.

Contactinformatie

Coördinator

• dr. Leen Torenvliet