Courses/AlgoLog2010Ing

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)