UE Algorithmique 1

Ce cours d'introduction présente les concepts de base indispensables à l'écriture d'algorithmes, prélude à l'activité de programmation. Un algorithme est vu ici comme une séquence d'actions (ou instructions) agissant sur un ensemble d'informations afin de résoudre un problème donné. Un langage algorithme standard est utilisé pour décrire les algorithmes. Les informations de l'algorithme sont distinguées en tant variables ou constantes typées, et sont déclarées dans le lexique de l'algorithme. Entier, réel, booléen, caractère, chaîne de caractères sont les types prédéfinis, à partir desquels d'autres types nommés (agrégats, énumérés, ...) peuvent être construits. Les instructions de base permettant de manipuler les informations sont la saisie, l'affichage, les structures conditionnelles et itératives. L'exécution d'une instruction de l'algorithme fait passer le système (l'ordinateur) d'un état (caractérisé par les valeurs d'un ensemble de variables de l'algorithme dites d'observation) à un autre. Un ensemble d'instructions correspondant à la résolution d'un (sous-)calcul (respectivement d'un (sous-)problème) peut être identifié et donner lieu à la définition d'une fonction (respectivement d'une action) qui viendra compléter le lexique de l'algorithme et pourra être utilisé au sein d'une instruction. Ces fonctions et actions, à travers la notion de paramétrage, permettent de lancer leur exécution à partir de configurations de données d'entrée diverses. Réunies au sein d'un système, elles en constituent l'ensemble des primitives indispensables à son utilisation, comme c'est le cas pour la Machine Tracés. Les structures de données de type tableaux permettent de manipuler un groupe d'informations en accédant directement à chaque information. Lorsque chaque information au sein d'un tableau est un tableau, on parle de tableaux multidimensionnels. Les fichiers quant à eux proposent un accès séquentiel à l'information et sont manipulés par des primitives et des schémas de traitement spécifiques. Enfin, la récursivité offre pour certains problèmes et de structures de données idéales (comme les tableaux) constitue une approche élégante et compacte de résolution.

• objectif 1 : maîtriser les notions de base de l'algorithmique : déclarations de variables et de types, instructions de base (conditionnelles, itératives), structures de données (tableaux, fichiers), fonctions et actions, récursivité

• objectif 2 : maîtriser la décomposition d'un problème en sous-problèmes et, de là, la décomposition modulaire d'un algorithme en sous-algorithmes (actions et/ou fonctions)

• objectif 3 : maîtriser le choix et la manipulation de types et de structure de données adaptés à la résolution d'un problème donné

aucun pré-requis pour ce cours de base d'algorithmique

Aucun dispositif ni matériel électronique n'est nécessaire. L'activité de conception d'algorithme est avant tout une tâche intellectuelle, le raisonnement produit pour résoudre le problème de donnée est transcriptible sur support papier au moyen du langage algorithmique.

Les notions vues en cours sont mises en pratique lors de séances de Travaux Dirigés

Curiosité naturelle, appétence pour les activités de réflexion et de résolution de problème

• A. Aho, J. Hopcroft, J. Ullman, Structures de données et algorithmes, InterEditions, Paris (Fr), 1987.

• T. Cormen, C. Leiserson, R. Rivest, Introduction à l'algorithmique, Dunod, Paris (Fr), 1994

• C. Froidevaux, M.-C. Gaudel, M. Soria, Types de données et algorithmes, Ediscience, Paris (Fr), 1993.

• D. Knuth, The art of computer programming, Addison-Wesley, Reading (MA US), 1973.

  Bien sûr, cette liste peut être complétée par une recherche sur Internet…

  En règle générale, l'algorithmique est affaire de technique et donc de pratique, tout autre ouvrage proposant des exercices (d'algorithmique ou de programmation) et leur solution détaillée, est donc a priori intéressant