Progression du cours d'ALGO.  S1 2014-2015.

Signification des marques:
A = Groupe A
B = Groupe B
I = Section Internationale
P = notion discutée dans le poly (algo.pdf)


Cours 1  (22 oct. [I], 27 oct. [AB])

[ABI ] Infos pratiques:
[ABI ]   https://www.lrde.epita.fr/~adl/ens/algo/
[ABI ]   adl@lrde.epita.fr  (poser les questions pendant le cours!)
[ABI ]   organisation de l'atelier
[ABIP] QCM
[ABIP] Sommes de suites arithmétiques
[ABIP] Sommes de puissances de 2
[ABI ] Calcul du nombre d'itérations de boucles imbriquées
[ABI ]   garder des sommes croissantes
[ABI ]   faire des changements de variable pour avoir un incrément de 1
[ABIP]   parties entières
[A  P]   n≤x ⇔ n≤⌊x⌋   et   n<x ⇔ n<⌈x⌉
[AB  ]   faire sauter la partie entière par majoration
[ABIP] Tri par selection
[ABIP] Nombre de comparaisons du tri par selection
[ABIP] Tri par insertion
[ABIP] Nombre de comp. du tri par insertion (meilleur et pire cas, cas moyen)
[  IP] Bestiaire des complexités

Cours 2 (3 nov. [ABI])

[ABIP] Rappels nombre de comp. tri par selection et insertion
[ABIP] Notations O,Ω,Θ, intuition et definition formelle
[ABIP] Lien entre O,Ω,Θ,o,ω et la limite de g(n)/f(n) qd n→∞
[ABIP] Algorithmes Merge et MergeSort
[ABIP] Complexité de Merge
[ABIP] Définition récursive de la complexité de MergeSort
[ABI ] Complexité de MergeSort si n=2^m, par substitutions
[ABIP] Complexité de MergeSort si n=2^m, en divisant par 2^m
[AB P] Bestiaire des complexités
[A I ] Il existe deux ints tels que x==-x (pour le TP du jour)

Cours 3 (4 nov. [ABI])

[ABI ] Discussion sur T(1)=Θ(1)
[ABI ] Résolution graphique de T(n)=2T(n/2)+Θ(n)
[ABIP] Théorème général
[ABIP]   Example d'applications du théorème général
[ABI ]   Explication intuitive du théorème général
[ABI ]   Cas où le théorème général ne marche pas
[ABI ] Arbres parfaits
[ABI ] Tas
[ABI ]   Extraction de la racine ("max") d'un tas
[ABI ]   Heapify
[ABI ]   Complexité de Heapify et de ExtractMax
[ABI ]   BuildHeap
[ABI ]   Borne supérieure (à la louche) de la complexité de BuildHeap

Cours 4 (5 nov. [ABI])

[ABI ] Calculer une interpolation linéaire (explication du TP de la veille)
[ABI ] Complexité précise de BuildHeap
[ABI ] Implémentation et complexité de HeapSort
[ABI ] QuickSort
[ABI ]   Partition avec première valeur comme pivot
[ABI ]   Complexité de Partition
[ABI ]   Complexité de QuickSort dans le meilleur cas  (n/2,n/2)
[ABI ]   Complexité de QuickSort dans le pire cas      (1,n-1)
[ABI ]   Complexité de QuickSort dans un cas favorable (10%,90%)
[ABI ] Discussion sur perf. de QuickSort/HeapSort/MergeSort vis à vis du cache

Cours 5 (6 nov. [ABI])

[ABIP] Borner une somme par des intégrales: somme des carrés et somme de 1/i
[ABI ] Complexité moyenne de QuickSort
[ABI ] Choix du pivot
[ABI ] Optimisations de QuickSort:
[ABI ]   Derécursiver QuickSort
[ABI ]   Récursion du plus petit côté
[ABI ]   Appel d'InsertionSort() pour les petits tableaux
[ABI ]   Complexité spatiale de QuickSort
[ABI ] Tri introspectif

Cours 6 (7 nov. [ABI])

[ABI ] Correction début TP1
[ABI ]   Discussions autour d'implémentations de int_width()
[ABI ]   Optimisation de int_width()
[ABI ]   ints_width() et print_int_array()
[ABI ] QuickSelect
[ABI ]   meilleur cas
[ABI ]   pire cas
[ABI ]   début de l'étude du cas moyen

Cours 7 (10 nov. [AB], 14 nov. [I])

[ABI ] QCM sur les cours précédents
[ABI ] Preuve de complexité par récurrence
[  I ]   Cas où il faut ajuster l'hypothèse de récurrence
[ABI ] Cas moyen de QuickSelect
[ABI ] Selection Linéaire
[ABI ] Borne inférieure sur la complexité des tris comparatifs

Cours 8 (17 nov. [AB], 20 nov. [I])

[ABI ] Tris stables, Tris en place
[ABI ] Rappels des complexités (temps/espace) des tris vus jusqu'à présent
[ABI ] Counting Sort
[ABI ] Radix Sort (LSB & MSB)
[ABI ] Bucket Sort

Cours 9 (24 nov. [AB], 27 nov. [I])

[ABI ] Complexités des opérations sur tableaux et listes
[ABI ] Complexité amortie: application aux tableaux dynamiques
[ABI ] Arbre binaire de recherche & Rotations
[ABI ] Insertion dans un arbre rouge et noir

Cours 10 (8 dec. [AB], 11 dec. [I])

[ABI ] Hachage parfait
[A   ]   probabilité de générer une fonction injective aléatoirement
[ABI ] gperf
[ABI ] Hachage avec résolution des colisions par chaînage
[ABI ]   nécéssité de réallouer pour maintenir des complexités en Θ(1) amorti
[ABI ] Adressage linéaire
[ABI ]   nécéssité de réallouer pour maintenir des complexités en Θ(1) amorti
[ABI ] Distance de Levenshtein
[ABI ]   définition récursive
[ABI ]   algorithme récursif de complexité O(3^n)
[AB  ]   preuve de complexité en O(3^n)
[ABI ]   intro de la mémoization pour améliorer les temps
[  I ]   écriture de l'algo avec mémoization

Cours 11 (15 dec. [AB], 18 dec. [I])

[ABI ] Distance de Levenshtein (suite)
[ABI ]   algo récursif avec mémoization
[ABI ]   version itérative
[ABI ]   récupérer les opérations correspondant à la solution
[ABI ]   lien avec diff et la correction orthographique (eg. zsh)
[ABI ] Chaînes de multiplications de matrices
[ABI ]   définition récursive
[ABI ]   approche bovine
[ABIP]   nombres de Catalan
[AB  ]   sous-structure optimale
[ABI ]   example avec 5 matrices
[ABI ]   récupération du parenthésage optimal

Cours 12 (18 dec. [AB], 19 dec. [I])

[ABI ] Le problème de la loutre
[ABI ]   algo récursif
[ABI ]   version itérative
[ABI ] Combinaisons de pièces
[ABI ]   définition récursive
[ABI ]   version itérative
[ABI ]   code C
[ABI ] Résumé du cours et de ses objectifs