Nouvelles

  • 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

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)