Elements of Combinatorial Computing
- 1st Edition - January 1, 1971
- Imprint: Pergamon
- Author: Mark B. Wells
- Language: English
- Paperback ISBN:9 7 8 - 1 - 4 8 3 1 - 7 0 8 5 - 5
- eBook ISBN:9 7 8 - 1 - 4 8 3 1 - 8 6 6 6 - 5
Elements of Combinatorial Computing focuses on the processes, principles, methodologies, and approaches involved in combinatorial computing. The publication first takes a look at… Read more
Purchase options
Institutional subscription on ScienceDirect
Request a sales quoteElements of Combinatorial Computing focuses on the processes, principles, methodologies, and approaches involved in combinatorial computing. The publication first takes a look at a language for combinatorial computing, language implementation and program efficiency, and computer representation of mathematical objects. Discussions focus on geometric configurations, elementary combinatorial configurations, sets and vectors, natural numbers, program optimization, data representation, set manipulation, notation for iteration and recursion, and nested iteration and recursive programming. The text then takes a look at backtrack programming, generation of elementary configurations, and additional basic techniques and manipulations. Topics include isomorph rejection, transformations, finite set covering, sorting techniques, permutations with repeated objects, compositions, partitions, subsets and combinations, and basic backtracking and impasse detection. The book examines additional basic techniques and manipulations and applications of advanced algorithms. The publication is highly recommended for computer science experts and researchers interested in the elements in combinatorial computing.
Preface
Chapter 1 A Language for Combinatorial Computing
1.1 Fundamentals
1.1.1 Program Structure
1.1.2 Notation for Real Number Operations
1.1.3 Data-types and Arrays
1.1.4 Procedures
1.2 Set Manipulation
1.2.1 Notation for Sets
1.2.2 Operations
1.2.3 Functions Based on the Order of the Elements
1.3 Transfer of Control—Conditional Statements
1.3.1 Basic Statement Structure
1.3.2 Simple Conditions
1.3.3 Compound Conditions
1.3.4 Additional Forms
1.4 Notation for Iteration and Recursion
1.4.1 For-Statement Structure
1.4.2 Simple Range Specification and Generation Procedures
1.4.3 Auxiliary Transfer of Control Statements
1.4.4 Compound Range Specification
1.4.5 Notations Involving Iteration
1.5 Nested iteration and Recursive Programming
1.5.1 With-Statement Structure
1.5.2 Range Specification
1.5.3 Auxiliary Transfer of Control Statements
1.5.4 Recursive Operations
Chapter 2 Language Implementation and Program Efficiency
2.1 Data Representation
2.1.1 Single-Word Forms
2.1.2 Multiple-Word Forms
2.1.3 Storage Allocation
2.1.4 Toggles and Special Indicators
2.2 Operations
2.2.1 Shifting and Exponentiation
2.2.2 Modular Arithmetic
2.2.3 Counting and Locating 1-Bits
2.2.4 Functions
2.2.5 Control Language
2.3 Program Optimization
2.3.1 Precomputation
2.3.2 Specialization Versus Generalization
2.3.3 Use of Sophisticated Notations
2.4 System Organization—Procedures
2.4.1 Program Segmentation
2.4.2 Procedure Linkage
2.4.3 Compilation and Execution
Chapter 3 Computer Representation of Mathematical Objects
3.1 Natural Numbers
3.1.1 Positional Representation
3.1.2 Gray Codes
3.1.3 Residue Representation
3.1.4 Prime Factor Representation
3.1.5 Bit Parity of Multiples of Primes
3.2 Sets and Vectors
3.2.1 Unordered Sets—Masks
3.2.2 Unordered Sets as Ordered Lists—Binary Search
3.2.3 Signatures—Fractional Word Representation
3.2.4 Vectors and Polynomials Modulo 2
3.3 Elementary Combinatorial Configurations
3.3.1 Combinations and Permutations
3.3.2 Permutations as Transformations
3.3.3 Finite Groups
3.3.4 Compositions and Partitions of a Whole Number
3.3.5 Partitions of a Set
3.4 Linear Graphs and Networks
3.4.1 Definitions and Terminology
3.4.2 Representation by Incidence Matrices
3.4.3 Incidence Systems
3.4.4 Tree-Like Data Structures
3.5 The n-Cube
3.5.1 Graph-Theoretic Representation
3.5.2 Normal Form Expressions of Boolean Functions
3.5.3 Prime Implicants (Basic Cells)
3.6 Geometric Configurations
3.6.1 Polyominoes
3.6.2 Chessboard Models
Chapter 4 Search and Enumeration—Backtrack Programming
4.1 Introduction to Backtrack Programming—The Search Tree
4.1.1 Elementary Signature Generation
4.1.2 Normal Tree Scan and Basic Program Structure
4.1.3 Notational Variants
4.2 Basic Backtracking and Impasse Detection
4.2.1 Graph Coloring
4.2.2 Anticipated Impasse Detection
4.2.3 Search Rearrangement
4.2.4 Hamiltonian Path Generation
4.3 Optimization Backtracking
4.3.1 Branch and Bound—The Traveling Salesman Problem
4.3.2 The Algorithm of Little, Murty, Sweeney, and Karel
4.3.3 Min-Max Optimization—Computer Chess
4.3.4 Local Optima by Method-of-Ascent
4.3.5 More Refined Approximation
4.4 Branch Merging
4.4.1 The Cut-Off and Tier Scans
4.4.2 Permanent Evaluation
4.4.3 Dynamic Programming Approach to Optimization
4.4.4 Enumeration by Branch Merging
Chapter 5 Generation of Elementary Configurations
5.1 Subsets and Combinations
5.1.1 Generation of All Subsets
5.1.2 r-Subsets—Combinations of Distinct Objects
5.1.3 Serial Numbers and Ranking of Combinations
5.2 Permutations of Distinct Objects
5.2.1 Lexicographic Generation and Serial Numbers
5.2.2 Generation by Transposition
5.2.3 Generation by Adjacent Transposition
5.2.4 Permutations Consistent with a Partial Ordering
5.3 Permutations with Repeated Objects
5.3.1 Lexicographic Generation
5.3.2 Serial Number Calculation
5.4 Compositions
5.4.1 Relationship with Subsets—Serial Numbers
5.4.2 Generation in Signature Form
5.4.3 Compositions as Permutations of Partitions
5.5 Partitions
5.5.1 Numerical Partitions in Signature Form
5.5.2 Serial Numbers for Numerical Partitions
5.5.3 Partitions of a Set
5.5.4 Binary Trees—Partitions Without Crossing
Chapter 6 Additional Basic Techniques and Manipulations
6.1 Sieving Processes
6.1.1 Modular Sieves
6.1.2 Isomorph Rejection by Sieve
6.1.3 Further Examples of Recursive Sieving
6.2 Sorting Techniques
6.2.1 Pigeonholing—Sort by Address Calculation
6.2.2 Merge-Exchange Sorting—Shell's Method
6.2.3 The Sort Permutation
6.3 Procedures Concerned with Connectedness
6.3.1 The Connectivity Matrix—WarshalVs Method
6.3.2 Sequential Generation of Components
6.3.3 Consistency Determination (Cycle Detection)
6.4 Finite Set Covering
6.4.1 The Basic Branching Algorithm
6.4.2 Disjoint Covers—Steiner Triple Systems
6.4.3 Irredundant Covers
6.4.4 Other Program Refinements
6.5 Transformations
6.5.1 Matrix Translation and Transposition
6.5.2 Symmetries of the Square—The Dihedral Groups
6.5.3 Permutation Group Generation
6.6 Isomorph Rejection
6.6.1 A Typical Problem—Basic Program Structures
6.6.2 Direct Comparison
6.6.3 The Indirect Comparison Approach
Chapter 7 Applications—Advanced Algorithms
7.1 Incidence Matrix Equivalence
7.1.1 Invariants
7.1.2 An Equivalence Algorithm
7.1.3 Reduced Latin Square Enumeration
7.2 The Steinhaus Sorting Problem
7.2.1 The Ford-Johnson Algorithm
7.2.2 Enumeration ofPoset Consistent Permutations—Discussion
7.2.3 The Enumeration Program
7.2.4 Computer Study of the Case n = 12
7.3 A Computer Study of the Four-Color Problem
7.3.1 Elementary Kempe Reductions
7.3.2 A General Approach to Reducibility Testing
7.3.3 Tractable Circuit Colorations
7.3.4 Contractions
7.4 Parker's Orthogonal Latin Square Generation
7.5 Simplification of Normal Form Boolean Expressions
Appendix I Tables of Important Numbers
I.1 Powers of 2; Factorials; Bell Numbers; Segner Numbers
I.2 Binomial Coefficients
I.3 Stirling Numbers of Second Kind
I.4 Number of Partitions of n into Parts ≤ m
I.5 Prime Numbers < 1000 (by Bit-Pattern)
Appendix II Tables of Interesting Numbers
II.1 Excess Number of Multiples ( < 2n)of p with Even 1-bit Parity
II.2 Number of Solutions to Queens' Problem
II.3 Folding Numbers
II.4 Answers to a Distribution Problem for n = 5
II.5 Number of Reduced Latin Squares
II.6 Number of Zero-One Matrices with Vanishing Permanent
II.7 Spectra of Determinant Magnitudes for Zero-One Matrices
Appendix III Compendium of Four-Color Reducible Configurations
Bibliography
Index
- Edition: 1
- Published: January 1, 1971
- No. of pages (eBook): 272
- Imprint: Pergamon
- Language: English
- Paperback ISBN: 9781483170855
- eBook ISBN: 9781483186665
Read Elements of Combinatorial Computing on ScienceDirect