主 题: From Clear Specifications to Efficient Implementations
报告人: Annie Liu (Professor,CS, SUNY Stony Brook)
时 间: 2007-09-17 下午 2:30
地 点: 理科一号楼 1560
Two major concerns of study rest at the center of computer science:
what to compute, and how to compute efficiently. Problem solving
involves going from clear specifications for the "what" to efficient
implementations for the "how". This is challenging because clear
specifications usually correspond to straightforward implementations,
not at all efficient, while efficient implementations are usually
difficult to understand, not at all clear.
This talk gives an overview of a general and systematic method for
transforming clear specifications into efficient implementations. The
method has three steps: (1) iterate---determine a minimum step to be
taken repeatedly, (2) incrementalize---maintain appropriate values
incrementally over the repeated steps, and (3) implement---design data
structures for the values maintained. We will illustrate the method
through examples, taken from problems in hardware design and image
processing expressed using loops and arrays, in query processing and
access control expressed using set operations, in sequence processing
and math puzzles expressed using recursive functions, in program
analysis and trust management expressed using logic rules, and in
building software components expressed using objects. Finally, we
summarize our ongoing projects on a number of fronts.
