Courses/AlgoLog2008App

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)