perm filename SEVEN.MSS[BIB,CSR]1 blob sn#661816 filedate 1982-06-01 generic text, type T, neo UTF8

@make(PublicationOrderForm,Number 17,AnnouncementDate "June 1982") @begin(center) List Number 17 @end(center) @Entry(Code "STAN-CS-82-901", Title "Optimal Font Caching", Author "David R. Fuchs and Donald E. Knuth", Price "$2.60", Mprice "$2.00", Note "19 pages", Date "May 1982") An efficient algorithm is presented for communicating letter-shape information from a high-speed computer with a large memory to a typesetting device that has a limited memory. The encoding is optimum, in the sense that the total time for typesetting is minimized, using a model that generalizes well-known ``demand paging'' strategies to the case where changes to the cache are allowed before the associated information is actually needed. Extensive empirical data shows that good results are obtained even when difficult technical material is being typeset on a machine that can store information concerning only 100 characters. The methods of this paper are also applicable to other hardware and software caching applications with restricted lookahead. @Entry(Code "STAN-CS-82-902", Title "Special Relations in Program-Synthetic Deduction", Author "Zohar Manna and Richard Waldinger", Price "$4.25", Mprice "$2.00", Note "75 pages", Date "May 1982",) Program synthesis is the automated derivation of a computer program from a given specification. In the deductive approach, the synthesis of a program is regarded as a theorem-proving problem. The desired program is constructed as a byproduct of the proof. This paper presents a formal deduction system for program synthesis, with special features for handling equality, the equivalence connective, and ordering relations. In proving theorems involving the equivalence connective, it is awkward to remove all the quantifiers prior to proving the theorem. The system therefore deals with partially skolemized sentences, in which some of the quantifiers may be left in place. A rule is provided for removing individual quantifiers when required after the proof is underway. The system is also nonclausal; i.e., the theorem does not need to be put into conjunctive normal form. The equivalence, implication, and other connectives may be left intact. @Entry(Code "STAN-CS-82-903", Title "Coloring Maps and the Kowalski Doctrine", Author "John McCarthy", Price "$2.25", Mprice "$2.00", Note "8 pages", Date "April 1982") It is attractive to regard an algorithm as composed of the logic determining what the results are and the control determining how the result is obtained. Logic programmers like to regard programming as controlled deduction, and there have been several proposals for controlling the deduction expressed by a PROLOG program and not always using PROLOG's normal backtracking algorithm. The present note discusses a map coloring program proposed by Pereira and Porto and two coloring algorithms that can be regarded as control applied to its logic. However, the control mechanisms required go far beyong those that have been contemplated in the PROLOG literature. @Entry(Code "STAN-CS-82-904", Title "Time-Split Methods for Partial Differential", Author "Randall John LeVeque", Price "$5.05", Mprice "$2.00", Note "102 pages", Date "April 1982") This thesis concerns the use of time-split methods for the numerical solution of time-dependent partial differential equations. Frequently the differential operator splits additively into two or more pieces such that the corresponding subproblems are each easier to solve than the original equation, or are best handled by different techniques. In the time-split method the solution to the original equation is advanced by alternately solving the subproblems. In this thesis a unified approach to splitting methods is developed which simplifies their analysis. Particular emphasis is given to splittings of hyperbolic problems into subproblems with disparate wave speeds. Three main aspects of the method are considered. The first is the accuracy and efficiency of the time-split method relative to unsplit methods. We derive a general expression for the splitting error and use it to compute the overall truncation error for the time-split method. This is then used to analyze its efficiency, measured by the amount of work required to obtain a given accuracy. The second topic is stability for split methods. After a demonstration that in general the product of two stable operators need not be stable, some important classes of hyperbolic splittings are identified for which the product of stable approximate solution operators is in fact stable. The final topic is the proper specification of boundary data for the intermediate solutions, e.g., the solution obtained after solving only one of the subproblems. A procedure is described which, for many problems, can be used to transform the given boundary conditions for the original equation into arbitrarily accurate boundary conditions for the intermediate solutions. Stability of the initial-boundary value problem is also discussed. The main emphasis is on hyperbolic problems, and the one-dimensional shallow water equations are used as a specific example throughout. The final chapter is devoted to some other applications of the theory. Two-dimensional hyperbolic problems, convection-diffusion equations, and the Peaceman-Rachford ADI method for the heat equation are considered. @Entry(Code "STAN-CS-82-905", Title "Wave Propagation and Stability for Finite Difference Schemes", Author "Lloyd N. Trefethen", Price "$8.20", Mprice "$2.00", Note "207 pages", Date "April 1982") This dissertation investigates the behavior of finite difference models of linear hyperbolic partial differential equations. Whereas a hyperbolic equation is nondispersive and nondissipative, difference models are invariably dispersive, and often dissipative too. We set about analyzing them by means of existing techniques from the theory of dispersive wave propagation, making extensive use in particular of the concept of it group velocity, the velocity at which energy propagates. The first three chapters present a general analysis of wave propagation in difference models. We describe systematically the effects of dispersion on numerical errors, for both smooth and parasitic waves. The reflection and transmission of waves at boundaries and interfaces are then studied at length. The key point for this is a distinction introduced here between it leftgoing and it rightgoing signals, which is based not on the characteristics of the original equation, but on the group velocities of the numerical model. The last three chapters examine it stability for finite difference models of it initial boundary value problems. We show that the abstract stability criterion of Gustafsson, Kreiss, and Sundstrom (GKS) is equivalent to the condition that the boundary permit no rightgoing signals in the absence of leftgoing ones. Wave propagation arguments yield a proof that for the typical instability of ``strictly rightgoing'' type, one has unstable growth in the l2 norm, not just in the complicated GKS norm. We prove that this growth is at least proportional to the number of time steps n for models driven by boundary data, and to sqrt n for models driven by initial data. We show further that most GKS-unstable boundaries exhibit it infinite reflection coefficients, which gives an alternative explanation of instability with respect to initial data. We conjecture that when an infinite reflection coefficient is present, the unstable growth rate increases from sqrt n to n. Throughout the dissertation, wave propagation ideas are also applied to various more specialized stability problems. We identify new classes of unstable formulas, including some in two space dimensions; derive new results relating stability to dissipativity; give new estimates on unstable growth for problems with two boundaries or interfaces; examine borderline cases that are GKS-unstable but l2-stable or nearly so; and present an explanation based on dispersion for known results on instability in Lp norms. @Entry(Code "STAN-CS-82-906", Title "Truncated-Newton Methods", Author "Stephen G. Nash", Price "$5.60", Mprice "$2.00", Note "120 pages", Date "May 1982") The problem of minimizing a real-valued function F of n variables arises in many contexts. Most methods for solving this problem have their roots in Newton's method, i.e. they are based on approximating F by a quadratic function Q. If the number of variables n is large, then Newton's method can be problematic since it requires the computation and storage of the Hessian matrix of second derivatives. We examine a flexible class of methods, called truncated-Newton methods. They are based on approximately minimizing the quadratic function Q using an iterative scheme. A truncated-Newton algorithm is made up of two sub-algorithms: an outer non-linear algorithm controlling the entire minimization, and an inner linear algorithm for approximately minimizing Q. The most important choice is the selection of the inner algorithm. When the Hessian matrix is known to be positive-definite everywhere, then the basic linear conjugate-gradient algorithm can be used. If not, Q may not have a minimum. We have used the correspondence between the linear conjugate-gradient algorithm and the Lanczos algorithm for tridiagonalizing a symmetric matrix to develop methods for the indefinite case. The performance of the inner algorithm can be greatly improved through the use of preconditioning strategies. A number of preconditioning strategies are derived here. Numerical tests show that a carefully chosen truncated-Newton method can perform significantly better than the best non-linear conjugate-gradient algorithms available today. This is important since the two classes of methods have comparable storage and operation counts, and they are the only methods available for solving many large-scale problems. @Entry(Code "STAN-CS-82-907", Title "Combinatorial Algorithms I", Author "Ernst W. Mayr", Price "$4.50", Mprice "$2.00", Note "83 pages", Date "May 1982") This report is an edited collection of the class notes prepared for course 253A of the same title which was taught by the author at the Department of Computer Science at Stanford University in the Winter Quarter 1982. The topics selected for an covered during the first part of this two quarter graduate course were Higher Level Data Structures, Selection, Minimum Spanning Trees, Path Compression, Pattern Matching in Strings, Searching Graphs with Applications, Maximum Matchings in Graphs, and Maximum Flow in Networks. @newpage @Entry(Code "STAN-CS-82-908", Title "Neomycin-Reconfiguring A Rule-Based Expert System for Application to Teaching", Author "Willlam J. Clancey and Reed Letsinger", Price "$2.40", Mprice "$2.00", Note "12 pages", Date "May 1982") NEOMYCIN is a medical consultation system in which MYCIN's knowledge base is reorganized and extended for use in GUIDON, a teaching program. The new system constitutes a psychological model for doing diagnosis, designed to provide a basis for interpreting student behavior and teaching diagnostic strategy. The model separates out kinds of knowledge that are procedurally embedded in MYCIN's rules and so inaccessible to the teaching program. The key idea is to represent explicitly and separately: a domain-independent diagnostic strategy in the form of meta-rules, knowledge about the structure of the problem space, causal and data/hypothesis rules, and world facts. As a psychological model, NEOMYCIN captures the forward-directed, "compiled association" mode of reasoning that characterizes expert behavior. Collection and interpretation of data are focused by the "differential" or working memory of hypotheses. Moreover, the knowledge base is broadened so that GUIDON can teach a student when to consider a specific infectious disease and what competing hypotheses to consider, essentially the knowledge a human would need in order to use the MYCIN consultation system properly. @Entry(Code "STAN-CS-82-909", Title "Plan Recognition Strategies in Student Modeling: Prediction and Description", Author "Bob London and William J. Clancey", Price "$2.40", Mprice "$2.00", Note "13 pages", Date "May 1982") This paper describes the student modeler of the GUIDON2 tutor, which understands plans by a dual search strategy. It first produces multiple predictions of student behavior by a model-driven simulation of the expert. Focused, data-driven searches then explain incongruities. By supplementing each other, these methods lead to an efficient and robust plan understander for a complex domain. @Entry(Code "STAN-CS-82-910", Title "Exploration of Teaching and Problem-Solving Strategies, 1979-1982", Author "Willlam J. Clancey and Bruce G. Buchanan", Price "$2.50", Mprice "$2.00", Note "17 pages", Date "May 1982") This is the final report for ONR Contract N-00014-79-C-0302, covering the period of 15 March 1979 through 14 March 1982. The goal of the project was to develop methods for representing teaching and problem-solving knowledge in computer-based tutorial systems. One focus of the work was formulation of principles for managing a case method tutorial dialogue; the other major focus was investigation of the use of a production rule representation for the subject material of tutorial program. The main theme pursued by this research is that representing teaching and problem-solving knowledge separately and explicitly enhances the ability to build, modify and test complex tutorial programs. @Entry(Code "STAN-CS-82-911", Title "Bibliography of Stanford Computer Science Reports 1963-1982", Author "Barbara J. Roberts and Irris Marashian", Price "$4.00", Mprice "$2.00", Note "61 pages", Date "May 1982") This is a bibliography of Computer Science Reports from 1963 through 1982. Each report is listed with an availability listing and the cost. @send(order <@b{@\Sub-totals@\@Ux(@hsp(.5 inch))@\@Ux(@hsp(.5 inch))}>) @send(order <@b{@\Publications total@\@Ux(@hsp (.5 inch))}>) @send(order <@b{@\Sales tax@\@Ux(@hsp (.5 inch))}>) @send(order <@b{@\Total enclosed@\@Ux(@hsp (.5 inch))}>)