Python L1, TD/TP 25.03

N'oubliez pas que vous avez aujourd'hui un exercice obligatoire ! Il sera consacré à la gestion des fichiers, et le traitement de leur contenu. Vous avez 3 jours [depuis la publication de ce texte] pour travailler ce sujet en profondeur.

Nous devons terminer les exercices restants de la semaine dernière. Concrètement, faisons l'exercice 5 et l'exercice 7.

L'exercice (5) de la semaine dernière porte très partiellement sur la lecture des fichiers. Les fichiers seront discutés en cours de cette semaine. SVP, soyez attentifs, votre exercice obligatoire suivant portera sur la gestion des fichiers ! Certains ont travaillé sur cet exercice le mercredi dernier, bien, au moins ils savent comment ouvrir un fichier en lecture.


Un peu de travail sur les fichiers.

Exercice 1.

L'exercice se divise en plusieurs étapes. Vous allez appliquer l'algorithme aux listes de compositeurs et d'oeuvres.

Attention ! Les dictionnaires contiennent des chaînes, mais aussi des entiers. Toute donnée numérique doit être convertie en chaîne ! (L'affichage fait la conversion automatiquement, mais il faut savoir le faire explicitement ; la conversion inverse également !) Il faut aussi surveiller les chaînes, elles ne doivent pas contenir des virgules (ici : pas de problèmes, mais que faire si cela arrive?...).

La procédure la plus compacte (et en fin de comptes la plus rapide) assemblera les données dans des listes ou tuples, et exploitera la procédure système writelines().


Exercice 2. La reconstruction

Écrivez un programme qui lit ce fichier et en reconstruit la liste de dictionnaires d'origine. Pour séparer une chaîne récupérée par la lecture, et contenant des virgules, utilisez (par exemple) la méthode split.
Mais réfléchissez : quelles peuvent être d'autres méthodes de séparation des mots entre les virgules?

Aussi : Comment séparer les mots ou phrases, si on sait qu'ils occupent un champ de largeur fixe, par ex. 15 colonnes? Par ex.:

0123456789012345678901234567890123456789...
COMPOSITEUR    ANNEE NAISS.   ANNEE MORT

Et si on sait que le texte est en colonnes, mais on ne connaît pas leur largeur, seulement une ligne modèle, similaire à la ligne ci-dessus, montre la structure de toutes lignes qui suivent?


Arbres (et récursivité...)

Exercice 3.

Arborescences et tuples/listes hiérarchiques. Des graphes particuliers, sans cycles, sans "convergence des arêtes" vers un noeud commun, sont des arbres, comme sur le dessin. On n'a pas besoin de dictionnaires pour naviguer à travers de telles structures.

On peut les construire comme une collection de listes ou de tuples (de taille 3 pour les arbres binaires) imbriquées. Si un noeud possède l'étiquette "A", et deux branches, gauche G et droite D, qui sont les arbres, il pourra avoir la représentation ["A",G,D]. Une feuille est un arbre avec un seul noeud, dont les branches sont vides, [] ou None, etc. Certains préfèrent les listes pour ces constructions, les autres – les tuples ; les détails de l'algorithmique seront différents, car les tuples ne sont pas modifiables, et il faudra à chaque pas construire un nouveau, tandis qu'avec les listes, on peut changer une branche sans toucher le reste, mais les idées sont similaires. [Et en L2 vous verrez la construction des arbres avec les objets Python].

L'usage des arbres (pas forcément binaires ; un noeud peut avoir plusieurs branches) est multiple.

La plupart des structures hiérarchiques est par définition arborescente.

Cela correspond à la composition d'un objet à plusieurs couches, ou à un exemple de classification (par exemple du monde biologique : animaux et végetaux, où les animaux se sub-divisent en mollusques, vertebrés etc. ..., où les vertebrés se divisent en canidés, primates et les dirigeants des partis extrêmistes, etc.) Les arbres sont aussi utiles pour l'algorithmique en général ; ils modélisent la récursivité, constituent la base des algorithmes du tri, etc. Un arbre peut représenter un jeu, avec les noeuds qui sont les états, et les branches – les coups qui mènent d'un état à un autre.

Le noeud principal (le plus haut) sera appelé la racine.

Commentaire final. La construction ci-dessus, (les petits à gauche, grands à droite) est loin d'être unique ! Cet exemple sert à montrer l'algorithme du tri. On peut construire des arbres variés, de plusieurs autres façons, et parcourir et modifier ces arbres également de manières diverses. Ne confondez donc pas notre exercice avec la généralité du problème.


Matplotlib et images

Exercice 4. Matplotlib et la rotation d'images

Continuation de l'exercices sur les images (et plus tard, peut-être, vous en aurez encore). Rotation des images. Un minimum d'information sur la géométrie vectorielle 2D s'impose. Dans l'Antiquité, quand les gestionnaires de l'Éducation Nationale étaient encore conscients que la France a donné à l'Humanité : Descartes, Monge (et Poncelet et Chasles), Legendre, Laguerre, Hermite, Rodrigues, Poincaré, Cartan (père et fils), et j'en passe..., la géométrie était enseignée au Lycée, et tous à l'université connaissaient cette formule :

$$x' = x\cdot \cos(\alpha) - y\cdot \sin(\alpha)\,; \quad y' = x\cdot \sin(\alpha) + y\cdot \cos(\alpha)\,.$$

Mais c'est fini... Cependant, c'est la base de l'Imagerie, donc son importance pour l'algorithmique visuelle est essentielle.

Vous devez apprendre cette formule de manière persistante, elle sert partout. Ceci peut être presque directement utilisé pour la rotation des images pixel par pixel ; les coordonnées sont les indices du tableau. Mais alors un certain nombre de précautions s'impose, sur le plan géométrique et algorithmique.

  1. Les indices vont de zéro jusqu'à la valeur limite (hauteur, largeur), et le zéro du répère c'est le coin supérieur gauche, dans le système Cartésien gauche (l'axe des \(y\) vers le bas), tandis que nous préférerions tourner l'image autour de son centre, et la formule mathématique ci-dessus est adaptée au système Cartésien traditionnel (\(y\) vers le haut).
  2. Les coordonnées transformées \((x',y')\) ne seront plus entières ! Il faut savoir ce qui signifie l'indice fractionnel, comment l'interpréter. On peut par ex. prendre la valeur entière la plus proche, ou utiliser l'interpolation entre les valeurs entières proches. Il faut aussi décider ce que l'on fait avec les coordonnées qui dépassent les bornes du tableau.

  3. Vérifier (vraiment, faites-le !) que la formule inverse à la précédente sera $$x = x'\cdot \cos(\alpha) + y'\cdot \sin(\alpha)\,; \quad y = -x'\cdot \sin(\alpha) + y'\cdot \cos(\alpha)\,,$$ il suffit de transposer la matrice de transformation.

La stratégie de la transformation du tableau A commence par l'allocation d'un nouveau tableau W (pour simplicité : de même taille. Les fragments qui dépassent son cadre seront tronqués). Sur le plan algorithmique, nous avons alors deux stratégies au choix :

  1. Parcourir, pixel par pixel, le tableau A : indices (i,j). Construire (i',j'), et par exemple, les arrondir. Ensuite remplir l'élément (i',j') du tableau W avec la couleur de ce pixel.
  2. La stratégie "inverse", qui sera utilisée, car elle est meilleure (les détails si vous le demandez). On parcourt les indices du tableau W : (i',j'), et on en reconstruit par la rotation inverse, les indices de la source (i,j), encore une fois, avec l'arrondi. La transformation inverse est banale, il suffit de passer de α à -α, comme montré dans le point (3) ci-dessus.

L'exercice. Suivre les consignes ci-dessous, et construire l'image tournée, à droite.


Pour l'image plus grande, la vitesse de l'algorithme n'est pas exceptionnelle, plusieurs secondes, à cause des boucles et d'indexation/calcul pixel par pixel. Cependant, en utilisant les dispositifs "matriciels" de numpy – l'usage des tableaux comme arguments mathématiques (sans boucles), on peut accélerer le processus par un très grand facteur, le résultat est presque instantané même si les dimensions dépassent 1000 × 1000. Ceci est une technique numpy avancée, il serait difficile de l'aborder maintenant. [Mais si quelqu'un me le demande, je vous la donnerai ; l'usage du PIL (suggéré dans d'autres cours) pour des exercices de ce genre n'a aucune raison.]


Votre rencontre avec les automates cellulaires.

Exercice 5.

On travaillera un peu avec des automates uni-dimensionnels, et avec leur représentation textuelle. La description est un peu simplifiée.

Un automate cellulaire est une collection (en 1 dimension ceci peut être une liste, un tuple, une chaîne, etc.) de "cellules". Chaque cellule est un objet Python (peut-être si simple qu'un nombre, parfois plus compliqué), qui possède un "état" : une valeur parmi plusieurs, au moins deux, par exemple "cellule vivante" ou "cellule morte". En visualisant les cellules on peut utiliser une couleur, ou un symbole/caractère particulier, etc.
Par exemple, une séquence de cellules bi-état, peut être représenté comme " oo o oo ooo oo o", une chaîne, où le caractère "o" représente une cellule "vivante", et l'espace : morte. (Avec plus d'états on peut utiliser plusieurs caractères).

Chaque cellule possède un mécanisme d'évolution (pour des automates simples, comme ici, le même pour toute cellule). Le temps est discret, l'état de la cellule passe au moment suivant, à un autre état [peut-être identique], en fonction de son état actuel, disons S, et les états des cellules voisines, disons : V1, V2, ... Vn, selon le nombre des voisins. Le nombre de voisins dépend de la dimension de l'ensemble de cellules, mais même en une dimension chaque cellule peut avoir plus de deux voisins, si les voisins plus éloignés influencent également la cellule en question.

Voici votre exercice. L'automate est binaire, uni-dimensionnel, seulement les voisins les plus proches comptent. Supposons que la règle d'évolution de la cellule centrale (rouge) en fonction de l'environnement des 3 cellules est donnée par des transformations genre : 'xyz' => 'w'. Prenons une réalisation concrète :

'   '     =>   ' '
'  o'     =>   'o'
' o '     =>   'o'
' oo'     =>   'o'
'o  '     =>   'o'
'o o'     =>   ' '
'oo '     =>   ' '
'ooo'     =>   ' '
et prenons comme l'état initial une seule cellule au milieu de plusieurs cellules mortes. Écrire la procédure d'évolution, et prouver que la séquence évoluera comme ci-dessous, de haut vers le bas.

                 o 
                ooo
               oo  o 
              oo oooo 
             oo  o   o 
            oo oooo ooo 
           oo  o    o  o 
          oo oooo  oooooo 
         oo  o   ooo     o 
        oo oooo oo  o   ooo 
       oo  o    o oooo oo  o 
      oo oooo  oo o    o oooo 
     oo  o   ooo  oo  oo o   o 
    oo oooo oo  ooo ooo  oo ooo 
  ........

Écrivez la procédure d'évolution de manière universelle, parametrée par les règles, de manière à ce qu'après le changement des règles, la procédure reste utilisable.

Cet exercice constitue une de bases (l'autre c'est Matplotlib, avec des dispositifs d'interfaçage, et l'usage des tableaux [arrays]) de votre devoir maison, et par la suite de votre dernier exercice noté en TP. Donc, commencez à travailler dessus tout de suite.

Semaine dernière
Semaine suivante
Retour à l'index