Learning Computing History

A Brief History of Discrete Structures

Discrete Structures: “The abstract mathematical structures used to represent discrete objects and relationships between these objects” --Kenneth H. Rosen.  It is the conceptual foundation and backbone for computer science since all digital information processing is the manipulations of discrete structures, discrete, a distinct separable element; structures, objects made by simpler objects or elements following a definite pattern.   

Mathematics relevant of discrete structures to the computer science includes:

• Functions, relations, and sets,

• Basic logic,

• Proof techniques,

• Basics of counting,

• Graphs and trees,

• Discrete probability

From computer science of view, it concerns mathematical reasoning, combinatorial analysis, discrete structures, algorithmic thinking & applications and modeling. It provides much of the basic concept for data structures, automata theory, operating systems, database, formal languages and more. 

The Mathematicians of Discrete Structures and Pioneers of Its Computing Applications:

• C. 350 B.C.E. Euclid author of the most successful mathematics book -- “Elements”
• C. 780-C. 850 Abu Ja’far Mohammed ibn Musa al-Khwarizmi composed the oldest works on arithmetic and algebra; he first introduced the Hindu numbers to Europe, as the very name “algorism” signifies.
• 1180 -1228 Leonardo Pisano Fibonacci introduced Arabic notation to European world for numerals and algorithms for arithmetic, famous for his “rabbit problem”, and work in finding integer solutions to equations.
• 1596-1650 Rene Descartes  French mathematician and philosopher, best known for his contributions to analytic geometry
• 1601-1665 Pierre De Fermat one of the inventors of analytic geometry and contributors to calculus, gave probability theory a mathematical basis
• 1623–1662 Blaise Pascal along with Fermat laid the foundations for the probability theory.
• 1654-1705 James Bernoulli Swiss mathematicians, important contributions on probability theory and in enumerations.
• 1707-1783 Leonhard Euler many contributions including number theory, combinatorics, analysis and their applications.
• 1735-1796 Alexandre-Theophile Vandermonde fundamental contributions on the roots of equations, the theory of determinants and the knight’s tour problem.
• 1749-1827 Pierre Simon Laplace contributions to celestial mechanics and statistics, one of the founders of probability theory.
• 1777-1855 Karl Friedrich Gauss Laid the foundations for modern number theory with the book of “Disquisitions Arithmeticae” in 1801
• 1795-1870 Gabriel Lame contributions in number theory, applied mathematics and thermodynamics.
• 1805-1859 G. Lejeune Dirichlet the first person to master Gauss’s Disquisitions Arithmeticae, and made many important discoveries in number theory.
• 1806-1871 Augustus De Morgan coined the term “mathematical induction”, gave a geometric interpretation of complex numbers, introduced De Morgan’s laws and knows as a reformer of mathematical logic.
• 1815-1864 George Boole inventor or Boolean algebra, which wide used in telephone switching and modern computers, and is regarded as a fundamental step for computer revolution.
• 1821-1894 Pafnuty Lvovich Chebyshev set the foundations of approximation theory, first one to recognize the general concept of orthogonal polynomials and also some contributions made to the probability theory.
• 1821-1895 Arthur Cayley developed the algebra of matrices, work in non-euclidean geometry and n-dimensional geometry.
• 1832-1898 Charles Lutwidge Dodgson a mathematical logician, developed a mechanical test of validity and, first used truth tables.
• 1834-1923 John Venn contributions to symbolic logic, probability theory
• 1837-1920 Paul Gustav Heinrich Bachmann a complete survey of number theory both the results and the methods of proof, elementary number theory, irrational numbers and Fermat’s Last Theorem. He also introduced the big-O notation.
• 1839-1910 Julius Peter Christian Petersen Known for contributions to graph theory.
• 1839-1914 Charles Sanders Pierce contributions to logic, set theory, abstract algebra and the philosophy of mathematics.
• 1845-1918 George Cantor the founder of set theory, he discovered that the set of real numbers is uncountable.
• 1849-1922 Alfred Bray Kempe contributions to kinematics and mathematical logic, known for his fallacious proof of the four color theorem
• 1877-1938 Edmund Landau main contribution is in analytic number theory, the distribution of primes.
• 1877-1947 Godfrey Harold Hardy had made important contributions to many branches of pure mathematics.
• 1878-1956 Jan Lukasiewicz contributions on three-valued logic and known for his introduction of Polish notation.
• 1887-1920 Srinivasa Ramanujan contributions to number theory, continued fractions, infinite series and elliptic functions.
• 1896-1980 Kazimierz Kuratowski contributions in topology, set theory, compactness and metric spaces
• 1898-1979 Helmut Hasse hand made fundamental contributions to algebraic number theory.
• 1903-1930 Frank Plumpton Ramsey creator of  Ramsey theory
• 1903-1995 Alonzo Church one of the founders for Symbolic Logic, contributions to computability theory, famous for the Church-Turing thesis
• 1908 Willard Van Orman Quine discovered “Quine-McCluskey” method, contributions including the theory of knowledge, logic and set theory, philosophies of logic and language.
• 1909-1994 Stephen Cole Kleene  contributions to the theory of recursive functions, investigating questions of computability and decidability and proved automata theory
• 1912-1954 Alan Mathison Turing inventor of “Turing machine”  - a general model of a computing machine
• 1913-1996 Paul Erdos made many contributions to combinatorics and number theory
• 1915 John Wilder Tukey best known for the invention, along with J.W. Cooley, of fast Fourier Transform. Also contributions to statistics.
• 1916 Claude Elwood Shanon one of the first people to use bits to represent information.
• 1924 Maurice Karnaugh made fundamental contributions to digital techniques in computing and telecommunication.
• 1924 John Backus the inventor of the first high level computer language FORTRAN, the inventor of standard notation to describe the syntax of a high level programming language -- Backus Naur Form (BNF), and functional programming language FP.
• 1928 Joseph Bernard Krushal contributions on minimum spanning trees, and multidimensional scaling
• 1928 Peter Naur work in building the first Danish computer and developing the programming language - ALGOL
• 1929 Edward J. McCluskey contributions in fault-tolerant computing, computer architecture, testing, and logic design
• 1930 Edsger Wybe Dijkstra one of the forceful proponents of programming, and made fundamental contributions to the OS, programming languages, and algorithms.
• 1934 C. A. R. Hoare many contributions to the theory of PL and programming methodology, also the creator of “quick sort”.
• 1935 Stephen Warshall contributions on research and development in OS, compiler, language design and operation research.
• 1938 Donald E. Knuth  founder of the computational complexity and fundamental contributions to compilers
• 1939 Neil Sloane coined the “kissing problem” and work including network design, coding theory and sphere packing.

 Summary: Discrete Structures is not only important on how to think mathematically, also on how to efficiently apply those using algorithms.  It is the finite mathematical concepts that form the absolutely core of computer science.