Site WWW de Laurent Bloch
Slogan du site

ISSN 2271-3905
Cliquez ici si vous voulez visiter mon autre site, orienté vers des sujets moins techniques.

Pour recevoir (au plus une fois par semaine) les nouveautés de ce site, indiquez ici votre adresse électronique :

Définitions, notations, pseudo-code
Article mis en ligne le 1er mars 2006
dernière modification le 14 août 2021

par Laurent Bloch

"http://www.w3.org/TR/REC-html40/loose.dtd">


Définitions

Auteur : William Saurin


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 :



  • tant que condition faire instruction ;... fait :



  • si condition alors instructions-si-vrai ; ... sinon instructions-si-faux ; ... finsi



  • si condition alors instructions-si-vrai ; ... fin si :



  • pour i valant de d à f faire instruction ; ... fait :



  • 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 :



  • 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

Algo

Nom de l’algorithme : recherche linéaire dans une suite de valeur

Données d’entrées : la liste (un tableau T) et la valeur à
rechercher V

Résultat en sortie : le numéro de l’élément trouvé

pos← 0 ;

tant que
pos < taille du tableau(T)
et T[pos] != V faire

pospos + 1

fait


si pos < taille du tableau(T) retourner pos
sinon retourner -1 finsi

Exemple

Rechercher 176 dans le tableau suivant :

pos                    
0 1 2 3 4 5 67 8 9 10 11
1 17 43 89 100 113 156 176 231 248 301

  pos                  
0 1 2 3 4 5 67 8 9 10 11
1 17 43 89 100 113 156 176 231 248 301

    pos                
0 1 2 3 4 5 67 8 9 10 11
1 17 43 89 100 113 156 176 231 248 301

      pos              
0 1 2 3 4 5 67 8 9 10 11
1 17 43 89 100 113 156 176 231 248 301

        pos            
0 1 2 3 4 5 67 8 9 10 11
1 17 43 89 100 113 156 176 231 248 301

          pos          
0 1 2 3 4 5 67 8 9 10 11
1 17 43 89 100 113 156 176 231 248 301

            pos        
0 1 2 3 4 5 67 8 9 10 11
1 17 43 89 100 113 156 176 231 248 301

              pos      
0 1 2 3 4 5 67 8 9 10 11
1 17 43 89 100 113 156 176 231 248 301


En Scheme ?

Codage 1

Codage 2


pos < taille du tableau(T) » et « T[pos] != V » ?—>

Combien de fois fait-on « pos < taille du tableau(T) » et « T[pos] != V » ?

Dans le pire des cas on va au bout de la liste : taille du tableau

Il y a autant de chance que chacune des valeurs du tableau soit recherchée,
elles ont chacune 1/taille du tableau chance d’être recherchées.

Et donc la valeur numero 0 donne 0 additions

la valeur numéro 1, 1 addition,

la valeur numéro i, i additions,

et donc :

0 *
1
taille du tableau
+ 1 *
1
taille du tableau
+ 2 *
1
taille du tableau
+ ...
(taille du tableau −1)
taille du tableau
=
taille du tableau * (taille du tableau − 1)
2
*
1
taille du tableau
= (taille du tableau −1) / 2



Si le tableau passe de N éléments à M > N éléments on passera de (N-1)/2
à (M-1) / 2 additions. On dira que cette recherche prends un nombre d’additions qui croît comme la taille du tableau, dans le pire des cas et dans le cas moyen.


Notation asymptotique

O

On dit qu’une fonction f est O(g) si il existe x0 et a
tels que pour tout x>x0 f(x)<ag(x)

Oméga

On dit qu’une fonction f est Ω(g) si il existe x0
et a tels que pour tout x>x0, f(x)>ag(x)

Théta

On dit qu’une fonction f est Θ(g) si il existe x0
et a1 et a2 tels que pour tout x>x0, a1g(x)<f(x)<a2g(x)



This document was translated from LATEX by H EVEA.