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

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

Cours 1 - Paradigmes de programmation, généricité 

• 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++
• Introduction à la généricité

Cours 2 - Preuve d'algorithme, classes de complexité

• 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, ...)
• Conception et analyse d'un algorithme
• Preuve d'un algorithme
• Analyse de complexité
• Outils d'analyse asymptotique

Cours 3 - Preuve et complexité des algorithmes récursifs, Tri par partition (Quick-sort)

• Problèmes faciles et difficiles
• Classe P, NP et NP-complet (lien vers une liste de problèmes NP)
  
• Outils de preuve des algorithmes récursifs vs. itératifs
• 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)

Cours 4 - TAD Séquence (ou Liste), TAD Ensemble et TAD Table

• Coût de la récursivité
• Dérécursification des appels récursifs terminaux
• 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)
• Type Abstrait Ensemble
• Notion de clé et Type Abstrait Table
• Fonction et table de hachage

Cours 5 - Table de hachage
 

• Fonction et table de hachage
• Gestion des collisions
• Adressage ouvert ou fermé
• Choix d'une fonction de hachage

Cours 6 -  Arbre binaire (AB), analyseur syntaxique, Arbre binaire de Recherche (ABR)

• 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
• Rappels rapides sur les Arbres Binaires de Recherche (ABR)
• ABR totalement équilibrés
  

Cours 7 -  AVL (Adelson-Velsky et Landis)

• ABR auto équilibrants : AVL 
• Opérations de rééquilibrage dans les AVL : rotations droite, gauche, double à droite et double à gauche
• Arbres 234
    Abordés en TD et en TP uniquement :
• Arbres Rouge Noir

Cours 8 -  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 9 -  Graphes

• Tri topologique
  
• Admissibilité d'un plus court chemin
• Introduction aux algorithmes glouton
• Algorithme de Dijkstra
• Réseau de transport
• Algorithme de Ford-Fulkerson
   
  Abordés en TD uniquement :
• Arbres couvrants minimum 
• coloriage de graphes

Cours 10 :  Méthodes de conception

• Algorithmes incrémentaux
• Diviser pour régner
• Programmation dynamique
• Algorithmes gloutons

.

Les feuilles de TD sont distribuées pendant les séances. 

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
• Module Complexe : version C/C++, version C
• Module Element (à étendre si besoin) et entêtes du Module Liste : Version C/C++, version C

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
• Module Tableau Dynamique
• Rappels lecture/écriture sur fichiers

Séance de TP 5 et 6 :

• Table de hachage

Séance de TP 7 et 8 :

• Arbre rouge/noir
• Fichiers fournis
• Module Arbre Binaire de Recherche (non équilibré)
  

Séance de TP 9 :  

• Graphes : Algorithme Dijkstra
• Dans votre application, les sommets de la grille 2D seront également dotés d'une amplitude.
• 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 10 :

•  ...
  

Séance de TP 11 :

• ...
  

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.