Deze cursusinformatie geeft aan hoe het onderwijs zal verlopen bij pandemieniveau code geel en groen.
Als er tijdens het academiejaar aangepast wordt naar code oranje of rood, zijn er wijzigingen mogelijk o.a. in de gebruikte werk - en evaluatievormen.

Algoritmen en complexiteit

Studiegidsnr:1001WETALC
Vakgebied:Informatica
Academiejaar:2020-2021
Semester:2e semester
Inschrijvingsvereisten:Min. 8/20 voor Discrete wiskunde, Talen en automaten en Gegevensabstractie en -structuren.
Contacturen:60
Studiepunten:6
Studiebelasting:168
Contractrestrictie(s):Geen contractrestrictie
Instructietaal:Nederlands
Examen:2e semester
Lesgever(s)Floris Geerts

Deze cursusinformatie is bedoeld om de student te ondersteunen bij het verwerken van de leerstof

3. Inhoud *

In deze cursus starten we met een herhaling van Turing machines aangezien dit berekeningsmodel aan de grondslag ligt van complexiteitstheorie. Naaste de klassieke Turing machines met een enkele tape, beschouwen we ook Turing machines met meerder tapes en niet-deterministische Turing machines.

Op basis hiervan worden vervolgens de begrippen tijds- en ruimtecomplexiteit bestudeerd. Wat tijdscomplexiteit betreft wordt veel aandacht besteed aan problemen die in polynomiale tijd zitten, en problemen die intrinsiek inefficient zijn (NP-complete problemen). De rol van reducties is hier heel belangrijk en tal van voorbeelden van reducties komen aan bod. De Stelling van Cook-Levin, waarin het standaardvoorbeeld van een NP-compleet probleem wordt behandeld, wordt bewezen de cursus.

Met betrekking to plaatscomplexiteit beschouwen PSPACE, L en NL en bijhorended complete problemen. Er wordt inzicht verschaft over de tradeoff tussen tijds- en plaatscomplexiteit. De stelling van Savitch wordt beschouwd om zo inzicht te geven in de kracht van niet-determinisme op ruimtecomplexiteit. Ook wordt de Stelling van Immerman-Szelepcsenyi bekeken. PTIME-complete problemen vervolledigen dit deel.

Tenslotte worden verbanden tussen de geziene complexiteitsklassen behandeld.