Fichier de rejeu Close

Indication Close

A propos de... Close

Commentaire Close

Téléchargements

Aide

Données

Objectif :

Ce cours poursuit 2 objectifs:
  • Vous rappeler les types de données de base en Python ainsi que les instructions pour les manipuler.
  • Vous permettre de concevoir des structures de données élaborées pour modéliser les informations nécessaires à la réalisation de votre projet.
Objectif 3:
  • manipuler les types de base python
  • représenter et initialiser des données complexes (arbres et graphes)
Validation:
Pour valider cet objectifs, vous devrez être capable de construire, représenter et modifier des données complexes. Une donnée complexe peut par exemple être un dictionnaire contenant une chaîne de caractères et une liste de liste de tuples de 3 entiers. Pour manipuler une telle donnée vous devrez comprendre si elle forme un arbre ou un graphe et pouvoir enchaîner une suite d’opérateur d’indexation : data['map'][2][1]=(2,1,5).

Types de bases

Résumé

Une donnée informatique est une suite de 1 et 0 dans la mémoire de la machine. Lorsqu’on connaît le type d’une donnée, il devient possible de reconstruire la signification de cette suite de bits et donc de la manipuler.

Lorsque nous écrivons un programme, nous manipulons les données en les affectant à des variables. En python, le typage d’une variable est automatique et dynamique puisqu’il correspond au type de la dernière donnée affectée à cette variable. Nous n’avons donc pas besoin de nous soucier du typage de variables. Nous devons néanmoins maîtriser le type des donnée pour les manipuler correctement.

Le tableau suivant récapitule les types de bases que vous avez déjà abordés en cours d’algorithmique. La dernière colonne indique si le type correspond à une donnée mutable ou non, ce qui a un impacts important sur le comportement d’un programme lorsqu’on passe les données en paramètre d’une fonction (voir portée et passage).

Vous pouvez vous référer au cours de S1 pour retrouver les informations concernant ces types, notamment pour les booléens, les entiers et les réels. Nous revenons ici sur les types : str, tuple, list et dict. La page de documentation de Python sur les Built-in Types vous fournira de nombreux éléments pour manipuler ces données.

Les chaînes de caractères

Définition :

chaîne de caractères

Une chaîne de caractères est une séquence non modifiable de caractères.

Quand utiliser une chaîne de caractères?

(Extraits de cahiers des charges)

”...le joueur sera décrit par son score, son nom, sa position...”

”...Lorsqu’on rentre dans une nouvelle pièce, la description de la pièce est affichée sous la carte...”

”...le joueur saisit la réponse au clavier ...”

Les chaînes de caractères servent à de nombreuses choses. Il est essentiel de maîtriser leur manipulation. Voici quelques exemples d’opérations qui peuvent être réalisées:

#creation d'une chaîne
s="toto"

#obtenir la taille
print len(s)

#concatenation de chaines
s1 = "Methodes"+" de"
s2 = " developpement"
s3 = s1 + s2
print s3

#acces à un caractere d'une position donnee.
s4="ABcD"
c=s4[2]
print c

#operation interdite, car une chaine est non modifiable:
s4[2] ="C"

#conversion d'une chaine en entier, puis en reel, puis à nouveau chaine de caracteres :
s5 = str(float(int("12")))
A faire :

Tester toutes ces instructions sur des chaînes de votre invention

Vous pouvez tester ces instructions ici.

python : code_run36.py
Sorties

            

Pour plus d’informations sur la manipulation des chaînes, familiarisez vous avec la documentation de Python. Elle indique l’ensemble des opérations qui peuvent être exécutées sur ce type de données (ici par exemple).

Une chaîne est une séquence de caractères. Nous utiliserons donc les chaînes de caractères pour décrire les données textuelles du jeu. Une chaîne de caractères peut contenir une lettre, un mot, une phrase ou un texte de plusieurs lignes. Elle peut également être vide. Les caractères qui composent la chaîne sont des caractères imprimables ou des caractères de contrôle (tabulation, retour à la ligne...). Basiquement, ces caractères sont codés par des 1 et des 0 (comme toutes les données dans la machine). La table ASCII permet d’établir une correspondance entre le codage binaire du caractère (donné en hexadécimal dans l’exemple) et ce qu’il faut afficher à l’écran:

On peut alors sélectionner un caractères de la table pour l’introduire dans une chaîne de caractères:

#normal
s1 = "ABC"

#octal
s2= "\101BC"

#hexadécimal
s3="\x41BC"

La table ASCII contient tous les caractères pour écrire en anglais. Afin de permettre l’écriture dans d’autres langues, il existe des versions étendues de la table ASCII qui introduisent des lettres accentuées et d’autres caractères spéciaux. L’utilisation de ces extensions a introduit des problèmes de compatibilité d’un pays à l’autre, d’un OS à l’autre, voire d’un logiciel à l’autre. Lorsque que vous lirez des fichiers textes, il peut être utile de connaître le système de codage utilisé. En exécutant le code suivant sur votre machine vous aurez la liste des encodages connu par votre interpréteur Python :

import encodings
for e in sorted(set(encodings.aliases.aliases.values())):
    print e

Une norme fait référence pour répertorier les différents caractères utilisés dans le monde. Il s’agit d’Unicode. Le site http://www.unicode.org/ référence 128 172 caractères. Si Unicode permet de lever les ambiguïtés concernant l’encodage des caractères, la plupart des logiciels ne sont pas capables d’afficher l’ensemble considérable des caractères encodés. Si vous choisissez d’afficher des caractères spéciaux assurez vous que le terminal cible soit capable de les afficher. Pour indiquer à python qu’une chaîne contient des caractères Unicode, il suffit de faire précéder la première guillemet du caractère u:

s = u"\u263a smile"

# http://www.unicode.org/fr/charts/PDF/U2600.pdf

UTF-8 est une méthode d’encodage des caractères Unicode compatible avec le codage ASCII. C’est le système d’encodage le plus utilisé aujourd’hui.

N-uplet (tuple)

Définition :

N-uplet ou tuple

Un N-uplet est une séquence non modifiable d’éléments. Ici, on peut assimiler un N-uplet à une liste non modifiable.

Quand utiliser une N-uplet?

Pour simplifier l’écriture ou pour passer plusieurs paramètres ou valeurs de retour en une seule fois.

Pour modéliser des données non modifiables du programme.

Pour modéliser des clés d’entrée de dictionnaire.

L’utilisation des tuples peut simplifier l’écriture d’un code python. C’est donc un outil intéressant, mais attention, les données d’un tuple ne sont pas modifiables.

#création d'un tuple pour décrire un point
origine= 10 , 50 , 90

#sélection d'éléments du tuple
print "x=",origine[0],"y=",origine[1]

#affectation de plusieurs variables avec un tuple
x,y,z= origine

#création d'un tuple à partir d'un liste
t=tuple([1,2,3])

#code produisant une erreur!!!!!
origine[1]=12
A faire :

Tester les instructions sur les N-uplet

Vous pouvez tester ces instructions ici.

python : code_run40.py
Sorties

            

Listes

Définition :

Liste

Une liste est une séquence variable d’éléments.

Quand utiliser une liste?

(Extraits de cahiers des charges)

”...le personnage possède un certain nombre d’objets dans son inventaire... “

”...une question sera choisie au hasard parmi tous les QCMs disponibles...”

”...il est possible d’afficher les dix meilleurs scores du jeu... “

”...les joueurs posent leurs pions sur une grille de 8 par 8 cases....”

A la différence des tuple, les listes sont modifiables. Il existe plusieurs opérations permettant de manipuler les listes. Recherchez et consultez la documentation Python.

#création d'une liste vide
l=[]

#création d'une liste avec des éléments
l=[1,2]
l.append(3)
l.append(4)
for i in l:
    print i

#création d'une liste de caractères à partir d'une chaîne de caractères
l=list("toto")

L’utilisation de listes de listes vous permet de créer des grilles en deux dimensions, des plateaux de jeux ou des images...

#image stickman
img=[]
img.append([' ','o',' '])
img.append(['-','|','-'])
img.append([' ','|','\\'])

#on bouge la jambe!
img[2][1]=' '
img[2][0]='/'

Voici un code qui pourrait vous être utile par la suite pour initialiser des grilles vides (on ne vous demande pas de le comprendre!):

matrix = [[0 for x in range(3)] for x in range(2)]

# [ [0,0,0],
#   [0,0,0] ]
A faire :

Tester les instructions sur les listes

Vous pouvez tester ces instructions ici.

python : code_run44.py
Sorties

            

Dictionnaires

Définition :

Dictionnaire

Un dictionnaire python est un conteneur qui associe des données à une clé. Le dictionnaire appartient à la famille des tables de hachage. La clé est souvent une chaîne de caractères mais peut être une autre donnée hachable (entier, réel, N-uplet).

Quand utiliser un dictionnaire?

(Extraits de cahiers des charges)

”...Le joueur possède un annuaire qui attribut un numéro à chaque personne rencontrée...”

”...on mémoirise la liste des actions rélaisées à chaque coordonnées de la carte...”

#création
dic = {'prenom': 'Jean', 'nom': 'Dupond'}

#parcours des clés
for cle in dic:

    #recupération d'un élément avec la clé
    print cle, ":", dic[cle]

#ajout d'un nouvel eleent
dic['tel']='0298056600'

#test de la présence d'une clé
if 'tel' in dic:
    print 'Téléphone:', dic['tel']

#suppression d'une entrée du dictionnaire.
del dic['mail']

Objets

Un objet est une donnée qui est utilisée dans la programmation orientée objet. Le cours de IPI précède le cours de programmation orientée objet, en conséquence de quoi nous ne définirons que partiellement la notion d’objet. En fait nous assimilerons un objet un dictionnaire que l’on manipulerait avec une synthaxe différente. En plus de ça, un objet appartient à un type que nous déclarons avec le mot clé class

Quand utiliser un dictionnaire?

(Extraits de cahiers des charges)

”...Le joueur est caractérisé par un nom, un score, une position...”

”...Pour chaque question, on propose 3 réponses parmi lesquelles la bonne réponse...”

Les objects seront les données que vous utiliserez le plus pour décrire les données de votre jeu. Nous nous en servirons pour implémenter les types abstraits de données (voir cours suivant).

#declaration du type
class Perso: pass

#création
obj=Perso()
obj.prenom="Jean"
obj.nom="Dupond"

#récupération d'une valeur
print(obj.prenom)


#pour obtenir le dictionnaire équivalent:
dic=obj.__dict__

print(dic)

On peut également voir un objet comme un espace de nommage qui nous permet de ranger des variables (prenom et nom) dans une variable (obj)

Exercices

  1. Chaîne et Liste : Découper un texte

    Lorsque vous lirez un fichier texte, vous obtiendrez une grande chaîne de caractères qui contiendra l’ensemble du texte lu. Selon ce que vous voulez en faire, vous pourriez avoir besoin de séparer le texte en phrases.

    Proposer un code pour la fonction splitSentences() qui découpe un texte passé en paramètre en une liste de phrases qui seront chacune une chaîne de caractères. Vous pouvez utiliser les fonctions split(),``pop()``, replace().

    Pour traiter cet exercice, vous devez vous documenter sur l’utilisation de la fonction split(), par exemple ici https://docs.python.org/3/library/stdtypes.html.

    texte= "L'ENIB est une école publique installée à Brest, accréditée par la Commission desTitres d'Ingénieur, membre de la\nConférence des Grandes Écoles et associée à l'Institut Mines-Télécom. L'école forme en 5 ans des ingénieurs\ngénéralistes dans les domaines de l'électronique, de l'informatique et de la mécatronique en lien avec une recherche\nde haut niveau. L'école, tout en préparant ses élèves ingénieurs à exercer leur futur métier dans un cadre\ninternational, offre des enseignements originaux, en lien direct avec ses valeurs d’humanisme, d’ouverture d’esprit et\nd’engagement sociétal. La formation académique est complétée par des stages en entreprise et des activités\nprofessionnalisantes tout au long du cursus."
    
    Votre réponse :
    python : code_run50.py
    Sorties
    
                
    Commentaires

    Consulter la documentation en ligne Python: Built-in Types pour comprendre l’utilisation de split().

    Une solution possible :
    def splitSentences(txt):
        #decoupage du texte en phrase
        sentences=txt.split('.')
    
        #supression de la dernière phrase vide.
        sentences.pop()
    
        #nettoyage des phrases
        for i in range(len(sentences)):
            #suppression des \n
            s=sentences[i].replace("\n",' ')
    
            #ajout d un point en fin de phrase.
            sentences[i] = s + "."
    
        return sentences
    
  2. Chaîne et Liste : Image

    En utilisant l’opération split() et list(), proposez un code qui transforme une image ASCII contenue par une chaîne, en une liste de listes de caractères.

    texte= "  _____   \n"+
           " /     \  \n"+
           "| () () | \n"+
           " \  ^  /  \n"+
           "  |||||   \n"+
           "  |||||   "
    
    Votre réponse :
    python : code_run54.py
    Sorties
    
                
    Commentaires

    Consulter la documentation en ligne Python: Built-in Types.

    Une solution possible :
    def splitImage(texte):
    
        #separation des lignes
        lines=texte.split("\n")
    
        #séparation des colonnes
        img=[]
        for l in lines:
            img.append(list(l))
    
        return img
    
  3. Chaîne et Dictionnaire : Image

    Même question que pour l’exercice précédent mais au lieu de produire une liste de liste, construisez un dictionnaire qui contient chacun des caractères. La clé d’entrée pour accéder à un caractère sera un 2-uplet de deux entiers correspondant à la position du caractère dans l’image.

    texte= "  _____   \n"+
           " /     \  \n"+
           "| () () | \n"+
           " \  ^  /  \n"+
           "  |||||   \n"+
           "  |||||   "
    
    Votre réponse :
    python : code_run58.py
    Sorties
    
                
    Commentaires

    Consulter la documentation en ligne Python: Built-in Types.

    Une solution possible :
    def splitImage(texte):
            #separation des lignes
            lines=texte.split("\n")
    
            #separation des colonnes
            img={}
            for i in range(len(lines)):
                for j in range(len(lines[i])):
                    img[i,j]=lines[i][j]
            return img
    

Portée et passage

Les données sont contenues dans des variables. Vous devez vous rappeler qu’une variable a une portée; c’est à dire qu’elle n’est connue que dans un certain contexte. Par exemple une variable locale n’est connue que dans la fonction dans la quelle on l’utilise.

Par ailleurs, certaines données, selon leur type, sont modifiables ou non modifiables. On parle de type mutable ou non mutable. Il faut bien comprendre que si on passe une donnée non modifiable (entier, réel, chaîne...) en paramètres d’une fonction, cette fonction ne pourra en aucun cas modifier cette donnée. A l’inverse, si la donnée peut être modifiée alors il sera possible pour la fonction de produire un effet sur cette donnée.

Expérimentez le code suivant pour bien identifier la différence entre la modification d’une donnée et la ré-affectation d’un variable.
python : code_run60.py
Sorties

            

Données complexes

Arbres

Définition :

Arbre de données

Un arbre est une structure de données récursive tel que chaque donnée, sauf la racine, possède un unique parent. Un arbre est un graphe particulier. Dans la pratique, nous construirons des arbres avec des dictionnaires, des listes ou des tuples.

Quand utiliser un arbre de données?

(Extraits de cahiers des charges)

”... Le jeu se compose de joueurs et d’un plateau. Chaque joueur est décrit par un nom, une position, une vitesse. Le plateau se décompose en cases, chaque case contient un mur ou une liste d’objets...”

Dès qu’on commence à utiliser des dictionnaires ou des listes on commence à construire des arbres de données. Le jeu que vous réaliserez mettra très probablement en œuvre des arbres de données. Il s’agit dans un premier temps d’être capable de représenter graphiquement ces arbres.

a = 12
b = 'toto'
l = [ a, b ]
s = 'clé'
c1 = s, 0 # création d'un tuple
c2 = s, 1 # idem
data = { c1: l, c2: None } #les tuple peuvent servir de clé dans un dictionnaire

Vous pouvez représenter l’arbre de données correspondant à la variable data de la manière suivante. Comprenez vous le lien entre le code précédant et l’image suivante?

_images/arbre1.png

Ici le dessin d’une liste de liste de 9 éléments représentant une grille de jeu de Morpion:

_images/arbre2.png

Faites vous le lien avec le code suivant?

grilleMorpion = [['X','O',' '],['X','X','X'],['O',' ','O']]

Vous devez être capable de lire, modifier et concevoir des arbres de données.

  1. Arbre de données 1

    Dessinez l’arbre de données contenu par la variable ‘gameData’.

    def initGame():
        global gameData
        img=[]
        img.append('++++++')
        img.append('+    +')
        img.append('+    +')
        img.append('+    +')
        img.append('++++++')
        gameMap={'size':5,'matrix':img}
    
        monsters={(1,1):'troll',(3,2):'goblin'}
    
        items=['potion','sword','bow']
        player={'name':'bob','score':0,'bag':items,'position':(2,2)}
    
        gameData={'map':gameMap,'player':player,'monsters':monsters}
    
    Votre réponse :
    Arbre de données : graph65.json

    Nœuds

    Vue d'ensemble
    Une solution possible :
    _images/exoArbre1.png
  2. Arbre de données 2 : QCM

    Initialisez la variable QCM pour que sa valeur corresponde à l’arbre de données suivant:

    _images/exoArbre2.png
    Votre réponse :
    python : code_run69.py
    Sorties
    
                
    Commentaires

    Vous pouvez utiliser une variable comme compteur d’itérations.

    Une solution possible :
    QCM={}
    QCM['Question']="Quelle est la couleur du cheval blanc d'Henri IV?"
    QCM['wrongAnswers']=['vert','12','bleu']
    QCM['answer']='blanc'
    
  3. Arbre de données 3 : Cibles

    Voici un exemple d’évaluation de ce chapitre de l’Enibook.

    Votre réponse :
    Arbre de données : graph73.json

    Nœuds

    Vue d'ensemble
    python : Donnees3.py
    Sorties
    
                
    Une solution possible :
    _images/Donnees3_correction.png
    '''
    IPI - Controle Continu : Objectif 3 : Données
    
    Voici l'initialisation d'une donnee "gameData" d'un jeu de tir :
    
    NE PAS MODIFIER LE CODE CI DESSOUS !
    
    '''
    import random
    
    
    txt="00000#01000#00300#00500#50300"
    
    lines=txt.split('#')
    img=[]
    
    for l in lines:
        img.append(list(l))
    
    x = random.randint(0,4);
    
    gameData={'score':0,'target':(x,0)}
    
    gameData['grid']=img
    
    # QUESTION 1
    # =======================================================================================
    '''
        Viser : Proposer un code qui modifie l'ordonnee de la cible ('target') sans
        changer son abscisse, pour qu'elle corresponde a la derniere ligne de la grille
        (grid). L'ordonnee étant le deuxieme element du tuple désigne par la cle target.
    '''
    
    gameData['target']= (gameData['target'][0],len(gameData['grid'])-1)
    
    
    # QUESTION 2
    # =======================================================================================
    '''
        Tirer ! :
            -Si la valeur de la case sur laquelle on tire est '0' , le score est divisee par deux.
            -Sinon on ajoute au score la valeur de la case ciblee. Par exemple, le caractere '5'
              augmente le score de 5 points. Proposer un code qui met à jour le score en fonction
              de la case ciblee.
    '''
    
    if (gameData['grid'][gameData['target'][1]][gameData['target'][0]] == 0):
        gameData['score'] = gameData['score']/2;
    else:
        gameData['score'] = gameData['score'] + int(gameData['grid'][gameData['target'][1]][gameData['target'][0]]);
    
    
    # QUESTION 3
    # =======================================================================================
    '''
        Tirer ! (suite) :Proposer un code qui met un '0' dans la case que l'on vient d'atteindre.
    '''
    gameData['grid'][gameData['target'][1]][gameData['target'][0]] = '0'
    
    print gameData
    

Graphes

Définition :

Graphe

un graphe est une collection de données mises en relation entre elles. Un graphe contient des noeuds (les données) et des liens (les relations binaires entre les données). Dans la pratique, non construirons des arbres avec des dictionnaires.

Quand utiliser un graphe?

”...Le donjon contient plusieurs salles reliées par des portes...”

”...Le jeux reprend le principe des livres dont vous êtes le héros...”

La théorie des graphes est un vaste sujet d’étude. Il existes de nombreux algorithmes de parcours de graphes (on peut citer celui du “voyageur de commerce” qui permet de trouver le plus court chemin pour parcourir l’ensemble des sommets d’un graphe), de preuve, de recherche, de représentation, etc... Ici, nous ne faisons qu’effleurer ce thème en imaginant comment on peut représenter des arcs et des sommets avec des données python et imaginer à quoi peut servir un graphe dans le projet.

Un graphe permet de montrer que des éléments (les somments) sont en relation (les arcs) avec d’autres éléments. Ces éléments peuvent être des pièces, des niveaux de jeux, des éléments d’histoire ou de scénario, des points sur une carte, etc...

On peut coder les graphes de plein de manières différentes selon comment on souhaite les utiliser. Vous pourrez imaginer votre propre solution. voici trois exemples de codage de graphes :

_images/graphe1.png
#Chaque cle du dictionnaire est un sommets
graph = {'A': ['B', 'C'],
         'B': ['C', 'D'],
         'C': ['D'],
         'D': ['C'],
         'E': ['F'],
         'F': ['C']}
#chaque sommet est un dictionnaire

a={'voisins'=[],'nom':'A'}
b={'voisins'=[],'nom':'B'}
c={'voisins'=[],'nom':'C'}
d={'voisins'=[],'nom':'D'}
e={'voisins'=[],'nom':'E'}
f={'voisins'=[],'nom':'F'}

a['voisins'].append(b)
a['voisins'].append(c)
b['voisins'].append(c)
b['voisins'].append(d)
c['voisins'].append(d)
d['voisins'].append(c)
e['voisins'].append(f)
f['voisins'].append(c)

graphe=[a,b,c,d,e,f]
#liens codes sous forme matricielle
graph = {'sommets': ['A','B','C','D','E','F'],
         'arcs'  : [[0,1,1,0,0,0],
                    [0,0,1,1,0,0],
                    [0,0,0,1,0,0],
                    [0,0,1,0,0,0],
                    [0,0,0,0,0,1],
                    [0,0,1,0,0,0]] }
  1. Graphe appartement

    Dessinez le graphe décrit dans le code suivant.

    p1={'nom':'cuisine','portes':[]}
    p2={'nom':'salon','portes':[]}
    p3={'nom':'couloir','portes':[]}
    p4={'nom':'chambre','portes':[]}
    p1['portes'].append(p2)
    p1['portes'].append(p3)
    p2['portes'].append(p1)
    p2['portes'].append(p3)
    p3['portes'].append(p2)
    p3['portes'].append(p1)
    p3['portes'].append(p4)
    p4['portes'].append(p3)
    
    Votre réponse :
    Arbre de données : graph80.json

    Nœuds

    Vue d'ensemble
    Une solution possible :
    _images/appartement.png
  2. Dessin graphe villes

    Représentez le plan suivant par un graphe.

    _images/carteducoin.png
    Votre réponse :
    Arbre de données : graph84.json

    Nœuds

    Vue d'ensemble
    Une solution possible :
    _images/villes.png
  3. Codage villes

    Codez le plans suivant par un graphe.

    _images/carteducoin.png
    Votre réponse :
    python : code_run88.py
    Sorties
    
                
    Une solution possible :
    brest     ={'nom':'Brest',     'routes':[]}
    saintRenan={'nom':'SaintRenan','routes':[]}
    plougastel={'nom':'Plougastel','routes':[]}
    leConquet ={'nom':'LeConquet', 'routes':[]}
    
    brest['routes'].append((plougastel,12))
    brest['routes'].append((saintRenan,13))
    brest['routes'].append((leConquet,32))
    
    saintRenan['routes'].append((brest,13))
    saintRenan['routes'].append((leConquet,15))
    
    leConquet['routes'].append((saintRenan,15))
    leConquet['routes'].append((brest,32))
    
    plougastel['routes'].append((brest,13))