Progression du cours d'ALGO.  S5 2019-2020.

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


Cours 1.  2h  30 sept. - 4 oct.

[RSTI ] Infos pratiques:
[RSTIP]   https://www.lrde.epita.fr/~adl/ens/algo/
[RSTIP]   adl@lrde.epita.fr  (poser les questions pendant le cours!)
[RSTI ]   mention de l'atelier à venir et des groupes de TD
[RSTI ] Présentation du cours: donner des outils pour calculer les complexités
[RSTI ]   notion de problème et d'algorithme
[RSTIP] Rappels de maths:
[RSTIP]   utilisation des logs, calcul de log10(1234) à la main.
[RSTIP]   sommes de suites arithmétiques
[RSTIP]   sommes de suites géométriques
[RSTIP]   parties entières, en particulier n≤x ⇔ n≤⌊x⌋ et n<x ⇔ n<⌈x⌉
[RSTI ] Calcul du nombre d'itérations de boucles imbriquées
[RSTI ]   garder des sommes croissantes et des termes positifs
[RSTI ]   faire des changements de variable pour avoir un incrément de 1


Cours 2.  2h  14-18 oct.


[RSTI ] QCM sur les premières pages du poly et le cours 1.
[RSTIP] Tri par selection
[RSTIP]   Nombre d'exécution de chacune des lignes
[RSTIP]   Lien entre ces nombres et le temps d'exécution
[RSTIP] Tri par insertion
[RSTIP]   Nombre d'exécution de chacune des lignes
[RSTIP]   Meilleur cas, pire cas, cas moyen


Cours 3.  2h  21 oct.

[RSTIP] Notations O,Ω,Θ, intuition et definition formelle
[RSTIP] Algorithmes Merge et MergeSort
[RSTIP] Complexité de Merge
[RSTIP] Définition récursive de la complexité de MergeSort
[RSTI ] Résolution graphique de T(n)=2T(N/2)+θ(n)
[RSTIP] Bestiaire des complexités
[RS I ] Annonce pour les TPs de l'après-midi:
[RS I ]   Les sujets sont sur https://algo.lrde.epita.fr/


Pas fait:
[    P] Lien entre O,Ω,Θ,o,ω et la limite de g(n)/f(n) qd n→∞


Cours 4.  2h  22 oct.

[RSTI ] Résolution de T(n)=2T(N/2)+θ(n) par substitutions
[RSTIP] Théorème général
[RSTIP]   Examples d'applications du théorème général
[RSTI ]   Cas où le théorème général ne marche pas
[RSTIP]   Intuitions sur les trois cas du théorème
[RSTIP] Arbres parfaits
[RSTIP] Tas
[RSTIP]   Extraction de la racine ("max") d'un tas
[RSTIP]   Suppression de la racine et correction du tas (graphiquement)
[RSTIP]   Heapify, BuildHeap, HeapSort


Cours 5.  2h   23 oct.

[RSTIP] Tas (suite)
[RSTIP]   Complexité précise de BuildHeap
[RSTIP]   Complexité de HeapSort
[RSTIP] Borner une somme par des intégrales: somme des log₂(i)
[RSTIP] QuickSort
[RSTIP]   Partition avec première valeur comme pivot
[RSTIP]   Complexité de Partition
[RSTIP]   Complexité de QuickSort dans le meilleur cas  (n/2,n/2)
[RSTIP]   Complexité de QuickSort dans le pire cas      (1,n-1)
[RSTIP]   Complexité de QuickSort dans un cas favorable (10%,90%)


Cours 6.  2h   24 oct.

[RSTI ] Faire sauter la somme de T(n) = cn + Σ_{i=1}^{n-1} T(i)
        en calculant T(n) - T(n-1).
[RSTIP]   Complexité moyenne de QuickSort
[RSTIP]   Autre choix du pivot: random ou median-of-3
[RSTIP] Optimisations de QuickSort:
[RSTIP]   Derécursiver un appel de QuickSort
[RSTIP]   Récursion du plus petit côté
[RSTIP]   Appel d'InsertionSort() pour les petits tableaux
[RSTIP]   Complexité spatiale de QuickSort


Cours 7.  2h   25 oct.

[RSTIP] Tri introspectif
[RSTI ] Pire cas des tris comparatifs
[RSTIP] Tri en place et tri stable
[RSTI ] Counting sort
[RSTI ] Radix Sort LSD
[RSTI ] Radix Sort MSD
[RSTI ]   Binary Quick Sort


Cours 8.  2h  28-31 oct.

[RSTIP] Preuve de complexité par récurrence
[RSTIP] QuickSelect
[R   P] Sélection linéaire


Cours 9.  2h  4-8 nov.

[RSTI ] Distance de Levenstein
[RSTI ]   Définition recursive
[RSTI ]   Implémentation naïve
[RSTI ]   Complexité de l'implémentation naïve
[RSTI ]   Version avec cache (memoization)
[RSTI ]   Implémentation itérative
[RSTI ] Problème de la chaîne de multiplication de matrices (Intro)

Cours 10.  2h  14-18 nov.

[RSTI ] Problème de la chaîne de multiplication de matrices
[RSTIP]   Nombres de Catalan.
[RSTI ]   Définition récursive du nombre de mult. scalaires minimal
[RSTI ]   Calcul sur un exemple
[RSTI ]   Complexité de la solution
[RSTI ] Sous-structure optimale
[RSTI ] Problème de la loutre (poissons et sac à dos)

Cours 11.  2h  21-25 nov.

[RSTI ] Combinaisons de pieces (coin_combo du TP5 de l'atelier)
[RSTI ] Résumé du semestre