Le blog-notes mathématique du coyote

On peut aussi suivre l'actualité des maths avec ces deux fils d'information Twitter en français :

• mathoscope
• mathsnews, d'Oliver Leguay

La musique est avant tout un plaisir. Plaisir de jouer, plaisir d'écouter. Sous ces joyeuses pratiques se cachent des fractales, des oscillations, des rythmes. Notre plaisir d'écoute est provoqué par l'équilibre entre le doux ronronnement et les surprises créées par les mélodies. La musique classique occidentale est connue pour être assez régulière voire prévisible.
N'allez pas demander aux grands compositeurs classiques, s'ils ont utilisés des théorèmes mathématiques pour plaire à nos oreilles. Tout ça n'est que le résultat statistique d'une volonté de plaire. On sait que le volume et les tonalités suivent des fractales, mais qu'en est-il des rythmes ? Trois chercheurs spécialisés en musique, psychologie, neurologie et enfin informatique ont disséqué les changements de rythme de 1788 mouvements de musiques provenant de 558 compositions classiques. Les résultats de cette étude regroupant ont été publiés le 6 mars dernier.
Ils ont mis en évidence qu'une écrasante majorité des rythmes obéissait à une loi mathématique, reliant la puissance à la fréquence. Il s'agit d'une loi de puissance de la forme : 1/(fⁿ), f étant la fréquence, n étant compris entre 0,5 et 1, selon les genres et les compositeurs. Coté genre, une symphonie sera proche d'un "n" à 1, alors que mazurka se verra doté d'un n vers 0,5. Les compositeurs ont eu aussi leur petite préférence. Les morceaux de Beethoven, Vivaldi sont parmi les plus prévisibles, à l'inverse de ceux de Mozart ou de Monteverdi.
Le fait que cette loi puisse être sous-jacente à des morceaux de musiques sur une période de plus de 400 ans montre que le rythmes tout comme la tonalité, participent à notre sensibilité musicale. Au delà de l'aspect statistique, ces chercheurs prouvent que les compositeurs, sans qu'ils ne s'en rendent compte, manipulent cette loi de façon à plaire à l'auditoire, mais aussi de façon à rendre unique leur œuvre. Finalement ces petits plaisirs auditifs ne seraient que mathématiques dans nos cerveaux d'homo-sapiens.

Pour aller plus loin : Daniel J. Levitina ,Parag Chordiab, Vinod Menonc. (2012) Musical rhythm spectra from Bach to Joplin obey a 1/f power law. PNAS March 6, 2012 vol. 109 no. 10 3716-3720

Source : Sur-la-Toile

La semaine passée, lors des élections présidentielles russes, la chaîne info pro-Poutine Russie-24 a montré que la participation dans la région de Rostov était de 146% : "Russie Unie" a récolté 58.99% des voix, le Parti communiste 32.96%, "Russie Juste" 23.74%, le Parti libéral-démocrate 19.41%, "Pomme" 9.32%, "Patriotes de Russie" 1,46% et "Juste cause" 0.59%. Total : 146.47%.

Source : skuky.net

Mon cours d'introduction à la théorie des graphes est disponible depuis peu au format papier.

Introduction à la théorie des graphes
Cahier CRM N° 6
Didier Müller
48 pages
2012


Le but de ce fascicule est d'initier les lycéens à la théorie des graphes. Il n'a pas pour ambition de présenter une théorie complète, mais de montrer comment les graphes peuvent être une méthode de résolution de problèmes intéressante.
Ce cours se veut accessible aux élèves de lycée, car il ne demande pratiquement pas de connaissances préalables. Il est découpé en deux parties principales : les graphes non orientés et les graphes orientés.
Comme la théorie des graphes utilise un jargon bien particulier, le début du cours comporte beaucoup de définitions. Un index et un lexique en fin de fascicule aideront l'élève à assimiler ces termes.

Les 75 exercices sont essentiellement de deux types :

• Des exercices théoriques sur les graphes, qui sont souvent des démonstrations assez simples, généralement par induction, ou par l'absurde ; il y a aussi des exercices de réflexion qui permettent de se rendre compte si on a bien compris un concept ou non.
• Des exercices pratiques où il peut être avantageux d'utiliser des graphes pour modéliser et résoudre un problème.

Une version papier (sans les corrigés) peut être commandée sur le site de la diffusion Pahud. Ce fascicule est aussi disponible en ligne gratuitement, ainsi qu'un second cahier contenant les solutions détaillées des exercices.

Une petite erreur quand même : l'intégrale de sin(x) est -cos(x)

Source : viedumastercs.wordpress.com

Source : Les céréales du Dimanche matin

Actuellement en kiosque, ce numéro hors-série de La Recherche, réalisé avec le magazine Tangente, vous propose de décrypter l'univers électoral à la lumière des mathématiques.

En cette période de campagne pour l’élection présidentielle française, les élections deviennent un sujet sérieux, présent dans tous les médias. Mieux vaut parfois éviter de l’aborder en famille, sous peine de créer quelques tensions… Prenant la tendance à contre-pied, La Recherche et Tangente ont choisi d’en faire un sujet de divertissement ludique en vous proposant ce numéro hors-série « Jeux mathématiques », spécial élections dont voici un aperçu.

Ce matin, en classe.
Moi : "Quelle est la particularité de la droite y = ax ?"
Une élève : "C'est une parabole !"

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.

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.

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

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.

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.

Les solutions sont ici

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

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

Gary McGuire, mathématicien irlandais, a résolu une énigme datant de plus de dix ans, en découvrant le plus petit sudoku qui existe. Pour cela, il a fallu plus de 7 millions d'heures de calculs sur un superordinateur.
Il n'existe que trois types de sudokus : ceux n'ont qu'une unique solution, ceux qui ont plusieurs solutions et ceux qui n'ont aucune solution. Les premiers sont intéressants, et les autres sont terriblement décevants et ne méritent pas le nom de sudoku (étymologiquement, "chiffre unique").
En général, moins un soduku possède de cases pré-remplies, plus sa complétion sera difficile. De tous les sudokus connus, les plus dépouillés ne comportent que 17 chiffres révélés. Peut-on trouver un sudoku à 16 chiffres ? La question a longtemps été ouverte, jusqu'au 1er janvier 2012. Gary McGuire et deux collaborateurs ont regardé attentivement les 6.7 milliers de milliards de milliards de grilles complètes existantes afin de voir s'il était possible de leur retirer plus de 64 chiffres sans les dénaturer. Leur conclusion : il n'existe pas de sudoku à 16 chiffres.

Pour en savoir plus, lire l'article Pendant ce temps, chez les Sudokus sur l'excellent blog "Choux Romanesco, vache qui rit et intégrales curvilignes".

Les hommes se comportent le mieux qu'ils peuvent lorsque des femmes séduisantes sont susceptibles de les regarder. Les femmes ne modifient pas leur comportement (en moyenne) quand des hommes les regardent par contre. On a réalisé deux expériences. La première a fait jouer 65 hommes et 65 femmes d'âge moyen de 21 ans à un jeu anonyme de coopération : ce jeu permet de faire un don d'argent à une groupe via un ordinateur. Le don est un acte altruiste : les autres joueurs en bénéficient tandis que le donneur ne reçoit rien en retour.
Les participants ne savaient pas quels étaient les autres personnes avec qui ils jouaient. Ils pouvaient être vus par deux personne, l'une du même sexe et l'autre du sexe opposé, et qui étaient des complices des chercheurs : un « beau gosse » et un joli brin de fille. On a ainsi remarqué que les hommes accroissaient leurs bonnes actions s'ils se sentent observés par le sexe opposé et les femmes pas du tout, quel que fut l'observateur.
La deuxième expérience a consisté à réaliser des groupes d'hommes. On leur demandait de faire un certain nombre de donations. Ces donations s'accroissaient lors d'une observation par une jolie femme : il y avait clairement une « compétition » de donations. Le chercheur Dr Iredale responsable de l'étude affirme que cette recherche montre que les bonnes actions s'accroissent lorsqu'il y a une opportunité de copulation (sic). L'altruisme masculin serait un peu la queue du paon dans notre espèce.

Sources : Sur-la-Toile, Science Daily