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