XD blog

2013-12

2013-12-30 Bitcoin

Le Bitcoin est la première monnaie électronique à susciter autant d'intérêt. Si vous voulez découvrir comment elle fonctionne, quel rôle elle a pu jouer durant la crise financière à Chypre, alors vous devriez sans doute écouter l'émission Place de la Toile du 12 décembre (France Culture) puis lire le blog Petit cours de Bitcoin pour les nuls. Il y a aussi l'épisode 13 de la saison 3 de la série The Good Wife qui s'intitule Bitcoin for dummies. Le sujet aurait problablement été plus intéressant s'il avait été traité par la série Ally McBeal qui n'aurait probablement pas utilisé la même astuce pour défendre son client.

L'arrivée de l'informatique et d'internet bouleverse quelques modèles économiques. La presse, la musique peinent à trouver un nouvel équilibre. On explore d'autres horizons, parfois depuis plus de 40 ans comme ce concept de supermarchés où les clients sont aussi les employés : FoodCoop (FoodCoop dans rue89) qui pourrait se décliner à Paris avec CoopLaLouve. Ce projet a cherché son financement sur KissKissBankBank qui sort des circuits traditionnels. Zach Braff, le réalisateur de Garden State a utilisé ce système pour financer son prochain film pour, dit-il, garder son indépendence.

2016/05/17, un lien vers une infographie que m'a envoyée Bastien Hudelot : Bitcoin, la crypto-monnaie qui monte

2013-12-29 Big or small modules in Python, pyrsslocal

It is not always easy to determine a good size for a module or a set of modules. Should it be kept as a single bloc which comes alone or a set of smaller modules? It is easier to understand a smaller modules. It usually limits itself to a small set of similar functionalities. However, extending a small module is faster than starting a new one, it avoids spending too much time setting up the installation steps, documentation automation, dependencies with others modules. Small modules grow, especially if you work late on them on your free time.

pypi makes it simple to install a module and its dependencies, GitHub helps to fork some existing module which needs to be fixed for a specific usage. That's why I started to split my own toolbox. Does it worth the effort knowing I'm the only one to use it? Probably not but, for my teachings, I think I will not be reluctant anymore to create a new small project for a specific purpose.

I created or updated three modules:

pyquickhelper: functions quickly written to help generating sphinx documentation
pyensae: functions used in pratical lessons
pyrsslocal: I was using Google Reader and I was reluctant to use another service, wondering if it would disappear. It could be improved but it is already usable.

2013-12-15 Quelques exercices de préparation à l'examen (5)

Lorsqu'on cherche un élément dans un tableau, c'est généralement pour retrouver sa position. Supposons maintenant que cet élément soit présent en plusieurs exemplaires et qu'on veuille toutes les positions où il est présent.

def positions(liste, element) :
    ...
    return une liste
    
l = [ 4,3,3,6,4,3 ]
print ( positions(l, 3) ) # affiche [1,2,5]

Dans un second temps, on veut transformer la liste l en un dictionnaire de sorte que la fonction positions ne contienne plus de boucle. Quelle est la solution la plus rapide ?

more...

2013-12-14 Quelques exercices de préparation à l'examen (4)

On reprend le même texte que celui de l'exercice précédent. On veut connaître le nombre maximum de mots qu'on peut trouver entre deux mots commençant par une voyelle.

# source du texte : http://www.gutenberg.org/files/1567/1567-h/1567-h.htm#link2H_4_0017
texte = """They are rattling breakfast plates in basement kitchens,
And along the trampled edges of the street
I am aware of the damp souls of housemaids
Sprouting despondently at area gates.
The brown waves of fog toss up to me
Twisted faces from the bottom of the street,
And tear from a passer-by with muddy skirts
An aimless smile that hovers in the air
And vanishes along the level of the roofs.""".replace("\n"," ").lower().split()

def nombre_de_mot_maximum(mots) :
    ...
    return un_nombre

more...

2013-12-13 Quelques exercices de préparation à l'examen (3)

On veut calculer la longueur moyenne des mots ayant le même nombre de voyelles. Le résultat est un dictionnaire où chaque élément vérifie :

La clé est le nombre de voyelles.
La valeur est la moyenne des mots du texte ayant le même nombre de voyelles.

La fonction qui compte le nombre de voyelles d'un mot est décrite sur cette page : exercice 2.

# source du texte : http://www.gutenberg.org/files/1567/1567-h/1567-h.htm#link2H_4_0017
texte = """They are rattling breakfast plates in basement kitchens,
And along the trampled edges of the street
I am aware of the damp souls of housemaids
Sprouting despondently at area gates.
The brown waves of fog toss up to me
Twisted faces from the bottom of the street,
And tear from a passer-by with muddy skirts
An aimless smile that hovers in the air
And vanishes along the level of the roofs.""".replace("\n"," ").lower().split()

def moyenne_longueur_pour_chaque_nombre_de_voyelles(mots) :
    ...
    return un dictionnaire

more...

2013-12-12 Quelques exercices de préparation à l'examen (2)

On veut écrire une fonction qui compte le nombre de voyelles dans un mot.

def compte_voyelles(mot):
    ...
    return le nombre de voyelles
    
print (compte_voyelles("oui"))  # doit afficher 3
print (compte_voyelles("non"))  # doit afficher 1

more...

2013-12-11 Quelques exercices de préparation à l'examen (1)

On veut écrire une fonction qui détermine si une lettre est une voyelle.

def est_voyelle(c):
    ...
    return 0 ou 1
    
print (est_voyelle("a"))  # doit afficher 1
print (est_voyelle("b"))  # doit afficher 0

Il faut écrire cette fonction de trois manières différentes :

La fonction n'est composée que de tests.
La fonction est composée d'un test et d'une liste.
Il n'y a aucun test dans la fonction, on utilise seulement un dictionnaire.

more...

2013-12-07 Optimisation sous contraintes appliquée au calcul du report des voix

Entre les deux tours des élections présidentielles, on parle beaucoup du report des voix des élections. Dans la plupart des articles que j'ai trouvés (Les 1.139.316 voix qui ont fait la victoire d'Hollande), ces intentions sont estimées par sondage. Un blog parle d'une méthode d'estimation après seulement que les élections ont eu lieu : Estimation des reports de voix - explications techniques. La méthode proposée est bayésienne. Ici, j'ai utilisé l'optmisation sous contraintes car c'est la méthode que je souhaitais illustrer pour mes enseignements. J'ai pris les élections comme exemples d'application. Les données sont accessibles sur le site (data.gouv.fr , élections 2012). Elles incluent les chiffres aggrégés par départements et cantons dont je me suis servi et que j'ai regroupés ici : french_elections.zip).

On dispose donc des voix ventilées par candidats et disponibles pour chaque départements. On cherche à calculer une matrice de report de voix qui soit la même pour tous les départements.

ARTHAUD	Abstentions	BAYROU	Blancs et nuls	CHEMINADE	Code dep	DUPONT-AIGNAN	HOLLANDE	JOLY	LE PEN	Département	MÉLENCHON	POUTOU	SARKOZY	total
source open.data.gouv.fr: élections 2012
1794	65996	32650	6453	860	1	7208	73096	7268	66540	AIN	30898	3323	97722	393808
2490	72928	19895	5196	738	2	5853	80751	3455	78452	AISNE	30360	3860	72090	376068
1482	45266	17814	5059	457	3	4068	61131	3232	37736	ALLIER	27969	2584	49477	256275
487	21034	7483	2111	283	4	1845	24551	2933	20875	ALPES DE HAUTE PROVENCE	15269	1394	25668	123933
1576	153383	38980	9063	1238	6	9241	111990	12556	136982	ALPES MARITIMES	49493	4048	216738	745288

Abstentions	Blancs et nuls	Code	HOLLANDE	Département	SARKOZY	total
source open.data.gouv.fr: élections 2012
67279	19513	1	131333	AIN	175741	393866
73997	21056	2	147260	AISNE	133760	376073
45079	14924	3	111615	ALLIER	84593	256211
20314	6639	4	49498	ALPES DE HAUTE PROVENCE	47444	123895
146254	30067	6	203117	ALPES MARITIMES	366055	745493

On cherche une matrice V qui permet d'obtenir les voix Y du second tour en fonction des voix du premier tour X :

$Y = VX, \; X \in M_{nc}, \; Y \in M_{nd}, \; V \in M_{cd}$

n est le nombre de départements, c est le nombre de candidats du premier tour (abstention et bulletin nuls inclus), d est le nombre de candidats du second tour. La matrice V définit le report des voix : V_ij est la proportion des voix du candidat c allant au candidat d. Elle vérifie les contraintes suivantes :

$\begin{array}{l} \forall c,d, \; V_{cd} \leqslant 0 \\ \forall c, \; \sum_{d=1}^{D} V_{cd} = 1 \end{array}$

more...

2013-12-06 Extend the exception stack in Python

Most of the time, message given by exception are not enough precise to quickly understand the error. To add more information, I used to catch it and throw a new one:

try :
    # something
except Exception as e :
    message = "my message with more information \n" + str(e)
    raise Exception(message)

However, it is possible to do this:

try :
    # something
except Exception as e :
    message = "my message with more information"
    raise Exception(message) from e

It does not break the exception stack as before. The new exception is just added to it.

more...

2013-12-02 Distance d'édition et programmation dynamique

La distance d'édition (ou distance de Levenstein) est un algorithme très connu qui sert à comparer deux mots, deux chaînes de caractères et, plus généralement, deux séquences. La distance est définie comme le nombre d'opérations minimum qui permet de passer du premier mot au second sachant qu'il n'existe que trois opérations possibles :

le remplacement d'un caractère par un autre,
la suppression d'un caractère,
l'insertion d'un caractère.

Par exemple, dans le cas des deux mots : idstzance et distances, cela donne :

Dans l'exemple qui précède, ces trois opérations ont un coût identique. Mais il pourrait tout-à-fait dépendre du caractère inséré ou supprimé ou de la comparaison entre les deux caractères. La distance est alors la somme de ces coûts.

Trouver le nombre minimal d'opérations est un problème classique qu'on peut résoudre à l'aide de la programmation dynamique. Cela veut dire que le problème vérifie la propriété suivante : Toute solution optimale s'appuie elle-même sur des sous-problèmes résolus localement de façon optimale (Wikipedia). Cela veut souvent dire qu'il existe une façon de trouver la solution du problème par récurrence. Ou alors, si on trouve une façon de couper le problème en deux, la solution optimale sera la combinaison des deux solutions optimales sur chacune des deux parties.

more...

2013-12-01 Recherche dichotomique, récursive, itérative et le logarithme

Lorsqu'on décrit n'importe quel algorithme, on évoque toujours son coût, souvent une formule de ce style :

$O\left(n^u (\ln_2 n)^v\right)$

u et v sont des entiers. v est souvent soit 0, soit 1. Mais d'où vient ce logarithme ? Le premier algorithme auquel on pense et dont le coût correspond au cas u=0 et v=1 est la recherche dichotomique. Il consiste à chercher un élément dans une liste triée. Le logarithme vient du fait qu'on réduit l'espace de recherche par deux à chaque itération. Fatalement, on trouve très vite l'élément à chercher. Et le logarithme, dans la plupart des algorithmes, vient du fait qu'on divise la dimension du problème par un nombre entier à chaque itération, ici 2.

La recherche dichotomique est assez simple : on part d'une liste triée T et on cherche l'élément v (on suppose qu'il s'y trouve). On procède comme suit :

On compare v à l'élément du milieu de la liste.
S'il est égal à v, on a fini.
Sinon, s'il est inférieur, il faut chercher dans la première moitié de la liste. On retourne à l'étape 1 avec la liste réduite.
S'il est supérieur, on fait de même avec la seconde moitié de la liste.

C'est ce qu'illustre la figure suivante où a désigne le début de la liste, b la fin, m le milieu. A chaque itération, on déplace ces trois positions.

more...

Xavier Dupré