Huitième cours

11. Complexité

11.1 Le tri à bulles

• Cf. TP 6.

11.2 Calcul de la valeur d'un polynôme (Hörner)

• Méthode naïve : addition des monômes. Complexité : n additions et 2*n multiplications.

  FUNCTION Valeur(x : REAL; P : Polynôme) : REAL;
  VAR i : INTEGER;
      xn, Somme : REAL;
  BEGIN
    xn := x;
    Somme := P.Coeff[0];
    FOR i := 1 TO P.Degre DO
    BEGIN
      Somme := Somme + xn * P.Coeff[i];
      xn := x * xn;
    END;
    Valeur := Somme;
  END;
  

• Méthode de Horner. Complexité : n additions et n multiplications.

  FUNCTION Valeur(x : REAL; P : Polynôme) : REAL;
  VAR i : INTEGER;
      Resultat : REAL;
  BEGIN
    Resultat := P.Coeff[P.Degre];
    FOR i := P.Degre-1 DOWNTO 0 DO
      Resultat := Resultat*x + P.Coeff[i];
    Valeur := Resultat;
  END;
  

12. Permutations

12.1 Définition mathématique

• S(E) : bijections de E. Ensemble à n éléments.
• Dessins de patates à une ou deux patates. Représentation (x,f(x)) et par cycles.
• Groupe, d'ordre n! (loi de groupe, élément neutre, ordre d'un élément).

12.2 Représentation informatique

• Par tableau de n élément valant 1 à n.
• nⁿ valeurs possibles, toutes ne sont pas des permutations.

12.3 Manipulation des permutations

• FUNCTION Valide(P : Perm) : BOOLEAN;
  Deux boucles, pour un test de surjectivité, avec un tableau booléen.
• PROCEDURE Entrée(VAR P : Perm);
• PROCEDURE Affiche(P : Perm);
• PROCEDURE AfficheCycles(P : Perm);
• FUNCTION IsIdentité(P : Perm) : BOOLEAN;
  Une boucle.
• PROCEDURE Identité(VAR P : Perm);
  Une boucle.
• PROCEDURE Inverse(P : Perm; VAR Q : Perm);
Q[P[i]] := i;
• PROCEDURE Compose(P,Q : Perm; VAR R : Perm);
R[i] := Q[P[i]];
• FUNCTION Ordre(P : Perm) : INTEGER;
  Boucle WHILE.

12.4 Énumération des permutations

• Dans l'ordre lexicographique.
• On change la première position pour laquelle ce n'est pas l'ordre reverse.