[Math] how discrete mathematics is related to computerscience

computational complexitycomputer sciencediscrete mathematicsdiscrete optimization

I have this basic question for sometime since i came across discrete mathematics, hence this question. How discrete mathematics is related to computer science. How its notions are used in the field of computer science.

Best Answer

I think a lot of it comes from the fact that discrete structures are easy to operate on in computing, and that computations themselves are usually modeled by discrete concepts.

For example, strictly speaking, formal language theory is a branch of discrete mathematics. It deals with finite structures (strings) in a from a countably-infinite universe. Modelling a yes/no problem as a set of strings allows for a large degree of formal reasoning about computations, so knowing the math/theory behind it is useful for a computer scientist.

Likewise, lots of problems can be reduced to discrete problems. For example, say you want to write a program which schedules a large set of classes so that no student has two classes at the same time. This is in fact a graph theory problem, known as "graph coloring". By knowing the theory behind graph coloring, a programmer realizes first that the problem is NP-complete, so there's not likely a fast general solution, but also can use pre-defined solutions for special types of graphs (chordal, comparability, planar, etc.)

Also, computer science and discrete math share a lot of ground. Both are heavily based in the concepts of recursion/induction.

Perhaps a more relevant question is why continuous mathematics isn't widely applied to computer science?