Socle commun deuxième année Licence Informatique

Algorithmique et structure de données

Course ID
UEF312
Campus
Département Informatique
Level
Licence
Semester
Semestre 3
Credit
6
Method
Cours, TD, TP

Objectifs de l’enseignement : ce module permettra aux étudiants d’apprendre d’une part la mise au point de certain algorithme de base en informatique, d’autre part, ils apprendront à manipuler des structure de données plus développées.

Connaissances préalables recommandées : algorithmique de base

Contenu de la matière :

Rappel

Chapitre 1 : Complexité algorithmique

  1. Introduction à la complexité
  2. Calcul de complexité

Chapitre 2 : Algorithmes de tri

  1. Présentation
  2. Tri à bulles
  3. Tri par sélection
  4. Tri par insertion
  5. Tri fusion
  6. Tri rapide

Chapitre 3 : Les arbres

  1. Introduction
  2. Définitions
  3. Arbre binaire
    • Définition
    • Passage d’un arbre n-aire à arbre binaire
    • ‘eprésentation chaînée d’un arbre binaire
    • Parcours d’un arbre binaire
      • Parcours préfixé (préordre ou RGD)
      • Parcours infixé (projectif, symétrique ou encore GRD)
      • Parcours postfixé (ordre terminal ou GDR)
    • Arbres binaires particuliers
      • Arbre binaire complet

3.5.3. Arbre binaire de recherche

Chapitre 4 : Les graphes

  1. Définition
  2. Représentation des graphes
  3. Parcours des graphes

NB : TP en C.

Mode d’évaluation : Examen (60%), contrôle continu (40%)

 Thomas H. Cormen, Algorithmes Notions de base Collection : Sciences Sup, Dunod,

  • Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest Algorithmique – 3ème édition – Cours avec 957 exercices et 158 problèmes Broché, Dunod,
  • Rémy Malgouyres, Rita Zrour et Fabien Initiation à l’algorithmique et à la programmation en C : cours avec 129 exercices corrigés. 2ième Edition. Dunod, Paris, 2011. ISBN : 978-2-10-055703-5.
  • Damien Berthet et Vincent Labatut. Algorithmique & programmation en langage C – vol.1 : Supports de cours. Licence. Algorithmique et Programmation, Istanbul, Turquie. 2014, 232.
  • Damien Berthet et Vincent Labatut. Algorithmique & programmation en langage C – vol.2 : Sujets de travaux pratiques. Licence. Algorithmique et Programmation, Istanbul, Turquie. 2014, pp.258.
  • Damien Berthet et Vincent Labatut. Algorithmique & programmation en langage C – vol.3 : Corrigés de travaux pratiques. Licence. Algorithmique et Programmation, Istanbul, Turquie. 2014, pp.217.
  • Claude Delannoy. Apprendre à programmer en Turbo C. Chihab- EYROLLES,