TP n°6 : Révisions et compléments - éléments de correction

$\require{color}$ $\require{xcolor}$ $\require{cancel}$ $\newcommand{\myfbox}[1]{\fcolorbox{red}{white}{$\textrm{#1}$}}$ $\require{stmaryrd}$ $\newcommand{\ient}{[\![}$ $\newcommand{\rrbracket}{]\!]}$ $\newcommand{\llbracket}{[\![}$ $\newcommand{\fient}{]\!]}$ $\newcommand{\R}{\mathbb R}$ $\newcommand{\K}{\mathbb K}$ $\newcommand{\N}{\mathbb N}$ $\newcommand{\C}{\mathbb C}$ $\newcommand{\P}{\mathbb P}$ $\newcommand{\E}{\mathbb E}$ $\newcommand{\V}{\mathbb V}$ $\newcommand{\Z}{\mathbb Z}$ $\newcommand{\dt}{\mathrm d}$ $\newcommand{\sh}{\operatorname{sh}}$ $\newcommand{\ch}{\operatorname{ch}}$ $\newcommand{\th}{\operatorname{th}}$ $\newcommand{\e}{\operatorname{e}}$ $\newcommand{\id}{\operatorname{Id}}$ $\newcommand{\mat}{\operatorname{mat}}$ $\newcommand{\sp}{\operatorname{Sp}}$ $\newcommand{\In}{\operatorname{I}}$ $\newcommand{\vect}{\operatorname{Vect}\ }$ $\newcommand{\rg}{\operatorname{rg}}$ $\newcommand{\tr}{\operatorname{Tr}}$ $\newcommand{\dis}{\displaystyle}$ $\renewcommand{\Im}{\operatorname{Im}}$ $\newcommand{\im}{\operatorname{Im}}$ $\newcommand{\bordermatrix}[3]{ \begin{matrix} \begin{matrix}#1\end{matrix} & \\ #3 & \hspace{-1em} \begin{matrix}#2\end{matrix} \end{matrix}}$ $\newcommand{\fonction}[5]{#1\ \colon \left\{\begin{array}{ccl}#2 & \longrightarrow & #3\\#4 & \longmapsto & #5\end{array}\right.}$ $\newcommand{\fonctionsansnom}[4]{\left\{\begin{array}{ccl}#1 & \longrightarrow & #2\\#3 & \longmapsto & #4\end{array}\right.}$ $\newcommand{\revdots}{\mathinner{\mkern1mu\raise1pt{\kern7pt\hbox{.}}\mkern2mu\raise4pt\hbox{.}\mkern2mu\raise7pt\hbox{.}\mkern1mu}}$ $\newcommand{\tendvers}[2]{\xrightarrow[#1\to#2]{}}$ $\newcommand{\q}[1]{\mathbf{Q#1}\ \triangleright}$ $\newcommand{\nicefrac}[2]{^{#1}/_{#2}}$

1 - Arguments des fonctions ; variables locales ou globales¶

Exercice 1

In [1]:

def max_pos(L: [int], i: int) -> (int, int):
    """
    Détermine le plus grand élément M d'une liste L jusqu'à l'indice i (inclus),
    ainsi que le premier indice pos réalisant ce maximum
    """
    M = L[0]
    pos = 0
    for k in range(i + 1):
        if L[k] > M:
            M = L[k]
            pos = k
    return M, pos

In [2]:

max_pos([1, 2, 3, 5, 6, 3, 4], 9)

Exercice 2

In [3]:

def max_pos(L: [int], i: int) -> (int, int):
    """
    Détermine le plus grand élément M d'une liste L à partir de l'indice i (inclus),
    ainsi que le premier indice pos réalisant ce maximum
    """
    assert (0 <= i < len(L))
    M = L[0]
    pos = 0
    for k in range(i + 1):
        if L[k] > M:
            M = L[k]
            pos = k
    return M, pos

In [4]:

max_pos([1, 2, 3, 5, 6, 3, 4], 9)

---------------------------------------------------------------------------
AssertionError                            Traceback (most recent call last)
<ipython-input-4-b2ea989d9b97> in <module>
----> 1 max_pos([1, 2, 3, 5, 6, 3, 4], 9)

<ipython-input-3-0902f1aee79d> in max_pos(L, i)
      4     ainsi que le premier indice pos réalisant ce maximum
      5     """
----> 6     assert (0 <= i < len(L))
      7     M = L[0]
      8     pos = 0

AssertionError:

Exercice 3

In [5]:

help(max_pos)

Help on function max_pos in module __main__:

max_pos(L: list, i: int) -> (<class 'int'>, <class 'int'>)
    Détermine le plus grand élément M d'une liste L à partir de l'indice i (inclus),
    ainsi que le premier indice pos réalisant ce maximum

On l'utilise alors dans la fonction tri de la manière suivante :

In [6]:

def tri(L: [int]) -> [int]:
    for i in range(len(L) - 1, 0, -1):
        M, pos = max_pos(L, i)
        L[pos], L[i] = L[i], L[pos]
    return L

In [7]:

L = [1, 2, 3, 5, 4, 3, 2, 6]

In [8]:

tri(L)

Out[8]:

[1, 2, 2, 3, 3, 4, 5, 6]

In [9]:

Out[9]:

[1, 2, 2, 3, 3, 4, 5, 6]

La liste L a été modifée par effet de bord !

Si l'on ne souhaite plus que la liste L soit modifiée par effet de bord, il suffit de la cloner au début de la fonction :

In [10]:

def tri(L: [int]) -> [int]:
    N = L.copy()
    for i in range(len(N) - 1, 0, -1):
        M, pos = max_pos(N, i)
        N[pos], N[i] = N[i], N[pos]
    return N

In [11]:

L = [1, 2, 3, 5, 4, 3, 2, 6]

In [12]:

tri(L)

Out[12]:

[1, 2, 2, 3, 3, 4, 5, 6]

In [13]:

Out[13]:

[1, 2, 3, 5, 4, 3, 2, 6]

2 - Recherche séquentielle¶

Exercice 4

In [14]:

def recherche_naive(x: float, L: [float]) -> bool:
    """
    Implémente la recherche naive d'un nombre x
    dans une liste de nombres L.
    Renvoie True si x est dans L et False sinon.
    """
    for elt in L:
        if x == elt:
            return True
    return False  # atteint seulement si l'on sort de la boucle for

In [15]:

recherche_naive(1, [2, 3, 4, 1, 2, 3, 5])

Out[15]:

True

In [16]:

recherche_naive(6, [2, 3, 4, 1, 2, 3, 5])

Out[16]:

False

In [17]:

recherche_naive(1, [])

Out[17]:

False

Exercice 5 : recherche dichotomique

In [18]:

def recherche_dicho(x: float, L: [float]) -> bool:
    """
    Recherche dichotomique de l'élément x dans la liste
    triée par ordre croissant L
    Renvoie True si x est dans L et False sinon.
    """
    a, b = 0, len(L) - 1
    while a <= b:
        i = (a + b) // 2
        if L[i] == x:
            return True
        elif L[i] > x:
            b = i - 1
        else:
            a = i + 1
    # arrivé ici, a > b et x n'est pas dans la liste L
    return False

Exercice 6 : recherche d'un motif dans un texte

Le plus simple à écrire est sans doute de "diviser pour régner", en écrivant d'abord une fonction qui teste la présence d’un mot à partir d’une position $i$ dans une chaîne de caractères :

In [19]:

def test(M: str, T: str, i: int) -> bool:
    """
    Teste la présence d’un mot M à partir d’une position i dans une chaîne de caractères T
    (on renvoie un booléen adéquat)
    """
    for j in range(len(M)):
        if M[j] != T[i + j]:
            return False  # cela met fin à la boucle for
    return True  # seulement si la boucle for est allée jusqu'au bout !

In [20]:

def recherche_naive(M: str, T: str) -> int:
    """
    Recherche le motif M dans la chaine T
    Renvoie l'indice de la premiere occurence de M dans T
    s'il y est present, et -1 sinon.
    """
    assert (len(M) <= len(T))  # les longueurs du mot et du texte sont compatibles
    n, m = len(T), len(M)
    indice = 0
    for i in range(n - m + 1):
        if test(M, T, i):
            return i  # on a rencontré M à partir de la position i dans T
    return -1  # seulement si la boucle for est allée jusqu'au bout !

In [21]:

recherche_naive("bambou", "bambamboum")

Out[21]:

In [22]:

recherche_naive("bim", "bambamboum")

Out[22]:

-1

Si l'on souhaite maintenant renvoyer le nombre d'occurrences du mot M dans le texte T, on peut adapter la fonction précédente de la manière suivante, en utilisant un compteur occ :

In [23]:

def recherche_naive(M: str, T: str) -> int:
    """
    Renvoie le nombre d'occurences de M dans T
    """
    assert (len(M) <= len(T))  # les longueurs du mot et du texte sont compatibles
    n, m = len(T), len(M)
    occ = 0
    indice = 0
    for i in range(n - m + 1):
        if test(M, T, i):
            occ += 1  # on a rencontré M à partir de la position i dans T
    return occ

In [24]:

recherche_naive("bambou", "bambamboum")

Out[24]:

In [25]:

recherche_naive("bam", "bambamboum")

Out[25]:

In [26]:

recherche_naive("bim", "bambamboum")

Out[26]: