Twenty or thirty years ago, computer science was basically a branch of mathematics.
Branches.
Nowadays, computer science has a wide range of research fields and a large number of researchers, which in turn has promoted its development in many aspects.
The development of mathematics, in a sense, can be said that children grow taller than their mothers.
But no matter what, the child will always have the mother's blood. This kind of blood is the foundation of mathematics.
Computer science in, that is, theoretical computer science.
Another intersection of modern computer science and mathematics is computational mathematics/numerical analysis/scientific calculation, which is not included in the theory traditionally.
About computer science. Therefore, this paper ignores all computational mathematics.
What is the word most often put together with theoretical computer science? A: Discrete mathematics. The two are so closely related.
Cut, so that it has become synonymous on many occasions.
Traditionally, mathematics is centered on analysis. Students in the department of mathematics have to study mathematical analysis for three or four semesters before answering.
Change, real change, functionality and so on. Real variables and functionals are considered by many people as the introduction to modern mathematics. In physics, chemistry and engineering
In application, it also focuses on analysis.
With the emergence of computer science, some previously neglected branches of mathematics suddenly become important. It has been found that this
The mathematical objects handled by some branches are obviously different from traditional analysis: the objects of analysis and research are continuous, so there are differences.
, integral becomes the basic operation; However, the research objects of these branches are discrete, so there are few opportunities for such projects.
Count. People therefore call these branches "discrete mathematics". The name of "discrete mathematics" is getting louder and louder, which eventually leads to
The traditional branch of mathematics centered on analysis is relatively called "continuous mathematics".
After decades of development, discrete mathematics has basically stabilized. It is generally believed that discrete mathematics includes the following disciplines:
1) set theory, mathematical logic, meta-mathematics. This is the foundation of mathematics and computer science.
2) Graph theory, algorithmic graph theory; Combinatorial mathematics, combinatorial algorithm. The core of computer science, especially theoretical computer science is
Algorithms, and a large number of algorithms are based on graphs and combinations.
3) Abstract algebra. Algebra is ubiquitous and very important in mathematics. In computer science, people are surprised.
People find that algebra has so many uses.
However, is theoretical computer science just as simple as adding a "discrete" hat to mathematics? All the way to the big one
About ten years ago, a master finally told us:No. D.E.Knuth (how great he is, I don't think I need to talk nonsense) opened a brand-new course concrete mathematics at Stanford. The word concrete has two meanings here:
First, for abstraction. Knut thinks that the object of traditional mathematics research is too abstract, which leads to specific problems.
Not caring enough. He complained that the mathematics he needed often didn't exist in his research, so he had to create some by himself.
Mathematics in order to directly meet the needs of application, he should advocate "concrete" mathematics. Let me explain it briefly here. For example, in set theory, mathematicians are concerned with the most fundamental problems-the various properties of axiomatic systems and so on. Mathematicians believe that it is not important what the properties of some specific sets, common sets, relationships and mappings are. However, it is these concrete things that are applied in computer science. Knut was the first to see this and was worthy of being the first computer person in the world.
Second, it is continuous plus discrete. Regardless of continuous mathematics or discrete mathematics,
All useful math!
The front is mainly from the mathematical point of view. From the computer point of view, theoretical computer science is the main research field at present.
Including computability theory, algorithm design and complexity analysis, cryptography and information security, distributed computing theory and
Line computing theory, network theory, bioinformatics computing, computational geometry, programming language theory and so on. These fields interact.
Cross, and new topics are constantly raised, it is difficult to sort out a clue.
Here are some random examples.
Because of the application demand, cryptography has become a hot research topic. Cryptography is based on number theory (especially computational number theory)
On the basis of algebra, information theory, probability theory and stochastic process, graph theory and combinatorics are sometimes used.
Many people think that cryptography is encryption and decryption, and encryption is scrambling data with a function. This is completely wrong.
Modern cryptography includes at least the following levels:
First, the basis of cryptography. For example, is it really difficult to decompose a large number? Is there a universal tool to prove that the protocol is correct?
Really?
Second, the basic discipline of cryptography. For example, better one-way function, signature protocol and so on.
Third, the advanced problems of cryptography. For example, the length of zero knowledge proof and the method of secret sharing.
Fourth, the new application of cryptography. Such as digital cash, traitor tracking, etc.