<jupyter_start><jupyter_text>notebook consultable, exécutable, modifiable et téléchargeable en ligne :         	- se rendre à : https://github.com/nsi-acot/continuite_pedagogique_premiere- cliquer sur l'icone "launch binder" en bas de page- patienter quelques secondes que le serveur Jupyter démarre- naviguer dans le dossier `"./algorithmique/complexite/"`- cliquer sur le nom de ce notebook  TP Complexité algorithmique **Objectif :** Dans ce TP, vous allez vérifier exprimentalement les complexités que vous avez abordées dans la leçon.Pour cela vous allez mesurer des temps d'exécution de divers algorithmes.  Il va falloir observer le temps d'exécution en fonction de la taille des données en entrée.  Mesurer le temps d'éxécution d'une portion de code.La librairie `timeit` permet de mesurer le temps d'exécution d'un code Python. Pour cela, le code doit être répété un grand nombre de fois pour avoir une mesure pertinente. C'est ce que fait la librairie timeit: répéter le code pour mesurer son temps d'exécutionLe premier argument est le fragment de code dont on mesure le temps.Le deuxième argument : `setup` est un fragment de code exécuté une seule fois.`t.repeat(repeat=1000,number=1)` est la répétition du code spécifié dans `Timer`, le code est éxécuté repeat (ici 1000) fois.Nous prendrons la valeur minimale des temps obtenus<jupyter_code>import timeit 
t=timeit.Timer('sin(1.2)',setup='from math import sin')
min(t.repeat(repeat=1000,number=1)) 

#répète sin(1.2) 1000 fois et prend le plus petit temps d'execution
# On peut vérifier que passer à 10000 exécution ne change pas *beaucoup* le temps d'exécution moyen.
t=timeit.Timer('sin(1.2)',setup='from math import sin')
#CODE A COMPLETER

#répète sin(1.2) 10000 fois et prend le plus petit temps d'execution<jupyter_output><empty_output><jupyter_text>Testons la vitesse de la fonction `max` qui renvoie le maximum d'une liste.   Dans la cellule ci-dessous, vous allez afficher le temps mis par la fonction `max` sur une liste de 50 nombres aléatoires.  Puis dans la cellule suivante, afficher le temps mis par la fonction `max` sur une liste de 500 nombres aléatoires.<jupyter_code># on configure la liste utilisée (ce code sera exécuté une seule fois.)
setup = '''
from random import randint
L = [randint(1,100) for i in range(50)]
'''
# Mesure du temps
t=timeit.Timer('max(L)',setup=setup)
temps = min(t.repeat(repeat=10000,number=1))
print(temps)
# Compléter cette cellule pour afficher le temps d'éxécution sur une liste de 500 éléments.<jupyter_output><empty_output><jupyter_text>Lors du passage d'une liste de 50 éléments à 500 éléments, le temps à été multiplié par **Votre réponse ici**  Expliquez ci-dessous pourquoi c'est cohérent avec le cours.  **Votre réponse ici**  Mesurer le temps d'une fonction à plusieurs paramètres.Pour mesurer le temps d'exécution d'une `fonction` `f` il faut la passer en argument à Timer avec ses arguments.Il y a plusieurs méthodes. La plus simple est de faire appel à la méthode partial de la librairie de programmation fonctionnelle functools qui permet de transformer la fonction f et ses paramètres en une nouvelle fonction avec moins de paramètres.Dans l'exemple, on transforme l'addition en une addition avec la constante 2.<jupyter_code>from functools import partial
def addition(x,y):
    return x+y

add2=partial(addition,2)
##add2 est une fonction d'un seul paramètre.
print(add2(4))<jupyter_output><empty_output><jupyter_text>Au moyen de partial, on peut fournir une fonction à Timer. On construit alors une liste des mesures du temps d'exécution.<jupyter_code># On va stocker les temps d'exécution dans la liste temps
temps = []
for i in range(5):
    # Pour chaque valeur i de 0 à 4 on exécute add2(i) puis on mesure le temps moyen d'exécution
    mesure=timeit.Timer(partial(add2,i))
    t=min(mesure.repeat(repeat=10000,number=1))
    # on ajoute ce temps à la liste temps
    temps.append(t)
    
print(temps)
# Constatez ci-dessous que la liste temps est constituée de 5 temps d'exécution relativements proches.<jupyter_output><empty_output><jupyter_text>Application au calcul de moyenne.Ci dessous, compléter le code de la fonction moyenne<jupyter_code>def moyenne(L):
    """
    Entrée : L liste de flottants
    Sortie : un flottant qui est la moyenne de la liste L
    """
    # Votre code ici
# Tests de la fonction moyenne
assert moyenne([1,2,3,4]) == 2.5
assert moyenne([1,2,3,4,5,6]) == 3.5<jupyter_output><empty_output><jupyter_text>On construit une liste `L` de 100 entiers tirés au hasard entre 1 et 10 000 :<jupyter_code>from random import randint
# Première mesure avec une liste de taille 100
L = [randint(1,10001) for i in range(100)]
mesure=timeit.Timer(partial(moyenne,L))
t=min(mesure.repeat(repeat=10000,number=1))
print(t)

# Seconde mesure avec une liste de taille 1000
###################
# Votre code ici
###################

# Troisième mesure avec une liste de taille 10000
###################
# Votre code ici  #
###################<jupyter_output>9.999894245993346e-08<jupyter_text>Codez la fonction `randlist` ayant :- en entrée : un entier $n$;- en sortie : une liste de taille $n$ constitués d'entier aléatoires entre 1 et 100.On rappelle que `randint(a,b)`renvoie un entier aléatoire entre $a$ et $b$.<jupyter_code>def randlist(n):
    ###################
    # Votre code ici  #
    ###################<jupyter_output><empty_output><jupyter_text>Ci-dessous, nous allons contituer deux listes `x` et `y` contenant respectivement :- la taille des données en entrée (ici la longueur de la liste);- le temps d'exécution de la fonction `moyenne` sur ces entrées.Prennez le temps de chercher à comprendre ce que font chaques instructions avant d'exécuter le code.<jupyter_code>x,y=[],[]
for i in range(1,1000,10):
    mesure=timeit.Timer(partial(moyenne,randlist(i)))
    t = min(mesure.repeat(repeat=100,number=1))
    x.append(i)
    y.append(t)
    
# Combien de fois la fonction moyenne est-elle appelée dans un tour de boucle 
# Réponse : 100 (repeat)<jupyter_output><empty_output><jupyter_text>Et ci-dessous, voici le code permettant d'afficher la courbe de y en fonction de x, c'est à dire le temps d'exécution en fonction de la taille des entrées.Le code n'est pas à savoir reproduire à partir de rien, mais il faudra sans doute l'adapter à d'autre exemples par la suite de ce TP. Donc prennez le temps de chercher à comprendre les instructions.<jupyter_code># Exécutez deux fois cette cellule si le graphique ne s'affiche pas.
import matplotlib.pyplot as plt
plt.rcParams.update({'font.size': 12})
fig = plt.figure(figsize=(10, 10))
plt.plot(x,y,marker='o',label = 'Moyenne de liste')
plt.xlabel('taille n')
plt.ylabel('temps de calcul en secondes [s]')
plt.legend(loc='upper left')
plt.grid()
plt.show()<jupyter_output><empty_output><jupyter_text>Complétez : On constate que la représentation graphique est **Votre réponse ici**Expliquez en quoi cela est cohérent avec le cours.**Votre réponse ici**  Parcours séquentielle d'une liste de liste Dans cette partie, vous allez analyser la vitesse d'exécution d'un code qui parcours une liste de liste.Codez,ci-dessous, une fonction `randlistlist` ayant :- en entrée : un entier $n$;- en sortie : une liste de liste de taille $n \times n$ constitués d'entier aléatoires entre 1 et 100.<jupyter_code>def randlistlist(n):
    ###################
    # Votre code ici  #
    ###################
t = randlistlist(10)
assert (len(t),len(t[0])) == (10,10)<jupyter_output><empty_output><jupyter_text>Codez,ci-dessous, une fonction `double` ayant :- en entrée : une liste L de liste de taille $n \times n$;- en sortie : une liste de liste de taille $n \times n$ constitués des doubles des éléments de L .<jupyter_code>def double(L):
    """
    L est une liste de liste d'entiers
    """
    ###################
    # Votre code ici  #
    ###################
L = [[1,2],[3,4],[5,6]]
assert double(L) == [[2,4],[6,8],[10,12]]<jupyter_output><empty_output><jupyter_text>Ci-dessous, nous allons contituer deux listes x et y contenant respectivement :- la taille des données en entrée ;- le temps d'exécution de la fonction `double` sur ces entrées. Prennez le temps de chercher à comprendre ce que font chaques instructions avant d'exécuter le code.<jupyter_code>x,y=[],[]
for i in range(1,100,10):
    mesure=timeit.Timer(partial(double,randlistlist(i)))
    t=min(mesure.repeat(repeat=100,number=1))
    x.append(i)
    y.append(t)
import matplotlib.pyplot as plt
plt.rcParams.update({'font.size': 12})
fig = plt.figure(figsize=(10, 10))
plt.plot(x,y,marker='o',label = 'Parcours de listes de listes')
plt.xlabel('taille n')
plt.ylabel('temps de calcul en secondes [s]')
plt.legend(loc='upper left')
plt.grid()
plt.show()<jupyter_output><empty_output><jupyter_text>Complétez : On constate que la représentation graphique est **Votre réponse ici**Expliquez en quoi cela est cohérent avec le cours.**Votre réponse ici**  Algorithmes de recherche dans une liste triée.Dans cette partie, nous allons comparer des algorithmes de recherche dans des listes.Un algorithme "naïf" et l'algorithme de dichotomie.  Algorithme naïf Codez,ci-dessous, une fonction `gene_liste_triee` ayant :- en entrée : un entier $n$ positif;- en sortie : une liste de taille $n$ de nombres aléatoire (entre 1 et 100) **triée dans l'odre croissant**.Le code `L.sort()` permet de trier une liste L en place (c'est à dire que L sera triée sans avoir besoin de réaliser une affectation).<jupyter_code>def gene_liste_triee(n :int):
    """
    Entrée : n est un entier, c'est la taille de la liste en sortie
    Sortie : L est une liste d'entiers positifs triée par ordre croissant.
    """
    ###################
    # Votre code ici  #
    ###################<jupyter_output><empty_output><jupyter_text>Codez,ci-dessous, une fonction `recherche_naif` ayant :- en entrée : une liste $L$ de taille $n$ triée dans l'ordre croissant et $c$ un entier.- en sortie : un booléen indiquant l'élément $c$ est dans la liste $L$.<jupyter_code>def recherche_naif(L,c):
    """
    Entrée : L est une liste d'entiers positifs triée par ordre croissant et c est un entier
    Sortie : un booléen qui indique si c est dans la liste L
    """
    ###################
    # Votre code ici  #
    ###################<jupyter_output><empty_output><jupyter_text>Ci dessous, codez l'algorithme de recherche dichotomique comme vu en cours.<jupyter_code>def recherche_dichotomique(L : list,c : float):
    """
    L est une liste triée dans l'odre croissant
    Retourne un booléen indiquant si l'élément c est dans la liste L
    """
    ###################
    # Votre code ici  #
    ###################
L = [2,3,5,7,11,13,17,19,23]
assert recherche_naif(L,23) == True
assert recherche_naif(L,25) == False
assert recherche_naif(L,0) == False
L = [2,3,5,7,11,13,17,19,23]
assert recherche_dichotomique(L,23) == True
assert recherche_dichotomique(L,25) == False
assert recherche_dichotomique(L,0) == False<jupyter_output><empty_output><jupyter_text>Ci-dessous, nous allons contituer deux listes x et y contenant respectivement :- la taille des données en entrée (ici la longueur de la liste;- le temps d'exécution de la fonction `recherche_naif` sur ces entrées. Prennez le temps de chercher à comprendre ce que font chaques instructions avant d'exécuter le code.<jupyter_code>x,y=[],[]
for i in range(1,1000,10):
    mesure=timeit.Timer(partial(recherche_naif,gene_liste_triee(i),42))
    t=min(mesure.repeat(repeat=100,number=1))
    x.append(i)
    y.append(t)
plt.rcParams.update({'font.size': 12})
fig = plt.figure(figsize=(10, 10))
plt.plot(x,y,'-bo',label = 'Recherche naïve')
plt.xlabel('taille n')
plt.ylabel('temps de calcul en secondes [s]')
plt.legend(loc='upper left')
plt.grid()
plt.show()<jupyter_output><empty_output><jupyter_text>Ci-dessous, nous allons contituer deux listes x et **z** contenant respectivement :- la taille des données en entrée (ici la longueur de la liste);- le temps d'exécution de la fonction `recherche_dichotomique` sur ces entrées. Prennez le temps de chercher à comprendre ce que font chaques instructions avant d'exécuter le code.<jupyter_code>x,z=[],[]
for i in range(1,1000,10):
    testTimer=timeit.Timer(partial(recherche_dichotomique,gene_liste_triee(i),42))
    t=min(testTimer.repeat(repeat=10000, number=1))
    x.append(i)
    z.append(t)
plt.rcParams.update({'font.size': 12})
fig = plt.figure(figsize=(10, 10))
plt.plot(x,z,'-ro',label = 'Recherche dichotomique')
plt.xlabel('taille n')
plt.ylabel('temps de calcul en secondes [s]')
plt.legend(loc='upper left')
plt.grid()
plt.show()<jupyter_output><empty_output><jupyter_text>Et enfin, affichons le temps d'exécution sur un même graphique.<jupyter_code>plt.rcParams.update({'font.size': 12})
fig = plt.figure(figsize=(10, 10))
plt.plot(x,y,'--bo',label = 'Recherche naïve')
plt.plot(x,z,'--ro',label = 'Recherche dichotomique')
plt.xlabel('taille n')
plt.ylabel('temps de calcul en secondes [s]')
plt.legend(loc='upper left')
plt.grid()
plt.show()<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.12476979742173112, 'fraction_numerical': 0.02302025782688766, 'mean_word_length': 5.2239732569245465, 'pattern_counts': {'":': 0, '<': 72, '<?xml version=': 0, '>': 72, 'https://': 1, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '18', 'dir': 'jupyter-structured-clean-dedup', 'id': '610606', 'license': 'CC0-1.0', 'n_tokens_mistral': 4830, 'n_tokens_neox': 4582, 'n_words': 1489, 'path': 'algorithmique/complexite/complexite-ELEVES.ipynb', 'repo_name': 'herve-vasseur/python-lycee', 'size': '13032'}