Annales de mathématiques approfondies

Sujet et corrigé ESSEC - Mathématiques II 1990 – remis au programme ECG

Adapté au nouveau programme ECG. Ce sujet de 1990 et son corrigé ont été retravaillés pour correspondre au programme en vigueur.

Thèmes du sujet

Complexité d'algorithmes de recherche du maximum et des deux plus grands éléments d'un tableau : étude de 1 + 1/2 + ⋯ + 1/n − ln n, nombre moyen de mises à jour sur une permutation aléatoire.

Plan du sujet

  1. Préliminaires : la suite 1+12+⋯+1n−ln⁡n1+\frac12+\cdots+\frac1n-\ln n
  2. Partie I : recherche du plus grand élément d'un tableau
  3. Partie II : recherche des deux plus grands éléments