ABSTRACT

Information is represented inside a computer by using structures that mimic mathematical models. Many different kinds of models can be used for the same information; conversely, many different kinds of information can be represented with the same model. One of the main reasons that we are able to solve problems efficiently is that we have mathematical tools that tell us how to convert between alternative representations.

This talk focuses on one of the most fundamental mathematical models, the notion of a "family of sets" over some universe. This model is essentially equivalent to many other models, such as Boolean functions, hypergraphs, or matrices of 0s and 1s. But the "family of sets" interpretation leads to a different way of thinking, and to a fundamentally different class of problems from those that are normally associated with functions or matrices.

A family of sets is naturally represented by a data structure called a ZDD. Two or more families are combined by basic operations such as union, intersection, join, meet, quotient. We are often interested in, say, the maximal sets of a family, or in the members of one family that don't contain any members of another, etc. Such operations form a "family algebra," and there are interesting algorithms to implement the operations of family algebra as operations on ZDDs.

Family algebra is a relatively new topic that is just beginning to be understood. Examples will be given of applications to (i) families of words in a dictionary; (ii) families of patterns that tile a shape; (iii) families of cycles and paths in a graph or network.

Bio

Donald E. Knuth (B.S. and M.S., Case Institute of Technology 1960; Ph.D., California Institute of Technology 1963) is Professor Emeritus of The Art of Computer Programming at Stanford University, where he supervised the Ph.D. dissertations of 28 students since becoming a professor in 1968. He is the author of numerous books, including three volumes (so far) of The Art of Computer Programming, five volumes of Computers & Typesetting, and a non-technical book entitled 3:16 Bible Texts Illuminated. His software systems TeX and Metafont are extensively used for book publishing throughout the world.

He is a member of the American Academy of Arts and Sciences, the National Academy of Sciences, and the National Academy of Engineering, and he is a foreign associate of the French, Norwegian, Bavarian, and Russian science academies as well as the Royal Society of London. He received the Turing Award from the Association for Computing Machinery in 1974; the National Medal of Science from President Carter in 1979; the Steele Prize from the American Mathematical Society in 1986; the Adelsköld Medal from the Royal Swedish Academy of Sciences in 1994; the Harvey Prize from the Technion of Israel in 1995; the John von Neumann Medal from the Institute of Electrical and Electronic Engineers in 1995; and the Kyoto Prize from the Inamori Foundation in 1996.

He holds honorary doctorates from Oxford University, the University of Paris, the Royal Institute of Technology in Stockholm, the University of St. Petersburg, the University of Marne-la-Vallée, Masaryk University, St. Andrews University, Athens University of Economics and Business, the University of Macedonia in Thessaloniki, the University of Tübingen, the University of Oslo, the University of Antwerp, the Swiss Federal Institute of Technology in Zürich, the University of Bordeaux, and nineteen colleges and universities in America.

More information about Donald E. Knuth.