1 - Cours, Magistral, n°1 : Bonjour complexité·s !
- Complexité :
- Définition. intérêt.
- Complexité dans le cas le pire, le meilleur
- Complexité des algos récursifs (exemples : factorielle, coefficients binomiaux, tri par fusion)
- Complexité en moyenne (exemple du tri par insertion (simple) & de quicksort (un peu plus dur))
- Complexité minimales des pb (inversion de matrices en n^2, tri en n · log n, enveloppe convexe en n · log n)
- Introduction à la preuve de programmes ; exemple de l'algorithme d'Euclide.
- Présentation des Piles & Files d'Attente.