diana@csri.toronto.edu (Diana Li) (07/18/89)
ACTIVITIES FOR THE WEEK COMMENCING JULY 24, 1989
(SF = Sandford Fleming Building, 10 King's College Road)
-------------------------------------------------------------
NUMERICAL ANALYSIS SEMINAR
SF 1101, at 2:10 p.m., Tuesday 25 July 1989
Vivette Girault
Laboratorie d'Analyse Numerique, University of Paris VI
"Steady-State Stokes Flow in Two or
Three-Dimensional Exterior Domains"
We consider the solution of the steady-state Stokes flow, in two and three
dimensions, on the exterior of a bounded domain. By imposing the
appropriate behaviour of the velocity at infinity, the problem can posed in
a variational form with a unique solution. If the external forces have
bounded support it is possible to solve the problem by coupling a finite
element method in the bounded region supporting f, with boundary integral
equations.
-------------------------------------------------------------
AI SEMINAR
SF 3202, at 11:00 a.m., Wednesday 26 July 1989
Marc Linster
Gesellschaft fur Mathematik und Datenverarbeitung, West Germany
"From KRITON to IRMA:
Two Paradigms for Automated Knowledge Acquisition"
GMD's project KRITON is concerned with basic research in the domain of
automated and computer-supported knowledge acquisition. After a short
presentation of GMD and its Institute for Applied Information Technology we
will describe the projects of the expert system research group that
constitute the context of the KRITON project.
I will first present and critique the knowledge-acquisition system KRITON
that integrates two techniques originating from cognitive psychology, i.e.
interview techniques and protocol analysis. The KRITON-system is based on
a bottom-up approach, i.e. it focuses on the support of rapid prototyping.
The second approach I will present is based on the KADS-knowledge-models
(Knowledge Acquisition and Design Structuring) and on our experience with
the techniques that were originally developed for the KRITON-system. This
approach is best described as model-guided knowledge acquisition. The
system that will result from the integration of knolwedge-modeling with
knowledge acquisition will be called IRMA (Interpretation, Representation,
Modeling and Acquisition). IRA-grid (Interpretation, Representation and
Acquisition using repertory-grids) is the first component of IRMA. It is a
knowledge-acquisition tool that tries to acquire the knowledge needed for
hypothesis-selection processes.
-------------------------------------------------------------
THEORY SEMINAR
SF 3202, at 2:00 p.m., Wednesday 26 July 1989
Noga Alon
Tel Aviv University & Bell Communications Research
"Balancing Vectors with Applications in Communication Theory"
Let F=F(n) denote the set of all vectors with coordinates +1 or -1 in the n
dimensional Euclidean space. We show that for every even n the minimum
cardinality of a subset S of F such that for every vector in F there is a
member of S orthogonal to it, is precisely n. This result and some of its
extensions have certain applications to communication theory.
(Joint work with Bergmann, Coppersmith and Odlyzko.)
-------------------------------------------------------------
THEORY SEMINAR
SF 1101, at 2:00 p.m., Thursday 27 July 1989
Michael Saks
Univeristy of California, San Diego
"The Cell-probe Complexity of Dynamic Data Structures"
The typical dynamic data storage and retrieval problem requires
maintenance of a data set in a way that permits certain types of changes in
the data set (updates) and queries about the data. One simple example is
the interval range-query problem: maintain a subset S of the integers 1 to
n, allowing updates of the form: given a specific element, add it to S if
it is not in and delete it otherwise, and queries of the form: how many
elements of the set are between i and j? For many such problems there
appears to be an inherent trade-off between the costs of updates and
queries. Here a new method for proving such tradeoffs is presented, which
can be used to give nearly tight tradeoffs for the interval range query
problem and several other problems, including partial sum-queries,
dynamic-list ranking, and disjoint set union-find. The lower bounds are
proved in Yao's cell-probe model which does not assume restrictions on the
representation of the data or on the operations allowed and are based only
on the number of write operations needed for an update versus the number of
read operations needed for a query. The lower bounds hold for amortized as
well as worst case complexity, and apply to randomized as well as
deterministic algorithms.
(Joint work with Michael Fredman.)
-------------------------------------------------------------
NUMERICAL ANALYSIS SEMINAR
SF 1105, at 2:10 p.m., Friday 28 July 1989
B.N. Parlett
University of California at Berkeley
"Isospectral Flows and Forward Instability of the QR Algorithm"
We describe the connection between certain systems of nonlinear
differential equations and the QR algorithm for transforming a square
matrix to upper triangular form.
The QR algorithm is backward stable. We describe conditions under which it
is forward stable. We mention recent results of Batterson and Smillie
showing the QR with Rayleigh quotient shifts can cycle and even behave
chaotically.