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  (...)
• 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 (...)
• 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  - Présentation du cours, rappel sur les prérequis

• 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 de l'exemple de Module donné en exemple sur les slides : ici.

Cours 2 et 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
• 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
• Outils de preuve des algorithmes récursifs (exemple du tri fusion)
• Complexité des algorithmes récursifs (Exemple du tri fusion)
• Equation de récurrence

Cours 4 - Complexité des algorithmes récursifs, Tri fusion, TAD Séquence (ou Liste)

• 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
• 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 -  Tri par partition (Quick-sort), Récursivité

• 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

Cours 6 -  TAD Ensemble et TAD Table,Table de hachage, Pointeurs de fonction

• Dérécursification des appels récursifs non terminaux
  
• Type Abstrait Ensemble
• Notion de clé et Type Abstrait Table
• Fonction et table de hachage
• Gestion des collisions
• Adressage ouvert ou fermé
• Choix d'une fonction de hachage
• Pointeurs de fonction

Cours 7-   Arbre binaire, Analyseur syntaxique

• 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

Cours 8  -  Arbre binaire de Recherche (ABR), AVL (Adelson-Velsky et Landis), Arbres 2-3-4, Arbres Rouge Noir

• ABR totalement équilibrés
• 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   (Evoqués en TD )
  

Cours 9  -  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)

Cours 10 -  Graphes, Méthodes de conception

• 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  : 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 à rappatrier 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 : Version C++ non circulaire
  

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
  
• Comparaison de performances entre les Arbres Binaires de Recherche et Table de Hachage
  

Séance de  TP 7:

• Arbres Cousus (sujet à faire en autonomie)
• Evaluation par binôme et en visio de votre travail sur les Tables de Hachage, les ABR et leurs performances.
  

Séance de TP 8:

• Arbres Binaires de Recherche Equilibrés Rouge Noir.
  

Séance de TP 9 :  

• Graphes : Coupure de graphe
  

Séance de 10:  

• Evaluation du TP  portant sur les graphes, soit sur les arbres

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.