[Distance Education in Python]

T - 4.3 Files

Publié le juillet 9, 2020 par jlt

II. Les Files

Vous allez vous-même compléter ci-dessous une possible implémentation de ces fonctions primaire, en utilisant le vocabulaire de la programmation orientée objet que nous avons déjà abordée. Dans toute la suite les files seront affichées entre crochets, comme des list python. Le coté du défilage est l'élément écrit le plus à droite. Ainsi, si l'on part d'une file vide, et que l'on enfile successivement les entiers 1, puis 2, puis 3, on obtiendra une file qui s'affichera de la façon suivante : [3, 2, 1]. Le sommet de cette file est l'entier 1.

Pour ne pas perdre de vue le sens de la File, la méthode str permettra d'afficher de quel coté on enfile et de quel coté on défile. Ce choix est arbitraire.

Implementer les fonctions primaires

Exercice de code

class File :
    def __init__(self) -> None:
        """
        les objets de classe File ont un seul attribut lst, de type list
        l'attribut lst est initialisé à une liste vide
        """     


    def est_vide_file(self) _> bool :
        """
        renvoie True si l'atrribut lst est une liste vide, False sinon
        """     

    def enfiler(self, x) -> None:
        """
        Insère la valeur x à l'indice 0 de l'attribut lst
        """     

    def defiler(self):
        """
        supprime la derniere valeur de l'attribut lst, et renvoie cette valeur
        précondition : l'attribut lst ne doit pas être une liste vide
        si la précondition n'est pas vérifiée, la méthode lève une exception ValueError
        """


    def __str__(self) :
        return "enfilage -> " + str(self.contenu) + " -> défilage"

#les lignes ci-dessous sont requises pour la validation
file1 = File()
print(file1);
file2 = File()
file2.enfiler(3)
print(file2)
file3 = File()
file3.enfiler(3)
file3.enfiler(7)
file3.defiler()
print(file3)

Maintenant que vos primitives sont définies vous allez pouvoir les tester

A vous de jouer !

Écrire ci dessous les instructions qui permettent d'obtenir successivement les affichages suivants :

enfilage -> [8] -> défilage
enfilage -> [14, 8] -> défilage
enfilage -> [12, 14, 8] -> défilage
enfilage -> [12, 14] -> défilage
enfilage -> [12] -> défilage
enfilage -> [] -> défilage

T4.3 dictionnaire versus listes

Publié le juillet 9, 2020 par jlt

Dans une bibliothèque, nous avons 10000 livres. Pour chacun un certain nombre de caractéristiques : auteur, date de parution, nombre de pages etc...

Nous allons nous limiter à une seule caractéristique, par exemple le nombre de pages. Chaque livre à donc un nombre de page (remarquons qu'inversement, plusieurs livres peuvent avoir le même nombre de pages).

Nous aimerions trouver le plus rapidement possible le nombre de pages d'un livre. Nous devons décider comment représenter la situation. Nous pouvons utiliser des tuples (livre, nbDePages), on construira alors une liste de tuples, ou nous pouvons utiliser un dictionnaire : {livre1: nbDePages1, livre2: nbDePages2 etc...}

A première vue, laquelle des deux représentations vous semble la plus adaptée (laquelle vous semble plus naturelle) ?

Par ailleurs, ce choix aura-t-il un impact en terme d'efficacité dans la recherche ?

C'est ce que nous allons explorer dans ce TP.

👉 Nous utilisons ici le type : list de python

Implémenter avec une liste ou un dictionnaire

Implémentation avec liste ou dictionnaire

Exercice de code : représenter le problème avec une liste de tuples

Vous disposez de 2 listes : une liste de livres, et une liste de nombre de pages. Les deux listes sont en correspondance : nbPages[i] est le nombre de pages de livre[i].
En utilisant ces deux listes vous devez en construire une nouvelle, avec des tuples (livre, nombre de pages).
Ensuite, en repartant de cette liste, construire un dictionnaire comme décrit plus haut.

livre = []
nbPages = []
livre.append("Un soir au club")
nbPages.append(231)
livre.append("Ada ou l'Ardeur")
nbPages.append(452)
livre.append("Le père Goriot")
nbPages.append(320)
livre.append("Les misérables")
nbPages.append(603)
livre.append("L'étranger")
nbPages.append(257)
# Votre code ici : former une liste de tuples à partir des 2 listes crées ci-dessus

print(liste)

# former de même un dictionnaire en réutilisant la liste créée :

print(dico)

Rechercher l'information souhaitée

Fonctions de recherche de l'information

Bravo ! Vous avez bien implémenté les deux modèles. Maintenant, créez deux fonctions pour trouver le nombre de pages d'un livre.

Exercice de code : Chercher l'information

Le correcteur automatique va maintenant générer pour vous une liste et un dictionnaire, comme vous l'aviez fait dans l'exercice précédent.
Vous devez coder deux fonctions de recherche, l'une dans la liste, l'autre dans le dictionnaire, renvoyant toute deux le nombre de page d'un livre.
Votre code ne doit rien afficher, le correcteur définira des arguments pour tester vos deux fonctions.

def findInList(livre: str, liste: list) -> int:
    """
    cherche le livre dans liste et renvoie le nombre de page
    """
    pass

def findInDico(livre: str, dico: dict) -> int:
    """
    cherche le livre dans le dictionnaire et renvoie le nombre de page
    """
    pass

Mesure d'efficacité

Mesure de l'efficacité

La liste et le dictionnaire générés sont de taille très limitée, aussi la mesure de l'efficacité de l'un et l'autre n'est pas aussi probante que si nous travaillions avec des listes de 10000 livres.

Néanmoins nous pouvons comparer la recherche dans la liste et la recherche dans le dictionnaire.

Exercice de code : Chercher l'information

Le correcteur automatique va maintenant générer pour vous

une liste et un dictionnaire, comme précédemment, nommées liste et dico
les deux fonctions de recherche findInlist et findInDico
une variable livre1.

Tout ce que vous avez à faire est d'inclure des appels répétés (disons 10000 fois) à chacune de vos fonction, pour mesurer les temps des recherches.

Vous rechercherez livre1 dans la liste, ou dans le dico.

Pour une fois, le correcteur ne tiendra pas compte des affichage en console pour évaluer votre code, mais il évaluera quand même le résultat important : quelle méthode est la plus efficace ?

from time import time

nb_appels = 10000

t = time()
# faire nb_appels appels à findInList

dt1 = time() - t
print("temps moyen avec la liste : ", dt1/nb_appels)

t = time()
# idem pour findInDico

dt2 = time()-t
print("temps moyen avec le dico :", dt2/nb_appels)
# cette dernière ligne sert pour le test : on détermine quelle implémentation est plus efficace
winner = "dico" if dt1>dt2 else "liste"

Mesure plus fine de la complexité

Bon, le dictionnaire est plus efficace. Mais ici on travaille sur une bibliothèque de 5 livres.... passons à quelques chose de plus réaliste. Dans l'exemple ci-dessous vous n'avez rien à coder, mais observer et conclure.

On génère pour vous une bibliothèque (c'est à dire, une liste et un dictionnaire) de 10000 livres (bon, les noms des livres ici sont des entiers, mais ça importe peu..). Le code ci-dessous va utiliser les deux fonctions de recherche pour déterminer le nombre de pages d'un livre. On va prendre des livres du début de liste, puis de plus en plus loin dans la liste.... on devrait donc mettre de plus en plus longtemps pour les trouver.

Pour chaque livre la recherche est répétée 100 fois afin d'estimer un temps moyen a peu près stable.

Exemple : Complexités

from time import time
from random import randint
# création de la liste et du dico :
liste = [(i, randint(200, 500)) for i in range(10000)]
dico = {}
for i in range(10000) :
    dico[i] = liste[i][1]
    
print('Dans tous les appels, nous chercherons (dans la liste ou dans le dico) le nieme livre, n étant la longueur de la liste et du dico')

for n in ( 100, 200, 400, 800, 1600) :
    print('résultat avec ',n,' livres')
    t = time()
    for _ in range(n) :
        findInList(n, liste)
    dt1 = time() - t
    print('temps moyen avec la liste :',round(dt1/n*10**6,2),'µs')

    t = time()
    for _ in range(n) :
        findInDico(n, dico)
    dt2 = time() - t
    print('temps moyen avec le dico :',round(dt2/n*10**6,2),'µs')
    winner = 'dico' if dt1>dt2 else 'liste'

Exercice à choix multiple

La complexité de la recherche dans la liste vous semble :

Votre choix :

Correct !

Exercice à choix multiple

La complexité de la recherche dans le dictionnaire vous semble :

Votre choix :

Correct !

T - 4.2 Piles

Publié le juillet 9, 2020 par jlt

I. Les piles

Exemple de primitive

On donne ci-dessous une possible implémentation de ces fonctions primaire, en utilisant le vocabulaire de la programmation orientée objet que nous avons déjà abordée.
Il existe bien d'autres possibilités pour implémenter ces fonctions primaires.
Dans toute la suite les piles seront affichées entre crochets, comme des list python. Le sommet de la pile est l'élément écrit le plus à droite. Ainsi, si l'on part d'une pile vide, et que l'on empile successivement les entiers 1, puis 2, puis 3, on obtiendra une pile qui s'affichera de la façon suivante : [1, 2, 3]. Le sommet de cette pile est l'entier 3.

A vous de jouer !

Ecrire ci dessous les instructions qui permettent d'obtenir successivement les affichages suivants :

[12] <- sommet
[12, 14] <- sommet
[12, 14, 8] <- sommet
[12, 14] <- sommet
[12] <- sommet
[] <- sommet

Autre fonction pour les piles

Alice désire écrire une fonction, qui doit retourner la taille de la pile. Attention, une fois que sa taille a été déterminée, la pile ne doit pas avoir été modifiée...
Elle propose le code suivant :

Le code d'Alice

A vous de résoudre ce problème

Ecrire ci-dessous une fonction taille qui remédie à ce problème Aide1

Applications

Vérifier les parenthèses d'une expression mathématique

Le but de cet exercice est d'écrire une fonction qui contrôle si une expression mathématique, donnée sous forme d'une chaîne de caractères, est bien parenthésée, c'est-à-dire s'il y a autant de parenthèses ouvrantes que de fermantes. On s'interdit d'utiliser des variables qui "comptent" les parenthèses ouvrantes ou fermantes.

Par exemple :

(..(..)..) est bien parenthésée.
(...(..(..)...) ne l'est pas .

L'algorithme :

On crée une pile. On parcourt l'expression de gauche à droite.
Si on rencontre une parenthèse fermante ")", alors :

Si la pile n'est pas vide, on dépile
Sinon on renvoie Faux"

À la fin la pile doit être vide...

Source : Stéphan Van Zuijlen

Compléter la fonction suivante :

T - 4.1 Listes

Publié le juillet 7, 2020 par jlt

introduction

Exemple d'implémentation en Python du type LISTE

Les listes

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 vous n'avez pas besoin de connaître cette implémentation. Il vous 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 avons choisi un affichage qui ressemble à celui du type list de python :

Une liste vide s'écrit []
Exemple de liste : [1, 2, 3]

Comprendre le fonctionnement des primitives

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

A vous d'utiliser les primitives

Dans quel ordre implémenter la liste ?

A vous maintenant !

Autres fonctions

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

Exercice de code : 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, ni in


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

Exercice de code : Compléter cette fonction qui doit retourner élément de rang n.

Votre fonction doit renvoyer la chaine de caractères "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

Utiliser une pile intermédiaire qui servira à empiler ce qui a été dépilé, pour ensuite pouvoir le récupérer