Computer Sciences Commons^™

Genesis Of An Expert System For Umr Degree Auditing, Ruth Sue Dare

Masters Theses

"This paper describes the features, design, and development of an expert system for degree auditing at the University of Missouri--Rolla. It summarizes artificial intelligence as it is known today while specifically addressing expert systems. It describes selected expert systems currently in existence.

The present audit procedure utilized at the University of Missouri--Rolla is discussed. A description is given of the design and development of an expert system, written in LISP, to conduct a degree audit. Finally there are concluding remarks which include an analysis of the system and a discussion of possible system enhancement"--Abstract, page ii.

Mica: Prototyping An Expert System Consultant, Joseph Howard Marchal

Masters Theses

"The United States, as the world's largest producer and consumer of scrap and flake mica, has an obvious economic interest in applications of artificial intelligence technology that would expedite beneficiation of mica. In the fall of 1985, personnel of the Tuscaloosa and Rolla research centers of the Bureau of Mines and of the University of Missouri--Rolla, Institute for Artificial Intelligence started the following long term research project: Develop an Expert System Consultant for the three basic stages of mica beneficiation: Stage 1: characterization of the material; Stage 2: treatment to obtain a concentrate; and Stage 3: evaluation of the resulting …

A Data Structure For The Use Of Patterns In The Perceptual Ordering Of The Game Of Chess, Russ L. Hanna

Masters Theses

"It is well known that the way one perceives a problem can influence the difficulty of solving the problem in a profound way. In the case of computer chess playing programs, one finds that most programs perceive the game in much the same way. They are all based on Shannon's original proposal for chess playing programs. His approach was to generate all of the possible combinations of moves up to a certain number of plays and then a subset of all combinations to a deeper level thereafter. Each of these moves would then be evaluated as to its relative worth. …

A Computerized Audio-Visual Speech Model, Joaquin Alberto Vila Ruiz

Masters Theses

"This thesis describes an expert system able to animate (graphically) and reproduce (acoustically) a text in any language which uses the Latin alphabet. A rule editor has been developed to create and modify the set of letter-to-sound rules of the target language. A parser has been implemented to apply the set of rules and translate text-to-speech. Each phoneme has a unique sound and thus requires its particular positioning of the vocal organs which are displayed in two different projections: a front view and a profile cross view of a human face in synchronization with the output sounds of the speech …

A Semantic Basis For Parallel Algorithm Design, Roger E. Eggen

Doctoral Dissertations

"As computing demands increase, emphasis is being placed on parallel architectures- To efficiently use parallel machines, software must be designed to take advantage of these machines. This research concentrates on an abstraction of algorithm design to permit the expression of parallel programs. The abstraction emphasizes thought about algorithms at a high level as opposed to algorithm implementation at a statement level. A model based on data flow allows algorithm expression using flow diagrams. The model specifies operating system requirements that support parallel programming at a module level. Paths are used to carry data between modules. Data enter modules through ports. …

Industrial Simulation With Animation, Edward T. Hammerand, Chung You Ho

Computer Science Technical Reports

This thesis examines and evaluates the new simulation language PCModel. Prior to the arrival of PCModel, simulation via computer typically resulted in pages of statistics compiled over the duration of the simulation. PCModel's approach is to simulate the model on the display before the user in real time. Additionally, user interaction is supported to allow changes to be made throughout the simulation run.

The evaluation of PCModel is accomplished through inspection of a pair of examples already simulated in a conventional simulation language. The examples show the relative strong and weak points of the language, as well as demonstrating how …

Method And Apparatus For Performing Hashing Operations Using Galois Field Multiplication, John L. Carter, George Markowsky, Mark N. Wegman

Computer Science Faculty Research & Creative Works

The invention comprises a method and apparatus for performing a hashing operation on an N bit number under control of a prespecified N bit hashing constant which comprises performing N/K finite field partial multiplications of the object to be hashed by the hashing constant, utilizing K logic and combinatorial circuits all of which operate in parallel to completely evaluate the number in N/K operations.

Another feature of the present invention is that the hashing constant loaded into the system may be changed at will with a resultant changing of the hashing characteristics to suit a particular class of objects to …

A Monte Carlo Analysis Of The Mincycle Algorithm For Generating Minimal Perfect Hash Functions, Pao-Po Hou, Thomas J. Sager

Computer Science Technical Reports

In this paper, several minimal perfect hashing function generating methods are examined. One of them, the mincycle method by Sager is evaluated by the Monte Carlo method. The results are represented in graphs and tables.

A Parallel Branch And Bound Algorithm For Integer Linear Programming Models, Rochelle L. Boehning, Billy E. Gillett

Computer Science Technical Reports

A parallel branch and bound algorithm is developed for use with MIMD computers to study the efficiency of parallel processors on general integer linear programming problems. The Haldi and IBM test problems and a System Design model are used in the implementation of the algorithm. Initially the algorithm solves the Haldi and IBM test problems on a single processor computer which simulates a multiple processor computer. The algorithm is then implemented on the Denelcor HEP multiprocessor using two of the IBM problems to compare the results of the simulation to the results using an MIMD computer. Finally the algorithm is …

An Algorithm For Parallel Subsumption, Ralph M. Butler, Arlan R. Dekock

Computer Science Technical Reports

Many current automated theorem provers use a refutation procedure based on some version of the principle of resolution. These methods normally lead to the generation of large numbers of new clauses. Subsumption is a process that eliminates the superfluous clauses from the clause space, thus speeding up the proof. The research presented in this thesis is concerned with the design and implementation of a subsumption algorithm which exploits the parallelism provided by a multiprocessor. For portability, all coding is done in the programming language C. Monitors are used as the synchronization mechanism. Correct performance in both a multiprocessor and uniprocessor …

A Parallel Array Scanning Algorithm, Ralph M. Butler, Ralph W. Wilkerson

Computer Science Technical Reports

Suppose we are given a vector X of n real numbers and we want to find the maximum sum found in any contiguous subvector of X. In Jon Bentley's article [l] on algorithm design and technique, a simple vector scanning problem and a series of progressively more efficient algorithms to solve this problem were discussed in some detail. Clearly, any algorithm must visit each location of X at least once and consequently a lower bound on the running time for problem is 0(n), which is in fact attainable as Bentley’s paper illustrates. However, the original motivation for this problem was …

Industrial Simulation With Animation, Edward T. Hammerand

Masters Theses

"This thesis examines and evaluates the new simulation language PCModel. Prior to the arrival of PCModel, simulation via computer typically resulted in pages of statistics compiled over the duration of the simulation. PCModel's approach is to simulate the model on the display before the user in real time. Additionally, user interaction is supported to allow changes to be made throughout the simulation run.

The evaluation of PCModel is accomplished through inspection of a pair of examples already simulated in a conventional simulation language. The examples show the relative strong and weak points of the language, as well as demonstrating how …

A Parallel Branch And Bound Algorithm For Integer Linear Programming Models, Rochelle L. Boehning

Doctoral Dissertations

"A parallel branch and bound algorithm is developed for use with MIMD computers to study the efficiency of parallel processors on general integer linear programming problems. The Haldi and IBM test problems and a System Design model are used in the implementation of the algorithm. Initially the algorithm solves the Haldi and IBM test problems on a single processor computer which simulates a multiple processor computer. The algorithm is then implemented on the Denelcor HEP multiprocessor using two of the IBM problems to compare the results of the simulation to the results using an MIMD computer. Finally the algorithm is …

Survey Of Routing Algorithms For Computer Networks, Lu Yu, Thomas J. Sager

Computer Science Technical Reports

This thesis gives a general discussion of routing for computer networks, followed by an overview of a number of typical routing algorithms used or reported in the past few years. Attention is mainly focused on distributed adaptive routing algorithms for packet switching (or message switching) networks. Algorithms for major commercial networks (or network architectures) are reviewed as well, for the convenience of comparison.

A Simple Method For Organizing Nearly Optimal Binary Search Trees, Joy L. Henderson, John R. Metzner

Computer Science Technical Reports

Improving the efficiency of retrieving information concerns users of computer systems involved in many applications- One way of addressing this concern is to organize a sorted sequence into a binary search tree. Knuth's Algorithm K is a bottom-up organization algorithm that always constructs a binary tree which minimizes average search time. However, the cost of executing Algorithm K is prohibitive for a large tree. The aim of this work is to find a less costly method of organizing sorted sequences into nearly-optimal binary search trees.

We present a top-down organization method which yields better average search times than top-down methods …

The Design And Implementation Of The Programming Language Natural, Alan L. Sparks, Thomas J. Sager, Arlan R. Dekock

Computer Science Technical Reports

This paper reports progress on the development of the programming language Natural, currently under design by Dr. Thomas J. Sager at the University of Missouri--Rolla. Natural is a very high-level language with a mathematical flavor, and includes several concepts relatively uncommon in programming language design.

The text also discusses an implementation on the IBM Personal Computer of Mini-Natural, a subset of Natural, and presents examples of programs written in Mini-Natural.

Color Computer Graphics As Applied To Introductory Calculus Instruction, Kathy B. Windhorst, Ralph E. Lee

Computer Science Technical Reports

The use of computer graphics to support and enhance the presentation of introductory calculus concepts is described.

Computer graphics provides more accurate graph sketching, consistent presentations and the ability to develop mathematical models incrementally. The addition of extensive use of color aids even more, adding contrast, color keying, dimensionality, and interest to an illustration.

Ten lessons have been designed, developed, and evaluated. They employ a set of subroutines which interface to the NBC APC microcomputer graphics software. These lessons as developed and evaluated may be used interactively in the classroom or by individuals, or noninteractively in the classroom by the …

A Focus Of Attention Algorithm For Expert Systems, Kevin W. Whiting, Arlan R. Dekock, John Bruce Prater

Computer Science Technical Reports

This research is primarily concerned with increasing the performance of expert systems. A refined focus of attention strategy and its affect on performance are discussed. Early expert systems used a brute force approach to process the knowledge base. Each production rule in the knowledge base was evaluated each cycle. More recently, processing efficiency has been increased by focusing the attention of the inference engine on a subset of the rules by "filtering" for further testing, only rules that could possibly fire given the current content of the context base. Focus of attention as developed in this research increases performance over …

Ciegen: A System For Testing Knowledge Base Compilation Heuristics On A Microcomputer, Jayne D. Ward, Billy E. Gillett, Arlan R. Dekock

Computer Science Technical Reports

The expert system has proven itself to be a valuable aid in diagnosing and treating problems in domains requiring expertise. The commercial world has been alerted to this fact and the thrust is to make the expert system portable and available on small computers.

The goal of this research has been to lay the groundwork for a domain independent expert system builder on a microcomputer. The result of this effort was CIEGEN, a system consisting of a rule compiler, inference engine, and rule generator developed on the IBM PC. It is domain independent, responsible for transforming a knowledge base of …

A Graphical Representation Of An Executing Program, Sherry A. Lile, Arlan R. Dekock, John Bruce Prater, Darrow Finch Dawson

Computer Science Technical Reports

This thesis describes the rationale for a computer program used as a teaching aid, as well as, the design, development, and implementation of that computer program. The program is a prototype that displays, line by line, a graphical depiction of a BASIC program being executed. Icons are used to represent FOR-NEXT loops, the contents of variables, I/O, and other programming elements. The internal logic associated with the Arithmetic-Logic Unit is also represented. The purpose is to produce an environment where the student may visualize the processes occurring in memory by viewing a symbolic portrayal of an executing program. The example …

The Optimal Trajectory Modelling Of Robot Manipulators, Mary Claire Miller, Chung You Ho, Arlan R. Dekock

Computer Science Technical Reports

Greater robot capability can be achieved through the use of robot manipulator control systems. Crucial to the success of these control systems is the optimal trajectory modelling of the path traced by the end- effector. To create this optimal path the utilization of B-Spline curve functions will be investigated, and compared to Cubic Spline curve functions.

An Experimental Study Of The Effects Of Modularity On Resource Consumption In Software Development, Alan D. Christiansen, Arlan R. Dekock, John Bruce Prater

Computer Science Technical Reports

Many authors have encouraged the use of modular programming techniques in software development. In fact, there is almost total agreement within industrial and academic circles that modularity is a desirable feature of any software package. Unfortunately, the desirability of modular design is almost always voiced without support from experimental evidence.

This paper consists of an experiment comparing the resource consumption of programmers based on the modularity practices employed during the design and programming phases of software development. The experiment tests the effectiveness of modularity in reducing psychological complexity of software.

The results of the research show that in some cases …

An Improved Algorithm For Generating Minimal Perfect Hash Functions, Thomas J. Sager

Computer Science Technical Reports

A minimal perfect hash function (MPHF) is a function from a set of M objects to the first M non-negative integers. MPHF's are useful for the compact storage and fast retrieval of frequently used objects such as reserved words in a programming language or commonly employed words in a natural language. In this paper we improve on an earlier result and present an algorithm for generating MPHF's with an expected time complexity proportional to M⁴. We also give a MPHF for the 256 most frequently used words in the English language.

Parallelism In The Language, Natural, Thomas J. Sager

Computer Science Technical Reports

Natural is a language designed to provide a vehicle for the expression of abstract programming concepts clearly and precisely in a natural and mathematical form. The concept of parallelism can be expressed both explicitly and implicitly in the language, Natural. Due to relative freedom from side-effects and the use of a special value, undef, subexpressions can often be evaluated in parallel. The for and do statements both allow for a parallel mode of execution. A builtin functional, prlleval, creates functions which can evaluate their arguements in a parallel mode. In addition, the concept of module allows for the definition of …

A New Method For Generating Minimal Perfect Hash Functions, Thomas J. Sager

Computer Science Technical Reports

A perfect hash function, PHF, is an injection, F, from a set, W, of M objects into the set consisting of the first N non-negative integers where N>=M. If N=M then F is a minimal perfect hash function, MPHF. PHFs are useful for the compact storage and fast retrieval of frequently used objects such as reserved words in a programming language or commonly employed words in a natural language.

The mincycle algorithm for finding PHFs executes with an expected time complexity proportional to M⁴ and has been used successfully on sets of cardinality up to 256. The mincycle …

A Graphical Representation Of An Executing Program, Sherry A. Lile

Masters Theses

"This thesis describes the rationale for a computer program used as a teaching aid, as well as, the design, development, and implementation of that computer program. The program is a prototype that displays, line by line, a graphical depiction of a BASIC program being executed. Icons are used to represent FOR-NEXT loops, the contents of variables, I/O, and other programming elements. The internal logic associated with the Arithmetic-Logic Unit is also represented. The purpose is to produce an environment where the student may visualize the processes occurring in memory by viewing a symbolic portrayal of an executing program. The example …

An Experimental Study Of The Effects Of Modularity On Resource Consumption In Software Development, Alan D. Christiansen

Masters Theses

"Many authors have encouraged the use of modular programming techniques in software development. In fact, there is almost total agreement within industrial and academic circles that modularity is a desirable feature of any software package. Unfortunately, the desirability of modular design is almost always voiced without support from experimental evidence.

This thesis consists of an experiment comparing the resource consumption of programmers based on the modularity practices employed during the design and programming phases of software development. The experiment tests the effectiveness of modularity in reducing psychological complexity of software.

The results of the research show that in some cases …

The Optimal Trajectory Modelling Of Robot Manipulators, Mary Claire Miller

Masters Theses

"Greater robot capability can be achieved through the use of robot manipulator control systems. Crucial to the success of these control systems is the optimal trajectory modelling of the path traced by the end- effector. To create this optimal path the utilization of B-Spline curve functions will be investigated, and compared to Cubic Spline curve functions"--Abstract, page ii.

The Design And Implementation Of The Programming Language Natural, Alan L. Sparks

Masters Theses

"This paper reports progress on the development of the programming language Natural, currently under design by Dr. Thomas J. Sager at the University of Missouri--Rolla. Natural is a very high-level language with a mathematical flavor, and includes several concepts relatively uncommon in programming language design.

The text also discusses an implementation on the IBM Personal Computer of Mini-Natural, a subset of Natural, and presents examples of programs written in Mini-Natural"--Abstract, page ii.

A Simple Method For Organizing Nearly Optimal Binary Search Trees, Joy L. Henderson

Masters Theses

"Improving the efficiency of retrieving information concerns users of computer systems involved in many applications- One way of addressing this concern is to organize a sorted sequence into a binary search tree. Knuth's Algorithm K is a bottom-up organization algorithm that always constructs a binary tree which minimizes average search time. However, the cost of executing Algorithm K is prohibitive for a large tree. The aim of this work is to find a less costly method of organizing sorted sequences into nearly-optimal binary search trees.

We present a top-down organization method which yields better average search times than top-down methods …