Résumé de section

  • Replier Déplier

    Généralités

    Tout replier Tout déplier
  • Replier Déplier

    Trame globale du cours

    Motivation de ce cours

    Ce cours n'existait pas dans le master d'informatique de Lyon 2 jusqu'en 2015. Il est apparu en 2016 en raison de nouvelles règles sur l'accréditation des mentions de master par le ministère de l'enseignement supérieur : sur un même site géographique, l'ensemble des établissements qui veulent délivrer une mention donnée, doivent co-accréditer cette mention. Pour nous, mention = "Informatique", site géographique = "Lyon / Saint-Etienne". 6 établissement délivrent (co-accréditent) le master Informatique. 16 parcours de M2 sont identifiés dans ces 6 établissements. Une autre règle veut que sur les 120 crédits ECTS qui constituent les 2 années de Master, tous les étudiants aient au moins 12 crédits "en commun". La manière dont les équipes pédagogiques des différents établissements du site ont mis en œuvre ces principes a été d'identifier 4 cours de 3 crédits qui doivent être suivis par l'ensemble des étudiants de l'ensemble des établissements. Le cours de complexité en fait partie (à Lyon, on ne peut pas délivrer le master de mention Informatique à un étudiant qui n'aurait pas suivi un cours de complexité) !

    Introduction

    • Définitions. Complexité en temps, en espace, sur des ordinateurs théoriques de modèle « RAM » [ il existe d’autres modèles, notamment pour les ordinateurs "parallèles" : PRAM (CRCW, CREW, …) ]
    • Méta langage algorithmique : affectation, conditionnelle, itération, fonction (récursivité)
    • Complexité élémentaire des constructions de base.

    Outils mathématiques :

    • Fonctions usuelles. Linéaire. Polynômes. Racine. Exponentielle. Logarithme.
    • Calculs de limites. 
    • Notations O(), Ω(), Θ() : Notation de Landau.
    • Complexité dans le pire des cas, [ dans le meilleur des cas, en moyenne ]
    • Algorithmes linéaires, quadratiques, polynomiaux, exponentiels, logarithmiques.
    • Exemples de la vie de tous les jours : longueur, surface, volume, grains de riz sur un échiquier, épaisseur d’une feuille pliée en 2, 4, 8…, nombre de tours de la dernière roue d’un compteur. Nombre de bits pour représenter un nombre. Temps pour rechercher un mot dans le dictionnaire.
    • Sommes usuelles (Somme des n premiers nombres, somme des n premiers carrés, somme des n premières puissances de x, …) 

    Exemples d’algorithmes et de calculs de complexité

    • Recherche d’un élément dans une liste (mal écrit : quadratique – amélioré : linéaire)
    • Recherche du plus grand, du plus petit
    • Recherche d’un élément dans une liste triée (dichotomie : log)
    • Algorithmes de tri
    • Tri par bulles
    • Tri par sélection
    • Tri par insertion
    • Parler de la récursivité. Donner des exemples : factorielle, Fibonacci
    • Tri fusion
    • Quicksort (parler du pire des cas)
    • Chronométrer l’exécution des algorithmes, vérifier la complexité expérimentalement. Tracer des courbes sous Excel.

    Paradigmes permettant d’estimer la compexité :

  • Replier Déplier

    Pour aller plus loin...

    Lire les chapitres 1, 2, 3, 4, 6, 7 de l'excellent ouvrage, "Introduction à l'algorithmique" [2ème édition] de Thomas Cormen, Charles Leiserson, Ronald Rivest, Clifford Stein, traduit en français par Xavier Cazin, Georges-Louis Kocher.

    Le SCD de Lyon 2 possède 5 exemplaires de la [3ème édition] de cet ouvrage, intitulée plus simplement "algorithmique".

  • Replier Déplier

    Pour vos révisions...