[Interactive Python Textbook]

S3-2 Documenter vos fonctions

Posted on November 2, 2021 by jlt

I Les signatures dans la définition

La plupart des langages de programmation nécessitent la spécification du typage des variables,

En Python, ce n'est pas obligatoire, mais fortement recommandé.

Voici la syntaxe qu'il faut utiliser :

def nomFonction(argument: type) -> typeRetour:
		blocs des instructions
		return résultat

Exemple 1 : La fonction carré

Prend en paramètre un float
renvoie un float

Exemple 2 : La fonction est_pair

Prend en paramètre un int
renvoie un bool

II Nommage

Une fonction :

Renvoie un résultat
ou fait quelques chose

Dans le deux cas, c'est une ACTION, et on nomme (le plus souvent) un fonction par un verbe. Ceci est particulièrement important pour les fonction qui font quelques chose sans renvoyer de résultat.

La convention PEP8 donne l'habitude de nommer les fonctions (comme les variables) avec des lettres minuscules et des tirets bas (celui du "8") _.

Exemples : lire_fichier, resoudre_equation, creer_grille_vide etc...

Comme pour les noms de variables, il est absolument recommandé de ne pas utiliser de caractères accentués dans les noms des fonctions.

On préfère toutefois parfois (ou souvent suivant les personnes) la convention dite camelCase qui consiste a écrire en minuscules, mais si le nom est constitué de plusieurs mots, on met une majuscules à tous les mots sauf le premier. Exemples : lireFichier, resoudreEquation, creerGrilleVide etc...

Pour clarifier la fonction, il est conseillé d'utiliser un verbe dans son nom (obtenir, donner, get, set, ...).

III. La docstring

Il est important de documenter vos fonctions, c'est-à-dire de décrire en quelques phrases le rôle de la fonction, de donner des informations sur la fonction, le lien entre les entrées et la sortie.

Pour cela, juste en dessous de la première ligne définissant la fonction, il suffit de mettre ses informations :

"""
Entrées : <donner la nom des paramètres, leur rôle et leurs types>
Sortie : préciser ce que renvoie la fonction (en précisant le type) ou péciser qu'elle ne renvoie rien, et décrire e qu'elle fait
"""

C'est ce que l'on appelle (en bon franglais) la docstring de la fonction.

Exemple 1

Exemple 2

Exemple 3

L'intérêt de l'auto-documentation d'une fonction par un texte est double :

Pour vous : le faire vous oblige à réfléchir au contenu de votre fonction avant de la programmer ; c'est un gain d'efficacité,
Pour les utilisateurs de votre code (ou pour vous longtemps après avoir programmé la fonction) : Quand on saisit dans la console, après l'exécution de la fonction, l'instruction help(nom de la fonction), Python affiche le docstring de la fonction ce qui nous permet d'avoir des informations sur la fonction en cas d'oubli.

Exercices

Exercice 1

Exercice 2

S3-1 Les fonctions

Posted on November 2, 2021 by jlt

Définir une Fonction

La fonction valeur absolue

Nous allons commencer avec un exemple. Vous rappelez-vous de la fonction abs ? Elle prend seulement un argument (un nombre x), et retourne sa valeur absolue (qui devient x quand x ≥ 0 et -x quand x < 0). La façon de définir cette fonction dans Python est :

Nous pourrions coder la même fonction différemment, sans que cela ne fasse aucune différence dans la façon de l'utiliser.

Dans cette seconde version nous introduisons 2 fois l'instruction return. Ne perdez pas de vue que, dès lors qu'une instruction return est exécutée, la fonction s'arrête (et on reprend le programme appelant là ou on l'avait arrêté).

Notez que dans cette version nous n'initialisons pas la variable valeur absolue, c'est inutile, on n'utilise aucune variable, on renvoie simplement un résultat.

Exercices

Exercice 1 : Pythagore

Coding Exercise: Pythagore

Ci dessous, donne ici une fonction qui teste si a^2 +b^2 == c^2 et qui affiche si le triangle est rectangle. Cette fonction ne renvoie rien (None).

Modifiez cette procédure pour la transformer en une fonction qui renvoie True si l'égalité est vraie et False sinon.

Vous devez modifier :

Le corps de la fonction pour renvoyer True ou False
La docstring et la ligne de la définition de la fonction
les appels pour que le programme principal affiche le résultat de la fonction.

def est_rectangle(a,b,c) -> None:
    """
    Entrées : a b et c, trois nombres
    Sortie : Rien :
        si a^2 + b^2 = c^2,  la fonction AFFICHE : le triangle est rectangle
        sinon elle affiche : le triangle n'est pas rectangle
    """
    if a**2 + b**2 == c**2 :
        print("le triangle est rectangle")
    else :
        print("le triangle n'est pas rectangle")

est_rectangle(3, 4, 5)
est_rectangle(20, 21, 29)
est_rectangle(5, 5, 5)

Exercice 2 : multiple de 3

Coding Exercise: Multiples de 3

Ci dessous une donne une fonction qui affiche les multiple de 3 jusqu'à 100.

Modifiez la fonction mult3 pour qu'elle affiche les multiples de 3 jusqu'à un entier MAX qui sera passé en paramètre.

Vous devez :

Modifier la définition de la fonction, pour passer un paramètre suplémentaire n_max
modifier le corps de la fonction pour n\'afficher les multiples de 3 que jusqu'à n_max
modifier la docstring

Le correcteur va générer un entier n_max pour exécuter et tester la fonction.

def mult3() -> int:
    """
    Entrée : rien
    Sortie : rien (None)
    affiche les multiples de 3 inférieurs à 100
    """
    for i in range(3, 101):
        if i%3 == 0 :
            print(i)

Exercice 3 : puissance

Exercice 4 : plus grande valeur

Exercice 5 : Vitesse moyenne

T 3.5 j'apprend à penser récursif

Posted on October 13, 2021 by jlt

Dans les exercices que vous avez réalisés, vous avez souvent éprouvé des difficulté à trouver le cas de base, et le cas similaire plus simple.

En réalité, pour beaucoup, vous n'avez jamais réfléchi de cette façon !

Au lieu de cela, vous avez regardé les exercices précédents, et tenté de vous en inspirer. Cela vous amène à écrire des bouts de codes, qui, si vous avez bien respecté les Types renvoyés, sont plus ou moins correct, mais incomplet, non fonctionnel...

Respecter les types ?

qu'est-ce que j'entend par là ?

1er exemple : Reprenons l'exercice my_range(a,b)

L'énoncé donne les spécifications de la fonction, et on lit :

:returns : list: la liste des entiers de a à b - 1

Il faudra donc que votre cas de base ET votre cas général renvoient toujours une liste. Seule exception, on renvoie None si a > b.

donc si vous écrivez :

return a + my_range(a,b) vous additionnez un int (a) et une liste -> typeError
return [ my_range(a,b) ] Vous avez bien compris qu'il faut renvoyer une liste, mais my_range(a,b) est une liste donc ici vous renvoyez une liste contenant une liste, donc une liste de liste, pas une liste d'entiers

2ème exemple : Reprenons l'exercice longeur(chaine)

L'énoncé donne les spécifications de la fonction, et on lit :

:returns : int: le nombre de lettres dans la chaine

Il faudra donc que votre cas de base ET votre cas général renvoient toujours un entier.

donc si vous écrivez :

return txt[0] + longueur( txt[1:] ) vous additionnez un str (txt[0]) et un int car longueur(txt) est toujours un int -> typeError
if txt == "" : return "" vous retournez une chaine, pas un int

Dans ce dernier cas, on voit bien que vous avez senti la solution : traiter le premier caractère, puis le reste de la chaine. Bon, vous avez un peu du mal a écrire txt[1:] parce que les chaines de caractères vous ennuient un peu, mais souvent vous avez plus ou moins tenté d'écrire cela.

Il est donc important de bien faire attention au type que la fonction retourne et le cas général doit combiner des solution de même types. Une liste + une liste, un int + un int, un str plus un str etc....

penser récursif

C'est là que vous pêchez le plus. Imiter un exercice précédent ne fonctionne pas, ils sont tous un peu différent.

Reprenons les :

1er exemple : somme(a,b) doit renvoyer a+b (un int)
on ne peut ajouter/retrancher que 1, on ne sait donc pas additionner a et b.
quelle est le problème trivial ? on pourrait songer à : somme(a,1) qui consiste à ajouter 1 (on sait faire) ou bien à somme(a,0) qui consiste à ne rien ajouter, on sait faire.

alors quel est le cas qui se rapproche un peu de ce cas simple ? c'est quand b diminue et se rapproche de 1 ou de 0. d'ou l'idée de rappeler somme(a,b-1)

Cette étape de réflexion est indispensable, et doit vous mener à écrire :

a+b = a +1 + (b - 1)

il existe 2 façon de l'entendre :

somme(a,b) = 1 + somme(a,b-1)
somme(a,b) = somme(a+1,b-1)

les deux sont corrects. Exprimons cela avec une phrase en français :

pour ajouter b à a : j'ajoute 1 puis j'ajoute tout le reste (b-1)

2ème exemple : longueur de la chaine

La phrase en français serait :

c'est 1 + la longueur du reste de la chaine.

la relation de récurrence s'écrira donc :

longueur(txt) = 1 + longeur(txt sans la première lettre)

reste à savoir écrire en python l'expression txt sans la première lettre

3ème exemple : my_range

vous êtes d'accord que nous écrivons de gauche à droite ? donc il est assez peu logique de commencer par la droite....

prenez un exemple quand vous ne voyez pas de suite. Si vous devez écrire range(2,6) vous allez forcément écrire 2 puis 3 puis 4 puis etc... puis 5.

le etc ci-dessus vous indique la réponse ! il indique qu'on répète ce qu'on vient juste de faire jusqu'à la fin de la liste. Ce etc est en fait notre expression pour indiquer une récurrence.

La bonne formulation sera :

Je met 2 dans la liste puis je vais recommencer avec les autres, c'est à dire my_range(3,6)

Si on respecte les types, ce 2 doit être dans une liste : [2]

reste à généraliser, avec a et b au lieu de 2 et 6 :

la liste des entiers de 2 à 5 est [2] + liste des entiers de 3 à 5

En voulant vous inspirer d'un exercice précédent, beaucoup ont écrit quelques chose du genre :

my_range(a,b) = my_range(a,b-1)

pourquoi pas, mais aller de a à b-1 est pareil que aller de a à b-2 et ajouter b-1, vous écrivez de droite à gauche ? C'est un peu malheureux, ça complique inutilement l'exercice, d'autant que vous vous emmêlez dans les b-1....

C'est parce que vous n'avez pas pensé récursif, mais plutôt pensé "comment j'ai fait dans cet autre exercice ?"

3ème exemple : parité de l'entier n

pour cet exercice c'est le cas de base qui peut vous guider. Le problème indique qu'on a pas le droit d'utiliser modulo (%), mais ce qu'on cherche est bien de savoir si n%2 == 0

et c'est trivialement vrai si n = 0

donc on va devoir se rapprocher de ce cas trivial. connaitre la parité de n-1 est en ce sens un peu plus simple que connaitre la parité de n, car on se rapproche de 0.

quel lien existe-t-il entre parité de n, et parité de n-1 ? ben c'est l'opposé:

si n pair n-1 est impair

s n impair n-1 est pair

on peut donc écrire :

partité de n = not ( parité de n-1)

et nous avons notre récurence !

-> return not est_pair(n-1)

un dernier exemple : printInline(a,b)

Cette fonction est en réalité une procédure, elle ne renvoi rien (None). Elle doit au contraire afficher quelques chose.

On est dans une situation similaire quand on dessine, par exemple avec Turtle.

Pour respecter les types on ne pourra en aucun cas écrire quelques chose comme :

printInline(a,b) = quelques chose + printInline(a,b-1)

Car additionner quelques chose et None est impossible !

La fonction doit FAIRE une partie du travail. laquelle ?

Puisque nous devons écrire une liste d'entiers, commençons par le premier :

print(a)

puis continuons avec tous les autres en partant du prochain qui est a+1 : printInline(a+1,b)

restera à régler le problème du retour à la ligne : print(a) induit un retour à la ligne qu'il faudra remplacer par un espace sans retour à la ligne : print(a,end=" ").

reste aussi a trouver quand s'arrêter ! le dernier entier à écrire sera b, donc a doit augmenter (a+1) et on s'arrête quand a == b, et là ont fera juste print(a) sans ajouter un espace cette fois, et sans rappeler la fonction.

Tout ces exemples sont différents, et il est dangereux de vouloir imiter la solution d'un exercice pour en résoudre un autre, la plupart du temps ça ne va pas fonctionner.

Ce qu'il faut faire c'est vraiment penser récursif : je fait en premier ceci puis je recommence avec le reste du problème.

entrainez vous SANS CODER

Exercice 1 :

On veux écrire une fonction qui calcule factoriel n (noté en maths : n!)

$fact(n) = 2 \times 3 \dots \times n$

on pourrait songer à commencer par la gauche mais on aura un problème :

$fact(n) = 2 \times ( 3 \times 4 \dots \times n )$

calculer $fact(n) = 2 \times 3 \dots \times n$ n'est pas un problème vraiment similaire au problème initial. Ca y ressemble mais ce n'est pas tout a fait vrai. car ce produit des entiers de 3 à n ne peut pas être écrit comme une factorielle, c'est-a-dire ne peut pas être écrit fact(quelques chose)

Vous l'avez remarqué, on peut souvent prendre le problème par le haut ou par le bas. par exemple :

longueur(txt) = 1 + longueur(txt[1:]) si je vais de gauche à droite (de bas en haut si je regarde l'indice de 0 à n-1)

mais aussi bien :

longueur(txt) = 1 + longueur(txt[;-1]) si je vais de droite à gauche (de haut en bas si je regarde l'indice de n-1 à 0)

dans un cas j'ai retiré le 1er caractère, dans l'autre cas le dernier, les 2 sont possibles.

Dans notre factorielle ça ne fonctionne pas. Mais pouvez vous exprimer la récurrence en partant du haut ?

Short Answer Exercise

$fact(n) = \dots fact(n-1)?$
Que mettez vous à la place des ... ? (mettre la réponse sans espace, et avec un opérateur
Your answer:

Correct!

Exercice 2

Proposez un algorithme récursif de calcul du produit de deux entiers naturels a et b en supposant que les seules opérations de base dont vous disposez sont

la somme de deux entiers a et b : a + b
soustraire 1 à un entier

On va transformer la multiplication en additions : $a \times b = a + a + \dots +a\ (somme\ de\ b\ termes)$

Short Answer Exercise

$produit(a,b) = \dots$
Que mettez vous à la place des ... ? (mettre la réponse comme une formule incluant l'appel de produit.
Ne mettre aucun espace dans la réponse.
Your answer:

Correct!

Exercice 3 : Palindrome

Un palindrome est un mot dont les lettres lues de gauche à droite sont les mêmes que celles lues de droite à gauche.

Les mots radar, elle, été, ici, kayak sont des palindromes.

On veux écrire une fonction qui teste si un mot est un palindrome.

ispalindrome(txt) renvoi True si txt est palindrome et False sinon.

ATTENTION AU TYPE : la fonction renvoie un booléen

le cas général doit donc renvoyer un booléen.

Quand on crée une liste on écrit par exeemple des choses comme :

return [a] + fonction(paramètres)

Dans le cas de booléen ce sera focéement :

return condition1 AND (ou OR) condition2

Vous noterez aussi que si le mot n'a qu'une seule lettre ou aucune lettre, il est forcément un palindrome.

Short Answer Exercise

le texte est un palindrome si ...==...
Ecrire l'expression booléenne qu'il vaut tester.
Your answer:

Correct!

Short Answer Exercise

écrire la seconde condition qui va permettre de continuer l'opération: cette condition est un rappel de ispalindrome avec les bon paramètres.

Le cas général s'écrire donc : return condition1 and condition2
Your answer:

Correct!

Et pour le cas de base, si la chaine est vide ou si la chaine ne contient qu'un caractère, que doit on renvoyer ?

Short Answer Exercise

Si len(txt) <=1 : return...
Your answer:

Correct!

Exercice 4

on veux tester si un lettre apparait dans un mot :

def appartient( lettre:str , mot:str ) -> bool :

Pour le cas général, il sera en deux parties :

On a trouvé la lettre :

Short Answer Exercise

if ... (sans aucun espace)
Your answer:

Correct!

dans ce cas :

Short Answer Exercise

return ... (sans aucun espace)
Your answer:

Correct!

ou bien on ne 'a pas trouvée :

Short Answer Exercise

return ... (sans aucun espace)
Your answer:

Correct!

Mais on pourrait l'écrire en une ligne, avec les même conditions que ci-dessus, mais qu'allez vous écrire entre les deux ?)

Short Answer Exercise

return condition1 ... condition2 (sans aucun espace)
Your answer:

Correct!

T 4.1 Partie 2 : implémenter l'interface

Posted on October 12, 2021 by jlt

Nous avons abordé le concept de Structure de Données Abstraite, et nous avons vu comment, avec un jeu minimal de primitive, nous pouvons manipuler une LISTE.
Rapellons les primitives utilisées :

cree_vide() : création d'une LISTE vide notée []
est_vide(liste) : True si la liste est vide et False sinon
ajouter(x,liste) ajouter un élément en tête
donne_tete(liste) : renvoi la tête
donne_queue(liste) : renvoi la queue qui est aussi une LISTE

A vous de créer cette interface

Commençons par cree_vide(). Ce n'est pas très difficile, cette fonction renvoie simplement une liste vide !

Maintenant la primitive ajouter().

Maintenant la primitive est_vide().

Là encore c'est très simple...

Et pour terminer, donne_tete et donne_queue

Avec la POO

La POO est un moyen très adapté pour créer des interfaces très faciles à utiliser. Vous allez créer une interface assez similaire aux 2 précédentes, mais utilisant le paradigme de la POO.

création d'une liste vide

On va créer une classe Liste. Les objets Liste auront 1 seul attribut, nommé contenu. Lors de l'instanciation, cet attribut prendra la valeur [].

création d'une méthode isempty

Ajoutez dans votre classe (que vous recopierez) une méthode isempty qui renvoie True si la liste est vide et False sinon.

création d'une méthode d'ajout

Pour ajouter des éléments nous n'allons pas créer une méthode ajouter.

En fait nous voudrions ajouter des éléments ainsi :

l1 = Liste() -> l1.contenu = []

l2 = Liste(3, l1) # ajoute 3 dans l1 -> l2.contenu = [3]

l3 = Liste(4, l2) # ajoute 3 dans l2 -> l3.contenu = [4, 3]

l4 = Liste(1, l3) # ajoute 3 dans l3-> l4.contenu = [1, 4, 3]

En mode empilé :
l = Liste(5, Liste(3, Liste(4, Liste() ) ) -> l.contenu = [5, 3, 4]

Cela pose un problème : lors de l'instanciation, on écrit l = Liste() sans arguments, tandis que quand on ajoute un élément, on écrit : l = Liste(x, liste), avec 2 arguments. Or, ces 2 instructions appellent la même fonction : le constructeur __init__.

Donc ce constructeur devrait avoir 0 paramètres si on instancie, et 2 paramètres si on ajoute. Cela est possible, en ajoutant des arguments optionnels ayant une valeur par défaut.

Toutefois, le constructeur ainsi modifié est assez complexe, le voici, vous n'avez pas à l'écrire, mais nous allons le commenter pour le comprendre.

création des getters get_tete et get_queue

Il s'agit de simples getters, vous pouvez les implémenter.

get_tete doit renvoyer contenu[0] si la liste est non vide, et [] sinon
get_queue doit renvoyer contenu[1:] si la liste contient au moins 2 éléments (une tête et une queue non vide) et [] sinon

T 4.1 (a finir) TAD LISTE

Posted on October 11, 2021 by jlt

Autres fonctions (cette partie n'est pas faite)

Coding Exercise: get_tete et get_queue

Implémentez les méthodes get_tete et get_queue puis créez une liste dont la tête sera 4, et la queue sera [5, 6, 1].
Vous afficherez les attributs de la liste en utilisant les getters.

class Liste :
    def __init__(self, tete=None , queue=None) :
        # si tete et queue ne sont pas présents,
        # on initialise les attributs (tete et queue) à None :
        if tete == None and queue == None :
            self.tete = None
            self.queue = None
        # sinon :
        else :
            # si la queue est vide, on met la tete dans la queue
            if queue.isempty() : 
                self.queue = None
                self.tete = tete
            # sinon, on ajoute la tete dans la queue
            else :
                if queue.queue != None :
                    self.queue = [queue.tete] + queue.queue
                else :
                    self.queue = [queue.tete] 
            # puis on met x dans tete :
            self.tete = tete
    def __str__(self) :
        return 'tête :' + str(self.tete) + '\nqueue :' + str(self.queue)
    def isempty(self) : 
        return self.tete==self.queue==None
    def get_tete(self) :
        pass
    def get_queue(self) :
        pass

On peut maintenant construire toutes les fonctions qui nous viennent à l'esprit.
Voici quatre exercices à réaliser ci-dessous, pour implémenter de nouvelles fonctions.
Pour chacun de ces exercices, vous ne pouvez utiliser que les fonctions "primitives" définies précédemment, ou une fonction que vous avez vous-même implémentée dans un des exercices ci-dessous.
Vous ne devez donc pas utiliser les instructions usuelles en python pour le type list, notamment accéder un élément avec ma_liste[0] par exemple.

Pour la réalisation des différentes fonctions, vous n'avez pas le droit d'utiliser len, append et []

exercice 1 :

exercice 2

exercice 3

exercice 4

Coding Exercise: Compléter cette fonction qui doit permettre de savoir si un élément x est dans la liste. Vous ne pouvez utiliser ni len, ni for, ni while


def appartient(x, liste):
    '''
    Cette fonction retourne True si x appartient à liste, et False sinon
    Précondition : x est de n'importe quel type, liste est du type abstrait LISTE
    Postcondition : Cette fonction renvoie un booléen
    Exemples : 
    >>> liste_1 = Vide()
    >>> liste_1 = Liste(1, liste_1)
    >>> liste_1 = Liste(2, liste_1)
    >>> liste_1 = Liste(3, liste_1)
    >>> appartient(4, liste_1)
    False
    >>> appartient(3, liste_1)
    True
    >>> liste_vide = Vide()
    >>> appartient(2, liste_vide)
    False
    '''
# compléter ici

exercice 5

Dans cet exercice, vous ne pouvez utiliser ni len, ni for, ni while, ni in

Coding Exercise: Compléter cette fonction qui doit retourner élément de rang n.

Votre fonction doit renvoyer n hors limite si n n'est le rang d'aucun élément de la liste

def lire_index(n, liste):
    '''
    Cette fonction retourne élément de rang n de liste. 
    On utilise les conventions habituelles : le plus a gauche est de rang 
    0, le suivant de rang 1...
    Si n est plus grand que longueur(liste)-1, ou negatif, la fonction 
    affiche le message :n hors limite et retourne None.
    :param n: n est de type entier.
    :param liste: liste est de type abstrait LISTE
    :returns: le type renvoyé est celui de l élement de rang n. La 
                fonction retourne None si n est hors limite ou si 
                la liste est vide. Elle affiche alors un message 
                explicatif.
    Exemples :
    >>> liste_1 = Vide()
    >>> liste_1 = Liste(1, liste_1)
    >>> liste_1 = Liste(2, liste_1)
    >>> liste_1 = Liste(3, liste_1)
    >>> lire_index(1, liste_1)
    2
    '''
# Compléter ici

T 4.1 (partie 1) TAD Listes

Posted on October 10, 2021 by jlt

introduction

Exemple d'implémentation en Python du type LISTE

Le type abstrait de donnée LISTE

Le langage de programmation Lisp (inventé par John McCarthy en 1958) a été un des premiers langages de programmation à introduire cette notion de liste (Lisp signifie "list processing").

On trouve différentes définitions du type abstrait liste.

Dans ce cours, nous définirons une liste comme une structure de donnée permettant de regrouper des données. C'est une structure linéaire qu'on ne peut parcourir qu'en partant du début. Elle est définie par son interface, c'est à dire l'ensemble des fonctions (méthodes), appelées des primitives qui vont permettre de creer et gérer la liste.

Il y a de nombreuses possibilités pour implémenter ce type abstrait, et on a pas besoin de connaître cette implémentation pour l'utiliser. Il suffit de connaître les spécifications des fonctions primitives, pour pouvoir les utiliser et éventuellement écrire d'autres fonctions.

Attention : ce que nous appelons listes dans ce chapitre n'est pas la même chose que les listes que vous connaissez en python. Il s'agit ici de types abstraits qui n'existent pas nécessairement de façon native dans tous les langages, mais peuvent être implémentés.

Le type abstrait LISTE est différent du type list. Nous le noterons dans ce cours, pour bien le différencier, en majuscules : LISTE.

Pour résumé, une LISTE est composée de :

sa tête (souvent noté car), qui correspond au dernier élément ajouté à la liste (en tête de liste)
et sa queue (souvent noté cdr) qui correspond au reste de la liste.

Écriture d'une liste

La manière dont sont affichées les listes dépend de leur implémentation. Dans ce qui suit nous allons conserver un affichage qui permet de bien visualiser la tête et la queue de la liste. Nous allons voir 3 implémentations différentes du type liste, toutes valables et on pourrait en inventer bien d'autres. Mais nous resteront sur le concept initial de John McCarthy

Nous verrons d'abord un premier exemple, sans POO :

Une liste vide contiendra | None | None | (ni queue ni tête)
Une liste à une seul élément n'a pas de queue mais a une tête : | 2 | None |
Une liste à plusieurs éléments : | 5 | 4 3 2 1 |

Notre type abstrait liste utilise donc des chaines de python pour la représentation, car il en faut bien une.

Un deuxième exemple : toujours sans POO, mais avec une notation différente, plus proche des list de python. Vous devrez construire l'interface pour ce cas.

Un troisième exemple : ave la POO

La POO est un outil très pratique pour modéliser des Listes. Nous pourront ainsi par exemple construire des liste ainsi :

une liste a 1 attribut contenu. Dans le cas d'une liste vide cet arrtibut contiendra []

Dans la littérature, on trouve des présentation très variées, souvent de ce type :

(5 , (4 , (3 , (2, (1,None)))))

mais aussi des présentation plus proche de celle de python :

[ 5 4 3 2 1] ou [5, 4, 3, 2, 1] ou avec des ( ).....

Tout est correct, puisque ce n'est qu'un choix de la façon de représenter un type abstrait. La représentation est plus ou moins lisible, mais les plus simples ne rendent pas toujours bien compte de la façon dont les données sont traitées en mémoire et comment on va y accéder.

Définition : Primitive

Un Type Abstrait de Données (TAD), parfois aussi nommé Structure de Données Abstraite (SDA) est implémenté grâce à un nombre restreint de primitives.
Une primitive est une fonction permettant de manipuler le TAD. Dans certain cas, ce peut être une classe (dans ce cas, c'est la constructeur qui joue le rôle d'une primitive lors de l'instanciation), ou une méthode, mais ça revient au même.

Quand on vous demande d'implémenter le type abstrait liste, la question est incomplète, car les définitions de ce TAD sont très variées. Nous allons dans tout ce cours utiliser un jeu de 5 primitives, ce qui correspond à la définition la plus couramment utilisée.

Créer une liste vide
savoir si une liste est vide (True ou False)
ajouter un élément
prendre la tête de la liste
prendre la queue de la liste

Définition : Interface

L'ensemble des primitive de notre TAD est nommé interface du TAD

Avec cette interface, notre TAD est défini. Bien sur, nous pourront créer d'autres fonctions pour manipuler notre TAD, comme par exemple longueur qui donnera la longueur de la liste, on index qui cherche l'indice d'un élément etc et .... mais ces fonctions devront être implémentées en utilisant les primitives.

Tous les langages modernes, et Python ne fait pas exception, utilisent des listes, souvent différente de ce modèle abstrait, et donc tous ont une implémentation d'un jeu de primitives pour manipuler des conteneurs.

Ces fonctions primitives ne sont pas directement utilisées par le programmeur, qui dispose d'autre syntaxes qui font appel à ces primitives.

un premier exemple

Comprendre le fonctionnement des primitives

Ci dessous nous avons implémenté les 5 primitives. Vous ne pouvez pas voir le code de l'impémentation, mais vous allez utiliser help( ) pour lire leurs documentations.

lisez attentivement les spécifications de chaque primitive, car elles vous permettront de comprendre leur fonctionnement.

A vous d'utiliser cette première interface

A vous maintenant !

Un second exemple

Changeons la notation

Dans le premier exemple nous utilisons une notation assez éloignée de celle à laquelle vous êtes habitués en python. Nous allons utiliser une interface très similaire à la première, mais avec une notation plus simple (mais qui ne permet pas aussi facilement de distinguer tête et queue de la liste).

Comme vous le voyez ici, notre TAD peut assez bien être utilisé pour implémente un type LISTE ressemblant au type list de python. Néanmoins, les liste de python peuvent aussi être utilisée d'autres façon, et ne sont pas limitées aux même usages que notre LISTE.

exercices avec cette interface

Vous vous rendez bien compte que, malgré la ressemblance, ce type LISTE n'est pas le même que le type list de python.

Coding Exercise: Compléter cette fonction qui doit permettre de savoir si un élément x est dans la liste. Vous ne pouvez utiliser ni len, ni for, ni while

def appartient(x, liste):
    '''
    Cette fonction retourne True si x appartient à liste, et False sinon
    Précondition : x est de n'importe quel type, liste est du type abstrait LISTE
    Postcondition : Cette fonction renvoie un booléen
    Exemples : 
    >>> liste_1 = Vide()
    >>> liste_1 = Liste(1, liste_1)
    >>> liste_1 = Liste(2, liste_1)
    >>> liste_1 = Liste(3, liste_1)
    >>> appartient(4, liste_1)
    False
    >>> appartient(3, liste_1)
    True
    >>> liste_vide = Vide()
    >>> appartient(2, liste_vide)
    False
    '''
# compléter ici

P5.1b les algorithmes de constructions de liste

Posted on December 4, 2020 by jlt

retourner une liste par ajout successifs

On veut retourner une liste (c'est à dire ranger ses éléments dans l'ordre inverse) et on va procéder par ajouter successifs (il existe d'autres façons de le faire).
L'algorithme est assez simple :

fonction retourner(lst) :
lstReverse = [ ]
tant que lst non vide :
retirer le dernier elem de lst et l'ajouter à la fin de lstReverse
fin de pour
renvoyer lstReverse

Coder ceci en python ne pose pas de grosse difficulté, mais il faut se souvenir de la méthode pop et de son usage….
Voici un code qui va te servir d'exemple pour l'exercice.

Rappel :
lst = [1,2,3]
a = lst.pop()
-> a=3 et maintenant lst=[1,2]
lst.pop() retire le dernier élément de la liste lst et renvoie sa valeur.

pyBox slug='5.1_reversePOP' solver="def reversePOP(lst: list ) -> list : lstR=[] while len(lst) > 0: e=lst.pop() lstR.append(e) return lstR lst=[3,1,6,7,2] print(reversePOP(lst)) " defaultcode="def reversePOP(lst: list ) -> list : # votre code ici lst=[3,1,6,7,2] print(reversePOP(lst)) " taboo="insert" title='reverse avec pop' ] [/pyBox]

Au lieu de append, on pourrait aussi utiliser une concaténation de liste : lstR = lstR + [val] donnera le même résultat, essaye les deux façons.
(attention : en réalité ces deux façon de procéder ne sont pas équivalentes. Elle donnent le même résultat et pour cette année nous n'entreront pas dans les détails sr la différence de traitement entre les deux)

On pourrait même ne rien ajouter et ne rien concaténer :

def reversePOP(lst: list ) -> list :
    lstR=[0] * len(lst) # initialise une liste avec len(lst) 0
    idx=0
    while len(lst) > 0:
        e=lst.pop()
        lstR[idx]=e
        idx+=1
    return lstR

Et là encore, le résultat est le même mais les opérations réalisées ne sont pas les même en réalités. Et ici aussi nous n'entreront pas cette année dans les détails.

Toutefois nous aurions pu écrire aussi bien cet algorithme :

onction retourner(lst) :
lstReverse = [ ]
tant que lst non vide :
retirer le premier elem de lst et l'ajouter au début de lstReverse
fin de pour
renvoyer lstReverse

Tu pourras coder ce second algorithme en utilisant lst.pop(0) qui retire l'élément d'indice 0 et lstR.insert(0,val) qui insère val en tête de liste.

On pourrait aussi utiliser une concaténation de liste : lstR = [val] + lstR donnera le même résultat, essaye les deux façons, et surtout remarque bien :

ajouter en tête : lst.insert(0,val) ou lst=[val] + lst
ajouter en queue : lst.append(val) ou lst=lst+[val]
retirer en tête : val = lst.pop(0)
retirer en queue :val = lst.pop()

Rappel :
lst = [1,2,3]
lst.insert(0,7)
-> Maintenant lst vaut [7,1,2,3]

Complexité

Pouvez vous estimer la complexité de ces différents codes de retournement ? Sont ils tous équivalent ?

Trier les éléments

Vous aller programmer ici une fonction tri(lst) qui va trier une liste. L'algorithme utilisé, que nous reverrons plus tard dans une autre forme, est le suivant :

fonction triInsertion(lst) :
  listTriee=[]
  Tant que longueur(lst) > 0 :
    rechercher l'indice du min dans lst
    retirer cet élément (avec pop) et l'ajouter (en queue) dans listeTrie
  fin de tant que
  renvoyer listeTriee
(la fonction idxMin(list) est disponible dans cet exercice)

Dans ce code, que vous venez de faire, on n'a pas vraiment de curseurs (il y en a cependant un, caché dans la fonction idxMin que vous avez utilisé), d'accumulateur, ou de compteur. En effet ici on ne compte rien, on ne somme rien, et on ne localise rien.

L'ajout successif d'élément dans une liste est un autre outil indispensable que vous serez souvent amenés à utiliser.

Complexité

Estimons la complexité de cet algorithme expérimentalement avec time().

En raison de limitations sur ce site, il n'est pas possible de travailler sur de très grandes listes. Néanmoins, ici, on a pris une séries de valeurs de N allant de 10 à 2560. A chaque fois on multiplie N par 2. Le temps de calcul évolue d'abord linéairement pour les petites valeurs de N mais rapidement on voit que quand N est multiplié par 2, le temps est multiplié par 4 (2² !)
La complexité semble donc plutôt proportionnelle à N² dans cet exemple.

Combien de fois est exécutée la boucle while ?
Combien d'opération sont executées dans cette boucle while ?

La réponse est que la boucle while est exécutée N fois, mais dans la boucle, on appelle idxMin. idxMin a une complexité en O(N), mais comme la liste lst est raccourcie au fur et a mesure, c'est un peu compliqué….

Au premier tour, idxMin cherche dans une liste de longueur N
A second tour dans une liste de longueur N-1
Au troisième tour, dans une liste de longueur N-2
etc… jusqu'au dernier tour, ou il ne reste qu'un élément.

si le temps de idxMin est N, alors le temps de tout les appels est :
1 + 2 + … + N = N(N+1)/2 = N² /2 + N/2

pour de grandes valeurs de N, N² >> N, la complexité sera proportionnelle à N². On parle ici de complexité quadratique que l'on note O(N²)

P5.1b premiers algorithmes

Posted on December 4, 2020 by jlt

Utiliser un compteur, un accumulateur, ou un curseur (le tryptique CAC)

Dans de nombreux cas, on doit :

compter le nombre d’occurrence d'une condition, dans ce cas, on utilisera un compteur
sommer (ou faire un produit) dans une boucle, dans ce cas, on utilisera un accumulateur
mémoriser la position d'un élément particulier, dans ce cas, on utilisera un curseur

Un compteur en action

Les compteurs sont des variables qu'on incrémente quand on trouve un éléments correspondant à un critère. Parfois il n'y a pas vraiment de critère, on compte simplement tout les éléments ou toutes les occurrences, mais la notion de comptage est fréquente en algorithmique. Nous avons déjà vu des utilisations de compteurs.

Multiples de 3

Avant de coder cette fonction, écrit le pseudocode de l'algo au brouillon
quand tu as écrit ton pseudo code, demande à ton professeur de le valider puis
recopie le sur le document papier puis implémente le ci-dessous.

Ecrire une fonction qui prend en argument une liste de nombres et renvoi le nombre de multiples de 3 dans cette liste

📌 Utiliser la syntaxe ne portant pas sur les indices pour parcourir la liste

Complexité

L'algorithme contient une boucle sur les éléments de la liste lst.

Avant la boucle on a 1 affection → 1 opération élémentaire
La boucle est exécutée N fois (nb d’élément dans la liste) et dans cette boucle il y a : 1 opération (%), un test, une addition et une affectation. → 4*N opérations élémentaires
Après la boucle il n'y a rien → 0 opération élémentaire

On a donc au total, 1+4N + 0 opérations élémentaires dans ce code.
<br>
4N+1 est une fonction linéaire, on dit qu'on a une complexité linéaire et on note O(N)

Pour appréhender cette complexité "proportionnelle à N" on va mesurer le temps mis par l'algorithme pour donner la réponse
on va mesurer le temps mis pour calculer la moyenne d'une liste de N nombres avec N=10 puis 100 puis 1000 etc … jusqu'à 1 million.
A chaque fois on multiplie N par 10 et on obtient un temps t (on à par exemple le t100 pour n=100, et le t1000 pour N=100 ) et on affichera t1000 / t100 pour voir le rapport entre le deux.
pour le 1er calcul on ne peux pas comparer au t précédent, on le divisera par 1.

On observe donc que lorsque le nombre N d'éléments de la liste est multiplié 10, le temps de calcul est multiplié aussi par un facteur du même ordre de grandeur. Nous observons donc encore bien ici une complexité linéaire.

Un accumulateur en action

Pour sommer ou multiplier (ou soustraire ou diviser) dans une boucle, on utilise une variable accumulateur. Nous avons déjà vu des utilisations d'accumulateurs.

Calcul de la moyenne

Complexité

L'algorithme contient une boucle sur les éléments de la liste lst.

Avant la boucle on a 1 affection → 1 opération élémentaire
La boucle est exécutée N fois (longueur de la liste) et dans cette boucle il y a une addition et une affectation. → 2*N opérations élémentaires
Après la boucle il n'y a rien → 0 opération élémentaire

On a donc au total, 1+2N + 0 opérations élémentaires dans ce code.
<br>
2N+1 est une fonction linéaire, la complexité est linéaire soit O(N)

Comme pour les multiples de 3 précédemment évaluons la complexité en executant le programme ci-dessous.

On observe bien lorsque le nombre N d'éléments de la liste est multiplié 10, le temps de calcul est multiplié aussi par un facteur du même ordre de grandeur. Nous observons donc encore bien ici une complexité linéaire.

Un curseur en action

Les curseurs sont des variables qui retiennent la position (l'index) d'un élément présentant une caractéristique particulière dans une liste. Un bon exemple est la recherche de la position du max des éléments d'une liste.

Indice du maximum

Complexité

L'algorithme contient une boucle sur les éléments de la liste lst de longueur N (en partant du 2ème)

Avant la boucle on a 1 affection → 1 opération élémentaire
La boucle est exécutée N-1 fois et dans cette boucle il y a une comparaison addition et une affectation. → 2(N-1) opérations élémentaires
Après la boucle il n'y a rien → 0 opération élémentaire

il y a donc 1+2N-2 = 2N-1 opérations élémentaires
On a donc une complexité linéaire soit O(N)

Il existe une variante (qu'on retrouve généralement dans tous les algorithme utilisant un curseur) à l'algorithme que nous venons de voir.

Si, au lieu de l'indice de la valeur maxi, on cherche la valeur elle même, l'algorithme est légèrement différent.:

Écrivez le pseudo-code modifié pour satisfaire cette recherche, faites le valider par votre professeur, recopier le sur votre feuille puis implementer le ci-dessous.

La tarte aux fruits

Posted on October 16, 2020 by jlt

Vous devez écrire un code qui va produire une recette de cuisine.
Vous devrez écrire les fonction suivantes :

cuisson( duree , temp ) :
Entrées :
duree (int) : temps de cuisson en minutes
temp (int) : température du four en degrés
Sortie :
cuisson renvoie une chaine de caractères contenant un message tel que :
"enfourner la tarte 45mn à 180°\n"
(Le \n est un retour à la ligne).
garnir( fruit , surface , tailleTarte )
Entrées :
fruit (str) : le type de fruit utilisé
surface (float) : la surface couverte avec un seul fruit (cm²)
tailleTarte (int) : le diametre du plat à tarte (6 ou 22 cm)
Sortie :
garnir renvoie une chaine de caractère et un entier :
La chaine est du type :
"Epluchez les pommes, garnir le plat.\n"
l'entier indique le nombre de fruits nécessaires.
Il faudra donc garnir le plat avec un fruit et recommencer jusqu'à ce que le plat soit entièrement garnit.
assemble(txt1,txt2,txt3,txt4) : assemblage des 4 lignes de la recette (dans le bon ordre)

La recette que votre code doit produire :

ingredients : 6 pommes et un fond de tarte.
Epluchez les pommes, garnir le plat.
enfourner la tarte 45mn à 180°
servir la tarte aux pommes

Mais attention ! Dans le cas d'une tarte aux fraise, on ne doit pas cuire les fraises... dans ce cas la recette sera :
ingredients : 26 fraises et un fond de tarte.
enfourner la tarte 45mn à 180°
Epluchez les fraises, garnir le plat.
servir la tarte aux fraises

Le nombre de fruits est celui calculé par la fonction garnir.

Partie 1 : Ecrire la fonction cuisson

Partie 2 : Ecrire la fonction garnir

T SDD4 Parcours de graphes

Posted on October 2, 2020 by jlt

Comme les autres structures de données, nous avons souvent besoin de parcourir un graphe.

Ci-contre un graphe non orienté, contenant 8 sommets et 10 arrêtes.

Sa matrice d'adjacence se définit ainsi :

matrice = [[0,1,1,0,0,0,0,0],
          [1,0,0,1,1,0,0,0],
          [1,0,0,1,0,0,0,0],
          [0,1,1,0,1,0,0,0],
          [0,1,0,1,0,1,1,0],
          [0,0,0,0,1,0,1,0],
          [0,0,0,0,1,1,0,1],
          [0,0,0,0,0,0,1,0]]

Sa liste d'adjacence s'écrit
A : B,C
B : A,D,E
C : A,D
D : B,C,E
E : B,D,F,G
F : E,G
G : E,F,H

Deux stratégies possibles

Recherche en profondeur d'abord, nommée Depth First Search alias DFS
Recherche en largeur d'abord, nommé BFS, Breadth First Seard, alias BFS

Recherche en profondeur d'abord

ci-dessous le sujet (à compléter) au format pdf

https://cscircles.cemc.uwaterloo.ca/wp-content/uploads/deroule-dfs-nonrec.pdf

Activité débranchée : Recherche en profondeur d'abord

Pour parcourir le graphes en profondeur d'abord :

on commence avec un nœud donné (point de départ)
on explore chaque branche complètement avant de passer à la suivante. Autrement dit, on commence d'abord par aller le plus profond possible. Comme pour les arbres, cet algorithme s'écrit naturellement de manière récursive.

Donc, parcourir un graphe en profondeur à partir d’un sommet, consiste à explorer le graphe en suivant un chemin. Lorsqu’on arrive sur un sommet qui n’a plus de voisins non visités, on remonte dans le chemin pour explorer les voisins non visités d’un autre sommet…

Première version : non récursive
On utilise une pile (aVoir) et une liste (vus)

Prenons en exemple le graphe montré plus haut :
On dispose

d’un graphe
d'une liste vus sommets_visités
et d’une pile aVoir des sommets à visiter

Algorithme de parcours DFS

Le sommet de départ est par exemple ’G’ on ajoute ce sommet de départ dans vus
On met dans la pile aVoir tous les voisins de G
Puis, tant que aVoir n’est pas vide :

• On récupère le sommet de la pile aVoir dans une variable sommet et on ajoute sommet dans vus
• on empile tous les voisins (non déjà visités et non déjà à voir) de sommet dans aVoir

Voici les contenus des variables au premier tour de la boucle tant que :

Au début:

sommet = g
aVoir: [h,f,e]
1er tour de la boucle :
sommet=e
vus : [g,e]
aVoir = [h,f,d,b]

Au second tour de la boucle tant que :

2nd tour
sommet = b
vu = [g,e,b]
aVoir : [h,f,d,a]

Au troisième tour de la boucle tant que :

3ème tour
sommet = a
vu = [g,e,b,a]
aVoir : [h,f,d,c]

Au quatrième tour de la boucle tant que :

4ème tour
sommet = c
vu = [g,e,b,a,c]
aVoir : [h,f,d]

Au cinqième tour de la boucle tant que :

5ème tour
sommet = d
vu = [g,e,b,a,c,d]
aVoir : [h,f]

Au sixième tour de la boucle tant que :

6ème tour
sommet = f
vu = [g,e,b,a,c,d,f]
aVoir : [h]

Au septième tour de la boucle tant que :

7ème tour
sommet = h
vu = [g,e,b,a,c,d,f,h]
aVoir : []
la boucle s'arrête

la liste aVoir est utilisée comme une PILE. On empile les voisins du sommet que l'on visite, puis on les dépile, c-a-d qu'on repart du dernier sommet empilé. C'est pour cette raison que l'on parcours l'arbre en profondeur, on commence par les voisin du dernier sommet. Si on utilisait aVoir comme une file, on parcourrais en largeur (ce que nous ferons plus loin).

Voici une représentation schématique du parcours que nous venons de faire, si on représente le graphe avec G en haut, puis par couche selon la distance à G :

Implémentation non récursive de l'algorithme

Algorithme :

Placer le sommet de départ dans vus Empiler les voisins de ce sommet dans aVoir tant que aVoir n'est pas vide : depiler le prochain sommet l'ajouter dans vus ajouter ses voisins non vus et non à voir dans aVoir

Implémentation récursive de l'algorithme DFS

Algorithme :

DFS(gr , sommet , vus) :
Placer le sommet de départ dans vus
pour chaque voisin de liste des voisins de ce sommet :
   si le voisin n'est pas déjà vu :
     DFS(gr,voisin,vus)
renvoyer la liste vus

Recherche en largeur d'abord

Activité débranchée : Recherche en LARGEUR d'abord BFS

https://cscircles.cemc.uwaterloo.ca/wp-content/uploads/deroule-bfs.pdf

Pour parcourir le graphes en largeur d'abord :

Algorithme de parcours BFS

on commence avec un nœud donné (point de départ)
on ajoute ce sommet dans vus
on enfile les voisins de ce sommet dans aVoir
tant que la FILE aVoir n'est pas vide :
-- on defile le prochain sommet et on l'ajoute dans la liste vus
-- on enfile ses voisins dans aVoir

Donc, parcourir un graphe en largeur à partir d’un sommet, consiste à explorer le graphe en explorant systématiquement tous les voisins d'un sommet avant de descendre dans la profondeur du graphe.

Voici les contenus des variables au premier tour de la boucle tant que :

Au début:

sommet = g
aVoir: [e,f,h]
1er tour de la boucle :
sommet=e
vus : [g,e]
aVoir = [f,h,d,b]

Au second tour de la boucle tant que :

2nd tour
sommet = f
vu = [g,e,f]
aVoir : [h,b,d]

Au troisième tour de la boucle tant que :

3ème tour
sommet = h
vu = [g,e,f,h]
aVoir : [b,d]

Au quatrième tour de la boucle tant que :

4ème tour
sommet = b
vu = [g,e,f,h,b]
aVoir : [d,a]

Au cinqième tour de la boucle tant que :

5ème tour
sommet = d
vu = [g,e,f,h,b,d]
aVoir : [a,c]

Au sixième tour de la boucle tant que :

6ème tour
sommet = a
vu = [g,e,f,h,b,d,a]
aVoir : [c]

Au septième tour de la boucle tant que :

7ème tour
sommet = c
vu = [g,e,f,h,b,d,a,c]
aVoir : []
la boucle s'arrête

la liste aVoir est utilisée comme une FILE. On enfile les voisins du sommet que l'on visite, puis on les défile, c-a-d qu'on repart du premier sommet enfilé. C'est pour cette raison que l'on parcours l'arbre en largeur, on commence par les voisins des premier sommets visités.

Voici une représentation schématique du parcours que nous venons de faire, si on représente le graphe avec G en haut, puis par couche selon la distance à G :

Implémentation (non récursive) de l'algorithme BFS

Algorithme :

Placer le sommet de départ dans vus Enfiler les voisins de ce sommet dans aVoir tant que aVoir n'est pas vide : defiler le prochain sommet l'ajouter dans vus ajouter ses voisins non vus et non à voir dans aVoir