This shows you the differences between two versions of the page.
| Both sides previous revision Previous revision | Next revision Both sides next revision | ||
|
teaching:mfe:ia [2011/03/18 11:55] bersini [> Développer un programme informatique permettant une analyse statistique en vue de l'évaluation d'un module psychothérapeutique.] |
teaching:mfe:ia [2011/03/22 14:48] stuetzle |
||
|---|---|---|---|
| Line 169: | Line 169: | ||
| Among the possible generalisations of the problem there is the Vertex Weighted and Edge Weighted Maximum Clique which asks to find the clique of maximum weight. Being generalisations they are also NP-hard. The goal of the project is to devise heuristic algorithms or adapt existing algorithms of the Maximum Clique for weighted version. | Among the possible generalisations of the problem there is the Vertex Weighted and Edge Weighted Maximum Clique which asks to find the clique of maximum weight. Being generalisations they are also NP-hard. The goal of the project is to devise heuristic algorithms or adapt existing algorithms of the Maximum Clique for weighted version. | ||
| + | |||
| + | Required skills: good knowledge of C or C++ programming. | ||
| + | |||
| + | |||
| + | * Contacts : | ||
| + | * [[http://iridia.ulb.ac.be/~stuetzle|Thomas Stuetzle (IRIDIA)]] | ||
| + | * [[http://iridia.ulb.ac.be/~fmascia|Franco Mascia (IRIDIA)]] | ||
| + | |||
| + | |||
| + | |||
| + | ===== Stochastic Local Search heuristics for solving NP-complete puzzles. ====== | ||
| + | |||
| + | This project is about single player games (puzzles) and the design of algorithms for tackling hard combinatorial optimisation problems. | ||
| + | Example puzzles are: <a href="http://en.wikipedia.org/wiki/Light_Up">Light Up</a>, <a href="http://en.wikipedia.org/wiki/Mastermind_(board_game)">Mastermind</a>, <a href="http://en.wikipedia.org/wiki/Minesweeper_(video_game)">Minesweeper</a>, etc. | ||
| + | |||
| + | The student will learn how to design and implement a Stochastic Local Search algorithm to solve NP-complete puzzles. The student will also learn how to analyse the performaces of the algorithm and perform statistically sound comparisons with the other algorithms available in literature. | ||
| Required skills: good knowledge of C or C++ programming. | Required skills: good knowledge of C or C++ programming. | ||