4 Application OF Discrete MATH IN Computer Science PDF

Preview

Summary

Download 4 Application OF Discrete MATH IN Computer Science PDF

Description

APPLICATION OF DISCRETE MATH IN COMPUTER SCIENCE ι i≫f l i l l ^ Discrete mathematics for computer science Murali ft Varanasi Studying this branch of mathematics Oscar /V. Garcia can provide you with a solid background for computer theory and applications The importance of mathematics to the study of both electrical engineering and computer science and engineering is well understood by educators and students alike. The topics learned in mathematics courses are often reviewed in engineering courses that partly focus on relevant mathematical concepts. It is almost impossible to imagine any engineering topic that can be studied without the aid of mathematics; today it is common practice to include at least half a year of mathematics in the engineering curriculum. Typical mathematical foundations developed in such a curriculum include courses in differential and integral calculus, probability and statistics, and differential equations. Additional topics such as linear algebra and matrices, numerical analysis, and discrete mathematics are often included as électives. The branch of mathematics referred to as discrete mathematics, or discrete structures, is critical to the study of computer science and engineering, as well as to the study of computer-related topics in electrical engineering. Discrete mathematics

provides a foundation for the design and implementation of hardware and software in digital computers. The need for such study is recognized by professional organizations such as the IEEE Computer Society and the Association for Computing Machinery (ACM). These organizations periodically make curricular recommendations through their respective educational activities boards, as well as through joint committees. They also work in collaboration with the IEEE and the Accreditation Board for Engineering and Technology to define criteria for accreditation of computer-related programs. All these eminent groups have endorsed the need for a course in discrete mathematics in addition to endorsing courses that cover the mathematics of the continuum, such as calculus and differential equations. The emphasis of a course in discrete mathematics should be directed toward developing theoretical tools for describing algorithmic applications and processes. The material can be broadly divided into two tracks, one based on the concepts of modern algebra as applied to sequential machines and computer system design, and the other based on graphs and trees as applied to data structures and algorithms. In addition, combinatoric mathematics is often included, covering techniques for enumerating the number of elements having a certain property. The key challenge, then, is to weave a unifying thread through sometimes dissimilar topics

and organize a cohesive body of knowledge that will provide a firm foundation for theory and applications in the computer area. The best teaching approach is to introduce each concept and follow it with interesting applications to reinforce its importance. A student can then appreciate the purpose of each theoretical tool and gain some understanding of its use. With this approach, the student avoids having to learn complex mathematical tools in the middle of studying other advanced topics. Topics in discrete mathematics A number of important topics should be included in a discrete mathematics course. Because of the variety of topics, some can only be treated in an introductory fashion. A more advanced treatment requires advanced undergraduate or graduate courses. The pertinent topics can be classified into five major themes: • mathematical reasoning • set theory • algebraic structures • graphs and trees • combinatorics At times the topics of generating functions and recurrence relations are also included under the heading of discrete mathematics. Mathematical reasoning includes such concepts as logical connectives, well-formed formulas, rules of inference, induction, methods of proof, predicates and quantifiers, and applications to computer logic and proofs of program correctness. These

concepts breed familiarity with the terminology and methodology of formal logic. The study of set theory includes sets and set algebra, relations of sets, recursive definition of sets, binary relations, ordering, composition of relations, equivalence relations and partitions, and applications. Set theory is basic in learning how to deal with objects and their relations from an abstract point of view. Concepts of algebraic structures provide the background essential to the study of finite state machines, switching theory, logic design, and general concepts in modern algebra. These algebraic structures include sets with defined operations; functions; composition; inverses; associative, commutative, and distributive operations; congruence relations; applications such as modular arithmetic, hashing functions, and machine equivalence and simulation; semigroups, monoids; groups; morphisms; lattices; Boolean algebra; and applications in switching theory and logic design. Another topic in discrete mathematics, graphs and trees, includes the study of directed and undirected graphs, paths, circuits, trees, reachability and connectedness, matrix 16 0278-6648/85/0200-0016$1.00 © 1985 IEEE IEEE POTENTIALS · FEBRUARY 1985 representation, applications to decision trees, balanced trees, Polish notation and trees, graph scheduling programs, flows in networks, data structure representation, theorem proving, and state graphs. These concepts

form the basis for the study of data structures and algorithms in a systematic manner. Combinatorics includes basic counting techniques, permutations and combinations, enumeration by recursion, the principle of inclusion and exclusion, and elements of Polya's theory, which provide a foundation in counting techniques that can be applied to algorithm analysis. Useful textbooks Several good textbooks on discrete mathematics cover the major themes identified here. Some of them are directed at beginning undergraduates, and others are aimed at advanced undergraduates. The books listed are suitable as texts for an undergraduate course in discrete mathematics. This list is not exhaustive; in addition to the books included here, a number of more advanced textbooks provide indepth treatment of one or more topics in discrete mathematics. Rather, the list is a good starting point for study of this area: • Bavel, Z., Math Companion for Computer Science, Reston, 1982, presents a concise treatment of the subject in an accessible and useful manner. • Birkhoff, F., and Bartee, T. C, Modern Applied Algebra, McGrawHill, 1970, provides excellent coverage of applications for set theory, algebraic structures, and graphs and trees. • Bobrow, L. S., and Arbib, Μ. Α., Discrete Mathematics, Saunders, 1974, provides an advanced undergraduate

or graduate treatment of algebraic structures. • Gersting, J. L., Mathematical Structures for Computer Science, / Freeman, 1983, offers good ^ coverage of algebraic aspects of discrete mathematics. • Gill, Α., Modern Algebra and Applications to Computer Science, McGraw-Hill, 1975, covers algebraic structures and their application to computers. • Johnsonbaugh, R., Discrete Mathematics, Macmillan, 1984, provides an overview of a large number of topics in a concise and pedagogically sound manner. • Kolman, B., and Busby, R. C. Discrete Mathematical Structures for Computer Science, Prentice-Hall, 1984, presents an introductory treatment that covers topics carefully selected to motivate students. • Korfhage, R. R., Discrete Computational Structures, Academic Press, 1974, supplies wide-ranging coverage of the topic, with emphasis on graph theory, including exercises in aspects of programming. • Levy, L. S., Discrete Structures of Computer Science, Wiley, 1980, provides a brief and concise treatment of the subject, with applications. • Liu, C. L., Elements of Discrete Mathematics, McGraw-Hill, 1977, covers set theory, graphs and trees, algebraic structures, and combinatorics, including recurrence relations, in an introductory level text. • Manna, Z., Mathematical Theory of Computation, McGraw-Hill,

1974, uses mathematical reasoning as a basis for a formal treatment of computation. • Mott, J. L., Kandel, Α., and Baker, T. P., Discrete Mathematics for Computer Scientists, Reston, 1983, is an undergraduate text that treats combinatorics and graph theoretical concepts with a mathematical flavor. • Prather, R. E., Discrete Mathematical Structures for Computer Science, Houghton-Mifflin, 1976, integrates algebraic concepts with an informal introduction to algorithms in a fairly comprehensive fashion. • Preparata, F. P., and Yeh, R. T., Introduction to Discrete Structures, Addison-Wesley, 1973, presents a complete coverage of the subject, including extensive bibliography, historical notes, and applications. • Stanat, D. E., and McAllister, D. F., Discrete Mathematics in Computer Science, Prentice-Hall, 1977, provides mathematically sound coverage of most subject areas of discrete mathematics. • Stone, H. S., Discrete Mathematical Structures, Science Research Associates, 1973, is an undergraduate text that surveys algebraic structures and their applications to computers. • Tremblay, J. P., and Mahohar, R. P., Discrete Mathematical Structures with Applications to Computer Science, McGraw-Hill, 1975, offers a detailed treatment of mathematical reasoning, set theory, algebraic structures, and graphs and trees in a mathematically precise manner. These texts, and other noteworthy

explorations of discrete mathematics, can assist in the proper blending of key concepts with interesting applications, thereby enabling students to appreciate the importance of these mathematical tools for analysis and design of computer hardware and software. About the authors Murali R. Varanasi is on the faculty of the department of computer science and engineering at the University of South Florida, Tampa. Dr. Varanasi has been active in the Educational Activities Board of the IEEE Computer Society over the last several years. Oscar N. Garcia is professor and chairman of the department of computer science and engineering at the University of South Florida, Tampa. Dr. Garcia is a fellow of the IEEE and was president of the IEEE Computer Society from 1982 through 1983. Drs. Varanasi and Garcia based this article on the recommendations of the Committee on Computer Sciences in Electrical Engineering of the National Academy of Engineering, the Curriculum Committee on Computer Science of the ACM, and the Educational Activities Board of the IEEE Computer Society. • VARANASI AND GARCIA—DISCRETE MATHEMATICS FOR COMPUTER SCIENCE 17...