Cet enseignement nécessite de connaître
et d'avoir intégré le contenu des UEs LIFAP1 et LIFAP3. Il est
également préférable d'avoir suivi LIFASR3, LIFAP2 et
LIFAP4. 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 (...)
- Paramètres non modifiables : Donnée,
- Paramètres modifiables : 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 (...)
- Constructeur et destructeur, surcharge de l'opérateur d'affectation
- 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)
- E/S avec << et >>
- Différentes étapes
de la compilation (...)
- Makefile
- Types abstraits Liste, File, Pile et Arbre Binaire de Recherche
- ....
Contenu fourni à titre indicatif
Cours
1 et 2 -
Présentation du cours, rappel sur les prérequis, introduction ou rappel de la notion de module
- Organisation de la mémoire : pile et tas, allocation dynamique
- Différence entre pointeur et référence
- Types abstraits
- Programmation modulaire et mise en oeuvre en C++
- Constructeurs, destructeurs, opérateurs d'affectation
Fichiers C++ de l'exemple du Module Complexe donné en exemple sur les slides :
ici.
Cours 3 - Preuve d'algorithme, classes de complexité, analyse asymptotique, preuve et complexité des algorithmes itératifs
- Conception et analyse d'un algorithme
- Preuve d'un algorithme
- Analyse de complexité
- Complexité des algorithmes itératifs
- Outils d'analyse asymptotique
Non fait en cours :
Cours 4 -
Outils de preuve, Tri fusion, TAD Séquence (ou Liste)
- Outils de preuve des algorithmes itératifs
- Outils de preuve des algorithmes récursifs (exemple du tri fusion)
- Retour sur le Type Abstrait Séquence et ses différentes implantations possibles
- Introduction des skip-lists pour l'implantation des Séquences Triées (et un lien vers l'article de recherche de l'inventeur des skip-lists, pour illustrer l'intérêt de la recherche en informatique)
Cours 5 -
Complexité des algorithmes récursifs,
Tri par partition (Quick-sort), Récursivité
- Complexité des algorithmes récursifs (Exemple du tri fusion)
- Equation de récurrence
- Master Theorem concernant l'analyse des algorithmes "diviser pour régner" (Divide and conquer)
- Retour sur les versions itératives et récursives du tri fusion
Cours 6 - TAD Ensemble et TAD Table,Table de hachage, Pointeurs de fonction
- Type Abstrait Ensemble
- Notion de clé et Type Abstrait Table
- Fonction et table de hachage
- Gestion des collisions
- Adressage ouvert
- Pointeurs de fonction
(non fait en cours)
- Adressage fermé
- Exemple de fonctions de hachage
Cours 7- Tri par partition, dérécursitication partielle ou totale
- Retour sur les algorithmes de tri sur place
- Tri par partition (Quick-sort)
- Coût de la récursivité
- Dérécursification, appels récursifs terminaux
- Dérécursification des appels récursifs non terminaux
Cours 8 - Arbres binaires, Analyseur syntaxique, Arbres Binaires de recherche
- Rappels sur les Arbres Binaires
- Dérécursification du parcours en profondeur d'un Arbre Binaire
- Analyse syntaxique pour la construction de l'arbre binaire d'une expression arithmétique (non fait en cours)
- Rappels sur les Arbres Binaires de Recherche (ABR) (parcours, insertion, taille, ...)
- Suppression dans un ABR
- ABR totalement équilibrés
Cours 9 - Arbre binaire de Recherche (ABR), AVL (Adelson-Velsky et Landis), Arbres 2-3-4, Arbres Rouge Noir
- ABR auto équilibrants
- AVL, définition
- Opérations de rééquilibrage dans les AVL : rotations droite, gauche, double à droite et double à gauche
- Arbres 234 (les B-arbres en sont une généralisation, utilisés dans les mécanismes de gestion des bases de données) (Abordés en TD)
- Arbres Rouge Noir (non faits en cours cette année)
Cours 10 - Graphes
- exemples de problèmes abordés en théorie des graphes
- graphes orientés vs. non orientés,
- définitions (chaînes, circuits, degré, etc.)
- représentation matricielle ou par liste d'adjacence
- parcours de graphe (largeur, profondeur)
- tri topologique
- admissibilité d'un plus court chemin
- introduction aux algorithmes gloutons
- algorithme de Dijkstra
- réseau de transport
- Algorithme de Ford-Fulkerson
Abordés en TD uniquement : Arbres couvrants minimum, coloriage de graphes
Cours complémentaire : Méthodes de conception (approfondis en TD10)
- Algorithmes incrémentaux
- Diviser pour régner
- Programmation dynamique
- Algorithmes gloutons
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, ...)
- Mise en oeuvre avec des void*
Il
pourra arriver que vous ayez à
rapatrier des fichiers sources sur ce site.
La description suivante peut-être
sujette à des modifications et est juste fournie à titre indicatif.
Séance de TP1 :
- Adapter un module aux changement de compilateurs g++, gcc
- Listes génériques
- Fichiers fournis
- Module Complexe : version
C/C++, version C
- Module Element (à étendre si besoin) et entêtes du Module Liste : Version C++, version C
- Eléments de correction pour la version C++ (certaines fonctions sont données sous une forme itérative puis sous une forme récursive)
Séance de TP 2 :
- Ajout d'une cellule (sentinelle) à une liste chaînée non circulaire
- Module liste triée ; ajout d'un second niveau de chaînage
Séance de TP 3 :
Séance de
TP 4 :
- Profil de complexité de la recherche et de l'insertion dans une
Skip-List; comparaison au profil obtenu pour des Listes et ou des
Tableaux Dynamiques Triés.
- Fichiers fournis
- Rappels lecture/écriture sur fichiers (readwritescanfprintblablabla) avec fprintf, fscanf, fread et fwrite. Vous pouvez aussi utiliser des ofstream et des ifstream.
Séance de TP 5 :
- Table de hachage.
- Commencer la séance en se renseignant sur les pointeurs de
fonctions qui seront utilisés dans ce TP (voir dernier slides du Cours
06).
Séance de TP 6 :
- Arbre
Binaire de Recherche (prérequis de l'UE)
- Comparaison de performances entre les Arbres Binaires de Recherche et Table de Hachage
Séance de TP 7 :
Séance de TP8 :
- Evaluation sur les arbres binaires, leur parcours, leur
couture et notions d'équilibres vues en cours : Interrogation en
début de TP.
- Arbres Binaires de Recherche Equilibrés : AVL ( sujet )
Séance de
TP 9 : Graphes, Dijkstra et Voronoï
- Graphes structurés en grille
- Graphe d'un terrain et recherche de chemin
- Pour des affichages ascii en couleur : exemple
Séance de
10:
- Evaluation du TP portant sur les graphes.
- Au programme une interro portant sur l'archive que vous avez rendue. Puis chaque binome sera interrogé à tour de rôle. Pendant ce temps, les autres étudiants travailleront sur l'algorithme A* : sujet (cette fois-ci le travail n'est pas à rendre :-) ).
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.