Présentation

Partie optimisation (10h CM, 12h TD, 10h TP)  :

Ce cours présente des approches par programmation linéaire, séparation & évaluation, programmation dynamique et heuristiques pour la résolution de problèmes d’optimisation combinatoire. Une introduction à la complexité et à la résolution de problèmes de satisfiabilité booléenne est également présentée.

Le cours aborde les points suivants :

• complexité algorithmique et théorie de la complexité
• modélisation et heuristique de résolution de problème de satisfiabilité booléenne (SAT)
• programmation linéaire : méthode du simplexe, modélisation MILP de problèmes d’optimisation 
• méthodes par séparation et évaluation, application à la programmation linéaire, problème de voyageur de commerce
• programmation dynamique : principe et applications (plus court chemin, gestion de stock)
• Approches diviser pour régner (et calcul parallèle)
• méthodes heuristiques approchées : introduction aux meta heuristiques, heuristiques gloutonnes. Applications d’heuristiques gloutonnes (sac à dos, couverture, voyageur de commerce)
• méthodologie de comparaison d’algorithmes

La mise en pratique se fait avec le logiciel CPLEX :

• utilisation directe
• langage de programmation OPL et modélisation
• génération de cas et automatisation de séries de test

Partie Modélisation et programmation des systèmes intéractifs (4h CM, 2h TD, 4h TP) :

Ce cours permet d’ouvrir aux problématiques de la conception et du développement de systèmes interactifs complexes. Les notions de base de la modélisation de l’interaction seront présentées. Ce cours propose d’illustrer les notions vues en cours via la mise en œuvre d’une étude de cas en appliquant une méthode à base d’automates pour la description du dialogue d’une application interactive.

Le cours présente : 

1. Introduction aux modèles du processeur humain et aux architectures des systèmes interactifs
2. Modélisation et programmation des systèmes interactifs