Aller au menu Aller au contenu
Diversité scientifique et technologique
L'école d'ingénieurs de physique, électronique, matériaux
Diversité scientifique et technologique

> Formation

Structures de Données et Algorithmes (PET S6) - 3PMEALG6

A+Augmenter la taille du texteA-Réduire la taille du texteImprimer le documentEnvoyer cette page par mail Partagez cet article Facebook Twitter Linked In Google+ Viadeo
  • Volumes horaires

    • CM : 5.0
    • TD : 5.0
    • TP : 14.0
    • Projet : 8.0
    Crédits ECTS : 2.5

Objectifs

L'enseignement introduit les principales notions et structures de données à la base des solutions à de nombreux problèmes non numériques. Il aborde la programmation récursive et les principales structures de données dynamiques et types abstraits utilisées aujourd'hui (listes, piles, files, arbres, graphes) et présente quelques implémentations et algorithmes utilisant ces structures de données.

Contact Michel DESVIGNES

Contenu

  • Principales notions abordées :
    1. Programmation récursive, notion de complexité
    2. Notion de Type de Données Abstraites
    3. Structures de données chaînées linéaires : listes, piles, files
    4. Dictionnaires et tables de hachage
    5. Structures de données arborescentes : arbres binaire
  • Tp : Ces notions sont mises en oeuvre BE par les étudiants, en langage C, sous Linux, sur des exemples concrets; Quelques exemples de problèmes traités :
    1. Fractale de MandelBrot et Récursivité
    2. Tri par tas
    3. Jeu de carte de la bataille avec pile et file
    4. Vérificateur orthographique et Table de Hachage
    5. Calcul formel de dérivée d'expressions mathématiques et arbre binaire
    6. Mini projet: Recherche d'itinéraires dans le métro et le RER parisien par recherche du plus court chemin dans un graphe avec différents algorithmes : Dijkstra, Bellman, A-Star.


Prérequis

Cours Programmation Structurée - Algorithmique (PET-S1)

Contrôles des connaissances

Examen Ecrit (2h)
Compte rendu de projet



Session 1 : Examen Ecrit1 x 80% + Projet 20%
Session 2 : Examen Ecrit2 x 80% + Projet 20%

Informations complémentaires

Cursus ingénieur->1A-PET->Semestre 6
Cursus ingénieur->1ère année ingénieur Phelma->Semestre 6

Bibliographie

Robert Sedgewick : Algorithms in C, Parts 1-5 (Bundle): Fundamentals, Data Structures, Sorting, Searching, and Graph Algorithms, Addison-Wesley, 2002, 0201756080
C.Froidevaux, M.C.Gaudel, M.Soria : Types de données et algorithmes , McGraw-Hill, 1990
A. Aho, J. Hopcroft, J. Ullman. Data structures and algorithms .Addison-Wesley, 1983.
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest : Introduction to Algorithms. MIT Press and McGraw-Hill., Third Edition. MIT Press, 2009. ISBN 978-0-262-53305-8.

A+Augmenter la taille du texteA-Réduire la taille du texteImprimer le documentEnvoyer cette page par mail Partagez cet article Facebook Twitter Linked In Google+ Viadeo

mise à jour le 11 juin 2015

Grenoble INP Institut d'ingénierie Univ. Grenoble Alpes