Devoir commun 2

Algorithmes avancés Sujet B

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

Durée: 90 min

Exercice 1

Combien les tris par insertion et sélection effectuent (dans le pire des cas, sur un tableau de taille n, à une constante près) :

d'opérations;
d'échanges d'éléments du tableau;
de comparaisons.

Choisir les réponses parmi : \(\log (n)\) ; \(n\) ; \(n\times \log (n)\) ; \(n^2\) .

Exercice 2

Un tableau d'entiers \(p\) contient la population des 1000 principales villes chinoises dans le désordre. Sans utiliser la méthode sort, donner un programme en python qui retourne un tableau contenant les 10 plus grandes populations.

Exercice 3

Soit \(t\) un tableau contenant le nom des 100 000 produits en vente sur votre site web. Votre site web reçoit de nombreuses requêtes de clients entrant le nom d'un produit pour vérifier s'il est disponible.

a. Comment organiser \(t\) pour accélérer les requêtes ?

b. Combien de cases du tableau devront être lues dans le pire des cas pour répondre à une requête ?

Exercice 4

Les figures ci-dessous présentent 4 jeux de données, avec une couleur par classe. Pour chacun de ces 4 jeux, on suppose que l'on dispose d'un échantillon de données étiquetées de taille suffisante.

On utilise la méthode des k plus proches voisins pour classifier les données inconnues.

Classer les jeux de données par ordre croissant en fonction du taux d'erreur attendu.
Indiquer ce que prédit la méthode de classification des plus proches voisins pour l'objet x dans chacun des cas suivants :

a) \(x\) a un voisin à distance 2, de classe «a» et deux voisins à distances 2 et 4; un de classe «b» et l'autre de classe «a». \(k=3\)

b) Même question, si \(k=1\)

Est-ce qu'éliminer les doublons dans l'échantillon à une influence sur l'algorithme ?

Exercice 5

Décrire le problème du rendu de monnaie: entrées, objectif.

L'algorithme glouton est-il optimal ? Sous quelles conditions ?

Gardien de Musée

Un musée place des tableaux le long d'un corridor. Une liste \(t\) indique la distance de chaque tableau au début du corridor (on néglige la largeur des tableaux). Chaque gardien peut surveiller un intervalle de 5m de long.

Écrire un algorithme glouton qui prend \(t\) en entrée et renvoie le nombre minimal de gardiens nécessaire pour surveiller tous les tableaux. Par exemple 2 gardiens suffisent pour \([6,8,12.5,17]\).

Hill-Climbing

On considère un tableau de \(n\times n\) valeurs toutes distinctes.

Un robot initialement placé sur la case supérieure gauche (ici 3) peut évaluer les quatre cases voisines (si elles existent) de la case sur laquelle il se trouve (à gauche, à droite, en haut, en bas).

Il n'évalue donc pas les cases diagonales et ne s'y déplace pas.

Proposer un programme glouton qui garantit que le robot aboutit à un maximal local sur la grille sans revenir sur ses pas.

Ici le robot terminera sur la case 12.