Mise à niveau : TD / TP 1

En général, je vous donne les énoncés de vos exercices et l'information de support, et je vous laisse travailler seuls. Il vous faudre relire le cours et accéder à la documentation de Python. Si vous vous sentez bloqué plus de 3 - 4 minutes, vous m'appelez, je vous dépanne. Je réponds à toute question, sauf celles qui n'ont pas été posées. Cette remise à niveau est pour vous, non pas pour moi, et la seule évaluation de votre progrès est dans vos esprits. Vous pouvez choisir vos exercices à volonté, pas forcément dans l'ordre ; lisez d'abord tous les énoncés.

Les exercices ci-dessous sont assez "mathématiques", non pas pour suggérer que Python sert surtout aux matheux, mais car la discipline formelle inhérente dans cette sorte de problèmes, facilite le codage : on sait bien de quoi on parle. Si cela ne vous convient pas, vous aurez des ennuis avec l'algorithmique, avec l'Intelligence Artificielle, avec l'Imagerie, avec la crypto, etc.

Introduction, la prise en main de Python.

Ouvrez un terminal sur votre machine, et lancez Python. Ouvrez aussi une interface integrée de Python : spyder et/ou idle, faites quelques expériences interactives. Attention. Si vous n'êtes pas inscrits, et vous ne pourrez pas accéder aux ressources du dept., la régularisation de votre situation peut prendre trop de temps. Dans ce cas, travaillez en binômes.

Créez un répertoire de travail dans vos ressources.

Si vous trouvez des problèmes quelonques, alarmez. Dans une semaine je vous aiderai moins...

Introduction, Python "standard", sans classes

Construction et analyse des graphes.

Exercice 1. Ceci est un sujet relativement compliqué, qui peut être traité en plusieurs étapes, mais nous traiterons seulement quelques éléments très simples. Le sujet est fondamental, car les graphes, c'est une abstraction qui représente toute sorte de relations entre les choses, les humains, entre les éléments et une structure composite qui les contient, etc. Une bonne partie d'algorithmique est consacrée aux graphes. Pas de Licence sans connaissance des graphes.

ograph (9K)

Un graphe orienté est une paire {S,A}, où S est un ensemble de sommets, ici tout simplement des étiquettes {A,B,C,D,E}, combiné avec A, un ensemble d'arêtes (ou arcs) qui connectent les sommets, ici {(A,C), (C,B), (D,A), (E,D), (A,B)}. Les deux ensembles sont nécessaires, car un ou plusieurs sommets peuvent rester déconnectés, et ils ne figureront dans la seconde liste. Nous pouvons donc représenter un graphe comme un tuple (S,A), où S, A sont également des tuples ou des listes, ou des ensembles (sets). Vous avez la liberté d'exploiter les structures de données que vous voulez.

  1. Concevoir et coder une autre représentation d'un tel graphe. Considérons que les noms des sommets sont des caractères : 'A', etc. Ecrire une procédure qui prend les deux listes, la première des caractères, et la seconde des tuples, et qui construit un dictionnaire, dont les clés sont des sommets "de départ" (des flèches), et les valeurs : les listes des sommets-cibles.

    Ici on aura {'A': ['B','C'], 'B': [], 'C': ['B'], 'D': ['A'], 'E': ['D']}

  2. Ecrire une fonction qui vérifie si deux sommets a et b sont connectés dans n'importe quel ordre.
  3. Ecrire une fonction qui à partir d'un sommet a construit la liste de tous les sommets accessibles transitivement de a. C'est-à-dire : les cibles de a, les cibles de toutes les cibles, etc. Faites attention, le graphe peut contenir des boucles, contenir par ex. des arcs : ('A','B'), ('B','C'), ('C','A') ..., et un programme mal construit peut boucler et se bloquer.

Ces fonctions doivent être construites depuis les deux représentations présentées : le tuple (S,A), et le dictionnaire.

... et encore un Exercice, un peu pénible (laissez-le, si vous avez d'autres choses à faire) : Etant donné une liste des sommets, écrire une fonction qui construit une clique : un graphe qui contient tous les arcs imaginables dans tous les sens ; chaque sommet étant connecté avec tous les autres.


Définition des classes et des méthodes (1)

On n'a pas pu discuter en cours les définitions des classes, il m'a fallu abréger la séance. Voici une définition de classe représentant des paires de composants, qui doivent simuler les nombres complexes. :
class Cmplx(object):
    def __init__(self,x,y):
        self.re=x
        self.im=y
    def __repr__(self):   # pour l'affichage.
        return "C("+str(self.re)+"," + str(self.im)+")"
    def __add__(self,autre):
        rr=self.re+autre.re
        ii=self.im+autre.im
        return Cmplx(rr,ii)
Je discuterai oralement le sens de cette construction.

La solution présentée n'est pas "professionnelle". On peut exécuter : Cmplx(4,6)+Cmplx(3,-1) et obtenir C(7,5). Mais Cmplx(4,8)+ 10 ne marchera pas. Il faut vérifier explicitement si le second argument x a le type Cmplx, sinon, on le considère comme nombre x, et on le convertit en complexe par Cmplx(x,0). Mais cela ne sera pas bon pour 10 + Cmplx(4,9), car le nombre 10 ne connaît pas nos définitions. Pour cela on a une autre méthode : __radd__ (right-add), lancée, si __add__ trouve que le premier argument est primitif, et le second PEUT être quelconque. Alors Python inverse l'ordre des arguments, et relance l'action : 10 + x x.__radd__(10).

Exercice 2. Coder de manière la plus complète la création de la classe Cmplx représentant les nombres complexes. Définissez la panoplie complète d'opérateurs, les 4 opérations +, - *, /, avec les méthodes "droites", __radd__, etc., avec __repr__, avec la norme, etc.

Définissez aussi la méthode qui calcule la phase d'un complexe, c'est l'arc-tangente du quotient de la partie imaginaire par la partie réelle. Attention, il faut utiliser la fonction atan2, non pas atan, et ne rien diviser, afin d'éviter des ambiguïtés et des singularités (si RE=0). Lisez quelque chose sur atan2, et sur la phase, l'argument angulaire des nombres complexes.

Comparez votre solution avec l'arithmétique sur les complexes prédéfinis en Python.


Exercice 3. Cet exercice est conceptuellement très similaire au précédent ; si après les complexes vous n'avez plus de doutes, passez à un autre, sinon, faites-le. Mais lisez l'énoncé de toute manière.

Arithmétique des fractions.

Nous allons travailler sur l'arithmétique des fractions rationnelles, n/d, avec n et d : entiers. Que ce soit une classe, instanciée comme R(n,d).

  1. Les fractions doivent être simplifiées, normalisées : le dénominateur doit être positif, le numérateur et le dénominateur ne doivent pas avoir des facteurs communs. Parfois on peut insérer dans le code une fraction "illégale", par ex. R(6,-9). Concevoir et coder une méthode de simplification des fractions : n et d doivent être toujours premiers entre eux, et d doit être strictement positif. Écrire d'abord la fonction pgcd(n1,n2) qui calcule le plus grand diviseur commun entre n1 et n2. L'algorithme classique d'Euclide est : si l'un de nombres est zéro, par convention le résultat est l'autre. Sinon, on lance la récurrence, le pgcd avec le plus petit de deux, et le reste de la division de l'un par l'autre. Ce reste, l'opération modulo, est : %. La méthode __init__ doit normaliser le résultat.
  2. Ecrire une méthode __repr__ qui construit une représentation "externe", habituelle, des fractions, par ex. la fraction R(2,3) doit être affichée comme le texte "2/3". Ne lancez pas la procédure print à l'intérieur de la méthode, mais construisez la chaîne-résultat, et retournez-la.
  3. Construisez une fonction qui ajoute deux fractions : 2/3 + 1/4 = 11/12add(R(2,3),R(1,4)) donne R(11,12).
  4. Construisez également les fonction de soustraction et de multiplication, mais seulement si vous avez encore beaucoup de temps libre, sinon passez aux autres choses.
  5. Après avoir fait des fonctions, convertissez-les en méthodes qui surchargent les opérateurs.


Exercice 4.

"Pseudo-dictionnaires" et chiffrage (code de César)

[Ce ne sera pas fait aujourd'hui]
La surcharge de la méthode __getitem__ dans la classe de l'objet p, permet d'étendre le programme par des constructions genre p[k], dont le comportement peut être non-standard. Cet objet n'a rien à voir avec les listes, la seule chose qui compte est la méthode
    def __getitem__(self,indx):
        ...
        return ...     l'expr. self[indx]

Définissez une classe qui simule un dictionnaire, de manière très spéciale. La classe hérite de object, et ne contient aucun vrai dictionnaire. L'instance de cette classe accepte seulement des textes comme clés (indices), tout autre argument entre crochets doit être refusé. (Tester type : str).

Le texte est transformé, et __getitem__ retourne le résultat de la transformation. La transformation consiste à remplacer chaque lettre du texte par la lettre décalé de 4 ; (ou une autre valeur définie comme variable de classe) caractères, alphabétiquement. Par ex. "f""j" (Concrètemet, si l'instance de cette classe est dd, alors dd['afd'] = 'ejh').

Il faut utiliser les fonctions ord et chr, qui convertissent les caractères en entiers, et vice-versa. Si le résultat numérique dépasse 255, on cycle à partir de zéro.




Retour