Discrete mathematics

Objects studied in discrete mathematics include integers, graphs, and statements in logic.

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.

Conversely, computer implementations are significant in applying ideas from discrete mathematics to real-world problems.

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 by ACM and MAA into a course that is basically intended to develop mathematical maturity in first-year students; therefore, it is nowadays a prerequisite for mathematics majors in some universities as well.

Included within theoretical computer science is the study of algorithms and data structures.

Petri nets and process algebras are used to model computer systems, and methods from discrete mathematics are used in analyzing VLSI electronic circuits.

Closely related is coding theory which is used to design efficient and reliable data transmission and storage methods.

Logic is the study of the principles of valid reasoning and inference, as well as of consistency, soundness, and completeness.

The study of mathematical proof is particularly important in logic, and has accumulated to automated theorem proving and formal verification of software.

Logical formulas are discrete structures, as are proofs, which form finite trees[10] or, more generally, directed acyclic graph structures[11][12] (with each inference step combining one or more premise branches to give a single conclusion).

Indeed, contemporary work in descriptive set theory makes extensive use of traditional continuous mathematics.

Combinatorics studies the ways in which discrete structures can be combined or arranged.

Analytic combinatorics concerns the enumeration (i.e., determining the number) of combinatorial structures using tools from complex analysis and probability theory.

They can model many types of relations and process dynamics in physical, biological and social systems.

It has applications to cryptography and cryptanalysis, particularly with regard to modular arithmetic, diophantine equations, linear and quadratic congruences, prime numbers and primality testing.

Topics that go beyond discrete objects include transcendental numbers, diophantine approximation, p-adic analysis and function fields.

Such a discrete function could be defined explicitly by a list (if its domain is finite), or by a formula for its general term, or it could be given implicitly by a recurrence relation or difference equation.

For instance, where there are integral transforms in harmonic analysis for studying continuous functions or analogue signals, there are discrete transforms for discrete functions or digital signals.

In algebraic geometry, the concept of a curve can be extended to discrete geometries by taking the spectra of polynomial rings over finite fields to be models of the affine spaces over that field, and letting subvarieties or spectra of other rings provide the curves that lie in that space.

The history of discrete mathematics has involved a number of challenging problems which have focused attention within areas of the field.

Formal verification of statements in logic has been necessary for software development of safety-critical systems, and advances in automated theorem proving have been driven by this need.

Several fields of discrete mathematics, particularly theoretical computer science, graph theory, and combinatorics, are important in addressing the challenging bioinformatics problems associated with understanding the tree of life.

Graphs such as these are among the objects studied by discrete mathematics, for their interesting mathematical properties , their usefulness as models of real-world problems, and their importance in developing computer algorithms .
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 A 4 .
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. [ 15 ]