Veronica Becher
vbecher@dc.uba.ar
Department of Computer Science
Faculty of Exact and Natural Sciences
University of Buenos Aires
Argentina
*****************************************************************
When is an infinite sequence random? As Kolmogorov said, classical
probability theory does not give an answer to the question. The obvious
definition says that a sequence is random if it has the same properties
as a sequence of coin flips. But this definition gives us no clue to
which are these properties. The definition of randomness had to be based
on computability, and arose from two different characterisations. One is
based on the hypothesis that random sequences should satisfy all
computable statistical properties of randomness (Martin-Lof tests,
1966). The other characterisation is based on the hypothesis that random
sequences should lack structure, regularity, and thus their initial
segments should be algorithmically incompressible: random infinite
sequences are those whose initial segments have essentially the same
size as the minimal-length computer programs needed to generate them
(Chaitin 1975-Kolmogorov 1966). The two characterisations coincide
(Chaitin 1975).
Le 28 mars 2001, 17h
SALLE U ou V, étage -2
ENS, Dépts. de Math. et d'Informatique, 45, Rue D'Ulm, 75005 Paris
"Information Quantique: ou pourquoi les incertitudes d'Heisenberg
engendrent une algorithmique surprenante."
Remy Mosseri (Groupe de Physique des Solides, Paris VI et VII)
*****************************************************************
L'information quantique est un nouveau champ de recherche dont l'objectif
avoué est de tirer partie des possibilités offertes par la mécanique quantique pour traiter l'information d'une manière efficace. Les deux composantes principales en sont la cryptographie quantique, qui ambitionne d'apporter une sécurité accrue par rapport aux systèmes de cryptographie classique, et d'autre part le calcul quantique, pour lequel de nouveaux algorithmes
basés sur les principes de la mecanique quantique doivent permettre, dans certains cas, de diminuer radicalement les temps de calculs (plus précisément ce qu'on appelle leur complexité algorithmique) nécessaires pour résoudre les problèmes. Le plus célèbre de ces problèmes est celui de la décomposition
d'un nombre en ses facteurs premiers, ce qui rapproche d'ailleurs le calcul
quantique du terrain de la cryptographie, où la théorie des nombres intervient dans les questions de codage.
Mais si cet objectif (lointain pour certain, voire meme illusoire pour les
plus pessimistes) permet de définir rapidement ce thème, son développement actuel, extrêmement rapide, tient aussi à ce qu'il ouvre, dans une approche
pluridisciplinaire, des perspectives excitantes relatives à une compréhension plus fine de phénomènes quantiques. Qu'il s'agisse de l'étude des états "intriqués" (qui sont au coeur des possibilités nouvelles de manipulation de l'information), où bien encore du phénomène de décohérence, qui verrouille le passage des manifestations quantiques entre les mondes microscopique et macroscopique, et qui s'avère par là le principal obstacle à la réalisation de dispositifs, il y a là un terrain fertile, tant dans le domaine de l'optique quantique que de la matière condensée (au travers de sa composante de physique mésoscopique).
Ainsi les études expérimentales recouvrent-elles des systèmes très différents, comme les ions ou les atomes neutres piégés, l'électro-dynamique quantique en cavités micro-ondes ou optiques, des "dispositifs" moléculaires basés sur des techniques RMN, des systèmes de boites quantiques mésoscopiques, ou bien encore des nano-jonctions supraconductrices...
L'objectif de ce seminaire sera de presenter ce thème émergent et ses enjeux, théoriques et experimentaux, tout en restant à un niveaux assez general et pas trop technique.
Foundation of a Computable Solid Modeling
Abbas Edalat (London, Imperial College)
(work with Andre Lieutier, Scientific team, Matra Datavision
& XAOLAB, LIM, Marseilles).
4/06: Université de Paris
7, 10h30, Salle 513, couloir 45-55, 5ème étage
abstract
MINI-COURS : Continuous Domains and
Their Applications
Abbas Edalat (London, Imperial College)
les 7 et 14 juin de 15h45 a 18h45 en
salle R (niveau -2), ENS (DMI)
Abstract
We give a survey of the work in the past few years on applications of
continuous domains to construct computational models in various areas
of mathematics and computer science. We first show how
domain-theoretic models are built for the real line, locally compact
Hausdorff spaces and metric spaces and explain how they can be given
an effective structure to obtain the computable elements and functions
associated with these structures. We then present a domain-theoretic
framework for exact real number computation, using linear fractional
transformations a la Vuillemin, in which numerical computation can
be
approximated up to any given precision, overcoming the problem of
round-off errors in floating point computation. We then introduce the
foundation of a computable topology and show how it gives rise to a
realistic framework for solid modelling. Finally, we outline a
domain-theoretic framework for measure and integration theory which
gives a generalization of the Riemann theory of integration to
arbitrary finite measures on locally compact Hausdorff spaces (more
generally to sigma-finite Borel measures on Polish or analytic spaces)
and show how this framework can be used to compute integrals up to
any
required precision.
Le 21 juin a 16 h a l'ENS en salle R (niveau -2), DMI:
Barry Jay
University of Technology, Sydney
TITRE: Shape Theory: FISh implementation
MINI-COURS: The functorial lambda-calculus (cours 1),
The shaped lambda calculus (cours 2)
Barry Jay (University of Technology, Sydney)
les 17 et 24 juin de 10h30 a 12h30 a Jussieu, salle 105, couloir 55-65