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 pays limited attention 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. 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. 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 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.
I have always felt that four years of basic computer knowledge is not enough, because it is too wide, and eight years should be almost enough. ......
In this regard, I would like to talk about the "computer foundation" which is generally offered in various schools in our department. Setting up basic computer courses in colleges and universities is a compulsory course requirement for all majors stipulated by the higher education department in China. The main content is to enable students to master the history of computer development and learn to use operating system, word processing, table processing and preliminary network application functions simply. But the goal of teaching this course in computer department must not be consistent with this. The goal of computer science course should be: let students fully understand the development of computer science, clearly grasp the research direction of computer science, and the forefront of development is the position of each course in the whole discipline system. Make clear the learning purpose, learning content and application field of each subject. Enable students to have an overall understanding of the whole subject in the early stage of subject learning, so as to clearly know what to learn in the future and how to learn. The position of computer application basic skills should be put in the second place or even later, because students in this department should have this exploration ability. This is very important. Recommend a book: New Perspectives of Computer Science by Machinery Industry Press. After reading this book, I deeply realize that I am still a beginner in computer science, and I have a thorough understanding of what computer science is.
An excellent student in the first-class computer department should never be just a master programmer, but must be a master programmer first. In college, the first professional course was C language programming. From a certain point of view, quite a few people who read computers live by writing programs. About which should be the first programming language. Personally, the key to which language the last section belongs to is to develop good programming habits. At that time, the teacher told us that it only took one week to learn a new language after laying a good foundation. Now I don't think it will take a week at all, provided that the foundation is laid first. Don't hesitate to learn. By the time you make a choice, others will already know several languages.
Assembly language and microcomputer principle are two particularly annoying courses. No matter how good your mathematical/theoretical foundation is, you can't take advantage of it. The order between these two dishes is also chicken or egg first. No matter which course you study first, it will involve something from another course. Therefore, we can only calm down and think slowly. This is a typical engineering class, which does not need too much cleverness and epiphany, but needs gradual enlightenment. Books about these two courses are not difficult to find in computer bookstores. Compare some of the latest books. Composition Principle recommended Computer Composition and Structure written by Professor Wang Aiying of Tsinghua University. Assembly language Everyone takes 8086/8088 into a door, and then you must learn 80x86 assembly language. It has practical value, is not backward, and has a good structure. Writing an efficient virus, embedding a little assembly in a high-level language and developing at a low level are always inseparable from him. Recommend Tsinghua University Shen Meimei's IBM-PC assembly language programming. Some people say that if you don't want to know the computer architecture and be a computer, there is no need to learn computer principles, assembly languages, interfaces and other courses. Is this reasonable? Obviously unreasonable, these things have to be mastered sooner or later and must be contacted. Moreover, these are the few advantages of computer major compared with other majors. It's important to know this when doing a project. It can't be said that technology is just for technology. People who only know technology can only be a coder at most, and they can never fully understand the design of the whole system. The older the coder is, the lower his value is. There is still a teaching problem about the principle of composition. When I was studying this course, the teacher omitted the working principle of CPU and microprogramming. The reason is that our country's CPU technology is not as good as other countries, and after such a long time, we finally produced a Godson that is 108,000 miles worse than Intel. It is recommended not to learn. I don't think this is a problem for all schools. If so, China can stop computer science in any direction. There are several things that can be done in the United States, such as software, hardware and applications, but nothing else can be done. Then why are we sitting here? The teaching concept needs to be changed.
Nowadays, not only students majoring in computer can't handle analog circuits, but also students majoring in electronics are mostly afraid. If you really want to eat software and hardware at the same time, then I suggest you look at Qiu Guanyuan's "circuit principle" first, and maybe look at analog circuits. Textbook: Kang's Fundamentals of Electronic Technology (Higher Education Press) is still good (used by the Electronic Department of our school). If you are interested, you can also refer to children's books.
Digital circuits are much better than analog circuits. Tsinghua University Shi Yan's book is a good textbook, but unfortunately there is little discussion on integrated circuits. I am very interested. Let's take a look at the design of large digital systems (Beihang's is still used more).
How to teach computer system structure is still controversial internationally. The better textbook that can be found in China is Stallings' Computer Organization and Architecture: Design for Performance (photocopied by Tsinghua).
Ben). The most popular book in the world is Computer Architecture: Aquatic Approach, written by Patterson &; Hennessy.
The operating system can choose one of the two books: Design and Implementation of Operating System Kernel and Modern Operating System. Both of them are classics, the only drawback is that they are not rigorous in theory. However, this field belongs to a hard-core system, and it is understandable to be sloppy in theory. If you want to see the theory, please recommend "Operating System" by Tsinghua University Publishing House, written by Zhang Yaoxue, director of the Higher Education Department, which is our textbook. In addition, I recommend a book "Principles of Windows Operating System" published by Machinery Industry Press. This book was written by Chinese operating system experts after a zero-distance visit to Microsoft for half a year, and it lasted more than a year. Almost all the experts who teach operating systems participated, except Zhang Yaoxue (now director of higher education department) in Tsinghua University. Bill Gates wrote the preface himself. It not only introduces the kernel of the operating system in detail in combination with windows2000, xp and XP, but also talks about some windows programming basics, which is very foreign-published, and some of the above contents can be said that only that book at home and abroad has a detailed introduction to the windows kernel.
If we learn formal language well first, I think we only need to learn four algorithms at the front end of compilation principle: recursive descent, which is the easiest to realize; Best top-down algorithm LL (k); Best bottom-up algorithm LR (k); Simplified SLR of LR( 1) (maybe there is another simplified LALR). The back end is completely engineering, which is naturally another story.
Recommended textbook: Compilation Principles and Practice written by Kenneth C.Louden is Compilation Principles and Practice (translated by Machinery Industry Press).
Learning the database should remind everyone that knowing how to use VFP, VB and PowerBuilder does not mean knowing the database. There are too many people in the world who think they know the database! Database design is both science and art, and database implementation is a typical project. So in a sense, database is the most typical computer course-the combination of science and engineering, mutual penetration. In addition, I recommend that you go through the database technology after studying software engineering, which will be a new feeling. Recommended textbook: Concept of Database System, Abraham silber Schatz, etc. As the completeness of knowledge, I also recommend you to have a look at the translation of Data Warehouse by Machinery Industry Press.
The standard textbook of computer network comes from Tanenbaum's Computer Network (translated by Tsinghua University). There is also the recommendation of Xie Xiren's Computer Network Course (People's Posts and Telecommunications Publishing House), which is clear and the references are authoritative. But the network also belongs to the hard-core system, and reading books alone is not enough. It is recommended to read more RFC. You can download RFC documents by number from IP reading in http://www.ietf.org/rfc.htm.. When you can master the common protocols around 10, few people dare to look down on you. I think it would be better to do the work of network design.
The importance of data structure is self-evident. After learning data structure, your programming ideas will be revolutionized and you will have a clear understanding of how to establish a reasonable and efficient algorithm. I think we should pay attention to the following points for the establishment of the algorithm:
When you encounter an algorithm problem, you should first know whether you have dealt with this problem before. If there is, it will usually be solved smoothly. If not, please consider the following questions:
1. Is the question based on some known and familiar data structure (such as binary tree)? If not, you should design your own data structure.
2. What kind of algorithm does the problem need? (Establish data structure, modify data structure, traverse, find, sort ...)
3. The mathematical essence of the algorithm needed to analyze the problem. Is it recursive? For recursive programming, as long as a reasonable parameter table and the conditions for the end of recursion are designed, it is basically done.
4. Continue to analyze the mathematical essence of the problem. According to your previous programming experience, imagine a possible solution and prove its correctness. If the topic requires time and space for the algorithm, prove that your idea meets its requirements. General time efficiency and space efficiency are difficult to balance. Sometimes it is necessary to save time by establishing auxiliary storage.
After a period of analysis, you have your own ideas to solve this problem. Alternatively, you can simply describe your algorithm in natural language. Continue to verify its correctness, try to find out the mistakes and find out the solutions. If necessary (if you find an insoluble contradiction), overturn your own ideas and start from scratch.
6. After confirming that your idea is feasible, start writing the program. In the process of writing code, consider all kinds of problems as thoroughly as possible. The plan should have a good structure and provide comments in key places.
7. Take an example, and then execute your program on paper with a pen to further verify its correctness. When you encounter a situation that is not in line with your idea, analyze whether the problem is programming or algorithm idea itself.
8. If the program passes the above correctness verification, it will be further optimized or simplified.
9. Write ideas analysis and comments.
The specific algorithm ideas can only be obtained by oneself through their own knowledge and experience, and there is no specific law (otherwise, all programmers can be laid off and the code will be automatically generated by the machine). You should have a rich imagination, that is, when a road is impassable, don't get into trouble, and dare to overthrow your own ideas. I'm just a beginner. I'll tell you some of the above experiences for your reference and discussion.
About artificial intelligence, I think it is also very worthy of our serious study. Although it is not a new discipline, it is definitely a promising discipline. One of the founders of artificial intelligence in China, Professor Tu Xuyan of University of Science and Technology Beijing (this old gentleman is my tutor Dr. Li Xiaojian) defined artificial intelligence in this way: artificial intelligence is a model.