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.