Définitions

Un algorithme est une une procédure de calcul bien définie qui lorsqu’on lui fournit des données d’entrée produit des résultats en sortie. C’est donc une suite de pas de calcul qui transforme une entrée en une sortie.

Un algorithme est une méthode de calcul qui résoud un problème bien posé. La description du problème doit donc établir une relation entre une entrée et une sortie. Un algorithme est une procédure de calcul qui permet d’établir cette relation entre entrée et sortie :

Exemple :

• Étant donnée une suite de nombres trouver où dans la suite se trouve l’un d’entre eux.
• Étant donnée une suite de nombre trouver le plus grand.
• Étant donnée une chaîne de caractère représentant une chaîne d’ADN non ambigüe (ne contenant que A, T, G et C) déterminer la protéine qu’elle encode.
• Étant donnée une chaine représentant une protéine calculer le segment le plus hydrophobe, c’est à dire celui dont la somme des coéfficient d’hydrophobicité des acides aminés est la plus élevée

Mauvais exemples :

• Trouver l’arbre phylogénétique d’un ensemble de séquences d’ADN.
• Trouver le meilleur alignement de deux séquences de protéines.
• Trouver tous les gènes d’un génome.

Recherche linéaire

Problème : recherche dans une collection ordonnée d’éléments : il s’agit par exemple des lignes d’un fichier de texte et on recherche la première
ligne qui contient le mot DNA.

Formulations :

1. On regarde la première ligne et si elle contient DNA on s’arrête (on a trouvé), sinon on regarde la deuxième ligne et si elle contient DNA on s’arrête (on a trouvé), sinon ...
2. On examine successivement les lignes du fichier, tant qu’on n’a pas atteint la fin du fichier et que la ligne ligne courante ne contient pas DNA on passe à la ligne suivante, si on n’a pas atteint la fin du fichier alors on retourne la ligne courante.

Pseudo-code

• Nom de l’algorithme,
  
• données d’entrées,
  
• résultats en sortie,
  
  
• bloc tant que  :
  tant que condition faire
   instruction ;
   ...
  fin tant que
  
  
• bloc si  :
  si condition alors
   instruction-si-vrai ;
   ...
  sinon
   instruction-si-faux ;
   ...
  fin si
  
  
• bloc pour :
  pour i allant de d à f faire
   instruction ;
    ; ...
  fin pour
  
  
• bloc
  debut
   instruction ;
   ...
  fin
  
• notation des tableaux : A[i] : l’élément de rang i dans le tableau A, on suppose les tableaux numérotés à partir de 0 ;
  
  
• tableau multidimensionnel A[i, j] : élément en ligne i et en colonne j du tableau A.
  
  
• notation de chaine de caractères : “string”
  
  
• notation d’affectation : a ← 10
  
  
• retourner valeur
  
  
• autre-algo(données)

Traduction en Scheme

• nom de l’algorithme “algo” : (define (algo
• données d’entrées “foo”, “bar” : (define (algo foo bar)
• résultat en sortie : valeur retournée par la fonction
• initialisation de variables a←1 b←2 : (let ((a 1) (b 2)) ...)

  
  
  

• tant que condition faire instruction ;... fait : (let nom-de-boucle () (if (condition) (begin expression ... (nom-de-boucle)))

  
  
  

• si condition alors instructions-si-vrai ; ... sinon instructions-si-faux ; ... finsi
  (if condition (begin expressions-si-vrai ...) (begin expressions-si-faux ... )

  
  
  

• si condition alors instructions-si-vrai ; ... fin si :
  (if condition (begin expressions-si-vrai ...)

  
  
  

• pour i valant de d à f faire instruction ; ... fait :
  (do ((i d (+ i 1))) ((> i f) 'fait) expressions ...)

  
  
  

• notation de chaine “string” : “string”
  
  
• assignation à une variable a ( a ← b ) : (set ! a b)
  
  
• assignation a une position i dans un tableau A de la valeur de la variable b, A[i] ← b : (vector-set ! a i b)
  
  
• assignation a une variable b de la valeur à la position i d’un tableau, b ← A[i] : (set ! b (vector-ref a i))
  
  
• En scheme il n’y a pas de vecteurs multidimensionnel, mais on peut faire des vecteurs de vecteurs : pour obtenir un tableau à l lignes et c colonnes on peut faire :
  (let ((tableau (make-vector l))) (do ((i 0 (+ i 1))) ((= i l) tableau) (vector-set! tableau i (make-vector c))) ...)

  
  
  

• La valeur en ligne i et à la colonne j d’un tableau s’obtient par A[i,j] : (vector-ref (vector-ref tableau i) j)
  
  
• On assigne à la ligne i et a la colonne j du tableau A la valeur b (A[i,j] ←b) par : (vector-set ! (vector-ref tableau i) j b)<BR
  
• L’appel à un autre algorithme autre-algo(don nées)  : (autre-algo données)

Recherche linéaire dans une liste

Notation asymptotique