Algorithmique appliquée

1 Edupython

1.1 Python3

1.1.1 Généralités

Nous programmerons en Python 3 qui est un language libre de programmation dont le site officiel – en anglais – est https://docs.python.org/3/ (les exemples de la documentation de la librairie python disponible à l'adresse https://docs.python.org/3/library/ peuvent vous intéresser).

Python permet un développement rapide d'applications (language interprété faiblement typé) dans des domaines très variés (voir par exemple https://github.com/trending/python) en mettant à disposition plusieurs paradigmes de programmation (programmation orientée objet, programmation fonctionnelle, programmation impérative, …).

Attention: il existe des différences notables entre la version 2 et la version 3 du language Python!

1.1.2 Indentation

On appelle indentation la suite d'espaces et/ou de tabulations en début de ligne. En python on n'utilisera jamais de tabulations (heureusement edupython convertit automatiquement une tabulation en une série de 4 espaces).

En python l'indentation est significative: ajouter ou supprimer des espaces en début de ligne peut modifier l'exécution d'un programme ou même générer une erreur de syntaxe (ce qui signifie q'une tentaive d'exécution du programme échouera sans qu'aucune instruction ne soit exécutée).

Plus précisément l'indentation permet de regrouper plusieurs instructions en un seul bloc syntaxique. Ainsi dans le script suivant

def nbr_chiffres(p):
    if type(p) != int:
        print("Fournir un nombre entier SVP")
        return None
    elif p<0:
        print("Fournir un nombre positif SVP")
        return None
    elif 0 <= p < 10:
        return 1
    elif 10<= p < 100:
        return 2
    elif 100<= p < 1000:
        return 3
    else:
        print("Fournir un nombre <1000 SVP")
        return None

1.2 Présentation d'Edupython

Tout éditeur de texte peut être utilisé pour écrire un programmable en Python mais nous utiliserons exclusivement le logiciel Edupython téléchargable à l'adresse http://edupython.tuxfamily.org/ et qui à l'avantage d'intégrer:

  • un éditeur adapté (coloration syntaxique, mise en évidence des erreurs de syntaxe, mise en évidence des parenthèses appairées, );
  • un interpréteur Python3 (le composant qui exécute le programme);
  • un débogueur en liaison avec l'éditeur;
  • des modules complémentaires (pour une utilisation plus avancée comme l'utilisation de bases de données).

1.3 Se repérer dans Edupython

Lorsque vous lancez EduPython vous obtenez une fenêtre subdivisée en quatre grande partie représentées dans la Figure 1

edupython.png

Figure 1 : Agencement de la fenêtre EduPython
Barre de menu/outils
  • permet d'accéder aux menus habituels (pour ouvrir/enregistrer un fichier, …)
  • permet de faire tourner le script écrit dans l'éditeur;
  • permet d'utiliser le débogueur…
Éditeur de texte
  • avec coloration syntaxique du code pour éviter de perdre du temps sur des erreurs grossières (chaîne de caractère non fermée, identifiant invalide, …);
  • avec détection et mise en évidence d'erreurs de syntaxes.
Console
  • permet de saisir rapidement des instructions Python pour faire des tests (par exemple en cas de doute sur le nom d'une variable ou d'une fonction);
  • la sortie standard est redirigée vers la console (donc les instructions print des scripts lancés depuis edupython affichent les messages dans la console).

2 Bases

2.1 Algo

2.1.1 Algorithmes

Un algorithme ou programme est

  1. une suite d'instructions;
  2. chaque instruction manipulant des données (nombres entiers, nombres flottants, chaîne de caractères, ou bien des données plus complexes comme des listes, des dictionnaires, des graphes, …);
  3. l'instruction exécutée après l'instruction courante n'est pas toujours l'instruction de la ligne suivante: le flot d'éxecution (c'est à dire l'ordre d'exécution des instructions) peut lui-même dépendre des données. Il est ainsi possible de sauter des instructions (cas du if - elif - else) ou bien de revenir en arrière (cas des boucles for et des boucles while), …
  4. le programme peut aussi afficher des données, écrire dans un fichier, envoyer des données sur une interface réseau, … En fait c'est ce qui distingue un programme d'un véritable algorithme, un algorithme ne pouvant (par définition) que retourner une valeur.

2.1.2 Variables: partie 1

Une variable est un espace aloué en mémoire qui fait donc référence à un contenu susceptible d'évoluer lors de l'éxecution du programme. Une variable est désignée par son identifiant et à chaque instant un identifiant ne peut désigner qu'une variable.

variable-p.png

#+RESULTS variable-p.png

Un identifiant (c'est à dire le nom d'une variable) doit être composé uniquement de lettres, de chiffres et du tiret bas (underscore). De plus le premier caractère ne doit pas être un chiffre.

identifiants valables:
mon_entier, _temporaire23, ~identifiant_correcte_mais_tres_long~, a_as_12_bbh
identifiants non valables:
mon-entier, 23temporaire, avec espace, @home

Dans beaucoup de languages il est nécessaire de déclarer une variable afin qu'un espace mémoire de taille suffisante lui soit aloué. Cela est inutile en Python et si la première utilisation d'une variable est pour lui affecter une valeur alors cette affectation vaut déclaration.

Cependant si la première utilisation d'une variable n'est pas une affectation il se produit une erreur NameError. Par exemple le programme:

p = 1
print(p + q)

se traduit par l'erreur "NameError: name 'q' is not defined".

En python, le type de valeur référencé par une variable peut évoluer durant l'exécution: une variable comme mavar peut contenir un entier comme 2 puis un flottant comme 1.4 puis une chaîne de caractère comme "police". Autrement dit le script suivant est valide:

mavar = 2
mavar = 1.4
mavar = "police"

2.1.3 Premier programme

Lancer Edupython, saisir le programme suivant (cadre en haut à gauche dont les lignes sont numérotées) puis l'exécuter. Vérifier que la sortie standard – qui s'affiche dans la console – correspond au contenu du cadre en bas à gauche. Le détail de l'exécution instruction après instruction est lui affiché dans la colonne de droite (lors du survol des lignes du tableau par votre souris la ligne correspondante du code source est aussi mise en évidence).

p = 1
print("p vaut:", p)
p = 2+p
print("p vaut:", p)
p = 5*p
print("p vaut:", p)
p vaut: 1
p vaut: 3
p vaut: 15
Ligne Instruction p (1-6;0)
1 'p = 1'  
2 'print("p vaut:", p)' 1
3 'p = 2+p' 1
4 'print("p vaut:", p)' 3
5 'p = 5∗p' 3
6 'print("p vaut:", p)' 15

2.2 Booléens

2.2.1 Valeurs booléennes et comparaison

  • les valeurs booléennes en Python s'écrivent True et False (attention aux majuscules!);
  • les opérateurs < et > ont leur sens usuel entre deux nombres (entiers ou flottants);
  • les inégalités larges <= et >= ne pouvant être entrées directement au clavier nécessitent deux caractères;
  • l'opérateur d'égalité en valeur == nécessite lui aussi deux caractères pour le distinguer de l'opérateur d'affectation =.
  • pour tester si une condition n'est pas vérifiée on peut utiliser not.
  • Pour tester la différence de deux valeurs a et b il y a plus simple que not a==b à savoir a != b
print("3<2?:", 3 < 2)
print("3>2?:", 3 > 2)
print("4<=5?:", 4 <= 5)
print("4>=5?:", 4 >= 5)
print("5==5.0?:", 5 < 5.0)
a=15
b = 12
c = 12
print("a<b?:", a < b)
print("a==c?:", a == b)
print("b==c?:", b == c)
3<2?: False
3>2?: True
4<=5?: True
4>=5?: False
5==5.0?: False
a<b?: False
a==c?: False
b==c?: True
Ligne Instruction a (1-11;0) b (1-11;0) c (1-11;0)
1 'print("3<2?:", 3 < 2)'      
2 'print("3>2?:", 3 > 2)'      
3 'print("4<=5?:", 4 <= 5)'      
4 'print("4>=5?:", 4 >= 5)'      
5 'print("5==5.0?:", 5 < 5.0)'      
6 'a=15'      
7 'b = 12' 15    
8 'c = 12' 15 12  
9 'print("a<b?:", a < b)' 15 12 12
10 'print("a==c?:", a == b)' 15 12 12
11 'print("b==c?:", b == c)' 15 12 12

2.2.2 Tests if - else

Lancer Edupython et y saisir le programme ci-dessous (attention à bien saisir les signes : en fin de ligne if et en fin de ligne else)

p = 10
if p>10:
    print("p est strictement plus grand que 10")
else:
    print("p est inférieur ou égal à 10")
p est inférieur ou égal à 10
Ligne Instruction p (1-5;0)
1 'p = 10'  
2 'if p>10:' 10
5 '    print("p est inférieur ou égal à 10")' 10

Modifier la première ligne du programme précédent comme ci-dessous puis exécuter ce nouveau programme. On s'aperçoit que le flot d'exécution (c'est à dire les instructions qui sont exécutées, voir la colonne "Ligne" du tableau de droite) a changé: celui-ci dépend bien des données!

p = 11
if p>10:
    print("p est strictement plus grand que 10")
else:
    print("p est inférieur ou égal à 10")
p est strictement plus grand que 10
Ligne Instruction p (1-5;0)
1 'p = 11'  
2 'if p>10:' 11
3 '    print("p est strictement plus grand que 10")' 11

2.2.3 if - elif - elif - … - else

Il est parfois nécessaires de discriminer entre plus de deux valeurs. Pour cela on ajoute autant de condition elif que nécessaire entre le if et le else

p = 24
if p==25:
    print("p est égal à 25.")
elif p==24:
    print("p est égal à 24.")
elif p>25:
    print("p est strictement supérieur à 25.")
else:
    print("p est strictement inférieur à 25 et différent de 24.")
p est égal à 24.
Ligne Instruction p (1-9;0)
1 'p = 24'  
2 'if p==25:' 24
4 'elif p==24:' 24
5 '    print("p est égal à 24.")' 24

Remarque: le if et chaque elif doit être suivi d'une condition, contrairement à else qui doit être immédiatement suivi de : (aux espaces près).

2.2.4 TP

  1. Recopier puis compléter l'algorithme ci-dessous afin
    • qu'il demande un entier a à l'utilisateur (première ligne déjà écrite);
    • qu'il affiche "a est strictement plus grand que 1", "a est inférieur ou égal à 1" ou "a est égal à 1" suivant la valeur de a.
  2. Écrire un algorithme qui
    • demande deux entiers first_int et second_int à l'utilisateur
    • puis affiche "first_int est strictement plus grand que second_int", "first_int est strictement inférieur à second_int" ou "first_int est égal à second_int" suivant les valeurs de first_int et second_int.
    1. Dans la console Edupython entrer successivement (on validera chaque entrée avec la touche entrée) 5%2, 6%2, 7%2, 8%2, 9%2, 10%2, 11%2, 12%2.
    2. A votre avis (et à l'aide de la question précédente), à quelle condition sur l'entier a l'expression a % 2 retourne-t-elle 0?
    3. À l'aide des deux questions précédentes, écrire un algorithme qui accepte un entier my_nbr en entrée puis affiche "a est pair" ou "a est impair" suivant la valeur de a.
  3. Recopier l'algorithme ci-dessous. Pourquoi le script ci-dessous n'affiche-t-il pas "p est égal à 25."? On donner la réponse sous la forme d'un commentaire (rappel: en python, les commentaires sont introduits par le symbol #)

    p = 25
    if p>24:
        print("p est strictement supérieur à 24.")
    elif p==25:
        print("p est égal à 25.")
    else:
        print("p est strictement inférieur à 24.")
    
  4. Écrire un programme qui accepte une chaîne de caractères en entrée puis affiche "la longueur de cette chaîne est paire" ou "la longueur de cette chaîne est impaire" suivant la longueur de cette chaîne (rappel: si ma_chaine est une chaîne alors len(ma_chaine) est la longueur de cette chaîne)

    chaine = input("Saisir une chaîne de caractères")
    
    if len(chaine) % 2 == 0:
        print("la longueur de cette chaîne est paire")
    else:
        print("la longueur de cette chaîne est impaire")
    
  5. Rappelons (voir ici si vous ne me croyez pas) qu'une année est bisextile si et seulement si

    • elle est divisible par 4 mais pas par 100;
    • ou bien si elle est divisible par 400.

    Rappelons aussi que en python un entier n est

    • divisible par 4 si et seulement si n%4==0;
    • divisible par 100 si et seulement si n%100==0;
    • divisible par 400 si et seulement si 400==0.

    azaz

    1. Vérifier dans la console les valeurs retournées par les expressions 8 % 4, 9 % 4, 124 % 4, 126 % 4, 200 % 100, 233 % 100, 800 % 400 et 801 % 400 sont cohérentes.
    2. Compléter le script suivant afin qu'il

      • commence par demander un entier annee à l'utilisateur;
      • puis affiche "Année bisextile" ou "Année non bisextile" suivant que l'année correspondante soit ou non bisextile.

      On vérifiera que entre 2016 et 2020 seuls les années 2016 et 2020 sont bisextiles.

    annee=int(input("Saisir une année"))
    

2.3 Built-in

2.3.1 La fonction type

Python dispose d'une fonction nommée type qui retourne le type de son argument.

Attention: le commande type retourne elle-même une quantité d'un type particulier (qui n'est pas une chaîne de caractères)!

print("Type entier:", type(128))
print("Type floattant:", type(128.0))
print("Type chaîne de caractère:", type("J'aime les maths"))
print("Type d'un type:", type(type("Un peu plus complexe")))
print("Type d'un type:", type(type(7.18)))
Type entier: <class 'int'>
Type floattant: <class 'float'>
Type chaîne de caractère: <class 'str'>
Type d'un type: <class 'type'>
Type d'un type: <class 'type'>

Remarques: Voici la signification de quelques abréviations utilisées comme nom de type:

  • int pour "integer" c'est à dire "entier" (voir la traduction);
  • str pour "string" c'est à dire "chaîne de caractères" (voir la traduction);

2.3.2 La fonction print

  • La fonction print affiche ses argument sur la "sortie standard";
  • ceux-ci sont séparés par un espace;
  • le tout est suivi d'un retour à la ligne;
  • Les arguments de la fonction print peuvent être de tout type est la représentation textuelle obtenue est presque toujours très bonne (c'est à dire complète et lisible).
p = 7
print("p vaut:", p)
p = p + 3
print("maintenant p vaut:", p)
p = 2*p
print("Et maintenant p vaut:", p)
p vaut: 7
maintenant p vaut: 10
Et maintenant p vaut: 20

2.3.3 Les fonctions de conversion

Les fonctions int et float sont des fonctions de conversion qui retournent respectivement un entier et un flottant. Elles acceptent des arguments de type variés et leur utilisation est donc diverse.

passage entre entiers et flottants
  • float(10) retourne le nombre flottant 10.0 (ce qui n'est pas exactement la même chose que l'entier 10 puisque leur type diffère;
  • int(10.0) retourne l'entier 10;
  • int(10.5) retourne l'entier 10 obtenu en supprimant la partie décimale de 10.5;
passage entre représentation textuelle et numérique
  • float("10.5") retourne le flottant 10.5 qui est très différent de la chaîne de caractères "10.5" (par exemple évaluer dans la console les expressions float("10.5")+1 puis "10.5"+1)
  • int("10") retourne l'entier 10 qui est très différent de la chaîne de caractères "10" (par exemple évaluer dans la console les expressions int("10")+1 puis "10"+1)

2.3.4 La fonction input

La fonction input permet de demander à l'utilisateur de saisir une valeur et retourne cette valeur sous le forme d'une chaîne de caractères. Si l'on souhaite

  • obtenir une valeur entière il faut donc passer la valeur retournée par la fonction input à la fonction int (la fonction int convertit une chaîne de caractères ne contenant que des chiffres en nombre entier), ce qui donne int(input("Mon message:"))
  • obtenir une valeur flottante il faut donc passer la valeur retournée par la fonction input à la fonction float (la fonction float convertit une chaîne de caractères ne contenant que des chiffres et le symbole . en nombre flottant), ce qui donne float(input("Mon message:"))

Remarque: au lieu de modifier le code source pour tester plusieurs valeurs, il vaut mieux utiliser la fonction input. Mais attention à ne pas oublier de convertir dans le type voulu car "12" est très différent de 12!

2.4 Types

2.4.1 Entiers et flottants

Quelques exemples valent mieux qu'un long discours:

Entiers
13, -13, 1300000, 0;
Flottants
10.2, 2., -13.5, 1300000.1, 14, .2, 14.;

Les opération usuelles entre nombres (entiers ou flottants) sont +, -, *, /.

p = 1.3
print("p vaut: ", p)
p = p + 3
print("maintenant p vaut: ", p)
p = 2*p
print("Et maintenant p vaut: ", p)
p vaut:  1.3
maintenant p vaut:  4.3
Et maintenant p vaut:  8.6
Ligne Instruction p (1-6;0)
1 'p = 1.3'  
2 'print("p vaut: ", p)' 1.3
3 'p = p + 3' 1.3
4 'print("maintenant p vaut: ", p)' 4.3
5 'p = 2∗p' 4.3
6 'print("Et maintenant p vaut: ", p)' 8.6

2.4.2 Chaîne de caractères

Les chaînes de caractère peuvent être saisie avec des guillemets simples ou double. Il n'y a aucune différence sauf si la chaîne contient elle-même des guillemets:

print("Une chaîne de caractères")
print('Une autre chaîne de caractères')
print("Il m'a dit: 'bonjour'!")
print('Et je lui ai répondu: "merci"!')
Une chaîne de caractères
Une autre chaîne de caractères
Il m'a dit: 'bonjour'!
Et je lui ai répondu: "merci"!
Ligne Instruction
1 'print("Une chaîne de caractères")'
2 "print('Une autre chaîne de caractères')"
3 'print("Il m\'a dit: \'bonjour\'!")'
4 'print(\'Et je lui ai répondu: "merci"!\')'

Si une chaîne de caractère délimitée par des guillemets simples (respectivement doubles) contient le caractère " (resp ') alors celui-ci doit être précédé d'un backslash (\) pour éviter qu'il ne soit interprété comme la fin de la châine de caractère (on dit que le backslash est un caractère d'échappement et que dans la chaîne "A\"B" le guillemet entre le "A" et le "B" est échappé).

print("Il m'a dit: \"bonjour\"!")
print('Et je lui ai répondu: \'merci\'!')
Il m'a dit: "bonjour"!
Et je lui ai répondu: 'merci'!
Ligne Instruction
1 'print("Il m\'a dit: ?"bonjour?"!")'
2 "print('Et je lui ai répondu: ?'merci?'!')"

2.4.3 La valeur None

  • None est l'unique valeur de son type qui est NoneType;
  • None n'est égale qu'à None:
print('None == "": ', None == "")
print('None == 0: ', None == 0)
print('None == .0: ', None == 0.)
print('None == None: ', None == None)
None == "":  False
None == 0:  False
None == .0:  False
None == None:  True

2.4.4 Les listes

  1. Définition
    • Une liste représente un ensemble ordonné d'objets indéxés à partir de 0 (comme souvent en informatique);
    • Pour saisir une liste il suffit d'écrire ses éléments dans l'ordre, séparés par des virgules, le tout encadré par des crochets;
    • si mavar est une liste alors mavar[0] est son premier élément (donc d'indexe 0), mavar[1] son second élément (donc d'indexe 1), mavar[2] est le troisième élément (donc d'indexe 2), …
    • tenter d'accéder à un élémént via un indice supérieur ou égal à la longueur de la liste est une erreur signalée par "IndexError: list index out of range".
    • la fonction len retourne la longueur de la liste donnée en argument (rappel: fonctionne aussi avec les chaînes de caractères).
    ma_lst = [49, True, 72.3, "Bla!"]
    print("ma_lst:", ma_lst)
    print("1er élmt de ma_lst:", ma_lst[0])
    print("2nd élmt de ma_lst:", ma_lst[1])
    ma_lst[1] = "MW"
    print("Après modification:")
    print("1er élmt de ma_lst:", ma_lst[0])
    print("2nd élmt de ma_lst:", ma_lst[1])
    
    ma_lst: [49, True, 72.3, 'Bla!']
    1er élmt de ma_lst: 49
    2nd élmt de ma_lst: True
    Après modification:
    1er élmt de ma_lst: 49
    2nd élmt de ma_lst: MW
    
  2. Indices positifs
    • pour faire référence à un élément d'une liste on saisit l'identifiant de la liste suivi de l'indice de l'élément recherché entre crochets: maliste[monindice]
    • une référence à un élément d'une liste peut se faire en lecture comme dans nbr = maliste[monindice] + 1 ou en écriture comme dans maliste[monindice] = 112.
    ma_lst = [49, 72.3, "London"]
    print("ma_lst:", ma_lst)
    print("Premier élmt de ma_lst:", ma_lst[0])
    print("Second élmt de ma_lst:", ma_lst[1])
    
    ma_lst: [49, 72.3, 'London']
    Premier élmt de ma_lst: 49
    Second élmt de ma_lst: 72.3
    

    Attention à ne pas tenter d'accéder à un élément d'une liste d'indice supérieur ou égal à sa longeur, même en écriture! Ainsi l'exemple suivant

    maliste = ["Indice 0", "Indice 1"]
    maliste[2] = "Indice 2"
    

    se traduit par l'erreur "IndexError: list assignment index out of range"

  3. Indices négatifs
    • Les indices négatifs parcourent les éléments de la liste à partir de la fin. Ainsi mavar[-1] représente le dernier élément de la liste et mavar[-2] l'avant dernier.
    • sinon ils peuvent être utilisés en lecture ou en écriture (comme les indices positifs);
    • tenter d'accéder à un élémént via un indice strictemtn inférieur à la longueur de la liste est une erreur signalée par "IndexError: list index out of range".
    funky_l = ["Po", 71, [1,2,9]]
    print("funky_l:", funky_l)
    print("Premier élément de funky_l:", funky_l[0])
    print("Dernier élément de funky_l:", funky_l[-1])
    print("Et funky_l[-1][1]:", funky_l[-1][1])
    
    funky_l: ['Po', 71, [1, 2, 9]]
    Premier élément de funky_l: Po
    Dernier élément de funky_l: [1, 2, 9]
    Et funky_l[-1][1]: 2
    
  4. Modifiction de listes

    Les listes sont modifiables en python. En effet on peut

    • changer l'élément d'indice donné (si l'indice n'est pas trop grand);
    • ajouter des éléments au début, au milieu ou en fin de liste;
    • supprimer des éléments au début, au milieu ou en fin de liste (attention: cela décale les indices des éléments suivants);
    1. Modification de l'élément d'indice donné (ou accès en écriture)

      On utilise comme déjà vu la notation avec des crochets

      rst12 = ["Il y a", 12, "élèves"]
      rst12[1] = 145
      print(rst12)
      
      ['Il y a', 145, 'élèves']
      

      Le nouvel élément peut très bien avoir un type différent du précédent:

      bzr_lst = [12, [1,2], "?"]
      bzr_lst[2] = bzr_lst[0]
      print(bzr_lst)
      
      [12, [1, 2], 12]
      

      Rappelons que la notation avec des crochets ne permet pas d'accéder – même en écriture – à un élément d'indice supérieur ou égal à la longueur de la liste (ou pour les indices négatifs inférieur à l'opposé de cette longueur).

    2. Suppression d'éléments d'une liste
      • On utilise pour cela le mot cléf del suivi du nom de la liste puis entre crochet l'indice que l'on souhaite supprimer;
      • attention car supprimer un élément d'une liste décale les indices de tous les éléments suivants.
      a = ["utf8", 20, 40, "azb126z", "FR"]
      del a[1]
      print(a)
      
      ['utf8', 40, 'azb126z', 'FR']
      
  5. Création rapide de liste
    • si maliste est une liste et n n entier naturel alors n*maliste crée une liste obtenue en concatenant n fois la liste maliste
    • on utilise surtout cela pour créer rapidement une liste de longueur donnée: maliste_longueur13 = 13*[None]
    liste_longueur7 = 7*[None]
    liste_longueur3 = 3*[None]
    print("liste_longueur7:", liste_longueur7)
    print("liste_longueur3:", liste_longueur3)
    
    liste_longueur7: [None, None, None, None, None, None, None]
    liste_longueur3: [None, None, None]
    

2.4.5 TP

  1. Écrire un programme qui demande à l'utilisateur de saisir deux chaînes de caractères puis retourne une liste à trois éléments qui sont dans l'ordre
    • la première chaîne saisie par l'utilisateur;
    • la seconde chaîne saisie par l'utilisateur
    • la somme des longueurs des deux chaînes;
  2. Écrire un script python qui demande deux nombres à l'utilisateur puis affiche une liste constituée de ces deux éléments triés dans l'ordre croissant
  3. Faire de même que l'exercice précédent mais avec trois valeurs cette fois.
  4. Écrire un script python
    • commençant par les lignes suivantes:

      mois = ["janvier", "février", "mars",
              "avril", "mai", "juin",
              "juillet", "août",
              "septembre", "octobre",
              "novembre", "décembre"]
      
    • qui demande un entier à l'utilisateur;
    • affiche le message "Mauvais indice" si le nombre saisi n'est pas compris entre 1 et 12;
    • affiche le nom du mois correspondant sinon (donc afficher "décembre" si l'utilisateur a entré 12).
  5. Faire de même que l'exercice précédent avec les jours de la semaine. Précisons que
    • la semaine commence un lundi;
    • l'algorithme doit donc afficher "mercredi" si l'utilisateur a entré 3.
  6. Écrire un programme qui demande un nombre entiers à l'utilisateur puis
    • affiche "Entrée invalide" si ce nombre est négatif ou strictement plus grand que 10.
    • dans le cas contraire affiche la liste de tous les nombres entier de 0 à 10 compris excepté l'entier entré par l'utilisateur. Par exemple si l'utilisateur entre 3 alors le programme doit afficher [0,1,2,4,5,6,7,8,9,10].
  7. Écrire un script python
    • commençant par les lignes suivantes (inutile de comprendre leur fonctionnement et utiliser le bouton bleu "Copy" pour sélectionner le code pour la copie):

      def jour_dans_semaine(num_mois, num_jour_ds_mois):
          """num_mois doit être compris entre 1 et 12 et num_jour_ds_mois entre
          1 et 31. Retourne un nombre entre 1 et 7 représentant le jour de
          la semaine.
          """
          mois = [4, 0, 1, 4, 6, 2, 4, 0, 3, 5, 1, 3]
          return ((num_jour_ds_mois-1 + mois[num_mois-1]) % 7)+1
      

      On admettra qu'après ces lignes jour_dans_semaine(a, b) est un entier compris entre 1 et 7 représentant le jour de la semaine de la date b/a/2016 (la semaine commençant le lundi). Ainsi jour_dans_semaine(7, 14) retourne 4 car le 14 juillet 2016 était un jeudi, quatrième jour de la semaine.

    • qui demande deux nombres à l'utilisateur;
    • puis affiche le jour de la semaine correspondante en toutes lettres (par exemple "lundi"). On passera par une liste…
  8. Améliorer le programme précédent pour qu'il vérifie que les entiers entrés par l'utilisateur représentent une date en 2016. On pourra utiliser la définition de variable ci-dessous qui donne dans l'ordre le nombre de jours de chaque mois en 2016 en commençant en janvier

    # Numéro du dernier jour de chaque mois de 2016
    nbr_jour_ds_mois = [31, 29, 31, 30,
                        31, 30, 31, 31,
                        30, 31, 30, 31]
    
  9. Écrire un script python qui
    • débute par les lignes suivantes (inutile de comprendre leur fonctionnement pour l'instant, leur effet est décrit dans le commentaire en fin de code):

      nbr_val = int(input("Nombre de valeurs:"))
      # nbr_val doit être un nombre entier mais aucune verificaton n'est
      # faite...
      valeurs_lst = [None]*nbr_val
      for i in range(nbr_val):
          valeurs_lst[i] = float(input("Entrer une valeur:"))
      valeurs_lst.sort()
      # À partir de maintenant nbr_val est un entier et valeurs_lst est une
      # liste triée dans l'ordre croissant contenant les nbr_val valeurs
      # entrées par l'utilisateur (qui doivent être des entiers ou des
      # flottants). Ainsi si l'utilisteur entre dans l'ordre 3, 4.2, -1.2
      # puis 9.7 alors après ces lignes nbr_val vaut 3 et valeurs_lst est la
      # liste [-1.2, 4.2, 9.7]
      
    • affiche la médiane des valeurs entrée par l'utilisateur. Voir par exemple en bas de la première page ici pour la définition de la médiane ou encore ici (rappel: un entier i est pair si et seulement si i%2==0).

3 Boucles

3.1 Boucle for

3.1.1 Syntaxe et exemples

  • La boucle for a pour syntaxe for myvar in myliste: où myliste est une liste et myvar est un identifiant. Le bloc syntaxique qui suit (délimité par l'indentation par rapport à for) est alors exécuté une fois pour chaque élément de myliste, la variable d'identifiant myvar prenant les valeurs des éléments de myliste (dans l'ordre).
  • Dans for myvar in myliste:, myvar doit être un identifiant et myliste doit représenter une liste. Ainsi for i in [1,2,3]: est correct de même que for j in maliste: si maliste est une variable contenant une liste.
print("Avant la boucle for")
for i in [-3, 4, 5, 10]:
    print(" i vaut:", i)
print("Après la boucle for")
Avant la boucle for
 i vaut: -3
 i vaut: 4
 i vaut: 5
 i vaut: 10
Après la boucle for
Ligne Instruction i (1-4;0)
1 'print("Avant la boucle for")'  
2 'for i in [-3, 4, 5, 10]:'  
3 '    print(" i vaut:", i)' -3
2 'for i in [-3, 4, 5, 10]:' -3
3 '    print(" i vaut:", i)' 4
2 'for i in [-3, 4, 5, 10]:' 4
3 '    print(" i vaut:", i)' 5
2 'for i in [-3, 4, 5, 10]:' 5
3 '    print(" i vaut:", i)' 10
2 'for i in [-3, 4, 5, 10]:' 10
4 'print("Après la boucle for")' 10

Autre exemple:

prime_int_lst = [2, 3, 5, 7, 11]
print("Avant la boucle for")
for nbr in prime_int_lst:
    print(" ", nbr, "est premier.")
print("Après la boucle for")
Avant la boucle for
  2 est premier.
  3 est premier.
  5 est premier.
  7 est premier.
  11 est premier.
Après la boucle for
Ligne Instruction nbr (1-5;0) prime_int_lst (1-5;0)
1 'prime_int_lst = [2, 3, 5, 7, 11]'    
2 'print("Avant la boucle for")'   [2, 3, 5, 7, 11]
3 'for nbr in prime_int_lst:'   [2, 3, 5, 7, 11]
4 '    print(" ", nbr, "est premier.")' 2 [2, 3, 5, 7, 11]
3 'for nbr in prime_int_lst:' 2 [2, 3, 5, 7, 11]
4 '    print(" ", nbr, "est premier.")' 3 [2, 3, 5, 7, 11]
3 'for nbr in prime_int_lst:' 3 [2, 3, 5, 7, 11]
4 '    print(" ", nbr, "est premier.")' 5 [2, 3, 5, 7, 11]
3 'for nbr in prime_int_lst:' 5 [2, 3, 5, 7, 11]
4 '    print(" ", nbr, "est premier.")' 7 [2, 3, 5, 7, 11]
3 'for nbr in prime_int_lst:' 7 [2, 3, 5, 7, 11]
4 '    print(" ", nbr, "est premier.")' 11 [2, 3, 5, 7, 11]
3 'for nbr in prime_int_lst:' 11 [2, 3, 5, 7, 11]
5 'print("Après la boucle for")' 11 [2, 3, 5, 7, 11]

3.2 Boucles while

3.2.1 Syntaxe et exemples

  • La boucle while a pour syntaxe while condition: où condition est une expression booléenne (dont l'évaluation retourne True ou False). Le bloc syntaxique qui suit (délimité par l'indentation par rapport à while) est exécuté tant que condition retourne True. Autrement dit la boucle s'arrête la première fois que condition retourne False.
i = 1
print("i avant la boucle while:", i)
while i<10:
    i = 2*i
print("i après la boucle while", i)
i avant la boucle while: 1
i après la boucle while 16
Ligne Instruction i (1-5;0) (while cond) i<10
1 'i = 1'    
2 'print("i avant la boucle while:", i)' 1  
3 'while i<10:' 1 V
4 '    i = 2∗i' 1  
3 'while i<10:' 2 V
4 '    i = 2∗i' 2  
3 'while i<10:' 4 V
4 '    i = 2∗i' 4  
3 'while i<10:' 8 V
4 '    i = 2∗i' 8  
3 'while i<10:' 16 F
5 'print("i après la boucle while", i)' 16  

Autre exemple:

solde = 100
print("solde avant la boucle while:", solde)
while solde<120:
    solde = solde*1.05
    print(solde)
print("solde après la boucle while", solde)
solde avant la boucle while: 100
105.0
110.25
115.7625
121.55062500000001
solde après la boucle while 121.55062500000001
Ligne Instruction solde (1-6;0) (while cond) solde<120
1 'solde = 100'    
2 'print("solde avant la boucle while:", solde)' 100  
3 'while solde<120:' 100 V
4 '    solde = solde∗1.05' 100  
5 '    print(solde)' 105.0  
3 'while solde<120:' 105.0 V
4 '    solde = solde∗1.05' 105.0  
5 '    print(solde)' 110.25  
3 'while solde<120:' 110.25 V
4 '    solde = solde∗1.05' 110.25  
5 '    print(solde)' 115.7625  
3 'while solde<120:' 115.7625 V
4 '    solde = solde∗1.05' 115.7625  
5 '    print(solde)' 121.55062500000001  
3 'while solde<120:' 121.55062500000001 F
6 'print("solde après la boucle while", solde)' 121.55062500000001  

3.3 TP

  1. un compte est rémunéré à 5%. Son solde au premier janvier 2017 était de 200 euros.
    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.
  2. 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".
  3. 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".
  4. 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.

4 Fonctions

4.1 Qu'est-ce?

Une fonction est

  • un bloc de code
  • sui est nommé, c'est à dire qu'on associe un identifiant à ce bloc de code;
  • qui dépend éventuellement de paramètres (aussi appelés arguments), qui sont des variables dont les valeurs initiales (en début du bloc de code) peuvent varier à chaque appel;
  • qui retourne une valeur (un nombre flottant, un entier, None, ou tout autre objet python comme une liste ou autre…). Si aucune valeur n'est explicitement retournée par le code d'une fonction alors cette dernière retournera None.
  • qui peut être exécuté (on dit plutôt appelé) plusieurs fois et avec des paramètres différents entre chaque appel.

Nous avons déjà croisé des fonctions qui font partie intégrante du language python. Ainsi len est une fonction qui accepte un argument (qui doit être une liste ou une chaîne de caractères) et retourne un entier (qui représente la longueur de cette liste ou de cette chaîne de caractères). Ainsi len([1,6,3]) est un appel à la fonction len avec comme argument la liste [1,6,3] et qui retourne 3, si bien que print(len([1,6,3])) affiche 3.

4.2 Définition de fonction

Pour définir une fonction en python on écrit dans l'ordre

  • le mot-cléf def suivi de un ou plusieurs espaces;
  • l'identifiant de la fonction (comme fonction_carree ou client_le_plus_riche ou encore dtls1_heartbeat). Cet identifiant est soumis aux même règles que les identifiants de variables;
  • une liste d'identifiants pour les arguments (qui sont des variables valables dans le corps de la fonction) séparés par des virgules et entre parenthèses;
  • deux points : (comme pour toutes les instructions qui délimitent des bloques de code comme if, elif et else);
  • le corps de la fonction est ensuite entièrement indenté (de quatre espaces) par rapport à la ligne contenant def ce qui permet ce délimiter le corps de la fonction (c'est à dire de savoir où s'arrête la définition);

De plus

  • dans le corps d'une fonction, on peut utiliser

(éventuellement plusieurs fois) l'instruction return

  • l'instruction return accepte une valeur comme argument (comme dans return 1 ou return True ou encore , return [1,2,"police"]);
  • lors de l'exécution du corps de la fonction, l'instruction return provoque l'arrêt de l'exécution du code de la fonction et le retour au code appelant.

Le code suivant définit une fonction d'identifiant dernier_element et acceptant exactement un seul argument (appelé ).

def dernier_element(maliste):
    if type(maliste)!=list:
      print("Erreur: l'argument n'est pas une liste.")
      return None
    elif len(maliste) == 0:
      print("Erreur: la liste est vide.")
      return None
    else:
      return maliste[-1]

4.3 Appel de fonction

Pour appeler une fonction (après sa définition!) on:

  • écrit son identifiant;
  • suivi, entre parenthèses et séparées par des virgules, des valeurs données à chaque paramètre pour cet appel (valeurs données dans le même ordre que dans la définition de la fonction);

Par exemple print("premier argument", "second argument"), len([2,9,2]) et range(3, 8) sont des appels de fonctions.

Dans l'exemple ci-dessous on appelle la fonction len avec comme paramètre equipe ce qui retourne la longueur de cette liste que l'on stoque dans la variable nbr_joueurs puis que l'on affiche.

equipe = [["Lassana", "Diarra"],
          ["Presnel", "Kimpembe"],
          ["Paul", "Pogba"],
          ["Abou", "Diaby"],
          ["Kingsley", "Coman"],
          ["Francois", "Clerc"],
          ["Ousmane", "Dembélé"],
          ["Aly", "Cissokho"],
          ["Geoffrey", "Kondogbia"],
          ["Steve", "Mandanda"],
          ["Karim", "Benzema"],
          ["Yann", "M'Vila"],
          ["Nabil", "Fekir"],
          ["Hatem", "Ben Arfa"],
          ["Layvin", "Kurzawa"],
          ["Raphael", "Varane"],
          ["Paul-Georges", "Ntep"],
          ["Olivier", "Giroud"],
          ["Maxime", "Gonalons"],
          ["Anthony", "Martial"],
          ["Loic", "Remy"],
          ["Guillaume", "Hoarau"]]
nbr_joueurs = len(equipe)
print(nbr_joueurs)
22

4.4 Exemples

La fonction suivante, appelée fonction_carre, retourne le carré de son argument et

  • les lignes 1 et 2 forment la définition de la fonction fonction_carre;
  • un premier appel à la fonction fonction_carre avec comme paramètre 12 est effectué à la ligne 4;
  • un second appel à la fonction fonction_carre avec comme paramètre 3 est effectué à la ligne 6.
def fonction_carre(x):
    return x*x

douze_au_carre = fonction_carre(12)
print(douze_au_carre)
print(fonction_carre(3))
144
9
Ligne Instruction douze_au_carre (1-6;0) x (1-2;1) x (1-2;1)
1 'def fonction_carre(x):'      
4 'douze_au_carre = fonction_carre(12)'      
1 'def fonction_carre(x):'   12  
2 '    return x∗x'   12  
5 'print(douze_au_carre)' 144    
6 'print(fonction_carre(3))' 144    
1 'def fonction_carre(x):' 144   3
2 '    return x∗x' 144   3

La fonction suivante, appelée plus_grand, accepte trois arguments et retourne le plus grand des trois. Ici elle est appelée avec les arguments 3, 4 et 1 et retourne donc 4.

def plus_grand(x, y, z):
    if x > y:
        if x > z:
            return x
        else:
            return z
    else:
        if y > z:
            return y
        else:
            return z
        return y

print(plus_grand(3, 4, 1))
4
Ligne Instruction x (1-12;1) y (1-12;1) z (1-12;1)
1 'def plus_grand(x, y, z):'      
14 'print(plus_grand(3, 4, 1))'      
1 'def plus_grand(x, y, z):' 3 4 1
2 '    if x > y:' 3 4 1
8 '        if y > z:' 3 4 1
9 '            return y' 3 4 1

4.5 TP

    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].
  1. Écrire une fonction mamoyenne qui accepte un seul argument que l'on supposera être une liste et retourne la moyenne des élements de cette liste. On vérifiera que cette fonction retourne bien 4 lorsqu'elle est appelée avec l'argument [1,9,2].
  2. Créer une fonction nbr_strictement_positifs qui accepte un argument de type liste et retourne le nombre d'éléments de cette liste qui sont strictement positifs. On vérifiera que cette fonction retourne bien 2 lorsqu'elle est appelée avec l'argument [-1,7,0,-3,4].
  3. 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.
  4. Créer une fonction renverse_et_incremente qui accepte un unique argument (on supposera qu'il s'agit d'une liste de nombres) et qui retourne une liste de même longueur obtenue en retournant la liste donnée en argument et en ajoutant 1 à chaque élément de cette liste. Ainsi l'appel renverse_et_incremente([1, 3, 7, 2]) doit retourner [3, 8, 4, 2], et l'on vérifie que c'est bien le cas. Pour vous aider, on propose de commencer comme ci-dessous
  5. Créer une fonction permute_extremites qui accepte un unique argument que l'on supposera de type liste et qui retourne la liste obtenue en échangeant le premier et le dernier élément de la liste donnée en argument. Ainsi l'appel permute_extremites([1,4,True,False,3]) doit retourner [3,4,True,False,1].
    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.

5 Cryptage

Dans toute cette partie on considérera les 26 lettres majuscules non accentuées de l'alphabet latin numérotées dans l'ordre alphabétique de 0 à 25. Pour chaque entiers a et b on s'interressera à la transformation qui à la lettre d'indice x associe la lettre d'indice (ax+b)%26.

Pour toute cette section on fournit les fonctions ci-dessous dont il est inutile de comprendre le code. La signification de leurs arguments et de la valeur retournée est décrite dans la docstring de la fonction, c'est à dire dans la châine de caractère juste sous la ligne commençant par def.

def indice_lettre(l):
    """Retourne l'indice entre 0 et 25 de son argument si ce dernier est
    bien un caractère majuscule non accentué (en python un caractère
    est une chaîne de caractères de longueur 1), sinon arrête
    l'exécution en provoquant une erreur.

    Args:
      l: chaîne de carcatère
    Retourne:
      Un entier entre 0 et 25
    """
    if not type(l) is str:
        raise Exception("L'argument n'est pas une chaîne de caractère")
    if len(l) != 1:
        raise Exception("La chaîne de caractère n'est pas un caractère seul")
    indice_ascii = ord(l)
    if indice_ascii < ord("A") or indice_ascii > ord("Z"):
        raise Exception("Le caractère n'est pas une lettre majuscule non accentuée")
    return indice_ascii - ord("A")
def lettre_d_indice(n):
    """Retourne le caractère majuscule non accentué d'indice n si n est un
    entier compris entre 0 et 25, dinon arrête l'exécution en
    provoquant une erreur.

    Args:
      n: entier compris entre 0 et 25
    Retourne:
      Un caractère majuscule.
    """
    if not type(n) is int:
        raise Exception("L'argument n'est pas un entier "+str(type(n)))
    if n < 0 or n > 25:
        raise Exception("L'entier n n'est pas compris entre 0 et 25")
    return chr(n+ord("A"))

5.1 TP

Pour chaque nouveau programme de ce TP, on commencera par copier-coller les définitions des fonctions indice_lettre et lettre_d_indice ci-dessus

  1. Afficher les valeurs retournées par les appels indice_lettre("A"), indice_lettre("B"), indice_lettre("Z") lettre_d_indice(0), lettre_d_indice(1), lettre_d_indice(25) et expliquer en quoi cela correspond aux valeurs attendues.
  2. Afficher les valeurs retournées par lettre_d_indice(indice_lettre("A")), lettre_d_indice(indice_lettre("Z")), indice_lettre(lettre_d_indice(0)) et indice_lettre(lettre_d_indice(25)). Expliquer ces valeurs.
  3. 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é").
      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?
    4. É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".

    5. É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".
  4. 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"
    
  5. 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?
  6. 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"

6 Tri

Dans cette section nous nous intéresserons à différentes façons de trier dans l'ordre croissant une liste de taille quelconque.

6.1 Tri à bulle

Pour trier (rappel: nous trierons toujours dans l'ordre croissant) une liste L avec le tri à bulle, on

  • parcourt tous les indices i pour cette liste en allant du plus petit indice possible (à savoir 0) à l'avant-dernier (à savoir len(L)-2);
  • à chaque fois que l'on tombe sur un indice i tel que L[i]>L[i+1] (ce qui signifie que l'élément d'indice courant, à savoir i, et le suivant ,ne sont pas dans le bon ordre) on échange ces deux éléments de position dans la liste L;
  • si on n'a jamais L[i]>L[i+1], c'est que la liste est triée dans l'ordre croissant. Sinon on reprend les étapes précédentes.

Voir cette animation pour un exemple de fonctionnement de cette algorithme avec la liste L=[56,22,14,5,35,69,8,15,12,7]. Remarquez que sur cet exemple, le tri nécessite neuf parcours de la liste L. On s'aperçoit que les éléments les plus grand "remontent" la liste alors que les éléments plus petits descendent. Si à la fin de chaque parcourt on coupe la liste en une première partie non triée et une seconde triée on obtient le tableau suivant

Numéro de parcours Début non trié Fin triée
1 [22,14,5,35,56,8,15,12,7] [69]
2 [14,5,22,35,8,15,12,7] [56,69]
3 [5,14,22,8,15,12,7] [35,56,69]
4 [5,14,8,15,12,7] [22,35,56,69]
5 [5,8,14,12,7] [15,22,35,56,69]
6 [5,8,14,12,7] [15,22,35,56,69]
7 [5,8,12,7] [14,15,22,35,56,69]
8 [5,8,7] [12,14,15,22,35,56,69]
9 [5,7] [8,12,14,15,22,35,56,69]
10 [] [5,7,8,12,14,15,22,35,56,69]

Le tri à bulle appliqué en python mais "à la main" (comprendre sans boucle) à la liste [5,8,9,4] est donné ci-dessous. Des commentaires ont été ajoutées pour documenter le code et des instructions print pour expliquer l'exécution.

Le but de cette sous-section est de coder cet algorthme de tri puis de visualiser ses performances.

L = [8,5,9,4]
print("Liste de départ:   ", L)
# PARCOURS 1
print("- PARCOURS 1:")
#
# Échange 1
#
# Le plus petit indice i>=0 et i<=2 tel que L[i]>L[i+1] est i=0 donc
# on échange L[0] et L[1]
tmp = L[0]
L[0] = L[1]
L[1] = tmp
#
print("  Après échange 1: ", L)
#
# Échange 2
#
# Maintenant L = [5,8,9,4]. On continue le parcours à partir de i=1 et
# on remarque que le plus petit indice i avec i>=1 et i<=2 tel que
# L[i]>L[i+1] est i=2 donc on échange L[2] et L[3]
tmp = L[2]
L[2] = L[3]
L[3] = tmp
# Maintenant L = [5,8,4,9]
print("  Après échange 2: ", L)
#
# Il n'y a pas d'indice i avec i>=2 et i<=2 tel que L[i]>L[i+1]. Comme
# on a effectué des échanges pendant le parcours courant on effectue
# un autre parcours car on n'est pas sûr que la liste soit triée (et
# d'ailleurs elle ne l'est pas).
#
# PARCOURS 2
print("\n- PARCOURS 2:")
#
# Échange 3
#
# Maintenant L = [5,8,4,9]. Le plus petit indice i>=0 et i<=2 tel que
# L[i]>L[i+1] est i=1 donc on échange L[1] et L[2]
tmp = L[1]
L[1] = L[2]
L[2] = tmp
# Maintenant L = [5,4,8,9]
print("  Après échange 4: ", L)
# Il n'y a pas d'indice i avec i>=2 et i<=2 tel que L[i]>L[i+1]. Comme
# on a effectué des échanges pendant le parcours courant on effectue
# un autre parcours car on n'est pas sûr que la liste soit triée (et
# d'ailleurs elle ne l'est pas).
#
# PARCOURS 3
print("\n- PARCOURS 3:")
#
# Échange 4
#
# Maintenant L = [5,4,8,9]. Le plus petit indice i>=0 et i<=2 tel que
# L[i]>L[i+1] est i=0 donc on échange L[0] et L[1]
tmp = L[0]
L[0] = L[1]
L[1] = tmp
# Maintenant L = [4,5,8,9]
print("  Après échange 5: ", L)
#
# Il n'y a pas d'indice i avec i>=1 et i<=2 tel que L[i]>L[i+1]. Comme
# on a effectué des échanges pendant le parcours courant on effectue
# un autre parcours car on n'est pas sûr que la liste soit triée (en
# fait elle l'est).
#
# PARCOURS 4
print("\n- PARCOURS 4:")
#
# Quel que soit l'indice i, 0<=i<=2, on n'a jamais L[i]>L[i+1]: la
# liste est triée et on s'arrête là.
print("La liste triée:    ", L)
  1. 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).
  2. Sauvegarder le script de la question précédente dans un nouveau fichier puis:
    • 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?
  3. 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.

  4. def performance_tri_a_bulle_ameliore(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_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 = 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 += (t_apres-t_avant)*1000
            plt_x[i] = taille
            plt_y1[i] = temps_cumule/nbr
        i = 0
        for taille in range(1,taille_max+1):
            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_a_bulle_en_place_ameliore(L)
                t_apres = time.clock()
                temps_cumule += (t_apres-t_avant)*1000
            plt_y2[i] = temps_cumule/nbr
        fig = plt.figure()
        ax = fig.add_subplot(111)
        ax.plot(plt_x, plt_y1, 'or', label="Trie à bulle non amélioré")
        ax.plot(plt_x, plt_y2, 'ob', label="Trie à bulle amélioré")
        ax.set_title("Comparaison avec l'algorithme de tri ameliore")
        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_ameliore(100)
    

Pour ceux qui n'ont pas fini le TD, merci de copier le script suivant dans un fichier puis de l'éxécuter (puis attendre quelques secondes)

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

def tri_a_bulle_en_place(L):
    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]
                L[i] = L[i+1]
                L[i+1] = tmp
                liste_triee_bool = False
    return L

def tri_a_bulle_en_place_ameliore(L):
    liste_triee_bool = False
    passe = 0
    pos_echange = 0
    while not liste_triee_bool:
        passe += 1
        liste_triee_bool = True
        pos_deb = max(0, pos_echange-1)
        pos_echange=None
        for i in range(pos_deb, len(L)-passe):
            if L[i] > L[i+1]:
                if pos_echange is None:
                    pos_echange = i
                tmp = L[i]
                L[i] = L[i+1]
                L[i+1] = tmp
                liste_triee_bool = False
    return L

def performance_tri_a_bulle_ameliore(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_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 = 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 += (t_apres-t_avant)*1000
        plt_x[i] = taille
        plt_y1[i] = temps_cumule/nbr
    i = 0
    for taille in range(1,taille_max+1):
        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_a_bulle_en_place_ameliore(L)
            t_apres = time.clock()
            temps_cumule += (t_apres-t_avant)*1000
        plt_y2[i] = temps_cumule/nbr
    fig = plt.figure()
    ax = fig.add_subplot(111)
    ax.plot(plt_x, plt_y1, 'or', label="Trie à bulle non amélioré")
    ax.plot(plt_x, plt_y2, 'ob', label="Trie à bulle amélioré")
    ax.set_title("Comparaison avec l'algorithme de tri ameliore")
    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_ameliore(100)

6.2 Tri par sélection

Le tri par sélection est celui du joueur de carte: on trie les éléments en parcourant la liste "de gauche à droite" en gardant la partie de gauche triée et en insérant l'élément courant à la bonne position dans cette partie triée de la liste (donc située à gauche de la position courante).

Le tri par sélection appliqué en python mais "à la main" (comprendre sans boucle) à la liste [5,8,6,4] est donné ci-dessous. Des commentaires ont été ajoutées pour documenter le code et des instructions print pour expliquer l'exécution.

lst_a_trier = [8,5,6,4]
print("- Étape 0:")
print("  lst_a_trier: ", lst_a_trier) # -> [5,8,6,4]
# Étape 1: on place les deux premiers éléments dans l'ordre.
print("- Étape 1:")
elmt_courant = lst_a_trier[1]
lst_a_trier[1] = lst_a_trier[0]
lst_a_trier[0] = elmt_courant
print("  lst_a_trier: ", lst_a_trier) # -> [5,8,6,4]
# Étape 2: on place le troisième élément pour que les trois premiers soient triés
print("- Étape 2:")
elmt_courant = lst_a_trier[2]
lst_a_trier[2] = lst_a_trier[1]
lst_a_trier[1] = elmt_courant
print("  lst_a_trier: ", lst_a_trier) # -> [5,6,8,4]
# Étape 4: on place le cinquième  élément pour que les cinq premiers soient triés
print("- Étape 4:")
elmt_courant = lst_a_trier[3]
lst_a_trier[3] = lst_a_trier[2]
lst_a_trier[2] = lst_a_trier[1]
lst_a_trier[1] = lst_a_trier[0]
lst_a_trier[0] = elmt_courant
print("  lst_a_trier: ", lst_a_trier) # -> [5,6,8,4]

Pour les questions suivantes on utilisera la fonction suivante qui accepte une liste comme argument et retourne l'indice de son minimum

  1. 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
    
  2. Écrire une fonction nommée tri_par_insertion_en_place qui accepte un unique argument que l'on supposera être une liste de nombres et qui retourne cette liste triée.
  3. Écrire une fonction nommée tri_par_insertion_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).
  4. Créer un nouveau script puis
    • 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)
      
  5. Souvegarder le script de la question précédente dans un nouveau fichier puis:
    • 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)
      
  6. 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?

6.3 Fonctions de comparaison et relations d'ordre

Nous allons étendre les tris à des listes de types plus complexes. En effet, les techniques de tri ne s'adressent pas qu'aux listes de nombres. Par exemple, pour élaborer un dictionnaire, il est nécessaires de trier des mots dans l'ordre alphabétique, qui est un ordre sur les chaînes de caractères. Mais on peut aussi souhaiter trier une liste de clients (chaque client étant représenté par un certains nombres de champs). Il est alors nécessaire de préciser l'ordre utilisé pour trier cette liste. On peut par exemple

  • trier par date de premier achat puis par ordre alphabétique du nom du client puis par numéro de client;
  • ou trier dans l'ordre alphabétique du nom du client puis dans l'ordre inverse du premier achat puis par numéro de client;

et l'on n'obtiendra pas le même résultat en général.

    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.
  1. 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.

  2. 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. É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.
      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.

7 Tableaux

Les éléments d'une liste pouvant être de type quelconque, il est possible de créer des listes de listes en python. C'est ce que nous appelerons des tableaux par la suite. L'exemple suivant montre comment définir un tableau rectangulaire de nombres et comment utiliser les indices avec ce tableau.

a = [[10,11,12],[20,21,22]]
print("1ère line du tableau a:", a[0])
print("2nd élément de la 1ère line du tableau a:", a[0][1])
1ère line du tableau a: [10, 11, 12]
2nd élément de la 1ère line du tableau a: 11

Un tableau rectangulaire de nombres comme ci-dessus sera assimilé à une matrices dans la suite. Cependant il faut faire attention au fait que, contrairement au cours de Mathématiques U21, les indices commencent ici à 0 (puisque ce sont des indices de listes).

Dans toute cette section, on pourra utiliser la fonction affiche_matrice ci-dessous qui affiche un tableau rectangulaire de nombres comme une matrice (inutile de comprendre le fonctionnement de cette fonction) et arrête l'exécution en affichant un message d'erreur explicite si le tableau n'est pas rectangulaire ou contient des éléments qui ne sont pas des nombres.

def affiche_matrice(A):
    """Affiche la matrice représentée par le tableau à deux dimensions A.

    Args:
      A: Un tableau à deux dimension d'entiers (c'est à dire une liste
         de liste d'entiers) Retourne: Un entier entre 0 et 25
      Retourne:
         Rien
    """
    def affiche_ligne(ligne, taille_elmt):
        fmt_str = "{:^{taille}d}"
        res = " ".join([fmt_str.format(elmt, taille=taille_elmt) for elmt in ligne])
        return "| {} |".format(res)

    if type(A) is not list:
        raise Exception("Ce n'est pas une liste!")
    if len(A) == 0:
        raise Exception("Le tableau est vide")
    len_lignes = None
    taille_elmt_max_str = 0
    for nligne, ligne in enumerate(A):
        if type(ligne) is not list:
            raise Exception("La ligne {} n'est pas une liste!".format(str(ligne)))
        if len_lignes is None:
            len_lignes = len(ligne)
        elif len(ligne) != len_lignes:
            fmt_str = "Les lignes ne sont pas toutes de même longueur (longueur {} puis {})!"
            raise Exception(fmt_str.format(len(ligne), len_lignes))
        for ncol,elmt in enumerate(ligne):
            if type(elmt) not in [int, float]:
                fmt_str = "L'élement {} (ligne {}, colonne {}) n'est pas un nombre!"
                raise Exception(fmt_str.format(str(elmt), nligne+1, ncol+1))
            taille_elmt_max_str = max(len(str(elmt)), taille_elmt_max_str)
    print("\n".join([affiche_ligne(ligne, taille_elmt=taille_elmt_max_str+2) for ligne in A]))
  1. Copier l'affectation suivante dans un nouveau script

    tableau_a_deux_dim = [[2, 5, 4, 3, 1, 5, 1, 4, 3, 0, 2, 7, 2, 1, 6, 3, 3, 4, 0, 6],
                          [4, 6, 7, 3, 2, 6, 7, 3, 0, 3, 6, 6, 6, 7, 3, 6, 7, 1, 4, 5],
                          [3, 3, 4, 1, 2, 2, 3, 7, 6, 0, 0, 4, 2, 0, 5, 4, 3, 5, 1, 0],
                          [4, 3, 4, 5, 5, 3, 5, 6, 0, 0, 4, 3, 6, 5, 7, 2, 6, 4, 4, 1],
                          [0, 1, 3, 7, 2, 5, 1, 7, 1, 4, 3, 5, 0, 6, 3, 1, 3, 3, 3, 5],
                          [0, 4, 6, 6, 7, 7, 2, 3, 0, 1, 3, 4, 4, 2, 0, 2, 6, 2, 4, 6],
                          [1, 6, 4, 7, 6, 1, 6, 4, 2, 4, 5, 4, 2, 7, 1, 6, 6, 0, 6, 6],
                          [2, 5, 5, 1, 1, 3, 1, 7, 5, 7, 1, 4, 3, 4, 4, 2, 0, 3, 2, 6],
                          [2, 5, 0, 7, 6, 3, 2, 0, 3, 6, 3, 6, 6, 6, 4, 3, 2, 7, 7, 7],
                          [5, 7, 5, 6, 6, 4, 3, 5, 6, 3, 2, 3, 2, 3, 4, 7, 1, 0, 5, 5],
                          [5, 5, 4, 3, 4, 2, 1, 6, 1, 5, 4, 7, 3, 3, 0, 1, 5, 7, 1, 6],
                          [7, 1, 1, 4, 6, 0, 3, 6, 1, 4, 4, 5, 7, 1, 4, 6, 4, 4, 0, 1],
                          [1, 5, 5, 3, 1, 4, 3, 4, 5, 7, 1, 6, 2, 1, 1, 6, 6, 6, 5, 0],
                          [1, 4, 3, 2, 6, 6, 7, 5, 5, 1, 2, 0, 5, 5, 5, 6, 7, 3, 0, 0],
                          [3, 6, 0, 1, 2, 2, 1, 4, 0, 5, 6, 7, 1, 7, 6, 0, 7, 0, 6, 4],
                          [7, 5, 6, 3, 1, 3, 0, 1, 5, 0, 7, 6, 7, 1, 7, 7, 0, 6, 6, 0],
                          [1, 5, 4, 7, 6, 6, 7, 1, 0, 3, 5, 5, 1, 6, 0, 2, 1, 1, 4, 6],
                          [7, 5, 6, 1, 3, 4, 6, 6, 1, 1, 4, 7, 6, 1, 0, 4, 3, 5, 0, 1],
                          [0, 2, 7, 6, 6, 4, 0, 6, 5, 5, 6, 0, 0, 0, 1, 6, 3, 4, 0, 7],
                          [1, 1, 0, 5, 4, 3, 0, 1, 5, 6, 2, 0, 2, 7, 1, 4, 6, 2, 1, 4]]
    
    1. Expliquer les valeurs retournées par les appels tableau_a_deux_dim[0], tableau_a_deux_dim[1], tableau_a_deux_dim[0][1] et tableau_a_deux_dim[1][0].
  2. Modifier la définition de la fonction matrice_de_un ci-dessous pour que lorsqu'elle est appelée avec les arguments n et p elle retourne un tableau à n lignes et p colonnes ne contenant que des 1. On vérifiera que l'appel matrice_de_un(3, 2) retourne [[1,1],[1,1],[1,1]] (utiliser la fonction affiche_matrice pour mieux visualiser la matrice correspondante).

    Rappel python: L'expression [None]*3 renvoie [None, None, None] et [1]*4 renvoie [1, 1, 1, 1]

    def matrice_de_un(n, p):
        matrice = [None]*p
        for num_ligne in range(p):
            matrice[num_ligne] = [3]*p
        return matrice
    
  3. Écrire une fonction matrice_coeff_num_ligne qui accepte deux arguments que l'on appellera n et p et qui retourne un tableau à n lignes et p colonnes où les coefficient de la ième ligne sont égaux à i. On vérifiera que l'appel matrice_coeff_num_ligne(2, 3) retourne [[1, 1, 1], [2, 2, 2]], et que l'appel matrice_coeff_num_ligne(3, 2) retourne [[1, 1], [2, 2], [3, 3]] (utiliser la fonction affiche_matrice pour mieux visualiser les matrices correspondantes).
  4. Écrire une fonction matrice_coeff_num_col qui accepte deux arguments que l'on appellera n et p et qui retourne un tableau à n lignes et p colonnes où les coefficient de la ième colonne sont égaux à i. On vérifiera que l'appel matrice_coeff_num_col(2, 3) retourne [[1, 2, 3], [1, 2, 3]] et que l'appel matrice_coeff_num_col(3, 2) retourne [[1, 2], [1, 2], [1, 2]] (utiliser la fonction affiche_matrice pour mieux visualiser les matrices correspondantes).
  5. Écrire une fonction matrice_identite qui accepte un unique argument que l'on nommera n et retourne un tableau à n lignes et n colonnes représentant la matrice identité de taille n. On vérifiera que l'appel matrice_identite(3) retourne [[1,0,0],[0,1,0],[0,0,1]].
  6. Dans cet exercice on considère un graphe G à 20 sommets nommés dans l'ordre alphabétique de "A" à "T" et dont la matrice d'adjacence est donnée par le tableau matrice_adj ci-dessous

    matrice_adj = [[0, 1, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 1, 0, 1, 1, 0],
                   [0, 1, 0, 1, 1, 1, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1],
                   [0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 1, 1],
                   [0, 1, 0, 0, 1, 1, 0, 1, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0],
                   [0, 0, 1, 0, 1, 0, 1, 0, 0, 1, 1, 0, 1, 0, 0, 0, 0, 1, 0, 0],
                   [1, 1, 0, 0, 0, 1, 1, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1],
                   [1, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 1],
                   [1, 0, 0, 1, 0, 1, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 0, 0],
                   [0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 0],
                   [0, 1, 1, 1, 0, 1, 1, 0, 0, 1, 1, 1, 1, 0, 1, 0, 0, 0, 0, 0],
                   [0, 0, 0, 1, 1, 0, 1, 0, 1, 1, 1, 1, 0, 1, 1, 0, 0, 0, 1, 0],
                   [0, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0],
                   [1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 1, 0, 1, 1, 1, 1, 0, 1, 0],
                   [0, 0, 1, 1, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 0],
                   [0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 1, 0, 1, 1],
                   [0, 0, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0],
                   [0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 1, 0],
                   [1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 0, 1, 1],
                   [1, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 0, 1, 1, 0, 0, 1],
                   [0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 1, 0, 0, 1, 1, 1, 1, 0, 1, 1]]
    

    Pour obtenir l'indexe d'un sommet à partir de 0 étant donné son nom, on pourra utiliser la fonction suivante (déjà donnée dans un TP précédent):

    def indice_lettre(l):
        """Retourne l'indice entre 0 et 25 de son argument si ce dernier est
        bien un caractère majuscule non accentué (en python un caractère
        est une chaîne de caractères de longueur 1), sinon arrête
        l'exécution en provoquant une erreur.
    
        Args:
          l: chaîne de carcatère
        Retourne:
          Un entier entre 0 et 25
        """
        if not type(l) is str:
            raise Exception("L'argument n'est pas une chaîne de caractère")
        if len(l) != 1:
            raise Exception("La chaîne de caractère n'est pas un caractère seul")
        indice_ascii = ord(l)
        if indice_ascii < ord("A") or indice_ascii > ord("Z"):
            raise Exception("Le caractère n'est pas une lettre majuscule non accentuée")
        return indice_ascii - ord("A")
    
    1. Vérifier que l'appel indice_lettre("T") retourne bien 19.
    2. Compléter la définition de la fonction nbr_succ_dans_G ci-dessous afin

      • qu'elle accepte un unique argument que l'on supposera êtres le nom d'un sommet de notre graphe (donc "A", "B", "C", "D", "E", "F", "G", "H", "I", "J", "K", "L", "M", "N", "O", "P", "Q", "R", "S" ou "T")
      • qu'elle retourne le nombre de successeurs de ce sommet dans le graphe de matrice matrice_adj
      def nbr_succ_dans_G(sommet):
          indice_sommet = indice_lettre(sommet)
          nbr_succ = 0
          for elmt in matrice_adj[indice_sommet]:
              if elmt == ...:
                  nbr_succ = ...
          return ...
      

      On vérifiera que l'appel nbr_succ_dans_G("A") retourne bien 9 et que l'appel nbr_succ_dans_G("B") retourne bien 10.

    3. Compléter a définition de la fonction nbr_pred_dans_G ci-dessous afin

      • qu'elle accepte un unique argument que l'on supposera êtres le nom d'un sommet de notre graphe (donc "A", "B", "C", "D", "E", "F", "G", "H", "I", "J", "K", "L", "M", "N", "O", "P", "Q", "R", "S" ou "T")
      • qu'elle retourne le nombre de predecesseurs de ce sommet dans le graphe de matrice matrice_adj
      def nbr_pred_dans_G(sommet):
          indice_sommet = indice_lettre(sommet)
          nbr_pred = 0
          for line in matrice_adj:
              if line[...] == ...:
                  nbr_pred = ...
          return ...
      

      On vérifiera que l'appel nbr_pred_dans_G("A") retourne bien 6 et que l'appel nbr_pred_dans_G("B") retourne bien 7.

    4. Définir une fonction est_un_arc qui accepte deux arguments que l'on supposera être des noms de sommets de G et qui retourne True s'l existe un arc dans G allant du premier au deuxième de ces sommets et False sinon. On vérifiera que l'appel est_un_arc("A", "C") renvoie True et est_un_arc("C", "A") renvoie False.
    5. Définir une fonction est_un_chemin qui accepte un unique argument que l'on supposera être une liste de noms de sommets de G et qui retourne True si cette liste est un chemin dans le graphe G et False sinon. On vérifiera que l'appel est_un_chemin(["A", "B", "D", "E"]) renvoie True et que l'appel est_un_chemin(["A", "B", "D", "G"]) renvoie False.
  7. Compléter la fonction produit_matrice ci-dessous pour

    • qu'elle accepte deux arguments que l'on nommera A et B, arguments que l'on supposera être des tableaux représentant des matrices multipliables;
    • et qui retourne le produit matriciel de A et B dans cet ordre.

    On pourra s'aider du schéma en-dessous pour se repérer dans les indices de chaque tableau

    def produit_matrice(A, B):
        n = len(A)
        p = len(B[0])
        produit_A_et_B = [None]*n
        for i in range(n):
            produit_A_et_B[i] = [None]*p
        for i in range(n):
            for j in range(p):
                produit_A_et_B[i][j] = ...
                for k in range(len(A[i])):
                    produit_A_et_B[i][j] = produit_A_et_B[i][j] + A[i][...]*B[...][j]
        return ...
    

    dia.png

    Figure 3 : Schéma de la multiplication matricielle (les indices commençant à 0)

On ajoutera les lignes suivantes en fin de script et on vérifiera que l'affichage correspond à ce que l'on attend de la multiplication matricielle…

A = matrice_de_un(2, 3)
B = matrice_de_un(3, 2)
print("A fois B:")
A_fois_B = produit_matrice(A, B)
affiche_matrice(A_fois_B)
print("\nB fois A:")
B_fois_A = produit_matrice(B, A)
affiche_matrice(B_fois_A)

8 Fonctions 2

8.1 Variables 2

8.1.1 Espaces de nom

Jusqu'à présent, nous avons prétendu qu'à chaque identifiant correspondait une unique variable et que ces associations n'évoluaient pas pendant l'exécution d'un programme. Mais en fait:

  • les associations entre identifiants et variables sont écrites dans des espaces de noms;
  • à chaque instant il peut exister plusieurs espace de noms. Il faut distinguer
    • l'espace de noms global qui est créé en début de programme et détruit à la fin de celui-ci. Les variables qui y résident sont dites globales;
    • les espaces de noms locaux qui forment une pile, au sens où ils "s'entassent les uns sur les autres". Ils sont créés puis empilés à chaque appel de fonction et dépilés puis détruits à chaque sorti de fonction. A leur création ils contiennent les associations entre les arguments de la fonction dans laquelle on rentre et les valeurs correpsondantes fournies lors de l'appel de cette fonction. L'espace de nom le plus haut (donc le dernier empilé) masque temporairement (jusqu'à ce qu'il soit dépilé) ceux d'en-dessous si bien qu'à chaque instant au plus un espace de nom local est actif. Les variables qui résident dans un espace de nom local sont dites locales à cette fonction (mais on devrait dire locales à un appel de cette fonction);
  • à un instant donné, un identifiant peut se trouver dans plusieurs espaces de noms locaux et aussi dans l'espace de nom global.

8.1.2 Accès aux variables en lecture

lorsque l'on cherche à accéder en lecture à une variable à partir de son identifiant

  • on cherche d'abord cette variable dans l'espace de nom local actif (celui qui est le plus haut sur la pile, donc celui qui correpond à l'appel de fonction en cours) si la pile n'est pas vide (autrement dit si on est bien dans une fonction) et si la variable n'a pas été déclarée avec le mot clef global. Si l'on trouve une variable avec cet identifiant dans cet espace de nom alors on utilise cette variable;
  • sinon (c'est à dire si l'on est en dehors de toute fonction ou si la variable a été déclarée avec le mot clef global) on cherche dans l'espace de nom global et si l'on y trouve une variable avec cet identifiant alors on utilise cette variable;
  • si l'on n'a alors toujours pas trouvé de variable avec cet identifiant alors une erreur NameError est levée et un message est affiché dans la console.

Considérons le schéma ci-dessous représentant des espaces de nom à un instant donné de l'exécution d'un programme.

varilecture.png

  • si l'on exécute l'instruction print(mavar1) alors l'interpréteur recherche d'abord une variable de nom mavar1 dans l'espace de nom local actif, soit dans le dernier espace de nom empilé (celui du haut), et il en trouve une. Cette instruction affiche donc "BTS SIO".
  • si l'on exécute l'instruction print(mavar1) et si la variable mavar1 est déclarée avec le mot-clef global dans la fonction courante alors l'interpréteur recherche une variable de nom mavar1 dans l'espace de nom global et il en trouve une. Cette instruction affiche donc "123.4".
  • si l'on exécute l'instruction print(mavar2) alors l'interpréteur recherche d'abord une variable de nom mavar2 dans l'espace de nom local actif, soit dans le dernier espace de nom empilé (celui du haut). Il n'en trouve pas donc il recherche maintenant dans l'espace de nom global où il en trouve une. Cette instruction affiche donc [1,2,0,"a"].
  • si l'on exécute l'instruction print(mavar3) alors l'interpréteur recherche d'abord une variable de nom mavar3 dans l'espace de nom local actif, soit dans le dernier espace de nom empilé (celui du haut). Il n'en trouve pas donc il recherche maintenant dans l'espace de nom global où il en trouve une. Cette instruction affiche donc [[1,2],[3,4]].
  • si l'on exécute l'instruction print(mavar4) alors l'interpréteur recherche d'abord une variable de nom mavar4 dans l'espace de nom local actif, soit dans le dernier espace de nom empilé (celui du haut). Il n'en trouve pas donc il recherche maintenant dans l'espace de nom global où il n'en trouve pas non plus. Une erreur NameError est alors levée (ce qui termine l'exécution du programme) et le message d'erreur NameError: name 'marvar4' is not defined est affiché dans la console.

8.1.3 Accès aux variables en écriture

  • lorsque l'on cherche à accéder en écriture à une variable à partir de son identifiant, alors

    • si on est en dehors de toute fonction ou si la variable a été déclarée avec le mot-clef global dans le corps de la fonction courante alors on utilise l'espace de nom global: si une variable avec cet identifiant y existe alors on l'utilise sinon on la crée avant de l'utiliser;
    • sinon on utilise l'espace de nom local actif (celui qui est en haut de la pile et qui correspond à l'appel de fonction courant): si une variable avec cet identifiant y existe alors on l'utilise sinon on la crée.

    Considérons le schéma ci-dessous représentant des espaces de nom à un instant donné de l'exécution d'un programme.

    variecriture.png

  • si l'on exécute l'instruction mavar1 = 12 alors l'interpréteur recherche une variable d'identifiant mavar1 dans l'espace de nom local actif (celui du haut de la pile) et il en trouve une. On se retrouve alors dans la situation suivante:

    resoidentifecrituremavar1.png

  • si l'on exécute l'instruction mavar2 = 12 et si mavar2 n'est pas déclarée avec le mot-clef global dans la fonction courante alors l'interpréteur recherche une variable d'identifiant mavar1 dans l'espace de nom local actif (celui du haut de la pile) et il n'en trouve pas. Il y en crée alors une et on se retrouve alors dans la situation suivante:

    resoidentifecrituremavar2.png

  • si l'on exécute l'instruction mavar2 = 12 et si mavar2 est déclarée avec le mot-clef global dans la fonction courante alors l'interpréteur recherche une variable d'identifiant mavar2 dans l'espace de nom global et en trouve une. On se retrouve alors dans la situation suivante:

    resoidentifecrituremavar2global.png

  • si l'on exécute l'instruction mavar3 = 12 et si mavar3 est déclarée avec le mot-clef global dans la fonction courante alors l'interpréteur recherche une variable d'identifiant mavar3 dans l'espace de nom global et n'en trouve pas, et il y en crée alors une. On se retrouve alors dans la situation suivante:

    resoidentifecrituremavar3.png

8.1.4 Exemples

Dans l'exemple suivant, l'identifiant a est utilisé par deux variables: l'une est globale et l'autre est locale à la fonction affiche_variable_locale_a. Dans la fonction affiche_variable_locale_a, on observe que c'est bien la variable locale à cette fonction qui est utilisée alors que hors de toute fonction c'est bien la variable globale qui est utilisée.

a = 9
def affichevariablelocalea():
    a = 20
    print("a:", a)
affichevariablelocalea()
print("a:", a)
a: 20
a: 9
Ligne Instruction a (1-6;0) a (2-4;1)
1 'a = 9'    
2 'def affichevariablelocalea():' 9  
5 'affichevariablelocalea()' 9  
2 'def affichevariablelocalea():' 9  
3 '    a = 20' 9  
4 '    print("a:", a)' 9 20
6 'print("a:", a)' 9  

Dans l'exemple suivant, l'identifiant b est utilisé par trois variables: l'une est globale, une autre est locale à la fonction ma_premiere_fonction et l'autre est locale à la fonction ma_seconde_fonction.

b = 8
def ma_premiere_fonction():
    b = 5
    print("Dans ma_premiere_fonction, b =", b)
def ma_seconde_fonction():
    b = 3
    print("Dans ma_seconde_fonction, b =", b)
ma_premiere_fonction()
ma_seconde_fonction()
print("Hors de toute fonction, b = ", b)
Dans ma_premiere_fonction, b = 5
Dans ma_seconde_fonction, b = 3
Hors de toute fonction, b =  8
Ligne Instruction b (1-10;0) b (2-4;1) b (5-7;1)
1 'b = 8'      
2 'def ma_premiere_fonction():' 8    
5 'def ma_seconde_fonction():' 8    
8 'ma_premiere_fonction()' 8    
2 'def ma_premiere_fonction():' 8    
3 '    b = 5' 8    
4 '    print("Dans ma_premiere_fonction, b =", b)' 8 5  
9 'ma_seconde_fonction()' 8    
5 'def ma_seconde_fonction():' 8    
6 '    b = 3' 8    
7 '    print("Dans ma_seconde_fonction, b =", b)' 8   3
10 'print("Hors de toute fonction, b = ", b)' 8    

Dans l'exemple suivant, l'identifiant b n'est utilisé que par une variable qui est globale.

b = 8
def ma_fonction():
    global b
    b = 5
    print("Dans ma_premiere_fonction, b =", b)
ma_fonction()
print("Hors de toute fonction, b = ", b)
Dans ma_premiere_fonction, b = 5
Hors de toute fonction, b =  5
Ligne Instruction b (1-7;0)
1 'b = 8'  
2 'def ma_fonction():' 8
6 'ma_fonction()' 8
2 'def ma_fonction():' 8
4 '    b = 5' 8
5 '    print("Dans ma_premiere_fonction, b =", b)' 5
7 'print("Hors de toute fonction, b = ", b)' 5

8.1.5 TP

  1. Copier-coller le script suivant dans un fichier

    foo = 1
    bar = 2
    
    def print_global_foo_and_global_bar():
        global foo, bar
        print("foo:", foo,"; bar:", bar)
    
    def assign_to_global_foo_and_global_bar(fooval, barval):
        global foo, var
        foo = fooval
        bar = barval
    
    def assign_to_global_foo_and_local_bar(fooval, barval):
        global foo
        foo = fooval
        bar = barval
    
    def assign_to_local_foo_and_global_bar(fooval, barval):
        global bar
        foo = fooval
        bar = barval
    
    print_global_foo_and_global_bar()
    # Explications:
    # 
    assign_to_global_foo_and_global_bar(3, 4)
    print_global_foo_and_global_bar()
    # Explications:
    # 
    assign_to_global_foo_and_local_bar(5, 6)
    print_global_foo_and_global_bar()
    # Explications:
    # 
    assign_to_local_foo_and_global_bar(7, 8)
    print_global_foo_and_global_bar()
    # Explications:
    #
    
    1. Expliquer les valeurs affichées par chaque appel à la fonction print_global_foo_and_global_bar dans le commentaire prévu en-dessous de ceux-ci.
    2. Copier-coller à nouveau le script ci-dessus dans un nouveau fichier puis modifier un seul des arguments parmi les appels aux fonctions assign_to_global_foo_and_global_bar, assign_to_global_foo_and_local_bar, et assign_to_local_foo_and_global_bar afin que le nouveau script affiche

      foo: 1 ; bar: 2
      foo: 3 ; bar: 2
      foo: 11 ; bar: 2
      foo: 11 ; bar: 8
      
  2. Copier-coller le script suivant dans un nouveau fichier

    foo = 1
    bar = 2
    
    def affecter_3_variable_globale_foo():
        global foo
        foo = 3
    
    def affecter_3_variable_locale_foo():
        foo = 3
    
    def affecter_5_variable_globale_bar():
        global bar
        bar = 5
    
    def affecter_5_variable_locale_bar():
        bar = 5
    
    
    print("foo:", foo, "; bar:", bar)
    glo_ou_loc = None
    while glo_ou_loc != "g" and glo_ou_loc != "l":
        glo_ou_loc = input("Affecter 3 à la variable foo globale (g) ou locale (l)? ")
        if glo_ou_loc != "g" and glo_ou_loc != "l":
            print("Mauvaise réponse: ni 'g', ni 'l'. Try again.")
    if glo_ou_loc == "g":
        affecter_3_variable_globale_foo()
    else:
        affecter_3_variable_locale_foo()
    
    print("foo:", foo, "; bar:", bar)
    glo_ou_loc = None
    while glo_ou_loc != "g" and glo_ou_loc != "l":
        glo_ou_loc = input("Affecter 3 à la variable foo globale (g) ou locale (l)? ")
        if glo_ou_loc != "g" and glo_ou_loc != "l":
            print("Mauvaise réponse: ni 'g', ni 'l'. Try again.")
    if glo_ou_loc == "g":
        affecter_3_variable_globale_foo()
    else:
        affecter_3_variable_locale_foo()
    
    print("foo:", foo, "; bar:", bar)
    glo_ou_loc = None
    while glo_ou_loc != "g" and glo_ou_loc != "l":
        glo_ou_loc = input("Affecter 5 à la variable bar globale (g) ou locale (l)? ")
        if glo_ou_loc != "g" and glo_ou_loc != "l":
            print("Mauvaise réponse: ni 'g', ni 'l'. Try again.")
    if glo_ou_loc == "g":
        affecter_3_variable_globale_foo()
    else:
        affecter_3_variable_locale_foo()
    
    print("foo:", foo, "; bar:", bar)
    glo_ou_loc = None
    while glo_ou_loc != "g" and glo_ou_loc != "l":
        glo_ou_loc = input("Affecter 5 à la variable bar globale (g) ou locale (l)? ")
        if glo_ou_loc != "g" and glo_ou_loc != "l":
            print("Mauvaise réponse: ni 'g', ni 'l'. Try again.")
    if glo_ou_loc == "g":
        affecter_5_variable_globale_bar()
    else:
        affecter_5_variable_locale_bar()
    

    Ce programme demande trois fois à l'utilisateur d'entrer une chaîne de caractères qui doit être soit "g", soit "l". Si l'utilisateur entre "g" alors une certaine valeur est affectée à une variable globale sinon s'il rentre "l" alors cette valeur est affectée à une variable locale de même identifiant.

    1. Vérifier que si l'utilisateur entre dans l'ordre "g", "l", "g", "l" alors ce programme affiche

      foo: 1 ; bar: 2
      foo: 3 ; bar: 2
      foo: 3 ; bar: 2
      foo: 3 ; bar: 5
      

      Expliquer cette affichage.

    2. Dire ce que doit entrer l'utilisateur pour que cet algorithme affiche dans l'ordre

      foo: 1 ; bar: 2
      foo: 1 ; bar: 2
      foo: 3 ; bar: 2
      foo: 3 ; bar: 2
      
  3. Recopier le script ci-dessous dans un nouveau fichier

    nbr = 0
    
    def nombre_appels_essai1():
        global nbr
        nbr = nbr + 1
        print("Fonction 'nombre_appels_essai2' appelée", nbr, "fois")
    
    def nombre_appels_essai2():
        nbr = nbr + 1
        print("Fonction 'nombre_appels_essai1' appelée", nbr, "fois")
    
    nombre_appels_essai1()
    nombre_appels_essai1()
    nombre_appels_essai1()
    nombre_appels_essai2()
    nombre_appels_essai2()
    
    1. Vérifier que cet script provoque une erreur UnboundLocalError. Cette erreur est-elle provoquée par la fonction nombre_appels_essai1 ou par la fonction nombre_appels_essai2?
    2. Expliquer cette erreur.
  4. Copier-coller le script suivant dans un nouveau fichier

    nbr_minutes = 100
    
    def ajoute_une_minute():
        # À compléter
        return
    
    def ajoute_dix_minutes():
        # À compléter
        return
    
    def afficher_nbr_minutes():
        # À compléter
        return
    
    afficher_nbr_minutes() # doit afficher 100
    ajoute_une_minute()
    afficher_nbr_minutes() # doit afficher 101
    ajoute_une_minute()
    afficher_nbr_minutes() # doit afficher 102
    ajoute_dix_minute()
    afficher_nbr_minutes() # doit afficher 112
    ajoute_dix_minute()
    afficher_nbr_minutes() # doit afficher 122
    

    Ce script compte un nombre de minutes dans une variable globale nommée nbr_minutes en commençant à 100. Chaque appel à la fonction ajoute_une_minute doit ajouter une minute à cette variable, chaque appel à la fonction ajoute_dix_minutes doit en ajouter 10, et la fonction afficher_nbr_minutes doit afficher cette variable.

    1. Compléter les définitions des trois fonctions ajoute_une_minute, ajoute_dix_minutes et afficher_nbr_minutes.
    2. Vérifier que les valeurs alors affichées par ce script sont cohérentes (voir les commentaires dans le fichier).
  5. Si vous avez fini, inscrivez-vous sur le site https://checkio.org/ en cliquant sur Python en haut à gauche (dans la partie "CheckiO" qui est dans la ciel) puis essayez le premier challenge!

8.2 Récursivité

On dit qu'une fonction est récursive si elle s'appelle elle-même. Par exemple la fonction somme_des_n_premiers_entiers définie ci-dessous est une fonction récursive.

n = 7
def somme_des_n_premiers_entiers(n):
    print("somme_des_n_premiers_entiers", n)
    if n == 1:
        return 0
    tmp = somme_des_n_premiers_entiers(n-1)
    return tmp + n
somme_des_n_premiers_entiers(3)
somme_des_n_premiers_entiers 3
somme_des_n_premiers_entiers 2
somme_des_n_premiers_entiers 1
Ligne Instruction n (1-8;0) n (2-7;1) n (2-7;2) n (2-7;3) tmp (2-7;1) tmp (2-7;2)
1 'n = 7'            
2 'def somme_des_n_premiers_entiers(n):' 7          
8 'somme_des_n_premiers_entiers(3)' 7          
2 'def somme_des_n_premiers_entiers(n):' 7 3        
3 '    print("somme_des_n_premiers_entiers", n)' 7 3        
4 '    if n == 1:' 7 3        
6 '    tmp = somme_des_n_premiers_entiers(n-1)' 7 3        
2 'def somme_des_n_premiers_entiers(n):' 7 3 2      
3 '    print("somme_des_n_premiers_entiers", n)' 7 3 2      
4 '    if n == 1:' 7 3 2      
6 '    tmp = somme_des_n_premiers_entiers(n-1)' 7 3 2      
2 'def somme_des_n_premiers_entiers(n):' 7 3 2 1    
3 '    print("somme_des_n_premiers_entiers", n)' 7 3 2 1    
4 '    if n == 1:' 7 3 2 1    
5 '        return 0' 7 3 2 1    
7 '    return tmp + n' 7 3 2     0
7 '    return tmp + n' 7 3     2  

Dans toute cette partie on utilisera fréquemment le symbol somme \(\sum\) et le symbol produit \(\prod\). Par exemple on a \(\sum_{i=1}^{3}i=1+2+3=6\), \(\prod_{i=1}^{3}i=1\times2\times3=6\), \(\sum_{i=2}^{3}i=2+3=5\), \(\sum_{i=3}^{5}i=3+4+5=12\), \(\sum_{i=3}^{3}i=3\), \(\sum_{i=4}^{4}i=4=4\).

  1. 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 * ...
    
  2. 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 * ...
    
  3. 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 + ...
    
  4. 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 + ...
    
  5. 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 * ...
    
  6. 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.
  7. À 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.

Auteur: Aurélien Bosché

Created: 2017-04-10 lun. 06:54

Validate