Stratégies de Résolution de problèmes

Responsable(s) : Alexandre SAIDI
Cours ⋅ 8 hTP ⋅ 28 hAutonomie ⋅ 12 h

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 dans 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.

Programme

  • Analyse et calcul de complexité des algorithmes récursivité (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 des complexités.
  • Exemples de calcul de complexité : les tris performants compléments.
  • 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).

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.

Contrôle des connaissances

Note des BEs (mini-projets) et test écrit (pondération 50 % - 50 %)