Courses/AlgoLog2009Ing

From LRDE

2009-09-28 & 2009-09-29 ING1 Séance 1 (3h)

  • Présentation
  • Introduction des mesures de complexité
  • Tri par insertion
  • cas favorable, défavorable, moyen
  • comparaisons des fonctions
  • Notations \Theta, \Omega, O
  • calculs de compléxité avec les notations \Theta et O
  • Petits exercices de manipulation

Je n'ai pas parlé des calculs simplifiés en ne comptant que les comparaisons. J'y reviendrai lors du prochain cours.

2009-10-05 & 2009-10-06 ING1 Séance 2 (3h) QCM

  • Tri par sélection
  • Tri fusion
  • Complexité du tri fusion, avec résolution graphique, sur un arbre.
  • Théorème général
  • Applications du théorème Général
  • Introduction du Tas (avec insertion et suppression de la racine)
  • Tri par tas naïf, en n'utilisant que des insertions et de suppressions

2009-10-19 & 2009-10-20 ING1 Séance 3 (3h) QCM

  • Tri par tas (avec Heapify)
  • Étude de complexité du tri par tas
  • Quick Sort
  • Complexité du pire cas
  • Complexité du meilleur cas
  • Complexité d'un cas favorable (10%-90%)
  • Étude du cas moyen
  • Dérécursivisation des fonctions
  • Discussion sur les optimisation du Quick Sort (pivot aléatoire, médiane de trois valeur, dérécursivisation de l'appel vers le plus gros sous-tableau, tri par insertion sur les petits tableaux).

2009-10-26 & 2009-10-27 ING1 Séance 4 (3h)

  • Tri introspectif
  • Complexité d'un problème
  • Borne sur les tris comparatifs
  • Tri linéaires: tri par dénombrement, tri par paquet
  • Sélection stochastique
  • Sélection linéaire

2009-11-02 & 2009-11-03 ING1 Séance 5 (3h)

  • Complexité des opérations sur les tableaux, listes simplement/doublement chaînées, triés ou non
  • Complexité des opérations sur les tableaux dynamiques (analyse amortie)
  • Pile, File, File à double entrée
  • Tableaux circulaires pour la représentation des files à double entrée
  • Files de priorités (avec un tas)
  • Tables de hachage
  • Fonctions de hachage parfaites
  • Résolution des collisions par chainage
  • Adressage ouvert

2009-11-09 & 2009-11-10 ING1 Séance 6 (3h)

  • Arbres binaires de recherche
  • Recherches, Parcours Infixes, Rotations
  • Arbres Rouge et Noir
  • Insertion
  • Complexité des opérations sur les arbres rouge et noir.
  • Skip List
  • Insertion et complexité en moyenne de l'insertion
  • Introduction des deux prochains cours: Algos diviser pour régner, Programmation dynamique, Algorithmes Gloutons.
  • Calcul de la complexité de la multiplication de deux polynômes représentés par coefficients (pour présenter Karatsuba la semaine prochaine).