Open Access. Powered by Scholars. Published by Universities.®
Physical Sciences and Mathematics Commons™
Open Access. Powered by Scholars. Published by Universities.®
Articles 1 - 9 of 9
Full-Text Articles in Physical Sciences and Mathematics
Development Of An Expert System To Convert Knowledge-Based Geological Engineering Systems Into Fortran, Jill J. Cress, Ralph W. Wilkerson
Development Of An Expert System To Convert Knowledge-Based Geological Engineering Systems Into Fortran, Jill J. Cress, Ralph W. Wilkerson
Computer Science Technical Reports
A knowledge-based geographic information system (KBGIS) for geological engineering map (GEM) production was developed in GoldWorks, an expert system development shell. GoldWorks allows the geological engineer to develop a rule base for a GEM application. Implementation of the resultant rule base produced a valid GEM, but took too much time. This proved that knowledge-based GEM production was possible but in GoldWorks implementation failed as a practical production system. To solve this problem, a Conversion Expert System was developed which accepted, as input, a KBGIS and produced, as output, the equivalent Fortran code. This allowed the engineer to utilize GoldWorks for …
The Directed Steiner Problem On Graphs: A Simulated Annealing Approach, Lawrence Joseph Osborne, Billy E. Gillett
The Directed Steiner Problem On Graphs: A Simulated Annealing Approach, Lawrence Joseph Osborne, Billy E. Gillett
Computer Science Technical Reports
The well-known Steiner Problem on Graphs is an NP-complete problem for which there are many heuristic and exact algorithms that are deterministic. In this dissertation a new approach to the directed version of this problem is made by applying the ideas of statistical mechanics through the use of the method of simulated annealing. A version of annealing is developed for the Directed Steiner Problem and compared with one of the best general annealing schemes. Then a comparison is made between simulated annealing and the traditional branch and bound technique. The dual ascent algorithm of Richard T. Wong is used to …
A Comparison Of Consistency Control Protocols, Michael Goldweber, Donald B. Johnson, Larry Raab
A Comparison Of Consistency Control Protocols, Michael Goldweber, Donald B. Johnson, Larry Raab
Computer Science Technical Reports
In this paper we analyze three protocols for maintaining the mutual consistency of replicated objects in a distributed computing environment and compare their performance with that of an oracle protocol whose performance is optimal. We examine these protocols, two dynamic protocols and the majority consensus protocol, via simulations using two measures of availability. The analysis shows that the dynamic protocols, under realistic assumptions, do not perform significantly better than the static voting scheme. Finally we demonstrate that none of these approaches perform as well as our oracle protocol which is shown to be an upper bound on availability.
Automated Translation Of Digital Logic Equations Into Optimized Vhdl Code, John Evan Stark, George Winston Zobrist
Automated Translation Of Digital Logic Equations Into Optimized Vhdl Code, John Evan Stark, George Winston Zobrist
Computer Science Technical Reports
It was desired to develop an algorithm for the automated translation of finite slate machines from state table form to optimized VHDL form. To do this, algorithms arc needed for reducing the state machine to simplest form, making state assignments, producing minimal logic equations to represent the state machine, and producing VHDL code which describes the intended circuit. Various such algorithms were examined and a prototype program written to perform this translation.
An Improved Exact Graph Coloring Algorithm, Thomas J. Sager, Shi-Jen Lin
An Improved Exact Graph Coloring Algorithm, Thomas J. Sager, Shi-Jen Lin
Computer Science Technical Reports
We present two algorithms for exact graph coloring of the vertex sequential with dynamic reordering of vertices variety. The first, W-DEG, is a straight-forward improvement on Korman’s original algorithm. The second, SWAP2, is a not so straight forward improvement on Korman’s algorithm and appears to offer the best performance of known exact graph coloring algorithms.
A Color-Exchange Algorithm For Exact Graph Coloring, Thomas J. Sager, Shi-Jen Lin
A Color-Exchange Algorithm For Exact Graph Coloring, Thomas J. Sager, Shi-Jen Lin
Computer Science Technical Reports
DEXCH, a color-exchange exact graph coloring algorithm is presented. On many classes of graphs, DEXCH can, in the mean, find the chromatic number of a graph considerably faster than the DSATUR algorithm. The improvement over DSATUR stems from the ability to reorganize the subset of colored vertices and to detect in certain instances the existence of a complete subgraph of cardinality equal to the number of colors used in the best coloring found so far. The mean improvement over DSATUR is greatest on high edge-density graphs attaining the value of 42% on random graphs of edge-density 0.7 on 64 vertices.
A Pruning Procedure For Exact Graph Coloring, Thomas J. Sager, Shi-Jen Lin
A Pruning Procedure For Exact Graph Coloring, Thomas J. Sager, Shi-Jen Lin
Computer Science Technical Reports
The graph coloring problem can be stated: “Given an undirected graph, using a minimal number of colors, assign each vertex a color so that if two vertices are connected by an edge then they are not assigned the same color.” Graph coloring can be used to solve scheduling problems with constraints of the form: events e and e' can not be scheduled together. Graph coloring is an NP-Complete problem. Generally large problems are solved heuristically, although some of the better heuristic algorithms use an exact graph coloring algorithm to finish coloring a graph after first reducing it heuristically …
On The Worst Case Of Three Algorithms For Computing The Jacobi Symbol, Jeffrey Shallit
On The Worst Case Of Three Algorithms For Computing The Jacobi Symbol, Jeffrey Shallit
Computer Science Technical Reports
We study the worst-case behavior of three iterative algorithms- Eisenstein's algorithm, Lebesgue's algorithm, and the "ordinary" Jacobi symbol algorithm - for computing the Jacobi symbol. Each algorithm is similar in format to the Euclidean algorithm for computing gcd (u,v).
Asymptotically Fast Algorithms For Spherical And Related Transforms, James R. Driscoll, Dennis M. Healy
Asymptotically Fast Algorithms For Spherical And Related Transforms, James R. Driscoll, Dennis M. Healy
Computer Science Technical Reports
This paper considers the problem of computing the harmonic expansion of functions defined on the sphere. We begin by proving convolution theorems that relate the convolution of two functions on the sphere to a "multiplication" in the sprectral domain, as well as the multiplication of two functions on the sphere to a "convolution" in the spectral domain. These convolution theorems are then used to develop a sampling theorem on the sphere.