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

Introduction à l’algorithmique

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 ?

Des fois, spécification et terminaison n’ont rien à voir.
Correction partielle : preuve = svt plus naturelle
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))

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.

Share on

Twitter Facebook Google+ LinkedIn