M. Pelleau & O. Baldellon

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.

L2-INFO 6 ECTS 54h S3 marie.pelleau@univ-cotedazur.fr,olivier.baldellon@univ-cotedazur.fr

Description

Ce cours est divisé en deux sous-modules :

  1. Structures de données
  2. Programmation C

Intervenants

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.

Programme

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

Les supports de cours pour Programmation C sont ici.

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 suivantes sont dédiées à la programmation C.
    • 6 CMs (2h)
    • 6 TPs (3h)

Modalités de contrôle des connaissances

Vous avez :

  • 1 note en Structures de données (SdD) et
  • 1 note en Programmation C (C)

La note de ce module est la moyenne de ces 2 notes (SdD + C)/2

Note en Structures de données

Pour la note de structure de données :

  • 1 Contrôle Continu (CC)
  • 1 Contrôle Terminal (CT)

Le calcul de la note est le suivant : max (CT, (CC+CT)/2)

Note en Programmation C

  • 1 QCM (~25%)
  • 1 Projet (~25%)
  • Interros surprises en amphi (~?%)
  • 1 CT (~50%)

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