Master Informatique 2e année


UE : Algorithmique Appliquée - 4TIN915
2023-2024

Modalités

Enseignants

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.

Ouvrages de références

Plan du cours

(tout ne sera pas traité)


    Avant-propos

  1. Introduction

  2. Algorithmes exacts

  3. Algorithmes d'approximation


Sujets des tests


Projet 2023

Ce projet a comme contexte le placement de stations de recharge rapide pour véhicule électrique sur autoroutes ... [lire la suite].

Projet 2022

Ce projet a comme contexte la sécurisation de villages contre les incendies ... [lire la suite].

Projet 2021

Ce projet a comme contexte le placement idéal de centres de vaccinations sur une ville ou un territoire ... [lire la suite].

Projet 2018, 2019 et 2020

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 pour l'année 2018 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 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 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