Discrete Mathematics in the Real World.
Discrete mathematics is a topic used widely in the field of computer science. Basically, discrete mathematics deals with objects that are discrete in nature rather than continuous. To give an example, a set of random integers or graphs may be studied under discrete mathematics as they aren’t continuous but certain concepts like Euclidean geometry or calculus may not be included as they are continuous in nature.
Theoretical computer science encompasses discrete mathematics that is relevant to computers. It makes extensive use of graph theory and mathematical reasoning. The analysis of algorithms and data structures is included in theoretical computer science. Computability, which is closely related to logic, investigates what can be calculated in principle, whereas complexity studies the time, space, and other resources consumed by computations. Computability is closely related to automata theory and formal language theory. To model computer systems, Petri nets and process algebras are employed, while methods from discrete mathematics are used to analyse VLSI electronic circuits. Computational geometry use algorithms to solve geometrical issues, whereas computer image analysis employs them to create image representations. The study of numerous continuous computational topics is also included in theoretical computer science.
What exactly is discrete mathematics?
Well, its just the study of mathematical structures which happen to be discrete in nature , i.e structures in which all the points are isolated from each other. This can include graphs, integers or some kind of logical statements. It will not include concepts which may be continuous in nature such as real numbers, calculus or Euclidean geometry.
Research in this field really took off when introducing digital computers which often use discrete steps and store data in discrete bits hen they operate. 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.
Subjects in discrete mathematics
Logic —
Logic is the study of correct reasoning or good arguments. It is often defined in a more narrow sense as the science of deductively valid inferences or of logical truths.
Set theory —
Set theory is the mathematical theory of well-determined collections, called sets, of objects that are called members, or elements, of the set. Pure set theory deals exclusively with sets, so the only sets under consideration are those whose members are also sets.
Number theory —
Number theory (or arithmetic or higher arithmetic in older usage) is a branch of pure mathematics devoted primarily to the study of the integers and integer-valued functions. Number theorists study prime numbers as well as the properties of mathematical objects made out of integers (for example, rational numbers) or defined as generalizations of the integers (for example, algebraic integers).
Combinatorics —
Combinatorics is an area of mathematics primarily concerned with counting, both as a means and an end in obtaining results, and certain properties of finite structures. It is closely related to many other areas of mathematics and has many applications ranging from logic to statistical physics and from evolutionary biology to computer science.
Graph theory —
In mathematics, graph theory is the study of graphs, which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of vertices (also called nodes or points) which are connected by edges (also called links or lines).
Algorithmics
Algorithmics is the systematic study of the design and analysis of algorithms. It is fundamental and one of the oldest fields of computer science. It includes algorithm design, the art of building a procedure which can solve efficiently a specific problem or a class of problem, algorithmic complexity theory, the study of estimating the hardness of problems by studying the properties of the algorithm that solves them, or algorithm analysis, the science of studying the properties of a problem, such as quantifying resources in time and memory space needed by this algorithm to solve this problem.
Computability and complexity theories
Computability is the ability to solve a problem in an effective manner. It is a key topic of the field of computability theory within mathematical logic and theory of computation within computer science. The computability of a problem is closely linked to the existence of an algorithm to solve the problem. Complexity theory and organizations, also called complexity strategy or complex adaptive organizations, is the use of the study of complex systems in the field of strategic management and organizational studies. It draws from research in the natural sciences that examines uncertainty and non-linearity. Complexity theory emphasizes interactions and the accompanying feedback loops that constantly change systems. While it proposes that systems are unpredictable, they are also constrained by order-generating rules.
• Linear algebra —
Linear algebra is a field of mathematics that is universally agreed to be a prerequisite to a deeper understanding of machine learning.
Although linear algebra is a large field with many esoteric theories and findings, the nuts and bolts tools and notations taken from the field are practical for machine learning practitioners.
Linear algebra is central to almost all areas of mathematics
Functions –
Functions were originally the idealization of how a varying quantity depends on another quantity. For example, the position of a planet is a function of time. In mathematics, a function from a set X to a set Y assigns to each element of X exactly one element of Y. The set X is called the domain of the function and the set Y is called the codomain of the function.
• Probability –
Probability is the branch of mathematics concerning numerical descriptions of how likely an event is to occur, or how likely it is that a proposition is true. The probability of an event is a number between 0 and 1, where, roughly speaking, 0 indicates the impossibility of the event and 1 indicates certainty. The higher the probability of an event, the more likely it is that the event will occur.
• Proofs —
A mathematical proof is an inferential argument for a mathematical statement, showing that the stated assumptions logically guarantee the conclusion. The argument may use other previously established statements, such as theorems; but every proof can, in principle, be constructed using only certain basic or original assumptions known as axioms, along with the accepted rules of inference.
USES OF DISCRETE STRUCTURES IN COMPUTER SCIENCE
Now us (the authors) being IT students we feel like its necessary to show how important discrete structures are in the field of computer science. Especially because a lot of the applications of discrete mathematics that we see on a daily basis originate from the fact that they are needed in the field of computer science.
Theoretical computer science encompasses discrete mathematics that is relevant to computers. It makes extensive use of graph theory and mathematical reasoning. The analysis of algorithms and data structures is included in theoretical computer science. Computability, which is closely related to logic, investigates what can be calculated in principle, whereas complexity studies the time, space, and other resources consumed by computations. Computability is closely related to automata theory and formal language theory. To model computer systems, Petri nets and process algebras are employed, while methods from discrete mathematics are used to analyse VLSI electronic circuits. Computational geometry use algorithms to solve geometrical issues, whereas computer image analysis employs them to create image representations. The study of numerous continuous computational topics is also included in theoretical computer science.
Real-Life Application of Discrete Mathematics
Railway planning
Deciding how to expand train rail lines, train timetable scheduling, and scheduling crews and equipment for train trips use both graph theory and linear algebra.
Google Maps
Google Maps utilizes discrete mathematics to calculate the quickest driving routes and timeframes. There is a simplified way that works with small maps, and there are complexities involved in converting to huge maps.
Cell phone communications:
Linear algebra and information theory are used to make efficient use of the broadcast spectrum for mobile phones. Graph theory or discrete optimization can be used to assign frequencies so that there is no interference with surrounding phones.
Delivery Route Problems:
If you need to leave home, visit a sequence of locations each exactly once and then return home — -such as might happen with a newspaper delivery route or scheduling bread to be delivered from a bakery to grocery stores — -this is known as the traveling salesperson problem, or TSP. There is a definitive source on the history of, and state-of-the-art work on TSP.
Designing password criteria is a counting problem:
Is the space of passwords chosen large enough that a hacker can’t break into accounts just by trying all the possibilities.
Voting systems:
There are different methods for voting — -not just the common cast-a-ballot-for-exactly-one-candidate method. The study of possible voting methods and how well their outcomes reflect the intent of the voters uses discrete mathematics.
Food Webs:
A food web describes the ways in which a set of species eat (and don’t eat) each other. They can be studied using graph theory.
Discrete Math in Cryptography
The field of cryptography, which is the study of how to create security structures and passwords for computers and other electronic systems, is based entirely on discrete mathematics. This is partly because computers send information in discrete — or separate and distinct — bits. Number theory, one important part of discrete math, allows cryptographers to create and break numerical passwords. Because of the quantity of money and the amount of confidential information involved, cryptographers must first have a solid background in number theory to show they can provide secure passwords and encryption methods.
Relational Databases
Relational databases play a part in almost every organization that must keep track of employees, clients or resources. A relational database connects the traits of a certain piece of information. For example, in a database containing client information, the relational aspect of this database allows the computer system to know how to link the client’s name, address, phone number and other pertinent information. This is all done through the discrete math concept of sets. Sets allow information to be grouped and put in order. Since each piece of information and each trait belonging to that piece of information is discrete, the organization of such information in a database requires discrete mathematical methods.
Conclusion:
Discrete mathematics is a very vast topic whose uses can be as simple as calculating the probability of a coin flip or as complex as helping in the medical field with surgery or other such difficult tasks. Discrete mathematics helps us make sense of data or structures which may otherwise seem random and help us draw useful conclusions from them.
Authors:-
- Aditya Dere
- Anushka Ahire
- Mandar Ambulkar
- Daksh Dagariya
- Vedant Jore
References
- Sk, Amanathulla & Bera, Biswajit & Pal, Madhumangal. (2021). Real world applications of discrete mathematics. 09. 152–158. 10.26637/MJM0901/0025.
- http://techiesgazette.marwadiuniversity.ac.in/?p=584
- http://cybercomputing.blogspot.com/2012/06/discrete-mathematics-applications-and.html
- https://www.javatpoint.com/applications-of-discrete-mathematics-in-computer-science
