Courses/AlgoLog2010Ing

From LRDE

Revision as of 13:50, 9 June 2014 by Clément Démoulins (talk | contribs) (Add Algo logs)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

2010-09-27 et 28 (3h)

  • Présentation
  • Introduction des mesures de complexité (temps, espace)
  • Problème de l'arrêt
  • Classes de complexité des problèmes (e.g. langages rationnels => S(n)=O(1))
  • Tri par insertion
  • cas favorable, défavorable, moyen
  • Notations \Theta, \Omega, O
  • comparaisons des fonctions
  • calculs de complexité avec les notations \Theta et O
  • Propriétés (sauf preuves avec limites) et petits exercices de manipulation
  • Tri par sélection
  • Définition de tri stable et en place seulement avec le groupe du lundi.

2010-10-04 et 05 (3h) QCM

  • Lien entre \Theta, \Omega, O et les limites des rapports des fonctions
  • Tri Fusion
  • Définition récursive de la complexité d'un algorithme récursif
  • Résolution d'une telle équation avec trois méthodes:
    • Méthode par itération de la définition
    • Méthode graphique
    • Théorème général (et applications sur plusieurs exemples)
  • Relations entre le nombre de noeuds, de feuilles, et la hauteur d'un arbre (nécessaires pour établir les complexités du Tri Fusion et de Heapify).
  • Définition d'un arbre parfait, représentation par un tableau
  • Définition d'un tas
  • Heapify, BuildHeap: Algorithmes pour la construction d'un tas
  • HeapSort: Tri par tas
  • Calcul des complexités de tous ces algorithmes.

2010-10-11 et 2010-10-12 (2h) 4 groupes: A puis A1 le lundi, B puis B2 le mardi

(mardi, trop d'étudiants avec le groupe B2 à cause des grèves)

  • Algorithme Quick Sort
  • Algorithme Partition
  • Déroulement sur un exemple
  • Calcul de la complexité de Partition
  • Tentative de calcul de la complexité de QuickSort
    • étude du pire cas (tableau trié)
    • généralisation aux partition avec suppression d'un nombre constant d'éléments
    • étude du meilleur cas (tableau toujours coupé en deux)
    • généralisation aux partitions avec ratio fixé
    • étude (fastidieuse!) du cas moyen
  • Discussion sur le choix du pivot: [fait avec tous les groupes sauf groupe B1 de 11h à 13h mardi]
    • Pivot aléatoire
    • Médiane de trois valeurs
  • Implémentation de QuickSort dans la libc [fait uniquement avec le groupe A de 9h à 11h lundi, mais pas les trois autres groupes]
    • médiane de trois valeurs
    • dérécursivisation du second appel
    • choix de faire l'appel récursif sur la plus petite des deux partitions
    • utilisation d'un tris pas insertion pour un faible nombre de valeurs

2010-10-18 et 2010-10-19 (2h) 4 groupes: A1 puis A le lundi, B1 puis B le mardi

  • Implémentation de QuickSort dans la libc [sauf avec le groupe A qui l'avait déjà vu]
    • médiane de trois valeurs
    • dérécursivisation du second appel
    • choix de faire l'appel récursif sur la plus petite des deux partitions
    • utilisation d'un tris pas insertion pour un faible nombre de valeurs
  • Complexité en espace du QuickSort
    • Version non-optimisée avec pire cas linéaire et meilleur cas logarithmique
    • Version optimisée (dérécursivée) avec pire cas logarithmique et meilleur cas linéaire
  • Tri introspectif
  • Borne du pire cas d'un tri comparatif
  • Tris linéaires: [seulement avec groupe A1 et A]
    • Tri par dénombrement: exemple, algo, et analyse de sa complexité
    • Tri par paquets: example
    • Tri par paquets: algo et analyze de sa complexité [seulement avec groupe A]

2010-10-25 et 2010-10-26 (2h) 4 groupes: A puis A1 le lundi, B puis B1 le mardi QCM

Beaucoup top d'étudiants dans le groupe B1.

  • Tris linéaires:
    • Tri par dénombrement: exemple, algo, et analyse de sa complexité [sauf avec groupe A et A1]
    • Tri par paquets: example [sauf avec groupe A et A1]
    • Tri par paquets: algo et analyze de sa complexité [sauf avec groupe A]
  • Tableau récapitulatif de tous les tris présentés
  • Mélange d'un tableau [avec groupe A uniquement]
  • Problème de la sélection (sauf groupe B)
    • Sélection "aléatoire", similaire à quick sort
    • Application sur un exemple
    • Calcul de la complexité de l'algo (sauf groupes B1 et A1)


2010-11-02 et 2010-11-03 (2h) 4 groupes: B1 puis B le mardi, A puis A1 le mercredi

  • Problème de la sélection (sauf groupe A)
    • Sélection "aléatoire", similaire à quick sort (groupe B)
    • Application sur un exemple (groupe B)
    • Calcul de la complexité de l'algo (groupes B, B1 et A1)
    • Sélection linéaire
    • Preuves par récurrence
  • Complexité de différentes opérations sur structures de données de base (tableaux et listes, triés ou non) (sauf groupe B)
  • Tableaux dynamiques (sauf groupe B)

2010-11-08 et 2010-10-09 (2h) 4 groupes: A puis A1 le lundi, B puis B1 le mardi QCM

  • Complexité de différentes opérations sur structures de données de base (tableaux et listes, triés ou non) (groupe B)
  • Tableaux dynamiques (groupe B)
  • Pile, File, File à double entrée
  • Tableaux circulaires
  • Files de priorité
  • Table de hachage statique (gperf...)
  • Table de hachage dynamique avec résolution par chaînage
    • complexité moyenne de l'insertion (groupe B1 arrêté avant la discution sur m=O(n)).
    • implementation de la libc avec modulo n et choix de n premier loin d'une puissance de 2
  • Paradoxe des anniversaires (fin pour le groupe A1, sauté )
  • Addressage ouvert
    • Sondage linéaire (fin pour le groupe A)
    • Sondage quadratique
    • Double hachage (fin pour le groupe B)

2010-11-15 et 2010-11-16 (2h) 4 groupes A1 et A le lundi (à VJ), B1 puis B le mardi

  • Fin haschage avec chaînage (groupe B1)
  • Paradoxe des anniversaires (groupes A, B1)
  • Addressage ouvert (tous sauf groupe B)
    • Sondage linéaire
    • Sondage quadratique
    • Double hachage
  • Arbres binaires de recherches
    • Compléxité des opérations classiques sur les ABR
    • Ordres préfixe/infixe/suffixe
    • Rotations
  • Arbres Rouge et Noir (fin groupe A et B1)
  • Début des Skip Lists jusqu'au calcul de \Theta(\log n) pour une skip list à n niveaux (fin pour groupe A1 et B).

2010-11-22 et 2010-11-23 (2h) 4 groupes A puis A1 le lundi, B puis B1 le mardi

  • Skip Lists
  • Algos diviser pour régner
  • Ex: Multiplication de polynomes
    • algo basique en \Theta(n^2)
    • Karatsuba en O(n^1.59)
    • intuition FFT en \Theta(n\log n)