COVID-19
COVID-19

Algorithmique et Structure de données dynamique

Description du programme de la matière:
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

ID Cours
ALSDD
Niveau
1ère année CP
Semestre
Semestre 2
Crédit
6
Volumes Horaires Cours
30.00
Coef
5
Volumes Horaires TD
60.00

Pré-requis:

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

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

We are using cookies to give you the best experience. You can find out more about which cookies we are using or switch them off in privacy settings.
AcceptPrivacy Settings

GDPR