Matière Algorithmique et structure de données 3
Unité d’enseignement fondamentale : UEF1
Crédits : 6
Coefficient : 3
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
3.1. Définition
3.2. Passage d’un arbre n-aire à arbre binaire
3.3. Représentation chaînée d’un arbre binaire
3.4. Parcours d’un arbre binaire
3.4.1. Parcours préfixé (préordre ou RGD)
3.4.2. Parcours infixé (projectif, symétrique ou encore GRD)
3.4.3. Parcours postfixé (ordre terminal ou GDR)
3.5. Arbres binaires particuliers
3.5.1. 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%)
Références
- Thomas H. Cormen, Algorithmes Notions de base Collection : Sciences Sup, Dunod, 2013.
- Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest Algorithmique - 3ème édition - Cours avec 957 exercices et 158 problèmes Broché, Dunod, 2010.
- Rémy Malgouyres, Rita Zrour et Fabien Feschet. 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, pp.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. <cel-01176120>
- 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. <cel-01176121>
- Claude Delannoy. Apprendre à programmer en Turbo C. Chihab- EYROLLES, 1994.