Python L1, TD/TP 01.04

N'oubliez pas que vous avez aujourd'hui une interrogation sur papier. Revisez BIEN les dictionnaires ; travaillez sur les graphes sous forme de dictionnaires (les exercices des dernières semaines, et l'ex. 1 ci-dessous).


Récursivité...

Exercice 1.

Il est vraiment temps de terminer les exercices des semaines précédentes ! Chemins dans les graphes et voisinage (fermeture transitive : l'ensemble d'objets joignables.

{'A': ['H', 'C'],
 'B': ['A'],
 'C': ['G', 'E'],
 'D': ['B'],
 'E': [],
 'F': ['B'],
 'G': [],
 'H': []}
Un graphe est une structure topologique (des choses dans l'espace, qui ont des relations entre elles), composée de noeuds, et des arêtes (ou arcs), qui connectent les noeuds dans un certain ordre. Les noeuds peuvent (d'habitude : doivent) être identifiables, par ex. par des étiquettes : textuelles ou numériques. Les arcs aussi, mais nous pouvons considérer qu'un arc est identifié par la paire de noeuds qu'il connecte.

La représentation du graphe-exemple à l'aide des dictionnaires est montrée ci-dessus, la représentation d'origine était la liste d'arêtes (avec la liste de noeuds pour complétude).

Construire une procédure qui à partir d'un noeud trouve TOUS les noeuds joignables par une séquence d'arcs. Mettre le noeud ititial dans le tampon, et ensuite utiliser la récursivité : appeler elle-même pour tous les noeuds - voisins immédiats. Si le noeud se trouve déjà dans le tampon, alors ne faire rien, passer aux autres.

Pour chaque descendant direct du noud de départ, quand on applique la récursivité, on met à jour le tampon. La solution est un programme de moins de 10 lignes.

Utiliser une stratégie similaire (mais un peu plus compliquée) et construire une procédure qui vérifie si entre deux nouds (ordonnés : départ et cible) il existe un chemin (séquence d'arcs).

La stratégie la plus banale, mais - en principe - plus coûteuse que nécessaire, est de lancer la procédéure précédente, et vérifier si le noeud-cible s'y trouve. Ceci nous dira si le chemin existe, mais ne le donne pas.

En général, ce problème a plusieurs variantes, et vous serez obligés de les apprendre un jour, par ex.: trouver TOUS les chemins entre deux noeuds. Ou, si les arêtes sont pondérées (chacun se voit affecté sa "longueur"), trouver le chemin le plus court [ou moins onéreux]. Ou, trouver un chemin qui passe par tous/maximum_de noeuds, etc. Ceci dépasse le cadre de ce cours.

La procédure de "foncer" récursivement depuis chaque voisin immédiat vers les plus lointains, retourner et recomencer en suivant un autre arc [branche en cas d'arbre] s'appelle le parcours en profondeur, très important pour l'algorithmique, mais parfois pas trop efficace. Pour l'intelligence artificielle, jeux stratégiques, etc., on utilise plus fréquemment le parcours en largeur : d'abord on traite tous les voisins immédiats, et seulement après on passe à ceux plus loin. Vous le verrez encore plusieurs fois.


Exercice 2.

Écrire une procédure perm(l) qui prend une liste, et en construit une liste de listes : la liste de toutes les permutations de l'original. Par ex., pour l=[1,2,3,4], on obtiendra :
[[1, 2, 3, 4], [2, 1, 3, 4], [2, 3, 1, 4], [2, 3, 4, 1], [1, 3, 2, 4], [3, 1, 2, 4], [3, 2, 1, 4], [3, 2, 4, 1], [1, 3, 4, 2], [3, 1, 4, 2], [3, 4, 1, 2], [3, 4, 2, 1], [1, 2, 4, 3], [2, 1, 4, 3], [2, 4, 1, 3], [2, 4, 3, 1], [1, 4, 2, 3], [4, 1, 2, 3], [4, 2, 1, 3], [4, 2, 3, 1], [1, 4, 3, 2], [4, 1, 3, 2], [4, 3, 1, 2], [4, 3, 2, 1]] .
(pas forcément dans cet ordre).

Stratégie. Construire d'abord une fonction auxiliaire, disons insrt(x,lst) qui insère "de manière non-déterministe" un objet quelconque x dans une liste, dans tous les endroits possibles, par ex. insrt('x',[1,2,3]) doit retourner [['x', 1, 2, 3], [1, 'x', 2, 3], [1, 2, 'x', 3], [1, 2, 3, 'x']].

Alors la solution de l'exercice combine l'usage de cette fonction avec la récursivité.


Répondre à la question : quelle est la longueur de la liste de permutations de N éléments?


Exercice 3.

Une figure fractale récursive.

Cet exercice peut être résolu par un système de Lindenmayer un peu généralisé, ou simplement par une procédure récursive opérant avec turtle, ou, de manière plus basique, avec Matplotlib. Vous aurez besoin d'un peu de calcul géométrique dans tous les cas : comment tourner un segment, comment trouver un point si on connaît un autre point, la longueur du segment et l'angle, etc.

La solution la plus facile pour vous est (probablement) avec turtle ; la figure à droite a été crée quand même avec Matplotlib pour que la dimension de la fenêtre soit spécifiée automatiquement en fonction de l'objet tracé. Sa profondeur récursive est 11.

Question de base. Étant donné un segment de ligne orienté, donc deux points : p0 et p1, construire deux autres points : p2 et p3, comme sur le dessin.

Dans cet exemple le segment secondaire à gauche est retréci par un facteur de 0.75, et tourné à gauche de 30 degrés. Le segment droit a la longueur de 0.66 fois l'original (p1 - p0), tourné à droite de 50 degrés.

Ceci doit être paramétrable. On peut obtenir ainsi des figures présentant des formes assez différentes.

La procédure récursive qui trace l'arbre : treerec(p0,p1,n) prend deux points qui déterminent le premier segment, et la profondeur. On trace le segment entre p0 et p1 en toute indépendance de n. Si n==0, on ne fait plus rien.

Pour n supérieur à zéro, on calcule la position des points p2 et p3, et on trace les arbres récursivement, avec la profondeur n-1 : entre p1 et p2, et entre p1 et p3. L'extension assez triviale, mais intéressante du programme serait de tracer les lignes avec la largeur variable...


Expressions algébriques

Des expressions algébriques (classiques, simples), par exemple x*(1-y)/(x-sin(1+3*x)+y) structurellement sont des arborescences, dont les noeuds-feuilles sont des données élémentaires, et les noeuds intermédiaires – les opérateurs ; les branches de ceux noeuds sont, naturellement, les opérandes. L'exemple ci-dessus aura la forme arborescente, présentée à gauche. (Confrontez la structure avec l'algèbre. Peut-être je me suis trompé...

N'oubliez JAMAIS quelles sont les précédences des opérateurs algébriques, et quelle est leur associativité : gauche pour les 4 opérations, droite pour la puissance.)

Cet exercice est très important pas seulement comme un entraînement en Python / récursivité,mais il est vital pour la compilation des langages de programmation.


Exercice 4.

Étant donnée la forme symbolique de l'expression, comme ci-dessus, avec les 5 opérateurs arithmétiques, et quelques fonctions élémentaires, construire et imprimer l'arbre structurel. Les feuilles sont soit des nombres, soit des chaînes, qui représentent les noms des variables, "x", "y", etc. Les noms des fonctions comme "sin" sont également des chaînes, mais puisque ces objets ne sont pas des feuilles, on peut les distinguer des variables. Ceci s'applique aux opérateurs.

Les noeuds intermédiaires sont des tuples : x+1 ('+', 'x', 1), sin(2/y) ('sin', ('/', 2, 'y')), etc. Les formes fonctionnelles sont des tuples d'arité 2, les formes opérationnelles binaires – des triplets.

Pour l'instant, pas besoin d'avoir des opérations d'arité différente.


Exercice 5.

Vous disposez d'un dictionnaire qui affecte des valeurs aux noms des "variables", par ex. {'x' : 3.2, 'y' : 0} , etc. Ce dictionnaire, ou un autre, contient également les définitions des opérateurs, par ex. {'sin' : sin, '*' : f}, où def f(x,y): return x*y, etc. Ici sin est l'objet - fonction appartenant au module math. (D'ailleurs, les opérateurs existent aussi comme des fonctions nommées, dans le module standard operator, allez le voir).

L'exercice consiste à évaluer une expression de ce genre. Le programme évalue la valeur d'une constante directement, d'une variable, grâce au dictionnaire, sinon, récursivement, en appliquant l'opération aux branches. Si x=1 et y=2, l'expression-exemple a la valeur -0.2661838. TESTER.


Exercice 6.

Vous devez connaître les règles de différentiation des expressions élémentaires. Écrivez une fonction, qui prend en paramètre une expression arborescente décrite ici, ainsi que le nom de la VARIABLE, spécifique, par ex. 'x', et qui calcule la dérivée de cette expression par rapport à la variable. Le résultat aura la forme non-simplifiée, inefficace, mais ceci restera pour un autre exercice.

Vous devez exploiter les propriétés habituelles de l'enchaînement (récursif) du calcul des dérivées. Pour x comme variable :

x' = 1
y' = 0
(a+b)' = a' + b'
(a*b)' = a'*b + a*b'
(a/b)' = (a'*b - a*b')/(b*b) = a'/b - a*b'/(b**2)
sin(a)' = cos(a)*a'
log(a)' = a'/a
... et les autres que vous allez reconstruire de vos mémoires et/ou des références mathématiques.

La dérivée de x*(1-y)/(x-sin(1+3*x)+y) sur x est donc

(1-y)/(x-sin(1+3*x)+y) - x*(1-y)*(1-cos(1+3*x)*3)/(x-sin(1+3*x)+y)**2
sauf que un humain fera un minimum de simplification dans sa tête, tandis que l'algorthme superficiel produira des formules considérablement plus longues, par exemple
(x+1)' = 1 + 0
((2+y)*x)' = (2+y)'*x + (2+y)*x' = (0+0)*x + (2+y)*1
Vous pourrez ajouter à la solution un simplificateur minimaliste, qui effectue récursivement la simplification de l'arbre : A σ(A) selon les règles :
σ(0+A) = σ(A)
σ(0*A) = 0 
σ(A/B) = σ(A)/σ(B) = 1 si σ(A)==σ(B)
etc. Les simplifications possibles, faciles et difficiles, sont très nombreuses.


Semaine dernière
Semaine suivante
Retour à l'index