Дискретная математика
Математика
  • формат pdf
  • размер 1.97 МБ
  • добавлен 28 октября 2011 г.
O’Donnell J., Hall C., Page R. Discrete Mathematics Using a Computer
Издательство Springer, 2006, -445 pp.

Computer science abounds with applications of discrete mathematics, yet students of computer science often study discrete mathematics in the context of purely mathematical applications. They have to figure out for themselves how to apply the ideas of discrete mathematics to computing problems. It is not easy. Most students fail to experience broad success in this enterprise, which is not surprising, since many of the most important advances in science and engineering have been, precisely, applications of mathematics to specific science and engineering problems.
To be sure, most discrete math textbooks incorporate some aspects applying discrete math to computing, but it usually takes the form of asking students to write programs to compute the number of three-ball combinations there are in a set of ten balls or, at best, to implement a graph algorithm. Few texts ask students to use mathematical logic to analyze properties of digital circuits or computer programs or to apply the set theoretic model of functions to understand higher-order operations. A major aim of this text is to integrate, tightly, the study of discrete mathematics with the study of central problems of computer science.
Concepts in discrete mathematics are illustrated through the solution of problems that arise in software development, hardware design, and other fundamental domains of computer science. The text introduces discrete math concepts and immediately applies them to computing problems. Applications of mathematical logic in design and analysis of hardware and software is an especially strong theme. The goal in this part of the material is to prepare students for a world that places a high value on the correct operation of computing systems in safety-critical, security-sensitive, and embedded systems and recognizes that formal methods based in mathematical logic are the primary tools for ensuring that computing systems function properly in such environments. The emphasis, here, is on preparation. In commercial applications, mechanized logic engines are essential to the enterprise of applying logic to the design and implementation of computing hardware and software. This text introduces students to mechanized logic in the form of propositional proof checking, and, through numerous paper-and-pencil exercises in applying logic to mathematical verification of hardware and software artifacts, gives students experience with the fundamental notions used by engineers who apply mechanized logic engines to the design of commercial computing systems. We believe these skills will be of increasing value in computer and software engineering, and our experience suggests that such skills contribute positively, even in the short run, to the ability of students to successfully design and implement software.
The text is organized in four parts: reasoning with equations, formal logic, set theory, and applications. The principle of induction is introduced early, for reasoning with equations, and applied to problems throughout the text. Reasoning with equations covers examples in several domains, including natural numbers of course, but also including sequences and sets. The logic portion of the text discusses two frameworks for formal reasoning: the natural deduction format of Gentzen and another syntax-based reasoning system based in Boolean algebra. Propositional logic is introduced first, then predicate logic, both in a natural deduction and Boolean algebra setting. Set theory discusses the usual basics, and illustrates many of the concepts by applying induction to define the integers. The set theoretic definitions of relations and functions are discussed, along with the usual properties that categorize them and allow them to be combined and manipulated. The applications portion of the text covers two extended examples, one conceing the design of a circuit for n-bit, ripple-carry addition, the other on the implementation of AVL tree operations. These augment the many, smaller examples that occur throughout the text and, together, help students understand how discrete mathematics contributes to the solution of difficult and important problems in computing.
A website for the text contains a collection of tools for experimenting with most of the concepts introduced. Included among these is a proof-checking system for propositional calculus. Students can use this system to make sure their proofs are correct and, more importantly, to experience the notion that proofs can be entirely formal and, therefore, useful in verifying the correctness of software and digital circuits. Other tools allow experimentation with set operations, Boolean formulas, and the notions of predicate calculus. These tools are expressed in Haskell, and the various operations for experimentation, including proofs, are expressed using Haskell syntax. In addition, Haskell is used to express the software and hardware designs that illustrate practical uses of logic and other aspects of discrete mathematics in computer science.
We feel that Haskell is an ideal notational choice for these examples because of its close affinity with customary algebraic notation. The compactness of software and hardware artifacts expressed in Haskell is another important advantage. Haskell serves both as a formal, mathematical notation, and as a practical and powerful programming language. This helps to strengthen the tight connection between mathematics and applications. Thus Haskell is used in the text on an equal footing with other mathematical notations. Students see Haskell in its role as a programming language, as well as a hardware description language, and the emphasis in this book is on reasoning about programs and circuits, not just programming.
We hope that students will find the experience of leaing about logic, sets, mathematical induction, and other concepts of discrete mathematics and its applications to computing problems interesting and enjoyable, and that they will be able to use these ideas in subsequent studies and professional work in computer science.
Programming and Reasoning with Equations.
ntroduction to Haskell.
Equational Reasoning.
Recursion.
nduction.
Trees.
Logic.
Propositional Logic.
Predicate Logic.
Set Theory.
Set Theory.
nductively Defined Sets.
Relations.
Functions.
Applications.
The AVL Tree Miracle.
Discrete Mathematics in Circuit Design.
A Software Tools .
B Resources on the Web.
C Solutions to Selected Exercises.
Похожие разделы
Смотрите также

Epp S.S. Discrete Mathematics with Applications

  • формат pdf
  • размер 9.73 МБ
  • добавлен 12 июня 2011 г.
Brooks Cole, 2010. - 984 pages. 4 edition Susanna Epp's "Discrete Mathematics with Applications" provides a clear introduction to discrete mathematics. Renowned for her lucid, accessible prose, Epp explains complex, abstract concepts with clarity and precision. This book presents not only the major themes of discrete mathematics, but also the reasoning that underlies mathematical thought. Students develop the ability to think abstractly as they...

Epp S.S. Discrete Mathematics with Applications

  • формат pdf
  • размер 47.76 МБ
  • добавлен 22 февраля 2011 г.
Brooks Cole, 2003. - 928 pages. Susanna Epp's Discrete Mathematics, Third edition provides a clear introduction to discrete mathematics. Renowned for her lucid, accessible prose, Epp explains complex, abstract concepts with clarity and precision. This book presents not only the major themes of discrete mathematics, but also the reasoning that underlies mathematical thought. Students develop the ability to think abstractly as they study the ideas...

Feil T., Krone J. Essential Discrete Math for Computer Science

  • формат pdf
  • размер 8.91 МБ
  • добавлен 19 января 2011 г.
Prentice Hall, 2002. - 216 Pages. This book introduces readers to the mathematics of computer science and prepares them for the math they will encounter in other college courses. It includes applications that are specific to computer science, helps learners to develop reasoning skills, and provides the fundamental mathematics necessary for computer scientists. Chapter topics include sets, functions and relations, Boolean algebra, natural numbers...

Gossett E. Discrete Mathematics with Proof

  • формат pdf
  • размер 55.48 МБ
  • добавлен 19 января 2011 г.
Prentice Hall, 2002. - 808 pages. For one-semester undergraduate Discrete Mathematics courses for math and computer science majors. This exceedingly well-written text equips students to apply discrete mathematics and provides opportunities for practice of the concepts presented. A semester of Calculus is useful for reasons of sophistication.

Haggard G., Schlipf J., Whitesides S. Discrete Mathematics for Computer Science

  • формат pdf
  • размер 25.96 МБ
  • добавлен 01 января 2011 г.
Brooks Cole, 2005. - 718 Pages. Master the fundamentals of discrete mathematics with DISCRETE MATHEMATICS FOR COMPUTER SCIENCE! An increasing number of computer scientists from diverse areas are using discrete mathematical structures to explain concepts and problems and this mathematics text shows you how to express precise ideas in clear mathematical language. Through a wealth of exercises and examples, you will learn how mastering discrete mat...

Hein J.L. Discrete Mathematics

  • формат pdf
  • размер 27.08 МБ
  • добавлен 01 января 2011 г.
2nd ed. Jones & Bartlett Publishers, 2002. - 731 pages. This introduction to discrete mathematics prepares future computer scientists, engineers, and mathematicians for success by providing extensive and concentrated coverage of logic, functions, algorithmic analysis, and algebraic structures. Discrete Mathematics, Second Edition illustrates the relationships between key concepts through its thematic organization and provides a seamless tran...

Ross K.A., Wright C.R. Discrete Mathematics (I том архива)

  • формат pdf
  • размер 90 МБ
  • добавлен 11 февраля 2011 г.
Prentice Hall, 2002. - 612 pages. Informal but thorough in its coverage, this introduction to discrete mathematics offers a carefully graded treatment of the basics essential to computer science. This book presents a sound mathematical treatment that increases smoothly in sophistication. Key Topics: The book presents utility-grade discrete math tools so that any reader can understand them, use them, and move on to more advanced mathematical t...

Ross K.A., Wright C.R. Discrete Mathematics (II том архива)

  • формат pdf
  • размер 26.47 МБ
  • добавлен 11 февраля 2011 г.
Prentice Hall, 2002. - 612 pages. Informal but thorough in its coverage, this introduction to discrete mathematics offers a carefully graded treatment of the basics essential to computer science. This book presents a sound mathematical treatment that increases smoothly in sophistication. Key Topics: The book presents utility-grade discrete math tools so that any reader can understand them, use them, and move on to more advanced mathematical t...

Scheinerman E.A. Mathematics: A Discrete Introduction

  • формат pdf
  • размер 21.56 МБ
  • добавлен 11 августа 2011 г.
Brooks Cole, 2005. - 592 pages. This book has two primary objectives: It teaches students fundamental concepts in discrete mathematics (from counting to basic cryptography to graph theory), and it teaches students proof-writing skills. With a wealth of learning aids and a clear presentation, the book teaches students not only how to write proofs, but how to think clearly and present cases logically beyond this course. Overall, this book is an i...