Aller au contenu

TD⚓︎

Exercice 1 : Maximum

Que fait la fonction récursive ci-dessous:

def mystere(lst, i = 0, j = None):
    if j is None:
        j = len(lst) - 1
    if i == j:
        return lst[i]
    else:
        milieu = (i + j) // 2
        return max(mystere(lst, i, milieu), mystere(lst, milieu + 1, j))

Exercice 2 : Mediane

  1. Réfléchir à l'utilisation da la méthode "diviser pour régner" pour déterminer la valeur médiane d'un tableau d'entier non trié.

  2. Mise en place: pour réaliser cet algorithme, nous allons chercher la k-ième valeur dans une liste.

    1. Réaliser une fonction sous_listes(lst, pivot) ayant en entrée une liste lstet une valeur de la liste pivot et retournant 3 sous-listes:

      • la sous-liste lst_g des valeurs strictement inférieures au paramètre
      • la sous-liste lst_d des valeurs strictement supérieures au paramètre
      • la sous-liste lst_m des valeurs strictement égales au paramètre

    On a alors trois cas possibles en fonction de la taille de ces trois sous-listes:

    • Si k est inférieur à la taille de la sous-liste de gauche, alors la k-ième valeur est dans la sous-liste de gauche
    • Sinon, si k est inférieur à la somme de la taille de la sous-liste de gauche et la taille de la sous-liste du milieu, alors la k-ième valeur est le pivot.
    • Sinon, la k-ième valeur appartient à la sous liste de droite (mais elle n'est plus la k-ième valeur de cette liste)
    1. Réaliser une fonction récursive rang(lst, k) implémentant cet algorithme.

  3. Le code suivant permet de mesurer le temps d'exécution:

    import timeit
from random import randint

lst = [randint(-100, 100) for i in range(1000)]
l = (len(lst) + 1)//2
lst_trie = sorted(lst)

def affiche_temps():
    print(timeit.timeit("rang(lst, l)", number=1000, globals=globals()))
    print(timeit.timeit("rang(lst_trie, l)", number=1000, globals=globals()))

    il affiche:

    >>> affiche_temps()
0.3120999999991909
0.06440000000293367

    Analyser les temps obtenus. Que pouvez vous en conclure ?

Exercice 3 : Type bac

Cet exercice porte sur la programmation Python (listes, dictionnaires) et la méthode "diviser pour régner".

Cet exercice est composé de trois parties indépendantes. Dans cet exercice, on s'intéresse à des algorithmes pour déterminer, s'il existe, l'élément absolument majoritaire d'une liste.

On dit qu'un élément est absolument majoritaire s'il apparaît dans strictement plus de la moitié des emplacements de la liste.

Par exemple, la liste [1, 4, 1, 6, 1, 7, 2, 1, 1] admet 1 comme élément absolument majoritaire, car il apparaît 5 fois sur 9 éléments. Par ailleurs, la liste [1, 4, 6, 1, 7, 2, 1, 1] n'admet pas d'élément absolument majoritaire, car celui qui est le plus fréquent est 1, mais il n'apparaît que 4 fois sur 8, ce qui ne fait pas plus que la moitié.

  1. Déterminer les effectifs possibles d'un élément absolument majoritaire dans une liste de taille 10.

Partie A : Calcul des effectifs de chaque élément sans dictionnaire⚓︎

On peut déterminer l'éventuel élément absolument majoritaire d'une liste en calculant l'effectif de chacun de ses éléments.

  1. Écrire une fonction effectif qui prend en paramètres une valeur val et une liste lst et qui renvoie le nombre d'apparitions de val dans lst. Il ne faut pas utiliser la méthode count.

  2. Déterminer le nombre de comparaisons effectuées par l'appel effectif(1, [1, 4, 1, 6, 1, 7, 2, 1, 1]).

  3. En utilisant la fonction effectif précédente, écrire une fonction majo_abs1 qui prend en paramètre une liste lst, et qui renvoie son élément absolument majoritaire s'il existe et renvoie None sinon.

  4. Déterminer le nombre de comparaisons effectuées par l'appel à majo_abs1([1, 4, 1, 6, 1, 7, 2, 1, 1]).

Partie B : Calcul des effectifs de chaque élément dans un dictionnaire⚓︎

Un autre algorithme consiste à déterminer l'élément absolument majoritaire éventuel d'une liste en calculant l'effectif de tous ses éléments en stockant l'effectif partiel de chaque élément déjà rencontré dans un dictionnaire.

  1. Recopier et compléter les lignes 3, 4, 5 et 7 de la fonction eff_dico suivante qui prend en paramètre une liste lst et qui renvoie un dictionnaire dont les clés sont les éléments de lst et les valeurs les effectifs de chacun de ces éléments dans lst.
def eff_dico(lst):
    dico_sortie = {}
    for ......... :
        if ... in dico_sortie:
            .....
        else:
            ...
    return dico_sortie
  1. En utilisant la fonction eff_dico précédente, écrire une fonction majo_abs2 qui prend en paramètre une liste lst, et qui renvoie son élément absolument majoritaire s'il existe et renvoie None sinon.

Partie C : par la méthode "diviser pour régner"⚓︎

Un dernier algorithme consiste à partager la liste en deux listes. Ensuite, il s'agit de déterminer les éventuels éléments absolument majoritaires de chacune des deux listes. Il suffit ensuite de combiner les résultats sur les deux listes afin d'obtenir, s'il existe, l'élément majoritaire de la liste initiale.

Les questions suivantes vont permettre de concevoir précisément l'algorithme. On considère lst une liste de taille n.

  1. Déterminer l'élément absolument majoritaire de lst si n = 1. C'est le cas de base.

On suppose que l'on a partagé lst en deux listes :

  • lst1 = lst[:n//2] (lst1 contient les n//2 premiers éléments de lst)
  • lst2 = lst[n//2:] (lst1 contient les autres éléments de lst)

  1. Si, ni lst1 ni lst2 n'admet d'élément absolument majoritaire, expliquer pourquoi lst n'admet pas d'élément absolument majoritaire.

  2. Si lst1 admet un élément absolument majoritaire maj1, donner un algorithme pour vérifier si maj1 est l'élément absolument majoritaire de lst.

  3. Recopier et compléter les lignes 4, 11, 13, 15 et 17 pour la fonction récursive majo_abs3 qui implémente l'algorithme précédent. Vous pourrez utiliser la fonction effectif de la question 2. 

    def majo_abs3(lst):
    n = len(lst)
    if n == 1:
        return ...
    else:
        lst_g = lst[:n//2]
        lst_d = lst[n//2:]
        maj_g = majo_abs3(lst_g)
        maj_d = majo_abs3(lst_d)
        if maj_g is not None:
            eff = ......
            if eff > n/2:
            return ...
        if maj_d is not None:
            eff = ......
            if eff > n/2:
            return ...