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.