M. Pelleau, MCF/J.-C. Regin, PR

Structures de données et programmation C

Ce cours a pour objectif d'introduire les structures de données les plus classiques en s'appuyant sur le langage de programmation bas niveau C.

Description

Ce cours est diviser en deux sous-modules :

  1. Structures de données
  2. Programmation C

Structures de données

Ce cours a pour objectif l’étude des structures de données et des algorithmes fondamentaux permettant d’organiser, de chercher et de manipuler des données de manière efficace. Il y a en fait deux parties bien distinctes dans cet enseignement. Il s’agit d’une part d’apprendre à utiliser des structures et des algorithmes, mais aussi de comprendre leur fonctionnement interne afin de pouvoir choisir le mieux adapté à un problème donné.

Le programme détaillé de cet enseignement est le suivant, les structures de données classiques seront étudiées :

  • Rappel sur les tableaux
  • Piles
  • Files
  • Listes

Pour chaque structure de données on considérera les algorithmes de manipulations classiques (ajout, insertion, suppression d’éléments…) Puis certains algorithmes utilisés dans le monde qui nous entourent et s’appuyant sur les structures de données vues seront détaillés, comme les algorithmes de tris par fusion ou par tas, l’algorithme de codage MP3… Afin de faciliter l’enseignement, un langage de description des algorithmes, proche d’un langage naturel, sera introduit et servira pendant les TDs. Pour chacun des algorithmes étudiés, nous analyserons la complexité algorithmique afin de déterminer les performances théoriques.

Supports de cours

Programmation C

Il s’agit d’une introduction à la programmation dans le langage C. C est un langage de programmation impératif devenu l’un des plus utilisés dans le monde.

Ce cours est divisé en 5 grandes parties :

  1. Introduction au C
  2. Tableaux, chaînes de caractères et caractères
  3. Pointeurs, chaînes de caractères et caractères
  4. Tableaux dynamiques et structures chaînées
  5. Nombre variable de paramètres, et fichiers
Supports de cours

Calendrier

  • Les 6 premières séances sont dédiées aux Structures de données.
    • 6 CMs (2h)
    • 6 TDs (2h)
  • Les 6 séances siuvantes sont dédiées à la programmation C.
    • 6 CMs (2h)
    • 6 TPs (3h)

Modalités de contrôle des connaissances

  • 2 CC (1 en structure de données, 1 en programmation C)
  • 1 CT

Ressources

  • T. Cormen, C. Leiserson, R. Rivest, Introduction à l’algorithmique, Dunod
  • D. Knuth, The Art of Computer Programming
  • R. Tarjan, Data Structures and Network Algorithms
  • R. Ahuja, T. Magnanti et J. Orlin, Network Flows, Prentice Hall
  • C. Berge, Graphes et hypergraphes, Dunod
  • M. Gondran et M. Minoux, Graphes et Algorithmes
  • B.W. Kernighan, D.M. Ritchie, The C Programming Language, Prentice Hall
  • B.W. Kernighan, D.M. Ritchie, Le langage C - C ANSI Kernighan, Masson - Prentice Hall, Traduit par J.-F. Groff et E. Mottier
  • S.P. Harbison, G.L. Jr. Steele, Langage C - Manuel de référence, Masson, Traduit en français par J.C. Franchitti