Algorithms and Complexity
6 EC
Semester 1, periode 2
5062ALCO6Y
| Eigenaar | Bachelor Informatica |
| Coördinator | dr. Leen Torenvliet |
| Onderdeel van | Minor Logic and Computation, jaar 1Bachelor Informatica, jaar 2Bachelor Wiskunde, jaar 2 |
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.
'Algoritmen & Complexiteit', Leen Torenvliet. De syllabus is (gratis en) downloadbaar. U vindt hem ook terug op de canvaspagina, of ook: https://staff.fnwi.uva.nl/l.torenvliet/PDFpapers/342.pdf
Het practicummateriaal is of komt wekelijks beschikbaar op canvas
Er is een volledige set slides. Aangezien deze nogal veranderen komen die na elk college beschikbaar. De opnamen van het college van vorig jaar zijn beschikbaar. Daarnaast maken we nieuwe opnamen van het college zoals het nu gegeven wordt.
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.
Activiteit | Aantal uur |
Hoorcollege | 28 |
Werkcollege | 14 |
Zelfstudie | 126 |
De student wordt geoefend in samenwerken in kleine groepen, het opstellen van algoritmen en wiskundige bewijzen, en het begrijpelijk formuleren van gedachten en modellen.
Aanwezigheidseisen opleiding (OER-B):
Aanvullende eisen voor dit vak:
Er is geen aanwezigheidsplicht. De wekelijkse toetsen worden online uitgevoerd.
| Onderdeel en weging | Details |
|
Eindcijfer | |
|
Eindcijfer |
Er zijn vijf groepsopdrachten, vijf toetsen en zes programmeeropgaven. Groepsopdrachten worden gemaakt in groepen van min 3 en max 5 studenten. Toetsen worden individueel online gemaakt. Programmeeropgaven worden wekelijks individueel gemaakt en (grotendeels) geautomatiseerd nagekeken.
Er is een herkansing in de vorm van een tentamen (2 uur) uitsluitend voor de toetsen en uitsluitend bij een onvoldoende resultaat, aangezien deze op een vast tijdstip worden georganiseerd. Het eindcijfer wordt bepaald door 1. Groepsopdrachten 60%, 2. Toetsen 20% en 3. Programmeeropdrachten 20%. Er zijn voor de onderdelen geen minimumvereisten. Het (60,20,20) gemiddelde moet 5.5 of hoger zijn.
| groepsopdr 1 | groepsopdr 2 | groepsopdr 3 | groepsopdr 4 | groepsopdr 5 | |
| toets 1 | toets 2 | toets 3 | toets 4 | toets 5 | |
| progopg 1 | progopg 2 | progopg 3 | progopg 4 | progopg 5 | progopg 6 |
| Herkansing toetsen | |||||
Op de theorieopgaven wordt feedback via de digitale leeromgeving geleverd (wekelijks door de docent) verder kan per groep of individueel via email een afspraak met de docent worden gemaakt voor meer uitleg.
theorieopgaven elke week over de behandelde collegestof (huiswerk)
elke week twee individuele vragen, online te beantwoorden.
elke week over een ander onderwerp. Individueel te maken
Onderstaande opdrachten komen aan bod in deze cursus:
Over het algemeen geldt dat elke uitwerking die je inlevert ter verkrijging van een beoordeling voor een vak je eigen werk moet zijn, tenzij samenwerken expliciet door de docent is toegestaan. Het inzien of kopiëren van andermans werk (zelfs als je dat hebt gevonden bij de printer, in een openstaande directory of op een onbeheerde computer) of materiaal overnemen uit een boek, tijdschrift, website, code repository of een andere bron - ook al is het gedeeltelijk - en inleveren alsof het je eigen werk is, is plagiaat.
We juichen toe dat je het cursusmateriaal en de opdrachten met medestudenten bespreekt om het beter te begrijpen. Je mag bronnen op het web raadplegen om meer te weten te komen over het onderwerp en om technische problemen op te lossen, maar niet voor regelrechte antwoorden op opgaven. Als in een uitwerking gebruik is gemaakt van externe bronnen zonder dat een bronvermelding is vermeld (bijvoorbeeld in de rapportage of in commentaar in de code), dan kan dat worden beschouwd als plagiaat.
Deze regels zijn er om alle studenten een eerlijke en optimale leeromgeving aan te kunnen bieden. De verleiding kan groot zijn om te plagiëren als de deadline voor een opdracht nadert, maar doe het niet.
Elke vorm van plagiaat wordt bestraft. Als een student ernstige fraude heeft gepleegd, kan dat leiden tot het uitschrijven uit de Universiteit.
Zie voor meer informatie over het fraude- en plagiaatreglement van de Universiteit van Amsterdam: www.student.uva.nl
Week 1: Complexiteitsafschattingen worst case, average case, amoritzed case.
Week 2: Technieken: Greedy algorithms: geld wisselen, continue knapsack, MST:Prim, Kruskal, Dijkstras algoritme
Week 3: Divide and Conquer: matrixvermenigvuldiging, dynamic programming:discrete knapsack, Floyd-Fulkerson, matrixvermenigvuldiging.
Week 4: Netwerk algoritmen:Ford/Fulkerson, Gelaagde netwerken, toepassingen; Discrete Fourier tranformatie
Week 5: Complexiteitstheorie, machinemodellen, P, EXP, reducties
Week 6: NP-volledigheid. Voorbeelden van NP-volledige problemen
Week 7: Benaderingen.
Er zijn *elke week* huiswerkopgaven die in groepjes gemaakt worden. De samenstelling van de groepjes wordt door de studenten zelf bepaald. Wie niet (voldoende) meedoet aan het huiswerk, te bepalen door een door de groep aan te wijzen contactpersoon, wordt uitgesloten van verdere deelname aan het huiswerk. De huiswerkopgaven bepalen voor 60% het eindcijfer.
Er is *elke week* in één van de colleges, na de pauze een schriftelijke toets van een kwartier. Bij onvoldoende score kan het materiaal in één keer in een herkansing na afloop van de collegereeks worden ingehaald (zie datanose). De toetsen bepalen voor 20% het eindcijfer.
Er is *elke week* een programmeeropgave. De programmeeropgaven zijn individueel en worden grotendeels geautomatiseerd nagekeken. De programmeeropgaven bepalen voor 20% het eindcijfer.
Het rooster van dit vak is in te zien op DataNose.
Aanbevolen voorkennis: Enige programmeerervaring, met name in imperatieve talen is een must. In het bijzonder is kennis van Python 3.0 nodig voor de programeeropgaven. Verder is kennis van grafen en grafeneigenschappen een voordeel. Basiskennis van wiskunde (bewijzen) is ook nuttig bij dit college.