clarke@utcsri.UUCP (Jim Clarke) (01/09/87)
(SF = Sandford Fleming Building, 10 King's College Road)
(GB = Galbraith Building, 35 St. George Street)
COLLOQUIUM, Tuesday, January 13, 11 am, SF 1101
A. Borodin
Towards a Theory for Online Algorithms
or
Using the Past to Plan for the Future in order to Cover Your Assets
(Work in collaboration with N. Linial and M. Saks)
Recommended Reading: Amortized Efficiency of List Update and Paging Rules;
Sleator and Tarjan; CACM Feb. 1985.
There are a number of examples of online algorithms which perform remark-
ably well as compared to an all knowing (in terms of the future) offline
algorithm. We would like to develop a general theory which helps explain
this surprising phenomena. We have not succeeded in doing so but, as a
possible first step in this direction, we consider ``metrical task sys-
tems''. A task system has n states {1,2 ,..., n} and a cost d(i,j) associ-
ated with each possible state transition. The system is metrical if d is
symmetric and satisfies the triangle inequality. There is an online algo-
rithm A which processes any sequence of tasks T with cost C sub A (T) <=
[(2n-1) C sub OPT (T) + constant ] where C sub OPT (T) is the minimum cost
of any offline algorithm which processes T. The factor (2n-1) is optimal.
AI SEMINAR, Tuesday, January 13, 3 pm, GB 120
Professor Hector Levesque
University of Toronto and
Canadian Institute for Advanced Research
All I Know
In standard logics of belief, there is an operator on sentences that can be
thought of as saying that the sentence in question is believed. But since
a belief normally does not exclude all others, the operator really says
that "at least" that sentence is believed. This raises the possibility of
a dual operator saying that "at most" the sentence is believed. It appears
that some forms of default (or nonmonotonic) reasoning are indeed based on
this latter concept, where it is necessary to take into account all that is
believed. This talk will present a formal semantic account of these
notions in a logic with two belief operators, and sketch some of its pro-
perties and uses.
GRAPHICS SEMINAR, Thursday, January 15, 11 am, GB 220
Aaron Marcus
Aaron Marcus & Associates
Topics in Advanced User Interface Design
Abstract: Issues of visible language programming, including typography,
symbolism, colour, layout, animation, and sequencing, will be discussed.
Some guidelines for screen design will be presented.
--
Jim Clarke -- Dept. of Computer Science, Univ. of Toronto, Canada M5S 1A4
(416) 978-4058
{allegra,cornell,decvax,linus,utzoo}!utcsri!clarke