Nouvelles

  • Le TP sur les arbres n-aires devra être rendu sur SPIRAL lundi 30 mars à 23h00 au plus tard
  • Interrogation en début de séance de TD le mercredi 18 mars à 8h00 (le sujet portera sur les TDs 1, 2 et 3)
  • Premier cours mercredi 4 février à 8h00, Amphi Jussieu, bâtiment Darwin

Intervenants

Par ordre alphabétique :

  • Julie DIGNE (julie.digne[AT]liris.cnrs.fr) : TD, TP
  • Raphaëlle CHAINE (raphaelle.chaine[AT]univ-lyon1.fr) : TP
  • Jérémy LEVALLOIS (jeremy.levallois[AT]liris.cnrs.fr) : TP
  • Julien MILLE (julien.mille[AT]univ-lyon1.fr) : responsable d'UE , cours, TD, TP

(remplacer [AT] par @)

Prérequis

Ce qui suit est, à peu de choses près, une recopie de la page du semestre d'automne (site de Raphaëlle Chaine)

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

Cours

Cours 1 - Paradigmes de programmation, généricité, preuve d'algorithme [PDF]

  • Différence entre pointeur et référence
  • Retour sur les principaux paradigmes de programmation
  • ... et conclusions à en tirer pour une programmation saine en C ou C/C++
  • 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
  • Problèmes faciles et difficiles
  • Classe P, NP et NP-complet
Cours 2 - Preuve d'algorithme récursif, tri par partition (quick-sort), dérécursification, TAD Séquence (ou Liste) et Ensemble, table de hachage [PDF]

  • Preuve des algorithmes récursifs vs. itératifs
  • Equation de récurrence
  • Théorème concernant l'analyse des algorithmes "diviser pour régner" (divide and conquer)
  • Tri par partition (quick-sort)
  • 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
  • Retour sur le Type Abstrait Séquence et ses différentes implantations possibles
  • Type Abstrait Ensemble
  • Notion de clé et Type Abstrait Table
  • Fonction de hachage

Cours 3 - Tables de hachage, arbres binaires [PDF]

  • Notion de clé et Type Abstrait Table
  • Fonction de hachage
  • Gestion des collisions
  • Adressage ouvert et fermé
  • Re-hachage
  • Rappels sur les arbres binaires

Cours 4 - Arbres binaires, arbres binaires de recherche, arbres auto-équilibrants [PDF]

  • Rappels sur les arbres binaires
  • Dérécursification du parcours en profondeur d'un Arbre Binaire
  • Analyseur syntaxique
  • Recherche, insertion et suppression dans les ABR
  • Arbres auto-équilibrants : arbres AVL
  • Ré-équilibrage par rotation

Cours 5 - Arbres 2-3-4, tas binaires, graphes, parcours [PDF]

  • Arbres 2-3-4
  • Tas binaires
  • Graphes orientés vs. non orientés
  • Terminologie (chaînes, circuits, degré, etc.)
  • Matrice d'adjacence, liste d'adjacence
  • Parcours en largeur
  • Parcours en profondeur

TP

TP 1 - Listes chainées [PDF]

TP 2 - Généricité [PDF]

  • Module Elément générique
  • Module Liste générique

TP 3 - Généricité (suite)

  • Implantez un algorithme de tri de votre choix sur votre liste chainée générique (les éléments manipulés doivent disposer d'une fonction de comparaison)
  • Implantez une liste chainée générique triée sans doublon. Dans cette liste, l'ordre des éléments doit être maintenu au fur et à mesure des ajouts et des suppressions (il n'y aura donc plus de procédure AjoutEnTete et AjoutEnQueue, mais une unique procédure Ajout, qui devra insérer l'élément au bon endroit, seulement s'il n'est pas présent dans la liste)

TP 4 - Skip-lists [PDF]

  • Structure de donnée
  • Recherche optimisée
  • Insertion optimisée

TP 5 - Arbres n-aires, expressions arithmétiques [PDF]

  • Votre module Arbre devra pouvoir être testé avec main.c (pour la version C pur) ou main.cpp (pour la version C/C++ avec passage par référence)
  • Date limite de rendu sur SPIRAL : lundi 30 mars à 23h00