Exercices corrigés -Algorithmique : ltableaux, listes, files

Exercice 1 - Dans un tableau ♡ [Signaler une erreur] [Ajouter à ma feuille d'exos] [Copier le lien]

On considère la fonction Python suivante :

def f(tab):
    m=tab[0]
    a=0
    n=len(tab)
    for i in range(1,n):
        if (tab[i]<m):
            m=tab[i]
            a=i
    return a

Quel résultat obtient-on en exécutant $\verb+f([8,1,3,7,2,3,6,8,19,4,2,0,1,2,1,10])+$ ?

Si $t$ est un tableau d'entiers de longueur $n\geq 3$, on dit que $i$ est la position d'un minimum local de $t$ si $1\leq i\leq n-2,$ $t[i]\leq t[i-1]$ et $t[i]\leq t[i+1]$. Écrire une fonction Python qui prend en entrée un tableau d'entiers et retourne la liste des positions de ces minimums locaux. On supposera que le tableau est de longueur au moins égal à $3$.

Corrigé

Exercice 2 - Insertion dans une liste triée ♡ [Signaler une erreur] [Ajouter à ma feuille d'exos] [Copier le lien]

Enoncé

Écrire une fonction qui prend en argument une liste triée $l$ et un entier $elt$ et qui renvoie la liste triée obtenue par insertion à sa place de $elt$ dans $l$. On fera attention à ce que la liste $l$ peut être vide.

Corrigé

def insere(l,elt):
    m=l.copy()
    if (len(m)==0):
        m.append(elt)
        return m
    if (elt>m[len(m)-1]):
        m.append(elt)
        return m
    i=0
    while (m[i]<elt):
        i+=1
    m.insert(i,elt)
    return m

Dans la fonction, on commence par tester si la liste est vide. Si ce n'est pas le cas, on regarde si l'élément est plus grand que tous les éléments de la liste : si c'est le cas, on l'ajoute à la fin. Sinon, on parcourt tous les éléments de la liste jusqu'à trouver la bonne place. Remarquons que la boucle se termine car, si on exécute la boucle, on sait que elt est inférieur ou égal au dernier élément de la liste. On réalise au début de la fonction une copie de la liste l pour ne pas modifier celle-ci.

Exercice 3 - Recherche du premier élément d'une liste ♡ [Signaler une erreur] [Ajouter à ma feuille d'exos] [Copier le lien]

Enoncé

Écrire une fonction prenant en argument une liste Liste et une variable x, et qui retourne le plus petit indice k de la liste tel que Liste[k] soit égal à x. Si la liste ne contient pas x, alors la fonction doit retourner -1.

Corrigé

def plus_petit(liste,x):
    n=len(liste)
    i=0
    while (i<n) and (liste[i]!=x):
        i+=1
    if i==n:
        return -1
    else:
        return i

Exercice 4 - Fusion de deux listes ♡ [Signaler une erreur] [Ajouter à ma feuille d'exos] [Copier le lien]

Enoncé

Écrire une fonction fusion qui prend en argument deux listes triées $L1$ et $L2$ et qui renvoie une seule liste triée contenant les éléments de $L1$ et $L2$.

Corrigé

On parcourt les deux listes en même temps afin de déterminer un premier rangement. On s'arrête lorsqu'une des deux listes est épuisée. On ajoute alors les termes qui restent de l'autre liste. Voici l'algorithme présenté sous Python.

def fusion(L1,L2):
    n1=len(L1)
    n2=len(L2)
    i,j=0,0
    L=[]
    while ( (i<n1) and (j<n2)):
        if (L1[i]<L2[j]):
            L.append(L1[i])
            i=i+1
        else:
            L.append(L2[j])
            j=j+1
    # On ajoute encore les termes de la liste non epuisee
    for i in range(i,n1):
        L.append(L1[i])
    for j in range(j,n2):
        L.append(L2[j])
    return L

Exercice 5 - Nombre d'occurences ♡ [Signaler une erreur] [Ajouter à ma feuille d'exos] [Copier le lien]

Enoncé

Écrire une fonction Python $maxi(L)$ prenant en argument une liste d'entiers naturels $L$ et renvoyant le maximum des entiers de cette liste (on n'utilisera pas de fonction spécifique de Python déterminant ce maximum). Quelle est le nombre d'opérations élémentaires effectué par cette fonction en fonction de la longueur $n$ de la liste?
Écrire une fonction Python $nboc(L)$ prenant en argument une liste d'entiers naturels $L$ et retournant une liste $T$ de longueur $M=maxi(L)+1$ où, pour tout $i\in\{0,\dots,M\}$, $T[i]$ est le nombre d'occurences de $i$ dans la liste $L$.
Quel est, en fonction de $n$ et $M$, le nombre d'opérations élémentaires effectué par votre fonction $nboc(L)$?
On veut que ce nombre ne dépende pas de $L$. Modifier votre fonction si ce n'est pas le cas.

Indication

Corrigé

Exercice 6 - Recherche par dichotomie dans une liste triée ♡ [Signaler une erreur] [Ajouter à ma feuille d'exos] [Copier le lien]

Enoncé

On propose l'algorithme suivant :

def rech_dicho(L,g,d,x):
    """L est une liste telle que L[g:d+1] est triee"""
    if x>L(d):
        return d+1
    else:
        a=g
        b=d
        while a!=b:
            c=(a+b)//2
            if x<=L[c]:
                b=c
            else:
                a=c+1
    return a

On prend $L=[2,4,5,7,7,8,10]$. Que renvoient les instructions suivantes?
- rech_dicho(L,1,5,6)
- rech_dicho(L,0,5,1)
Que fait la fonction rech_dicho?
Quelle est la complexité de cette fonction, mesurée en nombre de comparaisons. On pourra exprimer cette complexité en fonction d'un ou plusieurs paramètres parmi $\textrm{len}(L),g,d,x$.

Indication

Corrigé

- D'abord $L[5]=8$ qui est plus grand que $x=6$. On entre dans la partie "else" de la fonction, avec $a=1$ et $b=5$, puis $c=3$. On a $L[3]=7$ qui est plus grand que $x$, donc on change $b$ en $3$. On a ensuite (deuxième exécution de la boucle while) $c=2$ et $L[2]=5<6$. Il vient $a=3$ et on sort de la boucle. La fonction retourne donc $3$.
- Là encore, on va rentrer dans la boucle while. Comme $x$ est inférieur à tous les éléments de la liste, c'est toujours $b$ qu'on va changer. La fonction va donc retourner $0$.
Si $x>L[d]$, alors rech_dico retourne $d+1$. Sinon, rech_dico retourne un entier $k$ compris entre $g$ et $d$ tel que
- tous les éléments $L[g],\dots,L[k-1]$ sont strictement inférieurs à $x$;
- tous les élements $L[k],\dots,L[g]$ sont supérieurs ou égaux à $x$.
Cette propriété se démontre par le fait que, à chaque itération de la boucle, les éléments $L[g],\dots,L[a-1]$ sont strictement inférieurs ou égaux à $x$, et les éléments $L[b],\dots,L[d]$ sont supérieurs ou égaux à $x$. Cette propriété est vraie en rentrant dans la boucle. Ensuite, si la propriété est vraie au début d'une itération de la boucle, elle l'est encore en sortant de la boucle. En effet, si $L[c]\geq x$, alors $b=c$ et les éléments $L[b],\dots,L[d]$ sont encore supérieurs ou égaux à $x$ en sortant de la boucle (et $a$ est inchangé). Sinon, $L[c]<x$, et puisque $a=c+1$, les éléments $L[g],\dots,L[a-1]=L[c]$ sont bien strictement inférieurs à $x$.
Le nombre de comparaisons effectué est proportionnel au nombre d'itérations de la boucle. Notons $a_n$ (resp. $b_n$) la valeur de $a$ (resp. $b$) au début de la $n$-ième itération de la boucle. Alors $a_1=g$ et $b_1=d$. De plus, on a $b_{n+1}-a_{n+1}\leq\frac{b_n-a_n}{2}$. C'est vrai si $b_{n+1}=c\leq \frac{a_n+b_n}2$. En effet, on a alors $$b_{n+1}-a_{n+1}\leq\frac{a_n+b_n}2-a_n=\frac{b_n-a_n}2.$$ C'est aussi vrai si $a_{n+1}=c+1\geq\frac{a_n+b_n}2$ comme le montre un calcul similaire.
On a donc, tant qu'on n'est pas sorti de la boucle, $$b_n-a_n=\frac{g-d}{2^{n-1}}.$$ On sort pour le premier $n$ tel que $b_n-a_n<1$, et donc dès que $n$ vérifie l'inégalité $$1>\frac{g-d}{2^{n-1}}\iff n> 1+\log_2(g-d).$$ La complexité est donc $O\left(\log_2(g-d)\right)$.

Exercices corrigés - Algorithmique : ltableaux, listes, files