#! /usr/bin/env python3
# -*- coding: utf-8; mode: python -*-
r""" TP8 au Lycée Lakanal (sujet rédigé par Arnaud Basson), révisions de tout le programme, séance de questions, révisions de la syntaxe et des concepts clés.
- *Dates 1/2 :* jeudi 17 et 24 mars (2016).
- *Dates 2/2 :* dernier TP, jeudi 31 mars (2016).
- *Auteur :* Arnaud Basson & Lilian Besson, pour le cours d'informatique pour tous en prépa MP (http://perso.crans.org/besson/infoMP/),
- *Licence :* MIT Licence (http://lbesson.mit-license.org).
-----------------------------------------------------------------------------
"""
from __future__ import print_function, division # Python 2 compatibility
import random
import numpy as np
# %% Partie I. - Réception des données
if __name__ == '__main__':
print("\n\nI. Reception des donnees.")
# 1.1. Le capteur
[docs]def q1():
r""" Réponse à la question I.1.1).
On a :math:`2^{10} = 1024`, on code les entiers de l'intervalle :math:`[-512, 511]`
par leur reste modulo :math:`1024` (il est compris entre :math:`0` et :math:`1023`, donc son écriture binaire comporte au plus :math:`10` bits).
Cette méthode de codage est appelé le **complément à 2** (et ce n'est bien sur pas la seule possible).
.. note:: On avait déjà vu cette question dans le dernier DS.
"""
pass
[docs]def q2():
r""" Réponse à la question I.1.2).
:math:`10` bits permettent de représenter :math:`1024` valeurs, donc
l'intervalle :math:`[-5V, 5V]` est discrétisé
avec :math:`1024` points, soit une précision de :math:`10/1024`, environ égale à :math:`0.01 V`.
.. note:: Remarque : soit :math:`\delta = 10/1024`, les valeurs discrètes des mesures sont les :math:`k \times \delta`, avec :math:`k` entier dans :math:`[-512, 511]`.
"""
pass
# 1.2. Liaison avec l'ordinateur
[docs]def generateur_car():
r""" Fonction simulant la fonction de liaison avec le capteur, **non demandée** par l'énoncé et non fournie.
.. note:: Les concepts utilisés par cette fonction ne sont pas au programme de prépa, ne vous embêtez pas à la lire ou la comprendre.
"""
entete = ['U', 'I', 'P']
while True:
i = random.randrange(3)
yield entete[i]
n = random.randrange(1, 10)
nn = '0'*(3-len(str(n))) + str(n)
for car in nn:
yield car
somme = 0
for i in range(n):
x = random.randrange(-999, 1000)
somme += x
if x >= 0:
yield '+'
else:
yield '-'
x = str(abs(x))
x = '0'*(3-len(x)) + x
for car in x:
yield car
somme += int(random.gauss(.5, .5)) # Loi normale/gaussienne, mu = 0.5, sigma = 0.5
# on introduit une erreur avec une faible probabilité
somme = str(somme % 10000)
somme = '0'*(4-len(somme)) + somme
for car in somme:
yield car
capteur = generateur_car()
[docs]def car_read(nb):
r""" Fausse fonction ``car_read`` que l'énoncé utilise.
Elle fonctionne, mais ne génère pas de séquences de caractères ayant vraiment du sens.
Elle permet simplement au code suivant d'être valide, et éventuellement exécuté.
- Exemple :
>>> random.seed(0) # Always the same examples
>>> car_read = new_sequence()
>>> sequence = car_read(36)
>>> print(sequence)
P007-159-482+023-190+567-393-0479319
"""
return "".join(next(capteur) for k in range(nb))
[docs]def new_sequence():
r""" Réinitialise le générateur de caractères :py:func:`car_read`.
A utiliser comme ça :
>>> random.seed(0) # Always the same examples
>>> car_read = new_sequence()
>>> sequence = car_read(36)
>>> print(sequence)
P007-159-482+023-190+567-393-0479319
>>> car_read = new_sequence()
>>> sequence = car_read(32)
>>> print(sequence)
I003+511+237-4990249P009+620+804
"""
capteur = generateur_car()
def car_read(nb):
return "".join(next(capteur) for k in range(nb))
return car_read
[docs]def q3():
r""" Réponse à la question I.2.3).
``car_read(4)`` renvoie ``'+004'`` (c'est-à-dire la chaîne formée des
:math:`4` caractères qui suivent les caractères déjà lus ``'U003+012'``).
"""
pass
[docs]def lecture_trame(x):
r""" Réponse à la question I.2.4).
Le sujet donnait la spécification de cette fonction :
1. On lit 3 caractères pour connaître le nombre :math:`n` de blocs de données,
2. Pour chaque bloc, on lit 4 caractères pour un bloc, qu'on stocke dans ``L[k]`` (``k = 0 .. n-1``),
3. A la fin, on lit les 4 derniers caractères pour trouver la somme de contrôle ``S``.
.. warning:: Ne pas oublier dans cette fonction de faire la conversion des chaînes de caractères renvoyées par :py:func:`car_read` en nombres entiers.
- Exemple :
>>> random.seed(0) # Always the same examples
>>> car_read = new_sequence()
>>> sequence = car_read(36)
>>> print(sequence)
P007-159-482+023-190+567-393-0479319
>>> x, L, S = lecture_trame(sequence)
>>> print(L)
[-159, -482, 23, -190, 567, -393, -47]
>>> print(S)
9319
"""
# print("\n==> lecture_trame(x): x = \n", x) # DEBUG
# kind = str(x[0])
# print(" kind =", kind) # DEBUG
i = 1
n = int(x[i:i+3]) # lecture du nombre de blocs de données
# print(" n =", n) # DEBUG
i += 3
L = [0] * n
for k in range(n): # lecture des n blocs
L[k] = int(x[i:i+4]) # lecture d'un bloc (4 caractères, signe compris)
# print(" L[k] =", L[k]) # DEBUG
i += 4
S = int(x[i:i+4]) # lecture de la somme de contrôle
# print(" S =", S) # DEBUG
# Old
# n = int(car_read(3)) # lecture du nombre de blocs de données
# L = [0] * n
# for k in range(n): # lecture des n blocs
# L[k] = int(car_read(4)) # lecture d'un bloc (4 caractères, signe compris)
# S = int(car_read(4)) # lecture de la somme de contrôle
# return [x, L, S]
return [x, L, S]
[docs]def checkSum(trame, reste=10000):
r""" Réponse à la question I.2.5).
Il s'agissait simplement d'implémenter la vérification du reste de ``sum(L)`` modulo :math:`10000` ::
(sum(L) % 10000) == S
.. note::
Pour des sujets comme ça, si rien n'est indique, vous avez normalement le droit
d'utiliser les fonctions Python standards :py:func:`min`, :py:func:`max`, :py:func:`sum`
(pour la somme). Attention, pas de fonction :py:func:`prod` pour le produit...
- Exemple :
>>> random.seed(0) # Always the same examples
>>> car_read = new_sequence()
>>> sequence = car_read(36)
>>> print(sequence)
P007-159-482+023-190+567-393-0479319
>>> trame = lecture_trame(sequence)
>>> print(trame)
['P007-159-482+023-190+567-393-0479319', [-159, -482, 23, -190, 567, -393, -47], 9319]
>>> print(checkSum(trame))
True
"""
_, L, S = trame
return (sum(L) % reste) == S
[docs]def lecture_intensite():
r""" Réponse à la question I.2.7).
La boucle ``while True`` tourne indéfiniment tant qu'elle n'est pas
interrompue de force (par un ``break`` ou un ``return``, ou une exception).
Ceci nous permet d'attendre l'obtention d'une trame commençant par ``'I'``,
et contenant une somme de contrôle correcte (vérifiée avec :py:func:`checkSum`).
"""
while True:
# on lit des caractères jusqu'à obtenir un 'I'
while car_read(1) != 'I':
pass # mot clé de Python pour un bloc d'instructions vide
# on lit la trame puis on vérifie la somme de contrôle
trame = lecture_trame('I')
if checkSum(trame):
return trame
# sinon on passe à l'itération suivante (i.e. on recommence tout).
# %% Partie II. - Analyse des mesures
if __name__ == '__main__':
print("\n\nII. Analyse des mesures.")
# 2.1 Traitement numérique
[docs]def q7():
r""" Réponse à la question II.1.7).
L'intégrale de :math:`f` sur :math:`[a, b]` est approchée selon
`la méthode des trapèzes <XXX>`_
(avec :math:`n+1` points) par la somme suivante :
.. math:: S = \frac{h}{2} \times \sum_{k=0}^{n-1} \left( f(a + k \times h) + f(a + (k+1) \times h) \right)
où :math:`h = \frac{(b-a)}{n}` est le pas, ce qui donne après simplification :
.. math:: S = \frac{h}{2} \times \left( f(a)/2 + f(a+h) + f(a+2h) + \dots + f(a+(n-1)h) + f(b)/2 \right).
"""
pass
[docs]def trapezes(L):
r""" Réponse à la question II.1.8).
Si :math:`L = [a_0, a_1, \dots, a_n]` alors l'intégrale de :math:`f` sur :math:`[0,T]`
est approchée par :math:`\frac{T}{n} \times (a_0/2 + a_1 + a_2 + \dots + a_{n-1} + a_n/2)`
d'après :py:func:`q7` (:math:`a_k` étant la valeur de :math:`f(k T / n)` et :math:`T/n` le pas de temps).
La valeur moyenne (sur :math:`[0, 1]`) est donc approchée par :
.. math::
\frac{1}{n} \times (a_0/2 + a_1 + a_2 + \dots + a_{n-1} + a_n/2) \\
= \frac{1}{n} \times (\mathrm{sum}(a) - a_0/2 - a_n/2) \\
.. note:: Cette expression ne fait pas intervenir directement T, ni le pas de temps (puisque les valeurs de ``L`` sont déjà discrétisées temporellement.
.. attention:: Avec ces notations :math:`a_0, \dots, a_n`, la liste ``L`` contient ``n+1`` valeurs, attention. Donc ``n = len(L) - 1`` !
"""
n = len(L) - 1 # /!\ Attention ici len(L) = n+1
somme = sum(L) - (L[0] + L[-1])/2
return somme / n
[docs]def indicateurs(mesures):
r""" Réponse à la question II.1.9).
1. On calcule la moyenne des mesures, avec la formule des trapèzes, par la fonction :py:func:`trapezes`.
2. On pouvait utiliser une boucle ``for`` ou bien une liste en compréhension pour calculer les écarts quadratique.
ecarts_quad = [(f-moy)**2 for f in mesures]
3. On calcule l'écart-type comme la racine carrée de la moyenne de cette liste ``ecarts_quad``.
.. note:: Pour la **racine carrée**, comme toujours, on peut faire ``x ** 0.5`` ou bien ``math.sqrt(x)`` ou encore ``np.sqrt(x)`` (après avoir importe :py:mod:`math` ou :py:mod:`numpy` ``as np``).
"""
moy = trapezes(mesures)
ecarts_quad = [(val - moy)**2 for val in mesures]
ec_type = trapezes(ecarts_quad)**0.5
return moy, ec_type
# 2.2 Validation des mesures
#: ``omega`` sera considéré comme une variable globale. On prend une valeur quelconque (``1``).
omega = 1
[docs]def simulation(s0, k, dt=0.002, n=500):
r""" Réponse à la question II.2.10).
Ici il fallait utiliser un schéma d'Euler, dans le cas le plus simple : linéaire d'ordre 1, pour résoudre l'équation différentielle suivante :
.. math:: \frac{\mathrm{d} s(t)}{\mathrm{d} t} = - \frac{k}{10} (s(t) - e(t))
:label: EquDiff
.. note:: Le sujet suggérait d'utiliser :py:mod:`numpy`, donc on utilise :py:func:`np.sin` pour calculer le signal d'entrée ``e(t)``.
**Rappel :** si on note ``dt`` le pas de temps et ``t[0],...,t[n]`` les dates
discrétisées (``t[i] = i*dt``), la **méthode d'Euler** a pour but de fournir
des approximations ``s[i]`` des valeurs de la solution exacte aux instants ``t[i]``.
Ces approximations sont calculées par la relation de récurrence ::
s[i+1] = s[i] - dt \times f(s[i], e[i]) = s[i] - dt \times k/10 \times (s[i] - e(t[i])).
Les paramètres à passer à la fonction simulation sont :
- la valeur initiale ``s0 = s(0)``,
- et le coefficient ``k`` (constante dans l'équation :eq:`EquDiff`),
- (``omega`` sera considéré comme une variable globale).
.. warning:: Bien sur, on ne pouvait pas utiliser une fonction du module :py:mod:`scipy` (e.g. :py:func:`scipy.integrate.odeint`) pour calculer directement la solution de l'ED, il fallait implémenter *soi-même* le schéma d'Euler (les sujets le rappellent généralement).
"""
s = [0.0] * (n+1) # il y a (1/dt)+1 = 501 valeurs à calculer
s[0] = s0 # valeur initiale
for i in range(n):
s[i+1] = s[i] - dt * k/10 * (s[i] - np.sin(omega*i*dt))
return s
[docs]def validation(mesures, eps):
r""" Réponse à la question II.2.11).
Pour chaque ``k`` dans ``[0.5, 1.1, 2.0]``, on résout numériquement (avec :py:func:`simulation`),
puis on teste l'écart maximal entre les valeurs mesurées (``mesures[i]``) et les valeurs simulées ``s[i]``.
.. note:: On voit qu'il fallait bien sur mettre ``k`` comme un argument de la fonction précédente :py:func:`simulation`.
.. note:: Ici aussi, on peut utiliser directement la fonction de base de Python :py:func:`max` pour calculer cet écart minimum.
La question disait de renvoyer ``True`` si pour un des ``k`` l'écart maximal est :math:`\leq eps`, ou ``False`` sinon.
.. note:: En français, quand on ne précise pas "inférieur ou égal" ou "inférieur strict", "inférieur" signifie ``<=`` ("inférieur ou égal").
.. warning::
Soyez prudents, en français on utilise une virgule ``,`` pour commencer les décimales,
mais en anglais (et donc en Python), c'est un point ``.``
et on utilise une virgule pour séparer les valeurs dans une liste ou un tuple.
Il faut donc écrire ``[0.5, 1.1]`` et **surtout pas** ``[0,5, 1,1]`` ni ``[0,5; 1,1]``.
Le point-virgule ``;`` n'est **pas** utilisé en Python. Il peut servir à écrire deux instructions sur la même ligne, mais *il ne faut pas s'en servir*...
Si vous faites aussi du `caml <http://ocaml.org/>`_, faites attention puisque le ``;`` est utilise en caml pour séparer les valeurs dans une liste...
"""
for k in [0.5, 1.1, 2.0]:
s = simulation(0, k)
ecarts_num = [abs(mesures[i] - s[i]) for i in range(len(s))]
if max(ecarts_num) <= eps:
return True
return False
# %% Partie III. - Bases de données
if __name__ == '__main__':
print("\n\nIII. Bases de donnees.")
[docs]def q12():
r""" Réponse **SQL** à la question III.12). ::
SELECT nSerie
FROM testfin
WHERE 0.4 <= Imoy AND Imoy <= 0.5
On peut utiliser ``0.4 <= Imoy AND Imoy <= 0.5`` ou ``Imoy BETWEEN 0.4 AND 0.5``.
"""
pass
[docs]def q13():
r""" Réponse **SQL** à la question III.13). ::
SELECT testfin.nSerie, Imoy, Iec, modele
FROM testfin JOIN production
ON testfin.nSerie = production.nSerie
WHERE 0.4 < Imoy AND Imoy < 0.5
Ici il fallait faire la **jointure** (``table1 JOIN table2 ON table1.attr = table2.attr2``) des deux tables ``testfin`` et ``production`` (selon l'attribut ``nSerie``).
.. note:: Quand ``attr1 = attr2``, on peut utiliser le mot clé ``NATURAL JOIN`` mais il vaut mieux éviter (ce n'est pas clair de savoir si c'est au programme ou non).
"""
pass
[docs]def q14():
r""" Réponse **SQL** à la question III.14). ::
SELECT modele, count(*) as nombreValide
FROM production
GROUP BY modele
On groupe par modèle les données de la table ``production`` (``GROUP BY modele``).
La fonction d'agrégation ``COUNT`` permet d'obtenir l'effectif de chaque groupe.
.. note:: Le nommage de la deuxième colonne (``as nombreValide``) n'était pas requis.
"""
pass
[docs]def q15():
r""" Réponse **SQL** à la question III.15).
1. Première solution : avec une sous requête ::
SELECT nSerie, fichierMes
FROM testfin
WHERE nSerie NOT IN
(SELECT nSerie FROM production)
2. Deuxième solution : avec une différence ensembliste (``EXCEPT``)
{imprimantes non validées} = {toutes les imprimantes} \ {imprimantes validées}.
Subtilité : les deux tables dont on fait la différence doivent avoir **exactement**
les mêmes attributs, ce qui oblige à faire une jointure pour ajouter
les fichiers de mesures à la deuxième table (celle des imprimantes validées).
Cela donne une requête plus complexe ::
SELECT nSerie, fichierMes
FROM testfin
EXCEPT
SELECT testfin.nSerie, fichierMes
FROM testfin JOIN production
ON testfin.nSerie = production.nSerie
:Intérêt: analyser les mesures des imprimantes non validées afin de déterminer le problème ayant empêché leur validation (en vue d'y remédier).
"""
pass
# %% Partie IV. - Compression d'un fichier texte
if __name__ == '__main__':
print("\n\nIV. Compression d'un fichier texte.")
# 4.1 Exemples de codages
[docs]def q16():
r""" Réponse à la question IV.1.16).
Le codage de ``'EST'`` est ``1001``, et celui de ``'ASE'`` est ``1001`` aussi.
:Inconvénient: ce codage n'est **pas injectif**, donc il **ne peut pas être décodé** ! (Et donc, il ne sert à rien.)
"""
pass
[docs]def q17():
r""" Réponse à la question IV.1.17).
La séquence ``101101100000100101111`` = ``10 11 011 000 001 001 011 11``
code le mot ``'RETUOOTE'``.
- Ce mot de :math:`8` caractères occupe donc :math:`8` octets = :math:`64` bits en mémoire.
- La séquence codée occupe :math:`21` bits (:math:`24` si chaque caractère était sur :math:`3` bits, mais un ``R`` et deux ``E`` font chacun gagner un bit).
- Donc pour cet exemple, le taux de compression est de :math:`64/21` (à peu près = :math:`3`).
Mais pour que le décodage soit possible, il faut fournir non seulement le
texte codé ``'101101100000100101111'``, mais aussi la correspondance entre
caractères et codes (``'E':11``, ``'R':10``, etc).
Il faut donc stocker aussi cette correspondance dans le fichier compressé,
ce qui dégrade le taux de compression. Néanmoins ce codage reste intéressant
pour un texte long car dans ce cas la place mémoire occupée pour stocker la
correspondance entre lettres et codes est négligeable devant la taille du
texte compressé.
.. note:: Le sujet n'etait pas clair quant à savoir s'il fallait aussi transmettre la table de correspondance lors du calcul du taux de compression (sur ce message exemple ``'RETUOOTE'``).
"""
pass
[docs]def q18():
r""" Réponse à la question IV.1.18).
**Le codage doit être injectif** (deux textes distincts doivent être codés par
des séquences de bits distinctes).
Voici une condition *suffisante* garantissant l'injectivité du code :
il n'existe pas deux lettres ``x1`` et ``x2`` telles que le code de ``x1`` soit
un préfixe du code de ``x2``.
.. note:: On dit qu'un tel codage est un **codage préfixe**.
Le codage de :py:func:`q16` ne remplit pas cette condition (le code de ``E`` est ``1``,
préfixe du code ``10`` de ``A``) et il est ambigu.
Mais par contre, le codage de :py:func:`q17` remplit cette condition (au moins pour les six lettres qu'on nous donne).
:Remarques:
- La condition n'est pas nécessaire, par exemple le codage suivant ``'A':1``, ``'B':10``, ``'C':100`` ne la remplit pas, pourtant il est injectif.
- la condition ci-dessus (codage préfixe) permet un décodage facile des séquences de bits.
"""
pass
# 4.2 Tri des caractères selon leur fréquence
[docs]def est_present(x, cars):
r""" Fonction auxiliaire, qui renvoie ``True`` si ``x`` figure dans la liste ``cars``, ``False`` sinon.
.. note:: En Python, on peut écrire directement ``x in cars``. Ce n'est pas très clair de savoir si ce morceau de syntaxe est au programme ou pas.
- Complexité en temps : en :math:`\mathcal{O}(n)` ou ``n = len(cars)``.
"""
for c in cars:
if x == c:
return True
return False
# return x in cars
[docs]def caracteres_presents(donnees):
r""" Réponse à la question IV.2.19).
On ne demandait pas une complexité particulièrement efficace.
L'implémentation proposée à une complexité en temps en :math:`\mathcal{O}(n c)`
ou ``n = len(donnees)`` et ``c`` est le nombre de caractères différents.
Donc dans le pire des cas, on a un :math:`\mathcal{O}(n^2)` (atteint pour une liste avec ``n`` caractères distincts).
(En fait, ``n`` peut devenir très grand, mais en ASCII ``c`` est ``<= 256``. En UTF-8 ou UTF-16, il y a beaucoup plus de caractères différents mais leur nombre reste borne).
"""
cars = []
for x in donnees:
# x est-il déjà dans la liste cars ?
if not est_present(x, cars): # x not in cars
cars.append(x)
return cars
[docs]def indice(x, cars):
r""" Fonction auxiliaire, qui renvoie un indice ``i`` tel que ``cars[i] = x`` et si ``x`` n'est pas présent dans cars, elle renvoie ``-1``.
- Elle renvoie le plus petit ``i`` tel que ``cars[i] = x``.
.. note:: En Python, on peut écrire directement ``cars.index(i)``. Ce n'est pas très clair de savoir si ce morceau de syntaxe est au programme ou pas... Notez que la méthode ``index`` ne renvoie pas ``-1`` en cas d'échec, elle renvoie une exception (``ValueError``).
- Complexité en temps : en :math:`\mathcal{O}(n)` ou ``n = len(cars)``.
"""
for i in range(len(cars)):
if x == cars[i]:
return i
return -1
# return cars.index(x)
[docs]def caracteres_frequences(donnees):
r""" Réponse à la question IV.2.20).
On ne demandait pas une complexité particulièrement efficace.
L'implémentation proposée a une complexité en temps en :math:`\mathcal{O}(n c)`
ou ``n = len(donnees)`` et ``c`` est le nombre de caractères différents.
"""
cars = []
freq = []
# A l'initialisation, l'invariant (I) est vrai.
for x in donnees:
# x est-il déjà dans la liste cars ?
i = indice(x, cars)
if i >= 0:
freq[i] += 1 # si x est déjà présent, augmenter de 1 sa fréquence
# On utilise l'invariant (I)
else:
# On conserve ici l'invariant (I) disant que si x est présent (dans cars),
# sa fréquence (dans freq) est au même indice.
cars.append(x) # sinon ajouter x avec une fréquence de 1.
freq.append(1)
return cars, freq
[docs]def q21():
r""" Réponse à la question IV.2.21).
Exécution de ``aux(cars, freq, 2, 7)`` :
on indique les valeurs des variables après chaque itération de la boucle ``while``
(1ère ligne = état initial) ::
k m cars freq
7 7 [' ', 'a', 'c', 't', 'e', 'è', 's', 'r'] [4, 6, 3, 4, 8, 1, 7, 4] (ini)
6 6 [' ', 'a', 'c', 't', 'e', 'è', 's', 'r'] [4, 6, 3, 4, 8, 1, 7, 4] (1e iter)
5 6 [' ', 'a', 'c', 't', 'e', 'è', 's', 'r'] [4, 6, 3, 4, 8, 1, 7, 4] (2e iter)
4 5 [' ', 'a', 'c', 't', 'è', 'e', 's', 'r'] [4, 6, 3, 4, 1, 8, 7, 4]
3 5 [' ', 'a', 'c', 't', 'è', 'e', 's', 'r'] [4, 6, 3, 4, 1, 8, 7, 4]
2 5 [' ', 'a', 'c', 't', 'è', 'e', 's', 'r'] [4, 6, 3, 4, 1, 8, 7, 4]
Après la sortie de la boucle, on échange les éléments d'indices ``5`` et ``7``,
d'où l'état final des deux tableaux :
``[' ', 'a', 'c', 't', 'è', 'r', 's', 'e'], [4, 6, 3, 4, 1, 4, 7, 8]``
et la valeur renvoyée est ``5``.
"""
pass
[docs]def q22():
r""" Réponse à la question IV.2.22).
La fonction ``aux`` travaille sur le sous-tableau allant des indices ``i`` à ``j`` (inclus).
Il s'agit d'une fonction de partition (servant à effectuer un tri rapide),
elle utilise comme ``pivot`` le dernier élément du sous-tableau : ``pivot = freq[j]``,
et la partition se fait à partir de la droite (pas comme celle vue en TP, qui partait de la gauche).
La fonction partitionne le tableau ``freq[i:j+1] = [freq[i],...,freq[j]]``
de façon à placer à gauche du ``pivot`` les éléments ``<= pivot`` et à droite les éléments ``> pivot``.
"""
pass
[docs]def q22_preuve():
r""" Preuve formelle de la question IV.2.22) :
1. Terminaison : à chaque itération de la boucle ``while``, ``k`` diminue de ``1``
donc la boucle termine en exactement ``j-i`` itérations (on aurait aussi bien
pu faire une boucle ``for``).
2. Correction (prouver que la fonction fait ce qu'on veut).
Pour l'invariant : un dessin vaut mieux qu'un long discours ::
i k m j
-----------------------------------------------------------
| ... | <= pivot | > pivot |p|
-----------------------------------------------------------
(p désigne le pivot, les points de suspension les éléments pas encore examinés).
A la fin de chaque itération de la boucle ``while``, on a l'invariant suivant :
- ``freq[r] <= pivot`` pour tout indice ``r`` tel que ``k <= r < m``,
- ``freq[r] > pivot`` pour tout indice ``r`` tel que ``m <= r < j``.
2.a. Cet invariant est vrai avant d'entrer dans la boucle ``while``
(les 2 conditions sont vides lorsque ``k = m = j``).
2.b. Cet invariant est conservé par les itérations : on décrémente ``k`` de ``1`` et on examine ``freq[k]``
(qui est alors l'élément le plus à droite de la zone contenant les
points de suspension) : s'il est ``<= pivot`` il n'y a rien à faire;
s'il est ``> pivot`` (i.e. ``freq[k] > freq[j]``), on l'échange avec l'élément
*le plus à droite* de la zone <= pivot : pour cela on décrémente ``m`` de ``1``
et on effectue l'échange des éléments d'indices k et m.
Ainsi l'invariant est maintenu. Victoire.
2.c. En sortie de la boucle ``while``, on a k = i, et on effectue l'échange
du pivot avec l'élément d'indice m, afin de mettre le pivot à sa
place définitive entre les 2 zones ::
i m j
-----------------------------------------------------------
| <= pivot |p| > pivot |
-----------------------------------------------------------
La fonction ``aux`` a donc bien réalisé la partition du sous tableau
``[freq[i],...,freq[j]]`` autour du pivot ``p``.
Quant au tableau ``cars``, il est modifié en même temps que ``freq`` :
chaque fois qu'on échange deux éléments de ``freq``, on échange les
deux mêmes éléments de ``cars``, afin de conserver la propriété (I) de
correspondance entre les deux tableaux :
(I) pour tout indice ``r``, ``freq[r]`` est le nombre d'occurrences de ``cars[r]`` dans le texte initial.
"""
pass
[docs]def q23():
r""" Réponse à la question IV.2.23).
L'instruction suivante effectue le tri souhaité ::
tri(cars, freq, 0, len(cars)-1)
La fonction tri effectue le **tri rapide** ("quicksort") à l'aide de la fonction
de partition :py:func:`aux` (le tableau `freq` est trié en ordre croissant
et le tableau `cars` est modifié au fur et à mesure afin de conserver
la correspondance entre les deux tableaux, l'invariant (I) utilisé dans la fonction précédente).
La complexité dans le pire cas du tri rapide est :math:`\mathcal{O(n^2)}`, où n est la
longueur des tableaux considérés (mais en moyenne il est bien meilleur, en :math:`\mathcal{O(n \log(n))}`).
Le tri par fusion a une complexité plus faible dans le pire cas : :math:`\mathcal{O(n \log(n))}`.
"""
pass
# 4.3 Codage de Huffman
[docs]def insertion(t, q, cars_ponderes):
r""" Réponse à la question IV.3.24).
On peut utiliser ``cars_ponderes.insert(i, [t, q])`` pour insérer la petite liste `[t, q]` à la position ``i``, trouvée d'après ce que demande l'énoncé ::
i = argmin cars_ponderes[i][1] < q, i >= 0
"""
i = 0
while i < len(cars_ponderes) and cars_ponderes[i][1] < q:
i += 1
# cars_ponderes = cars_ponderes[:i] + [[t, q]] + cars_ponderes[i:]
# ou mieux :
cars_ponderes.insert(i, [t, q])
return cars_ponderes
[docs]def numero(x):
r""" On avait besoin de cette fonction auxiliaire, qui donne le numéro (un entier) associe au caractère ``x``. On utilise la fonction Python :py:func:`ord` (fournie par défaut).
- Exemples :
>>> print(numero('a'))
0
>>> print(numero('z'))
25
"""
return ord(x) - ord('a') # Envoie 'a' sur 0, 'b' sur 1, etc.
[docs]def codage(cars, freq):
r""" Réponse à la question IV.3.25).
On peut vérifier l'exemple de l'énoncé :
>>> cars = ['f','b','d','a','c','e']
>>> freq = [1, 2, 3, 4, 4, 9]
>>> print(codage(cars, freq))
['110', '1001', '111', '101', '0', '1000']
"""
# cars et freq sont triés par fréquence croissante
cars_ponderes = [[cars[i], freq[i]] for i in range(len(cars))]
# La liste des cars_ponderes restera triée par poids croissant au cours de l'algorithme.
code = [''] * len(cars) # Initialisation du tableau des codes
# Le code de chaque caractère x est code[k] où k = numero(x)
while len(cars_ponderes) > 1:
[s1, p1] = cars_ponderes[0]
[s2, p2] = cars_ponderes[1]
s = s1 + s2 # Concaténation des chaînes /!\
# On peut aussi faire "%s%s" % (s1, s2), ou "{}{}".format(s1, s2)
p = p1 + p2 # Somme des poids
cars_ponderes = cars_ponderes[2:] # Suppression de [s1,p1] et [s2,p2]
cars_ponderes = insertion(s, p, cars_ponderes) # Insertion de [s,p]
# Ajout d'un 0 dans les codes des lettres de s1
for x in s1: # x est un caractère
k = numero(x) # Le code de x est code[k]
code[k] = '0' + code[k]
for x in s2: # Idem avec s2
k = numero(x)
code[k] = '1' + code[k]
return code
# 4.4 Décodage
[docs]def q26():
r""" Réponse à la question IV.4.26).
C'était assez direct, une fois qu'on comprend ce qu'est l'ordre lexicographique :
'0' < '1000' < '1001' < '101' < '110' < '111'
On peut vérifier avec Python :
>>> tab = ['110', '1001', '111', '101', '0', '1000']
>>> print(sorted(tab))
['0', '1000', '1001', '101', '110', '111']
"""
pass
[docs]def q27():
r""" Réponse à la question IV.4.27). Décodage de ``txt_bin`` = ``'010100000011011101111011110'``.
Voici le découpage ::
txt_bin = '010' + '10' + '000' + '001' + '10' + '1110' + '1111' + '011' + '110'
À savoir :
- ``pos = 0``, ``m = 2``, code ``'010'``, lettre ``'b'``,
- ``pos = 3``, ``m = 4``, code ``'10'``, lettre ``'o'``,
- ``pos = 5``, ``m = 0``, code ``'000'``, lettre ``'n'``,
- ``pos = 8``, ``m = 1``, code ``'001'``, lettre ``'j'``,
- ``pos = 11``, ``m = 4``, code ``'10'``, lettre ``'o'``,
- ``pos = 13``, ``m = 6``, code ``'1110'``, lettre ``'u'``,
- ``pos = 17``, ``m = 7``, code ``'1111'``, lettre ``'r'``,
- ``pos = 21``, ``m = 3``, code ``'011'``, lettre ``' '`` (espace),
- ``pos = 24``, ``m = 5``, code ``'110'``, lettre ``'!'``,
Le texte ayant été compressé était donc ``'bonjour !'``.
"""
pass
[docs]def decode_car(txt_bin, pos, code):
r""" Réponse à la question IV.4.24).
C'est exactement une **recherche dichotomique** dans un tableau trié (le tableau
``code``), sauf qu'au lieu de manipuler des nombres ordonnés dans l'ordre usuel
on manipule des chaînes de caractères, ordonnées par ordre lexicographique.
**Subtilité technique :**
les codes ayant des longueurs variables, au moment
de tester si ``code[m]`` est présent dans la chaîne ``txt_bin`` à la position ``pos``,
il faut extraire de ``txt_bin`` une sous_chaine de longueur adéquate
(la variable ``longueur`` sert à cela, `cf. le code <_modules/TP8.html#decode_car>`_).
Le nombre de comparaisons de chaînes est du même ordre de grandeur que le
nombre d'itérations de la boucle ``while`` (il y a une ou deux comparaisons à
chaque itération, dans le ``if`` et le ``elif``), donc c'est en :math:`\mathcal{O}(\log n)`
où ``n = len(code)``.
**Rappel de la preuve :**
À chaque itération on travaille dans le sous-tableau ``code[g:d+1]``
i.e. ``[code[g], ..., code[d]]``, de longueur ``d-g+1``; initialement la
est ``n``, et à chaque itération cette longueur est au moins divisée par :math:`2`;
dans le pire cas le nombre :math:`p` d'itérations vérifie :math:`n \simeq 2^p`,
soit :math:`p \simeq \log(n)`.
"""
# Recherche dichotomique d'un préfixe de ``txt_bin[pos:]`` dans le tableau
# de chaînes ``code`` (trié par ordre lexicographique).
g = 0
d = len(code) - 1
while g <= d:
m = (g + d) // 2
longueur = len(code[m]) # longueur de la sous-chaîne à tester
if txt_bin[pos:pos+longueur] == code[m]: # pas d'erreur même si pos+longueur>len(txt_bin)
return m
elif txt_bin[pos:pos+longueur] < code[m]: # comparaison pour ordre lex
d = m - 1
else:
g = m + 1
# Normalement on ne sort pas du ``while`` sans avoir trouvé ce qu'on cherche
# sinon il y a un souci dans le codage !
raise ValueError("decode_car(txt_bin, pos, code) a echoue !")
# print("erreur de décodage")
[docs]def decode_txt(txt_bin, code, cars):
r""" Réponse à la question IV.4.29).
La dernière question n'était pas trop dure, en suivant à la lettre les consignes.
- Exemple :
>>> txt_bin = '010100000011011101111011110'
>>> code = ['000', '001', '010', '011', '10', '110', '1110', '1111']
>>> cars = ['n', 'j', 'b', ' ', 'o', '!', 'u', 'r']
>>> decode_txt(txt_bin,code,cars) # On trouve comme au dessus
'bonjour !'
"""
txt_clair = ""
pos = 0
while pos < len(txt_bin):
m = decode_car(txt_bin, pos, code) # décoder un caractère
txt_clair += cars[m] # ajouter ce caractère dans le texte décodé
pos += len(code[m]) # passer à la position du caractère codé suivant
return txt_clair
# %% Fin de la correction.
if __name__ == '__main__':
from doctest import testmod
print("Test automatique de toutes les doctests ecrites dans la documentation (docstring) de chaque fonction :")
# testmod(verbose=True)
testmod()
print("\nPlus de details sur ces doctests peut etre trouve dans la documentation de Python:\nhttps://docs.python.org/3/library/doctest.html (en anglais)")
# Fin de TP8.py