Korfhage / Rheinboldt Discrete Computational Structures

1. Auflage 2014
ISBN: 978-1-4832-6429-5
Verlag: Elsevier Science & Techn.
Format: PDF
Kopierschutz: 1 - PDF Watermark

E-Book, Englisch, 396 Seiten, Web PDF

Discrete Computational Structures describes discrete mathematical concepts that are important to computing, covering necessary mathematical fundamentals, computer representation of sets, graph theory, storage minimization, and bandwidth. The book also explains conceptual framework (Gorn trees, searching, subroutines) and directed graphs (flowcharts, critical paths, information network). The text discusses algebra particularly as it applies to concentrates on semigroups, groups, lattices, propositional calculus, including a new tabular method of Boolean function minimization. The text emphasizes combinatorics and probability. Examples show different techniques of the general process of enumerating objects. Combinatorics cover permutations, enumerators for combinations, Stirling numbers, cycle classes of permutations, partitions, and compositions. The book cites as example the interplay between discrete mathematics and computing using a system of distinct representatives (SDR) problem. The problem, originating from group theory, graph theory, and set theory can be worked out by the student with a network model involving computers to generate and analyze different scenarios. The book is intended for sophomore or junior level, corresponding to the course B3, 'Introduction to Discrete Structures,' in the ACM Curriculum 68, as well as for mathematicians or professors of computer engineering and advanced mathematics.

Autoren/Hrsg.

Korfhage, Robert R.

Rheinboldt, Werner

Inhaltsverzeichnis

1;Front Cover;1
2;Discrete Computational Structures;4
3;Copyright Page;5
4;Table of Contents;6
5;Preface;10
6;Acknowledgments;14
7;Chapter 1. Basic Forms and Operations;16
7.1;1. INTRODUCTION;16
7.2;2. ELEMENTS AND SETS;17
7.3;3. SUBSETS;18
7.4;4. VENN DIAGRAMS AND SET COMPLEMENTS;22
7.5;5. COMPUTER REPRESENTATION OF SETS;23
7.6;6. SET OPERATIONS;26
7.7;7. SET ALGEBRA;27
7.8;8. COMPUTER OPERATIONS ON SETS;29
7.9;9. PRODUCT SETS;32
7.10;10. RELATIONS, MAPPINGS, FUNCTIONS;33
7.11;11. EQUIVALENCE AND ORDER RELATIONS;41
7.12;11. EQUIVALENCE AND ORDER RELATIONS;41
7.13;12. THE LATTICE OF SUBSETS;46
7.14;13. VECTORS AND MATRICES;47
8;Chapter 2. Undirected Graphs;52
8.1;1. GRAPH THEORY;52
8.2;2. BASIC DEFINITIONS;53
8.3;3. SPECIAL CLASSES OF GRAPHS;57
8.4;4. MATRIX REPRESENTATION OF GRAPHS;64
8.5;5. RELATIONS AMONG GRAPH MATRICES;68
8.6;6. INVARIANTS AND GRAPH ISOMORPHISM;73
8.7;7. CYCLE BASIS;82
8.8;8. MAXIMAL COMPLETE SUBGRAPHS;87
8.9;9. STORAGE MINIMIZATION FOR MATRICES;93
8.10;10. BANDWIDTH OF CUBIC GRAPHS;98
8.11;11. BANDWIDTH OF BIPARTITE GRAPHS;107
8.12;12. PLANAR GRAPHS AND THE FOUR COLOR CONJECTURE;112
8.13;REFERENCES;115
9;Chapter 3. Gorn Trees;116
9.1;1. INTRODUCTION;116
9.2;2. TREE DOMAINS;119
9.3;3. TREES;124
9.4;4. PREFIX REPRESENTATION AND TREE FORMS;129
9.5;5. EXPLICIT DEFINITIONS;134
9.6;6. SEARCHING, SUBROUTINES, AND THEOREM PROVING;141
9.7;REFERENCES;144
10;Chapter 4. Directed Graphs;145
10.1;1. INTRODUCTION;145
10.2;2. BASIC DEFINITIONS;145
10.3;3. SPECIAL CLASSES OF GRAPHS;149
10.4;4. MATRIX REPRESENTATION OF DIRECTED GRAPHS;150
10.5;5. FLOWCHARTS;151
10.6;6. NETWORKS;154
10.7;7. MINIMAL COST FLOWS;162
10.8;8. PRUNING BRANCHES TO FIND THE SHORTEST PATH;164
10.9;9. CRITICAL PATHS;169
10.10;10. GRAPHS OF MULTIPROCESSING SYSTEMS;172
10.11;11. INFORMATION NETWORKS;173
10.12;REFERENCE;180
11;Chapter 5. Formal and Natural Languages;181
11.1;1. INTRODUCTION;181
11.2;2. SEMIGROUPS;182
11.3;3. FORMAL LANGUAGES;183
11.4;4. BACKUS NAUR FORM AND ALGOL-LIKE LANGUAGES;191
11.5;5. SEMANTICS OF FORMAL LANGUAGES;195
11.6;6. NATURAL LANGUAGES;196
11.7;REFERENCES;197
12;Chapter 6. Finite Groups and Computing;198
12.1;1. DEFINITIONS OF GROUPS AND SUBGROUPS;198
12.2;2. GROUPS OF GRAPHS;201
12.3;3. GRAPHS OF GROUPS;204
12.4;4. GENERATORS AND RELATIONS;205
12.5;5. PERMUTATIONS AND PERMUTATION GROUPS;212
12.6;6. PERMUTATION GENERATORS;218
13;Chapter 7. Partial Orders and Lattices;223
13.1;1. INTRODUCTION;223
13.2;2. PARTIAL ORDERS;223
13.3;3. LATTICES;226
13.4;4. SPECIALIZED LATTICES;232
13.5;5. ATOMIC LATTICES;238
13.6;REFERENCE;240
14;Chapter 8. Boolean Algebras;241
14.1;1. INTRODUCTION;241
14.2;2. PROPERTIES OF BOOLEAN ALGEBRAS;242
14.3;3. BOOLEAN ALGEBRAS AND SET ALGEBRAS;244
14.4;4. BOOLEAN FUNCTIONS;245
14.5;5. SWITCHING CIRCUITS;251
14.6;6. BOOLEAN FUNCTION MINIMIZATION;254
14.7;7. COMPUTER ARITHMETIC;264
14.8;REFERENCE;266
15;Chapter 9. The Propositional Calculus;267
15.1;1. INTRODUCTION;267
15.2;2. FUNDAMENTAL DEFINITIONS;268
15.3;3. TRUTH TABLES;270
15.4;4. WELL-FORMED FORMULAS;276
15.5;5. MINIMAL SETS OF OPERATORS;278
15.6;6. POLISH NOTATION;281
15.7;7. PROOFS IN LOGIC;287
15.8;8. SETS AND WORDSETS;295
15.9;REFERENCE;295
16;Chapter 10. Combinatorics;296
16.1;1. INTRODUCTION;296
16.2;2. PERMUTATIONS OF OBJECTS;296
16.3;3. COMBINATIONS OF OBJECTS;302
16.4;4. ENUMERATORS FOR COMBINATIONS;306
16.5;5. ENUMERATORS FOR PERMUTATIONS;313
16.6;6. STIRLING NUMBERS;315
16.7;7. CYCLE CLASSES OF PERMUTATIONS;318
16.8;8. PARTITIONS AND COMPOSITIONS;321
16.9;REFERENCES;326
17;Chapter 11. Systems of Distinct Representatives;327
17.1;1. INTRODUCTION AND HISTORY;327
17.2;2. THE THIRD QUESTION, GENERAL CASE;333
17.3;3. THE THIRD QUESTION, PARTITION CASE;337
17.4;4. SUMMARY;340
17.5;REFERENCES;341
18;Chapter 12. Discrete Probability;342
18.1;1. PROBABILITIES ON A DISCRETE SET;342
18.2;2. CONDITIONAL PROBABILITY AND INDEPENDENCE;348
18.3;3. COMPUTATION OF BINOMIAL COEFFICIENTS;352
18.4;4. DISTRIBUTIONS;356
18.5;5. RANDOM NUMBERS;366
18.6;REFERENCE;370
19;Answers and Hints for Selected Exercises;371
20;Index;390
21;Computer Science and Applied Mathematics;397