X ENS Informatique Commune PSI PT 2005

(Durée : 2 heures)
L'utilisation des calculatrices n'est pas autorisée pour cette épreuve.
Le langage de programmation choisi par le candidat doit être spécifié en tête de la copie.

On attachera une grande importance à la concision, à la clarté, et à la précision de la rédaction. On précisera en tête de copie le langage de programmation utilisé.

Le temps d'exécution d'une fonction est le nombre d'opérations élémentaires (addition, soustraction, multiplication, division, affectation, etc.) nécessaire au calcul de . Lorsque ce temps d'exécution dépend d'un paramètre , il sera noté . On dit que la fonction s'exécute :

Le problème consiste à faire le décompte du résultat des élections dans le pays . La règle électorale y est très laxiste, puisqu'on peut être élu sans s'être présenté. Plus prosaïquement, chaque votant vote pour , où est un entier positif quelconque (les habitants du pays sont identifiés par un entier représentant leur numéro de sécurité sociale).

Dans le pays , seul le candidat ayant obtenu strictement plus de des voix exprimées est élu au premier tour des élections.

Question 1 Écrire la fonction gagnant_tour1 qui retourne le gagnant du premier tour s'il existe. S'il n'existe pas, on retournera -1 . On se contentera d'une fonction faisant le calcul en temps quadratique par rapport à .

Question 2 Supposons le tableau trié en ordre croissant, vérifiant . Écrire une fonction gagnant_tour1_bis qui retourne le gagnant du premier tour en temps linéaire par rapport à .

Question 3 Si on sait trier un tableau de taille en temps , quel est l'ordre de grandeur du temps pris par le dépouillement du premier tour?

Au deuxième tour des élections, le candidat ayant obtenu le plus de voix est élu. Si égalité de voix, tous les candidats ayant obtenu le plus de voix sont élus (ex aequo).

Question 4 Écrire la fonction gagnants_tour2 qui imprime le(s) gagnant(s) du deuxième tour. On se contentera d'une fonction faisant le calcul en temps quadratique par rapport à (attention : on n'imprimera qu'une seule fois les noms des gagnants).

Question 5 On suppose maintenant le tableau trié en ordre croissant. Écrire une fonction gagnants_tour2_bis qui imprime le(s) gagnant(s) du deuxième tour en temps linéaire par rapport à .

Question 6 Si on sait trier un tableau de taille en temps , quel est l'ordre de grandeur du temps pris par le dépouillement du deuxième tour?

On suppose à nouveau le tableau non trié.
Un multi-ensemble d'éléments de est un ensemble où on autorise chaque élément à apparaître plusieurs fois (formellement, est une fonction de dans où est le nombre d'occurrences de dans . Par exemple, est un multi-ensemble. On dit que est un élément majoritaire dans contenant éléments si apparaît strictement plus que fois dans . Le gagnant du premier tour est donc l'élément majoritaire (s'il existe) dans le multi-ensemble . Dans ce dernier cas, on dira plus simplement que est majoritaire dans le tableau .

Question 7 Démontrer que si est majoritaire dans et que et sont deux éléments distincts de , alors est majoritaire dans le multi-ensemble obtenu en retirant de les éléments et .

Question 8 Démontrer que si est majoritaire dans et qu'il n'existe pas d'élément majoritaire dans les premiers éléments de , alors est majoritaire dans .

Question 9 En déduire la fonction gagnant_tour1_ter qui retourne le gagnant du premier tour en temps linéaire par rapport à .
Indication : faire deux passes sur le tableau ; dans la première passe, on cherche un candidat majoritaire; dans la deuxième passe, on vérifie qu'il est bien majoritaire.