Courses/AlgoLog2008App

From LRDE

Revision as of 13:50, 9 June 2014 by Clément Démoulins (talk | contribs) (Add Algo logs)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

2008-10-09 APP1 Séance 1 (2h)

  • Présentation
  • Introduction des mesures de complexité
  • RAM
  • 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

Oublis à corriger dans le prochain cours :

  • parler du livre
  • plan des cours
  • calculs simplifiés en ne comptant que les comparaisons.

2008-10-16 APP1 Séance 2 (2h)

  • mention du livre et du plan de cours
  • calculs de complexité simplifiés en ne comptant que les comparaisons
  • Retour sur les notations \Theta, \Omega, O
  • Propriétés des limites
  • Exercices sur ces notations
  • Définition de la compexité d'un problème (en parler plus tard les prochaines années)
  • Arbres enracinés (version graphe)
  • Arbre ordonné, arbre binaire
  • propriétés des arbres binaires (mais pas celles des arbres en général)

2008-10-23 APP1 Séance 3 (2h)

  • propriétés des arbres binaires, complets, et équilibrés.
  • tri fusion
  • complexité du tri fusion
  • Théorème général
  • applications du théorème général
  • tri par sélection
  • introduction de la structure de tas
  • algorithmes d'insertion et de suppression dans un tas (présentés graphiquement, pas par écrit)

2008-11-13 APP1 Séance 4 (4h)

  • tri par tas
  • tri rapide
  • tri introspectif
  • borne inférieure sur les tris comparatifs

2008-11-20 APP1 Séance 5 (2h)

  • tri par dénombrement
  • tri par paquets
  • mélange de tableau

2008-11-27 APP1 Séance 6 (2h)

  • recherche dichotomique
  • borne inférieure de la recherche comparative
  • calcul du minimum
  • sélection stochastique
  • esquisse de l'algorithme de sélection en O(1) avec le median des medians

2008-12-04 APP1 Séance 7 (2h)

  • Type abstrait
  • Complexité des opérations sur les tableaux (triés ou non)
  • Coûts des tableaux dynamiques, complexités amorties
  • Complexité des opérations sur les listes (simplement chaînées, doublement chainées, triées ou non)
  • Pile, File, File à double entrée
  • Tableaux circulaire pour représenter les files à double entrées
  • Files de priorité
  • QCM
  • Introduction aux tables de hachage.

2008-12-11 APP1 Séance 8 (2h)

  • Hachage avec chaînage
  • Adressage ouvert (linéaire, quadratique, double hachage)
  • Effet d'avalanche
  • Réallocation des tables de hachage
  • Arbres binaires de recherche
  • Arbres Rouge & Noir
  • Skip Lists

2008-12-18 APP1 Séance 8 (2h)

  • Résumé des complexités des structures de recherche.
  • Algorithmes Diviser pour Régner
  • Karatsuba.
  • Intro Prog. Dyn
  • Distance de Levenstein

2009-01-08 APP1 Séance 9 (4h)

  • Fin distance de Levenstein.
  • Chaîne de multiplications de matrices
  • Plus longue sous séquence commune
  • Algorithme gloutons
  • Rendu de monnaie
  • Problème de la loutre (avec ou sans couteau)

2009-01-15 APP1 Séance 10 (4h)

  • Codage de Huffman
  • Exponentiation rapide
  • Monoïdes, groupes
  • Cas des matrices et des polynômes
  • Chaînes additives, additives/soustractives
  • Suite de fibonacci
  • Calcul récursif
  • Programmation dynamique

QCM (20min)

2009-01-22 APP1 Séance 11 (2h)

  • Suite de la suite de fibonacci...
  • Vision matricielle
  • Fibonacci avec exponentielle de matrices
  • Diagonalisation
  • Formule de Binet
  • Plus courts chemins
  • Algorithme en n^4
  • Algorithme en n^3 log n (exponentiation de matrices sur un autre semi-anneau)
  • Algorithme en n^3 (Floyd-Warshall)