Courses/AlgoLog2008Ing

From LRDE

Revision as of 17:21, 27 June 2014 by Adl (talk | contribs) (Adl moved page Courses/AlgoLog2011Ing to Courses/AlgoLog2008Ing)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

2008-10-10 ING1 Séance 1 (2h), Groupe B puis Groupe A

  • Présentation
  • Introduction des mesures de complexité
  • RAM (je n'ai pas parlé de machines de Turing au groupe B)
  • Problème de l'arrêt.
  • 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

Je n'ai pas parlé des calculs simplifiés en ne comptant que les comparaisons. J'y reviendrai lors du prochain cours.

2008-10-17 ING1 Séance 2 (2h), Groupe B puis Groupe A

  • Calcul simplifiés en ne comptant que les comparaisons.
  • Retour sur les notations \Theta, \Omega, O
  • Petits exercices de manipulation
  • Complexité d'un problème (au groupe B uniquement)
  • Définition d'un arbre enraciné (à partir d'un graphe)
  • Définition d'un arbre binaire, d'un arbre binaire équilibré
  • Propriétés sur les arbres

Puis rapidement...

  • Tri fusion
  • Complexité du tri fusion, avec résolution graphique, sur un arbre.

2008-10-20 ING1 Séance 3 (4h), Groupe A

2008-10-21 ING1 Séance 3 (4h), Groupe B

  • Retour sur le tri fusion et la résolution de sa complexité
  • Théorème général
  • Applications du théorème Général
  • Complexité d'un problème (au groupe A uniquement)
  • Tri par sélection
  • Arbres parfaits
  • Tas (insertion et suppression présentés graphiquement)
  • Heapify, Build-Heap
  • Heap-Sort
  • Tri rapide
  • Cas favorable
  • Cas défavorable
  • Déséquilibre 1:10 / 9:10
  • Complexité moyenne
  • Choix du pivot aléatoire
  • Pivot médian (oralement pour le groupe A)
  • Tri rapide de la libc
  • Tri introspectif

2008-10-24 ING1 Séance 4 (2h), Groupe B puis Groupe A

  • QCM
  • résumé des complexités des tris comparatifs présentés
  • borne inférieure pour les tris comparatifs
  • tri par dénombrement
  • tri par paquets
  • calcul de la complexité moyenne du tri par paquets

2008-10-31 ING1 Séance 5 (2h), Groupe B puis Groupe A

  • mélange de tableau, calcul du cas moyen sur l'algo naïf
  • recherche dichotomique
  • borne inférieure sur la recherche par comparaison
  • recherche du minimum
  • borne inférieur sur la recherche du minimum
  • sélection stochastique
  • cas favorable, défavorable, moyen

2008-11-07 ING1 Séance 6 (2h), Groupe B puis Groupe A

  • Tri par sélection en O(1)
  • QCM
  • 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é

2008-11-10 ING1 Séance 7 (2h), Groupe B puis Groupe A

  • Tables de hachage
  • Rareté des fonctions injectives
  • GPerf
  • Résolution des collisions avec chaînage
  • Résolution des collilsions par adressage ouvert (sondages linéaire, quadratique, double hachage)
  • Réallocation des tables de hachage
  • Complexité des accès
  • Arbre binaire de recherche
  • Parcours préfixe, infixe, suffixe

2008-11-28 ING1 Séance 8 (2h), Groupe A puis Groupe B

  • Insertion et suppression dans un arbre binaire de recherche
  • Complexité des opérations dans un ABR
  • Définition des arbres rouge et noir
  • Hauteur des arbres rouge et noir
  • Insertion dans un arbre rouge et noir
  • Définition des skip lists
  • Algorithme d'insertion dans une skip list
  • Complexité moyenne de l'insertion (au groupe B seulement)

2008-12-08 ING1 Séance 9 (2h), Groupe A puis Groupe B

  • Résumé des complexité sur les structures de recherche
  • Algorithmes diviser pour régner
  • Multiplication de polynômes "de l'école" en \Theta(n^2)
  • Multiplication de polynômes de Karatsuba en \Theta(n^{\log 3})
  • Distance de Levenstein
  • définition récursive
  • algorithme récursif, de complexité exponentielle
  • arbre des appels récursifs
  • tableau des distances des suffixes pour une complexité quadratique (au groupe B seulement)

2008-12-15 ING1 Séance 10 (2h), Groupe B puis Groupe A

  • Programmation dynamique
  • Distance de Levenstein par programmation dynamique
  • Chaîne de multiplication de matrices
  • Intro de la plus longue sous-séquence commune.

2009-01-05 ING1 Séance 11 (2h), Groupe A puis Groupe B

  • Plus longue sous-séquence commune.
  • Algorithmes gloutons.
  • Rendu de monnaie.
  • Problème de la loutre (avec ou sans couteau)
  • Codage de Huffman.

2009-01-12 ING1 Séance 12 (4h), Groupe A puis Groupe B

  • Algorithme d'exponentiation rapide.
  • Monoïdes, groupes
  • Cas des matrices, polynômes
  • Chaînes additives, additives/soustractives
  • Éléments simplifiables d'un monoïde

(2h)

  • Suite de Fibonacci
  • Calcul récursif
  • Programmation dynamique
  • Exponentiation rapide
  • Diagonalisation
  • Formule de Binet

(3h)

  • 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)