Master Informatique 2e année


UE : Algorithmique Appliquée

2018-2019

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. Elles sont régulièrement mises à jour. Le chapitre d'introduction (résumé disponible ici) n'est pas le même.

Plan du cours

(tout ne sera pas traité)


  1. Introduction
  2. Algorithmes exacts
  3. Algorithmes d'approximation

Projet de programmation 2018

Ce projet a comme contexte la compétition mondiale de robotique RoboCup et plus particulièrement la ligue SSL. Dans cettes compétition, plusieurs robots à roues se déplacent rapidement et disputent un match de football robotique. Il est vrai que c'est plus que tentant en cette année de double étoile pour les Bleus et de la 3e pour l'équipe Rhoban du LaBRI dans la ligue Humanoid Kid-Size !

Dans le cadre de ce projet, l'objectif sera de traiter le problème de la défense, en particulier, comment placer les défenseurs pour éviter que les attaquants aient un angle de tir? Le problème sera abordé avec différents niveaux de simplifications et sera modélisé ... [lire la suite].

Projet de programmation 2017

L'inspiration de ce projet est la suivante: a) Dans le jeu Pac-Man, pour préparer les niveaux difficiles, on souhaite placer sur le plateau un ensemble de fantômes de sorte que toute position possible de Pac-Man soit à proximité d'un fantôme. b) Dans le jeu League of Legends, on souhaite placer les 5 héros pour que quelque soit l'emplacement où apparaît un monstre, on puisse y accéder rapidement.

Le problème peut se modéliser de la façon suivante. Étant donnés une carte et $k$ items que l'on peut placer sur la carte (fantômes, héros, wards ...) , comment disposer ces items de façon à couvrir au plus près tous les points de la carte ? Autrement dit, il s'agit de minimiser la distance maximale d'un point de la carte à un item. Plus simplement, si on le convertit en un problème de décision, étant donnés la carte, un nombre $k$ de héros/fantômes et une portée maximale $d$, existe-t-il un ensemble de $k$ points qui sont à distance au plus $d$ de tout sommet de la carte/du graphe. [Lire la suite sur 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