Application of Discrete Mathematics in Computer Science
Discrete Mathematics play a vital role in software Development in Computer science . Almost ever program is based on some Mathematical Model . To explore the application of Discrete mathematics in computer science let us begin from the evolution of computer languages and how mathematics played important role in the evolution of computer languages .
Programming languages and contribution of Mathematics : An overview
Here, we will not explore the history of programming languages in detail but we will only focus on those parts which are concerned and connected to our topic. Computers are electronic devices which are made of registers ,logics & gates etc. All the electronic devices can only understand the ON and OFF logic. Mathematics fertilized logic with the mathematical logic operations and number system. Despite the complex hardware the computer systems operates on a very rudimentary level .10 symbol number system(0,1,2,…9) is too complicated for the computer system to process. At the logic level a computer can understand only two states i.e. ON logic and OFF logic. The ON state is represented by Binary 1 and OFF state is represented by Binary 0.In modern computers the most basic unit of information is a BIT (0 or 1).A processor reads some sequence of Bits and then Performs some binary operation on them. The information which is processed by processor generates some output. There are lot of abstractions involved the whole process.(abstractions like conversion of user input to binary information, than processing the information in the processor and then again converting the processor’s binary output to human readable format).
All the programming languages which are developed till now are Greatly influenced by Mathematics. we can say that the evolution of computer and programming is made possible only due to Mathematics and Mathematical Logic involved in it . Mathematical logic is a subfield of mathematics with close connections to the foundations of mathematics and theoretical computer Science .each and every assignment statements, subroutines, conditional statements, iteration, etc everything follows some mathematical Logic which is rooted from low level binary logic to high level computational logic.
The history of Binary number system also known as BASE-2-NUMBER is very interesting and worth reading. evidence proves that binary numbers were used in India prior to around 5th–2nd centuries, more than 1500 years before their discovery in the west. The source of this discovery is a text of music by Pingala named “Chhandahshastra” meaning science of meters. Pingala developed mathematical concepts for describing prosody(poem), and in doing so he presented the first known description of a binary number system. The modern Binary numbers were discovered in the west by German mathematician Gottfried Leibniz in 1695 (Suggested Reading Leibniz G., Explication de l’Arithmétique Binaire, Die Mathematische Schriften, ed. C. Gerhardt, Berlin 1879, vol.7, p.223;). Let’s not Deviate focus from our topic .
In 1940’s with the invention of first electronic computer ,the first recognizable programming languages came into existence which is basically a low level assemble language. The Limited speed and limited memory capacity forced Programmers to write hand tuned assemble language programs. These assembly languages includes are very complex instructions. Even the programming of simple task is difficult and complex in assemble languages. These languages generally have binary information which needs to be converted into hex decimal codes to make it more Human Readable.
Between 1943-1945 Konrad Zuse proposed a programming language Plankalkül which is described for engineering purposes. It was the first high-level non-von Neumann programming language to be designed for a computer, Plankalkül was not published at that time due to the circumstances(2nd world war). In 1948 Zuse published a paper about the Plankalkül in the “Archiv der Mathematik” but still did not attract much feedback (Paper : for a long time to come programming a computer would only be thought of as programming with machine code). Plankalkül has drawn comparisons to APL(name after the book : A Programming Language) and relational algebra. It includes assignment statements, subroutines, conditional statements, iteration, floating point arithmetic, arrays, hierarchical record structures, assertions, exception handling, and other advanced features such as goal-directed execution. Plankalkül used Logical notation which was proposed in Begriffsschrift ( “concept-script”) a book on logic by Gottlob Frege, published in 1879. The Begriffsschrift was arguably the most important publication in logic since Aristotle founded the subject. The work of Plankalkül was influenced by Heinz Rutishauser. Heinz Rutishauser (30 January 1918 in Weinfelden, Switzerland – 10 November 1970 in Zürich) was a Swiss mathematician and a pioneer of modern numerical mathematics and computer science.
Between 1950 to 1957 lot of different programming languages like ARITH-MATIC, MATH-MATIC, MATRIX_MATH, FLOW-MATIC, etc are proposed .( Check the programming language timeline at http://en.wikipedia.org/wiki/Timeline_of_programming_languages)
In 1957 Fortran-I was introduced which is developed by IBM at their campus in south San Jose, California for scientific and engineering applications. In 1954-1955 FORTRAN concept was introduced. The Name FORTRAN is derived from The IBM Mathematical Formula Translating System. It is one of the most popular languages in the area of high-performance computing and is the language used for programs that benchmark and rank the world’s fastest supercomputers. A significant improvement in programming languages and new programming languages which came overtime put more abstractions on internal design of programming and the mathematics involved in it.
Later in 1957 Noam Chomsky published a book Syntactic Structures in which he developed the idea that each sentence in a language has two levels of representation — a deep structure and a surface structure. In 1959 Noam Chomsky introduced the mathematical Structure of a Grammar. This mathematical structure seeded all the modern programming languages.
In the summary written by ROBERT W. FLOYD in his paper The Syntax of Programming Languages-A Survey says
” The syntactic rules for many programming languages have been expressed by formal grammars, generally variants of phrase-structure grammars. The syntactic analysis essential to translation of programming languages can be done entirely mechanically for such languages. Major problems remain in rendering analyzers efficient in use of space and time and in finding fully satisfactory formal grammars for present and future programming languages. “
References and Suggested Readings :