Exercice 1. Écrire une procédure Min_Et_Max qui calcule le minimum et le maximum d'un vecteur. On veillera à faire le moins comparaisons possible.

Exercice 2. Écrire une fonction Fusion qui prend en arguments deux vecteurs supposés bien triés et qui renvoie le vecteur obtenu en faisant l'union ordonnée.

Exercice 3. Le triangle de Pascal permet de calculer les coefficients binomiaux. Mais son application nous concerne peu ici. Nous nous intéressons à sa construction, qui obéit aux règles suivantes. La première ligne du triangle est composée de deux éléments : 1 et 1. Pour tout n>1, la n^ième ligne comporte ensuite n+1 éléments, définis par:

le premier élément est 1,
pour tout i, 2 £ i £ n, le i^ième élément est la somme du i-1^ième et du i^ième élément de la ligne n-1,
le dernier élément est 1.

Ainsi, les quatre premières lignes du triangle de Pascal sont

Écrire une fonction Pascal qui prend en argument un entier positif n et rend comme résultat la n^ième ligne du triangle de Pascal.

Exercice 4. On dispose un vecteur T de taille n contenant tous les entiers de {0, ..., n}, sauf un. On veut déterminer quel est l'entier absent de T.

a. Donner un algorithme qui résoud le problème en temps linéaire, avec un espace mémoire annexe constant.

b. On suppose maintenant le tableau T est trié par valeur croissante. Montrer que le problème peut alors se résoudre par dichotomie. Quelle est alors la complexité ?

Exercice 5. Un élément est majoritaire dans un vecteur s'il représente strictement plus de 50% des éléments. On veut écrire une procédure qui détermine si un vecteur contient un élément majoritaire, et dans ce cas précise lequel. Il existe pour cela un algorithme linéaire, qui procède en construisant des vecteurs auxiliaires, de plus en plus petits et dans lesquels se trouve toujours l'élément majoritaire.