#!/usr/bin/env python
# coding: utf-8
#
Table of Contents
#
# # TP 1 - Programmation pour la préparation à l'agrégation maths option info
#
# ## Remarques sur le style
# Ici, pour vous montrer, j'ai utilisé :
# - En Python 3, avec des annotations de types.
# - Notez que ce ne sont que des annotations.
# - Pour plus, il faudrait utiliser [quelque chose comme `beartype`](https://stackoverflow.com/a/37961120/2809027).
#
# Notez que ce n'est absolument *pas nécessaire*, c'était juste pour montrer que ce genre d'annotations peut aider à passer de Caml à Python.
# # Fonctions
# ## Exercice 4
# In[65]:
def successeur(i : int) -> int:
assert isinstance(i, int), "Erreur : i = {} doit etre entier.".format(i)
assert i >= 0, "Erreur : i = {} doit etre >= 0.".format(i)
return i + 1
# In[66]:
successeur(3)
successeur(2 * 2)
successeur(2.5)
# ## Exercice 5
# In[4]:
def produit3(x, y, z):
return x * y * z
produit3_2 = lambda x, y, z: x * y * z
produit3_3 = lambda x: lambda y: lambda z: x * y * z
# In[5]:
produit3(1, 2, 3)
produit3_2(1, 2, 3)
produit3_3(1)(2) # lambda z : 1 * 2 * z
f = produit3_3(1)(2) # lambda z : 1 * 2 * z
f(3)
produit3_3(1)(2)(3)
# ## Exercice 6
# In[6]:
def exercice6(n : int) -> None:
for i in range(1, n + 1):
print(i)
for i in range(n, 0, -1):
print(i)
# In[7]:
exercice6(4)
# # Récursivité
#
# C'est simple. Pas besoin d'un mot clé `rec` quand on définit une fonction récursive en Python.
# ## Exercice 7
# In[8]:
def factorielle(n : int) -> int:
if n <= 0:
return 0
elif n == 1:
return 1
else:
return n * factorielle(n - 1)
# In[10]:
for i in range(8):
print("{}! = {:>5}".format(i, factorielle(i)))
# Note : ce {:>5} signifie que l'affichage utilise au moins
# 5 caractères, pour avoir un joli alignement :
# ## Exercice 8
#
# Pour ce genre de fonction, j'aime bien afficher les appels récursifs. On peut rendre ça optionnel, avec comme ici un argument nommé `log`, à valeur par défaut `log=False`.
# In[73]:
def pgcd(x : int, y : int, log: bool=False) -> int:
if log: print("x = {:>7}, y = {:>7}".format(x, y))
assert x >= 0 and y >= 0
if y == 1:
return 1
elif y == x or y == 0:
return x
if x < y:
return pgcd(x, y % x, log=log)
else:
return pgcd(y, x % y, log=log)
# In[74]:
pgcd(2021, 4, log=True)
# In[75]:
pgcd(10, 5)
# On peut faire des essais pour afficher notre calcul de PGCD, sur des entiers aléatoires entre $1$ et $100$.
#
# Pour se rassurer, on peut chercher dans la bibliothèque standard, à partir de Python 3.6 il y a la fonction `math.gcd` pour calculer le PGCD, sinon `fractions.gcd` ou encore dans le module (non standard) SymPy `sympy.gcd`.
# In[15]:
try:
from math import gcd
except ImportError:
try:
from fractions import gcd
except ImportError:
from sympy import gcd
from random import randint
for _ in range(10):
x = randint(1, 100)
y = randint(1, 100)
d = pgcd(x, y)
print("{:>3} ^ {:>3} = {:>3}".format(x, y, d))
assert d == gcd(x, y), "Erreur : mauvais calcul de pgcd(x={}, y={}) = {}, alors qu'il devrait etre = {}.".format(x, y, pgcd(x, y), gcd(x, y))
# ## Exercice 9
#
# Rien de particulier à faire, la récursivité fonctionne sans réfléchir :
# In[3]:
def fibonacci(n : int) -> int:
assert n >= 0
if n == 0 or n == 1:
return 1
else:
return fibonacci(n - 1) + fibonacci(n - 2)
# Dans IPython (ou Jupyter) on peut facilement mesurer le temps (moyen) d'exécution d'une fonction sur une entrée donnée, avec la *macro* `%timeit`.
# In[18]:
get_ipython().run_line_magic('timeit', 'fibonacci(35)')
# Dans Python, on peut faire pareil avec `timeit()` du module `timeit`.
#
# - avantage : on peut plus facilement récupérer le temps de calcul, et ensuite en faire des graphiques par exemple (e.g., afficher $T(f(n))$ en fonction de $n$ pour $n=10,100,...$),
# - inconvénients :
# + il faut bien penser de passer l'argument optionnel `globals=globals()` (`globals()` donne un dictionnaire qui stocke la valeur de toutes les variables définies, donc ici notamment de `fibonacci()`)
# + il faut penser à changer l'argument `number` qui par défaut vaut `1000000` : c'est très grand, et donc valable seulement pour estimer le temps de calculs très rapides, par exemple :
# In[9]:
get_ipython().run_line_magic('timeit', '2**35')
from timeit import timeit
timeit("2**35") / 1000000
# In[5]:
from timeit import timeit
number = 5
temps_calcul_fibo35 = timeit("fibonacci(35)", globals=globals(), number=number) / number
print("Pour calculer fibonacci(35), la fonction récursive naïve a pris {} secondes (moyenne sur {} essais)".format(temps_calcul_fibo35, number))
# ##### Fibonacci linéaire impérative
# Pour la version qui est en complexité (temporelle) linéaire dans l'entrée $n$, il suffit de déplier la récursion en calculant $F_{n+1}$ progressivement en partant de $F_0, F_1$.
# In[16]:
def fibonacci_lin(n : int) -> int:
fim1, fi = 1, 1
for _ in range(n):
fim1, fi = fi, fim1 + fi
return fim1
# On peut vérifier que cette deuxième implémentation fonctionne comme la première, et ensuite vérifier qu'elle est (bien) plus rapide.
# In[17]:
for i in range(10):
assert fibonacci(i) == fibonacci_lin(i)
# In[18]:
get_ipython().run_line_magic('timeit', 'fibonacci_lin(35)')
# ##### Fibonacci linéaire récursive
# Pour la version qui est en complexité (temporelle) linéaire dans l'entrée $n$, il suffit de déplier la récursion en calculant $F_{n+1}$ progressivement en partant de $F_0, F_1$.
# In[12]:
def fibonacci_lin_rec(n: int) -> int:
# invariant :
# m >= 1
# u = fibo(n-m+1)
# v = fibo(n-m)
# aux m u v = fibo(n)
def aux(m: int, u: int, v: int) -> int:
assert m >= 0
if m <= 1:
return u
else:
return aux(m-1, u+v, u)
return aux(n, 1, 1)
# On peut vérifier que cette troisième implémentation fonctionne comme la première, et ensuite vérifier qu'elle est (bien) plus rapide.
# In[13]:
for i in range(10):
assert fibonacci(i) == fibonacci_lin_rec(i)
# In[15]:
get_ipython().run_line_magic('timeit', 'fibonacci_lin_rec(35)')
# Voilà les différences :
#
# - Les deux implémentations linéaires sont bien plus rapides que l'implémentation naïve (exponentielle), comme prévu !
# - L'implémentation linéaire impérative est plus rapide que l'implémentation linéaire fonctionnelle récursive, car elle n'a pas besoin de faire des appels de fonctions et de dépiler ensuite les appels de fonctions.
# ##### Un petit graphique : juste pour montrer ce que l'on peut faire rapidement
# In[19]:
import numpy as np
import matplotlib.pyplot as plt
# In[30]:
# optionnel : vous ne l'aurez pas le jour de l'oral, mais c'est joli
from tqdm.notebook import tqdm
# In[31]:
valeurs_n = np.array(range(1, 32))
number = 5
# In[32]:
get_ipython().run_cell_magic('time', '', 'temps_calcul_fibo_rec = [\n timeit("fibonacci({})".format(n), globals=globals(), number=number) / number\n for n in tqdm(valeurs_n)\n # enrober un itérateur de la fonction tqdm(...)\n # permet d\'avoir une joli barre de progression\n]')
# In[33]:
number = 100
temps_calcul_fibo_lin = [
timeit("fibonacci_lin({})".format(n), globals=globals(), number=number) / number
for n in tqdm(valeurs_n)
]
temps_calcul_fibo_lin_rec = [
timeit("fibonacci_lin_rec({})".format(n), globals=globals(), number=number) / number
for n in tqdm(valeurs_n)
]
# In[36]:
plt.figure(figsize=(14, 10))
plt.plot(valeurs_n, temps_calcul_fibo_rec, "ro-", label="Récursive naïve")
plt.plot(valeurs_n, temps_calcul_fibo_lin, "bd:", label="Linéaire impérative")
plt.plot(valeurs_n, temps_calcul_fibo_lin_rec, "ys:", label="Linéaire récursive")
plt.legend()
plt.title("Comparaison de trois implémentations de la fonction de Fibonacci")
plt.xlabel("Valeurs de n")
plt.ylabel("Temps moyen de calcul en secondes")
plt.show()
# In[39]:
get_ipython().run_cell_magic('time', '', 'valeurs_n = np.array(range(10, 1000, 10))\nnumber = 1000\ntemps_calcul_fibo_lin = [\n timeit("fibonacci_lin({})".format(n), globals=globals(), number=number) / number\n for n in tqdm(valeurs_n)\n]\ntemps_calcul_fibo_lin_rec = [\n timeit("fibonacci_lin_rec({})".format(n), globals=globals(), number=number) / number\n for n in tqdm(valeurs_n)\n]')
# In[40]:
plt.figure(figsize=(14, 10))
plt.plot(valeurs_n, temps_calcul_fibo_lin, "bd:", label="Linéaire impérative")
plt.plot(valeurs_n, temps_calcul_fibo_lin_rec, "ys:", label="Linéaire récursive")
plt.legend()
plt.title("Comparaison de deux implémentations de la fonction de Fibonacci")
plt.xlabel("Valeurs de n")
plt.ylabel("Temps moyen de calcul en secondes")
plt.show()
# ## Exercice 10
#
# Aucune hypothèse n'est faite sur les arguments de la fonction, on supposera seulement qu'elle est itérable sur sa sortie.
# In[43]:
from types import FunctionType # inutile, juste pour faire joli
# première version, f : type x -> type x (simple)
def itere(f : FunctionType, n : int) -> FunctionType:
def fn(x):
for _ in range(n):
x = f(x)
return x
return fn
# In[44]:
itere(lambda x: x + 1, 10)(1)
# On peut aussi écrire une version récursive :
# In[45]:
def compose(f, g):
return lambda x: f(g(x))
"""
def f_rond_g(x):
return f(g(x))
return f_rond_g
"""
# In[48]:
def itere_rec(f : FunctionType, n : int) -> FunctionType:
assert n >= 0
if n == 0:
return lambda x: x
elif n == 1:
return f
else:
return compose(f, itere_rec(f, n-1))
return compose(itere_rec(f, n-1), f)
# In[49]:
itere_rec(lambda x: x + 1, 10)(1)
# In[50]:
get_ipython().run_line_magic('timeit', 'itere(lambda x: x + 1, 1000)(1)')
get_ipython().run_line_magic('timeit', 'itere_rec(lambda x: x + 1, 1000)(1)')
# In[119]:
# deuxième version, f : tuple -> tuple (simple)
def itere2(f : FunctionType, n : int) -> FunctionType:
def fn(*args):
for _ in range(n):
if isinstance(args, tuple):
args = f(*args)
else:
args = f(args)
if isinstance(args, tuple) and len(args) == 1:
return args[0]
else:
return args
return fn
# In[132]:
def plusun(x):
return x + 1
itere2(plusun, 10)(1)
def foisdeux(x, y):
return x * 2, y * 2
itere2(foisdeux, 10)(1, 2)
# ## Exercice 11
#
# C'est assez naturel, on affiche la suite de mouvement à faire, comme une suite de `"T1 -> T2"` par exemple.
# La fonction suivante affiche les déplacements qu'il faut faire pour déplacer une tour de hauteur `n` initialement posée en `x`, à destination de `z` et avec `y` comme position intermédiaire.
#
# - le cas de base est pour une tour de hauteur 1 : un seul déplacement de `x` vers `z` suffit,
# - le cas récursif est très simple : pour une tour de hauteur `n`, il faut déplacer de `x` vers `y` le haut de la tour (de hauteur `n-1` : 1er appel récursif), puis déplacer le plus gros disque (en un mouvement) de `x` vers `z`, puis de nouveau déplacer le haut de la tour (toujours de hauteur `n-1` : 2nd appel récursif) de `y` vers `z`.
# In[144]:
def hanoi(x : str, y : str, z : str, n : int) -> None:
def hanoiaux(orig : str, dest : str, inter : str, n : int):
if n == 0:
return 0
c1 = hanoiaux(orig, inter, dest, n - 1)
print("{} -> {}".format(orig, dest))
c2 = hanoiaux(inter, dest, orig, n - 1)
return c1 + 1 + c2
return hanoiaux(x, z, y, n)
# In[145]:
hanoi("T1", "T2", "T3", 1)
# In[146]:
hanoi("T1", "T2", "T3", 2)
# In[148]:
hanoi("T1", "T2", "T3", 5) # 31 = 2^5 - 1
# ----
# # Listes
# ## Exercice 12
# Les listes en Python sont des `list`.
#
# Elles ne fonctionnent **pas** comme des listes simplement chaînées comme en Caml : ce sont des tableaux, donc l'accès à `T[i]` pour n'importe quel `i` est en $\mathcal{O}(1)$ pour n'importe quel `i` et `n`.
#
# MUST READ
# Allez lire la page https://wiki.python.org/moin/TimeComplexity#list en détail !
# In[51]:
def concatene(liste1 : list, liste2 : list) -> list:
""" O(len(liste1) + len(liste2))"""
# return liste1 + liste2 # solution facile
n1, n2 = len(liste1), len(liste2)
res = []
for i in range(n1 + n2):
if i < n1:
res.append(liste1[i])
else:
res.append(liste2[i - n1])
return res
# In[153]:
concatene([1, 2, 3], [4, 5])
# ## Exercice 13
# In[56]:
from types import FunctionType
def applique(f : FunctionType, liste : list) -> list:
res = [f(x) for x in liste] # solution facile
res = map(f, liste) # encore plus facile
# en itérant la liste :
res = [ ] # tableau vide
for x in liste:
res.append(f(x))
# en itérant ses valeurs :
res = [ ] # tableau
for i in range(len(liste)):
res.append(f(liste[i]))
return res
# In[164]:
applique(lambda x : x + 1, [1, 2, 3])
# ## Exercice 14
# In[165]:
def liste_carree(liste : list) -> list:
return applique(lambda x: x**2, liste)
# In[167]:
liste_carree([1, 2, 3])
# ## Exercice 15
# In[180]:
def miroir_quad(liste : list) -> list:
# aucune idée pour le faire innefficacement en Python,
# ce ne sont pas des listes chaînées
return liste[::-1]
def miroir_lin(liste : list) -> list:
return [liste[-i] for i in range(1, len(liste) + 1)]
# In[181]:
miroir_lin([1, 2, 3])
# ## Exercice 16
# In[186]:
def insertion_dans_liste_triee(entiers : list, x : int) -> list:
i = 0
while i < len(entiers) and entiers[i] < x:
i += 1
return entiers[:i] + [x] + entiers[i:]
# In[187]:
insertion_dans_liste_triee([1, 2, 5, 6], 4)
# In[190]:
def tri_insertion(entiers : list) -> list:
assert all([isinstance(i, int) for _ in entiers])
def trix(e : list, acc : list) -> list:
if len(e) == 0: return acc
else: return trix(e[1:], insertion_dans_liste_triee(acc, e[0]))
return trix(entiers, [])
# In[191]:
tri_insertion([5, 2, 6, 1, 4])
# ## Exercice 17
# In[193]:
def ordre_decroissant(x, y):
return x > y
# In[195]:
from types import FunctionType
def insertion_dans_liste_triee2(entiers : list, x : int, ordre : FunctionType) -> list:
i = 0
while i < len(entiers) and ordre(entiers[i], x):
i += 1
return entiers[:i] + [x] + entiers[i:]
# In[196]:
insertion_dans_liste_triee2([6, 5, 2, 1], 4, ordre_decroissant)
# In[197]:
def tri_insertion2(entiers : list, ordre : FunctionType) -> list:
assert all([isinstance(i, int) for _ in entiers])
def trix(e : list, acc : list) -> list:
if len(e) == 0: return acc
else: return trix(e[1:], insertion_dans_liste_triee2(acc, e[0], ordre))
return trix(entiers, [])
# In[200]:
tri_insertion([5, 2, 6, 1, 4])
tri_insertion2([5, 2, 6, 1, 4], ordre_decroissant)
# ----
# # Exponentiation rapide
# ## Exercice 18
#
# Une approche naïve, de complexité temporelle linéaire en $n$ ($\mathcal{O}(n)$).
# In[76]:
def exp(x : int, n : int) -> int:
res = 1
for _ in range(n):
res *= x
return res
# In[80]:
x = 3
for n in range(8):
print(x, "**", n, "=", exp(x, n), "et =", x**n)
# In[4]:
x = 3
for n in range(8):
print(" {} ** {} = {:>5}".format(x, n, exp(x, n)))
# ## Exercice 19
#
# Une approche maline (optimale, en fait).
#
# Si n = 0 $x^0 = 1$
#
# Si n est pair :
# $$ x^n = (x^{(n/2)})^2$$
# $$ x^n = (x*x)^{(n/2)}$$
#
# Si n est impair :
# $$ x^n = x * (x^{((n-1)/2)})^2$$
# $$ x^n = x * (x*x)^{((n-1)/2)}$$
#
# In[82]:
def exp2(x : int, n : int) -> int:
assert n >= 0
if n == 0:
return 1
elif n == 1:
return x
elif n % 2 == 0:
# NE PAS FAIRE CA
# return exp2(x, n // 2) * exp2(x, n // 2)
return exp2(x * x, n // 2)
return exp2(x, n // 2) ** 2
elif n % 2 == 1:
return exp2(x * x, (n - 1) // 2) * x
# In[83]:
x = 3
for n in range(8):
print(" {} ** {} = {:>5}".format(x, n, exp2(x, n)))
# In[86]:
x = 3.1415
for n in range(8):
print(" {} ** {} = {:>5} et x**n = {}".format(x, n, exp2(x, n), x**n))
# ## Exercice 20
# On ne dispose pas de typage pour faire ça aussi joliment qu'en Caml...
# In[6]:
def mult_float(x : float, y : float) -> float:
return x * y
monoide_flottants = {
'mult': mult_float, # (*.) en Caml
'neutre': 1.
}
# In[6]:
class Monoide_flottant():
def __init__(self, x):
self.x
self.neutre = 1.0
def mult(self, other_float):
return self.x * other_float.x
# In[15]:
import numpy as np
def mult_ndarray(A : np.array, B : np.array) -> np.array:
return np.dot(A, B)
# Pas possible d'avoir un neutre pour une taille quelconque !
monoide_nparray = lambda n, m: {
'mult': mult_ndarray,
'neutre': np.eye(n, m)
}
# In[16]:
mult_ndarray([[1, 1], [1, 1]], [[1, 2], [3, 4]])
# Manuellement ce n'est pas trop dur :
# In[31]:
def mult_mat(A : list, B : list) -> list:
n, m = len(A), len(A[0]) # A est (n, m)
m2, p = len(B), len(B[0]) # B est (m2, p)
assert m == m2
C = [[0 for _ in range(p)] for _ in range(n)] # C est (n, p)
for i in range(n):
for j in range(p):
for k in range(m):
C[i][j] += A[i][k] * B[k][j]
return C
# Pas possible d'avoir un neutre pour une taille quelconque !
monoide_mat = lambda n, m: {
'mult': mult_mat,
'neutre': [[int(i==j) for j in range(m)] for i in range(n)] # I est (n, m)
}
# In[32]:
mult_mat([[1, 1], [1, 1]], [[1, 2], [3, 4]])
# ## Exercice 21
# In[87]:
def exp_rapide(monoide : dict, x, n : int):
mult = monoide['mult']
assert n >= 0
if n == 0:
return monoide['neutre']
elif n == 1:
return x
elif n % 2 == 0:
return exp_rapide(monoide, mult(x, x), n // 2)
elif n % 2 == 1:
return mult(exp_rapide(monoide, mult(x, x), (n - 1) // 2), x)
# ## Exercice 22
# In[34]:
def exp_rapide_float(x : float, n : int) -> float:
return exp_rapide(monoide_flottants, x, n)
# In[35]:
exp_rapide_float(2.0, 8)
# In[36]:
exp_rapide_float(0.2, 8)
# Et pour les matrices, un petit piège à cause des tailles :
# In[37]:
def exp_rapide_mat(A : list, k : int) -> float:
n, m = len(A), len(A[0])
mono = monoide_mat(n, m)
return exp_rapide(mono, A, k)
# In[38]:
for k in range(5):
exp_rapide_mat([[1, 1], [1, 1]], k)
# In[42]:
for k in range(5): # nilpotente
exp_rapide_mat([[0, 1, 2], [0, 0, 1], [0, 0, 0]], k)
# ## Exercice 23
#
# - On peut commencer par réécrire l'exponentiation rapide avec un `itere` :
# In[48]:
def exp_rapide_2(x, n : int):
def mul_par_x(y):
return x * y
return itere(mul_par_x, n)(x)
# In[49]:
exp_rapide_2(2.0, 8)
# - Mais on demandait ici d'écrire `itere` avec l'exponentiation rapide :
# In[94]:
def mult_fonction(f : FunctionType, g : FunctionType) -> FunctionType:
return lambda x: f(g(x))
monoide_fonction = {
'mult': mult_fonction,
'neutre': lambda x: x # identité !
}
# In[95]:
def itere_depuis_monoide(f, n):
return exp_rapide(monoide_fonction, f, n)
# In[99]:
print(itere_depuis_monoide(lambda x: x+1, 0)(1)) # 1
print(itere_depuis_monoide(lambda x: x+1, 10)(1)) # 11
print(itere_depuis_monoide(lambda x: x+1, 1000000)(1)) # pas de stack overflow car complexité O(log(n))
# A comparer avec l'implémentation naïve qui était en $\mathcal{O}(n)$ :
# In[101]:
print(itere(lambda x: x+1, 0)(1)) # 1
print(itere(lambda x: x+1, 10)(1)) # 11
print(itere(lambda x: x+1, 1000000)(1)) # stack overflow car complexité O(n)
# ----
# # Formule du calcul propositionnel
#
# **Spoiler alert** : en Python, c'est chaud.
#
# **ATTENTION** Il faut un peu d'habitude et d'idées pour réussir à faire tout ça aussi efficacement (enfin presque) qu'en OCaml.
#
# On va faire des choses non typées, avec des dictionnaires, pour bidouiller.
#
# ## Exercice 24
# ``(not p ^ ((q ^ not p) v (r v q)))`` s'écrit en Caml `` (Conj(Not(V("p")),Disj(Conj(V("q"),Not(V("p"))),Disj(V("r"),V("q")))))``.
#
# On va imbriquer des dictionnaires, les types, `V`, `Not`, `Conj` et `Disj` seront des clés, et les valeurs seront des formules ou couples de formules.
# Mais on va cacher ça et l'utilisateur verra exactement la même chose qu'en Caml !
# In[57]:
V = lambda x: {'V': x}
Not = lambda x: {'Not': x}
Disj = lambda x, y: {'Disj': (x, y)}
Conj = lambda x, y: {'Conj': (x, y)}
p = V('p')
r = V('r')
q = V('q')
not_p = Not(p)
f = Conj(Not(p), Disj(Conj(q, not_p), Disj(r, q)))
f
# In[60]:
f2 = (Conj(Not(V("p")),Disj(Conj(V("q"),Not(V("p"))),Disj(V("r"),V("q")))))
f2
# Si on veut afficher plus joliment ce genre de structures récursives, la fonction `pprint.pprint(...)` est là pour ça (elle affiche avec de l'indentation) :
# In[59]:
from pprint import pprint
# In[61]:
pprint(f2)
# ## Exercice 25
# Ensuite on fait une filtration "à la main" sur les clés du dictionnaire (de niveau 1, on ne récurse pas quand on teste `'V' in formule`).
# In[62]:
def taille(formule : dict) -> int:
if 'V' in formule:
return 0
elif 'Not' in formule:
return 1 + taille(formule['Not'])
elif 'Conj' in formule:
x, y = formule['Conj']
return 1 + taille(x) + taille(y)
elif 'Disj' in formule:
x, y = formule['Disj']
return 1 + taille(x) + taille(y)
# In[63]:
taille(f)
# In[64]:
taille(f2)
# ## Exercice 26
# In[109]:
def formule_to_string(formule : dict) -> str:
if 'V' in formule:
return formule['V']
elif 'Not' in formule:
return "~" + formule_to_string(formule['Not'])
elif 'Conj' in formule:
x, y = formule['Conj']
return "(" + formule_to_string(x) + " ^ " + formule_to_string(y) + ")"
elif 'Disj' in formule:
x, y = formule['Disj']
return "(" + formule_to_string(x) + " V " + formule_to_string(y) + ")"
# In[110]:
def affiche(formule):
print(formule_to_string(formule))
# In[111]:
affiche(f)
# Et voilà. Pas tellement plus dur hein !
# ## Exercice 27
# Les valeurs des variables seront données comme un dictionnaire associant nom de variable à valeurs booléennes.
# Et comme on veut frimer, on prend un [`defaultdict`](https://docs.python.org/3/library/collections.html#collections.defaultdict), qui est comme un `dict` mais qui stocke aussi une fonction qui donne la valeur des clés absentes du dictionnaire :
# In[104]:
from collections import defaultdict
d = defaultdict(lambda: False, {'p': True, 'q': False})
print(d['p']) # -> True car présent et True
print(d['q']) # -> False car présent et False
print(d['x']) # -> False car absent
print(d['xokazeok']) # -> False car absent
# In[113]:
valeurs_1 = defaultdict(lambda: False, {'p': True})
# In[114]:
valeurs_2 = defaultdict(lambda: False, {'r': True})
# In[89]:
def eval(valeurs : dict, formule : dict) -> bool:
if 'V' in formule:
return valeurs[formule['V']]
elif 'Not' in formule:
return not eval(valeurs, formule['Not'])
elif 'Conj' in formule:
x, y = formule['Conj']
return eval(valeurs, x) and eval(valeurs, y)
elif 'Disj' in formule:
x, y = formule['Disj']
return eval(valeurs, x) or eval(valeurs, y)
# In[90]:
eval(valeurs_1, f)
# In[91]:
eval(valeurs_2, f)
# ## Exercice 28
# In[93]:
def extrait_variables_x(formule : dict) -> list:
if 'V' in formule:
return [formule['V']]
elif 'Not' in formule:
return extrait_variables_x(formule['Not'])
elif 'Conj' in formule:
x, y = formule['Conj']
return extrait_variables_x(x) + extrait_variables_x(y)
elif 'Disj' in formule:
x, y = formule['Disj']
return extrait_variables_x(x) + extrait_variables_x(y)
# on enlève les doublons
def extrait_variables(formule : dict) -> list:
return list(set(extrait_variables_x(formule)))
# In[94]:
extrait_variables(f)
# On trouve facilement les $n$ variables d'une formule.
#
# Ensuite, un [`itertools.product`](https://docs.python.org/3/library/itertools.html#itertools.product) permet de générer les $2^n$ valuations.
# In[98]:
from itertools import product
def toutes_valeurs(variables):
for valeurs in product([False, True], repeat=len(variables)):
yield defaultdict(lambda: False, {k:v for k,v in zip(variables, valeurs)})
# In[103]:
list(toutes_valeurs(extrait_variables(f)))
# In[106]:
def str_of_bool(x : bool) -> str:
# return str(int(x))
return '1' if x else '0'
# In[116]:
def table_verite(formule : dict) -> None:
variables = extrait_variables(formule)
# D'abord la formule
for k in variables:
print(k, end=' ')
print('| ', end='')
affiche(f)
# Puis toutes ces valeurs possibles
for valeurs in toutes_valeurs(variables):
for k in variables:
print(str_of_bool(valeurs[k]), end=' ')
print('| ', end='')
print(str_of_bool(eval(valeurs, formule)))
# In[117]:
table_verite(f)
# Note : ce code est encore plus concis que celui donné dans la solution en Caml.
#
# > On peut vérifier, par exemple sur [Wolfram|Alpha](https://www.wolframalpha.com/input/?i=%28%28not+p%29+and+%28%28q+and+%28not+p%29%29+or+%28r+or+q%29%29%29) que l'on obtient bien le bon résultat...
# ----
#
# # Conclusion
#
# Comme vous le voyez, on arrive à répondre aux mêmes questions dans les deux langages, et il n'y a pas de grosses différences en pratique dans la mise en oeuvre.
#
# Là où OCaml excelle pour les types définis, le filtrage et la récursion, Python gagne en simplicité sur l'affichage, sa librairie standard et les dictionnaires et ensembles...