Discrete mathematics
Discrete mathematics is the study of mathematical structures that are discrete rather than continuous. In contrast to real numbers that vary "smoothly", discrete mathematics studies objects such as integers, graphs, and statements in logic.[1] These objects do not vary smoothly, but have distinct, separated values.[2] Discrete mathematics therefore excludes topics in "continuous mathematics" such as calculus and analysis. Discrete objects can often be counted using integers. Mathematicians say that this is the branch of mathematics dealing with countable sets[3] (sets that have the same cardinality as subsets of the natural numbers, including rational numbers but not real numbers). However, there is no exact, universally agreed, definition of the term "discrete mathematics."[4] Many times, discrete mathematics is described less by what is included than by what is excluded: continuously varying quantities and related notions.
The set of objects studied in discrete mathematics can be finite or infinite. The term finite mathematics is sometimes applied to parts of the field of discrete mathematics that deals with finite sets, particularly those areas relevant to business.
Research in discrete mathematics increased in the latter half of the twentieth century partly due to the development of digital computers which operate in discrete steps and store data in discrete bits. Concepts and notations from discrete mathematics are useful in studying and describing objects and problems in branches of computer science, such as computer algorithms, programming languages, cryptography, automated theorem proving, and software development. In turn, computer implementations are significant in applying ideas from discrete mathematics to real-world problems, such as in operations research, game theory and graph theory.
Although the main objects of study in discrete mathematics are discrete objects, analytic methods from continuous mathematics are often employed as well.
Discrete Mathematics Media
Complexity studies the time taken by algorithms, such as this sorting routine.
Computational geometry applies computer algorithms to representations of geometrical objects.
The ASCII codes for the word "Wikipedia", given here in binary, provide a way of representing the word in information theory, as well as for information-processing algorithms.
Graph theory has close links to group theory. This truncated tetrahedron graph is related to the alternating group A4.
The Ulam spiral of numbers, with black pixels showing prime numbers. This diagram hints at patterns in the distribution of prime numbers.
Much research in graph theory was motivated by attempts to prove that all maps, like this one, can be colored using only four colors so that no areas of the same color share an edge. Kenneth Appel and Wolfgang Haken proved this in 1976.
References
- ↑ Richard Johnsonbaugh, Discrete Mathematics, Prentice Hall, 2008.
- ↑ Weisstein, Eric W., "Discrete mathematics" from MathWorld.
- ↑ Norman L. Biggs, Discrete mathematics, Oxford University Press, 2002.
- ↑ Brian Hopkins, Resources for Teaching Discrete Mathematics, Mathematical Association of America, 2008.
Further reading
 |
The English Wikibooks has more information on: |
- Norman L. Biggs, Discrete Mathematics 2nd ed. Oxford University Press. ISBN 0-19-850717-8, and companion web site including questions together with solutions.
- Ronald Graham, Donald E. Knuth, Oren Patashnik, Concrete Mathematics
- Donald E. Knuth, The Art of Computer Programming ISBN 978-0321751041.
- Kenneth H. Rosen, Handbook of Discrete and Combinatorial Mathematics CRC Press. ISBN 0-8493-0149-1.
- Richard Johnsonbaugh, Discrete Mathematics 6th ed. Macmillan. ISBN 0-13-045803-1, and companion web site Archived 2021-04-27 at the Wayback Machine.
- John Dwyer & Suzy Jagger, Discrete Mathematics for Business & Computing, 1st ed. 2010 ISBN 978-1907934001.
- Kenneth H. Rosen, Discrete Mathematics and Its Applications 6th ed. McGraw Hill. ISBN 0-07-288008-2, and companion web site.
- Ralph P. Grimaldi, Discrete and Combinatorial Mathematics: An Applied Introduction 5th ed. Addison Wesley. ISBN 0-20-172634-3
- Susanna S. Epp, Discrete Mathematics with Applications Brooks Cole. ISBN 978-0495391326
- Jiří Matoušek & Jaroslav Nešetřil, Invitation to Discrete Mathematics, OUP, ISBN 978-0198502081.
- Mathematics Archives Archived 2011-08-29 at the Wayback Machine, Discrete Mathematics links to syllabi, tutorials, programs, etc.
- Andrew Simpson, Discrete Mathematics by Example McGraw Hill. ISBN 0-07-709840-4
- Kenneth A. Ross & Charles R. B. Wright, Discrete Mathematics. ISBN 978-8131790618