M. Pelleau, MCF/J.-C. Regin, PR
Structures de données et programmation C
Description
Ce cours est diviser en deux sous-modules :
- Structures de données
- 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
- CM 1, 4 diapositves par page, 2 diapositves par page + notes
- CM 2, 4 diapositves par page, 2 diapositves par page + notes
- CM 3, 4 diapositves par page, 2 diapositves par page + notes
- CM 4, 4 diapositves par page, 2 diapositves par page + notes
- CM 5
- TD1, TD2, TD3, TD4, TD5, TD6
- Contrôle continu, ainsi qu’une correction
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 :
- Introduction au C
- Tableaux, chaînes de caractères et caractères
- Pointeurs, chaînes de caractères et caractères
- Tableaux dynamiques et structures chaînées
- Nombre variable de paramètres, et fichiers
Supports de cours
- Le Cours. Il ne faut pas hésiter à venir le consulter régulièrement car il change souvent.
- TP1, TP2, TP3, TP4, TP5
- Les sources pour le TP3 et le TP5
- Le QCM de 2010 (contrôle continu) et avec les solutions
- Le deuxième contrôle de 2011, ce document contient les réponses aux questions
- L’énoncé du Projet de 2011
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