Courses/AlgoLog2007

From LRDE

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.