Les tableaux

I/ Exemple

1) Les carrés

2) En extension

En Python on écrit

[0,1,4,9,16,25,36,49,64,81]

3) Par ajouts successifs

L = []
for k in range(10):
    L.append(k**2)
    print(k,L)

0 [0]
1 [0, 1]
2 [0, 1, 4]
3 [0, 1, 4, 9]
4 [0, 1, 4, 9, 16]
5 [0, 1, 4, 9, 16, 25]
6 [0, 1, 4, 9, 16, 25, 36]
7 [0, 1, 4, 9, 16, 25, 36, 49]
8 [0, 1, 4, 9, 16, 25, 36, 49, 64]
9 [0, 1, 4, 9, 16, 25, 36, 49, 64, 81]

4) En compréhension

[k**2 for k in range(10)]

II/ Algorithmes

1) Longueur

def longueur(tableau):
  compteur = 0
  for x in tableau:
    compteur = compteur+1
  return compteur

Un invariant possible est la variable compteur contient le nombre d'éléments déjà comptés. On peut prouver la correction de l'algorithme avec why3.

Le coût de cet algorithme est linéaire : le parcours du tableau prend un temps proportionnel à sa longueur.

2) Appartenance

def est_dedans(elt,tableau):
  for x in tableau :
    if x==elt:
      return True
  return False

Un invariant possible est l'élément cherché n'est pas parmi les éléments déjà explorés. On peut prouver la correction de l'algorithme avec why3.

Pour tester le premier élément, on ne fait qu'une comparaison, le coût est donc constant :

Si l'élément n'est pas dans la liste, le coût est linéaire :

3) Minimum

def minimum(tableau):
    entier = float('inf')
    for i in range(len(tableau)):
        if tableau[i] <= entier:
            entier = tableau[i]
    return entier

Un invariant possible est la variable entier contient le minimum des éléments déjà examinés.

Le coût est linéaire :

Maximum

Un invariant possible est la variable m contient le maximum de la liste explorée jusqu'ici :

def maximum(L):
    #@ requires forall i. 0<=i<len(L) -> L[i]>=0
    #@ ensures forall i. 0<=i<len(L) -> result>=L[i]
    m = 0
    for k in range(len(L)):
        #@ variant len(L)-k
        #@ invariant forall i. 0<=i<k -> L[i]<=m
        if L[k]>m:
            m = L[k]
    return m

On peut prouver cela en ligne avec why3.

4) Somme

def total(liste):
    somme = 0
    for elt in liste:
        somme += elt
    return somme

Un invariant possible est la variable somme contient la somme des éléments déjà parcourus.

III/ Haskell

En fait, tous les algorithmes présentés ici utilisent la fonction foldl de Haskell (en Python, reduce). On va considérer ici que tous les éléments de la liste sont des entiers. La fonction foldl accepte en entrée

• une opération (fonction portant sur deux éléments) associative,
• un élément de départ (typiquement l'élément neutre de l'opération),
• une liste,

et calcule le résultat de l'opération sur la totalité de la liste.

1) Longueur

On gagne à définir la fonction constante qui, à chaque élément de la liste, associe le nombre 1 :

un :: Int -> Int
un x = 1

Alors en appliquant cette fonction à la liste L on obtient une liste constituée de 1 et ayant la même longueur que L.

longueur :: [Int] -> Int
longueur liste = foldl (+) 0 (map un liste)

2) Appartenance

dedans :: Int -> [Int] -> Bool
dedans elt liste = foldl (||) False (map (== elt) liste)

L'équivalent en Python s'appelle any. En mathématiques on note ∃.

3) Minimum

Pour le maximum, on utilise la fonction max qui, à deux nombres, associe le plus grand des deux :

maxi :: [Int] -> Int
maxi liste = foldl (max) 0 liste

Pour le minimum, on choisit une valeur de départ qui ne risque pas d'être le minimum de la liste : le plus grand entier représentable avec deux octets.

mini :: [Int] -> Int
mini liste = foldl (min) (2^24) liste

4) Somme

Exemple archétypal : l'addition est définie pour deux entiers, et on l'étend à autant d'entiers que possible :

somme :: [Int] -> Int
somme liste = foldl (+) 0 liste

On en déduit la programmation en Haskell de la fonction moyenne :

moyenne :: [Int] -> Int
moyenne liste = (somme liste) // longueur liste

IV/ Autres langages

1) Javascript

a) Appartenance

let dedans = function(elt,L) {
    let i, x
    for (i=0; i<L.length; x=L[i++]) {
        if (x==elt) {return true}
    }
    return false
}

b) Minimum et maximum

let minimum = function(L) {
    let i,m, x
    for (i=0,m=Infinity; i<L.length; x=L[i++]) {
        if (m>x) {m=x}
    }
    return m
}

let maximum = function(L) {
    let i,m, x
    for (i=0,m=0; i<L.length; x=L[i++]) {
        if (m<x) {m=x}
    }
    return m
}

c) Somme et moyenne

let somme = function(L) {
    let i, s
    for (i=0,s=0; i<L.length; s+=L[i++]) {}
    return s
}

let moyenne = function(L) {
    let i, s
    for (i=0,s=0; i<L.length; s+=L[i++]) {}
    return s/L.length
}

2) bash

a) Maximum

maximum(){
    local m=0
    for x; do
        if [ $m -lt $x ]
            then let "m=$x"
        fi
    done
    echo $m
}

b) Somme

somme(){
    local s=0
    for x in $@; do
        let "s+=$x"
    done
    echo $s
}

3) Ruby

a) Minimum et maximum

def minimum(liste)
    m = 1.0/0
    liste.each { |x|
        if m>x
            m = x
        end
    }
    return m
end

def maximum(liste)
    m = 0
    liste.each { |x|
        if m<x
            m = x
        end
    }
    return m
end

b) Somme et moyenne

def somme(liste)
    s = 0
    liste.each { |x| s+=x }
    return s
end

def moyenne(liste)
    s = 0
    liste.each { |x| s+=x }
    return s.to_f/liste.size
end

4) Lua

a) Appartenance

function dedans (elt,liste)
    for k,v in ipairs(liste) do
        if v==elt then return true end
    end
    return false
end

b) Maximum

function maximum (liste)
    local m = 0
    for k,v in ipairs(liste) do
        if v>m then m=v end
    end
    return m
end

c) Somme et moyenne

function somme (liste)
    local s = 0
    for k,v in ipairs(liste) do
        s = s+v
    end
    return s
end

function moyenne (liste)
    local s = 0
    local n = 0
    for k,v in ipairs(liste) do
        s = s+v
        n = n+1
    end
    return s/n
end