-
Cours :
- Listes, dictionnaires et lecture de fichiers
(lundi matin) - Bonnes pratiques pour les projets
(lundi après-midi)- cours 2
transparents : pdf, html - planche de TD/TP 2 (pdf)
- cours 2
- Spécification et tests
(mardi matin) - Correction partielle
(mardi après-midi)- cours 4
transparents : pdf, html - planche de TD/TP 4 (pdf)
- cours 4
- Correction de tri, et complexité en mode débranché
(mercredi matin)- transparents : pdf
- planche de TD/TP 5 (pdf)
- Comparaison des complexités des tris
(mercredi après-midi) - Complexité d'algorithmes
(jeudi matin)- transparents : pdf
- planche de TD/TP 7 (pdf)
- Recherche d'un élément majoritaire dans un tableau
(jeudi après-midi) - Algorithmes gloutons
(vendredi matin)- cours 9
transparents : pdf, html - planche de TD/TP 9 (pdf)
- cours 9
- Algorithme des k plus proches voisins
(vendredi après-midi)- cours 10
transparents : pdf, html - planche de TD/TP 10 (pdf)
- cours 10
Recherche d’un élément majoritaire
Etant donnée une liste L
de n
éléments (avec répétitions), le problème de l’élément majoritaire consiste à déterminer si il existe un élément dont le nombre d’occurences est plus grand que n/2
.
Algorithme Naïf
Décrire un algorithme qui recense les éléments distincts et qui calcule pour chacun d’eux son nombre d’occurences.
Quelle est la complexité de cet algorithme ?
Diviser pour régner
On divise la liste L
en deux sous-listes L1
et L2
de même taille (à une unité près).
Montrer qu’un élément qui n’est majoritaire ni dans L1
ni dans L2
ne peut pas être majoritaire dans L
.
En déduire un algorithme pour le calcul d’un élément majoritaire.
Montrer que la complexité de cet algorithme est O(n log n)
.
Algorithme optimal
Nous allons montrer que l’algorithme suivant permet de résoudre le problème avec une complexité optimale.
Pour mieux voir les choses, supposons que l’on ait à déterminer s’il existe une couleur majoritaire parmi n
balles colorées contenues dans un sac.
On dispose d’une étagère pour poser les balles les unes à côté des autres et d’une corbeille pouvant contenir autant de balles que nécessaire.
Description de l’algorithme
L’algorithme se décompose en deux phases :
Prendre une balle
b
dans le sac. Si la dernière balle posée sur l’étagère est de la même couleur queb
, placerb
dans la corbeille. Sinon, placerb
sur l’étagère. Dans ce dernier cas, si la corbeille est non-vide, prendre une balle dans la corbeille et la placer à côté deb
sur l’étagère. Répéter cette opération tant que le sac est non vide.Soit
c
la couleur de la dernière balle poséee sur l’étagère. Remettre toutes les balles dans le sac tout en calculant le nombrem
de balles de couleurc
. Sim > n/2
alorsc
est majoritaire sinon il n’y a aucun élément majoritaire.
Preuve de correction
Montrer par récurrence sur le nombre d’itérations de la phase 1, qu’à la fin de chacune des itérations, toutes les balles de la corbeille sont de la même couleur que la dernière balle posée sur l’étagère.
Observer que deux balles placées consécutivement sur l’étagère n’ont pas la même couleur.
En déduire que seule la couleur de la dernière balle posée sur l’étagère peut être majoritaire.
Complexité
Analyser la complexité de cet algorithme.