Logo ESI
Bannière
ESI talents

Bienvenue



Retour - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

Syllabus ALSDD
Télécharger



Crédits : 6

ALSDD
Algorithmique et Structure de données dynamique
Algorithmics and dynamic data structures

Coef : 5
VH Cours : 30.00
VH TD : 60.00
Pré-requis :
UEF1.1 : algorithmique et structures de données statiques

Ingénierie des Compétences

Familles de Compétences
  • CF4 : Concevoir, réaliser et maintenir des logiciels de qualité
Type de compétence: TEC : Technique, MET : Méthodologique, MOD : Modélisation, OPE : Opérationnel,
Niveau de compétence:
Base Intermédiaire Avancé


Famille de Compétence Compétence Elément de Compétence Type
CF4 C4.0: Développer des programmes informatiques C40.6: Confectionner un dossier technique de programmation MET
C40.5: Traduire un algorithme dans un langage de programmation et le commenter TEC
C40.4: Proposer un découpage modulaire en procédures et/ou fonctions et le justifier TEC
C40.2: Identifier les structures algorithmiques statiques et dynamiques adéquate pour construire un algorithme à partir de l’analyse d’un problème MET
C40.3: Déboguer un programme et vérifier un algorithme TEC
C4.A: Analyser et concevoir des algorithmes C4A.1: Etudier les structures de données et de fichiers et analyser l’efficacité des algorithmes MET

Description du programme de la matière

Objectifs:

Ce module aborde les aspects fondamentaux de la science informatique. Parmi les objectifs, nous pouvons citer :
- Maîtriser les structures de données de base
- Savoir appliquer et implémenter les structures de données de base
- Introduire les structures de données avancées
- Concevoir des algorithmes efficaces
- Analyser et mesurer la complexité des algorithmes

Contenu:

INTRODUCTION AUX POINTEURS (5 h.)
Introduction au langage Pascal
Allocations statique et dynamique
Relation entre tableaux et pointeurs

II LES LISTES LINEAIRES CHAINEES (6 h.)
définitions, fonctions de base et manipulations (longueur, accès, suppression, insertion,), tri de listes, implémentation des listes avec la représentation contigüe

III LES PILES ET LES FILES (3 h.)
Définitions, fonctions de base, utilisations,

IV LA RECURSIVITE (6 h.)
Principe
Conceptions d'algorithmes récursifs
Sémantique de la récursion
Passage d'algorithmes récursifs en algorithmes itératifs
La récursivité dans le langage c

V LES ARBRES (9 h.)
Définition, fonctions de bases
Arbres binaires
Définition, fonctions de bases, parcours des arbres
Arbres de recherche binaire (manipulation)
Arbres m-aires
Définition, fonctions de bases, parcours des arbres
Transformation en arbre binaire

VI LA COMPLEXITE (6 h.)
Efficacité en temps et en espace
Notation de Landau (O-notation)
Règles de calcul de la complexité d’un algorithme itératif
Calcul de la complexité des algorithmes récursifs

RECOMMANDATIONS :
Il est recommandé d’utiliser le vidéo projecteur pour le cours et de diffuser un support de cours ou polycopié.
les TDs/TPs doivent se faire dans des salles de cours équipées de matériels informatiques
L’accent doit absolument être mis sur l’aspect démarche méthodologique et respect du formalisme adopté
Le langage de programmation utilisé est le langage C. Il est introduit au fur et à mesure de l’avancement du cours. Son apprentissage se fera par autoformation par le biais de brochures.

Travail Personnel:

- Deux Tp à réaliser
- Un projet avec un langage pédagogique dédié aux algorithmes

Bibliographie:

- The art of Computer Programming, Volume 3: Sorting and Searching
Donald E. Knuth, Addison Wesley Professional

- Art of Computer Programming, Volume 1: Fundamental Algorithms
Donald E. Knuth, Addison Wesley Professional

- Data Structures and Their Algorithms
Harry R. Lewis, Larry Denenberg, Addison Wesley Professional

- Data structures using Pascal
Aaron M.Tenenbaum,Moshe J. Augenstein, Edition Prentice Hall International Editions

- Introduction to the Design and Analysis of Algorithms
Anany V. Levitin, Addison Wesley Professional

- Computer Algorithms: Introduction to Design and Analysis
Sara Baase,Allen Van Gelder,Addison Wesley Professional

- Algorithms in C, Parts 1-5 (Bundle): Fundamentals, Data Structures, Sorting, Searching, and Graph Algorithms
Robert Sedgewick, Addison Wesley Professional

- Computer Science: An Overview
J. Glenn Brookshear, Addison Wesley Professional

- Concepts of Programming Languages,
Robert W. Sebesta, Addison Wesley Professional

- Programming Languages: Concepts and Constructs
Ravi Sethi,Addison Wesley Professional

- History of Programming Languages, Volume
Thomas J. Bergin, Richard G. Gibson, Addison Wesley Professional

- Programming and Problem Solving with Delphi
Mitchell C. Kerman, Addison Wesley Professional

- Data structure and algorithms
A. V. Aho, J.E Hopcroft, J.D Ullman, Addison Wesley Professional

- Introduction to Algorithms, Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein, The MIT Press.

- Structures de données et de fichiers
D.E. ZEGOUR, Edition Chihab

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -