• laboratoire d'informatique et des systemes complexes
  • laboratoire d'informatique et des systemes complexes
  • ecole pratique des hautes etudes
  • association pretopologics
  • librairie java pretopologie

Laboratoire d'Informatique et des Systèmes Complexes

Ivan :: LAVALLEE



Ivan LAVALLÉE, Professeur

Laboratoire LAISC
EPHE,
41 rue Gay Lussac
75005 Paris
Tel : +33 (0)1 44 10 78 85
Fax : +33 (0)1 43 26 88 16
Situation Professeur.

Recherche Recherche Opérationnelle : élève de R. Faure, j’ai commencé mon activité de recherche en Recherche Opérationnelle. Toute mon activité ultérieure en matière de recherche a été sous-tendue par le souci d’optimisation qui a guidé ma carrière de recherche. En R.O., qu’il s’agisse de la R.O. elle-même, (R. Faure lui-même a présenté un résultat d’optimisation que j’avais obtenu en R.O. ) ; Algorithmique : domaine dans lequel j’ai obtenu deux résultats très remarqués: sur la reconnaissance de structures particulières en réseau d'une part, et d'autre part, sur le problème dit des tours de Hanoï, j’ai obtenu un résultat algorithmique inattendu montrant que le problème n’est pas de caractère récursif ce qui a conduit à un travail de fond sur la récursivité en programmation et une thèse ;

Parallélisme, distribué : cherchant toujours à optimiser, j’ai identifié le parallélisme en informatique comme étant un thème majeur de développement. De même, le développement des réseaux m’a conduit à promouvoir l’algorithmique distribuée de contrôle sur quoi j’ai obtenu une thèse de doctorat d’état en 1986 au LRI à Orsay. Je suis parti de l’idée qu’il ne fallait plus penser processeur par processeur pour établir un système, mais globalement, considérant qu’il s’agissait de structurer un ensemble d’objets communicants, en les considérant tous égaux, sans qu’il y ait a priori d’entité (i.e. processus) privilégiée, et qu’il fallait s’intéresser aux performances, ce qui m’a conduit à avancer la structure en arbre de contrôle sous-jacente alors que les structures qui existaient étaient basées sur des anneaux. J’ai par conséquent, produit une série d’algorithmes distribués pour obtenir une telle structure d’arbre suivant les contextes et hypothèses propres au système, en d’une part minimisant le nombre de messages échangés, d’autre part maximisant autant que faire se peut le parallélisme, tant temporel que physique. J’ai par la suite cherché à affaiblir les conditions dans lesquelles ces algorithmes étaient amenés à opérer, ce qui m’a conduit à concevoir un algorithme distribué à connaissance minimale probabiliste ;

Récursivité : dans la même période, j’ai cherché à généraliser mon résultat sur les tours de Hanoï, qui m’a permis de donner une version itérative de la multiplication de Straßen .

Récursivité & parallélisme :tout en continuant en algorithmique distribuée, j’ai utilisé les concepts avancés dans la dérécursivation des algorithmes pour les paralléliser. Cette volonté de constamment optimiser m’a conduit à m’intéresser à la maîtrise de la complexité et des systèmes complexes, les systèmes distribués étant un bon modèle de systèmes complexes ;

Complexité: ces différents thèmes m’ont conduit, à la fois en enseignement et en recherche à m’intéresser à la complexité, tant à la complexité des algorithmes en tant que telle (Turing- Lévine ;Cook), qu’à "la Kolmogorov".

Publications

Publications, ouvrages et conférences Ouvrages individuels et collectifs

  • Livre Exercices corrigés de Recherche Opérationnelle, par le groupe ROSEAUX, édité chez Masson (10 co-auteurs) 14,
    • Tome 1 graphes : leurs usages, leurs algorithmes ;
    • Tome 2 Phénomènes aléatoires en recherche opérationnelle;
    • Tome 3 Programmation linéaire et extensions ; problèmes classiques.
  • Livre Algorithmique parallèle et distribuée Hermès, Paris 1990;
  • Livre L’Homme et les techniques Messidor, Paris 1991 ;
  • Livre Sur des principes fondamentaux de l’algorithmique distribuée -OPOPAC- en commun avec Yakup Paker du Queen Mary and Westfield College de Londres, Hermès, Paris 1993 ;
  • Livre Protocoles, et programmation dans les réseaux, Hermès, Paris 1995 ;
  • Livre Cyber Révolution, éditions du Temps des Cerises, Pantin 2002 ;
  • Livre OPODIS’06, Elsevier (avec Shvartsman Alexander 15) 2007 ;
  • Livre Complexité et algorithmique avancée (une introduction), éditions Hermann, Paris février 2008 ;
  • Special Issue of OPODIS 2006 TCS 2009 ; Livre Complexité et algorithmique avancée (une introduction), éditions Hermann, Paris février 2009, deuxième édition revue et augmentée.

Revues et publications à comité de lecture international

  • Un algorithme de détermination de couvertures minimales Publications scientifiques d’IBM, IBM-service 161, étude 141 -1972 ;
  • Un algorithme de détermination de couvertures de cardinal minimal, RAIRO 7ième année, R-2, 1973, p. 17-28 ;
  • Reconnaissance du caractère distributif d’un treillis fini, Comptes Rendus Académie des Sciences Paris, tome 282 (21 juin 1976), série Algèbre, p.1339-1441 ;
  • Note sur le problème des tours de Hanoï Acta Vietnamica, Hanoï 1982 ; Un algorithme parallèle efficace pour construire un arbre de poids minimal dans un graphe, R.A.I.R.O. verte, 1985 ;
  • Une procédure purement itérative pour le problème des tours de Hanoï, Revue Roumaine de mathématiques pures et appliquées, n°̊6, 1985 ;
  • A fully distributed (minimal) spanning tree algorithm, Inf. Proc. Letters 23 (1986) p. 55-62, (1 co-auteur)
  • Algorithmique parallèle et distribuée, application à l’optimisation combinatoire, Thèse d’état, Université Paris 11 (LRI), 28 juin 1986.
  • Systematic Building of a distributed recursive algorithm, example the shortest path algorithm, Acta Mathematica Vietnamica, 1995, Volume 20, n°1, p.3-30 .
  • Fair and reliable self-stabilizing communication Studia Informatica Universalis Special Issue Vol.2 No.1
  • Self-stabilizing Distributed Spanning Tree and Leader Election Algorithm. Special Issue of The International Journal of Computer and Information Science (IJCIS) octobre 2000.
  • Reliable Self-Stabilizing Communication for Quasi Rendezvous Studia Informatica Universalis Volume 1 Numéro 1, 2001, (2 co-auteurs) ;
  • Version itérative de la multiplication de Strassen.C. R. Acad. Sci. Paris, t.333, Série I, p. 383-388, 2001, (1 co-auteur) ;
  • Création d’une base de données anatomo-fonctionnelle sur le cerveau, .C. R. Acad. Sci. Paris, C.R. Biologies 325 (2002), p. 1-17 (1 co-auteur)
  • A Distributed Preflow-Push Algorithm for the Maximum Flow Problem (revised paper), Lecture Notes in Computer Science, Springer 2005, 195-206. 3 co-auteurs.
  • A General Scalable Parallelizing of Strassen’s Algorithm for Matrix Multiplication on Distributed Memory Computers. International Journal of Software Engineering, Research, Management et Applications -IJSERA- 2006.
  • A New Direction to Parallelize Winograd’s Algorithm on Distributed Memory Computers (revised version), Lecture Notes in Computer Science, Springer 2008, 445-458. 3 co-auteurs.
  • Optimizing Mobile Networks Connectivity and Routing Using percolation Theory and epidemic Algorithms, 10th I2CS, Jubilee Edition 2010, Bangkok, Lecture Notes in Informatics, 165 GI 2010 (2 co-auteurs).
  • A New Direction to Parallelize Winograd’s Algorithm on Distributed Memory Computers (revised version), Lecture Notes in Computer Science, Springer 2008, 445-458. 3 co-auteurs.
  • Optimizing Mobile Networks Connectivity and Routing Using percolation Theory and epidemic Algorithms, 10th I2CS, Jubilee Edition 2010, Bangkok, Lecture Notes in Informatics, 165 GI 2010 (2 co-auteurs).

Congrès et conférences à sélection (comité de lecture) internationale et actes

  • Une heuristique efficace : La notion de regret en Recherche Opérationnelle, présenté par R. Faure, Polskie Toutargustwo Cybernetyczne, III symposium : p.n. Methody Heuristy, 25. (Wresnia 1976) ;
  • Rectangles maximaux dans une relation binaire quelconque, IIIth symposium on Operations Research., Universitat Mannheim, Sept. 1978 Proceedings. p. 157-171 ;
  • An efficient parallel algorithm for computing a minimum spanning tree, Parallel Computing 83, Berlin, proceedings p.259-262, 1984 ;
  • Scheme for complexity measures for distributed and parallel algorithms, Summer School on Combinatorics. Federal University of Rio de Janeiro, Brazil, Juillet 1985. (1 co-auteur) ;
  • Scheme for efficiency-performance measures of distributed and parallel algorithms, 1st Int. Work. on Dist. Alg. Proceedings (WDAG) ”Distributed Algorithms on graphs” edited by Eli Gafni and Nicola Santoro, p.69-103, Carleton University press (1 co-auteur).1986 ;
  • Conférencier invité à ”Performance in parallel computers”, Séminaire International sur les Supercalculateurs Scientifiques, Paris 2-6 février 1986, paru dans ”Supercomputing State-of-the-Art”, Super-computers and combinatorial algorithms,p. 95-110, North Holland Publishing, 1987 ;
  • Sur un problème de structuration de réseau Actes conférence invitée, Université de Tunis, Mai 1989 ;
  • Spanning tree construction for nameless networks, Proceedings of the fourth International Workshop on Distributed Algorithms (WDAG-4), Bari Italy 24-26 Sept. 90. Publié dans Lectures Notes on Computer Science n°486 p. 41-56. Springer Verlag Juin 1991 (1 co- auteur); ; Il s’agit là, à ma connaissance du premier algorithme probabiliste distribué de la littérature entièrement spécifié et implémenté;
  • Recursive Distributed Programming Schemes, ISADS 93, Kawasaki Japon proceedings p. 235-247, North Holland publishing 1993 (1 co-auteur) ;
  • Sur l’intelligence artificielle (débat avec J. Pitrat), colloque AIDRI, Lyon-1993, proceedings édités par Hermès. ;
  • A parallel probabilistic algorithm to find ”all” vertices of a polytope, Congrès International d’optimisation IEEE, Hano ̈ı, Juillet 1993 ;
  • La récursivité comme mode systématique de programmation distribuée, Application au problème des plus courts chemins”, Congrès OPOPAC, , La Canau, Nov. 1993. actes, p. 202-213, Hermès éd. (1 co-auteur) ;
  • A distributed recursive solution to the shortest path problem Congresso IO 94, Avril 1994, Braga, Portugal. (2 co-auteurs) ;
  • Routing tables maintenance with mobile agents. In Booklet of the 15th Triennal Conference of the International Federation of Operational Research Societes, IFORS, page 67, Pekin, China, July 1999 (1 co-auteur) ;
  • A Simple Heuristic for the Min-Cut k-Partition Problem. In Mathematical Foundations of Informatics MFI’99, Hanoi, Vietnam, October 1999 (1 co-auteur) proceedings World Proc. Ed. 2005, p. 55-65, Do Long Van, Masami Ito editors ;
  • Self-stabilizing Distributed Spanning Tree and Leader Election Algorithm In Proceedings of the ACIS 1st International Conference on Software Engineering Applied to Networking and Parallel/ Distributed Computing, pages 612-616, 2000. SNPD ’00 ;
  • Fair and Reliable Self-stabilizing Communication. In Proceedings of the 4th International Conference on Principles Of Distributed Systems, OPODIS 2000 Paris, december 2000 ;
  • Fast Matrix Multiplication : An iterative schema without stacks ; International Conference on Software Engineering Research and Applications (ICSERAI03)June 25 - 27, 2003 Crowne Plaza Union Square, San Francisco, USA (1 co-auteur) ;
  • ”A new distributed algorithm for the maximum flow problem”, 4th International Symposium on parallel and Distributed Computing, Lille, France, 2005; IEEE Computer Society, Washington, DC, (1 co-auteur) ;
  • A General Scalable Parallelizing Winograd’s Algorithm for Matrix Multiplication on Distributed Memory Computers. In 3th International Conference on Computer Sciences Research, Innovation and Vision for the Future, pages 71-79, Can Tho City, Vietnam, February 2005 (1 co-auteur) ;
  • A General Scalable Implementation of Fast Matrix Multiplication Algorithms on Distributed Memory Computers. In 6th International Conference on Software Engineering, Artificial Intelligence, Networking and Parallel/Distributed Computing, pages 116-122, Baltimore, Maryland, USA, May 2005 (1 co-auteur). IEEE Computer Society ;
  • A General Scalable Parallelizing of Strassen’s Algorithm for Matrix Multiplication on Distributed Memory Computers. In 4th Annual International Conference on Computer and Information Science, pages 221 - 226, Jeju Island, South Korea, July 2005 (1 co-auteur). IEEE Computer Society ;
  • A general scalable implementation of fast matrix multiplication algorithms on distributed memory computers”, 6th ACIS International Conference on Software Engineering, Artificial Intelligence, Networking, and Parallel/Distributed Computing (SNPD’05), Orlando, USA, 2005 (1 co-auteur) ;
  • Toward a multi-scale approach for spatial modelling and simulation of complex system .(2 co-auteurs) ECCS2005 Paris 2005 ;
  • A distributed préflow-push algorithm for the maximum flow problem, 5th Conference of Innovative Internet Community Systems (I2CS’05), Paris, France, June 2005.(2 co- auteurs) ;
  • Une approche multi-échelle pour l’étude des systèmes complexes (2 co-auteurs) RIVF 2006 Ho Chi Minh Ville (1 co-auteur) ;
  • An adaptative Distributed algorithm for the maximum flow problem in an underlying asynchronous network ( 2 co-auteurs) RIVF 2006 Ho Chi Minh Ville ;
  • A new direction to parallelize Winograd’s algorithm on distributed memory computers (2 co-auteurs) International Conference on High Performance Scientific Computing HPSC Hano ̈ı March 6-10 2006 (1 co-auteur) ;
  • Un modèle de percolation et de diffusion épidémique pour l’optimisation des réseaux mobiles MANETS Actes 11eme conférence on Inform. Proc. and Management of uncertainty in knowledge based systems, IPMU, Paris Juillet 2006 Vol. 3, pages 2698-2707 (2 co-auteurs) ;
  • A Complex Systems Approach in ATM modeling, Proceedings of the European conference on Complex systems, ECCS’06, Oxford, Great Britain, September , 2006 (2 co-auteurs) ;
  • A complex systems approach in atm modeling, European Conference on Complex Systems (ECCS’06), Oxford, UK, September 2006. (2 co-auteurs) ;
  • Percolation, pretopology and complex systems modeling, Models and Simulations Conference (MS’06), Paris, France, June 2006. (2 co-auteurs) ;
  • Generalizing a high performance parallel strassen implementation on distributed memory mimd architectures, 6th International Workshop on Innovative Internet Community Sys- tems (I2CS’06), Neuchatel, Switzerland, June 2006 ; Lecture Notes in Computer Science.(2 co-auteurs) ;
  • A space aware agent-based model link process for the study of hierarchical complex system, Symposium on Applied Computing (SAC’06), Dijon, France, 2006 (2 co-auteurs) ;
  • Investigating air trafic control dynamics using random cellular automata, 6th EURO- CONTROL Innovative Research Workshop & Exhibition (INO’06), Bretigny sur Orge, , décembre 2006, 139-143 ; (2 co-auteurs) ;
  • An adaptive distributed algorithm for the maximum flow problem in the underlying asyn- chronous network. RIVF 2006 : p. 187-194 ;
  • Complexité, percolation et optimisation stochastique, Congrès de la Recherche Opérationnelle et d’Aide à la Décision (ROADEF’06), Lille, France, février 2006 (2 co-auteurs) ;
  • Modélisation et simulation de phénomènes complexes dans le cadres des Systèmes d’In- formation Géographiques, conférence WATARID, Urumqi, Chine, Octobre 2006, actes numériques, non paginés ;
  • Generalized percolation processes using pretopology theory, International Conference of Research, Innovation and Vision of the Future (RIFV’07), Hanoi, Vietnam , March 2007, 130-134 ; IEEE Computer Society, Washington, DC, (2 co-auteurs) ;
  • Clustering based on Kolmogorov information, 14th International Conference on Knowledge- Based and Intelligent Information & Engineering Systems 8, 9, 10 September 2010 Cardiff, Wales, UKR. Setchi & al. ed. : KES 2010, Part 1, LNAI 6276, pp. 452-460, 2010.

Conférences sans actes

  • " A parallel Branch and Bound algorithm ", congrès Euro VII, Université de Bologne (italie) 1985 ;
  • " Le parallélisme en algorithmique ", (tutorial) Montevideo, Uruguay, Juillet 1985 ;
  • Conférencier invité à l’ " école de Mathématiques et Intelligence Artificielle de l’université de Tunis "du 20 Mars au 1 Avril 1985 pour 3 conférences invité : – Un exposé de synthèse (tutoriel) sur l’algorithmique distribuée, – Un cours sur l’architecture des ordinateurs parallèles, – Détection d’états stables en distribué ;
  • Conférencier invité à " Symposium on Mathematics of Computation ", organisé par : International Council On Mathematics In Developping Countries (ICOMID), à Ho Chi Minh ville, Viˆet-nam, du 24 avril au 2 mai 1987. " A fully distributed asynchronous algorithm for leader election and (minimum) spanning tree ".

Publications avec comité de lecture national

  • Mémoire d’ingénieur IIE-CNAM,Contribution à l’algorithmique non numérique.-directeur Étienne Pichat- 1971;
  • Recouvrements d’un ensemble par une sous famille de ses parties, Thèse de Docteur- Ingénieur, Juin 1974, université Paris VI ;
  • Caractérisations algorithmiques simples des treillis distributifs et des treillis modulaires de longueur finie, Groupe Combinatoire de l’AFCET, 02/06/1977, p. 1-11 ;
  • Algorithme de la tranche en Programmation linéaire concave, publication CNRS, groupe de recherche Claude François Picard, n°25, p. 51-60 1981;
  • Sur un problème de gestion de piles, séminaire AFCET, proc. p.12-17, 1982.
  • Notes sur le parallélisme, publication CNRS GR. 22, n°1, avril 1983;
  • Theory and Practice of matrix multiplication in parallel and vectorial processors, publication CNRS, GR 22, n°2, avril 1983 ;
  • Directions de recherche en algorithmique parallèle et distribuée, INRIA Mars 1986; 9. L’apport du parallélisme à la Recherche Opérationnelle, Journée du 20 ème anniversaire du groupe combinatoire de l’AFCET, Décembre 1986 ;
  • Un algorithme totalement distribué pour le problème de l’arbre minimum , colloque C3 mars 1986, CNAM ;
  • Apprentissage de propriétés semi-globales sur un système distribué I. Lavallée RR INRIA n°0819 1988;
  • Yet another distributed election and spanning tree algorithm I. Lavallée, C. Lavault RR INRIA n°1024 1989;
  • Un algorithme probabiliste d’élection et d’arbre couvrant sur des réseaux anonymes I.Lavallée, C. Lavault RR INRIA n°1151 1989 ;
  • Efficient routine protocols in nameless networks I.Lavallée C. Lavault RR INRIA n°1254 1990 ;
  • Un algorithme distribué d’élection non prédéterminée et d’arbre couvrant. F. Butelle I. Lavallée RR INRIA n°1444 1991;
  • La récursivité mode de programmation distribuée. G. Florin, I. Lavallée RR INRIA n°1536 1991 ;
  • A Parallel Probabilistic algorithm to find ”all” vertices of a polytope. P.C. Duong, I. Lavallée RR INRIA n°1813 1992;
  • Systematic Building of a distributed algorithm : example : the shortest path problem. G. Florin, R.G. Cardenas, I. Lavallée RR INRIA n°1902 1993 ;
  • Communications autostabilisées, proc. Of Workshop à Amiens, (Hermès éd.) 1997 ; 20. Exorcisme ou communication fiable et équitable autostabilisée in Parallélisme et Répartition, pages 9-21. Hermès, Paris, 1998.

Diffusion sociale des connaissances

  • Directeur de la revue STUDIA INFORMATICA UNIVERSALIS éditions Hermann. J’ai négocié la publication de la revue avec l’éditeur Hermann, j’ai dirigé la publication de 7 numéros, 6-1, 6-2, 6-3 (année 2008) ; 7-1 ; 7-2 ; 7-3 (année 2009) ; 8-1 Février 2010. À partir de février 2010, c’est Alain Bui qui prend la rédaction en chef de la revue.
  • Entretien Inscriptions assistées par ordinateur à l’université de Paris-Val-de-Marne 0-1 Articles de presse, ouvrages, conférences, émissions et entretiens... Informatique, n°551, 30 juillet 1979;
  • Entretien APL et conversationnel à l’université INFORMATIQUE et GESTION, n°108, Septembre 1979 ;
  • Article L’architecture des super-calculateurs, TEMPS REéL n°66, 17 au 30 Octobre 1983, p. 38-42 ;
  • Article Comment accélérer les calculs?, 01 Informatique, n°958, 25 mai 1987, p. 40-41;
  • Article (25 pages) L’informatique aujourd’hui, réflexions pour demain dans Une révolution par l’intelligence, ouvrage collectif avec G. Cohen Tannoudji (Physique), J. P. Kahane (Mathématiques) & alii, Éditions Messidor-Avancés Scientifiques 1991;
  • Article Les artifices de l’intelligence La Pensée, numéro spécial (n°282) -1992-;
  • Émission télévisée Connaissance de la Science sur la 5, UNISAT, Université Audiovisuelle Francophone, avec J. Arsac et J.P. Verjus 1993 ;
  • Article L’ombre de l’intelligence revue Quaderni n°25, p. 43-59, Centre Ntnl du Livre, éd. AZ presse, 1995 ;
  • Article Des ordinateurs et des hommes, Regards (mensuel) n°10, Février 1996 ; Conférence publique Complexités, informatique, etc. , Mardi de Paris 8, 9/12/1997 ;
  • Article Vous avez dit complexité ?, Discussion avec S.J. Gould, Regards (mensuel) n°31 Janvier 1998 ;
  • Débat public Cyber révolution et Société, Nice Décembre 2002 ; Ouvrage Cyber révolution éditions Le temps des cerises, 2002 ;
  • Article Recherche : pour un monde nouveau, un citoyen majeur, Journal L’Humanité 7 Juin 2004 ;
  • Article Des bons usages de l’énergie revue La Pensée n°346 ; septembre 2006 ; Rédacteur en chef du n°356 de la revue La Pensée; décembre 2008.