The purpose of this thesis is to give a survey of the methods currently used to solve the numerical eigenvalue problem for real symmetric matrices. On the basis of the advantages and disadvantages inherent in the various methods, it is concluded that Householder's method is the best. Since the methods of Givens, Lanczos, and Householder use the Sturm sequence bisection algorithm as the final stage, a complete theoretical discussion of this process is included. Error bounds from a floating point error analysis (due to Ortega), for the Householder reduction are given. In addition, there is a complete error analysis for the bisection process. / Science, Faculty of / Mathematics, Department of / Graduate

The managements of integrated forest products firms in British Columbia and elsewhere must make many involved decisions in order to effectively plan the intermediate-range (one year) operations of their firms. The production systems of the forest industry involve complex allocations of many resources among competing activities. In addition, interdependencies between processes exist and frequently products are transferred between divisions. This thesis explains and illustrates how linear programming may be used to assist managements of integrated forest products firms in their planning activities. In particular, the linear programming technique is used to find suggested optimal operating plans for the total range of the firm's operations — from woodlands, through production plants to sales operations. The specific details of model construction, the mathematical programming, and the problems encountered are illustrated by a hypothetical forest products firm. A linear model has been developed for the hypothetical firm, computer solutions have been interpreted, and suggestions have been made for implementation of results. Although the author does not attempt to quantify the value of linear programming to a firm's profitability, the many explanations and illustrations serve to support the view that managerial effectiveness is enhanced through use of the technique. Decisions regarding intermediate-range planning can be made by managers with an increased understanding of the complex relationships within their firm's production and sales functions. In presenting this thesis in partial fulfilment of the requirements for an advanced degree at the University of British Columbia, I agree that the Library shall make it freely available for reference and Study. I further agree that permission for extensive copying of this thesis for scholarly purposes may be granted by the Head of my Department or by his representatives. It is understood that copying or publication of this thesis for financial gain shall not be allowed without my written permission. / Business, Sauder School of / Graduate

A study in game-playing programming is made using the game of pentominoes which has a very large branching factor and where there exists almost no precise, factual information to guide the conduct of the play. The difficulties encountered imply that some apparent advantages of heuristic techniques are more heavily problem-dependent than is usually conceded. A guiding device capable of learning is incorporated which significantly improves the program's play in competition with versions lacking it and shows subjective improvement with human competition. / Science, Faculty of / Computer Science, Department of / Graduate

A theoretical technique for the minimization of a function by a random search is presented. The search is a modification of the Optimum Step Size Random Search of Schumer and Steiglitz to include reversals. A theory for updating the step size is presented upon which an implementation of a search algorithm suitable for high-dimensional functions with no requirements for derivative evaluations is based. / Applied Science, Faculty of / Electrical and Computer Engineering, Department of / Graduate

Some portions of real-time computer process control software can be programmed with special purpose high-level languages. A translator writing system for minicomputers is developed to aid in writing translators for those languages. The translator writing system uses an LR(1) grammar analyzer with an LR(1) skeleton parser. XPL is used as the source language for the semantics. An XPL to intermediate language translator has been written to aid in the translation of XPL programs to minicomputer assembly language. A simple macro generator must be written to translate intermediate language programs into various minicomputer assembly languages. / Applied Science, Faculty of / Electrical and Computer Engineering, Department of / Graduate

The purpose of this thesis is to develop a solution to the problem of determining the minimal spanning tree with degree restraints for a given non-directional graph. Section 1 gives an introduction to the problem. A set of definitions describing the graphical terminology used in the body of the thesis, is presented along with a description of the problem. At the end of this section a few applications of the problem are given. Section 2 outlines the method of solution used. The algorithm incorporates a branch and bound technique and this problem solving method is discussed in general in the first part of the section. Some other applications of branching and bounding are also discussed. Next, the complete algorithm is described along with a proof of optimality. A sample problem is worked through to illustrate the method of solution. Two different minimal spanning tree algorithms, one by R.C. Prim, the other by J.B. Kruskal, are used in the main core of the solution algorithm. These two approaches are discussed with the aid of a sample problem, at the end of Section 2. Computer programs were written to test the algorithms. Several sets of data were compiled for various sizes of graphs and values of degree restrictions. The results of these runs were tabulated and are discussed in Section 3. Next, a comparison is made of the method discussed here and a solution involving linear programming. Section 3 also presents some useful heuristic approaches at sub-optimization which effectively reduce the amount of computation. Section 4 summarizes the results of Section 3 and indicates the best approach to use for a specific problem. / Science, Faculty of / Computer Science, Department of / Graduate

A combination of many grades of veneer may be jointly produced by peeling any one type of logs. This means that the plywood manufacturer can not really know the profit margins of the panels he produces. And for most of the manufacturers, the cost of the logs constitutes about 65% of the total cost of producing the plywood panels. Consequently, the manufacturer finds it very difficult to select his sales strategy and to price his panels. The plywood manufacturer also has opportunities to minimize his log cost and processing cost by selecting the right combination of logs to peel and using the right constructions in laying up the panels. Linear programming techniques are used in this study to provide an approach to the above mentioned problems for a selected plywood manufacturer. Through this, it is hoped as well to provide an examination of the way to use linear programming techniques and an evaluation of their usefulness as management tools in plywood manufacturing. A survey of the reported experience of some plywood manufacturers indicated that the use of L. P. had been instrumental in saving some hundreds of thousands of dollars per annum for some manufacturers. An L. P. model was constructed for the largest of the four mills of the Case Company, using the operating situations predicted for the year 1967. Such problems (and their solutions) as were encountered in defining, identifying and measuring the variable process costs and the need for making simplifying assumptions were examined. The L. P. model seeks to optimize the choice of panel output, the choice of log input and the choice of panel constructions simultaneously because these three decisions are interrelated and somewhat interdependent. The L. P. analysis suggests that about 30% of the dollar sales of the Case Mill in 1967 were made in unprofitable (thin) panels. Even after allowing for possible over estimation in measuring the variable processing cost, this may call for a thorough re-examination of the sales strategy and the panel pricing system. To produce the panel output selected for 1967, the best log combination apparently includes the use of a much higher proportion of Fir Peeler #2 and Sawlog #3, Interior Fir and Hemlock-Balsam Mix than was used by the Company in its mill. Also, the model suggests proportions of Fir Peeler #1, #4 and S. F.P. might be much lower than what the Company tended to use. These tentative findings may have significant implications for choosing log acquisition policies. The model suggests the choice in panel construction may be to peel Peeler logs for .104" high quality veneer, Interior Fir for .130" veneer and other low quality logs for .171" core veneer. It also suggests down-grading some veneer and using some subsidiary panel constructions so as to utilize fully the total supply of veneer from the logs peeled. The usefulness of the L.P. analysis is fully realized by making a comprehensive post-optimal analysis of the sensitivity of the optimality of the solution to various changes in the log supply and/or panel demand and/or processing cost situations. This analysis may enable the company to determine which of the operating factors seem crucial in determining the profitability of the panels and what may constitute the best log combination to use. From this, the manufacturer could possibly know when and how to adapt his program of operation in response to any future changes in (or any revision in the forecast of) the operating situation. This analysis is also helpful in gauging the importance of the assumptions made when constructing the model. No comprehensive sensitivity analysis was carried out in this study. However, recommendations regarding appropriate post-optimal analyses are presented. Lastly, the study concludes by presenting an L. P. model of possible use to analyze the four mills of the Company together, recognizing the possibilities of specialization and cooperation among the mills. / Business, Sauder School of / Graduate

Three recent random search algorithms are compared on the basis of efficiency, and on the basis of sensitivity to noise, scaling and the number of variables. A general discussion of random search methods points out their advantages and disadvantages in relation to deterministic methods. A new random vector generator is described in the appendix. / Applied Science, Faculty of / Electrical and Computer Engineering, Department of / Graduate

The present Thesis addresses the problem of specification and verification of communicating systems with value passing. We assume that such systems are described in the well-known Calculus of Communicating Systems, or rather, in its value passing version. As a specification language we propose an extension of the Modal μ-Calculus, a poly-modal first-order logic with recursion. For this logic we develop a proof system for verifying judgements of the form b ⊢ Ε : Φ where E is a sequential CCS term and b is a Boolean assumption about the value variables occurring free in E and Φ. Proofs conducted in this proof system follow the structure of the process term and the formula. This syntactic approach makes proofs easier to comprehend and machine assist. To avoid the introduction of global proof rules we adopt a technique of tagging fixpoint formulae with all relevant information needed for the discharge of reoccurring sequents. We provide such tagged formulae with a suitable semantics. The resulting proof system is shown to be sound in general and complete (relative to external reasoning about values) for a large class of sequential processes and logic formulae. We explore the idea of using tags to three different settings: value passing, extended sequents. and negative tagging. / Graduate

Kowalski's connection graph method provides a representation for logic programs which allows for the incorporation of better procedural control techniques than standard logic programming languages. A proposed search strategy for visual recognition which combines top-down and bottom-up techniques has been incorporated in a connection graph implementation. The connection graph representation also allows for the natural incorporation of constraint satisfaction techniques in logic programming. Kowalski's approach to incorporating constraint satisfaction techniques in connection graphs is examined in detail. It is shown that his approach is not efficient enough to be used as a general preprocessing algorithm but that a modified version may be of use. Increased control of search and the incorporation of consistency techniques increase the procedural adequacy of logic programs for representing knowledge without compromising the descriptive capacity of the form. / Science, Faculty of / Computer Science, Department of / Graduate