Objectifs de la formation
Approfondir les connaissances des élèves en analyse, algorithmes, méthodes de résolution, performantes et programmation. Parmi les objectifs de cours, il est important de donner aux élèves les connaissances et les méthodes et outils pratiques nécessaires à la mise en œuvre de l'activité de modélisation de solutions et/ou de conception d’algorithmes et de leur programmation. L'étude d'exemples de problèmes réputés complexes et les solutions proposées en informatique compléteront ce cours.
Mots-clés
Algorithme, Analyse d'algorithme, Complexité, Graphe, Résolution, Stratégie de résolution
Programme
- Analyse et calcul de complexité des algorithmes récursivité (cf. CAML).
- Introduction courte aux TDAs et les types de données remarquables stratégies de résolution algorithmique.
- Stratégie Diviser et Régner, Programmation Dynamique.
- Approche Greedy (approche Gloutonne / gradient).
- Algorithmes à essais successifs, Back Tracking (AES et BT).
- Branch and Bound (B & B).
- Résolution de l’équation caractéristique pour le calcul de complexité.
- Exemples de calcul de complexité.
- Méthodes de preuve (optionnel).
- Introduction à la théorie NP (optionnel).
- Algorithmes sur la théorie des nombres avec calcul de complexité (optionnel) optimisation (au sens recherche opération).
- Graphe comme outils de modélisation, Algorithmes de graphes, Théorie des graphes.
Compétences visées
- La résolution des problèmes non triviaux en Informatique nécessite une démarche Mathématique rigoureuse. Une fois le problème posé, les phases de recherche d'un modèle, l'étude algorithmique de la solution et le calcul de sa complexité sont les éléments importants de cette démarche. La phase de preuve (et de justesse de la solution proposée) qui complète cette démarche n'est pas détaillé dans ce cours même si des références en seront données. Prouver la justesse de ce qui est écrit est néanmoins abordé.
- Dans un souci de rapport théorique / pratique équilibré, l'objectif de ce cours est de donner aux élèves les connaissances et les méthodes et outils pratiques nécessaires à la mise en œuvre de l'activité de conception d’algorithmes et de leur programmation. L'étude d'exemples de problèmes réputés complexes et les solutions proposées en Informatique compléteront ce cours.
- Aborder la définition d'un algorithme à partir de son énoncé. Dès le début, tenir compte de la faisabilité (calculabilité) et de la complexité des algorithmes.
- Étudier quelques classes d'algorithme et des stratégies de résolution. Étude des structures de données importantes : graphes et arbre. Réalisation de TDs et des mini-projets avec des stratégies diverses.
Évaluation
Note des BEs (mini-projets) et test écrit (pondération 50 % - 50 %)