clarke@utcsri.UUCP (11/17/87)
(SF = Sandford Fleming Building, 10 King's College Road)
(GB = Galbraith Building, 35 St. George Street)
SUMMARY:
A.I. SEMINAR, Tuesday, November 24, 2 pm, GB244 -- John Holland:
"Genetic Algorithms and Classifier Systems"
THEORY SEMINAR, Thursday, November 26, 11 am, SF1101 -- Valerie King:
"An O(n**8/7) Lower Bound on the Randomized Complexity of Graph Properties"
SYSTEMS SEMINAR, Thursday, November 26, 3 pm, GB 244 -- Jan Pachl:
"Livelocks in Ring Networks"
NUMERICAL ANALYSIS SEMINAR, Thursday, November 26, 4 pm, GB119 --
Bradley L. Lucier:
"The Relationship Between Regularity and Approximation for Hyperbolic
Conservation Laws"
----------------------------
A.I. SEMINAR, Tuesday, November 24, 2 pm, GB244
Professor John Holland
University of Michigan
"Genetic Algorithms and Classifier Systems"
Message-passing, rule-based systems, in which many rules called "classifi-
ers" are active simultaneously, offer attractive possibilities for exploit-
ing architectures for parallel computation. With some care, such systems
can be designed for use in conjunction with credit assignment and rule
discovery algorithms, called "bucket brigade" and "genetic" algorithms,
respectively, so that the system adapts to new situations. The study of
"classifier systems" has been substantially aided by relevant pieces of
theory. In particular, fixed point theorems aid in understanding the role
of "bucket brigade" algorithms in apportioning credit, and new versions of
theorems from mathematical genetics help in understanding th way in which
"genetic algorithms" generate new rules from "building blocks" that have
already proved useful to the system.
References:
INDUCTION: PROCESSES OF INFERENCE, LEARNING, AND DISCOVERY. Holland et al.
MIT Press. 1986. GENETIC ALGORITHMS AND THEIR APPLICATIONS. Grefen-
stette. Erlbaum Publishers. 1987
THEORY SEMINAR, Thursday, November 26, 11 am, SF1101
Ms. Valerie King
University of California at Berkeley
"An O(n**8/7) Lower Bound on the Randomized Complexity
of Graph Properties"
A decision tree algorithm determines whether an unknown graph with n nodes
has a property by examining the entries of the graph's adjacency matrix and
branching according to the information already gained. All
(isomorphism-invariant) graph properties which are monotone (not destroyed
by the addition of edges) and nontrivial (holds for some but not all
graphs) have been shown to require O(n**2) queries in the worst case.
We investigate the power of randomness in recognizing these properties
by considering randomized decision tree algorithms in which coins may be
flipped to determine the next entry to be examined. The complexity of
a randomized algorithm is the expected number of entries that are exam-
ined in the worst case. The randomized complexity of a property is the
minimum complexity of any randomized decision tree algorithm which com-
putes the property. We improve Yao's lower bound on the randomized com-
plexity of any monotone nontrivial graph property from O(n*log**1/12 n) to
O(n**8/7).
SYSTEMS SEMINAR, Thursday, November 26, 3 pm, GB 244
Professor Jan Pachl
University of Waterloo
"Livelocks in Ring Networks"
The starting point of this talk is the observation that the medium-access
protocols in some existing and proposed ring networks are livelock-prone:
Under certain circumstances, a single transmission error may bring the ring
into a state in which data packets are sent but not delivered.
Several simple modifications that make the protocols livelock-free will be
described. The correctness of some modifications is not obvious; in fact,
it may not even be obvious what correctness in the presence of transmission
failures should mean. It will be shown how a simple formalism allows us to
describe unambiguously the key aspects of the protocols and to reason about
their correctness.
NUMERICAL ANALYSIS SEMINAR, Thursday, November 26, 4 pm, GB119
Professor Bradley L. Lucier
Purdue University
"The Relationship Between Regularity and Approximation
for Hyperbolic Conservation Laws"
I will present a moving-grid numerical method that approximates discontinu-
ous solutions of hyperbolic conservation laws of the form,
(C) [These equations are omitted from this nroffed posting,
for the sake of the poster's sanity. If you want to see
them, come to the seminar.]
These equations arise in many physical contexts, including mechanics.
Error bounds for this method show that for many problems, the rate of
approximation in L1(R) of the solution u(cdot,t) by piecewise linear functions
with free knots is as good at later times as at the initial time. This
approximation result leads to a new Sobolev-space type regularity theory for
discontinuous solutions of (C). The smoothness classes characterized by
approximation with piecewise linear functions with free knots are similar to
Lp spaces for 0 < p < 1 (i.e., they are quite strange!), in that their "unit
balls" are not convex.
--
Jim Clarke -- Dept. of Computer Science, Univ. of Toronto, Canada M5S 1A4
(416) 978-4058
{allegra,cornell,decvax,linus,utzoo}!utcsri!clarke