Crédits ECTS
2.5
Responsable:
JUGANARU-MATHIEU Mihaela
Description générale :
Dans son activité tout
ingénieur sera confronté à la conception et à la mise en oeuvre de méthodes de
résolution de problèmes de type Gestion et Affectation de Ressources,
Planification, Organisation, Ordonnancement, ... bref de nombreux problèmes de
nature discrètes, c'est à dire modélisables par des structures finies, que l'on
rencontre dans des domaines aussi variés que la Santé, l'Environnement, la
Production, ... et bien sûr l'Informatique.En général ces problèmes
peuvent être résolus par plusieurs méthodes dont il faudra savoir évaluer les
coûts. De plus les algorithmes cherchés doivent idéalement être le plus
économes possibles en moyens, en temps .. C'est dans cette optique que dans ce
cours nous proposons quelques éclairages et pistes possibles permettant
d'aborder er de résoudre concrètement ce type de problèmes tout en sachant en
mesurer les efficacités algorithmiques et les limites.Il s'agit donc d'une part
de faire un tour d'horizon raisonné de nombreuses stratégies classiques
possibles de résolution de problèmes, Paradigmes Algorithmiques. Et d'autre
part de présenter des résultats essentiels concernant une classification des
problèmes par rapport à la "difficulté" (complexité) que l'on a à les
résoudre par des algorithmes, autrement dit de s'initier à le Théorie de la
Complexité. Enfin, à défaut de pouvoir résoudre exactement et de façon efficace
un problème, nous examinerons quelques méthodes de calcul de solutions
approchées et les questions que pose cette approche.
Cohérence entre les unités pédagogiques du groupe pédagogique:
Ce cours comprend deux UP,
l'une portant spécifiquement sur les différentes stratégies possibles
envisageables de résolution algorithmique d'un problème, que ce soit exactement
ou approximativement, et l'autre se consacrant à présenter de façon rigoureuse
les résultats fondamentaux concernant la classification des problèmes (Classes
P, NP, Problèmes NP - Complets, ...):
·
Paradigmes de
Résolution (24h)
·
Théorie de la
Complexité (15h)
Parcours et cohérence avec les autres groupes pédagogiques:
Ce GP peut être vu comme
un prolongement UP "Formalisation pour la programmation" (partie Algorithmes) du TC Informatique et de l'UP
"Recherche Opérationnelle" du TC Mathématique.
Il est bien sûr fortement relié à la Majeure "Informatique" puisqu'il a l'objectif de donner une assise
algorithmique et méthodologique rigoureuse à toute démarche informatique visant
à la résolution effective de problèmes concrets.
Les techniques de
résolution présentées dans la Toolbox Calcul haute performance, en
particulier le programmation parallèle, peuvent être vues comme d'autres
paradigmes de résolution de problèmes et constituent donc un prolongement
naturel et utile au GP.
Il est complémentaire au Défi 'Intelligence Artificielle" qui aborde et présente d'autres
approches concernant la résolution des problèmes, UP "Problem
Solving", et ouvre la problématique vers d'autres domaines plus actuels de
l'Informatique.
Cette TB a un prolongement
naturel et complémentaire en la TB "Recherche Opérationnelle et aide à la
Décision" qui n'aborde pas directement les aspects complexités
algorithmiques mais qui présente de nombreuses autres approches conceptuelles
et méthodologiques de problèmes discrets (modélisation, optimisation,
simulation, analyse multicritère, ...).
Mots-clés:
Conception et Analyse d'Algorithmes
Résolution de Problèmes
Théorie de la Complexité
Méthodes Approximatives
Algorithmes Bio Inspirés