Progression du cours d'ALGO.  S5 2016-2017.

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


Cours 1 (24 oct.)

[ABCIP] QCM
[ABCI ] Infos pratiques:
[ABCI ]   https://www.lrde.epita.fr/~adl/ens/algo/
[ABCI ]   adl@lrde.epita.fr  (poser les questions pendant le cours!)
[ABCI ]   organisation de l'atelier
[ABCIP] Sommes de suites arithmétiques
[ABCI ] Calcul du nombre d'itérations de boucles imbriquées
[ BCI ]   garder des sommes croissantes et des termes positifs
[ABCI ]   faire des changements de variable pour avoir un incrément de 1
[ABCIP]   parties entières
[ABCIP] Tri par selection
[ABCIP] Nombre de comparaisons du tri par selection
[   IP] Tri par insertion
[   IP] Nombre de comp. du tri par insertion (meilleur et pire cas)

Cours 2 (31 oct.)

[ABC P] Tri par insertion
[ABC P] Nombre de comp. du tri par insertion (meilleur et pire cas)
[ABCIP] Notations O,Ω,Θ, intuition et definition formelle
[ABCIP] Lien entre O,Ω,Θ,o,ω et la limite de g(n)/f(n) qd n→∞
[ABCIP] Algorithmes Merge et MergeSort
[ABCIP] Complexité de Merge
[ABCIP] Définition récursive de la complexité de MergeSort
[   I ] Résolution graphique de T(n)=2T(N/2)+θ(n)
[ABCI ] Il existe deux ints tels que x==-x (pour le TP du jour)

Cours 3 (2 nov.)

[ABC  ] Résolution graphique de T(n)=2T(N/2)+θ(n)
[ABCI ] Résolution de T(n)=2T(N/2)+θ(n) par substitutions
[ABCIP] Théorème général
[ABCIP]   Examples d'applications du théorème général
[ABCI ]   Cas où le théorème général ne marche pas
[   IP]   Intuitions sur les trois cas du théorème (Fig. 47-49 du poly)
[ABCIP] Arbres parfaits
[ABCIP] Tas
[ABCIP]   Extraction de la racine ("max") d'un tas
[ABCIP]   Suppression de la racine et correction du tas (graphiquement)
[ABC P]   Construction d'un tas
[ABC P]   Heapify

Cours 4 (3 nov.)

[   IP]   Construction d'un tas
[   IP]   Heapify
[ABC P] Complexité de Heapify
[ABCIP] Complexité BuildHeap (à la louche, puis précise)
[ABCIP] Complexité de HeapSort
[ABCIP] QuickSort
[ABCIP]   Partition avec première valeur comme pivot
[ABCIP]   Complexité de Partition
[ABCIP]   Complexité de QuickSort dans le meilleur cas  (n/2,n/2)
[ABCIP]   Complexité de QuickSort dans le pire cas      (1,n-1)
[ABC P]   Complexité de QuickSort dans un cas favorable (10%,90%)

Cours 5 (4 nov.)

[ABCIP] Borner une somme par des intégrales: somme des carrés et somme de 1/i
[   IP]   Complexité de QuickSort dans un cas favorable (10%,90%)
[ABCIP] Complexité moyenne de QuickSort
[ABCIP] Choix du pivot
[ABCIP] Optimisations de QuickSort:
[ABCIP]   Derécursiver un appel de QuickSort
[ABCIP]   Récursion du plus petit côté
[ABCIP]   Appel d'InsertionSort() pour les petits tableaux
[ABCIP]   Complexité spatiale de QuickSort (évoquée seulement)
[ABCI ] Tri introspectif
[ABC  ] Notion de rang / algo naïf de la recherche de la valeur de rang k

Cours 6 (7 nov.)

[ABCI ]  QCM #2
[ABCI ]  Review de code TP#1.

Cours 7 (14 nov. [ABC], 15 nov. [I])

[ABCI ] Preuve de complexité par recurrence
[ABCI ] QuickSelect
[ABCI ] algorithme de la "médiane des médianes"

Cours 8 (18 nov.)

[ABCI ] Borne inférieur du pire cas des tris comparatifs
[ABCI ] Résumé de tous les tris vus jusqu'à présent
[ABCI ]   + Complexité spatiale
[ABCI ]   + Tri en place / Tri stable
[  CI ] CountingSort

Cours 9 (21 nov. [ABC], 22 nov. [I])

[AB   ] CountingSort
[ABCI ] Radix Sort LSD
[ABCI ] Radix Sort MSD
[ABCI ]   Binary Quick Sort
[ABCI ] Bucket Sort
[ABCI ]   average case of Bucket Sort
[ABCI ] Insertion into dynamic arrays
[ABCI ]   amortized complexity

Cours 10 (5 déc. [ABC])

[ABC  ] Multiplication de polynômes
[ABC  ]   algorithme naïf en θ(n²)
[ABC  ]   lien avec la multiplication des (grands) nombres
[ABC  ]   algorithme de Karastuba en θ(n^log₂(3))
[ABC  ]   représentation des polynômes par racines
[ABC  ]   représentation des polynômes par valeurs
[ABC  ]   (intuition) FFT en θ(n log n)

Cours 11 (9 déc. [ABCI])

[ABCI ] Distance de Levenstein
[ABCI ]   Définition recursive
[ABCI ]   Implémentation naïve
[ABCI ]   Memoization
[ABCI ]   Implémentation itérative]
[  CI ] Problème de la chaîne de multiplication de matrices (intro)
[  C P]   Nombres de Catalan.

Cours 12 (12 déc. [ABC], 13 déc [I])

[AB   ] Problème de la chaîne de multiplication de matrices (intro)
[AB IP]   Nombres de Catalan.
[ABCI ]   Définition recursive du nombre de mult. scalaires minimal
[ABCI ]   Calcul sur un exemple
[ABCI ]   Complexité de la solution
[ABCI ] Définition de la programmation dynamique
[  C  ] Problème de la loutre (poissons et sac à dos)

Cours 13 (13 déc [I], 16 déc [ABC])

[AB I ] Problème de la loutre (poissons et sac à dos)
[ABCI ] Combinaisons de pieces (coin_combo du TP5 de l'atelier)
[ABCI ] Résumé du semestre