Le blog-notes mathématique du coyote

 

Extra
Langues :

Editorial

Ce blog a pour sujet les mathématiques et leur enseignement au Lycée. Son but est triple.
Premièrement, ce blog est pour moi une manière idéale de classer les informations que je glâne au cours de mes voyages en Cybérie.
Deuxièmement, ces billets me semblent bien adaptés à la génération zapping de nos élèves. Ces textes courts, privilégiant le côté ludique des maths, pourront, je l'espère, les intéresser et leur donner l'envie d'en savoir plus ou, pourquoi pas, de créer leur propre blog...
Enfin, c'est un bon moyen de communiquer avec des collègues de toute la francophonie.


mardi 28 février 2012

Lemme de Burnside (2)

Le lemme de Burnside... Outre le fait qu'il n'est pas dû à Burnside et qu'on peut le considérer autrement qu'un lemme, ce résultat obscur de la théorie des groupes permet de faire des choses hallucinantes ! Si si ! Il permet par exemple de compter le nombre de colliers que l'on peut faire avec 3 perles rouges, 3 perles bleues et 5 perles vertes. Il permet aussi de compter le nombre de colliers que l'on peut faire avec 6 perles jaunes, 3 perles bleues, une perle verte et une perle rouge.
Il permet en fait de répondre à n'importe quel problème de dénombrement avec des perles ! (et certains problèmes sans perle : combien y a-t-il de façons de partager un paquet de Vache qui rit (aux isométries près) entre 3 personnes, combien existe-t-il de sudokus réellement différents, etc.). Le lemme de Burnside est l'exemple typique de l'énoncé abstrait d'un domaine abstrait qui trouve des applications concrètes dans des domaines concrets (pour peu que l'on aime fabriquer des colliers).

Lire l'article sur Choux Romanesco, vache qui rit et intégrales curvilignes.

lundi 27 février 2012

Sesamath.ch

L'association "Sesamath Suisse Romande" a été créé en 2009 pour favoriser en Suisse Romande la diffusion des principes et des ressources existantes de sa "grande soeur" Sesamath (France). Elle a comme objectif de diffuser les principes et les ressources de Sesamath (France), mais aussi d'adapter et/ou produire des ressources pédagogiques spécifiquement adaptées aux plans d'études officiels romands de mathématique, puis de les mettre gratuitement et sous licence libre à disposition des enseignants, élèves et parents de toute la Romandie.

mardi 21 février 2012

La génération aléatoire de clés RSA ne laisse pas assez de place au hasard

Le si réputé algorithme de génération de clés de chiffrement RSA ne laisse pas une part assez grande au hasard pour être totalement fiable. Des chercheurs viennent ainsi de démontrer qu’il offre au mieux une sécurité de 99,8 % et, au pire, une sécurité nulle.

L’algorithme utilisé pour générer des certificats X.509 ou encore des clés de chiffrement PHP n’est pas aussi sûr que l’on pouvait l’imaginer jusqu’ici. La découverte en a été faite par des chercheurs en cryptographie de l'EFFL et publiée dans un article Ron was wrong, Whit is right. Ceux-ci indiquent avoir procédé à une «vérification de l’état sanitaire de clés publiques trouvées sur Internet», avec pour objectif de «tester la validité de l’assertion selon laquelle un choix aléatoire différent est fait à chaque fois que des clés sont générées ». Une opération qui a échoué : «la vaste majorité des clés publiques fonctionne comme prévu» mais «deux modulos RSA pour mille n’offrent aucune sécurité ». Pourquoi ? Notamment parce qu’il y a des duplicatas, bien involontaires, certes, mais dont l’existence même pose problème.
Concrètement, les chercheurs aboutissent à la conclusion «qu’il y a plus de duplicatas» que ce que les études précédentes avaient pu laisser penser : «sur 6,4 millions de modulos RSA distincts, 71504 (1,1 %) apparaissent plus d’une fois, et même des milliers de fois pour certains.» Pire, ils assurent avoir trouvé 12934 modulos RSA n’offrant aucune sécurité : «les clés privées [correspondantes] sont accessibles à n’importe qui prendrait la peine de reproduire notre travail », assurent-ils. Et d’estimer ainsi que, au mieux, l’algorithme RSA 1024 bits offre une sécurité de 99,8 %. Pour ces chercheurs, le chiffrement basé sur un secret unique - et non pas sur un couple clé privé/clé publique - et sur l’algorithme Diffie-Hellman serait finalement plus sûr. Pour l’expert Bruce Schneier, c’est un «excellent travail» qu’on fait là les chercheurs. Mais pour lui, l’algorithme RSA ou le principe du chiffrement asymétrique ne sont pas remis en cause par cette étude : le problème vient «presque certainement du générateur de nombres aléatoires» utilisé pour la création de ces clés publiques. Et «cela ne devrait surprendre personne. L’un des points les plus difficiles de la cryptographie est la génération de nombres aléatoires ». Et d’ajouter que «la capacité à produire quelque chose d’aléatoire n’est pas une exigence fonctionnelle et à moins que vous ne la testiez spécifiquement - et que vous sachiez comment la tester - vous penserez probablement que votre système cryptographique fonctionne correctement ».
En fait, pour les chercheurs, c’est environ 0,003 % des clés RSA publiques qui est potentiellement vulnérable, « ce qui ne semble pas inacceptable ». Pour Bruce Schneier, il y a effectivement un risque mais il est difficile à quantifier. Et la nature aléatoire - encore - de la menace fait «qu’il est difficile de savoir comment monétiser» la faille. Ce qui tend à réduire la menace concrète. Toutefois, il s’interroge sur l’éventualité de générateurs de nombres aléatoires «volontairement affaiblis. Les suspects les plus évidents sont les services de renseignement nationaux comme la NSA. Je n’ai aucune preuve mais si je devais affaiblir des systèmes de chiffrement, je commencerais par les générateurs de nombres aléatoires.»

Source : lemagIT.fr

lundi 20 février 2012

Preuves interactives

En théorie de la complexité, les preuves interactives permettent, via un jeu de questions et réponses, de certifier, avec une très forte probabilité, la véracité d’un énoncé. En voilà un exemple, où il est question des chaussettes d’un daltonien.

Lire l'article sur Images des mathématiques.

samedi 18 février 2012

La vache - Les pompiers


mercredi 15 février 2012

Programmation en Python pour les mathématiques


Programmation en Python pour les mathématiques
Alexandre Casamayou-Boucau, Guillaume Connan, Pascal Chauvin
Dunod (8 février 2012)
304 pages

Présentation de l'éditeur
Python est un langage de programmation libre, multi-plateforme, offrant des outils de haut niveau et une syntaxe simple. Il est particulièrement apprécié des pédagogues qui y trouvent un langage où la syntaxe, séparée des mécanismes de bas niveau, permet une initiation aisée aux concepts de base de la programmation. C'est le langage le plus répandu dans le monde scientifique. Cet ouvrage présente tout ce que le mathématicien doit savoir sur ce langage : comment se le procurer, comment l'installer, l'utiliser, quelles sont ses fonctionnalités proprement mathématiques et quels problèmes sont susceptibles d'être résolus grâce à lui. Didactique et simple d'approche, il aborde donc conjointement la programmation, l'algorithmique et les applications mathématiques. Sans chercher une exhaustivité impossible, il montre comment la flexibilité et la versatilité du langage Python en font un très bon choix pour une utilisation scientifique. Des programmes d'accompagnement sont disponibles en téléchargement sur le site dunod.com.

mardi 14 février 2012

Tangram coeur


Les solutions sont ici

dimanche 12 février 2012

Dernier Tangente en Suisse

J'avais mentionné il y a deux ans l'arrivée du magazine Tangente dans les kiosques suisses. Malheureusement, le no 144 sera le dernier disponible en Suisse, suite à un "sabotage" du diffuseur Naville (je cite l'encart "à nos amis suisses", page 3) . Il n'y a donc plus qu'une solution pour nous désormais : s'abonner...

jeudi 9 février 2012

Wolfram|Alpha Pro

Sur le Wolfram Blog hier : une (longue) annonce pour Wolfram|Alpha Pro.

mardi 7 février 2012

Plongée au cœur du Web

Et si les secrets de la réussite des géants du Web, les Google, Facebook, Twitter ou autres Amazon trouvaient leur origine au XVIIIe siècle à Königsberg, en Allemagne ? A cette époque un mathématicien, Leonhard Euler, donna en effet naissance à une discipline devenue pilier de ces sites Internet : la théorie des graphes. Le problème d'Euler était de parcourir les quatre quartiers de sa ville sans emprunter deux fois l'un des sept ponts les reliant. Soit, sur un dessin, le fameux graphe, quatre sommets (ou noeuds) reliés par sept arêtes (ou liens). Les problèmes des vedettes du Web sont conceptuellement semblables, mais à une tout autre échelle : des milliards de "quartiers" (les pages Web, les profils, les clients...) et des milliards de "ponts" (les liens html, les "amis", les achats... reliant tout ce beau monde). La question est d'inventer les outils permettant de trouver la bonne information dans cette nuée, d'identifier des noeuds capitaux pour la bonne tenue de l'ensemble, de regrouper les gens par affinité, ou de recommander de nouveaux produits aux acheteurs. En outre, contrairement à Königsberg, cette "ville" possède des quartiers et des ponts qui bougent, naissent ou meurent...
Il y a une dizaine d'années, une nouvelle science est donc apparue, pour décrire et comprendre ces graphes ou réseaux de grandes tailles qui grossissaient sans plan préétabli : le Web et ses réseaux sociaux (Facebook, LinkedIn, Twitter, Viadeo...). Les mathématiciens et informaticiens y ont vu un terrain de jeu stimulant pour pousser leurs théories et calculs dans leurs retranchements. "Il y a de quoi attirer de jeunes talents qui, auparavant, se lançaient dans la finance", constate Henri Verdier, président du pôle de compétitivité Cap Digital. Il a justement cofondé une entreprise, MFG Labs, avec deux mathématiciens.
Les physiciens s'y sont intéressés, armés de leurs outils statistiques qui permettent de passer du microscopique (l'agitation des atomes d'un gaz, par exemple) au macroscopique (comme la température de ce gaz). Même les sciences humaines s'y sont mises, car pour un sociologue les réseaux sociaux existaient bien avant le Web. Certains d'entre eux avaient déjà dessiné des graphes, à la main, pour décrire les interactions entre différents membres de communautés familiales, religieuses, sportives... "Le Web est à la fois l'objet de la recherche et le moyen de la recherche", constate Dominique Cardon, sociologue au laboratoire Sense d'Orange Labs. Le mouvement est lancé. Des bases de données d'articles scientifiques, comme PubMed, recensent déjà plus de 200 articles ayant comme sujet Facebook, une centaine concernant Twitter, comme si ces sites étaient des gènes ou des particules. Des conférences et des revues spécialisées se créent.
En France, l'Institut Télécom vient de lancer une chaire "réseaux sociaux", soutenue par Danone ou La Poste. Une seconde sur la question des "données numériques" suivra très bientôt. Autour du médialab de Sciences Po sera développé un instrument à trois "bras", DIME-SHS (Données, infrastructure, méthodes d'enquêtes en sciences humaines et sociales), pour faire passer les sciences humaines à l'ère du numérique.

Jungle foisonnante

Outre des technologies pour effectuer des sondages via des tablettes, il y aura une plate-forme archivant et donnant accès à des études de terrain précédentes. Enfin, un service permettra aux chercheurs de construire et d'analyser leurs propres corpus issus de l'exploration des multiples "traces" laissées par les internautes sur le Web : billets de blogs, tweetts, liens hypertextes postés, statistiques d'usages... "Nous avons beaucoup de demandes de chercheurs pour de tels outils, mais d'autres sont encore réticents, notamment car la méthodologie n'est pas encore mûre, explique Paul Girard, l'un des ingénieurs de ce futur équipement au médialab de Sciences Po. Le Web ne dit pas tout."
Cette mode est affublée de plusieurs noms : science du Web, science des réseaux, humanités numériques... Peu importe, à peine née, ses résultats intéressent les fournisseurs commerciaux de services Web. Comment trier l'information au plus vite ? Comment identifier des communautés d'intérêts dans la jungle foisonnante du Web ? Comment se diffusent des informations ou des produits sur ces réseaux ?...
D'autres acteurs aimeraient aussi avoir ces réponses. Le secteur de la sécurité et de la défense rêve de surveiller les activités suspectes et de les anticiper. Les sondeurs (et hommes politiques) guettent toute percée sur la mesure de l'"état de l'opinion" sans recourir aux sondages. Le marketing s'y plonge pour repérer les profils influents et élaborer des campagnes efficaces... Le vieux rêve (ou cauchemar) d'une prédiction du futur refait surface. Où en est-on vraiment ? Le succès le plus évident de l'application de la théorie des graphes au Web est à chercher du côté du moteur de recherche Google. Alors que, dans les années 1990, des sites hiérarchisent à la main les informations dans de gigantesques annuaires reposant sur le contenu des sites et des pages référencées, Sergey Brin et Larry Page, les fondateurs de Google, innovent à partir de 1995. Leur méthode recense seulement les liens hypertextes qui permettent de passer d'une page à l'autre et en tire un classement, selon le "vieux" principe académique qui veut que plus une page est citée (via ces liens), plus elle est pertinente. C'est donc la structure même du réseau qui sert à son classement. Pas son contenu. "Cette rupture a périmé en un rien de temps les autres techniques", rappelle Dominique Cardon, qui constate également que cette suprématie est en passe d'être chamboulée.
Plus modestement que Google, d'autres sociétés utilisent la force de la structure sur le contenu pour se repérer dans la jungle des sites Web. Par exemple Linkfluence : cette start-up, dont Le Monde est partenaire, réalise ainsi des cartes de la blogosphère francophone. Plus de 13 500 sites sont regroupés en trois "continents", eux-mêmes sous-divisés en vingt territoires, etc. Le tout en analysant les liens entre eux et en vérifiant a posteriori les contenus.
Cette quête de "communautés" est une branche toujours très active de la recherche en mathématique et informatique pour l'automatiser. La méthode la plus efficace a été inventée par l'université de Louvain, en 2008, et appliquée avec succès sur de très grands graphes, comme les échanges téléphoniques belges et français (Le Monde du 17 décembre 2011) ou Twitter, LinkedIn... En quelques minutes, la masse informe de noeuds "explose" et devient une galaxie plus lisible avec des agrégats bien séparés. Reste à étudier les évolutions dans le temps de ces réseaux et à tenir compte des multi-appartenances des noeuds. Car, les sociologues le savent bien, un individu peut avoir plusieurs "identités".

Les nains et les géants

Cette structuration des graphes en communautés est l'une des propriétés remarquables mises en évidence par les pionniers américains de la fin des années 1990, tels Duncan Watts, Albert-Laszlo Barabasi, Jon Kleinberg... Il existe, dans ces grands réseaux, des régions denses avec beaucoup de liens et de grands espaces sans lien. Ils ont aussi réalisé que ces réseaux, malgré leur nombre important de noeuds et de liens, sont en fait de petite taille. Autrement dit qu'en quelques sauts, de lien en lien, on peut parcourir n'importe quel point du graphe. Selon Albert-Laszlo Barabasi, le Web tout entier aurait même un diamètre inférieur à vingt.
Plus récemment, les chercheurs de Facebook ont trouvé que le diamètre du réseau social était inférieur à cinq. Attention, petit diamètre ne signifie pas que nous soyons tous "amis". "Ce résultat sur Facebook n'a ni sens ni implication sociologique. En effet, une propriété caractéristique de ces réseaux dits petits-mondes est que le nombre de liens (comme le nombre d'amis sur Facebook) est réparti de manière aussi inéquitable entre les noeuds du réseau que le capital au sein d'une population : être à quatre poignées de main d'une personne qui a 3 000 amis déclarés ne la rend pas plus abordable que se trouver le nez devant sa porte close, explique Christophe Prieur, du laboratoire d'algorithmique du CNRS et de l'université Paris Diderot. Dans un monde (hypothétique) où la personne la plus éloignée de vous serait à six pas, ce six signifie l'infini."
L'une des lois du Web est en effet que la richesse va à la richesse et que, grosso modo, 20 % des noeuds possèdent 80 % des liens. Cette loi statistique que l'économiste italien Vilfredo Pareto a exhibée pour la richesse s'applique aussi à ces graphes. Dans ce cas, les notions de moyenne n'ont pas de sens. La "richesse" ne se répartit pas comme les notes d'une classe ou les tailles des individus le long d'une courbe en cloche. Au pays du Web, les nains et les géants ne sont pas rares.

David Larousserie - Le Monde.fr - 3.2.2012

1 2 >