Q.C.M. Bilan Algorithme :

Que signifie qu'un algorithme à un ordre de complexité supérieur à un autre ?

Quel est le bon classement des ordres de complexité.

Un algorithme A est en \(\Theta(n)\) et un algorithme B est en \(\Theta(n^2)\) pour une taille n donnée ils ont la même vitesse, que va t'il se passer si on double la taille de la donnée ?

Les fonctions suivantes sont là pour déterminer si un tableau à deux éléments identiques, donner leurs ordre de grandeur (la fonction peut être faite après avoir vu la notion de dictionnaire) :

Pour faire une recherche dichotomique dans un tableau il faut :

On estime qu'il y a 2¹⁸⁴ atome dans l'univers, si on pouvait les ordonner et si on devait en retrouver un, alors par dichotomie en supposant qu'une étape prenne une seconde, on y arriverai en :

En reprenant l'exercice précédent mais en appliquant l'algorithme naif qui consiste essayer les atomes les uns après les autres alors il faut :

Si on double le nombre d’élément d'un tableau ordonnée alors pour trouver un élèment grace à la recherche dichotomique il faut :

Combien faut il d'étapes (c'est à dire de calcul de l'indice milieu) pour trouver 182 dans le tableau par recherche dichotomique ?

Au pire dans un tableau de 1576 élèment il faut combien d'étapes pour trouver (ou pas) un élèment ?

Cochez les bonnes réponses

Trier le tableau [4,1,3,5,2] par insertion demande exactement combien de comparaisons ?

Cocher les algorithmes qui permettent de trier par ordre croissant un tableau d'entiers :

Avec le tri par selection doubler la taille du tableau à trier va :

Si on souhaite trier le tableau [5,1,6,4,2] de facons croissante avec le tri par selection les différents changements à la fin de la première boucle seront :

Si on souhaite trier le tableau [5,1,6,4,2] de facons croissante avec le tri par insertion les différents changements à la fin de la première boucle seront :

On donne la table suivante

En utilisant l'algorithme glouton avec pour critère la ville la plus proche, pour le problème du voyageur de commerce commençant à Grenoble, donner la quatriéme ville visitée après Grenoble.

Pour rendre 175.59 euros en le moins de pièces-billets il faut en donner :

Sur l'image ci dessous des points de deux catégories (rouge et bleu) sont placés. Si on utilise l'algorithme des 3 plus proches voisins avec la distance euclidienne, donner les points qui seront dans la catégorie rouge (sans ambiguités) :