Master Informatique 2e année


UE : Algorithmique Appliquée

2017-2018

Modalités

Enseignants

Ouvrages de références

Notes de cours

Titrées "Analyse d'Algorithme", il n'est pas conseillé d'imprimer ces notes de cours. Le chapitre d'introduction (résumé disponible ici) n'est pas le même et elles sont régulièrement mises à jour.

Plan du cours

(tout ne sera pas traité)

  1. Introduction

  2. Algorithmes exacts
    1. Temps polynomial vs. exponentiel
    2. Problèmes jouets
    3. Algorithmes exhaustifs (brute force)
    4. Complexité paramétrique: définition
    5. Arbre borné de recherche
    6. Réduction à un noyau : "kernalisation"
    7. Théorie des mineurs de graphes
    8. Réduction aux graphes de treewidth bornée
    9. Remarques finales

  3. Algorithmes d'approximation
    1. Introduction
    2. Problèmes bien caractérisés
    3. Couverture par sommets de taille minimum
    4. Couverture par ensembles

Projet de programmation 2017

Voir le Moodle.

Projet de programmation 2016

Il s'agit de déterminer le score maximum réalisable avec une poignée de n cartes d'un jeu de UNO. De précieux détails sont disponibles ici et . Vous pourrez éventuelement utiliser le générateur de graphes gengraph.c pour vos jeux d'essais en testant par exemples les graphes uno et unok.

Articles en relations avec le projet:
(user: gavoille et password: bib0)


gavoille@labri.fr Mail