English

Année thématique 2002-2003

Les mathématiques en informatique

Sommaire École d'été Conférences internationales annuelles Cours Chaires Aisenstadt Ateliers Aide financière Périodes de Concentration Séminaires COMITÉ ORGANISATEUR

 

 

 

 

 

 

 

 

 

  

Introduction

Le domaine de l'informatique, avec une origine formelle datant du dix-neuvième siècle et des racines remontant à Euclide, est maintenant une discipline mathématique de plein droit, avec de solides fondements théoriques sur lesquels s'appuient son développement spectaculaire. L'année thématique du CRM sur les mathématiques en informatique propose une exploration en profondeur une gamme de sous-domaines qui sont des clefs de voûte pour l'informatique moderne, qui exhibent un contenu mathématique significatif et nouveau, et qui ont en effet influencé le développement des mathématiques.

En mathématiques, les domaines dont l'apport a d'abord été crucial à l'informatique furent la logique et les mathématiques discrètes. Depuis lors, l'informatique théorique s'est grandement développé, et des idées provenant du domaine, partant de concepts tels que l'efficacité, la complexité et la tractabilité, occupent une position de plus en plus importante en mathématiques. Récemment, des méthodes probabilistes sont devenus un thème récurrent, traversant toute l'informatique. Une attention toute particulière sera portée à l'utilisation de ces techniques, aussi bien dans les domaines théoriques que dans des domaines appliqués tels que la simulation et l'apprentissage automatisé.

---

ÉCOLE D'ÉTÉ

• Organisateur: Gilles Brassard (Montréal)

La théorie de l'information classique est résolument dans la physique classique de Newton et Einstein. mais l'univers est régi par les lois de la mécanique quantique. Ceci nous a empêchés de profiter pleinement de ce que la nature a à offrir pour fins de traitement de l'information. Par exemple, la mécanique quantique rend possible une cryptographie inconditionnellement confidentielle ainsi qu'un niveau de parallélisme qui laisserait pantois un ordinateur classique de la taille de l'univers. Le but de cette école est de rendre accessible la notion d'informatique quantique à un public qui n'a pas de connaissances préalables de la mécanique quantique, mais qui est scientifiquement éduqué en mathématiques ou en informatique.

• Conférenciers: Andris Ambainis, Charles Bennett, Gilles Brassard, Harry Buhrman, Richard Cleve, Claude Crépeau, Daniel Gottesman, Nicolas Gisin, Peter Høyer, Raymond Laflamme, Alain Tapp et John Watrous.

Pour de plus amples informations

CONFÉRENCES DE LA CHAIRE AISENSTADT

Les conférenciers de la Chaire Aisenstadt cette année seront László Lovász (Microsoft Research) et Endre Szemerédi (Rutgers).

PÉRIODES DE CONCENTRATION

Théorie de la complexité et analyse des algorithmes
Mai-Juin 2002

•Organisateurs: Pierre McKenzie (Montréal), Denis Thérien (McGill)

En mai 2002, le CRM sera l'hôte de deux des conférences les plus importantes de l'informatique théorique, le Symposium on Theory of Computing de l'ACM et la Conference on Computational Complexity de L'IEEE. En plus, il y aura plusieurs ateliers d'une semaine sur des sujets au coeur de l'informatique théorique. Chaque atelier réunira un nombre de chercheurs de premier plan qui donneront des cours de survol ainsi que que des conférences sur la recherhce de pointe.

13-17 mai , 2002: Série de cours sur les programmes de branchement par Ingo Wegener
(Dortmund)

19-21 mai 2002: ACM Symposium on Theory of Computing (STOC)

21-24 mai 2002: IEEE Conference on Computational Complexity

27-31 mai 2002: Aspects probabilistes des programmes de branchement

Les techniques probabilistes ont un rôle important en informatique qui provient d'algorithmes donnant une solution efficace à des problèmes pour lesquels aucune solution déterministe n'est connue, ou par l'intermédiaire de l'étude probabiliste de la complexité. Une semaine sera vouée à ce thème, en commençant par les liens entre les techniques probabilistes et les programmes de branchement.

3-7 juin 2002: Vérification et model-checking

Depuis dix ans, le travail théorique dans le domaine de la vérification a porté fruit. Cet atelier couvrira les aspects les plus importants de ce développement, en particulier, ceux liés au model-checking.

10-14 juin 2002: Complexité descriptive

Autre domaine qui a pris de l'importance au cours des dernières années, la complexité descriptive donne un outil complémentaire aux méthodes plus traditionnelles en complexité. Après un survol du domaine, l'atelier se concentrera sur les liens entre programmes de branchement et les structures algébriques.

Les invités pour les ateliers d'une semaine comprennent: D. Barrington, P. Beame, P.L. Crescenzi, R. Gavalda, N. Immerman, K.J. Lange, P. Pudlak, A. Razborov, M. Sachs, R. Raz, P. Schnoebelen.

Fondements de la mécanique quantique à la lumière de la théorie de l'information
13 octobre - 2 novembre 2002

•Responsables: Gilles Brassard (Montréal), Christopher A. Fuchs (Bells Labs, Lucent Technologies)

L'aphorisme le plus connu de Rolf Landauer est « l'information est physique ».Cet atelier se réclame de la conviction que « la physique est information »! Notre but à long terme est de reformuler les fondements de la mécanique quantique à la lumière de la théorie de l'information quantique. Plutôt que d'être contre-intuitive, se pourrait-il que la mécanique quantique soit inévitable pour que l'information se comporte tel que nous le découvrons maintenant?

Par exemple, que nous apprend sur la physique le fait que la distribution cryptographique de clefs inconditionnellement sécuritaire est possible alors que la mise en gage de bits ne l'est pas?

Sur invitation seulement.

Invités: H. Barnum, G. Brassard, H. Briegel, J. Bub, A. Cabello, C. Caves, R. Cleve, C. Fuchs, N. Gisin, D. Greenberger, L. Hardy, P. Hayden, A. Holevo),R. Jozsa, A. Kent, D. Mayers, D. Mermin, T. Mor, M. Nielsen, A. Peres, I. Pitowsky, R. Schack, B. Schumacher, J. Smolin, R. Spekkens, A. Steane (*), D. Wallace, W. Wootters, A. Zajonc.

Combinatoire, probabilités et algorithmes
Mai 2003

•Responsables: David Avis (McGill), Luc Devroye (McGill), Bruce A. Reed (Waterloo)

Ne rien laisser au hasard. Ce cliché exprime la croyance commune que l'aléatoire n'a pas sa place dans des méthodologies bien conçues: il faut que tous les points soient sur les i. En mathématiques discrètes, au moins, rien ne pourrait être plus loin de la vérité. L'introduction de choix aléatoires dans des algorithmes peuvent améliorer leur performance. L'application de méthodes probabilistes a mené à la résolution de problèmes combinatoires qui avaient résisté à une solution depuis des décennies.

Une période de concentration d'une durée d'un mois aura lieu autour de ce thème général. Les conférenciers de cette école présenteront une variété d'armes, la plupart de l'arsenal probabiliste, et leurs applications en combinatoire et à l'étude d'algorithmes. La plupart des mini-cours auront lieu en mai 2003, et nous anticipons une interaction importante entre les participants durant cette période.

Il y aura des mini-cours de 5 heures donnés par: V. Chvatal (Rutgers), A. Frieze (Carnegie-Mellon), C. McDiarmid (Oxford), M. Molloy (Toronto), J. Pach (City College New York and Hungarian Academy of Sciences), ainsi que des conférences de N. Alon (Technion). Les conférences Aisenstadt de L. Lov‡sz (Microsoft Research) et de E. Szemeredi (Rutgers) seront intégrées au programme.

Pour de plus amples renseignements

CONFÉRENCES INTERNATIONALES ANNUELLES

ACM Symposium on Theory of Computing (STOC)
19-21 mai 2002

IEEE Conference on Computational Complexity
21-24 mai 2002

•Responsables: Pierre Mackenzie (Montréal), Denis Thérien (McGill)

Ces deux conférences font partie intégrante de la période de concentration sur la Théorie de la complexité et analyse des algorithmes.

Mathematical Foundations of Programming Semantics
(MFPS)
19-22 mars 2003

•Responsable: Prakash Panangaden (McGill)

Les ateliers et conférences de cette série, tenus annuellement depuis 1985, visent la création d'un forum pour les chercheurs dans tous les domaines touchant à la sémantique, et l'amélioration de la communication et des interactions entre mathématiciens et informaticiens qui travaillent dans ces domaines. Les domaines touchés du côté mathématique comprennent les catégories, la logique et la topologie, et la théorie des types, la sémantique et le dessin et la mise en oeuvre de langages informatiques du côté informatique.

Pour plus de renseignements

IEEE Symposium on Logic in Computer Science (LICS)
20-26 juin 2003

•Responsables: Amy P. Felty (Ottawa), Philip Scott (Ottawa)

Tenu à l'Université d'Ottawa, l'IEEE Symposium on Logic in Computer Science (LICS) est un forum international sur les aspects théoriques et appliqués de l'informatique reliés à la logique dans le sens large. Le CRM contribuera à l'organisation de quatre conférences satellites de ce symposium.

Pour plus de renseignements

ATELIERS

La génération de nombres aléatoires et ensembles de points hautement uniformes
17-28 juin 2002

•Responsable: Pierre L'Ecuyer (Montréal)

Cet atelier réunira les chefs de file mondiaux, tant du côté pratique que théorique, dans la génération de nombres aléatoires par ordinateur et la conception d'ensembles de points hautement uniformes pour l'intégration quasi-Monte Carlo. Le thème général sera le développement de logiciels pratiques pour des classes variées d'applications, telles que la simulation, la statistique, l'analyse numérique, les jeux, les loteries, la cryptologie, etc. En simulation, des ensembles de points hautement uniformes remplacent souvent avec avantage des nombres aléatoires traditionnels. Leur construction et leur analyse peut s'appuyer sur des techniques très semblables à celles des générateurs de nombres aléatoires, et nous désirons renforcer ce lien.

Les conférenciers invités comprennent: C. Crépeau, L. Devroye, M. Evans, B.L. Fox, M. Fushimi, J. Gentle, P. Hellekalek, S. Heinrich, W. Hormann, A. Keller, G. Larcher, P. L'Ecuyer, J. Leydold, C. Lemieux, M. Mascagni, M. Matsumoto, S. Ninomiya, T.Nishimura, A.B. Owen, G. Pirsic, W. Schmid, I. Sloan, S. Tezuka, H. Wozniakowski, C. Xing.

Pour plus de renseignements et inscription

Modèles mathématiques et techniques pour l'analyse de systèmes
30 septembre - 4 octobre 2002

•Responsable: Prakash Panangaden (McGill)

L'analyse de systèmes s'est énormément diversifié et approfondi au cours des années récentes. En termes de diversification, les systèmes d'intérêt comprennent les systèmes stochastiques, les systèmes en temps réel et les systèmes hybrides, pour lequel l'espace d'états est en partie discret et en partie continu. Les applications comprennent des systèmes de gestion pour l'aviation, les systèmes de contrôle de procédés, des systèmes de télécommunication et des systèmes de gestion militaires. Tous ces exemples exigent qu'on compose avec une évolution continue dans le temps et fréquemment avec des aspects probabilistes. La méthode qui a probablement eu le plus de succès pour composer avec ces questions, méthode maintenant vieille de 20 ans, est celle de la vérification de modèles. Ceci a maintenant été étendu aux systèmes probabilistes et le théorie a avancé au point où des outils ont été conçus et construits. Mathématiquement, des techniques co-inductifs, tels la bisimulation, ont démontré leur valeur de façon répétée.

L'atelier aura deux conférenciers principaux, qui donneront chacun cinq conférences: Prof. Marta Kwiatkowska, U. Birmingham « Probabilistic Model Checking » and Dr. Jan Rutten, CWI Amsterdam « Coinductive Calculus ».

Les autres conférenciers invités comprennent: R. Alur, P. Caines, R. Jagadeesan, D.Precup.

Pour plus de renseignements et inscription

Théorie des modèles finis
2-9 mars 2003

•Responsable: Denis Thérien (McGill)

Cet atelier ciblera la capacité d'expression de logiques ainsi que la relation profonde entre la logique et la théorie de la complexité. Le conférencier principal sera Phokion Kolaitis (U.C. Santa Cruz). L'atelier aura lieu au Bellairs Research Institute de l'Université McGill.

Pour plus de renseignements

Semigroupes et automates
17-21 mars 2003

Cet atelier portera sur les développements récents de la théorie des automates et des semi groupes, en particulier ceux qui se rapportent à des questions de longue date telles que la décidabilité du dot-depth et la décidabilité de la complexité de Rhodes.

Pour plus de renseignements

Réduction cryptographique de protocoles quantiques et classiques
20-23 mai 2003

•Responsable: Claude Crépeau (McGill)

Du côté classique, les protocoles cryptographiques ont été étudiés depuis deux décennies sous différentes hypothèses sur la capacité de calcul. Des protocoles tels que Bit Commitment, Oblivious Transfer et Multiparty Computations ont été mis en oeuvre et réduits l'un à l'autre. Depuis quelques années, des résultats semblables ont été obtenus dans un contexte d'adversaires équipés d'ordinateurs quantiques. Cet atelier réunira des spécialistes des protocoles classiques et quantiques, qui feront le point sur ce sujet de recherche fascinant.

Les conférenciers invités comprennent: D. Beaver, C. Cachin (*), R. Cramer, C. Crépeau, I. Damgaard, P. Dumais, D. Gottesman, J. van de Graaf, R. Impagliazzo (*), J. Kilian, D. Mayers, M. Naor (*), S. Rudich (*), L. Salvail, A. Smith, A. Tapp, S. Wolf, M. Yung.

(*) à confirmer

Pour plus de renseignements

Percées dans l'apprentissage automatisé
8-11 juin 2003

•Responsables: Yoshua Bengio (Montréal), Balazs Kégl (Montréal), Doina Precup (McGill)

Les probabilités sont au coeur des percées récentes dans la théorie et la pratique des algorithmes d'apprentissage. Cet atelier ciblera trois grands domaines où ces percées sont cruciales: la théorie statistique de l'apprentissage, les algorithmes d'apprentissage, et l'apprentissage par renforcement. Cet atelier réunira des experts de chacun de ces domaines. Parmi les sujets couverts, on peut citer les méthodes variationnelles, les modèles graphiques, le défi de la dimensionnalité, les méthodes empiriques pour tirer avantage de théories sur l'erreur de généralisation, ainsi que des applications.

Les conférenciers invités comprennent: P. Bartlett, A. Barto, N.de Freitas, P. Frasconi, G. Hinton, M. Jordan, V. Koltchinskii, Y. Le Cun, M. Littman, G. Lugosi, S. Mahadevan, S. Roweis, B. Scholkopf, D. Schuurmans, S Singh, R. Sutton.

Pour de plus amples renseignements

SÉMINAIRE

Il y aura un séminaire toute l'année sur les mathématiques de l'informatique.

COURS

Les universités montréalaises offrent une panoplie de cours dans le sujet de l'année. La liste peut être consultée sur les sites suivants : http://www.iro.umontreal.ca/cours/
http://www.cs.mcgill.ca/acadpages/grad/course-grad.html
http://www.cs.concordia.ca/programs/grad/courses.html
http://www.info.uqam.ca/dinfo/coursdepframe.html

AIDE FINANCIÈRE POUR ÉTUDIANTS

De l'appui financier est disponible pour étudiants à la maîtrise, au doctorat et pour les boursiers post-doctoraux désirant visiter le CRM pendant l'année thématique. Toute demande doit être accompagnée d'une lettre de référence du directeur de recherche ainsi que d'un curriculum vitae.

Veuillez faire parvenir votre demande d'aide financière à:

Activités scientifiques
Centre de recherches mathématiques
Universite de Montréal C.P. 6128,
Succursale Centre-ville, Montréal (Québec)
CANADA H3C 3J7
Télécopieur: (514) 343-2254

Courriel: activites@CRM.UMontreal.CA

COMITÉ ORGANISATEUR

Ceux qui désirent participer à ces activités sont priés d'écrire à:

Louis Pelletier
Centre de recherches mathématiques (CRM)
Université de Montréal
C.P. 6128, Succ. Centre-ville
Montréal (Québec)
CANADA H3C3J7

Adresse électronique: ACTIVITES@CRM.UMontreal.CA

Dernières modifications: le 4 septembre 2002
Webmestre