TD 08 - Recherches

1 Échauffement

1.1 Exercice 1

Construire un tableau de 6 valeurs pour lequel quand je cherche si la valeur 1 est dans le tableau :

  1. l’algorithme de recherche séquentielle est le meilleur.
  2. l’algorithme de recherche séquentielle est le pire.
  3. l’algorithme de recherche dichotomique est le meilleur.
  4. l’algorithme de recherche dichotomique est le pire.
  • Recherche séquentielle meilleure : La valeur cherchée doit être en première position
  • Recherche séquentielle pire : La valeur n’est pas dans le tableau ou en dernière position
  • Recherche dichotomique meilleure : La valeur est au milieu du tableau trié
  • Recherche dichotomique pire : La valeur nécessite le maximum de divisions

2 Recherche séquentielle

2.1 Exercice 2

Écrire un algorithme qui cherche dans un tableau de \(n\) entiers, le premier et dernier indice d’une valeur et qui renvoie la somme de ces indices ou -1 dans le cas où il y a moins que deux occurrences.

Par exemple pour l’instance [2,0,-1,0,6,0,4,2], avec la valeur 0, qui apparaît à l’indice 2 en premier et 6 en dernier, on renvoie \(2+6=8\) ; mais pour la valeur 6, on renverra -1 car elle n’apparaît qu’une fois dans le tableau.

2.2 Exercice 3 🏠

On dispose d’un tableau de \(n\) entiers. On souhaite trouver un indice du tableau tel que la valeur correspondante soit plus grande que celles des cases voisines.

Par exemple pour l’instance [2,0,-1,7,6,5,4,2], les indices 1, 4 peuvent répondre au problème car \(T[1]=2\geq T[2]=0\) ; \(T[3]=-1 \leq T[4]=7\) et \(T[4]=7\geq T[5]=6\).

On peut montrer (bon exercice) qu’un tableau d’entiers contient toujours au moins une telle valeur (qu’on appellera un pic).

Écrire l’algorithme de recherche séquentielle qui trouve l’indice d’un pic du tableau.

NotePour les rapides

Écrire une version dichotomique en utilisant l’observation suivante : à l’indice milieu \(m\), si \(T[m-1] > T[m]\), alors le sous-tableau de \(g\) à \(m-1\) contient nécessairement un pic (éventuellement en \(g\)). De même, si \(T[m+1] > T[m]\), le sous-tableau de \(m+1\) à \(d\) contient nécessairement un pic (éventuellement en \(d\)). On peut ainsi éliminer une moitié du tableau à chaque étape.

2.3 Exercice 4 🏠

On dispose de deux tableaux de \(n\) entiers triés.

Écrire un algorithme en \(O(n)\) qui cherche et renvoie la première valeur commune aux deux tableaux. Si elle n’existe pas, l’algorithme renvoie -1.

3 Recherche dichotomique

3.1 Exercice 5

On considère un tableau de \(n\) éléments binaires (donc que des 0 ou des 1), trié dans l’ordre croissant. Par exemple l’instance [0,0,0,0,0,1,1].

Écrire l’algorithme qui retourne le nombre de 0 de ce tableau. Il faut que cet algorithme ait une complexité en \(O(\log(n))\).

3.2 Exercice 6 🏠 : Problème des téléphones

Le laboratoire Banana souhaite évaluer la résistance à la chute de plusieurs modèles de téléphones.

Le protocole est le suivant : on laisse tomber un téléphone d’une hauteur \(i\) mètres.

  • Si le téléphone se casse, alors on le jette.
  • Si le téléphone ne se casse pas, il reste utilisable pour d’autres tests.

L’objectif est de déterminer la hauteur maximale \(h\) (avec \(0 \leq h \leq n\)) telle que le téléphone supporte la chute d’une hauteur \(h\) mètres sans se casser.

  1. En supposant que l’on dispose d’un nombre illimité de téléphones identiques pour les tests (on peut donc perdre autant de téléphones cassés qu’on veut), proposer une méthode permettant de déterminer la hauteur maximale \(h\) en un minimum de tests.

    Quelle est la complexité en nombre de tests dans le pire cas ?

  2. Que faire si on ne dispose que d’un seul téléphone de test ? Proposer la meilleure stratégie possible et donner le nombre maximal de tests nécessaires dans ce cas.

  3. (Pour les rapides) Si on ne dispose que de deux téléphones pour effectuer ces tests, proposer une stratégie qui minimise le nombre maximal de tests au pire cas.

  4. Pour \(n=100\), combien de tests au pire dans chacun des cas suivants :

    • nombre illimité de téléphones,
    • un seul téléphone,
    • deux téléphones.
  • Illimité : Utiliser la recherche dichotomique
  • Un seul : Tester séquentiellement de 1 à n
  • Deux téléphones : Stratégie intermédiaire (sauts optimaux)