Université Claude
Bernard - Département Informatique Lyon 1
Algorithmique, Programmation et Complexité - LIF9
|
Licence
Sciences et Technologies - L3
2015-2016 -
Semestre automne
|
Algorithmique,
Programmation
et Complexité
Nouvelles récentes :
- Dans le cadre de la mise en place de la nouvelle habilitation, LIF9 évolue et s'appelle désormais LIFAP6.
Prérequis
:
Cet
enseignement nécessite de connaître et d'avoir intégré le contenu des
UEs LIF1 et LIF5. Il est également préférable d'avoir suivi LIF3 et
LIF7. Voici ici une liste non exhaustive des notions sur lesquelles
vous rafraîchir la mémoire avant d'aborder l'UE :
- Gestion de la mémoire (...)
- Organisation en pile des variables d’un programme
- Allocation dynamique dans le tas (new/delete, malloc/free)
- Différents modes de passage des paramètres d’une
procédure (...)
- Donnée, donnée-résultat, résultat
- Notion de pointeur (...)
- Arithmétique des pointeurs (...)
- Différence entre (type) pointeur et (pseudo-type) référence (...)
- Type Abstrait et Programmation Modulaire (...)
- Nuance entre définition et déclaration
- Spécificité des
tableaux statiques et des chaînes de caractères en C/C++ (...)
- Lecture /
écriture
- scanf, printf, … (entrée/sortie standard)
- fscanf, fprintf, fread, fwrite, feof, fopen, fclose, …
(entrée/sortie sur fichiers)
- Différentes étapes
de la compilation (...)
- Makefile
- Types abstraits Liste, File, Pile et Arbre Binaire de Recherche
- ....
Plus de précisions sur le(s)
langage(s)
Le
langage utilisé est une extension du langage C
(ANSI89-ISO90) auquel
sont ajoutés certains éléments C++
(ISO98), à
l'exclusion des éléments relatifs à la
programmation objet
(au programme
de LIF13). On pourra également choisir de programmer en C pur
(on peut dans ce cas utiliser une normalisation plus récente que
ISO90).
Transparents de cours :
Cours
1 -
Paradigmes de programmation, prérequis
- Différence entre pointeur et référence
- Retour
sur les principaux paradigmes de programmation
- ... et
conclusions à en tirer pour une saine programmation C pur ou C/C++
Cours
2
- Généricité
- Introduction à la généricité
- Macros
- Pointeurs de fonctions
- Généricité en C et en C/C++ (échange générique, éléments génériques, ...)
Cours 3
- Preuve d'algorithme, classes de complexité, preuve et complexité des algorithmes itératifs (resp. récursifs),
- Conception et analyse d'un algorithme
- Preuve d'un algorithme
- Analyse de complexité
- Outils d'analyse asymptotique
- Problèmes faciles et difficiles
- Classe P, NP et NP-complet (lien vers une liste de problèmes NP)
- Outils de preuve des algorithmes itératifs vs. récursifs (exemple du tri fusion)
- Complexité des algorithmes itératifs vs. récursifs
Cours 4 -
Complexité des algorithmes récursifs, tri par partition (Quick-sort), TAD Séquence (ou Liste)
- Complexité des algorithmes récursifs
- Equation de récurrence
- Théorème concernant l'analyse des algorithmes "diviser pour régner" (Divide and conquer)
- Retour sur le tri fusion
- Tri par partition (Quick-sort)
- Retour sur le Type Abstrait Séquence et ses différentes implantations possibles
- Introduction des skip-lists (et un lien vers l'article de recherche de l'inventeur des skip-lists, pour illustrer ce que représente la recherche en informatique)
Cours 5 - TAD Ensemble et TAD Table, Table de hachage
- Coût de la récursivité
- Dérécursification des appels récursifs terminaux
- Type Abstrait Ensemble
- Notion de clé et Type Abstrait Table
- Fonction et table de hachage
- Choix d'une fonction de hachage
Cours 6 - Table de hachage (fin), Arbre binaire (AB)
- Gestion des collisions
- Adressage ouvert ou fermé
- Rappels sur les Arbres Binaires
- Dérécursification du parcours en profondeur d'un Arbre Binaire
Cours 7 - Analyseur syntaxique, Arbre binaire de Recherche (ABR), AVL (Adelson-Velsky et Landis)
- Analyse syntaxique pour la construction de l'arbre binaire d'une expression arithmétique
- Rappels rapides sur les Arbres Binaires de Recherche (ABR)
- ABR totalement équilibrés
- ABR auto équilibrants : AVL
Cours 8 - AVL, Graphes
- Opérations de rééquilibrage dans les AVL : rotations droite, gauche, double à droite et double à gauche
- Arbres 234
- Arbres Rouge Noir (Abordés en TD et en TP uniquement)
- graphes orientés vs. non orientés,
- définitions (chaînes, circuits, degré, etc.)
Cours 9 - Graphes
- représentation matricielle ou par liste d'adjacence
- parcours de graphe (largeur, profondeur)
- Tri topologique
- Admissibilité d'un plus court chemin
- Introduction aux algorithmes glouton
- Algorithme de Dijkstra
Cours 10 : Réseaux, Méthodes de conception
- Réseau de transport
- Algorithme de Ford-Fulkerson
Abordés en TD uniquement : (Arbres couvrants minimum, coloriage de graphes)
- Algorithmes incrémentaux
- Diviser pour régner
- Programmation dynamique
- Algorithmes gloutons
Les phrases clé du cours :
.
Informations
concernant les
TDs :
Les
feuilles
de TD sont distribuées pendant les
séances.
Informations
concernant les
TPs :
Les
feuilles
de TP sont distribuées pendant les séances. Il
pourra arriver que vous ayez à
rapatrier des fichiers sources sur ce site.
Spécificateurs
de format de printf
Spécificateurs
de format de scanf
Concernant les outils de
gestion de projet, de compilation et de déboggage (gcc, valgrind), vous
pouvez vous rafraîchir la mémoire en consultant les
prérequis de LIF7 ainsi que les liens suivants :
- Compilation avec gcc sous Linux
- Mise au point de programmes avec GDB
- Gestion de projet : Make et Makefile, ou Comment écrire un Makefile
Séance de TP1 :
- Adapter un module aux changement de compilateurs g++, gcc
- Listes génériques
- Fichiers fournis
Séance de TP en autoformation :
Fin du TP1
Séance de TP 2 :
- Module élément générique
- Listes génériques
Séance de TP 3 et 4 :
- Retour sur les Listes génériques
- Skip-lists
- Fichiers fournis
Séance de
TP 5 :
Séance de TP 6 :
- Travail sur le TP à rendre (skip-list)
Séance de TP 7 et 8:
- Evaluation du TP sur les skip-lists
- Analyseur syntaxique d'une expression arithmétique par construction et évaluation de l'arbre binaire associé
Séance de
TP 9 et 10:
- Graphes :
- Votre algorithme de recherche de plus court chemin doit être
indépendant de votre application et ne manipuler le graphe qu'à travers
son interface générale.
Séance de
TP 11 :
- Evaluation du TP sur les graphes (interro sur papier à 14h, puis démonstration en salle machine, par binôme).
Contrôle
continu Intégral
Rendu de TPs
Interro de cours : au début de certaines séances de TD
Contrôle terminal (exemple annale contrôle final)
Il
est vivement
conseillé :
- de
lire attentivement les
transparents ainsi que vos notes de cours
- de
s'entraîner
à refaire les exercices vus en TD/TPs
L'assiduité des étudiants entre
également dans l'évaluation du contrôle
continu.
Bibliographie
C++ :
- The
C++
Programming Language,
Bjarne Stroustrup, 3. Auflage, Addison-Wesley,
1997, (existe en version française) - Le
langage et la
bibliothèque C++, Norme ISO
Henri Garetta, Ellipse, 2000
- C++
Primer, Lippman & Lajoie,
Third Edition, Addison-Wesley, 1998
- Effective
C++,
Scott Meyers, Second Edition, 1998
- The
Design and Evolution of C++,
Bjarne Stroustrup, 1994
- The
ISO/IEC C++ standard,
American National Standards Institute, First Edition, 1998
Bibliographie
C :
- The C
Programming Language (Ansi C)
B.W. Kernighan - D.M. Ritchie
Ed. Prentice Hall, 1988
Le langage C - C ANSI
B.W. Kernighan - D.M. Ritchie
Ed. Masson - Prentice Hall, 1994
- Langage
C - Manuel de
référence
Harbison
S.P., Steele Jr. G.L.
Masson, 1990
(traduction en français par J.C. Franchitti)
- Méthodologie
de
la programmation en langage C,
Principes et applications
Braquelaire
J.P.
Masson, 1995
- N'oubliez
jamais de vous
servir du man!
Bibliographie
Algorithmique
:
- Introduction
to Algorithms
Cormen T., Leiserson C., Rivest R.
MIT Press, Cambridge, 1990
Introduction à l'algorithmique
Cormen T., Leiserson C., Rivest R.
Dunod, 1994
- Structures
de
données et algorithmes
A. Aho, J.Hoptcroft, J. Ullman,
InterEditions
- Types
de données et algorithmes
C. Froideveaux, M.C. Gaudel, M. Soria,
Ediscience
- The
Art
of Computer Programming
D. Knuth, Vol. 1 et 3, Addison-Wesley
- Algorithmes
de graphes
C. Prins,
Eyrolles
Sites web
Unix
and Internet Fundamentals HOW TO ( VO, VF
)
Informations
pratiques et enseignants:
Cours
magistral :
Mercredi 10h à 11h30 -- 10
séances (ne correspondant pas forcément à des semaines consécutives)
TD :
10 séances de 1h30 (ne
correspondant pas forcément à des semaines consécutives) le mercredi de 8h15 à 9H45
TP :
10 +1 séances de 3h00, le mercredi de 14h30 à 17h30
Soutien :
(voir calendrier)
- Cours
- Chaine
Raphaëlle (raphaelle.chaine(à)liris.cnrs.fr)
(semestre automne)
- TD
et TP
- Chaine Raphaëlle (raphaelle.chaine(à)liris.cnrs.fr)
- Hamdi Cherif Azzouz (azzouz.hamdi-cherif(à)liris.cnrs.fr)
- Iehl Jean-Claude (jciehl(à)bat710.univ-lyon1.fr)
- Louvet Nicolas (nicolas.louvet(à)univ-lyon1.fr)
- Nivoliers Vincent (vincent.nivoliers(à)univ-lyon1.fr)