Algorithmique appliquée

1. dans le contexte de cet exercice, qu'affiche le programme ci-dessous?

   solde = 200
   for annee in range(2018, 2030):
       solde = solde*1.05
   print(solde)
   

2. dans le contexte de cet exercice, qu'affiche le programme ci-dessous?

   solde = 200
   annee = 2017
   while solde<300:
       solde = solde*1.05
       annee = annee + 1
   print(annee)
   

3. En fait l'algorithme ci-dessus ne prend pas en compte les frais fixes de 30 euros par an pour la tenu de ce compte (qui sont prévelés après le versement des intérêts). Modifier maintenant cet algorithme afin qu'il prenne en compte ces frais et pour qu'il affiche l'année où le solde de ce compte est au moins de 400 euros.

Le programme ci-dessous est un "jeu" où l'utilisatur doit trouver une valeur (ici la valeur ne change pas et vaut toujours 10…)

nbr_a_deviner = 10
nbr_correct = False
while not nbr_correct:
    nbr = int(input("Saisir un nombre entier: "))
    if nbr == nbr_a_deviner:
        nbr_correct = True
    else:
        nbr_correct = False
    if not nbr_correct:
        print("Essayez encore une fois")
print("You win!")

1. Recopier puis modifier ce programme pour qu'il affiche "Nombre trop grand" ou bien "Nombre trop petit" suivant la valeur entrée au lieu de simplement afficher "Essayez encore une fois".

On admettra que la fonction suivante nommée est_premier retourne True si et seulement si son argument est un nombre premier.

def est_premier(n):
    if n<=1:
        return False
    for i in range(2,n-1):
        if n%i==0:
            return False
    return True

1. Vérifier que l'appel est_premier(11) retourne True et que que l'appel est_premier(12) retourne False.
2. Écrire un programme qui affiche tous les nombres premiers qui sont inférieurs à 200.
3. Écrire un programme qui affiche les 200 premiers nombres premiers.

1. Écrire une fonction nommée countdown acceptant un unique argument que l'on supposera être un entier strictement positif et qui affiche un compte à rebours à partir de cet entier. Ainsi countdown(4) doit afficher dans l'ordre 4, 3, 2, 1, et enfin 0.
2. Écrire une fonction nommée countdown_boom acceptant un unique argument que l'on supposera être un entier strictement positif et qui affiche un compte à rebours à partir de cet entier tel que countdown_boom(4) affiche dans l'ordre 4, 3, 2, 1, et enfin "Boom".

En partant d'un nombre entier strictement positif, on dresse la liste des nombres entiers obtenus de la façon suivante:

s’il est pair, on le divise par 2; s’il est impair, on le multiplie par 3 et on ajoute 1. Ensuite on répéte l’opération tant que le nombre obtenu est différent de 1 (si l'on obtient 1 alors on s'arrête).

Ainsi si l'on part de 5, on obtient dans l'ordre 16 (car 5 est impair et 3*5+1=16) puis 8 (car 16 est pair et 16/2=8) puis 4 (car 8 est pair et 8/2=4) puis 2 (car 4 est pair et 4/2=2) puis 1 (car 2 est pair et 2/2=1). On vérifie de même que si l'on part de 6 alors on obtient cette fois dans l'ordre: 6, 3, 10, 5, 16, 8, 4, 2, 1.

Les suites de nombres ainsi obtenues sont appelées suites de syracuse. Ainsi 5, 16, 8, 4, 2, 1 est la suite de syracuse obtenue à partir de l'entier 5 et 6, 3, 10, 5, 16, 8, 4, 2, 1 est la suite de syracuse obtenue à partir de l'entier 6.

La fonction suivante nommée terme_suiv_syracuse permet d'obtenir le nombre suivant de la suite si le nombre courant est donné comme paramètre x:

def terme_suiv_syracuse(x):
    if x%2==0:
        return int(x/2)
    else:
        return 3*x+1

• vérifier que les valeurs retournées par les appels terme_suiv_syracuse(5) et terme_suiv_syracuse(16) sont cohérentes.
• afficher les termes de la suite ainsi obtenue si l'on part de l'entier 5 (on utilisera la fonction terme_suiv_syracuse).
• écrire une fonction nommée syracuse qui accepte un unique argument (que l'on supposera de type int) et qui affiche tous les termes de la suite obtenue à partir de l'entier x. Ainsi l'appel syracuse(6) doit afficher dans l'ordre 6, 3, 10, 5, 16, 8, 4, 2 et enfin 1.
• écrire une fonction nommée temps_de_vols_syracuse qui accepte un unique argument (que l'on supposera de type int) et qui retourne le nombre d'entiers de la suite obtenue à partir de l'entier x. Ainsi l'appel temps_de_vols_syracuse(6) doit retourner 9 (car la suite de syracuse 6, 3, 10, 5, 16, 8, 4, 2, 1 est constituée de 9 entiers). On vérifiera que l'appel temps_de_vols_syracuse(27) retourne bien 112.

1. Qu'affiche le script suivant? Expliquer.

   def somme_deux_arguments(x,y):
       return x+y
   
   somme = somme_deux_arguments(11, 12)
   print(somme)
   

2. Définir une fonction produit_deux_arguments qui accepte deux arguments (supposés de type float ou int) et retourne leur produit.
3. Définir une fonction somme_trois_arguments qui accepte trois arguments (supposés de type float ou int) et retourne leur somme.
4. Définir une fonction moyenne_trois_arguments qui accepte trois arguments (supposés de type float ou int) et retourne leur moyenne.

1. Modifier la définition de fonction ci-dessous afin que cette fonction accepte un argument que nous supposerons être une liste puis retourne la somme des éléments de cette liste (ainsi le script ci-dessous devrait afficher 17 car 3+4+10=17 ce qui n'est pas le cas car la définition de la fonction est bogguée).

   def somme_elmt_liste(lst):
       somme_tmp = 1
       for elmt in lst:
           somme_tmp = elmt
       return somme_tmp
   
   somme = somme_elmt_liste([3, 4, 10])
   print(somme)
   

2. Définir une fonction qui accepte un argument que nous supposerons être une liste puis retourne le produit des éléments de cette liste. On vérifiera que cette fonction retourne bien 120 lorsqu'elle est appelée avec l'argument [1,2,3,4,5].

Un élève a 500 euros sur son compte. Son compte est rémunéré à 5%, c'est à dire que le solde est multiplié par 1,05 par chaque année. Il a alors défini une fonction en Python nommée prediction_solde qui accepte en argument le solde initial et le nombre d'annee et retourne le solde de ce compte apres ce nombre d'années. Cette fonction est donnée ci-dessous

def prediction_solde(solde_init, nbr_annee):
    solde_tmp = solde_init
    for annee in range(nbr_annee):
        solde_tmp = solde_tmp*1.05
    return solde_tmp

1. Copier cette définition dans un script puis appeler cette fonction pour afficher le solde de ce compte après 10 ans (vous devez trouver environ 814.447313388721).
2. En fait les frais de gestion de compte sont de 17,7 euros par an (somme qui est prélevée avant la rémunération à 5%). Définir une nouvelle fonction prediction_solde2 qui accepte en argument le solde initial et le nombre d'annee et retourne le solde de ce compte apres ce nombre d'années. Vérifier que le solde après 10 ans est maintenant de environ 580,69 euros.

1. Définir une fonction un_elmt_en_commun acceptant deux arguments que l'on supposera être de type list et qui retourne True si ces deux listes ont au moins un élément en commun et False dans le cas contraire. Ainsi l'appel un_elmt_en_commun([1,2],[4,3,7]) doit renvoyer False, l'appel un_elmt_en_commun([1,2],[4,2,7]) doit renvoyer True et l'appel un_elmt_en_commun([1,2,7],[1,2,7]) doit aussi renvoyer True.
2. Définir une fonction un_elmt_en_commun acceptant deux arguments que l'on supposera être de type list et qui retourne True si ces deux listes ont au moins un élément en commun et False dans le cas contraire. Ainsi l'appel un_elmt_en_commun([1,2],[4,3,7]) doit renvoyer False, l'appel un_elmt_en_commun([1,2],[4,2,7]) doit renvoyer True et l'appel un_elmt_en_commun([1,2,7],[1,2,7]) doit aussi renvoyer True.

On s'interesse au cryptage où le caractère d'indice n (où n est compris entre 0 et 25) est crypté en le caractère d'indice (21*n+5)% 26. Ainsi le caractère "A"

• qui est d'indice indice_lettre("A"), c'est à dire 0;
• est crypté en le caractère d'indice (21*0+5)% 26, soit d'indice 5;
• c'est à dire en lettre_d_indice(5), soit en "F"

Les étapes ci-dessous sont transcrites en python ci-dessous

indice_lettre_depart = indice_lettre("A")
indice_lettre_cryptee = (21*indice_lettre_depart+5)% 26
lettre_cryptee = lettre_d_indice(indice_lettre_cryptee)
print(lettre_cryptee)

1. Vérifier comme ci-dessus que le caractère "B" est crypté en le caractère "A".
2. Écrire une fonction nommée cryptage_a21_b5_car qui accepte un argument que nous supposerons être un caractère majuscule non accentué et qui retourne le caractère crypté. Vérifier que les valeurs retournées par les appels cryptage_a21_b5_car("A") et cryptage_a21_b5_car("B") sont cohérentes.
3. Écrire une fonction cryptage_a21_b5_str qui accepte un unique argument que nous supposerons de type str et retourne cette chaîne de caractères cryptée caractère par caractère à l'aide de la fonction cryptage_a21_b5_car (ainsi l'appel cryptage_a21_b5_str("AB") doit retourner "FA" car cryptage_a21_b5_car("A") retourne "F" et cryptage_a21_b5_str("B") retourne A). Pour cela on rappelle que l'operateur de concaténation en python est + (donc par exemple print("M." + " " + "Bosché") affiche "M. Bosché").
4. 1. Écrire deux fonctions nommées cryptage_a5_b1_car et cryptage_a5_b1_str analoguent à cryptage_a21_b5_car et cryptage_a21_b5_str mais où le caractère d'indice n est crypté en le caractère d'indice (5*n+1)% 26. On vérifiera que l'appel cryptage_a5_b1_car("A") retourne B.
   2. Afficher la valeur retournée par cryptage_a5_b1_str(cryptage_a21_b5_str("HELLOWORLD")). À quoi correspont la fonction cryptage_a5_b1_str pour la fonction de cryptage cryptage_a21_b5_str?

5. Écrire une fonction nommée cryptage_a_b_car

   • qui accepte trois arguments que nous appellerons a, b et l où nous supposerons que a et b sont des entiers et l un caractère majuscule non accentué
   • et qui retourne la lettre d'indice (a*n+b)% 26.

   On vérifiera que l'appel cryptage_a_b_car(21,5,"A") retourne la même chose que cryptage_a21_b5_car("A") à savoir "F".

6. Écrire une fonction cryptage_a_b_str qui accepte trois arguments que nous appellerons a, b et l où nous supposerons que a et b sont des entiers et l une chaîne de caractères majuscules non accentués et qui retourne la chaîne de caractère obtenue en cryptant l lettre par lettre à l'aide de cryptage_a_b_str. On vérifiera que l'appel cryptage_a_b_str(21, 5, "AB") retourne "FA".

Décrypter le texte suivant en sachant qu'il est obtenu par l'appel cryptage_a_b_str(a, b, texte) où texte est un texte écrit en français (la ponctuation et les espaces ont été enlevés ainsi que les accents) et a et b sont des entiers (que l'on peut supposer compris entre 0 et 25). Aide: parmi les 26*26=676 combinaisons possibles pour les entiers a et b, on pourra ne s'intéresser qu'aux combinaisons qui à partir de texte_crypte produisent une chaîne de caractères comportant au moins 50 caractères "R", 30 caractères "A", moins de 10 caractères "Z" et moins de 10 lettre "W".

texte_crypte="WVXIVEIVXVAMNAMXGBEVBEWVKINARNDXRPAXMDMBVXVANXXVLCWVVANMDPANWVRPAXDGVINAMTBVWDZAPINARVWPBCWDPBWVLVEIDXGVXGIPDMXGVWOPLLVXPAMWVXXVBWVXRNBXVXGVXLNWOVBIXEBCWDRXVMGVWNRPIIBEMDPAGVXZPBQVIAVLVAMXPAMIVXPWBGVUEPXVIGNAXBAVGVRWNINMDPAXPWVAAVWWVWVXGIPDMXANMBIVWXDANWDVANCWVXVMXNRIVXGVWOPLLVNKDATBVRVMMVGVRWNINMDPARPAXMNLLVAMEIVXVAMVNMPBXWVXLVLCIVXGBRPIEXXPRDNWWVBIINEEVWWVXNAXRVXXVWVBIXGIPDMXVMWVBIXGVQPDIXNKDATBVWVXNRMVXGBEPBQPDIWVZDXWNMDKVMRVBUGBEPBQPDIVUVRBMDKEPBQNAMVMIVNRONTBVDAXMNAMRPLENIVXNQVRWVCBMGVMPBMVDAXMDMBMDPAEPWDMDTBVVAXPDVAMEWBXIVXEVRMVXNKDATBVWVXIVRWNLNMDPAXGVXRDMPJVAXKPAGVVXGVXPILNDXXBIGVXEIDARDEVXXDLEWVXVMDARPAMVXMNCWVXMPBIAVAMMPBSPBIXNBLNDAMDVAGVWNRPAXMDMBMDPAVMNBCPAOVBIGVMPBX"

La question précédente a montré que le fait de crypter un même caractère toujours de la même façon fragilise la méthode de cryptage. On décide donc de crypter des blocs de deux caractères d'un coup au lieu de crypter les caractère un à un. Pour crypter une chaîne constituée de deux caractères:

• on récupère l'indice x de la première lettre;
• on récupère l'indice y de la seconde lettre;
• le première caractère de la chaîne cryptée sera alors la lettre d'indice (x+9*y) % 26 et le second la lettre d'indice (15*x+6*y) % 26.

En python, le cryptage de la chaîne "AB" s'écrit donc

msg = "AB"
x = indice_lettre(msg[0])
y = indice_lettre(msg[1])
x_crypte = (x+9*y) % 26
y_crypte = (15*x+6*y) % 26
lettre_1_crypt = lettre_d_indice(x_crypte)
lettre_2_crypt = lettre_d_indice(y_crypte)
msgc = lettre_1_crypt + lettre_2_crypt
print(msgc)

1. Vérifier que "CD" est crypté en "DW" .
2. Écrire une fonction nommée crypt_a1_b9_c15_d6_bloc qui accepte une chaîne de caractère dont on supposera qu'elle est de longueur 2 et qui retourne la chaîne cryptée. On vérifiera que l'appel crypt_a1_b9_c15_d6_bloc("BO") retourne "XV".
3. Pour crypter une chaîne de longueur quelconque on doit tout d'abord commencer par la concatener avec "Z" si sa longueur est impaire afin d'obtenir une chaîne de longueur paire. Écrire une fonction nommée remplissage qui accepte un unique argument que l'on supposera être une chaîne de caractères et qui retourne la même chaîne si sa longueur est paire et la chaîne concatenée avec "Z" sinon. On vérifiera que l'appel remplissage("SIO") retourne "SIOZ" et que l'appel remplissage("BOOM") retourne "BOOM".
4. Écrire une fonction nommée crypt_a1_b9_c15_d6_str qui accepte un unique argument que l'on supposera de type str et retourne cette chaîne une fois cryptée. On vérifiera que l'appel crypt_a1_b9_c15_d6_str("JEDETESTELEPROFDEMATH")) retourne "TDNRDXHUZWJUNBGPICPKYV".

5. À cette question on transforme une chaîne de deux caractères de la façon suivante:

   • on récupère l'indice x de la première lettre;
   • on récupère l'indice y de la seconde lettre;
   • le première caractère de la chaîne cryptée sera alors la lettre d'indice (6*x+17*y) % 26 et le second la lettre d'indice (11*x+y) % 26.

   Questions:

   1. Écrire une fonction nommée trans_a6_b17_c11_d1_bloc qui accepte une chaîne de caractère dont on supposera qu'elle est de longueur 2 et qui retourne la chaîne transformée comme expliquée ci-dessus.
   2. Observer ce que retournent trans_a6_b17_c11_d1_str(crypt_a1_b9_c15_d6_str("LAVIEENROSE")) et trans_a6_b17_c11_d1_str(crypt_a1_b9_c15_d6_str("HELLOWORLD")). À votre avis, qu'est trans_a6_b17_c11_d1_str pour la fonction de cryptage crypt_a1_b9_c15_d6_str?

En cryptant les messages comme dans les deux questions précédentes mais avec d'autres coefficients (ainsi il existe des entiers a,b,c,d que l'on peut supposer compris entre 0 et 25 tels que la chaîne obtenue à partir d'une chaîne de longueur 2 soit celle dont la première lettre est d'indice (a*x+b*y) % 26 et la seconde celle d'indice (c*x+d*y) % 26…) on a obtenu le texte crypté ci-dessous

texte_crypte = "SDSUYQGOAJRFOCRGUYRFUXVUQAHYBJSDEIJJGZALLZWYBMAEUKDFBXRDEYNAOCKETYDHMNULUGOORKPJBPUYRFWTGVNNDHMNGZDFOKRFANEWUMULOCWYGZDFUYAJITMNMPYVPJWLYRXDEDEIHRXFBJYRMAHEOCSBOJWRWGIILSEQPTEDAWUECWVUYIPFTPXLBVXFBJGZBXSZULNZOCMAOJQHLZEVNYGKYRPIUVIKXUOCSGIJRFZAVHIIIDXUOIVHQAYVGZUMSUYQGOAJRFLJXFRDEYNAOCSJDFATVUIIELGVRDUVFOGIDHWZNNUMXDFBEWVHQANAXLKSSDQHAJRFJGQUSDXUGICSIILSOCOJUFEOATVUALSDIKIXKCMNCZSZOHEIUEQSWEJJGZSUOCRFSPRFELGVEQUMLZOHBXCABVQAYVALSDLOAMGZKCEXGZKATBIAOPALIIJPQUYVEDQNKJBXIAUXVUUVFOGIDHSPRFPTBVQSINOJYIEYKCVHQAYVWYVVOCRDUXEVANCIFBALJTBVJGQUSDXUHRJJIARQXFEDIIVUNNRGYOTPZDBXIAUXVUUYSWDTUVLOWYNBOCUYMNMSAJGZUMEYANCDTBEWZAVHQAANGZIJXFAJRFALUMDROCALOHBXCABVQAVUWYMNYIEYKCVHQALIRFALOCDFPJKSSGIIWYDHYHHRPJBRYPAJLSAMBVKSRFZACSEDSGHAGKUMLZORNAOCGUIAOPWYEIGODFCSFCWYNGXDALSJLORDVHMNTBMNTPTBMNZNBVHRXDRDSZIDHXDHVHQAANGZYRSDELGVRDXFZVUVIKTBHRKQWYUXDUGIDHMNPTSTLSEQPODHVLBPIVTYWYOFGIFOHRPJQUSUYQGOAJRFWTXDIIBWLBHXRDDHIDXDMNDTUMJGOCIXUKKEVUALOKZZEWVHQAYVKSUPOCLBALSDNAEQSWDFNNMNKZKZCNYRVUIDXDKSSDAEKSRFZACSEDIDXDQUSUYQGOAJRFEIVTWYNYKMZMDHHXSDIKIXKCMNCZSZOHEIXFEDYHXFBJSDLOAMGZWEFIFZQHLBEDEDRKQSADXUKYQSIXJWOCEYTBLJOCOCELRKVHIAOPSDALBZBJVHQAHYEDTPXZGZDHIIQHUZBVQUDFXFEDIIVUNNPOJJLBVHMPYVGZALIXLOGIDHIDVLYIEYKCVHQAANDFYIRFWEYOOCYQGOGZLSBPRDUYRFANBVEDGZAJZAEQRGBRYPPOJJYIEYKCVHQATCOCUKMAALIIIIYRXUEWIIKEVUIIRGOCKZUQJGPNOCWERFIIPOUGAMZDOCLBANAJRFTPBVOCALWGLZEIGOPJAJZAUEQSMBRFEIOCRFSPCJYBOCALEYANCDTBEWZAVHQASTOJCHDTSDHXHROCPTVHXDIIPTUFTBYRSDALBZBJVHQACFQLRDRXRFOJEDWGKPSUHRKSJJGZKCMPYVGZALSDXLKSTBLTWYOPCPOPEIJJYIEYKCVHQAANDFYIRFWEYOOCYQGOSDGZZANNMAJWRXKSSDQHAJRFJGQUSDXUXFEDYHQUSDUVOJHLEDWGALVUIIQHUZBVQUDFXFEDIIVUNNPOJJLBVHMPYVGZALIXLOGIDHIDQSPTWEQXJJOCUKMAALEYHYSZULNZTPLBXZUVSUGIDHRGYIEYKCVHQANAOCZADHEVXFZVUVEIUEQSIXINOJTBIILOQAANBNWYDUTPPNWRKCJJMSXSATEVDRQARKKSRDKSXFEWIIGZUMSUYQGOAJRFSURFTYDHQSLJBPCSEDSWNACSZAHRNNNBOCZAGKKAGKPTWYNBOCNDNNMAKEVUSUDFUXSTLJNNNBIAQHCDTBEWZAVHQAANTBWEEILBWYMNNBOCGUOHWRIKAJRFUMPIFBMNOCTPIAOPPTVHXDOKOCGUOHWRIKAJRFIISPCJIHGIDHWZOJEYVULDSJUMXUOCSGJSUKOPEIHLBJAJHEBNWYATEOQLSGATVULBHRKSSDEDPTWYMNYIEYKCVHQABWYOVLUKEDKEVUALBZBJEQWTXDUMYVSGAQOJSGIDSZUMAJRFBXKSGOGZOCMNEDZEAEAJWGEDWGQNHXALLJRFKANNQSQLCSYVKYQSALLJRFLJLBXZUVSUGIDHWZEVAJUVMNADXUKYQSUYEIRDHXVHBVEDRFRDIAVWCAIIALEDYRCDTBEWZARDDHALMVOPALSUZVUXVUQAYVALGZYRPOOCEDAWRFLJOCALIXLOGIDHWZALOKUGOOOJIIPOJJIAOPLBXZUVSUGIDHWZADXUAMNBOCSWAJUMAJRFLJOCOCKETHEDNBJJYQTPALPTTBQUSDCDTBEWZAVHQARKJJYIEYKCVHQAOJYRSDEDPJQARKOCOCKETHEDNBOCWCKEZVGZSUZAAMMNKEVUOJWGSUCSEDUMSDCIUGBMEWIIKEVUEVWLCBQSLSOCXFATSJIIGZUMSUYQGOAJRFLJKSSDEDOCALADEWZAGKUMYVSGGUTBIIPORFRGDHIITHGZALUMDRVTBVOCOCOFDHAJRFOJSGVCUCRKJJBJAJBZHRIAIJDHPOWUVPYODHRDTPALWEDTZZBXIAUXVUDHWYZAQUUYWGDERDGZNBDNRDTPBVOCDHZAFZRJEYXDOCYRKEVUCSEDLJNNLJOCSWRKBVQAYVWRCHOCTPBJAJBZDHIAOXDHPOPREVSWALKCITPCSJSUHRRDLBRXYACFPTEDLOWYWEMWIAXUOCUYEIEWVHBVEDZNVHEORGOCKCEXEOGIQUIIDEUKKETPTBQULJJHEDIIVUBJAJBZOCHLBMKYQSVUUMYVSWRKBVQARKNNKCDHOJMNSGOLSUYQGOAJRFUMSQVUSJDFWLMNIJKJWENOYIWEPTNNWGSDGXDHUZEWNNWGWYSDEDNDRDNDOCKCDHAJWREIAGSKHRAMTPHRKSSDEDOCPFNNRGRXVHHRXFATOOAXVHQARKTV"

Décrypter ce message en sachant que le message de départ contient le mot "IMPOT"

Compléter les programme suivant afin qu'il affiche la liste [5,8,9,4] triée à l'aide du tri à bulle.

L = [5,8,9,4]
liste_triee_bool = False
while not liste_triee_bool:
    liste_triee_bool = True
    for i in range(len(L)-1):
        if L[i] > L[i+1]:
            tmp = L[i]
            ... = ...
            ... = ...
            liste_triee_bool = ...
print(L)

1. Écrire une fonction nommée tri_a_bulle_en_place qui accepte un unique argument que l'on supposera être une liste de nombres et qui trie cette liste.
2. Écrire une fonction nommée tri_a_bulle_sans_effet_de_bord qui accepte un unique argument que l'on supposera être une liste de nombres et retourne cette liste triée sans modifier cette liste (Autrement dit on commencera par créer une copie de la liste passée en argument).

• ajouter au tout début de ce script les lignes suivantes (qui importent des modules python, le premier s'appelant timeit et permet de chronométrer des portions de code, et le second s'appelant matplotlib.pyplot et permettant de tracer des graphiques)

  import time
  import gc
  import random
  import matplotlib.pyplot as plt
  

• ajouter à la fin du script les lignes suivantes (qui définissent une fonction qui trace le temps que met en moyenne votre fonction tri_a_bulle_en_place à trier une liste en fonction de la taille de cette liste)

  def performance_tri_a_bulle(taille_max, nbr=40):
      """Affiche le temps nécessaire en moyenne pour trier une liste avec le
      tri à bulle en fonction de la taille de cette liste.
  
      Args:
        taille_max: considérer les liste de longueur comprises entre 0
                    et taille_max.
        nbr: nombre de valeurs pour le calculs des moyennes.
      Retourne:
        None
      """
      plt_x = [None]*(taille_max+1)
      plt_y = [None]*(taille_max+1)
      i = 0
      for taille in range(1,taille_max+1):
          i += 1
          temps_cumule = 0
          gc.disable()
          for j in range(nbr):
              L = [random.randint(0,255) for xx in range(taille)]
              t_avant = time.clock()
              tri_a_bulle_en_place(L)
              t_apres = time.clock()
              temps_cumule += (t_apres-t_avant)*1000
          gc.enable()
          gc.collect()
          plt_x[i] = taille
          plt_y[i] = temps_cumule/nbr
      fig = plt.figure()
      ax = fig.add_subplot(111)
      ax.plot(plt_x, plt_y, 'or', label="Tri à bulle")
      ax.set_title("Temps pour trier une liste avec le tri à bulle en fonction\n" +
                "de la taille de la liste.")
      ax.set_xlabel("Taille de la liste")
      ax.set_ylabel("Temps (en ms)")
      legend = ax.legend(loc='upper center', shadow=True)
      plt.show()
  
  performance_tri_a_bulle(100)
  

• Exécuter ce script et observer le graphique. Pour trier une liste deux fois plus longue, faut-il à votre avis plus de deux fois plus de temps en général?

Copier la définition de tri_a_bulle_en_place en une nouvelle fonction tri_a_bulle_en_place_ameliore et améliorer les performances de cette fonction de tri en observant

1. que après le ieme parcourt les derniers i éléments sont déjà à leur place;
2. qu'il est inutile de reprendre le parcourt en début de liste à chaque fois mais uniquement à partir de la position précédent le premier échange du parcours précédent puisque les éléments situant avant ce premier échange sont dans l'ordre croissant.

Aide: on gardera et actualisera en mémoire le numéro de parcourt courant dans une variable nommée num_parcours_courant ainsi que la position du précédent échange dans une variable nommée pos_premier_echange (que l'on initialisera à 0).

Vérifier que l'appel tri_a_bulle_en_place_ameliore([[5,1,3,2,0]) renvoie un résultat cohérent.

Compléter les programme suivant afin qu'il affiche la liste [5,8,9,4] triée à l'aide du tri par sélection.

lst_a_trier = [8,5,9,4]
for i in range(1, len(lst_a_trier)):
    elmt_courant = lst_a_trier[i]
    j=i
    while j>0 and lst_a_trier[j-1]>elmt_courant:
        lst_a_trier[j] = lst_a_trier[...]
        j = j-1
    lst_a_trier[...] = elmt_courant

• ajouter (si elles n' sont pas déjà) au tout début de ce script les lignes suivantes (qui importent des modules nécessaires pour la suite)

  import time
  import random
  import gc
  import matplotlib.pyplot as plt
  

• ajouter à la suite la définition de la fonction tri_a_bulle_en_place écrite au TP précédent

• ajouter à la suite du script les lignes suivantes (où est définie puis appelée une fonction performance_tri_par_sélection qui tracent le temps que met en moyenne votre fonction tri_par_sélection à trier une liste en fonction de la taille de cette liste)

  def performance_tri_par_sélection(taille_max, nbr=40):
      """Affiche le temps nécessaire en moyenne pour trier une liste avec le
      tri par sélection en fonction de la taille de cette liste.
  
      Args:
        taille_max: considérer les liste de longueur comprises entre 0
                    et taille_max.
        nbr: nombre de valeurs pour le calculs des moyennes.
      Retourne:
        None
  
      """
      plt_x = [None]*(taille_max+1)
      plt_y = [None]*(taille_max+1)
      i = 0
      gc.disable()
      for taille in range(1,taille_max+1):
          gc.collect()
          i += 1
          temps_cumule = 0
          for j in range(nbr):
              L = [random.randint(0,255) for xx in range(taille)]
              t_avant = time.clock()
              tri_par_insertion_en_place(L)
              t_apres = time.clock()
              temps_cumule += (t_apres-t_avant)*1000
          plt_x[i] = taille
          plt_y[i] = temps_cumule/nbr
      fig = plt.figure()
      ax = fig.add_subplot(111)
      ax.plot(plt_x, plt_y, "og", label="Tri par sélection")
      ax.set_xlabel("Taille de la liste")
      ax.set_ylabel("Temps (en ms)")
      legend = ax.legend(loc='upper center', shadow=True)
      gc.enable()
      plt.show()
  
  performance_tri_par_sélection(100)
  

• ajouter au tout début de ce script les lignes suivantes

  import time
  import random
  import gc
  import matplotlib.pyplot as plt
  

• ajouter à la fin du script les lignes suivantes (qui tracent le temps que met en moyenne votre fonction tri_par_sélection à trier une liste en fonction de la taille de cette liste)

  def performance_tri_par_insertion_et_a_bulle(taille_max, nbr=40):
      """Affiche le temps nécessaire en moyenne pour trier une liste avec le
      tri par sélection en fonction de la taille de cette liste.
  
      Args:
        taille_max: considérer les liste de longueur comprises entre 0
                    et taille_max.
        nbr: nombre de valeurs pour le calculs des moyennes.
      Retourne:
        None
  
      """
      plt_x = [None]*(taille_max+1)
      plt_y1 = [None]*(taille_max+1)
      plt_y2 = [None]*(taille_max+1)
      i = 0
      for taille in range(1,taille_max+1):
          i += 1
          temps_cumule_tri_sel = 0
          for j in range(nbr):
              L = [random.randint(0,255) for xx in range(taille)]
              t_avant = time.clock()
              tri_a_bulle_en_place(L)
              t_apres = time.clock()
              temps_cumule_tri_sel += (t_apres-t_avant)*1000
          plt_x[i] = taille
          plt_y1[i] = temps_cumule_tri_sel/nbr
          temps_cumule_tri_sel = 0
          for j in range(nbr):
              L = [random.randint(0,255) for xx in range(taille)]
              t_avant = time.clock()
              tri_par_insertion_en_place(L)
              t_apres = time.clock()
              temps_cumule_tri_sel += (t_apres-t_avant)*1000
          plt_y2[i] = temps_cumule_tri_sel/nbr
      fig = plt.figure()
      ax = fig.add_subplot(111)
      ax.plot(plt_x, plt_y1, 'or', label="Tri à bulle")
      ax.plot(plt_x, plt_y2, 'og', label="Tri par sélection")
      ax.set_title("Comparaison du tri à bulle et du tri par insertion")
      ax.set_xlabel("Taille de la liste")
      ax.set_ylabel("Temps (en ms)")
      legend = ax.legend(loc='upper center', shadow=True)
      plt.show()
  
  performance_tri_par_insertion_et_a_bulle(100)
  

Le script ci-dessous définit une autre fonction de tri nommée tri_qsort_en_place qui implémente un algorithme de tri appelé quick-sort et connu comme étant particulièrement rapide (inutile de comprendre comment fonctionnne cet algorithme) puis affiche les performances de ce tri de avec celles des deux tris précédents

import time
import gc
import random
import matplotlib.pyplot as plt

def tri_qsort_en_place_aux(l, fst, lst):
    if fst >= lst:
        return
    i, j = fst, lst
    pivot = l[fst]
    while i <=j:
        while l[i] < pivot:
            i += 1
        while l[j] > pivot:
            j -= 1
        if i<=j:
            l[i], l[j] = l[j], l[i]
            i, j = i+1, j-1
    tri_qsort_en_place_aux(l, fst, j)
    tri_qsort_en_place_aux(l, i, lst)

def tri_qsort_en_place(l):
    tri_qsort_en_place_aux(l, 0, len(l)-1)

def performance_tri_par_insertion_et_a_bulle_et_qsort(taille_max, nbr=40):
    """Affiche le temps nécessaire en moyenne pour trier une liste avec le
    tri par sélection en fonction de la taille de cette liste.

    Args:
      taille_max: considérer les liste de longueur comprises entre 0
                  et taille_max.
      nbr: nombre de valeurs pour le calculs des moyennes.
    Retourne:
      None

    """
    plt_x = [None]*(taille_max+1)
    plt_y1 = [None]*(taille_max+1)
    plt_y2 = [None]*(taille_max+1)
    plt_y3 = [None]*(taille_max+1)
    i = 0
    gc.disable()
    for taille in range(1,taille_max+1):
        gc.collect()
        i += 1
        temps_cumule_tri_sel = 0
        for j in range(nbr):
            L = [random.randint(0,255) for xx in range(taille)]
            t_avant = time.clock()
            tri_a_bulle_en_place(L)
            t_apres = time.clock()
            temps_cumule_tri_sel += (t_apres-t_avant)*1000
            gc.collect()
        plt_x[i] = taille
        plt_y1[i] = temps_cumule_tri_sel/nbr
        temps_cumule_tri_bulle = 0
        for j in range(nbr):
            L = [random.randint(0,255) for xx in range(taille)]
            t_avant = time.clock()
            tri_par_insertion_en_place(L)
            t_apres = time.clock()
            temps_cumule_tri_bulle += (t_apres-t_avant)*1000
        plt_y2[i] = temps_cumule_tri_bulle/nbr
        temps_cumule_tri_qsort = 0
        for j in range(nbr):
            L = [random.randint(0,255) for xx in range(taille)]
            t_avant = time.clock()
            tri_qsort_en_place(L)
            t_apres = time.clock()
            temps_cumule_tri_qsort += (t_apres-t_avant)*1000
        plt_y3[i] = temps_cumule_tri_qsort/nbr
    gc.enable()
    fig = plt.figure()
    ax = fig.add_subplot(111)
    ax.plot(plt_x, plt_y1, 'or', label="Tri à bulle")
    ax.plot(plt_x, plt_y2, 'og', label="Tri par sélection")
    ax.plot(plt_x, plt_y3, 'ob', label="Tri qsort")
    ax.set_title("Comparaison du tri à bulle, du tri par insertion et du tri qsort")
    ax.set_xlabel("Taille de la liste")
    ax.set_ylabel("Temps (en ms)")
    legend = ax.legend(loc='upper center', shadow=True)
    plt.show()

performance_tri_par_insertion_et_a_bulle_et_qsort(100)

Ce tri vous paraît-il réellement plus performant?

1. Dans un fichier, afficher les valeurs renvoyées par les expression "AB"<"BA", "BA"<"BA" et "AAA"<"A" . À quel ordre sur les chaînes de caractère correspond l'opérateur relationel < en python?
2. Recopier la définition de votre fonction tri_par_insertion_en_place au début d'un nouveau script puis afficher la valeur renvoyée par l'expression tri_par_insertion_en_place(["AB", "BA", "AA", "BB", "AAAA", "BBB"]). Qu'en pensez-vous?

1. Dans un fichier, afficher les valeurs renvoyées par les expression [1, 7]<[2, 8], [1, 7]<[1, 1], [3, 4]<[2, 5] et [2, 5]<[2, 5, 5]. À quel ordre sur les listes correspond l'opérateur relationel < en python (grosse aide)?
2. Recopier la définition de votre fonction tri_par_insertion_en_place au début d'un nouveau script puis afficher la valeur renvoyée par l'expression tri_par_insertion_en_place([[1, 7], [2, 8], [1, 1], [3, 4], [2, 5], [2, 5, 5]]). Qu'en pensez-vous?

1. Écrire une fonction de comparaison inf_strict_comp_long_puis_ordre_alpha qui compare deux chaînes de caractères par leur longueur puis (si elles sont de même longueur) en utilisant l'ordre alphabétique. Ainsi cette fonction doit accepter deux arguments (que nous supposerons être des chaînes de caractères) et doit

   • retourner True si le première chaîne de caractère est de longueur strictement plus petite que la seconde (rappel: si c est une chaîne alors len(c) est la longueur de cette chaîne);
   • retourner True si les deux chaînes ont même longueur et la première est strictement plus petite que l'autre dans l'ordre alphabétique (rappel: d'après le premier exercice de ce TP, la chaîne c1 est avant la chaine c2 pour l'ordre alphabétique si et seulement si l'expression c1 < c2 retourne True);
   • retourner False sinon.

   On pourra s'aider du squelette suivant

   def inf_strict_comp_long_puis_ordre_alpha(c1, c2):
       if len(c1) < len(c2):
           return ...
       elif len(c1) == len(c2):
           if c1 < c2:
               ...
           else:
               ...
       else:
           ...
   

   À la suite de ces définitions on affichera les valeurs retournées par les appels inf_strict_comp_long_puis_ordre_alpha("AA", "B"), inf_strict_comp_long_puis_ordre_alpha("AA", "AB") et inf_strict_comp_long_puis_ordre_alpha("DD", "ABC") et on s'assurera que les valeurs affichées sont cohérentes.

2. Écrire la définition d'une fonction tri_comp_long_puis_ordre_alpha_en_place qui trie (en utilisant l'algorithme de tri à bulle ou le tri par sélection, à votre guise) une liste de chaînes de caractères en utilisant l'ordre défini par la fonction inf_strict_comp_long_puis_ordre_alpha (c'est à dire que qu'une chaîne c1 sera considérée strictement inférieur à une autre chaîne c2 si et seulement si l'appel inf_strict_comp_long_puis_ordre_alpha(c1, c2) retourne True). On affichera la valeur retournée par l'appel tri_comp_long_puis_ordre_alpha_en_place(["AB", "BA", "AA", "BB", "AAAA", "BBB"]) et on vérifiera sa cohérence.

1. Écrire une fonction de comparaison inf_strict_comp_inv_long_puis_ordre_alpha qui compare deux chaînes de caractères dans l'ordre inverse de leur longueur puis (si elles sont de même longueur) en utilisant l'ordre alphabétique.

   À la suite de ces définitions on affichera les valeurs retournées par les appels inf_strict_comp_inv_long_puis_ordre_alpha("AA", "B"), inf_strict_comp_inv_long_puis_ordre_alpha("AA", "AB") et inf_strict_comp_inv_long_puis_ordre_alpha("AA", "ABC").

2. Écrire la définition d'une fonction tri_comp_inv_long_puis_ordre_alpha_en_place(l) qui trie (en utilisant l'algorithme de tri à bulle ou le tri par insertion, à votre guise) une liste de chaînes de caractères en utilisant l'ordre défini par la fonction inf_strict_comp_inv_long_puis_ordre_alpha. On affichera la valeur retournée par l'appel tri_comp_inv_long_puis_ordre_alpha_en_place(["AB", "BA", "AA", "BB", "AAAA", "BBB"]) et on vérifiera sa cohérence.

Le but de cet exercice est de trier de plusieurs façons la liste des présidences des États-Unis d'Amérique. Celles-ci sont fournies dans la variable list_usa_psdt définie ci-dessous.

# Liste des présidences des États-Unis (les mandats successifs du même
# présidents sont considérés comme ne faisant qu'une présidence).
# Chaque élement de cette liste est lui même une liste composée dans
# l'ordre:
#
# - de la date de début de présidence
# - de la date de fin de fin de présidence
# - du prénom du président
# - du nom du président
#
# Rmq: Le deuxième prénom (Delano dans Franklin Delano Roosevelt) et
# les initiales supplémentaires (S. dans Harry S. Truman) ont été
# enlevés sauf pour George W. Bush pour le distinguer de son père...

list_usa_psdt = [[1897, 1901, "William", "McKinley"],
                 [1963, 1969, "Lyndon", "Johnson"],
                 [1933, 1945, "Franklin", "Roosevelt"],
                 [1801, 1809, "Thomas", "Jefferson"],
                 [1929, 1933, "Herbert", "Hoover"],
                 [1921, 1923, "Warren", "Harding"],
                 [1881, 1885, "Chester", "Arthur"],
                 [1974, 1977, "Gerald", "Ford"],
                 [1913, 1921, "Woodrow", "Wilson"],
                 [1809, 1817, "James", "Madison"],
                 [1869, 1877, "Ulysses", "Grant"],
                 [1845, 1849, "James", "Polk"],
                 [1969, 1974, "Richard", "Nixon"],
                 [1857, 1861, "James", "Buchanan"],
                 [1865, 1869, "Andrew", "Johnson"],
                 [2009, 2017, "Barack", "Obama"],
                 [1881, 1881, "James", "Garfield"],
                 [1853, 1857, "Franklin", "Pierce"],
                 [1817, 1825, "James", "Monroe"],
                 [1909, 1913, "William", "Taft"],
                 [1989, 1993, "George", "Bush"],
                 [1981, 1989, "Ronald", "Reagan"],
                 [1993, 2001, "Bill", "Clinton"],
                 [1885, 1889, "Grover", "Cleveland"],
                 [1849, 1850, "Zachary", "Taylor"],
                 [1825, 1829, "John", "Adams"],
                 [1893, 1897, "Grover", "Cleveland"],
                 [1829, 1837, "Andrew", "Jackson"],
                 [1841, 1845, "John", "Tyler"],
                 [1945, 1953, "Harry", "Truman"],
                 [1837, 1841, "Martin", "Van Buren"],
                 [1953, 1961, "Dwight", "Eisenhower"],
                 [1797, 1801, "John", "Adams"],
                 [1789, 1797, "George", "Washington"],
                 [2001, 2009, "George", "W. Bush"],
                 [1889, 1893, "Benjamin", "Harrison"],
                 [1901, 1909, "Theodore", "Roosevelt"],
                 [1861, 1865, "Abraham", "Lincoln"],
                 [1923, 1929, "John", "Coolidge"],
                 [1841, 1841, "William", "Harrison"],
                 [1850, 1853, "Millard", "Fillmore"],
                 [1977, 1981, "James", "Carter"],
                 [1961, 1963, "John", "Kennedy"],
                 [1877, 1881, "Rutherford", "Hayes"]]

1. Écrire la définition d'une fonction inf_strict_comp_long_presidence_puis_debut_mandat qui accepte deux arguments psdce1 et psdce2 (où, comme dans la définition de list_usa_psdt ci-dessus, une présidence est une liste de longueur 4 constitutée dans l'ordre du année de début, d'une année de fin, du prénom du président puis du nom du président) et qui renvoie
   • True si la présidence psdce1 fut strictement plus courte que la présidence psdce2;
   • True si les présidences psdce1 et psdce2 étaient de même longueur et la présidence psdce1 commença avant psdce2;
   • False sinon.
2. Écrire la définition d'une fonction tri_comp_long_presidence_puis_debut_mandat_en_place qui trie (en utilisant l'algorithme de tri à bulle ou le tri par insertion, à votre guise) une liste de présidences en utilisant l'ordre défini par la fonction inf_strict_comp_long_presidence_puis_debut_mandat (c'est à dire que l'on supposera qu'une présidence prdce1 est strictement inférieur à prdce2 si et seulement si l'appel inf_strict_comp_long_presidence_puis_debut_mandat(prdce1, prdce2) retourne True). On affichera la valeur retournée par l'appel tri_comp_long_presidence_puis_debut_mandat_en_place(list_usa_psdt) et on vérifiera sa cohérence..

3. Écrire la définition d'une fonction tri_comp_long_puis_alpha_nom_puis_alpha_prenom_puis_debut qui trie (en utilisant l'algorithme de tri à bulle ou le tri par insertion, à votre guise) une liste de présidences en comparant les présidences

   • d'abord par leur durée;
   • puis par l'ordre alphabétique du nom du président;
   • puis par l'ordre alphabétique du prénom du président
   • puis dans l'ordre des dates de début de présidence.

   On commencera par écrire une fonction de comparaison inf_strict_comp_long_puis_alpha_nom_puis_alpha_prenom_puis_debut adéquate. On affichera la valeur retournée par l'appel tri_comp_long_puis_alpha_nom_puis_alpha_prenom_puis_debut(list_usa_psdt) et on vérifiera sa cohérence.

Ci-dessous est donnée une liste où chaque élément représente une capitale. Plus précisant chaque élément est une liste où

• le permier élement est une chaîne de caractères donnant le pays dont la ville est capitale;
• le second élement est une chaîne de caractères donnant le nom de la capitale;
• le troisième élément donne une estimation du nombre d'habitants de cette capitale.

liste_capitales = [['China', 'Beijing', 20693000],
                   ['India', 'New Delhi', 16787949],
                   ['Japan', 'Tokyo', 13189000],
                   ['Philippines', 'Manila', 12877253],
                   ['Russia', 'Moscow', 11541000],
                   ['Egypt', 'Cairo', 10230350],
                   ['Indonesia', 'Jakarta', 10187595],
                   ['Democratic Republic of the Congo', 'Kinshasa', 10125000],
                   ['South Korea', 'Seoul', 9989795],
                   ['Bangladesh', 'Dhaka', 8906000],
                   ['Mexico', 'Mexico City', 8851080],
                   ['Iran', 'Tehran', 8846782],
                   ['United Kingdom', 'London', 8630100],
                   ['Peru', 'Lima', 8481415],
                   ['Thailand', 'Bangkok', 8249117],
                   ['Colombia', 'Bogotá', 7613303],
                   ['Vietnam', 'Hanoi', 7587800],
                   ['Hong Kong', 'Hong Kong', 7298600],
                   ['Iraq', 'Baghdad', 7216040],
                   ['Singapore', 'Singapore', 5535000],
                   ['Turkey', 'Ankara', 5150072],
                   ['Chile', 'Santiago', 5084038],
                   ['Saudi Arabia', 'Riyadh', 4878723],
                   ['Germany', 'Berlin', 3520000],
                   ['Syria', 'Damascus', 3500000],
                   ['Algeria', 'Algiers', 3415811],
                   ['Spain', 'Madrid', 3233527],
                   ['North Korea', 'Pyongyang', 3144005],
                   ['Afghanistan', 'Kabul', 3140853],
                   ['Kenya', 'Nairobi', 3138369],
                   ['Greece', 'Athens', 3090508],
                   ['Ethiopia', 'Addis Ababa', 3040740],
                   ['Argentina', 'Buenos Aires', 2891082],
                   ['Italy', 'Rome', 2868104],
                   ['Ukraine', 'Kyiv', 2847200],
                   ['Cameroon', 'Yaoundé', 2765568],
                   ['Taiwan', 'Taipei', 2686516],
                   ['Brazil', 'Brasília', 2648532],
                   ['Jordan', 'Amman', 2600603],
                   ['Angola', 'Luanda', 2453779],
                   ['South Africa', 'Pretoria', 2345908],
                   ['France', 'Paris', 2241346],
                   ['Uzbekistan', 'Tashkent', 2207850],
                   ['Azerbaijan', 'Baku', 2204200],
                   ['Sweden', 'Stockholm', 1856475],
                   ['Cuba', 'Havana', 2135498],
                   ['Cambodia', 'Phnom Penh', 2011725],
                   ['Romania', 'Bucharest', 1942254],
                   ['Venezuela', 'Caracas', 1838939],
                   ['Morocco', 'Rabat', 1789635],
                   ['Austria', 'Vienna', 1749673],
                   ['Sudan', 'Khartoum', 1740661],
                   ['Hungary', 'Budapest', 1729040],
                   ['Poland', 'Warsaw', 1711324],
                   ['Belarus', 'Minsk', 1702061],
                   ['Uganda', 'Kampala', 1659600],
                   ['Ghana', 'Accra', 1640507],
                   ['Madagascar', 'Antananarivo', 0.0704],
                   ['Lebanon', 'Beirut', 1574387],
                   ['Ecuador', 'Quito', 1504991],
                   ['Zimbabwe', 'Harare', 1487028],
                   ['Qatar', 'Doha', 1450000],
                   ['Yemen', "Sana'a", 1431649],
                   ['Guinea', 'Conakry', 1399981],
                   ['Malaysia', 'Kuala Lumpur', 1381830],
                   ['Uruguay', 'Montevideo', 1369797],
                   ['Zambia', 'Lusaka', 1331254],
                   ['Mali', 'Bamako', 1289626],
                   ['Czech Republic', 'Prague', 1241664],
                   ['Haiti', 'Port-au-Prince', 1235227],
                   ['Libya', 'Tripoli', 1184045],
                   ['Kuwait', 'Kuwait City', 1171880],
                   ['Serbia', 'Belgrade', 1154589],
                   ['Dominican Republic', 'Santo Domingo', 1111838],
                   ['Somalia', 'Mogadishu', 1097133],
                   ['Bulgaria', 'Sofia', 1090295],
                   ['Congo', 'Brazzaville', 1088044],
                   ['Belgium', 'Brussels', 1080790],
                   ['Armenia', 'Yerevan', 0.3629],
                   ['Mozambique', 'Maputo', 1076689],
                   ['Sierra Leone', 'Freetown', 1070200],
                   ['Ireland', 'Dublin', 1045769],
                   ['Georgia', 'Tbilisi', 1044993],
                   ['Senegal', 'Dakar', 1030594],
                   ['Guatemala', 'Guatemala City', 1022000],
                   ['Liberia', 'Monrovia', 1010970],
                   ['Burkina Faso', 'Ouagadougou', 1005231],
                   ['Nepal', 'Kathmandu', 1003285],
                   ['Pakistan', 'Islamabad', 955629],
                   ['Nicaragua', 'Managua', 926883],
                   ['Myanmar', 'Naypyidaw', 925000],
                   ['Mongolia', 'Ulan Bator', 907802],
                   ['Malawi', 'Lilongwe', 902388],
                   ['Canada', 'Ottawa', 898150],
                   ['Bolivia', 'La Paz', 877363],
                   ['Kyrgyzstan', 'Bishkek', 843240],
                   ['Kazakhstan', 'Astana', 835153],
                   ['Togo', 'Lomé', 824738],
                   ['Panama', 'Panama City', 813097],
                   ['Netherlands', 'Amsterdam', 810909],
                   ['Croatia', 'Zagreb', 804200],
                   ['Oman', 'Muscat', 797000],
                   ['Niger', 'Niamey', 794814],
                   ['Moldova', 'Chişinău', 794800],
                   ['Israel', 'Jerusalem', 780200],
                   ['Nigeria', 'Abuja', 778567],
                   ['Albania', 'Tirana', 763634],
                   ['Tunisia', 'Tunis', 767629],
                   ['Turkmenistan', 'Ashgabat', 763537],
                   ['Chad', "N'Djamena", 751288],
                   ['Honduras', 'Tegucigalpa', 735982],
                   ['Central African Republic', 'Bangui', 731548],
                   ['Mauritania', 'Nouakchott', 719167],
                   ['Rwanda', 'Kigali', 718414],
                   ['Latvia', 'Riga', 713016],
                   ['Jamaica', 'Kingston', 701063],
                   ['Macedonia', 'Skopje', 668518],
                   ['United States', 'Washington D. C.', 658893],
                   ['Norway', 'Oslo', 645701],
                   ['Finland', 'Helsinki', 596661],
                   ['United Arab Emirates', 'Abu Dhabi', 585097],
                   ['Tajikistan', 'Dushanbe', 582496],
                   ['Portugal', 'Lisbon', 564657],
                   ['Denmark', 'Copenhagen', 562253],
                   ['Lithuania', 'Vilnius', 556723],
                   ['Gabon', 'Libreville', 556425],
                   ['Eritrea', 'Asmara', 1258001],
                   ['El Salvador', 'San Salvador', 521366],
                   ['Paraguay', 'Asunción', 520722],
                   ['Macau', 'Macau', 520400],
                   ['Scotland', 'Edinburgh', 492680],
                   ['Djibouti', 'Djibouti', 475332],
                   ["Côte d'Ivoire", 'Yamoussoukro', 454929],
                   ['Guinea-Bissau', 'Bissau', 452640],
                   ['Estonia', 'Tallinn', 440206],
                   ['Slovakia', 'Bratislava', 424207],
                   ['Puerto Rico', 'San Juan', 421356],
                   ['New Zealand', 'Wellington', 398300],
                   ['Burundi', 'Bujumbura', 384461],
                   ['Bosnia and Herzegovina', 'Sarajevo', 383604],
                   ['South Sudan', 'Juba', 372410],
                   ['Australia', 'Canberra', 354644],
                   ['Costa Rica', 'San José', 328195],
                   ['Papua New Guinea', 'Port Moresby', 0.0409],
                   ['Laos', 'Vientiane', 287579],
                   ['Tanzania', 'Dodoma', 287200],
                   ['Lesotho', 'Maseru', 267652],
                   ['Cyprus', 'Nicosia', 270000],
                   ['Slovenia', 'Ljubljana', 280140],
                   ['Suriname', 'Paramaribo', 254147],
                   ['Namibia', 'Windhoek', 252721],
                   ['Bahamas', 'Nassau', 248948],
                   ['Botswana', 'Gaborone', 225656],
                   ['Benin', 'Porto-Novo', 223552],
                   ['Kosovo', 'Prishtina', 198214],
                   ['Transnistria', 'Tiraspol', 159163],
                   ['Mauritius', 'Port Louis', 147251],
                   ['Montenegro', 'Podgorica', 141854],
                   ['Bahrain', 'Manama', 140616],
                   ['Guyana', 'Georgetown', 134599],
                   ['Cape Verde', 'Praia', 125464],
                   ['Switzerland', 'Berne', 121631],
                   ['Sri Lanka', 'Sri Jayawardenepura Kotte', 118556],
                   ['Iceland', 'Reykjavík', 115000],
                   ['Barbados', 'Bridgetown', 110000],
                   ['Maldives', 'Malé', 103693],
                   ['Bhutan', 'Thimphu', 101259],
                   ['Equatorial Guinea', 'Malabo', 100677],
                   ['New Caledonia', 'Nouméa', 89207],
                   ['Northern Cyprus', 'Nicosia', 84893],
                   ['Fiji', 'Suva', 84410],
                   ['Swaziland', 'Mbabane', 81594],
                   ['Luxembourg', 'Luxembourg', 76420],
                   ['Saint Lucia', 'Castries', 70000],
                   ['Northern Mariana Islands', 'Saipan', 62392],
                   ['Comoros', 'Moroni', 60200],
                   ['Solomon Islands', 'Honiara', 59288],
                   ['East Timor', 'Dili', 59069],
                   ['São Tomé and Príncipe', 'Sao Tome', 56166],
                   ['American Samoa', 'Pago Pago', 52000],
                   ['Trinidad and Tobago', 'Port of Spain', 50479],
                   ['Nagorno-Karabakh Republic', 'Stepanakert', 49986],
                   ['Curaçao', 'Willemstad', 49885],
                   ['Saint Vincent and the Grenadines', 'Kingstown', 40020],
                   ['Samoa', 'Apia', 39813],
                   ['Vanuatu', 'Port Vila', 38000],
                   ['Monaco', 'Monaco', 35986],
                   ['Gambia', 'Banjul', 34828],
                   ['Kiribati', 'Tarawa', 30000],
                   ['Aruba', 'Oranjestad', 29998],
                   ['Seychelles', 'Victoria', 29298],
                   ['Gibraltar', 'Gibraltar', 29286],
                   ['Jersey', 'Saint Helier', 28380],
                   ['Brunei', 'Bandar Seri Begawan', 28135],
                   ['Cayman Islands', 'George Town', 26798],
                   ['Isle of Man', 'Douglas', 26600],
                   ['French Polynesia', 'Papeete', 26200],
                   ['West Bank', 'Ramallah', 25500],
                   ['Marshall Islands', 'Majuro', 25400],
                   ['Andorra', 'Andorra la Vella', 22884],
                   ['Antigua and Barbuda', "St. John's", 22679],
                   ['Tonga', 'Nukuʻalofa', 22400],
                   ['Faroe Islands', 'Tórshavn', 18573],
                   ['Guernsey', 'St. Peter Port', 16701],
                   ['Belize', 'Belmopan', 16451],
                   ['Greenland', 'Nuuk', 15469],
                   ['Dominica', 'Roseau', 14847],
                   ['Saint Kitts and Nevis', 'Basseterre', 13043],
                   ['Åland', 'Mariehamn', 11296],
                   ['United States Virgin Islands', 'Charlotte Amalie', 10817],
                   ['Federated States of Micronesia', 'Palikir', 9900],
                   ['British Virgin Islands', 'Road Town', 9400],
                   ['Grenada', "St. George's", 7500],
                   ['Malta', 'Valletta', 6444],
                   ['Saint Barthélemy', 'Gustavia', 6000],
                   ['Collectivity of Saint Martin', 'Marigot', 5700],
                   ['Saint Pierre and Miquelon', 'Saint-Pierre', 5509],
                   ['Cook Islands', 'Avarua', 5445],
                   ['Liechtenstein', 'Vaduz', 5248],
                   ['San Marino', 'City of San Marino', 4493],
                   ['Tuvalu', 'Funafuti', 4492],
                   ['Turks and Caicos Islands', 'Cockburn Town', 3700],
                   ['Falkland Islands', 'Stanley', 2115],
                   ['Svalbard', 'Longyearbyen', 2075],
                   ['Christmas Island', 'Flying Fish Cove', 1493],
                   ['Sint Maarten', 'Philipsburg', 1338],
                   ['Wallis and Futuna', 'Mata-Utu', 1191],
                   ['Anguilla', 'The Valley', 1169],
                   ['Nauru', 'Yaren', 1100],
                   ['Guam', 'Hagåtña', 1100],
                   ['Montserrat', 'Brades', 391],
                   ['Bermuda', 'Hamilton', 1010],
                   ['Vatican City', 'Vatican City', 826],
                   ['Saint Helena Ascension and Tristan da Cunha', 'Jamestown', 714],
                   ['Niue', 'Alofi', 616],
                   ['Tokelau', 'Atafu', 524],
                   ['Palau', 'Ngerulmud', 391],
                   ['Cocos (Keeling) Islands', 'West Island', 120],
                   ['Pitcairn Islands', 'Adamstown', 56],
                   ['South Georgia and the South Sandwich Islands', 'King Edward Point', 18]]

1. 1. Écrire une fonction de comparaison inf_strict_comp_nbr_hab_puis_pays_alpha qui compare deux capitales d'abord par leur nombre d'habitants puis compare le nom des pays de ces capitales par ordre alphabétique;
   2. Trier la liste des pays à l'aide de l'ordre défini par la fonction inf_strict_comp_nbr_hab_puis_pays_alpha.
2. 1. Écrire une fonction de comparaison inf_strict_comp_inv_nbr_hab_puis_nom_cap_alpha qui compare deux capitales d'abord dans l'ordre inverse de leur nombre d'habitants puis compare le nom des pays de ces capitales par ordre alphabétique;
   2. Trier la liste des pays à l'aide de l'ordre défini par la fonction inf_strict_comp_inv_nbr_hab_puis_nom_cap_alpha.

Copier-coller la définition de la fonction produit_de_1_a_n ci-dessous puis la compléter afin que l'appel produit_de_1_a_n(n) retourne \(\prod_{i=1}^{n}i\) (c'est à dire le produit des entiers de 1 à n). On vérifiera que les appels produit_de_1_a_n(3) et produit_de_1_a_n(5) retournent des valeurs cohérentes.

def produit_de_1_a_n(n):
    if n == 1:
        return ...
    tmp = produit_de_1_a_n(n-1)
    return tmp * ...

Copier-coller la définition de la fonction produit_de_3_a_n ci-dessous puis la compléter afin que l'appel produit_de_3_a_n(n) retourne \(\prod_{i=3}^{n}i\) (c'est à dire le produit des entiers de 3 à n). On vérifiera que les appels produit_de_3_a_n(3) et produit_de_3_a_n(5) retournent des valeurs cohérentes.

def produit_de_3_a_n(n):
    if n == ...:
        return ...
    tmp = produit_de_3_a_n(n-1)
    return tmp * ...

Copier-coller la définition de la fonction somme_de_0_a_n ci-dessous puis la compléter afin que l'appel somme_de_0_a_n(n) retourne \(\sum_{i=0}^{n}i\) (c'est à dire la somme des entiers de 0 à n). On vérifiera que les appels somme_de_0_a_n(3) et somme_de_0_a_n(5) retournent des valeurs cohérentes.

def somme_de_0_a_n(n):
    if n == ...:
        return ...
    tmp = somme_de_0_a_n(n-1)
    return tmp + ...

Copier-coller la définition de la fonction somme_de_1_a_n ci-dessous puis la compléter afin que l'appel somme_de_1_a_n(n) retourne \(\sum_{i=1}^{n}i\) (c'est à dire la somme des entiers de 1 à n). On vérifiera que les appels somme_de_1_a_n(3) et somme_de_1_a_n(5) retournent des valeurs cohérentes.

def somme_de_1_a_n(n):
    if n == ...:
        return ...
    tmp = somme_de_1_a_n(n-1)
    return tmp + ...

Copier-coller la définition de la fonction somme_des_carres_de_0_a_ncarre ci-dessous puis la compléter afin que l'appel somme_des_carres_de_0_a_ncarre(n) retourne \(\sum_{i=0}^{n}i^2=0^{2}+1^{2}+2^{2}+\cdots+n^{2}\). On vérifiera que les appels somme_des_carres_de_0_a_ncarre(3) et somme_des_carres_de_0_a_ncarre(5) retournent des valeurs cohérentes.

def somme_des_carres_de_0_a_ncarre(n):
    if n == ...:
        return ...
    tmp = somme_des_carres_de_0_a_ncarre(n-1)
    return tmp * ...

On considère la fonction fonction_mystere_recursive récurrente ci-dessous:

def fonction_mystere_recursive(a, b):
    if b==0:
        return 0
    else:
        return a + fonction_mystere_recursive(a, b-1)

1. afficher les valeurs renvoyées par les appels fonction_mystere_recursive(3, 0), fonction_mystere_recursive(3, 1), fonction_mystere_recursive(3, 2), fonction_mystere_recursive(3, 3) et fonction_mystere_recursive(3, 10).
2. Plus généralement que renvoit l'appel fonction_mystere_recursive(a, b), si a et b sont deux entiers et a est positif?
3. Vérifier que l'appel fonction_mystere_recursive(3, -2) échoue avec une erreur de type RecursionError. Expliquer pourquoi.

1. Écrire une fonction récursive nbr_elmt_egaux_même_ind qui accepte deux arguments que l'on suposera être de type liste et qui retourne le nombre d'éléments égaux et aux même indices entre ces deux listes. Ainsi nbr_elmt_egaux_même_ind([1,2], [2,1]) doit retourner 0, nbr_elmt_egaux_même_ind([1,2], [1,2]) doit retourner 2 et nbr_elmt_egaux_même_ind([1,2,3], [1,4,2]) doit retourner 1. On rappelle que si l est une liste non vide alors l[1:] est la liste constituée des mêmes éléments sauf du premier.
2. Écrire une fonction récursive nbr_elmt_en_commun qui accepte deux arguments que l'on suposera être de type liste et qui retourne le nombre d'éléments commun aux deux listes. Ainsi nbr_elmt_en_commun([1,2], [2,1]) doit retourner 2, nbr_elmt_en_commun([1,2], [1,2]) doit retourner 2 et nbr_elmt_en_commun([1,2,3], [1,4,2]) doit retourner 2. On rappelle que si l est une liste non vide alors l[1:] est la liste constituée des mêmes éléments sauf du dernier.

À cette question, on considère les opérations suivantes sur une chaîne de caractère

• la suppression d'une lettre;
• l'insertion d'une lettre;
• le substitution d'une lettre par une autre.

On appelle distance de levenshteim entre deux chaînes le nombre minimal de suppressions, d'insertions ou de substitutions nécessaires en partant de ces deux chaînes pour arriver à une chaîne commune. Le but de cet exercice est d'écrire une fonction récursive dist_leven qui accepte deux arguments de type chaîne de caractères et qui retourne la distance de levenshteim entre ces deux chaînes. Ainsi

• l'appel dist_leven("MA", "MAM") doit renvoyer 1 (soit on supprime un caractère de la seconde chaîne de caractères soit on ajoute un caractère à la première chaîne ce qui ne fait dans les deux cas qu'une opération);
• l'appel dist_leven("MAP", "MAM") doit renvoyer 1 (il suffit de substituer la dernière lettre d'une des chaîne en la dernière lettre de l'autre);
• l'appel dist_leven("MAPM", "MAM") doit renvoyer 1 (il suffit de supprimer le "P" de la première chaîne de caractères).

Les deux premières questions ne nécessitent pas d'écriture de code

1. Justifier que l'appel
   1. dist_leven("", "M") doit renvoyer 1;
   2. dist_leven("", "SIO") doit renvoyer 3;
   3. dist_leven("Z", "") doit renvoyer 1;
   4. dist_leven("CAR", "") doit renvoyer 3.
2. Plus généralement, si c est une chaîne de caractères, que doit renvoyer l'appel
   1. dist_leven("", "c")?
   2. dist_leven("c", "")?

3. Rappelons que si c1 est une chaîne de caractères, alors c1[:-1] est la chaîne constituée des même caractères à l'exception du dernier. Ainsi si vous exécuter les instruction c1="SIO" puis print(c1[:-1]) dans la console alors vous devriez voir affiché "SI". Dans la suite on aura toujours

   • c1_moins_derniere_lettre=c1[:-1];
   • c2_moins_derniere_lettre=c2[:-1].

   On admettra que pour calculer dist_leven(c1, c2) on peut procéder ainsi:

   • Si c1 ou c2 est la chaîne vide, renvoyer directement la distance de levenshteim en utilisant la question précédente.
   • si les deux chaînes ont même dernier caractère (soit si c1[-1]==c2[-1]) alors la distance de levenshteim entre c1 et c2 est égale à celle entre c1_moins_derniere_lettre et c2_moins_derniere_lettre;
   • sinon
     • on calcule dist_supr_dern_let_c1 = dist_leven(c1_moins_derniere_lettre, c2)+1;
     • on calcule dist_supr_dern_let_c2 = dist_leven(c1, c2_moins_derniere_lettre)+1;
     • on calcule dist_subst_dern_let = dist_leven(c1_moins_derniere_lettre, c2_moins_derniere_lettre)+1;
     • on renvoie le plus petit de ces trois nombres.

   Copier-coller la définition de la fonction dist_leven ci-dessous puis la la compléter. On vérifiera que les appels dist_leven("", "SIO"), dist_leven("SIO", "SIO"), dist_leven("SIO", "BIO"), dist_leven("SIO", "PSIO") et dist_leven("SIO", "SZI") revoient des valeurs correctes et que l'appel dist_leven("CHIENS", "NICHE") renvoie 5.

   def dist_leven(c1, c2):
       if len(c1) == 0:
           return ...
       if len(c2) == 0:
           return ...
       c1_moins_derniere_lettre = c1[:-1]
       c2_moins_derniere_lettre = c2[:-1]
       if c1[-1] == c2[-1]:
           return dist_leven(...,...)
       else:
           dist_supr_dern_let_c1 = dist_leven(..., ...) + 1
           dist_supr_dern_let_c2 = dist_leven(..., ...) + 1
           dist_subst_dern_let = dist_leven(..., ...) + 1
           dres = min(..., ..., ...)
           return ...
   

4. On suppose maintenant que le coût d'une substitution est le double de celui d'une suppression ou d'une insertion (le coût d'une suppression ou d'une insertion sera toujours de 1 mais le le coût d'une substitution sera de maintenant de 2). Écrire la définition d'une fonction dist_leven_subst_double calculant cette nouvelle distance.
5. On suppose maintenant que le coût d'une substitution est deux fois moindre que celui d'une suppression ou d'une insertion (le coût d'une suppression ou d'une insertion sera toujours de 1 mais le le coût d'une substitution sera de maintenant de 0.5). Écrire la définition d'une fonction dist_leven_suppr_et_ins_double calculant cette nouvelle distance.