View source for Courses/AlgoLog2009Ing

== 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).