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

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


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

[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
[ABI ] Calcul du nombre d'itérations de boucles imbriquées
[ BI ]   garder des sommes croissantes et des termes positifs
[ABI ]   faire des changements de variable pour avoir un incrément de 1
[ABIP]   parties entières
[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)


Cours 2  (26 oct. [ABI])

[A   ] complément boucles: garder des sommes croissantes et des termes positifs
[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
[  I ] Résolution graphique de T(n)=2T(N/2)+θ(n)
[  IP] Bestiaire des complexités
[AB  ] Il existe deux ints tels que x==-x (pour le TP du jour)


Cours 3 (27 oct. [ABI])

[ABI ] Discussion sur T(1)=Θ(1)
[AB  ] 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 ]   Cas où le théorème général ne marche pas
[ABIP] Arbres parfaits
[ABIP] Tas
[ABI ]   Extraction de la racine ("max") d'un tas
[ABIP]   Heapify
[ABIP]   BuildHeap
[ABIP]   HeapSort
[  IP]   Complexité de Heapify


Cours 4 (28 oct. [ABI])

[AB  ] Calculer une interpolation linéaire (explication du TP de la veille)
[AB P] Complexité de Heapify
[ABIP] Complexité BuildHeap (à la louche, puis précise)
[ABIP] Complexité de HeapSort
[ABIP] QuickSort
[ABIP]   Partition avec première valeur comme pivot
[ABIP]   Complexité de Partition
[ABIP]   Complexité de QuickSort dans le meilleur cas  (n/2,n/2)
[ABIP]   Complexité de QuickSort dans le pire cas      (1,n-1)
[  IP]   Complexité de QuickSort dans un cas favorable (10%,90%)


Cours 5 (29 oct. [ABI])

[AB P]   Complexité de QuickSort dans un cas favorable (10%,90%)
[ABIP] Complexité moyenne de QuickSort
[ABIP] Borner une somme par des intégrales: somme des carrés et somme de 1/i
[ABIP] Choix du pivot
[ABIP] Optimisations de QuickSort:
[ABIP]   Derécursiver QuickSort
[ABIP]   Récursion du plus petit côté
[ABIP]   Appel d'InsertionSort() pour les petits tableaux
[ABIP]   Complexité spatiale de QuickSort
[ABI ] Tri introspectif
[  I ] QuickSelect
[  I ]   Complexité du meilleur cas et du pire cas


Cours 6 (30 oct. [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()
[AB  ] QuickSelect
[AB  ]   Complexité du meilleur cas et du pire cas
[ABI ]   début de l'étude du cas moyen
[  I ]   preuve de la complexité moyenne par récurrence


Cours 7 (2 nov. [AB], 5 nov. [I])

[AB  ] preuves par récurrence de complexité recursives
[AB  ] preuve de la complexité moyenne de QuickSelect
[ABI ] LinearSelect et sa complexité
[ABI ] définition "tri stable" & "tri en place"
[ABI ] résumé des complexités de tris vus jusqu'à présent
[ABI ] calcul des complexités spatiales de ces tris
[  I ] CountingSort et sa complexité


Cours 8 (9 nov. [AB]; 12 nov [I])

[ABI ] CountingSort et sa complexité
[ABI ] Radix Sort (LSB & MSB)
[ABI ] Bucket Sort


Cours 9 (16 nov. [AB], 19 nov. [I])

[ABI ] Complexité amortie, application aux des tableaux dynamiques
[ABI ] Arbre binaire de recherche & Rotations
[ABI ] Insertion dans un arbre rouge et noir


Cours 10 (18 nov. [AB], 19 nov. [I])

[ABI ] Hachage parfait & 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 ] Multiplication de polynômes
[ABI ]   multiplication naive en ϴ(n²)
[ABI ]   Karatsuba en ϴ(n^{log_2(3)})
[ABI ]   FFT (mentionnée, mais non détaillée) en ϴ(n log n)


Cours 11 (7 dec. [AB], 11 dec. [I])

[ABI ] Distance de Levenstein
[ABI ]   définition récursive
[ABI ]   ajout d'un cache pour memoïsation
[ABI ]   définition itérative
[ABI ] Chaîne de multiplications de matrices
[ABIP]   dénombrement des parenthésages (nombres de Catalan)
[ABI ]   définition récursive du nombre de parenthésage minimum
[  I ]   exemple déroulé


Cours 12 (14 dec. [AB])

[AB  ] exemple déroulé pour la chaîne de mulitplications de matrices
[AB  ] problème de sac à dos (loutre + poissons)
[AB  ]   définition récursive
[AB  ]   version itérative
[AB  ] Combinaisons de pièces
[AB  ]   définition récursive
[AB  ]   version itérative
[AB  ]   code C
[AB  ] résumé du cours et de ses objectifs