Graphs such as these are among the objects studied by discrete mathematics, for their interestingmathematical properties, their usefulness as models of real-world problems, and their importance in developing computeralgorithms.
The set of objects studied in discrete mathematics can be finite or infinite. The termfinite mathematics is sometimes applied to parts of the field of discrete mathematics that deal 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 ofdigital 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 ofcomputer science, such ascomputer algorithms,programming languages,cryptography,automated theorem proving, andsoftware development. Conversely, computer implementations are significant in applying ideas from discrete mathematics to real-world problems.
Although the main objects of study in discrete mathematics are discrete objects,analytic methods from "continuous" mathematics are often employed as well.
In university curricula, discrete mathematics appeared in the 1980s, initially as a computer science support course; its contents were somewhat haphazard at the time. The curriculum has thereafter developed in conjunction with efforts byACM andMAA into a course that is basically intended to developmathematical maturity in first-year students; therefore, it is nowadays a prerequisite for mathematics majors in some universities as well.[6][7] Some high-school-level discrete mathematics textbooks have appeared as well.[8] At this level, discrete mathematics is sometimes seen as a preparatory course, likeprecalculus in this respect.[9]
TheFulkerson Prize is awarded for outstanding papers in discrete mathematics.
Theoretical computer science includes areas of discrete mathematics relevant to computing. It draws heavily ongraph theory andmathematical logic. Included within theoretical computer science is the study of algorithms and data structures.Computability studies what can be computed in principle, and has close ties to logic, while complexity studies the time, space, and other resources taken by computations.Automata theory andformal language theory are closely related to computability.Petri nets andprocess algebras are used to model computer systems, and methods from discrete mathematics are used in analyzingVLSI electronic circuits.Computational geometry applies algorithms to geometrical problems and representations ofgeometrical objects, whilecomputer image analysis applies them to representations of images. Theoretical computer science also includes the study of various continuous computational topics.
TheASCII codes for the word "Wikipedia", given here inbinary, provide a way of representing the word ininformation theory, as well as for information-processingalgorithms.
Information theory involves the quantification ofinformation. Closely related iscoding theory which is used to design efficient and reliable data transmission and storage methods. Information theory also includes continuous topics such as:analog signals,analog coding,analog encryption.
Logical formulas are discrete structures, as areproofs, which form finitetrees[10] or, more generally,directed acyclic graph structures[11][12] (with eachinference step combining one or morepremise branches to give a single conclusion). Thetruth values of logical formulas usually form a finite set, generally restricted to two values:true andfalse, but logic can also be continuous-valued, e.g.,fuzzy logic. Concepts such as infinite proof trees or infinite derivation trees have also been studied,[13] e.g.infinitary logic.
Set theory is the branch of mathematics that studiessets, which are collections of objects, such as {blue, white, red} or the (infinite) set of allprime numbers.Partially ordered sets and sets with otherrelations have applications in several areas.
In discrete mathematics,countable sets (includingfinite sets) are the main focus. The beginning of set theory as a branch of mathematics is usually marked byGeorg Cantor's work distinguishing between different kinds ofinfinite set, motivated by the study of trigonometric series, and further development of the theory of infinite sets is outside the scope of discrete mathematics. Indeed, contemporary work indescriptive set theory makes extensive use of traditional continuous mathematics.
Graph theory, the study ofgraphs andnetworks, is often considered part of combinatorics, but has grown large enough and distinct enough, with its own kind of problems, to be regarded as a subject in its own right.[14] Graphs are one of the prime objects of study in discrete mathematics. They are among the most ubiquitous models of both natural and human-made structures. They can model many types of relations and process dynamics in physical, biological and social systems. In computer science, they can represent networks of communication, data organization, computational devices, the flow of computation, etc. In mathematics, they are useful in geometry and certain parts oftopology, e.g.knot theory.Algebraic graph theory has close links with group theory andtopological graph theory has close links totopology. There are alsocontinuous graphs; however, for the most part, research in graph theory falls within the domain of discrete mathematics.
Discrete geometry and combinatorial geometry are about combinatorial properties ofdiscrete collections of geometrical objects. A long-standing topic in discrete geometry istiling of the plane.
Inalgebraic geometry, the concept of a curve can be extended to discrete geometries by taking thespectra ofpolynomial rings overfinite fields to be models of theaffine spaces over that field, and lettingsubvarieties or spectra of other rings provide the curves that lie in that space. Although the space in which the curves appear has a finite number of points, the curves are not so much sets of points as analogues of curves in continuous settings. For example, every point of the form for a field can be studied either as, a point, or as the spectrum of thelocal ring at (x-c), a point together with a neighborhood around it. Algebraic varieties also have a well-defined notion oftangent space called theZariski tangent space, making many features of calculus applicable even in finite settings.
Inapplied mathematics,discrete modelling is the discrete analogue ofcontinuous modelling. In discrete modelling, discrete formulae are fit todata. A common method in this form of modelling is to userecurrence relation.Discretization concerns the process of transferring continuous models and equations into discrete counterparts, often for the purposes of making calculations easier by using approximations.Numerical analysis provides an important example.
The history of discrete mathematics has involved a number of challenging problems which have focused attention within areas of the field. In graph theory, much research was motivated by attempts to prove thefour color theorem, first stated in 1852, but not proved until 1976 (by Kenneth Appel and Wolfgang Haken, using substantial computer assistance).[15]
Several fields of discrete mathematics, particularly theoretical computer science, graph theory, andcombinatorics, are important in addressing the challengingbioinformatics problems associated with understanding thetree of life.[17]
^Biggs, Norman L. (2002),Discrete mathematics, Oxford Science Publications (2nd ed.), The Clarendon Press Oxford University Press, p. 89,ISBN9780198507178,MR1078626,Discrete Mathematics is the branch of Mathematics in which we deal with questions involving finite or countably infinite sets.
^Brotherston, J.; Bornat, R.; Calcagno, C. (January 2008). "Cyclic proofs of program termination in separation logic".ACM SIGPLAN Notices.43 (1):101–112.doi:10.1145/1328897.1328453.
