perm filename NAOMI[BIB,CSR] blob sn#398064 filedate 1978-11-27 generic text, type C, neo UTF8

COMMENT ⊗ VALID 00013 PAGES C REC PAGE DESCRIPTION C00001 00001 C00003 00002 .DEVICE XGP C00004 00003 .once center C00006 00004 STAN-CS-79-691 THE CONSTRUCTION OF INITIAL DATA FOR HYPERBOLIC SYSTEMS C00010 00005 HPP-77-39 MODELS OF LEARNING SYSTEMS C00012 00006 STAN-CS-79-693 A CLASS OF SOLUTIONS TO THE GOSSIP PROBLEM C00014 00007 STAN-CS-79-694 COMPUTER SCIENCE AT STANFORD, 1977-1978 C00016 00008 AIM-321 RECENT RESEARCH IN ARTIFICIAL INTELLIGENCE AND FOUNDATIONS C00017 00009 HPP-78-22 CONSIDERATIONS FOR MICROPROCESSOR-BASED TERMINAL DESIGN C00020 00010 STAN-CS-79-697 ON THE LINEAR LEAST SQUARES PROBLEM WITH A QUADRATIC C00022 00011 STAN-CS-79-698 IMPERICAL ESTIMATES OF PROGRAM ENTROPY C00025 00012 HPP-78-23 SACON: A KNOWLEDGE-BASED CONSULTANT FOR STRUCTURAL ANALYSIS C00028 00013 .begin center C00031 ENDMK C⊗; .DEVICE XGP; .SINGLESCRIPT .SPACING 10*5 MILLS; .PAGE FRAME 47 HIGH 80 WIDE .TITLE AREA HEADING LINES 1 TO 2 .AREA TEXT LINES 3 TO 47 .every heading (January,1979 Reports,{Page}) . .turn on "↔" for "→" .turn on "%,π,α,#,&,∂,↑,↓,[,]" .turn on "∩" for "↑" .turn on "∪" for "↓" .font 1 "SAIL25"; .SELECT 1 . .AT 8 ⊂ONCE INDENT 5;⊃ .at "@" ⊂"####"⊃ . .PLACE TEXT; . .next page .once center MOST RECENT CS REPORTS - JANUARY 1979 @Listed below are abstracts of the most recent reports published by the Computer Science Department of Stanford University. @TO REQUEST REPORTS: Check the appropriate places on the enclosed order form, and return the entire order form page (including mailing label) by January 26, 1979. In many cases we can print only a limited number of copies, and requests will be filled on a first come, first serve basis. If the code (FREE) is printed on your mailing label, you will not be charged for hardcopy. This exemption from payment is limited primarily to libraries. (The costs shown include all applicable sales taxes. PLEASE SEND NO MONEY NOW, WAIT UNTIL YOU GET AN INVOICE.) @ALTERNATIVELY: Copies of most Stanford CS Reports may be obtained by writing (about 2 months after MOST RECENT CS REPORTS listing) to NATIONAL TECHNICAL INFORMATION SERVICE, 5285 Port Royal Road, Springfield, Virginia 22161. Stanford Ph.D. theses are available from UNIVERSITY MICROFILMS, 300 North Zeeb Road, Ann Arbor, Michigan 48106. .begin nofill -------------------------------------------------------------------------- -------------------------------------------------------------------------- STAN-CS-79-691 THE CONSTRUCTION OF INITIAL DATA FOR HYPERBOLIC SYSTEMS FROM NONSTANDARD DATA Author: Kenneth P. Bube↔(Thesis) .end @Abstract: We study the first order systems of hyperbolic partial differential equations with periodic boundary conditions in the space variables for which complete initial data are not available. We suppose that we can measure u↑I , the first j components of a solution u of the system, perhaps with its time derivatives, but cannot measure u∩[II] , the rest of the components of u , completely and accurately at any time level. Such problems arise in geophysical application where satelites are used to collect data. We consider two questions. How much information do we need to determine the solution u uniquely in a way which depends continuously on the data? How do we use these data compuationally to obtain complete initial data at some time level? @We investigate several approaches to answering these questions. We show that under certain hypotheses u∩[II] at the initial time is determined uniquely by and depends continuously on the data obtained by measuring either u↑I over a whole time interval or u↑I and its first time derivative at the initial time, together ith either u∩[II] on a hyperplane in space of one lower dimension or a finite number of Fourier coefficients of u∩[II] at the initial time. Our results demonstrate that it is possible to reduce the data requirements of u∩[II] if sufficient information about u↑I is available. @One appliction we examine is the effect of the Coriolis term in the linearized shallow water equations on the possibility of recovering the wind fields from the geopotential height. @We present algorithms and computational results for these approaches for a model two-by-two system, and examine the method for intermittent updating currently being used in numerical weather prediction as a method for the assimilation of data. Our results suggest that the use of different frequencies of updating is important to avoid slow convergence. .begin nofill No. of pages: 119 Available in microfiche only. -------------------------------------------------------------------------- HPP-77-39 MODELS OF LEARNING SYSTEMS Authors: Bruce G. Buchanan, Tom M. Mitchell, Reid G. Smith & C. Richard Johnson Jr. .end @Abstract: The terms adaptation, learning, concept-formation, induction, self-organization, and self-repair have all been used in the context of learning system (LS) research. In this article, three distinct approaches to machine learning and adaptation are considered: (i) the adaptive control approach, (ii) the pattern recognition approach, and (iii) the artificial intelligence approach. @Progress in each of these areas is summarized in the first part of the article. In the next part a general model for learning systems is presented that allows characterization and comparison of individual algorithms and programs in all these areas. The model details the functional components felt to be essential for any learning system, independent of the techniques used for its construction, and the specific environment in which it operates. Specific examples of learning systems are described in terms of the model. .begin nofill No. of pages: 38 Cost: $ 2.80 -------------------------------------------------------------------------- STAN-CS-79-693 A CLASS OF SOLUTIONS TO THE GOSSIP PROBLEM Author: Douglas B. West .end @Abstract: We characterize and count optimal solutions to the gossip problem in which no one hears his own information. That is, we consider graphs with n vertices where the edges have a linear ordering such that an increasing path exists from each vertex to every other, but there is no increasing path from any vertex to itself. Such graphs exist only when n is even, in which case the fewest number of edges is 2n-4, as in the original gossip problem. We characterize optimal solutions of this sort (NOHO-graphs) using a correspondence with a set of permutations and binary sequences. This correspondence enables us to count these solutions and several subclasses of solutions. The numbers of solutions in each class are simple powers of 2 and 3, with exponents determined by n. We also show constructively that NOHO-graphs are planar and Hamiltonian, and we mention applications to related problems. .begin nofill No. of pages: 61 Cost: $ 3.45 -------------------------------------------------------------------------- STAN-CS-79-694 COMPUTER SCIENCE AT STANFORD, 1977-1978 Editor: Jonathan King .end @Abstract: This report is a review of Stanford Computer Science Department activities for the academic year 1977-78. The report includes:## (1) The Chairman's overview of the important events of the year, (2) Recent activities and interests of faculty members and research associates arranged by research specialty, (3) Advanced doctoral students in each specialty and their research topics, (4) Recipients of M.S. and Ph.D. degrees, (5) Speakers at seminar and colloquia series, and (6) Bibliography of Computer Science Department technical reports. .begin nofill No. of pages: 27 Cost: $ 2.50 -------------------------------------------------------------------------- AIM-321 RECENT RESEARCH IN ARTIFICIAL INTELLIGENCE AND FOUNDATIONS OF PROGRAMMING Authors: Lester Earnest et al. .end @Abstract: Summarizes recent research in the following areas: artificial intelligence and formal reasoning, mathematical theory of computation and program synthesis, program verification, image understanding, and knowledge based programming. .begin nofill No. of pages: 94 Cost: $ 4.35 -------------------------------------------------------------------------- HPP-78-22 CONSIDERATIONS FOR MICROPROCESSOR-BASED TERMINAL DESIGN Authors: Reid G. Smith & Tom M. Mitchell .end @Abstract: We discuss the design of hardware and software for inexpensive microprocessorr-based terminal/microcomputers. Such devices are fundamentally microcomputers that have been adapted, with specialized software, to operate as remote terminals for a host compuer. @The discussion centers on a specific video terminal designed and constructed by the authors. This terminal is based on the INTEL 8080 microprocessor and is equipped with software sufficient to emulate the characteristics of standard video terminals required by several available SCREEN-ORIENTED text editors in common use at sites throughout the ARPAnet. @We have found that the microprocessor adequately serves as the controller for such terminals, and that a SOFTWARE-BASED approach to the design of such terminals offers substantial advantages in capabilities, flexibility, and cost over the HARDWARE-BASED approach. We suggest guidelines for future designs of microprocessor-based terminals on the basis of our experience designing and using the terminal described here. In order to take full advantage of the flexibility afforded by microprocessor-based designs, we have implemented the capability to DOWNLOAD and execute 8080 programs written and assembled on a host computer. This allows the user to customize and extend the microcomputer with the software development tools and mass storage provided by the host computer. The terminal is thus a complete, stan-alone microcomputer system specially configured for its role as a terminal. .begin nofill No. of pages: 14 Cost: $ 2.10 -------------------------------------------------------------------------- STAN-CS-79-697 ON THE LINEAR LEAST SQUARES PROBLEM WITH A QUADRATIC CONSTRAINT Author: Walter Gander .end @Abstract: In this paper we present the theory and practical computational aspects of the linear least squares problem with a quadratic constraint. New theorems characterizing properties of the solutions are given and extended for the problem of minimizing a general quadratic function subject to a quadratic constraint. For two important regularization methods we formulate dual equations which proved to be very useful for the application os smoothing of datas. The resulting algorithm is a numerically stable version of an algorithm proposed by Ruthishauser. We show also how to choose a third order iteration method to solve the secular equation. However we are still far away from a foolproof machine independent algorithm. .begin nofill No. of pages: 120 Available in microfiche only. -------------------------------------------------------------------------- STAN-CS-79-698 IMPERICAL ESTIMATES OF PROGRAM ENTROPY Author: Richard E. Sweet↔(thesis) .end @Abstract: With the trend toward small computers, there is an increased emphasis on compact object programs. This can be accomplished by using an encoding that is specialized for a given programming language. This thesis explores the question of a lower bound for the size of an encoding for "typical" programs. The approach is to apply the principles of information theory to an empirical sample of programs. A collection of 114 Mesa programs, comprising approximately a million characters of source text, is analyzed. @The representation of programs used for analysis is that of trees. The concept of a Markov source is defined for trees in several ways, and the entropy of these sources is estimated. A Markov source of non-uniform order is defined, which has better empirical characteristics for the tree sources, and can also be useful for standard sequential sources. For the Mesa sample studied, an information content of approximately one half bit per character of source is estimated. In addition, the tree data can be used to address several questions of programming style and static variable usage. .begin nofill No. of pages: 167 Cost: $ 6.40 -------------------------------------------------------------------------- HPP-78-23 SACON: A KNOWLEDGE-BASED CONSULTANT FOR STRUCTURAL ANALYSIS Authors: James Bennet, Lewis Creary, Robert Englemore & Robert Melosh .end @Abstract: In this report we describe an application of artificial intelligence (AI) methods to structural analysis. We describe the development and (partial) implementation of an "automated consultant" to advise non-expert engineers in the use of a general-purpose structural analysis program. The analysis program numerically simulates the behavior of a consultant, called SACON (Structural Analysis CONsultant), is based on a version of the MYCIN program [Shortliffe 74], originally developed to advise physicians in the diagnosis and treatment of infectious deseases. The domain-specific knowledge in MYCIN is represented as situation-action rules, and is kept independent of the "inference engine" that uses the rules. By substituting structural engineering knowledge for the medical knowledge, the program was converted easily from the domain of infectious diseases to the domain of structural analysis. .begin nofill No. of pages: 65 Cost: $ 3.55 -------------------------------------------------------------------------- -------------------------------------------------------------------------- .END .begin center Available from Stanford Systems Optimization Laboratory .end .begin nofill SOL 78-19 A BIDIAGONALIZATION ALGORITHM FOR SPARSE LINEAR EQUATIONS AND LEAST-SQUARES PROBLEMS Authors: Christopher C. Paige & Michael A. Saunders .end @Abstract: A method is given for solving Ax = b and min||Ax-b||↓2 where the matrix A is large and sparse. The method is based on the bidiagonalization procedure of Golub and Kahan. It is analytically equivalent to the method of conjugate gradients (CG) but possesses more favorable numerical properties. The Fortran implementation of the method (subroutine LSQR) incorporates reliable stopping criteria and provides estimates of various quantities including standard errors for x and the condition number of A. Numerical tests are described comparing LSQR with several other CG algorithms. Further results for a large practical problem illustrate the effect of pre-conditioning least-squares problems using a sparse LU factorization of A. Available by writing directly to: Gail L. Stein, Systems Optimization Laboratory, Department of Operations Research, Stanford University, Stanford, California 94305 U.S.A. .BEGIN NOFILL -------------------------------------------------------------------------- --------------------------------------------------------------------------