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

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

       Non  fait en cours :

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

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 :

• Skip-lists

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  :

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