Title:From clear specifications to efficient implementations
Speaker:Prof. Annie Liu
Venue:Lecture Room,State Key Lab of Computer Science, Level 3 Building #5, Institute of Software, CAS
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,
building software components expressed using objects. Finally, we summarize our ongoing projects on a number of fronts.