L'algorithme minmax utilise 3n/2-2 comparaisons pour trouver le minimum et maximum de n nombres (n pair).

1. Combien sont utilisées quand n est impair?
2. Pour l'algorithme plus naif qui compare chaque nombre après le deuxième avec le maximum des précédents et (s'il était inférieur au maximum) avec le minimum, le nombre de comparaisons dépend de l'ordre des données; Quels sont les nombres minimum et maximum de comparaisons?
3. On veut démontrer que tout algorithme basé sur les comparaisons doit utiliser au moins le même nombre que minmax. On va utiliser une méthode de l'adversaire : chaque fois que l'algorithme effectue une comparaison, l'adversaire donne une réponse qui est cohérente avec les réponses précédentes mais choisie afin d'obliger l'algorithme à prendre le maximum de temps; ici l'adversaire devrait essayer de garder le plus grand nombre possible d'éléments du tableau qui pourraient être le minimum et/ou le maximum.
   Donner une stratégie pour l'adversaire qui oblige tout algorithme à effectuer au moins le nombre de comparaisons de minmax.
   Conclure que tout algorithme nécessite ce nombre, au moins dans le pire cas.
4. Pour étudier le comportement d'un algorithme en moyenne, on peut supposer que tous les n! ordres possibles des n données ont la même probabilité; avec cette supposition, est-il vrai que tout algorithme doit faire autant de comparaisons que minmax en moyenne?

1. Expliquez pourquoi cette remarque est complètement stupide!
2. Un algorithme raisonnable utiliserait la méthode de Strassen pour les grandes matrices et basculerait sur la méthode simple pour les petites; si on ne compte que le temps des opérations de base (addition multiplication et soustraction des éléments des matrices) et que toutes ces opérations prennent le même temps, quel est le bon seuil entre les grandes et les petites matrices?