Overblog Suivre ce blog
Administration Créer mon blog
16 janvier 2014 4 16 /01 /janvier /2014 10:42

 

Le problème des sept ponts de Königsberg est un problème mathématique connu pour être à l'origine de la théorie des graphes. Résolu par Leonhard Euler, il se présente de la façon suivante :


Konigsberg bridges.png 7 bridges.svg Konigsburg graph.svg


La ville de Königsberg (aujourd'hui Kaliningrad) est construite autour de deux îles situées sur le Pregel et reliées entre elles par un pont. Six autres ponts relient les rives de la rivière à l'une ou l'autre des deux îles, comme représentés sur le plan ci-dessus. Le problème consiste à déterminer s'il existe ou non une promenade dans les rues de Königsberg permettant, à partir d'un point de départ au choix, de passer une et une seule fois par chaque pont, et de revenir à son point de départ, étant entendu qu'on ne peut traverser le Pregel qu'en passant sur les ponts.

Résolution du problème[modifier | modifier le code]

Une telle promenade n'existe pas, et c'est Euler qui donna la solution de ce problème en caractérisant les graphes que l'on appelle aujourd'hui « eulériens » en référence à l'illustre mathématicien, à l'aide d'un théorème dont la démonstration rigoureuse ne fut en fait publiée par Carl Hierholzer qu'en 1873.

Ce problème n'a sous cette forme non généralisée qu'un intérêt historique, car pour ce cas, il est assez intuitif de démontrer que la promenade demandée n'existe pas. Pour voir cela, il suffit d'associer un graphe à la ville comme dans la figure ci-dessus et de supposer que la promenade recherchée existe. On peut alors, à partir de la promenade, ordonner les sept arêtes du graphe de façon à ce que deux arêtes consécutives par rapport à notre ordre soient adjacentes dans le graphe (en considérant que la dernière et la première arête sont consécutives, puisqu'il y a retour au point de départ).

Ainsi tout sommet du graphe est-il nécessairement incident à un nombre pair d'arêtes (puisque s'il est incident à une arête il est aussi incident à l'arête précédente ou qui lui succède dans l'ordre). Mais le graphe a des sommets qui sont incidents à trois arêtes, d'où l'impossibilité.

Notons que même si on renonce à exiger le retour au point de départ, une promenade traversant une et une seule fois chaque pont n'existe pas. Elle existerait si au plus deux sommets du graphe, correspondant aux points à choisir respectivement comme départ et arrivée, étaient incidents à un nombre impair d'arêtes, or les sommets du graphe des ponts de Königsberg sont tous les quatre dans ce cas ; la promenade est donc impossible. Il suffirait cependant de supprimer ou de rajouter un pont quelconque pour que le graphe modifié permette des promenades tous ponts sans retour (seuls deux sommets restant d'incidence impaire). Et ce sont au moins deux ponts, bien choisis, qu'il faudrait ajouter ou retirer pour permettre la promenade avec retour initialement cherchée.

On peut donner à ce problème une solution moins théorique. Il suffit de remarquer qu'il y a quatre zones, les deux rives et les deux îles, chacune reliée aux autres par un nombre impair de ponts. Ce nombre impair fait que si l'on entre dans une région R, on doit y rester. Or on ne peut finir sa promenade dans plus d'une de ces quatre régions.

MS XibniY : LE BLOG DE MOHAMED SALEH IBNI OUMAR - dans INFORMATIQUE
commenter cet article
16 janvier 2014 4 16 /01 /janvier /2014 10:37

 

                                                File:Salesman.PNG


Le problème du voyageur de commerce, étudié depuis le 19e siècle, est l’un des plus connus dans le domaine de la recherche opérationnelle. Jouez à trouver le meilleur parcours possible... et découvrez différentes méthodes informatiques proposées pour résoudre ce problème.

C'est déjà sous forme de jeu que William Rowan Hamilton a posé pour la première fois ce problème, dès 1859. Sous sa forme la plus classique, son énoncé est le suivant : « Un voyageur de commerce doit visiter une et une seule fois un nombre fini de villes et revenir à son point d’origine. Trouvez l’ordre de visite des villes qui minimise la distance totale parcourue par le voyageur ». Ce problème d’optimisation combinatoire appartient à la classe des problèmes NP-Complets definition.

Les domaines d’application sont nombreux : problèmes de logistique, de transport aussi bien de marchandises que de personnes, et plus largement toutes sortes de problèmes d'ordonnancement. Certains problèmes rencontrés dans l'industrie se modélisent sous la forme d’un problème de voyageur de commerce, comme l'optimisation de trajectoires de machines outils : comment percer plusieurs points sur une carte électronique le plus vite possible ?

Comme illustration de ce problème, nous vous proposons le jeu ci-dessous. Le but ? Trouver le parcours du voyageur pour qu'il visite toutes les villes de France affichées, en respectant la durée maximale du voyage, exprimée en heures. Le nombre de villes à visiter dépend de la difficulté choisie. En mode deux joueurs, si les parcours trouvés ont la même durée, le gagnant sera celui qui aura trouvé la solution le plus rapidement.

MS XibniY : LE BLOG DE MOHAMED SALEH IBNI OUMAR - dans INFORMATIQUE
commenter cet article
9 décembre 2013 1 09 /12 /décembre /2013 10:19

 

 

L’informatique entretient avec la cryptologie – l’art du code secret – une relation passionnelle. A la fois parce les ordinateurs sont apparus comme des machines extrêmement efficaces pour casser des codes secrets, et aussi évidemment créer des codes. Mais aussi parce que des informations tous les jours plus importantes circulant aujourd’hui sur les réseaux informatiques, elles nécessitent un art du cryptage toujours plus complexe.


 
 
 

 

Au fond, au hold-up numérique et décentralisé ayant eu lieu il y a 15 jours à votre trajet quotidien avec votre passe Navigo, de Wikileaks à Paypal, de votre déclaration d’impôt en ligne (qu’il faut remplir avant ce soir), à votre dossier médical…. tout est affaire de cryptologie, c’est-à-dire de confidentialité, d’authentification. Mais quels sont les liens théoriques entre informatique et cryptologie ? Comment l’une et l’autre des disciplines évoluent conjointement depuis 70 ans ? Où en est-on de la cryptographie aujourd’hui ? Quelles sont les perspectives d’avenir ?

  • Philippe Guillot,Maître de conférences en mathématique à l’Université de Paris 8 (Saint-Denis). Son objet de recherche est la cryptologie, et il est l’auteur de plusieurs ouvrages sur la question. Le dernier vient de sortir aux éditions Edp-sciences et s’intitule : La cryptologie, l’art des codes secrets.  

 

MS XibniY : LE BLOG DE MOHAMED SALEH IBNI OUMAR - dans INFORMATIQUE
commenter cet article
3 mars 2013 7 03 /03 /mars /2013 21:32

 

 

Isis Truck a commencé sa recherche dans le groupe MODECO (Modélisation multi-agents dans les systèmes DEcisionnels et COopératifs en environnement incertain) à Reims et a obtenu une thèse de doctorat en informatique de l’université de Reims en 2002. Elle a rejoint le LIASD (Laboratoire d’Intelligence Artificielle de Saint-Denis) de l’université Paris 8 en 2003 en tant que maître de conférences. Ses centres d’intérêts se situent surtout dans le champ de la représentation des connaissances en milieu incertain et imprécis, en particulier en utilisant des concepts de logique floue et logique multi-valuée. Parallèlement, elle travaille aussi dans le domaine de l’informatique musicale.

Avec Alain Bonardi, nous développons un projet d’assistant virtuel de metteur en scène. De plus amples détails sur ce travail sont disponibles ici.

Concernant la problématique de visualisation sonore, il nous semble évident que des méthodes issues de la logique floue sont tout à fait adéquates pour représenter de façon pertinente et intelligente du son en général. La théorie des sous-ensembles flous qui englobe la logique floue, inventée par Lotfi Zadeh dans les années 1965 a été imaginée pour modéliser mathématiquement des concepts typiquement humains, typiquement non modélisables a priori par des formules classiques. Les dernières avancées proposées par Zadeh lui-même sont de modéliser mathématiquement la perception humaine. La perception des sons en fait donc partie. Il évoque notamment la théorie computationnelle des perceptions, la théorie des protoformes (notion de résumé de données), etc. Un de ses derniers articles est disponible sur le site de Science Direct.

Plus concrètement, la représentation du son avec divers outils est une question que beaucoup de chercheurs ont déjà fouillée. Par exemple, l’utilisation de la couleur, domaine où la perception est reine, a été assez largement utilisée pour représenter les signaux sonores (voir Golan Levin,Kostas Giannakis, Vincent Lesbros, etc.). La couleur se prête assez bien à un tel type de représentation car elle est fonction de la perception humaine, comme les ondes sonores. Elle peut donc, si elle est utilisée pertinemment, se calquer sur la perception sonore. Ici aussi, la logique floue peut avoir un intérêt en modélisant d’une part la perception des couleurs, et, du même coup, la perception sonore.

Bibliographie

A propos de la notion d’émotion évoquée plus haut, Lola Canamero travaille sur les comportements intelligents adaptatifs au travers d’agents artificiels autonomes. En particulier, elle s’intéresse au rôle que les phénomènes émotionnels jouent dans de tels systèmes. On pourra lire, par exemple : 
- Cañamero, L.D. 2003. Designing Emotions for Activity Selection in Autonomous Agents. In R. Trappl, P. Petta, S. Payr, eds., Emotions in Humans and Artifacts, pp. 115-148. Cambridge, MA : The MIT Press. 
- http://homepages.feis.herts.ac.uk/ comqlc/

- http://www.emotion-research.net/

A propos de l’assistant virtuel, d’autres travaux existent dans ce domaine. On peut citer notamment l’équipe de Friberg qui propose un système qui analyse la voix et les mouvements de joueurs dans le cadre d’un jeu interactif. Ce sont les mouvements et voix des joueurs qui constituent les valeurs en entrée dans le jeu. (voir http://www.speech.kth.se/music/projects/Ghostgame/)

3 septembre 2012 1 03 /09 /septembre /2012 17:15

 

 

Isis Truck

Maître de conférences en informatique, Chargée de mission à la taxe d'apprentissage

Université Paris 8

3 septembre 2012 1 03 /09 /septembre /2012 17:07

 


Isis Truck

Maître de conférences en informatique, Chargée de mission à la taxe d'apprentissage

Université Paris 8

 


 

L’association



Cap Digital est le pôle de compétitivité de la filière des contenus et services numériques. Ses 9 communautés de domaine regroupent plus de 700 adhérents : 620 PME, 20 grands groupes, 50 établissements publics, écoles, et universités ainsi que 10 investisseurs en capital.

Cap Digital œuvre à faire de la Région Île-de-France l’une des références mondiales du numérique, tant d’un point de vue industriel que stratégique. Le développement de la R&D, la croissance des entreprises, la mise en réseau de ses adhérents et leur promotion à l’international sont autant de missions pour soutenir la créativité et la compétitivité de ce secteur industriel qui représente à lui seul un marché mondial de 3000 milliards d’euros.

Cap Digital organise le festival Futur en Seine, rendez-vous mondial annuel des forces vives de la création, de l’innovation et de l’économie numérique désireuse d’exposer, rencontrer, débattre, d’exprimer et de partager une vision du futur avec le grand public.

www.capdigital.com
info@capdigital.com

Livret de présentation Cap Digital

Téléchargez les Statuts de Cap Digital

Pour prendre en compte la croissance du Pôle et celle du nombre de Communautés, Cap Digital a réorganisé sa gouvernance.

Notre expertise sectorielle s’exprime au travers d’une organisation comprenant des commissions thématiques, des communautés de domaine et des experts. Ces  entités sont perméables et malléables. Un membre d’une commission peut être aussi membre d’une communauté et expert Cap Digital. L’objectif de cette nouvelle structuration est de multiplier les échanges entre communautés de domaine et de laisser le champ libre aux évolutions nécessaires.

La gouvernance

Président : Henri VERDIER, Fondateur de MFG Labs

Vices présidents :

* Pierre Danet, Directeur chargé de la Coordination Informatique du Groupe Hachette Livre

* Stéphane Distinguin, Fondateur FaberNovel, concepteur de la Cantine

* Philippe Herbert, Associé chargé des investissements dans les secteurs Internet et Mobile de Banexi Ventures Partners

* Francis Jutand, Directeur scientifique de l’Institut Mines TELECOM

* Catherine Lucet, Directrice pôle éducation EDITIS

* Olivier Muron, Directeur des Relations Institutionnelles d’Orange Labs R&D (Groupe FRANCE TELECOM)

Trésorier : Olivier Muron, Directeur des Relations Institutionnelles d’Orange Labs R&D (Groupe FRANCE TELECOM)

Les membres du Conseil d’ Administration (par ordre alphabétique):
Bruno AIDAN, Alcatel-Lucent Pascal BURON, FICAM Daniel CANEPA, Préfecture d’Ile-de-France Serge DAHAN, APROGED Pierre DANET, Hachette Livre Thierry DE VULPILLIERES, Microsoft Stéphane DISTINGUIN, Faber Novel  Olivier DRESSAYRE, La Poste Gérard EUDE, Conseil Général de Seine et Marne Claude FARGE, Universcience Lydie FENECH, Pôle Média Grand Paris  Guy GOUREVITCH,  G&G Entreprises et Conseil Philippe HERBERT, Banexi Ventures Partners Didier HUCK, Technicolor Francis JUTAND, Institut Mines Telecom Jean-Marc LABAT, Université Pierre et Marie Curie Olivier LANDAU, Sofrecom  Catherine LUCET, EDITIS  Jean-Louis MISSIKA, Conseil Général de Paris  Sandrine MURCIA, Silicon Sentier Olivier MURON, Orange Stéphane NATKIN, CNAM Adeline NAZARENKO, Université Paris 13 Catherine PEYROT, CAPITAL GAMES Jean-Paul PLANCHOU, Conseil Régional d’Ile-de-France Pascal POPELIN, Conseil Général de Seine Saint Denis Olga RODIONOFF, Université Paris 8 Isabelle RYL, INRIA Julien SCHNEIDER, Euromedia Françoise SOULIE-FOGELMAN, KXEN Jean-Pierre SPILBAUER, Conseil Général du Val de Marne Philippe SUEUR, Conseil Général du Val d’Oise Daniel TERUGGI, INA Frédéric VACHER, Administrateur 3DS Henri VERDIER, MFG Labs.

Le Bureau Exécutif est composé de 17 membres, nommés par le Conseil d’administration, et de 4 membres invités
Bruno AIDAN Alcatel-Lucent Christine BALAGUE, Institut Mines Telecom Sud Paris Hervé CHATEAUNEUF, FICAM  Patrick COCQUET, Cap Digital Pierre DANET, Hachette-Livre Lydie FENECH, Pôle Audiovisuel Cinéma Multimédia du Nord Parisien Jean-Louis FRECHIN, ENSCI Martine GARNET-RIZET, Vecsys Vincent GOLLAIN, ARD IDF  Francis JUTAND, Institut Mines Telecom Philippe LETELLIER, Institut Telecom Jean-François MARCOTORCHINO, Thales Land&Joint Systems Benoit MAUJEAN, Mikros Olivier MURON, Orange Labs R&D Stéphane NATKIN, CNAM Frédéric ORU, Silicon Sentier Catherine PEYROT, Capital Games Jean-Charles POMEROL, UPMC Nicolas ROSE, XAnge Private Equity (représentant du collège des investisseurs)  Isis TRUCK, UFR 6 Henri VERDIER, Président de Cap Digital.

Les commissions thématiques :
Il existe trois Commissions : Connaissances, Contenus et Services, en charge de coordonner les Communautés de Domaine.
Les commissions thématiques orchestrent le processus d’expertise des projets et désignent les experts Cap Digital. Ces derniers peuvent être membres d’une commission thématique et/ou d’une communauté de domaine. Les commissions synthétisent également la stratégie fixées par les communautés de domaine.

Commission thématique Services

Présidente : Christine BALAGUE – Institut Mines-Telecom
Adjointe : Frédérique LEGRAND – Orange ♦ Adjoint : Louis MONTAGNE – Bearstech
Membres : Jérôme ADAM – Easy-Life ♦ Pierre-Antoine CHARDEL – Telecom Ecole de Management ♦ Olivier CHOURAKI – Mobiluck ♦ Nicolas COLIN – Cause Builder ♦ Hugues DE MAZANCOURT – Lingway ♦ Dana DIMINESCU – ParisTech ♦ Gianbeppi FORTIS – Solutions 30 ♦ Marie GAILLARD – Consultante Education ♦ Laurent GILLE – Institut Mines-Télécom ♦ Daniel KAPLAN – FING ♦ Petra KOUDELKOVA – Aldebaran ♦ Dominique LAOUSSE – SNCF ♦ Jerôme LELEU – Groupe M ♦ Vincent PUIG – IRI ♦ David RAICHMAN – Ogilvy Digital Lab Paris ♦ Manuel ZACLAD – Cnam-Dicen
En savoir plus sur la Commission thématique Services

Commission thématique Contenus

Président : Benoit MAUJEAN -  Mikros Image
Adjointe : Françoise PRETEUX – Telecom SudParis ♦ Adjoint : Hugues VINET – IRCAM ♦ Adjoint : Emmanuel ZAZA – Tetraedge Games
Membres : Olivier AMATO -  Smart Jog ♦ Luc AUDRAIN – Hachette Livre ♦ Thomas BAUDEL -  ILOG/IBM ♦ Venceslas BIRI – Université Marne La Vallée  ♦ Morgan BOUCHET – Orange Content Division ♦ Vincent BOYER – Paris 8 ♦ Stéphan BRUNESSAUX – EADS ♦ Vincent CASTAIGNET – Musicovery ♦ Jean Yves DONNART – Thales ♦ Didier GIRAUD -  INA  ♦ Cedric GUIARD – ADN ♦ Baptiste HEYNEMANN -  CNC ♦ Eric LEGUAY – Gobelins ♦ Eric MAHE – Indépendant ♦ Mathieu PARMENTIER – France Television ♦ Jean PONCE – INRIA ♦ Michel REILHAC – Arte ♦ Philippe RIGAUX – Cnam ♦ Jean-Louis VERLAINE – Black Sheep Studio.
En savoir plus sur les membres de la Commission thématique Contenus.

Commission thématique Connaissance

Présidente : Martine GARNIER-RIZET – Vecsys
Adjointe : Bernadette BOUCHON-MEUNIER – Paris 6 ♦ Adjoint : Patrick CONSTANT – Pertimm
Membres : Patrick ALBERT – IBM ♦ Alain BONARDI – Paris 8 ♦ Nozha BOUJEMAA – INRIA Roc ♦ Jean DELAHOUSSE – Consultant ♦ Olivier GALIBERT – LNE ♦ Catherine GOUTTAS – Thales ♦ Gregory GREFENSTETTE – 3DS Exalead ♦ Charles HUOT – Temis ♦ Jean-François LAVIGNON – BULL ♦ Bénédicte LEGRAND – LIP6 ♦ Denis MARRAUD – EADS  ♦ Michel PLU – Orange ♦ Philippe PORTELLI- Université de Strasbourg ♦ Gaelle RECOURCE – Kwaga ♦ Sophie ROSSET – Limsi-CNRS ♦ Marc SALLIERES – Altic ♦ Belen SOLANO – CEA List ♦ Françoise SOULIE FOGELMAN – KXEN ♦ Charles TIJUS – Lutin ♦ Claire WAAST-RICHARD – EDF R&D.
En savoir plus sur les membres de la Commission thématique Connaissance.

Les experts Cap Digital :
Accédez à la liste des experts
Comment devenir expert ?

Les communautés de domaine:
Jeu vidéo, Design numérique, Culture Presse Media, Image Son et Interactivité, Robotique et objets communicants, Éducation et Formation numérique, Services et usages Mobiles, Ingénierie des Connaissances, Logiciel libre coopération et nouveaux modèles.

L’équipe opérationnelle :
L’équipe opérationnelle est dirigée par Patrick Cocquet, Délégué Général de Cap Digital.
14 mai 2012 1 14 /05 /mai /2012 09:13

 

Abstract

A correct reasoning with an elementary geometry problem is often closely linked to an intelligent reading of the figure associated to the problem. 

This work is the first part of a software helping reading a figure. The program, such as it is written at present, is able to detect circles and lines, and also some simple 

geometric configurations in an image. This paper handles notably with the difficulties we had to surmount in order to 

carry this work to a successful conclusion. 

Keywords : geometry problem, figure, objects detection, Hough Transform.

IMPU IMPU

5 avril 2012 4 05 /04 /avril /2012 12:53
LCP-nets: A linguistic approach for non-functional preferences in a semantic SOA environment
Type of publication: Article
Citation: ChTM10
Journal: Journal of Universal Computer Science
Volume: 16
Number: 1
Year: 2010
Pages: 198-217
Note: MoVe INT LIP6
URL: http://www.jucs.org/jucs_16_1/...
Keywords:  
Authors Châtel, Pierre
Truck, Isis
Malenfant, Jacques
Added by: [UNK]
5 avril 2012 4 05 /04 /avril /2012 12:51

 

Resources (URL, PDF, PS...)

URL: http://dblp.uni-trier.de/db/journals/jucs/jucs16.html#ChatelTM10

BibTeX record

@article{journals/jucs/ChatelTM10,

  added-at = {2010-07-21T15:46:33.000+0200},

  author = {Châtel, Pierre and Truck, Isis and Malenfant, Jacques},

  biburl = {http://www.bibsonomy.org/bibtex/201fa1d7fb955da8ff7fdf81e74640e00/dblp},

  date = {2010-04-27},

  ee = {http://www.jucs.org/jucs_16_1/lcp_nets_a_linguistic},

  interhash = {be2a7b8e6b42f1038014431db184139e},

  intrahash = {01fa1d7fb955da8ff7fdf81e74640e00},

  journal = {J. UCS},

  keywords = {dblp},

  number = 1,

  pages = {198-217},

  timestamp = {2010-07-21T15:46:33.000+0200},

  title = {LCP-Nets: A Linguistic Approach for Non-functional Preferences in a Semantic SOA Environment.},

  url = {http://dblp.uni-trier.de/db/journals/jucs/jucs16.html#ChatelTM10},

  volume = 16,

  year = 2010

}

20 mars 2012 2 20 /03 /mars /2012 00:06

Cours capteurs Intelligents

 

 

Définitioncapteur-intelligent.png

 

Le capteur intelligent correspond principalement à l'intégration dans le corps du capteur d'un organe de calcul interne (microprocesseur, micro-contrôleur), d'un système de conditionnement du signal (programmable ou contrôlé) et d'une interface de communication... Plus largement, le concept de capteur intelligent se décompose ainsi (Selon le livre "Capteurs intelligents et méthodologie d'évaluation") :

 

  • un ou plusieurs transducteur(s)
  • des conditionneurs spécifiques
  • d'une mémoire
  • d'une alimentation
  • d'un organe intelligent interne permettant un traitement local et l'élaboration d'un signal numérique
  • d'une interface de communication.

 

Le capteur intelligent est un dispositif communiquant : cette notion de communication constitue probablement l'élément clé du concept de capteur intelligent. Reste que pour qu'un capteur puisse communiquer, il est nécessaire de définir un protocole de communication. Ce dernier réside dans une puce implantée dans chaque capteur et permet aux différents organes d'être compris par toutes les entités du système de communication. Toutefois, aussi paradoxal que cela puisse paraître, il n'existe pas réellement de standard de communication aujourd'hui : les protocoles sont disparates d'un constructeur à l'autre, si bien que les équipements d'origines différentes ne peuvent communiquer.

  • : XibniY : BLOG DE MOHAMED SALEH IBNI OUMAR
  • XibniY : BLOG DE MOHAMED SALEH IBNI OUMAR
  • : Blog dédié à l'Histoire, à la Beauté et à l'Enseignement des Mathématiques. Contact: ioms001@yahoo.fr
  • Contact


PLAQUEIBNI.jpg

"Le Professeur Ibni est un mathématicien tchadien de renom, Ancien Directeur du CNAR (CNRS tchadien), Ancien Recteur et Ancien Ministre de l'Enseignement Supérieur et de la Recherche, il avait initié plusieurs jumelages avec des Universités Etrangères, au service de l’enseignement des sciences dans son pays et en Afrique plus généralement"

PRIXIBNI.jpg
Candidature au Prix Ibni