A core problem of computer theory-from mathematics;
I remember when I was a freshman, I went to high school every Saturday and did my homework every day (at that time, it was a six-day work system). Many students exclaimed that they had gone to the wrong door: What department do we study here? Yes, you are at the right door. This is the Department of Computer Science and Technology. The tradition of China's computer department is to train people to do academic research, especially theoretical research (the direction is not necessarily problematic, but the work is not so satisfactory). In the final analysis, the theoretical research of computer, such as network security, graphics and iconology, audio-visual processing, has a great relationship with mathematics, although it may be non-mainstream mathematics in the eyes of orthodox mathematicians. Here I also want to clarify my point of view: As we all know, mathematics is a theory abstracted from real life. The reason why people abstract reality into theory is to use the abstracted theory to better guide practice. Some mathematical researchers like to use some existing theoretical knowledge to deduce several inferences, but they don't know that one is that it is probably wrong to consider the problem incompletely, and the other is that his inference can't find a prototype in real life and can't guide practice. Strictly speaking, I am not an idealist. Integrating theory with practice in political lessons has always been a beacon to guide me to learn scientific and cultural knowledge (at least I think computer science and technology should be this direction).
In fact, it is not enough for our computer department to learn advanced mathematics and optics (typical engineering colleges generally offer advanced mathematics). We should study mathematical analysis like the department of mathematics (the department of computer science in Tsinghua seems to offer mathematical analysis), and our students majoring in computer science have complicated feelings about it. It is biased towards proving mathematics courses, which is very helpful for us to cultivate good analytical ability. My software engineering tutor, Wang Yihua, a teacher from the School of Mathematics and Physics of Beijing University of Technology, once taught us that most students in the Department of Mathematics are engaged in software design and analysis, while most students in the Department of Computer Science are engaged in programmer work. The reason is that the analytical reasoning ability of mathematics students is far above ours in training. The strange phenomenon that appeared in that year was that the students of computer department were among the best in high school mathematics (I hope they didn't offend other students), and the teaching hours were second only to those of mathematics department, but the effect was not satisfactory after learning. Are all the students not working hard? I didn't see it. I wonder if it's in the wrong direction. What is the reason? Thought-provoking.
My humble opinion is that students in computer department have different requirements for mathematics, but they are even more different from physics. The so-called "Advanced Mathematics" for non-mathematics majors is nothing more than deleting the difficult theoretical parts in mathematical analysis and emphasizing the application of formulas. For the computer department, the most useful part of mathematical analysis is the theoretical part that has been deleted. To put it bluntly, for computer majors, the so-called "engineering mathematics" that pursues calculation has completely gone into a misunderstanding. Can you understand mathematics by remembering a bunch of formulas of surface integral? It's better to check now, so why bother to remember. Or just use math or Matalab. My favorite thing to do in the department is to recommend reference books to my younger brothers and sisters. Among China's books on mathematical analysis, Peking University and Zhang Zhusheng's New Lecture on Mathematical Analysis is generally considered the best. In case you are really good at math, you can read Fichkingolz's Calculus Course-but I don't think it's necessary. After all, you don't want to transfer to the math department. Jimmy Dovich's Mathematical Analysis Problem Set is basically a calculation thing. The book is famous, but it may not be suitable for us. Again, what is important is the establishment of mathematical thought. Living in the information society, we pursue high efficiency. Let's leave the calculation to the computer. However, the mathematical analysis of Fudan University seems to be a good textbook.
China's so-called higher algebra is equal to linear algebra plus a little polynomial theory. I think this has a good side, because it can make students feel that algebra is a structure earlier, rather than a pile of matrices. I have to mention "Advanced Algebra" edited by Cheng Sen and Sheng of Nanda Lin, which is quite comfortable. This book contains the basic elementary results of polynomial and linear algebra quite comprehensively, and also provides some useful and profound contents, such as Sturm sequence, Shermon-Morrison formula, generalized inverse matrix and so on. It can be said that as an undergraduate, if you can understand this book thoroughly, then you are a master. The better advanced algebra textbooks in China are the ones used by Tsinghua Computer Department, which are published by Tsinghua Publishing House and there are many in bookstores. From the perspective of abstract algebra, the results in higher algebra are just some examples of the properties of algebraic systems. Mr. Mo Zongjian's Algebra has a profound discussion on this. However, Mr. Mo's book is too profound for an undergraduate to accept. I might as well wait until I am mature.
As mentioned above, computer science students learn advanced mathematics: they know what it is, and more importantly, why it is. The purpose of your study should be: to apply abstract theory to practice, not only to master the problem-solving methods, but also to master the problem-solving ideas. Learning theorems is not a simple application, but mastering the proof process, that is, mastering the origin of theorems and training your reasoning ability. Only in this way can we achieve the goal of learning this science, and at the same time, we can narrow the thinking gap between us and our classmates in the mathematics department.
Probability theory and mathematical statistics are very important, but unfortunately, most colleges and universities will teach less about this course. What is missing now is at least a stochastic process. It is a shame for computer students that they have never heard of Markov process before graduation. How can you analyze networks and distributed systems without stochastic processes? How to design randomization algorithm and protocol? It is said that "Random Mathematics" is a compulsory course in Tsinghua Computer Department. In addition, discrete probability theory is particularly important for computer students. The engineering mathematics in our country is continuous probability. At present, some schools in the United States offer a simple course of "discrete probability theory", which simply deletes continuous probability and talks about discrete probability in depth. We don't have to do this, but we should pay more attention to discrete probability. I think it's best to finish the work as soon as possible.
Computational methodology (also called mathematical analysis in some schools) is the last course given to us by the College of Mathematics and Science. The average student attaches limited importance to this course and thinks it is useless. This is just a formula! In fact, graphics and images can not be separated from it, and cryptography can not be separated from it. Moreover, the application calculation in many scientific projects is mainly numerical. There are two extremes in this course: one is the classic "numerical analysis", which focuses entirely on mathematical principles and algorithms; The other is the increasingly popular "scientific and engineering computing", which simply teaches students to program with software packages. Personally, I think students in the computer department must know why our students in the computer department want to take this course. I am inclined to learn the theory well and then realize it by computer. It is best to use C language or C++ programming. There are still quite a few books working in this direction. Here, I recommend Calculation Method, which was jointly published by CHEP and springer Publishing House and compiled by the Department of Mathematics of Huazhong University of Science and Technology (now Huazhong University of Science and Technology). In this respect, China University of Science and Technology has done a lot of work in China, but personally, this book is the best, at least in programming: evaluation of arbitrary mathematical functions, finding roots of equations. Li Qingyang's book is too theoretical to be closely combined with practical application.
Every school will offer discrete mathematics courses, involving set theory, graph theory, abstract algebra and mathematical logic. However, isn't it a bit too tight to squeeze so much content into a discrete mathematics course? In addition, it is also a huge defect that computer majors don't understand combination and number theory. Want to do theory, don't know combination, don't know number theory, it's too bad. Ideally, it is best to separate the six courses of set, logic, graph theory, combination, algebra and number theory. This is of course unrealistic, because there are not so many class hours. Maybe three courses can be offered in the future: set and logic, graph theory and combination, algebra and number theory. Our school has started to do this. No matter how you attend classes, students always have to learn. Let's talk about the above three groups respectively.
Classic set theory, Beijing Normal University published a book "Basic Set Theory", which is good. Mathematical Logic, The Mathematical Logic of Computer Science written by Professor Lu Zhongwan from Institute of Software, Chinese Academy of Sciences is good. Now you can find the video of Professor Lu Zhongwan's lecture. /html/dir/20065438+0/11/06/3391.htm Go and see for yourself. Generally speaking, learning set/logic is not difficult, and ordinary high school students can understand it. But the later, the more I feel unfathomable. After learning the above books, if you still have the energy and interest to explore further, you can try Introduction to Axiomatic Set Theory and a course of mathematical logic in GTM series. Both books have versions imported from World Book Publishing House. If you can handle these two books, you can really enter the door logically, so you don't have to waste time listening to me.
It is said that at most only thirty people in China know graph theory. This statement is correct. Graph theory is so skillful that almost every problem has its own unique method, which is a headache. But this is its charm: as long as you are creative, it can give you a sense of accomplishment. My tutor said that you can write a paper by grabbing anything in graph theory. You can feel the depth and breadth of the content inside! Among the domestic graph theory books, Graph Theory and Its Algorithms by Wang Shuhe is very successful. On the one hand, its content is very comprehensive in domestic textbooks. On the other hand, its emphasis on algorithms is very suitable for computer department (originally a textbook of HKUST computer department). Based on this book, refer to several translated books, such as Bondy &；; Moore's Graph Theory and Its Application, Graph Theory and Circuit Network translated by People's Posts and Telecommunications Publishing House, etc. It's all so-so, which is enough for undergraduates. In addition, GTM series "Modern Graph Theory" has been introduced into world books. This book is really classic! There seems to be another translation in China. However, to learn this level, it is better to read the original. The completion of this book also marks the entry of graph theory.
In discrete mathematics, we have world-class experts in the Experimental College of Beijing University of Technology. His name is Shao Xuecai. He graduated from Fudan University majoring in probability theory. He has taught advanced mathematics, linear algebra and probability theory. Finally, he turned to discrete mathematics and published countless books. There is a collection of essays in Singapore, which is very classic. If you want to learn the true meaning of discrete mathematics, you might as well look for it. I have specially attended this teacher's class, which is extremely classic. But you have to dig the essence from his casual words. In the conversation with him, I deeply found another problem. Although Mr. Shao has written countless books, according to his own statement, each book is similar. I was really surprised. He said it was mainly because of the limitation of the outline that it was not convenient to write more. No wonder it is rarely heard that writing a book abroad requires an outline (even if there is, the content is much broader), so everyone is the same. This is the beauty of the foreign language version of the book. The latest scientific and technological achievements are discussed. If nothing else, at least "theoretical knowledge keeps pace with the times."
The combination feels that there is no suitable domestic book. Let's read the classic Concrete Mathematics written by Graham and Knut. Xidian university Publishing House has a translated version. Abstract algebra, the domestic classic is Mr. Mo Zongjian's Algebra. This book is a textbook of Peking University Mathematics Department, and it is well received. However, for undergraduates, this book is too profound. You can learn some other textbooks first, and then look back at algebra. There are many international classics, including GTM series. Recommend a book that is not classic, but the easiest to learn: Computer Science (the mathematical basis of computer science), that is, theoretical computer science. It turns out that I once read a translation from the 1970s in the library of Oriental University Town (the cover is gone, but I love to pay attention to this kind of book), which is probably called computer mathematics. That book would have been a good book at that time. Now it seems that the coverage is very wide, but the depth is much worse. However, it is recommended that freshmen have a look, at least to get you started in computational mathematics.
What is the word most often put together with theoretical computer science? A: Discrete mathematics. They are so closely related that they have become synonyms on many occasions. (This is also reflected in previous books) Traditionally, mathematics is centered on analysis. Students in the department of mathematics have to study mathematical analysis for three or four semesters, then complex variable function, real variable function, universal function and so on. Real variables and functionals are considered by many people as the introduction to modern mathematics. The application in physics, chemistry and engineering is mainly based on analysis.
With the emergence of computer science, some previously neglected branches of mathematics suddenly become important. It is found that the mathematical objects handled by these branches are obviously different from the traditional analysis: the solution of analysis and research is continuous, so differentiation and integration become basic operations; But the objects of these branches are discrete, so there are few opportunities for such calculation. People therefore call these branches "discrete mathematics". The name of "discrete mathematics" is getting louder and louder, and finally the traditional branch of mathematics centered on analysis is called "continuous mathematics" relatively.
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. Algorithms are the core of computer science, especially theoretical computer science, 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 to find that algebra has so many applications.
However, is theoretical computer science just as simple as adding a "discrete" hat to mathematics? Until 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 of all: for abstraction. Knuth thinks that the object of traditional mathematics research is too abstract, which leads to insufficient attention to specific problems. He complained that the mathematics he needed often didn't exist in his research, so he had to create some mathematics himself. In order to meet the needs of application directly, 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. Secondly, concrete is continuous and discrete. Both continuous mathematics and discrete mathematics are useful mathematics!
The combination of theory and practice-the category of computer science research
The front is mainly from the mathematical point of view. From the computer point of view, the main research fields of theoretical computer science at present include: computability theory, algorithm design and complexity analysis, cryptography and information security, distributed computing theory, parallel computing theory, network theory, bioinformatics computing, computational geometry, programming language theory and so on. These fields intersect with each other, and new topics are constantly put forward, so it is difficult to sort out a clue. If you want to do this job, I recommend you to read the series of books of China Computer Federation, which at least represents the authority of our country. 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), algebra, information theory, probability theory and stochastic process, and sometimes graph theory and combinatorics are also used. Many people think that cryptography is encryption and decryption, and encryption is scrambling data with a function. This understanding is too simple.
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 common tool to prove the correctness of the protocol?
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.
In the distributed system, there are also many important theoretical problems. For example, synchronization and mutual exclusion protocols between processes. A classic result is that when the communication channel is unreliable, there is no deterministic algorithm to realize the cooperation between processes. Therefore, it is almost meaningless to improve TCP three-way handshake. For example, it is a matter of time. The common order is causal order, but causal order has not had a theoretical result until recently ... for example, there is no practical method to deal with deadlock perfectly. For example, ... If you have learned the operating system, mention it yourself! If the computer only has theory, then it is only a branch of mathematics, not an independent science. In fact, besides theory, computer science has a broader sky.