View source for Courses/AlgoLog2007

== 2007-10-02 ING1 Séance 1 (4h) ==

* Présentation, support (livre), et plan du cours

* Définition informelle d'algo (Pas d'exemple)
* Définition formelle
* Calculabilité pb de l'arrêt
* Restriction des Pb envisagés
* On veut une mesure de complexité indépendante...
* RAM

* Tri par insertion
* cas favorable, défavorable
* cas moyen
* on veut s'abstraire des constantes de la machine
* Notation \Theta
* simplification des calculs

* Bornes asymptotiques supérieures est inférieures
* Propriétés des limites
* Exercices sur les bornes

* Tableau de comparaison

* Arbres enracinés (version graphe)
* Arbre ordonné, arbre binaire
* propriétés d'arbres
* Arbre équilibrés + propriétés

* Tri fusion
* illustration
* explication de merge
* complexité et sa preuve par un arbre de récursion

* Théoreme général pour les équations de récurrence
* 4 exemples d'application

* Complexité d'un problème

== 2007-10-09 ING1 Séance 2 (4h) ==

* Plan partie deux
* Problème du tri, tri stable, tri instable
* Tri par séléction

* Arbre parfait, arbre parfaitement ordonné, et tas
* Opérations sur les indices
* Heapify
* Build-Heap
* complexité naïve du Build-Heap
* complexité plus précise de Build-Heap
* algo du tri par tas et sa complexité

* Tri rapide, introduction

* Tri rapide, algorithme
* exemple
* cas favorable, défavorable
* complexité moyenne (partition constante)
* complexité moyenne (partition bonne/mauvaise)
* calcul de la complexité moyenne
* Tri rapide stochastique
* Pivot median
* Conclusion sur le tri rapide

* Tri introspectif (intro, algo)

* Résumé des complexité.

== 2007-10-16 ING1 Séance 3 (4h -30min alerte incendie) ==

* Borne inférieure sur le tri comparatif.
* Tri par dénombrement
* Tri par paquets
* Rappels probabilistes
* Tri par paquets: étude probabiliste

* Recherche dichotomique
* Complexité de la recherche dichotomique
* Arbre de décision (et complexité) pour une recherche par comparaison

* Recherche du minimum
* Problème de la sélection
* Sélection stochastique
* Cas favorable, pire cas
* complexité moyenne donnée mais pas calculée

* explication d'une sélection en O(n).

* Mélange naïf
* Cas favorable, cas défavorable
* Étude du mélange naïf en moyenne
* Mélange plus mieux

== 2007-10-23 ING1 Séance 4 (4h -15min QCM) ==

* Types abstraits
* Représentations d'ensembles: séquences, tableaux associatifs
* Tableaux
* Tableaux dynamiques
* Listes
* Piles et files
* Tableaux circulaires
* Files non-bornées et tableaux circulaires
* Files de priorité
* Algorithme d'insertion dans un tas

* Tableaux associatifs
* Tables de hachage
* Injectivité de la fonction de hachage dans K ou F.

* Rareté des fonctions injectives
* GPerf
* Hachage avec chaînage (Hypothèse de hachage uniforme pas mentionnée)

* Hachage par division
* Hachage par multiplication
* Effet d'avalanche
* Hachage par shift/add sur les bits

* Adressage ouvert
* Méthodes de sondage pour adressage ouvert
* Complexité de l'adressage ouvert

* Arbre binaire de recherche. (Juste l'intro)

== 2007-10-30 ING1 Séance 5 (4h -15min QCM) ==

* Parcours préfixes, infixes, suffixes
* Insertion dans un arbre binaire de recherche
* Suppression dans un ABR
* Complexité des opérations sur les ABR

* Arbres rouge et noir
* Tailles des ARN
* Rotations
* Insertion dans un ARN, exemples, trois cas à gérer

* Algo d'insertion dans un ARN
* Suppression sans les détails
* Conclusion ARN

* Skip lists
* Exemple à deux niveaux
* Exemple à log n niveaux
* Algo d'insertion dans une skip list
* Coût de la recherche (sans démo)

* Résumé des complexités des structures de recherche

== 2007-11-06 ING1 Séance 6 (4h) ==

* Distance de Levenshtein (déf, exemple, algo, illustration)

* Principes programmation dynamique

* Multiplications de matrices: parenthésage
* Multiplications de matrices: exemple parenthésage
* Multiplications de matrices: solution bovine
* Multiplications de matrices: sous-structure optimale
* Multiplications de matrices: définition récursive
* Multiplications de matrices: résolution par tableau, exemple graphique

* Multiplications de matrices: algorithme

* Algorithmes gloutons
* Principe
* Rendu de monnaie
* Propriétés gloutonnes
* Problème de la loutre
* Problème de la loutre en Prog. Dyn

* Codage de Huffman

* un exo de révision (min/max avec lecture par paire) pour occuper les dernières minutes.