Skip to content

Séquence 1

L'objectif de la séquence est de positionner le concept d'algorithme dans le domaine scientifique de l'informatique et de montrer que son usage populaire peut être ambigü et source d'interprétations. On poura lire le chapitre 1 de l'ouvrage

Algorithmique par Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest et Clifford Stein Dunod 3ième édition 2010 lien des versions plus anciennes sont accessibles partiellement sur internet.

Question 1

Un algorithme peut être (réponse vrai/faux)

  1. intelligent
  2. légal
  3. correct
  4. efficace
  5. obsolète

réponses (éléments)

  1. Faux : un algorithme est un texte, il n'agit pas, ne réfléchit pas, celui qui a conçu l'algorithme par contre peut être intelligent, asctucieux,...
  2. Faux : de même que précédemment, un algorithme n'a pas de sens légal. Par contre son usage est soumis à la législation. Jusqu'à présent il n'y a pas de contrainte éthique ou juridique sur l'écriture des algorithmes.
  3. Vrai : Un algorithme est conçu pour résoudre un problème de traitement d'information, il est correct si pour toute entrée du problème l'algorithme associe la sortie attendue (spécifiée)
  4. Vrai : un algorithme est destiné à être traduit dans un langage de programmation puis à être exécuté sur une machine (informatique), même en supposant que le programme soit une bonne écriture de l'algorithme, que l'algorithme soit correct, la meilleure machine du monde ne pourra peut-être pas l'exécuter car trop d'opérations seraient nécessaires. Par exemple, un algorithme de tri d'éléments comparables consiste à "mélanger" les objets, tester s'ils sont dans l'ordre et recommencer jusqu'à ce qu'ils le soient. Vous pouvez faire le calcul du nombre moyen de tests nécessaires pour trier un tableau de 1000 éléments avec cette méthode.
  5. Faux : un algorithme écrit n'a pas de raison d'être obsolète ou d'avoir une "durée de vie". Par contre, au vu de l'évolution des machines il peut présenter moins d'intérêt car moins adapté aux contraintes matérielles (par exemples certains algorithmes de tris ont été conçus pour travailler sur des données sur bande magnétiques et la lecture/écriture des données était très coûteuse.

Question 2

Sur la page Wikipedia Recherche dichotomique d'un élément dans une structures. Plusieurs présentations sont proposées.

  1. Le problème est bien spécifié (c'est à dire que l'on connaît l'association entre l'entrée et la sorie de l'algorithme
  2. l'algorithme est exprimé dans plusieurs versions
  3. l'algorithme est prouvé
  4. l'algorithme est montré efficace
  5. la présentation de la version en anglais de la page lien a une autre forme de présentation

réponses (éléments)

  1. Faux : les entrées du problème ne sont pas suffisemment détaillées. les éléments doivent-ils être comparables 2 à 2, le type des éléments est entier alors que rien ne le précise, l'élément doit-il être dans le tableau, peut-il y avoir plusieurs fois le même élément ?
  2. Vrai : une version de l'algorithme en langage naturel, une version récursive et une version itérative.
  3. Faux : l'algorithme n'est pas formellement prouvé, (la spécification n'étant pas formelle)
  4. Faux : on a calculé la complexité, de manière approximative car les hypothèses sur les données d'ntrée ne sont pas fournie. On en déduit une complexité de l'ordre de O(log(n)) mais ne montre pas que l'on ne peut pas faire mieux
  5. La présentation de la page anglaise fait d'autres choix de présentation, en particulier

Question 3

Dans l'algorithme du crêpier (Pancake sorting) on a supposé que les faces d'une crêpe sont identiques. On suppose maintenant que les crêpes ont une face jolie et une plus brûlée. On veut positionner les crêpes dans le tas final avec la plus jolie face sur le dessus. Évidemment l'opération Retourne-préfixe retourne toutes les crêpes concernées (donc inverse leurs faces).

1 Crêpier-Récursif (T,n)
2   if n != 1
3       k =Indice-du-max (T,n)
4       // recherche de l’indice de la valeur maximale du tableau de 1 à n
5       Retourne-préfixe (T,k)
6       // positionnement de la plus grande crêpe au sommet de la pile
7       Retourne-préfixe (T,n)
8       // positionnement de la plus grande crêpe à la position n
9       Crêpier-Récursif (T,n-1)
10      // appel r´ecursif pour trier le tableau de 1 à n - 1

Comment modifier l'algorithme initial en insérant

if (dessus-crêpe(T[1]) == ???) Retourne-préfixe(T,1)
  1. la ligne doit être insérée après la ligne 1,2,3,5,7 ou 9
  2. la valeur de dessus-crêpe(T[1]) dans le test est jolie ou brûlée

réponses (éléments)

  1. Lorsque l'on positionne la crêpe la plus grande au sommet après la première opération de Retourne-préfixe la deuxième opération Retourne-préfixe va inverser la face de la crêpe. Donc la face visible avant le deuxième retournement doit être brulée pour que, in fine, la crêpe mise en position ait sa jolie face sur le dessus. On doit donc insérer la ligne entre les deux opérations de Retourne-préfixe, soit après la ligne 5.
  2. avant le deuxième retournement la face au sommet de la pile doit être brûlée, Donc on doit avoir if (dessus-crêpe(T[1]) == joli) Retourne-préfixe(T,1)

Question 4

On considère la fonction miroir une version simplifiée de Retourne-préfixe, qui effectue le renversement du tableau.

def miroir(T):
    """ modifie le tableau T en renversant ses éléments
    la modification se fait en place
    >>> T = ['A', 'B', 'C', 'D']
    >>> miroir(T)
    >>> T
    ['D', 'C', 'B', 'A']
    """
    n = len(T)
    for i in range(n):
        T[i], T[n-i] = T[n-i], T[i]
Le code proposé ci-dessus semble présenter des erreurs de nature algorihmique.

  1. Le code est correct (répondre aux questions suivantes (vrai/faux) si vous estimez que le code n'est pas correct)
  2. Le code présente une/des erreur(s) d'indiçage
  3. Les bornes pour l'itération devraient être for i in range(1,n):
  4. Les bornes pour l'itération devraient être for i in range(0,(n - 1) // 2):
  5. Les bornes pour l'itération devraient être for i in range(0,n // 2): avec l'échange T[i], T[n-i-1] = T[n-i-1], T[i]

réponses (éléments)

Un code exprimant la même idée

def miroir_corrige(T):
    """ modifie le tableau T en renversant ses éléments
    la modification se fait en place
    >>> T = ['A', 'B', 'C', 'D']
    >>> miroir(T)
    >>> print(T)
    ['D', 'C', 'B', 'A']
    >>> T1 = ['A', 'B', 'C', 'D','E']
    >>> miroir(T1)
    >>> print(T1)
    ['E','D', 'C', 'B', 'A']

    """
    n = len(T)
    for i in range(0,n // 2):
        T[i], T[n - i - 1] = T[n - i - 1], T[i]
  1. Faux : le code n'est pas correct, erreurs de conceptions et de correspondances d'indices
  2. Vrai : par exemple lorsque i = 0à la première itération n - i = n et T[n]n'est pas défini (le tableau est indicé de 0à n)
  3. Faux : il n'y a plus d'erreurs d'indices, mais le résultat n'est pas correct, on fait 2 fois le miroir donc le tableau est inchangé
  4. Faux : Les bornes ne sont pas correcte par rapport à l'échange
  5. Vrai