SluitenHelpPrint
Switch to English
Cursus: INFOMSEAHP
INFOMSEAHP
Seminar exact algorithms for hard problems
Cursus informatieRooster
CursuscodeINFOMSEAHP
Studiepunten (ECTS)7,5
Categorie / NiveauM (Master)
CursustypeSeminarium
VoertaalEngels
Aangeboden doorFaculteit Betawetenschappen; Onderwijsinstituut Informatica;
Contactpersoondr. H.L. Bodlaender
Telefoon+31 30 2534409
E-mailH.L.Bodlaender@uu.nl
Docenten
Docent
dr. H.L. Bodlaender
Feedback en bereikbaarheid
Overige cursussen docent
Blok
Onbekend
Aanvangsblok
1
TimeslotD: WO-middag, WO-namiddag, Vrijdag
Onderwijsvorm
Voltijd
Aanmeldingsprocedureadministratie onderwijsinstituut
Inschrijven via OSIRISJa
Inschrijven voor bijvakkersJa
VoorinschrijvingNee
WachtlijstNee
Plaatsingsprocedureadministratie onderwijsinstituut
Cursusdoelen
-
Inhoud

It is generally believed that NP-hard problems do not have polynomial time algorithms that solve them. Suppose we want to know the exact solution to an NP-hard problem: we then can look for algorithms that use exponential time, but that still are as fast as possible. In this seminar, we investigate a number of algorithmic techniques for exactly solving (NP-)hard problems, and for analysing algorithms that use exponential time. Amongst others, we look to branch-and-reduce, inclusion-exclusion, algorithms on planar graphs. We also investigate topics from fixed parameter tractability: suppose that we want to solve a problem exactly, but we know that there is a solution of small size. Does that help? And if so, how much? In the course, we look at a number of modern (and a few old) algorithms, but will also try to build and analyse fast exponential algorithms for a few specifically selected problems.

 

http://www.cs.uu.nl/education/vak.php?vak=INFOMSEAHP&jaar=2008

 

Ingangseisen
Je moet een geldige toelatingsbeschikking hebben
Verplicht materiaal
-
Werkvormen (aanwezigheidsplicht)
Seminar (Verplicht)

Toetsen
Tentamen
Weging100
Minimum cijfer6

SluitenHelpPrint
Switch to English