Graduate Thesis Or Dissertation
 

Knots : a measure of program complexity

Public Deposited

Downloadable Content

Download PDF
https://ir.library.oregonstate.edu/concern/graduate_thesis_or_dissertations/db78tf52h

Descriptions

Attribute NameValues
Creator
Abstract
  • Most measures of program complexity gauge either textual or control flow attributes of a program. A recent addition to the field of complexity measures, the knot metric, is a function of both these attributes. A knot measurement reflects the degree of control-flow tangle in a program's listing. This thesis discusses and proves four functional properties of the knot measure. 1. Calculation of a program's knot content is fast with respect to the number of branches in a program. A worst-case optimal algorithm for computing knots is quadratic in time and linear in space. 2. The complexity of a program can be reduced by rearranging groups of statements in a manner that retains the program's function yet lowers its knot content. The problem of finding an arrangement with the fewest knots for any arrangement of a program is probably difficult or NP-complete, but approximation methods are fast and often find the minimum knot arrangement. 3. A direct relationship exists between the types of knots in a program text and the structuredness of that program. This leads to an easily testable, sufficient condition for unstucturedness. Thus unstuctured programs may be detected without graphically reducing the control structure to structured programming conventions. 4. An empirical investigation of a set of FORTRAN programs, testing for their knot content, rearrangement characteristics, cyclomatic number, and program length, demonstrates the practicality of the knot measure. Most programs benefited from rearrangement, and a fast, heuristic algorithm was effective in finding a program text ordering with minimal knot content. Furthermore, the knot content of a program is dissassociated from two other measures of complexity, cyclomatic number and program length. Knots must measure some aspect of complexity missed by those measures. Overall, the knot metric is an effective, and efficient means for detecting, reducing, and controlling some attributes of software complexity.
Resource Type
Date Available
Date Issued
Degree Level
Degree Name
Degree Field
Degree Grantor
Commencement Year
Advisor
Academic Affiliation
Non-Academic Affiliation
Subject
Rights Statement
Publisher
Peer Reviewed
Language
Digitization Specifications
  • File scanned at 300 ppi (Monochrome) using Capture Perfect 3.0 on a Canon DR-9050C in PDF format. CVista PdfCompressor 4.0 was used for pdf compression and textual OCR.
Replaces

Relationships

Parents:

This work has no parents.

In Collection:

Items

Thumbnail Title Date Uploaded Visibility Actions
file details McAlisterRichardEarl1980.pdf 2017-08-07 Public Download