Aller au contenuAller à la rechercheAller au menu

UE Algorithmique 2

Diplômes intégrant cet élément pédagogique :

Descriptif

Ce cours avancé d'algorithmique fait suite au cours d'introduction d'algorithmique ("Algorithmique 1"). Il s'agit de progresser dans la maîtrise de techniques et de structures de données élaborées. L'accent est d'abord mis sur la gestion d'un ensemble d'informations encapsulé au sein d'une structure de classe à laquelle est associée un ensemble de primitives permettant la création d'un tel ensemble, l'ajout d'un nouvel élément à l’ensemble, la modification d'un élément existant, la suppression d'un élément, l'énumération (parcours) des éléments, la recherche d'un élément particulier. La notion d'ordre sur les informations permet alors d'introduire des techniques de tri classiques (insertion, sélection, à bulles). Dans une deuxième partie, les notions de pointeur et de liste chainée sont introduites. Les primitives décrites plus haut sont examinées dans ce contexte. Le chapitre 3 s'intéresse à la notion d'adressage dispersé et à la technique dite de hachage. Les structures de graphes, plus particulièrement celles d'arbres et d'arbres n-aires et binaires, sont explorées à travers différents types de parcours. Enfin, des techniques plus élaborées de tri sont introduites.

  • objectif 1 : maîtriser les notions avancées de l'algorithmique : classe, pointeur, adresse, liste chainée, hash-table, graphe, arbre, tri

  • 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é

Pré-requis recommandés

le pré-requis est d'avoir suivi le cours "Algorithmique 1" et d'en maîtriser les bases ou des notions équivalentes, le même langage algorithmique étant ici utilisé

Compétences visées

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

Bibliographie

  • 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

Informations complémentaires

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

Lieu(x) : Grenoble
Langue(s) : Français