Nouvelles

Réouverture en janvier 2015...

Intervenants

Par ordre alphabétique :

  • Julie DIGNE (julie.digne[AT]liris.cnrs.fr) : TD
  • Raphaëlle CHAINE (raphaelle.chaine[AT]univ-lyon1.fr) : TP
  • Jean-David GENEVAUX (jean-david.genevaux[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

  • 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

Cours 2 - Preuve d'algorithme, classes de complexité, tri par partition (quick-sort), dérécursification, TAD Séquence (ou Liste)

  • Problèmes faciles et difficiles
  • Classe P, NP et NP-complet
  • 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

Cours 3 - TAD Séquence/liste (suite), tables de hachage

  • 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
  • Gestion des collisions
  • Adressage ouvert et fermé
  • Re-hachage

Cours 4 - Arbres binaires, arbres binaires de recherche

  • 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

Cours 5 - Arbres auto-équilibrants, tas binaires, graphes

  • Arbres auto-équilibrants : arbres AVL
  • Ré-équilibrage par rotation
  • Arbres 2-3-4
  • Tas binaires
  • Graphes orientés vs. non orientés
  • Terminologie (chaînes, circuits, degré, etc.)

Cours 6 - Graphes (suite), parcours, plus court chemin

  • Matrice d'adjacence, liste d'adjacence
  • Parcours en largeur
  • Parcours en profondeur
  • Tri topologique
  • Plus court chemin : algorithme de Dijkstra

Cours 7 - Flot maximal, méthodes de conception

  • Problème de flot maximal
  • Algorithme de Ford-Fulkerson
  • Méthodes de conception
  • Programmation dynamique (exemple : triangulation minimale)
  • Mise en évidence d'une sous-structure optimale
  • Algorithmes gloutons

TP

TP 1 - Listes chainées

TP 2 - Généricité

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

TP 3 - Skip-lists

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

TP 4 - Arbres n-aires, expressions arithmétiques

TP 5 - Graphes, plus court chemin