Algorithmes simples

Que renvoie recherche([3, 7, 1], 7) pour la fonction de recherche séquentielle du cours ?

La valeur $7$ est présente dans la liste (à l'indice $1$), donc la fonction recherche (qui renvoie un booléen, pas un indice) renvoie True.

Quel est le pgcd de $48$ et $18$ ?

Par l'algorithme d'Euclide détaillé dans le cours : $\text{pgcd}(48,18)=\text{pgcd}(18,12)=\text{pgcd}(12,6)=\text{pgcd}(6,0)=6$.

Vrai ou faux : le tri par sélection trouve, à chaque étape, le plus petit élément restant et le place en tête de la partie non triée.

Vrai, c'est exactement le principe du tri par sélection : à l'étape $i$, on sélectionne le minimum de la sous-liste $L[i:]$ et on l'échange avec $L[i]$.

Quelle valeur renvoie la fonction indice(L, v) du cours si v n'est pas présent dans L ?

Par convention, la fonction renvoie $-1$ lorsque la valeur recherchée n'a été trouvée à aucun indice de la liste, après avoir parcouru tous les éléments.

Quelle est la complexité (en pire cas) de la recherche séquentielle dans une liste de longueur $n$ ?

Dans le pire cas (valeur absente, ou en dernière position), la recherche séquentielle examine les $n$ éléments de la liste : complexité linéaire $O(n)$.

Après la première itération ($i=0$) du tri par sélection sur $[5,2,8,1,9]$, quel est l'état de la liste ?

Le minimum de toute la liste est $1$, à l'indice $3$. On l'échange avec l'élément d'indice $0$ (qui est $5$) : $[1,2,8,5,9]$.

Vrai ou faux : a, b = b, a % b en Python échange et met à jour simultanément les deux variables, en utilisant l'ancienne valeur de a pour calculer le modulo.

Vrai. En Python, l'affectation multiple a, b = expr1, expr2 évalue d'abord toutes les expressions à droite avec les valeurs courantes, puis effectue les affectations. Donc a % b utilise bien l'ancienne valeur de a (et de b) avant toute modification.

Quelle est la complexité (pire cas) du tri par sélection sur une liste de $n$ éléments ?

Le tri par sélection effectue, pour chacune des $n$ étapes, une recherche du minimum parmi en moyenne $n/2$ éléments restants : le nombre total de comparaisons est de l'ordre de $n^2/2$, soit $O(n^2)$.

Calculer la moyenne de la liste $[4, 8, 6, 2]$ à l'aide des fonctions somme et moyenne du cours.

$\text{somme}=4+8+6+2=20$. $\text{moyenne}=20/4=5{,}0$.

Modifier la fonction recherche pour qu'elle compte le nombre de comparaisons effectuées avant de trouver la valeur (ou avant de conclure son absence). Donner le code modifié.

Une solution possible :

def recherche_comptee(L, v):

compteur = 0

for x in L:

compteur = compteur + 1

if x == v:

return True, compteur

return False, compteur

On incrémente un compteur à chaque comparaison effectuée (à chaque tour de boucle), et on le renvoie en plus du résultat booléen. Python permet de renvoyer plusieurs valeurs sous forme de tuple avec return a, b.

Dérouler le tri par insertion sur la liste $[3, 1, 4, 2]$ étape par étape ($i=1,2,3$) et donner le résultat final.

$i=1$ : clé $=L[1]=1$. On compare à $L[0]=3 > 1$, donc on décale $3$ vers la droite et on insère $1$ en tête : $[1,3,4,2]$.

$i=2$ : clé $=L[2]=4$. On compare à $L[1]=3$ : $3 < 4$, pas de décalage : $[1,3,4,2]$ inchangée.

$i=3$ : clé $=L[3]=2$. On compare à $L[2]=4>2$ : décalage, puis à $L[1]=3>2$ : décalage, puis à $L[0]=1 \leq 2$ : on insère $2$ juste après : $[1,2,3,4]$.

Le résultat final est la liste triée $[1,2,3,4]$.

Démontrer que l'algorithme d'Euclide se termine toujours en un nombre fini d'étapes, pour tous entiers $a \geq b > 0$ donnés au départ.

À chaque itération de la boucle while b != 0, le couple $(a,b)$ devient $(b,\, a\bmod b)$. Or, par définition du reste de la division euclidienne, $0 \leq a\bmod b < b$ (strictement).

Donc la nouvelle valeur de $b$ (qui est $a \bmod b$) est strictement inférieure à l'ancienne valeur de $b$. La suite des valeurs successives de $b$ est donc une suite strictement décroissante d'entiers naturels.

Une telle suite ne peut pas décroître indéfiniment (elle est minorée par $0$) : elle atteint nécessairement la valeur $0$ après un nombre fini d'étapes, ce qui termine la boucle while. $\square$

Pourquoi le tri par sélection effectue-t-il toujours environ $n^2/2$ comparaisons, indépendamment de l'ordre initial de la liste (contrairement au tri par insertion) ?

La boucle interne du tri par sélection (recherche du minimum dans la partie restante) s'exécute toujours sur tous les éléments restants, sans condition d'arrêt anticipée, quel que soit leur ordre. C'est pourquoi sa complexité est toujours $\Theta(n^2)$, alors que le tri par insertion peut s'arrêter plus tôt (boucle while) si la liste est déjà presque triée.

Écrire une fonction est_trie(L) qui renvoie True si la liste L est triée par ordre croissant, False sinon.

Une solution possible :

def est_trie(L):

for i in range(len(L) - 1):

if L[i] > L[i+1]:

return False

return True

On parcourt les paires d'éléments consécutifs ; dès qu'on en trouve une dans le mauvais ordre ($L[i]>L[i+1]$), on renvoie False immédiatement. Si aucune paire n'est dans le mauvais ordre après le parcours complet, la liste est triée : on renvoie True. On utilise range(len(L)-1) pour éviter une erreur d'indice hors limites en comparant le dernier élément à un suivant inexistant.

On veut calculer le PGCD de trois entiers $a, b, c$. Proposer une fonction pgcd3(a, b, c) réutilisant la fonction pgcd du cours, en justifiant l'identité mathématique utilisée.

Une solution possible :

def pgcd3(a, b, c):

return pgcd(pgcd(a, b), c)

Justification : un entier $d$ divise simultanément $a, b, c$ si et seulement si $d$ divise $\text{pgcd}(a,b)$ et $d$ divise $c$ (car $d \mid a$ et $d\mid b \iff d \mid \text{pgcd}(a,b)$). Donc l'ensemble des diviseurs communs à $a,b,c$ est exactement l'ensemble des diviseurs communs à $\text{pgcd}(a,b)$ et $c$, ce qui donne $\text{pgcd}(a,b,c) = \text{pgcd}(\text{pgcd}(a,b),\,c)$. Cette associativité permet de réduire le calcul du pgcd de $n$ nombres à des appels successifs de la fonction à deux arguments.