Devoir commun 2

Algorithmes avancés Sujet C

L'usage de la calculatrice n'est pas autorisé

Durée: 70 min

Exercice 1

Est-ce que l'ordre dans lequel sont donnés les éléments de l'échantillon a une influence sur le résultat de l'algorithme des k plus proches voisins ? Expliquer.

Est-ce que l'ordre dans lequel sont donnés les éléments de l'échantillon a une influence sur le résultat d'un algorithme glouton ? Expliquer.

Exercice 2

a. Indiquer pour chaque valeur de \(k\) la classe prédite par l'algorithme des \(k\) plus proches voisins pour le point étoilé sur la figure ci-dessous.

b. Pour \(k=3\), un objet peut-il se voir prédire la classe 3 ? Si oui, où devrait être cet objet ? Si non, pourquoi ?

Exercice 3 : Complexité

Quel est le nombre exact de comparaisons et d'échanges dans l'algorithme de tri par sélection, dans le pire des cas, sur un tableau de taille 4 ? et sur un tableau de taille 10 ?

Quand on passe d'un tableau de taille \(n\)  à un tableau de taille \(2n\), comment varie le nombre de comparaisons effectuées dans le pire des cas par le tri par sélection ou le tri par insertion ?

Exercice 4

Un trésor se trouve caché à des coordonnées entières \((x_1,y_1)\) entre 0 et 999. On dispose d'un capteur directionnel que l'on peut placer sur la grille en exécutant une fonction \(f(x,y)\)  qui retourne une paire \((\mathit{v_x},\mathit{v_y})\) telle que \(\mathit{v_x}\)  vaut \(1\) si \(x>x_1\) , \(-1\) si \(x<x_1\)  et 0 si \(x=x_1\) , et similairement pour \(\mathit{vy}\) avec \(y\)  et \(y_1\) .

Écrire un programme en Python qui adapte la recherche dichotomique pour trouver l'objet en un minimum d'appels à \(f\)  (il n'est donc pas question de faire deux recherches : une sur \(x\)  puis une sur \(y\) ).

Exercice 5

Un automobiliste part en vacances et doit parcourir un long trajet. Il prend la route avec le plein de carburant. Son véhicule peut parcourir une distance maximale de 530 kilomètres avec le plein. La route empruntée comporte \(n\)  stations services: \(\text S_0\) ,\(\text S_1\),\(\text S_2\),...\(,\text S_{n-1}\)rangées dans l'ordre rencontré pendant le parcours. La première est à une distance \(d_0\)  du départ, la deuxième est à une distance \(d_1\)  de la première etc. Le point d'arrivée est à une distance \(d_n\) de la dernière station.

Écrire un programme en Python qui donne le nombre minimal de stations dans lesquels l'automobiliste doit s'arrêter pour arriver à destination.