Tableaux

Tableaux, recherche et tris simples

Frédéric Herbreteau, Bordeaux INP/LaBRI (frederic.herbreteau@bordeaux-inp.fr)

Tableaux

Un tableau t est:

  • une zone de mémoire contiguë,
  • de taille fixe n,
  • contenant des données de même type,
  • indexé de 0 à n-1,
  • avec accès t[i] en temps constant $\Theta(1)$

Exemple:

| 1 | 2 | 3 | 4 | 5 | |-|-|-|-|-|

tableau t de taille n=5, indexé de 0 à 4, t[0] vaut 1, et t[3] vaut 4

Type abstrait IntArray

  • le type abstrait IntArray représente les tableaux d’entiers
  • len(t) ou t.size donne le nombre d’éléments dans le tableau t
  • t[i] donne la valeur à l’index i dans t avec 0 <= i < t.size
def newIntArray(size: int) -> IntArray:
    """ Returns a new array of integers of specified size, filled with 0 """

def newRandomIntArray(size: int) -> IntArray:
    """ Returns a new array of integers of specified size, randomly filled with number between 0 and size-1 """

def newSortedRandomIntArray(size: int) -> IntArray:
    """ Returns a new sorted array of integers of specified size, randomly filled with numbers between 0 and size-1 """

def newPermutationIntArray(size: int) -> IntArray:
    """ Returns a new array of integers of specificed size, filled with a  random permutation of integers between 0 and size-1 """

def newExplicitIntArray(l : List[int]) -> IntArray:
    """ Returns a new array filled with the elements from l """

def reverseArray(t: IntArray):
    """ reverse array t """

def equalArray(t1: IntArray, t2: IntArray) -> bool:
    """ Returns True if t1 and t2 have same size and elements, False otherwise """

Algorithmes de recherche

Recherche linéaire

Recherche la première occurrence de x dans le tableau d’entiers t

  • PRECOND: t est un tableau d’entiers, et x est un entier
  • POSTCOND: si x appartient à t, alors findFirst retourne le plus petit entier i entre 0 et t.size-1 tel que t[i] = x, sinon findFirst retourne None

Exercice 1

  • Écrire un algorithme basé sur le principe de recherche linéaire
def findFirst(t: IntArray, x: int) -> int | None:
  • Prouvez que l’algorithme termine, qu’il est correct et évaluer sa complexité

Recherche du maximum

Recherche la plus grande valeur du tableau d’entiers t

  • PRECOND: t est un tableau d’entiers
  • POSTCOND: retourne None si t est vide, sinon x tel que x est la plus grande valeur qui appartient à t

Exercice 2

  • Écrire un algorithme
def findMax(t: IntArray) -> int | None:
  • Prouvez que l’algorithme termine, qu’il est correct et évaluer sa complexité

Recherche dichotomique dans un tableau trié

Recherche de x dans le tableau d’entiers t trié

  • PRECOND: t est un tableau d’entiers trié, et x est un entier
  • POSTCOND: si x appartient à t, alors findBin retourne un entier i entre 0 et t.size-1 tel que t[i] = x, sinon findBin retourne None

Exercice 3

  • Écrire un algorithme de complexité $\Omicron(\log_2(t.size))$
def findBin(t: IntArray, x: int) -> int | None:
  • Prouvez que l’algorithme termine et qu’il est correct

Algorithmes de calcul

Somme

Somme des éléments d’un tableau d’entiers

  • PRECOND: t est un tableau d’entiers
  • POSTCOND: sumArray retourne la somme des entiers dans t

Exercice 4

  • Combien vaut la somme des valeurs d’un tableau vide?
  • Écrire un algorithme
def sumArray(t: IntArray) -> int:
  • Prouvez que l’algorithme termine, qu’il est correct et évaluer sa complexité

Produit scalaire

Produit scalaire de deux tableaux d’entiers

  • PRECOND: t1 et t2 sont deux tableaux d’entiers de même taille
  • POSTCOND: scalarProduct retourne le produit scalaire de t1 et t2

Exercice 5

  • Rappeler la définition du produit scalaire
  • Écrire un algorithme
def scalarProduct(t1: IntArray, t2: IntArray) -> int:
  • Prouvez que l’algorithme termine, qu’il est correct et évaluer sa complexité

Occurrences

Compte les occurrences de x dans t

  • PRECOND: t est un tableau d’entiers, et x est un entier
  • POSTCOND: countArray retourne le nombre d’occurrences de x dans t

Exercice 6

  • Écrire un algorithme
def countArray(t: IntArray, x: int) -> int:
  • Prouvez que l’algorithme termine, qu’il est correct et évaluer sa complexité

Fréquences

Calcule la fonction de fréquence des valeurs d’un tableau t

  • PRECOND: t est un tableau d’entiers positifs ou nuls
  • POSTCOND: freqArray retourne un tableau d’entiers tel que t[i] est la fréquence de i dans t

Exercice 7

  • Quelle doit-être la taille du tableau retourné par freqArray?
  • Écrire un algorithme
def freqArray(t: IntArray) -> IntArray:
  • Prouvez qu’il termine et qu’il est correct. Évaluer sa complexité en temps et en espace.

Comparaisons de tableaux

Égalité de tableaux

Décider si deux tableaux t1 et t2 contiennent les mêmes valeurs, aux mêmes indices

  • PRECOND: t1 et t2 sont deux tableaux d’entiers
  • POSTCOND: equalArray retourne la première position où t1 et t2 diffèrent

Exercice 8

  • Que doit retourner equalArray si t1 et t2 n’ont pas la même longueur?
  • Comment savoir si t1 et t2 sont égaux à partir de la valeur retournée?
  • Écrire un algorithme
def equalArray(t1: IntArray, t2: IntArray) -> int:
  • Prouvez que l’algorithme termine, qu’il est correct et évaluer sa complexité

Égalité de tableaux à rotation près

Décider si deux tableaux t1 et t2 sont égaux à rotation d près, plus précisément, si t2 est égal t1 auquel on aurait appliqué une roation d

  • PRECOND: t1 et t2 sont deux tableaux d’entiers, et d est un entier
  • POSTCOND: equalRotArray retourne True si t1 et t2 sont égaux à rotation d près, False sinon

Exercice 9

  • Écrire un algorithme
def equalRotArray(t1: IntArray, t2: IntArray, d: int) -> bool:
  • Prouvez que l’algorithme termine, qu’il est correct et évaluer sa complexité

Premiers algorithmes de tris

Fonction d’échange

Nous utiliserons la fonction swap qui permutte les valeurs aux indices i et j dans t.

def swapArray(t: IntArray, i: int, j: int) -> None:
    assert i < t.size
    assert j < t.size
    x: int = t[i]
    t[i] = t[j]
    t[j] = x
  • Cette fonction termine-t-elle?
  • Quelles sont ses PRECOND et POSTCOND? Est-elle correcte?
  • Quelle est sa complexité?

Tri à bulle - principe

Trier un tableau d’entiers t par ordre croissant

  • PRECOND: t est un tableau d’entiers
  • POSTCOND: t est trié, et il contient les mêmes valeurs et en même nombre

Principe:

  • on commence par placer la plus grande valeur en dernière position
    • on part de t[0], et à chaque fois que t[i+1] < t[i] on les échange
    • ainsi, la plus grande valeur va “remonter” en dernière position
  • puis on procède de même avec la deuxième plus grande valeur
    • elle remontera en avant dernière position
  • et ainsi de suite

Tri à bulle - algorithme

def bubbleSort(t: IntArray):
    for i in range(t.size - 1, 0, -1):
        for j in range(0, i):
            if t[j+1] < t[j]:
                swapArray(t, j, j+1)

Exercice 11

  • prouver la terminaison et la correction de bubbleSort
  • quels sont les cas au mieux et au pire?
  • calculer la complexité temporelle de bubbleSort

Tri par sélection (extraction) - principe

Trier un tableau d’entiers t par ordre croissant

  • PRECOND: t est un tableau d’entiers
  • POSTCOND: t est trié, et il contient les mêmes valeurs et en même nombre

Principe:

  • supposons que les valeurs t[0], …, t[i-1] sont triées, et inférieures ou égales aux valeurs t[i], …, t[t.size-1]
  • on calcule l’index j du minimum de t à partir de l’indice i
  • on échange t[i] et t[j]

Tri par sélection (extraction) - algorithme

Exercice 12

def argmin(t: IntArray, i: int) -> int:
    assert i < t.size
    imin = i
    for k in range(i+1, t.size):
        if t[k] < t[imin]:
            imin = k
    return imin

def selectionSort(t: IntArray):
  • Que calcule la fonction argmin? Quelles sont ses PRECOND et POSTCOND?
  • Écrire l’algorithme selectionSort
  • Prouver la terminaison et la correction de l’algorithme, puis évaluer sa complexité

Tri par insertion - principe

Trier un tableau d’entiers t par ordre croissant

  • PRECOND: t est un tableau d’entiers
  • POSTCOND: t est trié, et il contient les mêmes valeurs et en même nombre

Principe:

  • supposons que les valeurs t[0], …, t[i-1] sont triées
  • on “descend” t[i] à sa place par échanges successifs

Tri par insertion - algorithme

Exercice 13

  • Écrire l’algorithme insertionSort
def insertionSort(t: IntArray):
  • Prouver la terminaison et la correction de l’algorithme
  • Quels sont les cas au mieux et au pire?
  • Évaluer sa complexité

Conclusion et perspectives

Conclusion

  • Structure: compétences développées
    • concevoir et formaliser des algorithmes de traitement de séquences
    • prouver la terminaison et la correction d’algorithmes itératifs
    • évaluer la complexité asymptotique d’algorithmes itératifs
  • Algorithmes de recherche
    • gain exponentiel sur un tableau trié

Question: ce gain exponentiel repose-t-il sur la même condition que dans le cas de la recherche d’un zéro d’une fonction?

  • Algorithmes de tri de complexité quadratique au pire

Peut-on faire mieux?

Exercices supplémentaires

Recherche de la dernière occurrence

Recherche la dernière occurrence de x dans le tableau d’entiers t

  • PRECOND: t est tableau d’entiers, et x est un entier
  • POSTCOND: si x appartient à t, alors findLast retourne le plus grand entier i entre 0 et t.size-1 tel que t[i] = x, sinon findLast retourne None

Exercice 14

  • Écrire un algorithme
def findLast(t: IntArray) -> int | None:
  • Prouvez que l’algorithme termine, qu’il est correct et évaluer sa complexité

Moyenne des valeurs d’un tableau

Moyenne des valeurs d’un tableau d’entiers

  • PRECOND: t est un tableau d’entiers
  • POSTCOND: avgArray retourne la moyenne des entiers dans t

Exercice 15

  • Combien vaut la moyenne des valeurs d’un tableau vide?
  • Écrire un algorithme
def avgArray(t: IntArray) -> float:
  • Prouvez que l’algorithme termine, qu’il est correct et évaluer sa complexité

Égalité à permutation près

Décider si deux tableaux sont égaux à permutation près

  • PRECOND: t1 et t2 deux tableaux d’entiers (éventuellement $\ge 0$)
  • POSTCOND: retourne True si t1 et t2 sont égaux à permutation près, False sinon

Exercice 16

  • Écrire un algorithme
def eqPermutationArray(t1: IntArray, t2: IntArray) -> bool:
  • Prouvez que l’algorithme termine, qu’il est correct et évaluer ses complexités temporelle et spatiale

Rotation d’un tableau dans un autre

Créer un tableau obtenu par rotation de t de distance d

  • PRECOND: t est un tableau d’entiers, et d est un entier $\ge 0$
  • POSTCOND: rotArray retourne un nouveau tableau, égal a t à rotation d près

Exercice 17

  • Écrire un algorithme
def rotArray(t: IntArray, d: int) -> IntArray:
  • Prouvez que l’algorithme termine, qu’il est correct et évaluer ses complexités temporelle et spatiale