Journal Magic: the Gathering, le problème de l'arrêt, et une inférence un peu rapide

Posté par  . Licence CC By‑SA.
Étiquettes :
42
10
mai
2019

Slate m'offre, dans un article récent, le moyen de concilier mes trois passions : l'informatique théorique, le jeu de société, et me moquer des journalistes.

Ça commence donc par un article plutôt banal sur arXiv : les auteurs ont, à partir de deux decks très spécifiques (mais légaux selon les règles du jeu de société Magic), réussi à créer une machine de Turing. Machine de Turing un peu particulière puisqu'elle mène à la victoire du joueur A (…)

Journal OpenJDK JEP 180: HashMap, collisions & attaques par la complexité

Posté par  . Licence CC By‑SA.
Étiquettes :
84
4
mai
2014
Ce journal a été promu en dépêche : OpenJDK JEP 180: HashMap, collisions & attaques par la complexité.

Dans ce journal, je vais parler de la JEP 180 d'OpenJDK 8 qui propose une solution intéressante aux problèmes d'attaques sur la complexité que rencontrent les tables de hachage.

On a déjà parlé de ce sujet ici même à plusieurs reprises. Je vais cependant rapidement représenter le problème et l'évolution des discutions. Le lecteur averti sur le sujet ira directement au dernier paragraphe pour voir la proposition de la JEP 180.

Présentation des tables de hachage

Une table de (…)

Journal P=NP démontré ?

Posté par  (site web personnel) . Licence CC By‑SA.
Étiquettes :
20
30
mai
2013

Xinwen Jiang a publié sur le site de la Cornell University un papier nommé «A Polynomial Time Algorithm for the Hamilton Circuit Problem» qui impliquerait que P=NP est vrai.

«In this paper, we introduce a so-called Multistage graph Simple Path (MSP) problem and show that the Hamilton Circuit (HC) problem can be polynomially reducible to the MSP problem. To solve the MSP problem, we propose a polynomial algorithm and prove its NP-completeness. Our result implies NP=P.»

Pour mémoire le lien (…)

Le colonel Moutarde, sur la table (de hachage), avec un livre de maths

Posté par  . Édité par baud123, claudex, Benoît Sibaud et patrick_g. Modéré par Malicia. Licence CC By‑SA.
Étiquettes :
78
30
déc.
2011
Sécurité

Quand des chercheurs en informatique font de la théorie, certains écoutent, comme les développeurs de Perl. D'autres dorment au fond de la classe : cette fois, le bonnet d'âne est pour PHP, Python, V8 (JavaScript par Google, qui sert par exemple dans node.js), Ruby (sauf CRuby), de nombreux serveurs d'applications en Java, mais aussi ASP.NET. Ils ont dû se réveiller brutalement mercredi, lors d'une présentation d'Alexander Klink et Julian Wälde au Chaos Communication Congress montrant comment saturer très simplement un serveur grâce à une attaque basée sur la complexité algorithmique.