Spécification/Correction/Terminaison, Triplets de Hoare, Complexité amortie

Introduction à l’algorithmique

Recherche d’un maximum

Max(T,n)
  max ⟵ T[1]
  // {max = T[1]}
  For i from 2 to n do
    // {max = max(T[k] | 1 \leq k < i }
    If T[i] > max then
      // {T[i] > max(T[k] | 1 \leq k < i }
      max ⟵ T[i]
      // {max = T[i] > max(T[k] | 1 \leq k < i }
    Else
      skip
    // {max = max(T[k] | 1 \leq k \leq i } ⟶ \leq car i est incrémenté à la fin de la boucle "for"
  // {max = max(T[k] | 1 \leq k < n }
  return max

Complexité : $n-1$ comparaisons

⟶ On peut faire mieux (cf. TD : rassembler les éléments 2 par 2 : 3 comparaisons par bloc de deux éléments) : $\frac{3(n-1)}{2}$ comparaisons.

Paradigmes algorithmiques : ex : diviser pour régner, mémoïsation, etc…


Correction

Un algo est correct ssi :

  • il se termine
  • il implémente sa spécification

Peut-on dire syntaxiquement (en théorie) si un programme termine ? NON : contre-exemple :

Ackermann

Ackermann(m,n):
  if m == 0:
    return n+1
  if n==0:
    return Ackermann(m-1,1)
  return Ackermann(m-1, Ackermann(m,n-1))

⟹ Ackermann ne peut pas être écrite avec des boucles for : pourquoi ? Parce que la valeur de retour croît trop pour un programme incluant des boucles for.


Comment se fait la correction ?

Correction partielle, puis terminaison.

Pq correction partielle ?

  1. Des fois, spécification et terminaison n’ont rien à voir.
  2. Correction partielle : preuve = svt plus naturelle
  3. Correction partielle : des fois, simplifie la terminaison

Peut-on établir la terminaison ?

NON : contre-exemple de Turing : ABS : supposons qu’il existe un programme Termine(Code, Donnée) qui teste si un Code(Donnée) termine.

Fou(Code)
  Tant que Termine(Code, Code)
    faire fait

ALORS : Fou(Fou) termine ⟺ Fou(Fou) ne termine pas


Relation bien fondée

Si $<$ est une relation binaire sur un ensemble $E$ : elle est bien-fondée ssi il n’existe pas de suite infinie $e$ telle que \(∀ n, e_{n+1} < e_n\)

  • $(ℕ, <)$ est bien fondé

Propriétés : Si $<$ est bien fondée, alors :

  • elle est irréflexive (sinon, les suites constantes sont “infiniment décroissantes”)
  • $<^{+}$ : la relation transitive ($x <^{+} y$ ssi il existe des $z_i$ tq $x < z_1 < ⋯ < z_n < y$ ) est bien fondée, a fortiori
  • La fermeture transitive réflexive $<^{*}$ (i.e $<^{+}$ OU $=$) est une relation d’ordre partielle (réflexive, transitive, antisymétrique)
  • Un produit cartésien de 2 ensembles bien fondés muni de l’ordre lexicographique est bien fondé (par l’absurde). (idem pour $k$ ensembles)

Terminaison des boucles

Soit $E, <$ un ensemble bien-fondé.

While i > 0 and j > i do
  i ⟵ i*j
  j ⟵ 2*j

Terminaison : $E, < = ℕ^2, <$ : $𝜑(i, j)=(max(3-i, 0), j-i)$ décroît.

Terminaison des appels récursifs

Pour Ackermann : $(E, <) = (ℕ^2, <)$ et $𝜑$ l’identité (c’est $(m,n)$ qui décroît)

⟶ Pas de différence de traitement des boucles / des fonctions récursives : c’est selon les paramètres.

Correction partielle : les triplets de Hoare

Triplet de Hoare : ${𝜑}pg{𝜓}$ : précondtion - programme - postcondition

Sert à la spécification et à la vérification.

Attention ! Dans l’exemple de la factorielle :

  • postcondition : PAS $out = in!$ mais $out = x!$ car $in$ peut avoir été modifiée par le programme (d’où l’intérêt de la variable logique $x$ : elle stocke la valeur initiale de $in$)

$s \bullet pg$ : on a appliqué $pg$ avec comme entrée $s$.

Si le triplet est valide : $\vDash {𝜑}pg{𝜓}$


Etablir un triplet : affectation

$\vdash 𝜑$ : on a prouvé $𝜑$ avec notre système de preuve

Dans la pratique : on prouve de “droite à gauche” / “bas en haut”

Etablir un triplet : concaténation

Difficulté : trouver le bon $\theta$

Ex : Programme qui échange $x$ et $y$

x ⟵ x + y
y ⟵ x - y
x ⟵ x - y

NB: Si on veut manipuler autre chose que des entiers, on revient aux mots (bits).

Etablir un triplet : conditionnelle

On n’introduit pas de nouveaux objets : donc plus facile que la concaténation.

NB : Les preuves terminent car la taille du programme diminue quand on remonte de bas en haut.

Etablir un triplet : itération

Quand $t$ augmente de 2, $a$ augmente de $1$ ⟹

Difficulté : trouver un invariant $𝜑$.

Etablir un triplet : règles annexes

  • règle du skip, si on ne fait rien
  • affaiblissement : conclusion plus faible que l’hypothèse : on prouve qch de plus fort que ce dont on a besoin. Précondtion $𝜑’$ plus faible, postcondition $𝜓’$ est plus forte.

NB : complexe à mettre en oeuvre : dans la plupart des systèmes : $𝜑 ⟹ 𝜑’$ indécidable.

Correction et complétude

Correction

Tout ce qui est prouvé est vrai.

Complétude :

Ce qui est vrai peut être prouvé.

Correction : par construction du système de preuve.

/!\ Complétude sans correction est inutile ! Car on peut avoir un système de preuve bidon où “tout est vrai”.

Programme d’Hilbert : trouver un programme qui énumère tous les énoncés vrais dans $(ℕ, +, *)$. Th de Gödel : il n’en existe pas !

MAIS pour $(ℝ, +, *)$ : il y en a ! (on ne peut pas trouver de système logique du premier ordre pour où on peut exprimer le fait qu’un réel est entier)

raisonnable = implémentable par une machine.

Etablir un triplet : récursivité

On peut substituer l’utilisation d’un structure dynamique (la pile) à la récursivité.

MAIS : récursivité : souvent plus naturelle.

Execution d’un programme récursif : pourquoi peut-on supposer que fact(sous-donnée) est correcte ? ⟶ récurrence décroissante : on termine par les cas de base.

Analyse de complexité

Bien faire la différence entre problèmes et instances (cas particuliers).

En complexité : on mesure le temps d’exécution du programme en fonction de la taille de l’instance en entrée.

Représentations possibles

Ex: Graphes :

  • Liste d’adjacence
  • Matrice d’adjacence

Pour représenter un entier $n$ ⟶ $\log(n)$ bits.

Attention : est-ce les instances grandissent vite au cours de l’exécution du programme ?

Ex :

  • Pivot de Gausse : en $O(n^3)$, certes : mais les pivots grandissent comment ? (réponse : polynomialement, puisque ce sont des déterminants de sous-matrices de la matrice originale)

Attention : si les entiers sont les entrées : leur représentation croît logarithmiquement. Mais en représentation unaire : croît en linéairement.

Mesures de Complexité

  • Le temps d’exécution
  • La mémoire occupée

Chez nous : temps d’abord, mémoire après (ordre lexicographique).

Quel cas considérer :

  • Pire cas
  • Cas moyen : plus réaliste, mais suppose une distribution sur les instances (à justifier au niveau de la modélisation) + analyse plus compliquée (probas).
  • Meilleur cas (rarement étudié) : il y a des algos conçus pour optimiser le meilleur cas.

Loi de Moore : nb de transistor = $\times 2$ tous les 18 mois.

⟹ On s’abstrait des caractéristiques matérielles :

  • temps symboliques
  • opérations significatives

Analyse amortie :

Pourquoi amortie ? Car chaque incrémentation dépend des précédentes.

$f(n)$ : deux critères :

  • Complexité amortie en $O(1)$
  • Peu de place

Complexité amortie

Complexité en pire cas, mais on se donne des outils pour la calculer

Complexité en moyenne

Pour tout $n$, distribution sur les instances de taille $n$.

ABR :

  • l’espace des clés est ordonné.
  • facteur déterminant pour la complexité : la hauteur de l’arbre (en pire cas : temps proportionnel à la hauteur de l’arbre).

Distribution :

Ex:

  • Distribution uniforme sur tous les arbres à $n$ sommets.
\[E(f_n) = \sum\limits_{i=1}^n \frac 1 n E(f_{n,i})\]

Point clé : la distribution d’insertion est uniforme.

Important :

Plutôt que de majorer $2^{max(a,b)}$ par $2^{a+b}$, on le majore par $2^a+2^b$.


$E(f_n) ≤ n^3 + 1$ : par réc

Les arbres (même pas équilibrés, en moyenne) sont meilleurs que les liste (recherche en moyenne en $O(n/2)$ (élément au centre)).

Schémas

Diviser pour régner :

  • top ⟶ down
  • ss-problèmes indépendants (arbre)

MAIS :

si ss-problèmes = dépendants, il vaut mieux une méthode bottom ⟶ up : ex, programmation dynamique

MAIS : Pb de la programmation dynamique :

  • ss-pbs = graphe acyclique ⟹ pb de mémoire
    • on n’a pas forcément besoin de retenir tous les ss-pbs selon l’ordre dans lequel on parcourt le graphe.

Recherche du plus grand facteur commun

En espace : tableau en $O(mn)$


C       O                         M     P      U --- ------ -------------           ------ ------ ------

O 0 1 1 1 1

R 0 max(0,1,0+0 (R<>0))

D

I


Problème du sac à dos

$v_1, ⋯, v_n$ donnés :

on cherche $I ⊆ {1, ⋯, n}$ tq $\sum_i v_i$ soit maximale et $\sum_i v_i ≤ w$ (pour $w$ fixé).

Ordonnancement de tâches.

Attention : tâches doivent être indépendantes

Énorme avantage des arbres $a-b$ : si on veut former un seul arbre à partir de deux arbres tq l’un a des feuilles toutes plus grandes que l’autre : on les concaténer en temps logarithmique, et les couper.

Leave a comment