Cet enseignement nécessite de connaître et d'avoir intégré le contenu des UEs LIFAPI et LIFAPSD. Il est également préférable d'avoir suivi LIFAPB, LIFAPR et LIFProjet.

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
• ....

Le langage utilisé est le langage C++ sans recourir à l'héritage ni aux éléments les plus avancés de la norme C++11 (et normes postérieures). On pourra également être amené à programmer en C pur.

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

      Abordé en cours pour élargir vos compétences :

• Problèmes faciles et difficiles
• Classe P, NP et NP-complet (lien vers une liste de problèmes NP)

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, Master Theorem, Tri fusion

• 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

      Non fait en cours mais abordé en TP sous forme simplifiée liée à un cas particulier :

• 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*

Liens utiles :
Spécificateurs de format de printf
Spécificateurs de format de scanf

Des exemples simples de lecture écriture sur fichier (ascii ou binaire) :  readwritescanfprintblablabla .

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

Feuilles de TD : fournies sous forme papier dans les TDs en présentiel.

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 :

• Une implémentation des séquences triées performante pour les insertions : Skip-lists
  
• Eléments de correction (insertion avec ou sans doublon donnée sous une forme itérative, à vous d'écrire la fonction de recherche)
  

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 :

• Arbres cousus
  

Séance de TP8  :

• Arbres Binaires de Recherche Equilibrés : AVL 
• Si certains étudiants ont terminé, ils peuvent établir des statistiques sur le temps d'une recherche ou d'une insertion dans un AVL contenant n éléments et visualiser la courbe donnant ce temps moyen en fonction de n.
  

Séance de TP 9 (maj avec ajouts de conseils) :  Graphes, Recherche de chemins, Flot maximal dans une image et Coupe de graphe

• Erratum : Ne couper que les arcs saturés mais PAS LES ARCS DE FLOT NUL (ceci est lié à la simplification de l'algoithme adapté à des images)
• Heure limite repoussée à 23h59 pour le dépot de votre archive mardi soir
  Le travail n'a pas besoin d'être complet mais il doit être fait avec soin. Bien mettre en valeur tout ce qui a été fait.
  A minima, viser à chercher un chemin entre la source et le puit et le représenter (par exemple en mettant les pixels du chemin en noir) sur l'image originale (en niveau de gris).
  
• Graphes structurés en grille
• Graphe d'un terrain et recherche de chemin
  
• Des exemple d'images pgm ascii ici.
• Images et résultats obtenus (baboon niveau de gris (image originale en format réduit), baboon binarisée (format réduit), capacités obtenues pour baboon (format réduit), baboon binarisée (format entier) en 30 minutes et 284236 itérations,  petite image de test, binarisation petite image)
  
• Des exemples simples de lecture écriture sur fichier (ascii ou binaire) :  readwritescanfprintblablabla .
• 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.