Pré-requis:
Familles de Compétences
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 |
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.
Deux Tp à réaliser
Un projet avec un langage pédagogique dédié aux algorithmes
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