EFF : Effectivité et efficacité

• Intervenant : Didier Caucal, chargé de recherche au CNRS (Didier.Caucal@irisa.fr)
• Volume : 21 heures

Présentation

Ce module fait suite à une demande d'étudiants en DEA et en thèse, et est un complément dans la connaissance générale en informatique.

Dans ce module, nous traitons les deux questions suivantes. Étant donné un problème, peut-on le résoudre de façon effective? Une solution donnée est-elle efficace? L'intérêt est d'éviter de rechercher un algorithme à un problème non effectif, et sinon d'être capable de distinguer les algorithmes efficaces de ceux qui ne le sont pas. Après des rappels nécessaires, nous proposons des études de cas variés permettant de maîtriser ces deux aspects dans des situations concrètes.

Aucun prérequis n'est demandé.

Plan du module

1. Effectivité : machines algorithmiques, problèmes sans solution effective, étude de cas.
2. Efficacité : combinatoire, récurrences, étude de cas.

Bibliographie

• L. Comtet, Analyse combinatoire, tomes 1 & 2, Presses Universitaires de France, 1970.
• D. Knuth, The art of computer programming, tomes 1 & 3, Addison Wesley, 1973.
• R. Sedgewick, P. Flajolet, Introduction à l'analyse des algorithmes, International Thomson Publishing France, 1996.
• A. Arnold, I. Guessarian, Mathématiques de l'informatique, Masson, 1992.
• C. Froidevaux, M.-C. Gaudel, M. Soria, Types de données et algorithmes, McGraw Hill, 1990.
• T. Cormen, C. Leiserson, R. Rivest, Introduction à l'algorithmique, Dunod, 1992.
• J.M. Autebert ``Calculabilité et décidabilité'' Masson 1992.
• M. D. Davis, E. J. Weyuker ``Computability, complexity and languages, Fundamentals of theoretical science'' Academic Press 1983
• D. Harel ``The spirit of computing'' Addison-Wesley 1987.
• J. Hopcroft, D. Ullman ``Introduction to automata theory, languages, and computation'' Addison-Wesley 1979.
• A. Salomaa ``Introduction à l'informatique théorique'' Armand Colin 1989.
• P. Wolper ``Introduction à la calculabilité'' Interéditions 1991.