Algorithmes et complexité

Chargé de TD et TP au semestre 1 (Master 1)

Objectifs

Le but de l’algorithmique peut être résumé par: trouver un « bon » algorithme pour un problème donné. Cela soulève de nombreuses questions:

  1. Existe-t-il un algorithme pour résoudre le problème? ( calculabilité, indécidabilité).
  2. Le problème est-il un « classique »? (modélisation, reformulation, connaissances).
  3. Comment concevoir un algorithme? (algorithmes corrects par construction, paradigmes)
  4. L’algorithme apporte-t-il bien la réponse au problème donné? ( orrection des algorithmes)
  5. Que dire des ressources utilisées par l’algorithme? (analyse d’algorithmes)
  6. L’algorithme est-il « raisonnablement » efficace? Pourrait-on faire mieux? Que dire des ressources minima nécessaires pour résoudre le problème? (complexité des problèmes)
  7. Peut-on espérer avoir un algorithme « rapide » exact? Le problème est-il « dur »? (NP-dureté)
  8. Que faire face à un problème dur?

L’objectif du cours est de préparer les étudiants à répondre à ces questions difficiles, de les entraîner au « computational thinking« . A l’issue de ce module, les étudiants doivent être donc capables:

  1. d’analyser un problème – modélisation, reformulation, complexité, réduction.
  2. de concevoir une solution algorithmique appropriée, exacte ou approchée, en particulier en utilisant à bon escient les structures et paradigmes classiques- programmation dynamique, algorithme glouton, recherche exhaustive, heuristique, …-
  3. d’analyser cette solution -correction, complexité, efficacité, … .

Contenu

  1. Rappels sur les notions de complexité et correction d’algorithmes.
  2. Paradigmes classiques de conception d’algorithmes (programmation dynamique, diviser et régner, algorithmes gloutons, backtracking, …).
  3. Complexité de problèmes, Classes P, NP et EXPTime, Réductions polynomiales, NP-dureté.
  4. Quelques méthodes « avancées » pour résoudre de manière exacte ou approchée des problèmes NP-durs (Branch-and-Bound, algorithmes probabilistes, heuristiques, méta-heuristiques, …)

Bibliographie

Il y a de nombreuses ressources en ligne sur le domaine. Il y a également de nombreux livres excellents sur l’algorithmique et la complexité, par exemple:

  1. Introduction à l’algorithmique, par Thomas H. Cormen, Charles Leiserson, Ronald Rivest, (Editions Dunod, disponible à la BU), livre référence en algorithmique
  2. Algorithms, par Robert Sedgewick et Kevin Wayne, qui se présente comme essential information that every serious programmer needs to know about algorithms and data structures avec un site associé à la quatrième édition
  3. Algorithm Design Manual, avec beaucoup d’applications concrètes, par Steven Skiena dont le site contient de nombreuses ressources en ligne
  4. Algorithm Design, par John Kleinberg et Eva Tardos (Editions Addison Wesley 2005) qui est aussi tourné vers les applications (voir le site associé )
  5. A guide to Algorithm Design, par Anne Benoit, Yves Robert et Frédéric Vivien, (Editions CRC Press) avec de nombreux exercices corrigés
  6. Sur l’aspect « algorithmic pattern », par Bruno R. Preiss, Data Structures and Algorithms with object-oriented design patterns in Java, disponible sur le Web.

Programmation Fonctionnelle

Chargé de TD et TP au semestre 6 (Licence 3).

Objectif

Ce module est une introduction à la programmation fonctionnelle.

L’objectif est ainsi d’appréhender comment concevoir des programmes suivant ce paradigme centré sur l’évaluation de fonctions, et de voir comment cette approche aide à écrire des programmes clairs, concis, corrects et élégants.

Contenu

La programmation fonctionnelle est un paradigme très riche, avec de nombreuses notions liées, notamment :

  • fonctions d’ordre supérieur (combinateurs) ;
  • systèmes de types (vérification et inférence des types) ;
  • structures de données purement fonctionnelles ;
  • filtrage de motifs ;
  • stratégies d’évaluation (en particulier stricte et paresseuse1) ;
  • λ-calcul ;
  • monades.

Le cours s’appuie sur le langage Haskellle langage purement fonctionnel à évaluation paresseuse.

Technologies du Web 1

Chargé de TD et TP au semestre 2 (Licence 1).

Objectifs

À l’issue de ce module les étudiants doivent

  • Être capables de concevoir des documents web dans le respect des standards.
    • Connaître les principaux standards du web : (X)HTML 5, CSS, Javascript, DOM
    • Maîtriser la notion de séparation contenu / forme / dynamicité
    • Savoir
      • décrire un document sous forme arborescente,
      • traduire ce modèle en un document (X)HTML 5,
      • réaliser la mise en forme en utilisant le langage CSS,
      • rendre le document dynamique et le manipuler via l’interface DOM et javascript.
    • Être conscient de l’importance du respect des normes.
    • Maîtriser le processus de rédaction et de validation des documents.
  • Savoir développer des programmes en javascript et connaître les bases de ce langage.
  • Connaître les bases de la programmation événementielle.
  • Être capables de rechercher des informations et les exploiter (spécifications de standards HTML, CSS, …, sites web d’information, etc.).

Compétences

  • Participer à la conception et à la réalisation d’applications logicielles :
    • connaître plusieurs styles/paradigmes de programmation et plusieurs langages,
    • comprendre les différentes natures des informations : données, traitements, connaissances, textes,
    • mettre en œuvre des méthodes d’analyse pour concevoir des applications et algorithmes à partir d’un cahier des charges partiellement donné.
  • Connaître les savoirs pratiques et les technologies actuelles attachés à la discipline.

Conception Orientée Objet

Chargé de TD et TP au semestre 5 (Licence 3).

Objectifs

Cette UE suit directement l’UE POO du S4. Les objectifs de l’UE COO sont :teaserbox_1516941

  • la compréhension et la maîtrise de la notion de polymorphisme.
  • la connaissance des principes essentiels de la conception objet et leur maîtrise pour favoriser une bonne construction de logiciels.
  • la conception de tests pour aider la maintenance sur le long terme et augmenter la confiance des développeurs.
  • la reconnaissance et l’application des principaux patrons de conception (design patterns).

Les design patterns sont introduits afin d’illustrer ces propos.

A Comparison of Decoding Strategies for the 0/1 Multi-objective Unit Commitment Problem

ucpIn the single objective Unit Commitment Problem (UCP) the problem is usually separated in two sub-problems : the commitment problem which aims to fix the on/off scheduling of each unit and the dispatching problem which goal is to schedule the production of each turned on unit. The dispatching problem is a continuous convex problem that can easily be solved exactly. For the first sub-problem genetic algorithms (GA) are often applied and usually handle binary vectors representing the solutions of the commitment problem.Then the solutions are decoded in solving the dispatching problem with an exact method to obtain the precise production of each unit. In this paper a multi-objective version of the UCP taking the emission of gas into account is presented. In this multi objective UCP the dispatching problem remains easy to solve whereas considering it separatly remains interesting. A multi-objective GA handling binary vectors is applied. However for a binary representation there is a set of solutions of the dispatching problem that are pareto equivalent. Three decoding strategies are proposed and compared. The main contribution of this paper is the third decoding strategy which attaches an approximation of the Pareto front from the associated dispatching problem to each genotypic solution. It is shown that this decoding strategy leads to better results in comparison to the other ones.

Authors

Sophie Jacquin, Lucien Mousin, Igor Machado, El-Ghazali Talbi, Laetitia Jourdan