$$\newcommand{\mtn}{\mathbb{N}}\newcommand{\mtns}{\mathbb{N}^*}\newcommand{\mtz}{\mathbb{Z}}\newcommand{\mtr}{\mathbb{R}}\newcommand{\mtk}{\mathbb{K}}\newcommand{\mtq}{\mathbb{Q}}\newcommand{\mtc}{\mathbb{C}}\newcommand{\mch}{\mathcal{H}}\newcommand{\mcp}{\mathcal{P}}\newcommand{\mcb}{\mathcal{B}}\newcommand{\mcl}{\mathcal{L}} \newcommand{\mcm}{\mathcal{M}}\newcommand{\mcc}{\mathcal{C}} \newcommand{\mcmn}{\mathcal{M}}\newcommand{\mcmnr}{\mathcal{M}_n(\mtr)} \newcommand{\mcmnk}{\mathcal{M}_n(\mtk)}\newcommand{\mcsn}{\mathcal{S}_n} \newcommand{\mcs}{\mathcal{S}}\newcommand{\mcd}{\mathcal{D}} \newcommand{\mcsns}{\mathcal{S}_n^{++}}\newcommand{\glnk}{GL_n(\mtk)} \newcommand{\mnr}{\mathcal{M}_n(\mtr)}\DeclareMathOperator{\ch}{ch} \DeclareMathOperator{\sh}{sh}\DeclareMathOperator{\th}{th} \DeclareMathOperator{\vect}{vect}\DeclareMathOperator{\card}{card} \DeclareMathOperator{\comat}{comat}\DeclareMathOperator{\imv}{Im} \DeclareMathOperator{\rang}{rg}\DeclareMathOperator{\Fr}{Fr} \DeclareMathOperator{\diam}{diam}\DeclareMathOperator{\supp}{supp} \newcommand{\veps}{\varepsilon}\newcommand{\mcu}{\mathcal{U}} \newcommand{\mcun}{\mcu_n}\newcommand{\dis}{\displaystyle} \newcommand{\croouv}{[\![}\newcommand{\crofer}{]\!]} \newcommand{\rab}{\mathcal{R}(a,b)}\newcommand{\pss}[2]{\langle #1,#2\rangle} $$
Bibm@th

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

Listes
Exercice 1 - Insertion dans une liste triée [Signaler une erreur] [Ajouter à ma feuille d'exos]
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é
Exercice 2 - Recherche du premier élément d'une liste [Signaler une erreur] [Ajouter à ma feuille d'exos]
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é
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é
Enoncé
  1. É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?
  2. É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$.
  3. Quel est, en fonction de $n$ et $M$, le nombre d'opérations élémentaires effectué par votre fonction $nboc(L)$?
  4. On veut que ce nombre ne dépende pas de $L$. Modifier votre fonction si ce n'est pas le cas.
Indication
Corrigé
Exercice 5 - Recherche par dichotomie dans une liste triée [Signaler une erreur] [Ajouter à ma feuille d'exos]
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

  1. 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)
  2. Que fait la fonction rech_dicho?
  3. 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é