TD2 - Application

Exercice variant

On donne la fonction suivante, permettant de vérifier si une chaîne de caractères est un palindrome (mot qui se lit dans les 2 sens). La fonction retourne vrai si c’est un palindrome, faux sinon :

def palindrome(m) :
    i = 0
    j = len(m)-1
    pal = True
        while i <= j and pal == True :
        if m[i] == m[j] :
            i = i+1
            j = j-1
        else :
            pal = False
    return pal

Remplir les tableaux suivants avec m = ”radar” et m = ”sauras” :

Radar

Nombre Exécution	i	j	pal
init	0		True
1
2

Sauras

Nombre Exécution	i	j	pal
init	0		True
1
2

👉 Revenir au cours 👈

Exercice invariant

Puissance

On donne le programme suivant :

def puissance(n):
    p = 1
    for k in range(n):
        p = p*2
    return p

En suivant les 3 étapes, démontrer la correction de ce programme avec la propriété p = 2^k.

Tri sélection

Le tri par sélection est une autre méthode de tri consistant à choisir, à chaque tour de boucle, l'élément le plus petit de la liste, et de l'échanger de place avec le premier élément. L'algorithme recommence le même principe à partir du deuxième élément, puis le troisième, jusqu'à la fin.

1. Dessiner les étapes permettant de trier la liste [5,3,9,1,7] avec le tri par sélection.
2. Écrire un algorithme permettant de trouver le plus petit élément dans une liste, et qui échange sa place avec le premier élément.
3. Modifier l'algorithme pour lui permettre de répéter les opérations en avançant dans la liste.
4. Démontrer, selon le même principe, la correction du programme du tri par sélection (c’est-à-dire vérifier que la propriété que la liste soit triée est vraie). On peut s'aider de la liste suivante :

   i	t
   0	5 9 -1 2 7
   1	-1 9 5 2 7
   2	-1 2 5 9 7
   3	-1 2 5 7 9
   4	-1 2 5 7 9

👉 Revenir au cours 👈