Eerste semester
Tweede semester
Beide semesters
Dit jaar
Volgend jaar
Wisselende jaren
Extern
Voorwaarden
Onderwijstaal
Duur
NiveauComplexiteit van algoritmen (B-KUL-G0Q63B)
Demoen Bart (coördinator) |
Demoen Bart |
Sneyers Jon
Doelstellingen
De theorielessen hebben als doel het kennen en begrijpen van het belang van een niet triviaal aantal complexiteitsklassen, hun onderlinge samenhang en relatie tot andere complexiteitsklassen, de robuustheid van de definities enhet computationeel model en de relatie van wat op dit ogenblik bekend is i.v.m. de vraag P ?= NP. Daarmee moet de student gewapend zijn om bij zijn/haar onderzoek in teogepaste domeinen van de informatica, die kennis en dat begrip te gebruiken om de bestudeerde problematiek complexiteitsgewijs te plaatsen. De oefenzittingen en projecten hebben tot specifiek doel vaardigheid en begrip te verwerven i.v.m. het afleiden van eigenschappen van (meestal nieuwe) algoritmen.
Begintermen
Deze cursus steunt op kennis van programmeren, logica, een inleiding tot automaten en berekenbaarheid. Lacunes i.v.m. kansrekenen en tellen zullen waar nodig ad-hoc aangevuld worden.
Aard van het studiemateriaal
Cursustekst
Toledo
Handboek
Plaats in het onderwijsaanbod
-
Master in de wiskunde (uitdovend vanaf 2012-2013)
120 sp.
- Master in de informatica (uitdovend, enkel 2e fase) (Onderzoeksprofiel) 120 sp.
- Master in de informatica (uitdovend, enkel 2e fase) (Specialisatie computationele informatica) 120 sp.
- Master in de informatica (uitdovend, enkel 2e fase) (Specialisatie databases) 120 sp.
- Master in de ingenieurswetenschappen: computerwetenschappen (Hoofdspecialisatie Artificiële intelligentie) 120 sp.
- Master in de ingenieurswetenschappen: computerwetenschappen (Hoofdspecialisatie Computationele informatica) 120 sp.
Onderwijsleeractiviteiten
4.0 sp. Complexiteit van algoritmen (B-KUL-G0Q63a)
Inhoud
Hieronder verwijst een getal naar het overeenkomstige hoofdstuk uit het boek van Arora en Barak.
1. Het computationeel model en zijn belang (1)
2. De basisklassen: P, NP, co-NP (2)
3. Diagonalisatie en zijn grenzen (3)
4. Ruimtecomplexiteit: PSPACE, NSPACE, L, NL (4)
5. De polynomiale hierarchie en alternerende logische formules (5)
6. Een niet-uniform computationeel model: Boolse circuits (6) P/poly, NC
7. Algoritmen met een randomgenerator: BPP, RP, co-RP, ZPP (7)
8. Inleiding tot benaderende oplossingen (8)
9. Inleiding tot berekeningen met reele getallen en de relatie met de Turing machine (uit het boek van J.F. Traub en Werschulz)
10. Ondergrenzen voor circuits (14)
11. De complexiteit van het tellen van oplossingen:
Studiemateriaal
Computational Complexity: A Modern Approach, auteurs Sanjeev Arora and Boaz Barak; selectie van hoofdstukken.
Complexity and Information, J.F. Traub, A.G. Werschulz selectie
1.0 sp. Complexiteit van algoritmen: oefeningen (B-KUL-G0Q64a)
Inhoud
1. Een aantal onderlinge polynome reducties van NP-complete problemen.
2. Bestuderen van een aantal nieuwe algoritmen en hun eigenschappen; bijvoorbeeld diverse aritmetische algoritmen (ggd, vermenigvuldigen,...), grafenalgoritmen (hamiltoniaanse kring, ustcon, onafhankelijke knopenverzameling, grafekleuring ...) en andere (union-find...)
3. Voorstellen van het project.
1.0 sp. Complexiteit van algoritmen: project (B-KUL-G0Q65a)
Inhoud
1. Individueel of in kleine groepjes uitwerken van problemen, bijvoorbeeld oefeningen uit het boek van Arora en Barak of een geselecteerd onderwerp uit gerelateerd werk; daarover wordt gerapporteerd tijdens een oefenzitting aan de medestudenten.
Evaluatieactiviteiten
Evaluatie : Complexiteit van algoritmen (B-KUL-G2Q63b)
Toelichting
- permanente evaluatie van activiteit tijdens lessen en oefenzittingen: 3/20 van de punten
- evaluatie van de voorstelling van het project: 3/20 van de punten
- mondeling examen met schriftelijke voorbereiding tijdens de examenperiode: 14/20 van de punten.
De voorstelling van het project gebeurt tijdens de oefenzitting, maar kan in uitzonderlijke gevallen ook gebeuren tijdens de examenperiode. Bij een onvoldoende op het project in de eerste examenzittijd krijgt de student de kans het project verder uit te werken, of een nieuw project te maken voor de tweede zittijd. De deadline voor het indienen van de schriftelijke neerslag van het project is één week voor het begin van de examenperiode.
