A. Sigayret : Algorithmique

Exercices d'algorithmique : série 4

N.B. Rechercher sur Wikipedia (ou autre) les définitions inconnues nécessaires à la résolution des exercices.

Exercice 4.1.
a) Ecrire un algorithme qui donne la valeur maximale contenu dans un tableau de n lignes et p colonnes. Donner sa complexité.
b) Ecrire un algorithme qui donne la valeur médiane d'un tableau à trois dimensions n×p×q. Donner sa complexité.
c) Ecrire un algorithme qui cherche si une valeurs x appartient à un tableau de dimension n d1×...×dn. Donner sa complexité.

Exercice 4.2.
On veut trier un tableau T de n entiers naturels non nuls en le copiant dans un autre tableau U tel que, pour chaque élément e de T, U[e]=e, et pour i n'appartenant pas à T, U[i]=0.
a) Comment déterminer la taille de U ?
b) Ecrire un algorithme qui effectue ce transfert. Quel peut être sa complexité ?
c) Ecrire un algorithme qui copie les n valeurs utiles de U dans un tableau W de taille n.
d) Montrer que W réalise un tri par ordre croissant des valeurs de T.

Exercice 4.3.
a) Ecrire un algorithme qui place dans un tableau les n premières valeurs d'une suite arithmétique de premier terme U0 et de raison x.
b) Ecrire un algorithme qui copie les éléments d'un tableau de n lignes et p colonnes dans un tableau unidimensionnel de np valeurs.
c) Ecrire un algorithme qui copie les éléments d'un tableau unidimensionnel de n valeurs dans un tableau carré à deux dimensions.
d) Ecrire un algorithme qui décale vers la gauche de k positions les éléments d'un tableau à n éléments, les éléments du début étant perdus.
e) Ecrire un algorithme qui réalise une permutation circulaire de k positions vers la gauche dans un tableau à n éléments.
f) Ecrire un algorithme qui fusionne deux tableaux triés de tailles respectives n et p pour former un tableau trié de taille n+p.

Exercice 4.4.
La k-ième somme diagonale S(k) d'une matrice carrée M est définie par S(k)=&Sigmai+j=k M[i,j].
a) Pour la matrice Mo=((5;7;2);(4;1;7);(0-4;5)) quelles sont, si elles existent les valeurs de S(1), S(2), S(4), S(7) ?
b) Ecrire un algorithme calculant S(k) pour une valeur k et une matrice carrée M données. Evaluer la complexité en fonction de k.
c) Construire et prouver un algorithme récursif calculant la plus grande somme diagonale S(k) d'une matrice M de n×n éléments. Evaluer la complexité en fonction de n.

Exercice 4.5.
On propose différents algorithme de tri dans un tableau T de n éléments ordonnables.
algorithme Insertion : on échange si nécessaire les deux premiers éléments puis, à chaque étape, les k premières valeurs du tableau sont triées et on place le k+1-ième élément afin que les k+1 premières valeurs soient triées...
algorithme MinAmax : on place la valeur minimale de T en T[1] puis le minimum d T[2]−T[n] dans T[2], et ainsi de suite.
algorithme Bulle : on parcours le tableau en échangeant chaque élément de T avec son successeur s'il lui est supérieur. On recommence jusqu'à ce que le tableau soit trié.
algorithme Pivot : on choisit une valeur x de T comme référence et on place toutes les valeurs inférieures à x en début de T et les autres après. On répète l'opération sur les deux sous-tableaux, etc. Le tri est immédiat quand un sous-tableau contient au plus deux éléments.
N.B. L'algorithme est-il amélioré si on choisit pour x la valeur médiane du sous-tableau ? (ce tri est aussi appelé tri de Hoare ou tri rapide).
algorithme Dichotomie : on partage le tableau en deux sous-tableaux de taille égales (à 1 près) et on tri ces sous-tableaux de manière récursive. On fusionne les deux sous-tableaux triés pour former un tableau trié.
a) Pour chacun de ces algorithmes, écrire une version itérative et une version récursive.
b) Donner les preuves et la complexité.
N.B. On pourra rechercher d'autres méthodes de tri et écrire les algorithmes précisés correspondant.

Exercice 4.6.
On représente un sous-ensemble S d'un ensemble E de n éléments par un tableaux de booléens : S[i]=Vrai quand E[i] appartient à S.
Pour chacun des problèmes suivants, construire un algorithme et en donner la preuve et le complexité.
a) Ajout d'une valeur à S.
b) Suppression d'une valeur de S.
c) Tester l'appartenance d'une valeur à S.
d) Tester si S est vide.
e) Intersection de deux ensembles S1 et S2.
f) Union de deux ensembles S1 et S2.
g) Tester l'inclusion de S1 dans S2.

Exercice 4.7.
On représente une relation binaire R interne à un ensemble E à n éléments (càd R⊆E×sE) comme un tableau booléen M à deux dimensions tel que M[i,j]=Vrai ⇔ (i,j)∈R.
a) Ecrire des algorithmes qui testent respectivement si une relation est 
  – réflexive,
  – anti-réflexive,
  – symétrique,
  – anti-symétrique,
  – transitive,
  – une relation d'équivalence,
  – une relation d'ordre stricte.
b) Donner les preuves et les complexités de ces algorithmes.
c) Ecrire un algorithme qui calcule les classes d'équivalence d'une relation d'équivalence.

Exercice 4.8.
On veut tester la présence d'une valeur x dans un tableau T trié.
a) En quoi ce problème est-il similaire à la recherche d'un mot dans un dictionnaire ?
b) Montrer, en écrivant un algorithme correspondant et en le prouvant que ce problème est en O(lg(n)) où lg est le logarithme en base 2.
c) Quel peut être l'intérêt de cet algorithme pour la représentation d'un ensemble par un tableau booléen vu précédemment ?

Exercice 4.9.
Un caviste veut réorganiser ses bouteilles alignées dans un rayonnage. Ces bouteilles de vin blanc, de rosé, et de rouge ont été placées au hasard et il veut grouper séparément les rosés, puis les blancs et enfin les rouges. Quatre d'actions élémentaires sont à sa disposition : prendre une bouteille dans une case avec la main droite libre ou bien avec la main gauche libre, poser dans une case libre la bouteille qu'il tient dans sa main droite ou bien dans sa main gauche.
a) Ecrire un algorithme qui effectue le rangement des bouteilles. Remarque. on ne tient pas compte des déplacements du caviste le long du rayonnage..
b) Quelle est la complexité de votre algorithme .
N.B. Ce problème peut être résolu en temps linéaire. Il a été proposé et résolu par Dijkstra sous le nom de "Problème du drapeau hollandais".