<jupyter_start><jupyter_text><NAME> : DIVISER POUR REGNERLe paradigme "diviser pour régner" fait partie des entrées prépondérentes au bac. I)  Le principeLes 15 joueuses d’une équipe de volleyball ont la liste des joueuses de l’équipe avec leur numéro de téléphone. La capitaine reçoit l’information que le prochain match a été déplacé. Il faut prévenir toutes les autres joueuses. Solution 1 : la capitaine se charge d’appeler toutes les autres joueuses. Si elle passe 5 minutes au téléphone avec chacune d’entre-elles. Question : En combien de temps (noté t1) l’ensemble de l’équipe est informé? En déduire la complexité de cette solution en fonction de n (taille de l’équipe)  Solution 2 : Une solution plus efficace et plus confortable pour la capitaine est qu’elle divise la liste de joueuses en deux moitiés. Elle appelle alors la première joueuse de chacune des deux listes obtenues. Elle leur donne l’information de report de match et leur demande à leur tour de faire la même chose : diviser en deux la demi-liste à laquelle elles appartiennent, appeler la première joueuse de chacune des parties et ainsi de suite … jusqu’à ce qu’il n’y ait plus personne à prévenir.Représentons l’arbre des appels pour la liste de 15 joueuses numérotées de 1 à 15.Question : Si on suppose qu’un appel téléphonique dure 5 min. En combien de temps (noté t2) l’ensemble de l’équipe est informé ? En déduire la complexité de cette solution en fonction de n (taille de l’équipe)  II) Exemples classiques simples :  1) la recherche par dichotomieon dispose d'un tableau de taille n trié, on cherche si une valeur v est présente dans le tableau<jupyter_code>import random
n=100
t = [random.randint(0,1000) for i in range(n)]
t.sort()
print(t)<jupyter_output>[3, 10, 18, 29, 36, 64, 72, 72, 85, 105, 120, 122, 137, 148, 160, 160, 182, 192, 199, 205, 219, 221, 245, 248, 250, 251, 253, 277, 286, 295, 303, 307, 310, 326, 333, 338, 348, 349, 372, 372, 373, 377, 432, 434, 454, 467, 469, 494, 501, 523, 538, 556, 592, 606, 614, 624, 633, 637, 657, 664, 675, 680, 690, 716, 720, 721, 723, 734, 736, 739, 739, 747, 747, 777, 778, 801, 802, 818, 825, 827, 832, 836, 840, 850, 865, 869, 878, 891, 919, 940, 941, 957, 961, 965, 970, 971, 977, 978, 988, 998]<jupyter_text>Méthode naïve : on parcourt le tableau jusqu'à trouver l'élément Quelle est la complexité de cet algorithme ?<jupyter_code>def recherche(v,t):
    """ entree : v valeur, t tableau
        sortie : booleen qui dit si v appartient à t"""
    # à coder<jupyter_output><empty_output><jupyter_text>Méthode par dichotomie : on va passer par une fonction intermédiaire récursive `dicho(v,t,imin,imax)` qui cherche v entre l'indice imin et imaxQuelle est la complexité de cet algorithme ?<jupyter_code>def dicho(v,t,imin,imax):
    """ entree : v valeur, t tableau, imin indice min , imax indicemax où cherché
    sortie : booleen qui dit si v appartient à t entre les indices ci-dessus"""   
    # à coder<jupyter_output><empty_output><jupyter_text>2) L'exponentiation rapide on cherche à calculer x^n = x*x*x*x ....*x (n fois) méthode naïve (mais récursive!)Quelle est la complexité de cet algorithme ?<jupyter_code>def exp(x,n):
    """entrée : x réel, n entier positif
       sortie : la valeur de x^n
    """
    # à coder en récursif !<jupyter_output><empty_output><jupyter_text>méthode "diviser pour régner"on utilise le fait que x^6 = x^3 * x^3on fera attention à la parité de n .Quelle est la complexité de cet algorithme ?<jupyter_code>def exp2(x,n):
    """entrée : x réel, n entier positif
       sortie : la valeur de x^n
    """
    # à coder en récursif !<jupyter_output><empty_output><jupyter_text>3) Exemple moins classique :On cherche le maximum dans un tableau de n valeurs non trié.<jupyter_code>import random
n=100
t = [random.randint(0,1000) for i in range(n)]<jupyter_output><empty_output><jupyter_text>approche naïve : on cherche linéairement le maximum<jupyter_code>def maxi(t):
     """entrée :t tableau non vide
       sortie : la valeur max
    """ 
    # à coder<jupyter_output><empty_output><jupyter_text>approche "diviser pour régner".On découpe le tableau en 2 et on compare les 2 max obtenus.<jupyter_code>def maxi2(t,imin,imax):
    """entrée :t tableau non vide, imin et imax deux indices
       sortie : la valeur max entre imin et imax
    """<jupyter_output><empty_output><jupyter_text>4) Le grand classique du "diviser pour régner" : le tri-fusion<jupyter_code>import random
n=100
t = [random.randint(0,1000) for i in range(n)]<jupyter_output><empty_output><jupyter_text>rappel :  1) on dispose d'une fonction `fusion` qui réunit deux listes triées  2) on découpe le tableau en deux et on trie les parties séparément (on peut ensuite fusionner les résultats<jupyter_code>def fusion(t1,t2):
    """entrée : t1 et t2 deux tableaux triés 
       sortie : un tableau contenant les valeurs triées de t1 et t2"""
    # à coder

def tri_fusion(t):
    """entree: t tableau non vide
      sortie : tableau trié 
    """
     # à coder<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.09692671394799054, 'fraction_numerical': 0.0681639085894405, 'mean_word_length': 4.554704595185996, 'pattern_counts': {'":': 0, '<': 41, '<?xml version=': 0, '>': 41, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 12, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '10', 'dir': 'jupyter-structured-clean-dedup', 'id': '582545', 'license': 'CC0-1.0', 'n_tokens_mistral': 2170, 'n_tokens_neox': 1828, 'n_words': 693, 'path': 'SYNTHESE -  DIVISER POUR REGNER.ipynb', 'repo_name': 'MCHASLE/TNSI', 'size': '5087'}