Article: Hu Wei Learning (theory) computer
Author: Sir (Ah astringent)
Date: 2001-10
-------------------------------------------------- ------------------------------
*********************************************************** *****************
Copyright Notice: SIR True Aesthetics, Nanjing University Alumni.
For academic or education (non-profit) purposes, reserved this copyright voice
In the case of the Ming, you can freely reprint the electronic version of this article. if you
To reprint this article on traditional media, please work with Nanjing University Little Lily BBS
Netizen SIR on the station.
*********************************************************** *****************
I will also pretend to be a master, talk about a little personal experience of learning a computer. Since I am doing theory, I will focus on the theory.
I remember the big one, just on my undergraduate, the mathematical analysis of the six lessons, the six lessons, the time of operation (at the time of work on the six-day). Some students exclaimed the wrong door: What is the system of this? Yes, you didn't go wrong, this is (at the time) South University computer system. The tradition of the department is cultivating academic research, especially theoretical research. The theoretical study of the computer is that it is mathematics, although it is a non-mainstream mathematics in the eyes of orthodox mathematicians.
Mathematics analysis This stuff, our people who learn computer have a complicated feelings. Love it is that it is the first door, and it is also a mathematics lesson of credits. It has long been a long-term study course - 94 can be selected. Its importance can be seen. Hate it is that it seems to be a rare opportunity, and thinking is very different from these discrete / limited works we often do. The strange phenomenon in the year is: the high school mathematics foundation of the computer system is a number of all-calios (I hope that the classmates who have not charged other systems), the number of teaching hours is second only to the mathematics, but the effect after learning is almost the first countdown. Where is the reason, what is thought-minded?
My personal is: computer class students, the requirements of mathematics are different from mathematics, and they are even greater. The so-called "higher mathematics" of the Number of Number Schools is not unrestricted to delete more difficult theories in mathematical analysis, emphasizing the set formula calculation. For the computer system, the biggest use of mathematical analysis is the theoretical part of being deleted. It is difficult to listen to a little, and the so-called "Engineering Mathematics", the pursuit of the computer system, has completely entered the magic. Remember the formula of a pile of curved scores, can you understand mathematical analysis?
Chinese mathematical analysis, generally believe that the "New Speaking of Mathematical Analysis" is the best. I personally think that the "Mathematical Analysis Tutorial" of the NATM Secondary School is also good, at least a typical southern style, we look at kind. Just a lot of learning. In case, your mathematics is so good. These two books are not enough, then see Phi Golden Corz's "Subcommittees" is good - but I think there is nothing necessary, after all, you don't want to go Mathematics is going.
Jimmydovich's "mathematical analysis problem set" is basically a calculated stuff. If you plan to test what "Engineering Mathematics One" can do it. Otherwise, don't do it.
China's so-called higher algebra, is equal to linear algebra, plus a point of polynomial theory. I thought this is a good side, because you can make students feel that the algebra is a structure, not a bunch of matrices. I used Lin Chengsen and Sheng Songbai two teachers, I felt quite comfortable. I still reserved the textbook until now. This book comprehensively contains the basic primary results of the polynomial and linear algebra, and also provides some useful relatively deep content, such as Sturm sequences, Shermon-Morrison formulas, generalized inverse matrices, and the like. It can be said that as undergraduates can eat this book, they can be masters. Later, it was able to publish in the South University Press, but unfortunately, it was not used in the side of the rail. Good domestic high album materials also have the Tsinghua Computer System, Tsinghua Publishing House published, a lot of bookstores, I will know. Features, there is not much difference with the South University.
But the above two books cannot be said to be perfect. From the viewpoint of abstract algebra, the results in the higher algebra are just some examples of algebraic system properties. Mr. Mo Zongjian's "Mathematics" is a deep discussion. However, Mr. Mo's book is very much very well. As undergraduate, I am afraid that it is difficult to accept, but I will wait until I have matured some readings.
Probability Theory and Mathematical Statistics This class is very important, but unfortunately there are few things.
Less things are random processes. I haven't heard of the Markov process in graduation, which is the shame of the computer system. No random process, how do you analyze networks and distributed systems? How to design a randomized algorithm and agreement? It is said that the Tsinghua Computer Department has "random mathematics" and it is a compulsory course. People can be an engineering school, as a person who has been self-righteous, the "Science Computer Department", I feel embarrassed.
In addition, the discrete probability has special importance to the computer system. Now, the United States has already opened a simple "discrete probability" course, simply delete continuous probability, and put discrete probability. We don't have to do this, but it should be more emphasis on discrete probability.
The calculation method is the last class that is given to us by mathematics. General students have limited extent to this class, thinking is nothing. In fact, doing graphic images can be inseparable from it. Moreover, the application calculation in many scientific projects is dominated by values.
This class has two extreme talks: one is classical "numerical analysis", completely speaking mathematics principles and algorithms; the other is now increasingly popular "scientific and engineering calculations", simply teaching students with software package programming. Several teachers in the South University School have made a good thing, publish an extremely classic textbook translation of the former: German Stoer's "Numerical Analysis]. If you can learn the most lightweight one-third of this book, even if there is no white calculation method! The latter language seems to have not kept the trend in China? However, as long as you have the opportunity to install Matlab on your own computer, you can do itself not to communicate.
In this line, it usually opens a discrete mathematics, including aggregation, chart, and abstract algebra, and then open a digital logic. This arrangement is mainly due to the logical tradition of Nanta: Many of the teachers in the department, Mr. Mr. Mr. Mr. Sun is a logical professional origin (see Mr. Sun ".
However, so many contents are squeezed in a class of discrete mathematics, is it too tight? In addition, the computer system does not understand the combination and number theory, and it is also a huge defect. To do theory, you don't understand the combination or the number of dollars, it is too big.
From the ideal state, it is best to separate six lessons: collection, logic, chart, combination, algebra, number. This is of course not realistic because there is not so many lessons. Perhaps you can open three lessons in the future: collection and logic, chart theory and combination, algebraic and numbers.
Regardless of how the class is open, students will always learn. The above three sets of content is told below. Classical aggregation theory, Beijing Normal University, a "basic set theory" is good. The "Collection Theory Guide" of the Nanta Publishing Zhu Zus (Mu Jia) may have more views, but his book is too powerful, and read it.
Mathematical logic, Mr. Mo's book is naturally a classic. However, we have to admit that this book is long, and it is afraid that it is not enough. Especially the proposition / predicate calculation has a lot of different talks, and more people can greatly open their own horizons. For example, Lu Zhong Wan's "Mathematical Logic for Computer Science" is good. Teacher Zhu also had a book of "Mathematical Logic Tutorial", but it also reads a lot.
Overall, learning the collection / logic starting is not difficult, but the more it feels deeply unspeakable. It is recommended that students who are interested in reading Zhu's "Mathematical Basis introduction" - this book is a little time to have a simple style, talking about the wonderful place, the so-called "Sky, the colorful", it is grateful. After reading, you have a probably understanding of these most fundamental problems in these mathematics / philosophy.
After you have finished learning, if you still have a relaxation, you can try "Introduction to Axiomatic Set Theory" and "A Course of Mathematical Logic" in the GTM family. These two have the introduction of world books. If you can get these two books, you can say that you really get into the door in logic, you don't have to waste time to listen to me. :)
It is said that there is only 30 people in China to understand the picture in China (when the class, Chen Daocheng, when I was in class, Chen Daochao was transferred to the teacher's teacher). This words are inevitable. This picture is East, the skill is too strong, and there is a unique method for almost every question. But this is also its charm: as long as you have creativity, it can give you a sense of accomplishment. So there is nothing to say, do it.
In the domestic chart book, Wang Shuhe teacher's "chart theory and its algorithm" were very successful. On the one hand, its content is very comprehensive in domestic textbooks. On the other hand, its emphasis on the algorithm is very suitable for the computer system (originally the BRIC computer system textbook). With this book, refer to a few translations, such as Bondy & Murty, "Figure" and its application ", post and telecommunications network translation," charts and circuit networks ", etc., as a horse, tiger, is enough.
Further, the world book introduces "Moderngraph THEORY" with the GTM series. This book is indeed a classic! There is also a translated version of the country. However, learning this level or reading the original version. Get this book, also marked the picture to the door, huh, huh. Combination feels not too suitable domestic book. Or read the classic "specific mathematics" of Graham and Knuth, etc., there is a translation version, and the West is out.
Abstract algebra, domestic classic is Mr. Mo Zongjian's "Mathematics". This book is a teaching material of Peking University Mathematics and is deeply praised. However, for undergraduates, this book is too deep. You can learn some other textbooks first, and then look back to see "Mathematics". The international classics can be more, and there is a lot of pile in the GTM series. It is recommended to talk about classics, but the easiest, easier to learn:
http://www.math.miami.edu/~ec/book/
This "Introduction to Linear and Abstract Algebra" is very easy to understand, and combines abstract algebra and linear algebra, it is very ideal for beginners. But please pay attention to the copyright issue, don't violate the law.
In terms of data, there is a classic "primary diameter" in China (Pan's brothers, Peking University). Take a little more, there are more classic (world-class) and more difficult "number guides" (Mr. Hua Lugeng, Science Edition, and Nine Bookstore). Take a basic chapter to get a probably, enough for undergraduates. But this is just the primary aumentation. After graduating from undergraduate, you must learn a number of words, you must read English, such as Bach's "Introduction to Algorithmic Number The". The root of theory computer is in the algorithm. It is indeed very correct to open an algorithm design and analysis to undergraduate students. Way to Western world, there is approximately no three-flow computer system does not use the algorithm as a compulsory.
The algorithm textbook is currently recognized as the "Introduction To Algorithms" waiting in Corman. This is enough for entry, it is already enough to refer to other books. Southern Translation Published this book, Chinese name is "Common Data Structure and Algorithm of Modern Computer". Pie seems to provide Linked for online courses, I don't have to talk nonsense.
Last to the form language and automaton. We have used the Bei post to the textbook, it should be clear. However, there is a little to emphasize: the role of form language and automators is mainly used as a computational model, not to be compiled. In fact, the front end of the compilation is already a dead field, without any Open Problem. If this is, we don't have to go to school in the form of language - what is used in Yacc. Then, in the depth, there is a large limit in conjunctive links, and modern sense is not enough. Therefore, it is recommended to be interested in learning English book ... but in English books, there is not much better, and there seems to be the textbook in this area.
After getting started, the model language defined in the form of the automaton is more interesting with the model defined by the recursive function in the automaton, and can be said to be very interesting. I only know now, what is "the beauty of the palace, the rich" rich "!
Hu Lei learning computer - outside theory
If the computer only has theory, it is just a branch of mathematics, not a separate science. In fact, in addition to theory, computer science has a broader sky. I have been thinking that four years is not enough to learn the basic knowledge of the computer because the face is too wide ... a good student of a first-class computer department will never be just a programming master, but he must first be a programming master.
When I go to college, the first professional class program design, now it is like a computer science introduction? Regardless of the name, in short, people who read the computer are dining by the procedure.
Last year, there has been a debate in the computer version, which is the first program design language. I personally think that in which language belongs to the end, the key is to develop a good program habit. When the teacher said to us, after the foundation, I learned a new language only a week. Now I think it is not a week at all - premise is to put the foundation.
There are two different legal orders in the data structure: a primary algorithm for reducing it, another as a senior programming lesson. Nowadays, the domestic courses seem to be between the two, and a slight view. I personally think that if there is another algorithm class, I am afraid that the next goal is more important.
There are two popular data structures in China: Peking University Red Book (Xu Zhuoqua waiting, high school version) and Tsinghua 's green paper (Yan Weimin waiting, Tsinghua Edition). The difference between the two books is not big. The red book is a little deeper in theory, and of course, the strict algorithm is still far away. The green paper is more acceptable, and it is a good topic set, but I think it will make students write homework with pseudo code, I am afraid it is too good. It is best to debug after the algorithm is Code, in order to exercise programming capabilities.
Compilation predictions and microcomputer principles are two-person lesson. Your mathematics / theoretical foundation is better, and it is not cheap. The order between the two classes is also better than having a chicken or the first egg. No matter which door you will learn, it will involve another class. So, I can only calm down slowly. This is a typical engineering class, there is no need to smart and epidemic, but it takes the step of water drop stone wear. It is not difficult to find in the computer bookstore. Get a few newest, look at it.
The simulation circuit is East East, but now not only the computer system is could not engage in the computer system, but also the electronic student is more scared. If you really want the hardware and software to eat, then I suggest you look at Qiu Guanyuan's "circuit principle", and maybe it will look at the analog circuit in the analog circuit.
Textbook: "Electronic Technology Foundation" of Kang Huang is still nice. Interested, you can also refer to Tong Poetry.
Digital circuits should be much better than the analog circuit.石 's book is also a good textbook, and the regret is that the integrated circuit is less. I am really interested, go to the southeast wireless system to listen to their lessons.
How to teach the computer system structure, it is still arguing internationally. The better textbooks that can be found in China are Stallings' "Computer Organization and Architecture: Designing for Performance". The most popular international is "Computer Architecture: a quantitative approach", by Patterson & Hennessy.
The operating system can use TANENBAUM's "Operating System Design and Implementation" and "Modern Operating System" two books. Both of these are classic, the only disadvantage is theoretical is not strict. However, this area belongs to Hardcore System, so it is also the same as the theoretical manual.
If you first learn the form, you will see the front end of the compilation principle. I only learn four algorithms: the most easily achieved recursive decline; the best auto-down algorithm LL (K); the best bottom up algorithm LR (k); LR (1) simplified SLR (perhaps another simplified LALR?). The backend is completely engineering nature, nature is Another Story.
Recommended Textbook: Aho et al. The famous Dragon Book: "Compilers: Principles, Techniques and Tools". Or APPEL "Modern Compiler Implementation In C".
The first meaning of learning the database is to tell you that it will use VFP to program the database. (This world has thought of too many people who understand the database!) Database design is both scientific and art, and database implementation is a typical project.
So in a sense, the database is the most typical computer class - the combination of science and engineering, penetrates each other.
Recommended textbooks: SilberSchatz, et al., "Database System Concepts".
The standard textbook of the network is still from Tanenbaum: "Computer Networks". However, the network is also Hardcore System, so light reading is not enough. It is recommended to read the RFC multi-read, read from IP. Waiting to master 10 kinds of common agreements, there are no few people who dare to look at you.
This "Hu Wei" must be ended, and then it is not my strength. In fact, there are still many basic courses worthy, such as programming language principles, graphic image processing, artificial intelligence, and more. How can I have limited efforts, I don't dare to make the laughter.
Finally, statement: The two "Hu Wei" before and after only for the study of the undergraduate phase. Even if you get these full, the road is still long ...
Theoretical computer science
I have promised Russel, I have a little time today, and I am on the debt. Computer science and mathematics have a bit strange. Two-30 years ago, computer science basically or a branch of mathematics. Now, computer science has a wide range of research and many researchers, in many ways to promote mathematical development, from a sense to say that children are growing higher than mothers.
But no matter what, this child always flows through the blood of the mother. This blood is the Mathematical Underpinning of Computer Science (Mathematical Basis of Computer Science), and is the theoretical computer science.
Another cross for modern computer science and mathematics is calculating mathematics / numerical analysis / scientific calculations, which are traditionally not included within the theoretical computer science. Therefore, this paper is ignored to the computational mathematics.
What is the word most common and theoretical computer science? A: Discrete mathematics. The relationship between the two is so close, so that they become synonyms in many cases.
Traditionally, mathematics is analyzed centered. The mathematics classmates should learn the mathematical analysis of the three or four semesters, then they are rehabilitated, real transformation, function, and so on. Realism and functional letters are considered to be a modern mathematics. In physics, chemistry, engineering applications, also analyzed.
With the emergence of computer science, some mathematics branches that have not been attached to the past are suddenly important. It has been found that the mathematical objects of these branches have obvious differences from traditional analysis: the object of analysis and research is continuous, and thus differentials, points become basic operations; and the objects of these branches are discrete, and there is little opportunity Perform such calculations. It is thus called these branches to "Discrete Mathematics". The name of "Discrete Mathematics" is getting loud and losing, and finally, the traditional mathematical branch of analysis-centric mathematics is relatively referred to as "continuous mathematics."
After decades of development, discrete mathematics is basically stabilized. It is generally believed that discrete mathematics contain the following disciplines:
1) Collection theory, mathematical logic and metamodology. This is the basis of the entire mathematics, and it is also the foundation of computer science.
2) Figure theory, algorithm chart; combined mathematics, combined algorithm. Computer science, especially the core of theoretical computer science is algorithm, and a large number of algorithms are based on graph and combination.
3) Abstract algebra. The algebra is inexpensive, which is very important in mathematics. In computer science, people surprised that modern numbers have more applications.
However, the theoretical computer science is just that the top of "discrete" hats is simple in mathematics? It has been finally a master that I finally told us that one year ago.
D. E.knuth (he has more great, I don't want to use me nonsense) Opened a new courses in Stanford. Concrete Mathematics. CONCRETE The word has two meanings here:
First, for Abstract. Knuth believes that the object of traditional mathematical research is too abstract, causing not enough attention to specific problems. He complained that the mathematics he needs in research often does not exist, so he can only create some mathematics. In order to directly facilitate application, he should advocate "specific" mathematics.
Here I am doing a simple explanation. For example, in the collection, mathematician care is the most fundamental problem - the various properties of the axiom system. And some of the specific collection of nature, all common collections, relationships, and mapping are what mathematics feel that it is not important. However, in computer science, it is precisely these specific things. Knuth can first see this, it is worthy of the first person of the world.
Second, Concrete is Continuous plus discrete (discrete). Regardless of continuous mathematics or discrete mathematics, it is useful mathematics!
The front is mainly seen from the perspective of mathematics. From a computer perspective, theoretical computer science currently the main research field includes: calculated theory, algorithm design and complexity analysis, cryptography and information security, distributed calculation theory, parallel calculation theory, network theory, biological information calculation, Calculate geometry, program language theory, etc. These areas are crossing each other, and new topics are constantly being put forward, so it is difficult to figure out a clue. Let's give some examples. Due to the promotion of application requirements, cryptography is now a hot spot study. Cryptography is based on numerical (especially calculating numbers), algebra, information theory, probability theory, and random processes, sometimes also used in the chart and composition.
Many people think that cryptography is encrypted and decrypt, and encryption is to disrupted the data with a function. This is a big mistake. Modern cryptography includes at least the following levels:
First, the basis of cryptography. For example, is it really difficult to break down a large number? Can there be a general tool certificate agreement?
Second, the basic topics of cryptography. For example, better one-way functions, signature protocols, etc.
Third, high-level issues of cryptography. For example, the length, secret sharing of zero knowledge certificates.
Fourth, new application of cryptography. For example, digital cash, traitor tracking, etc.
There are also many important theoretical issues in a distributed system. For example, synchronization between processes, mutex protocols. A classic result is: When the communication channel is unreliable, there is no determination algorithm to achieve the same process. Therefore, it is almost meaningful to improve TCP three handshakes. For example, timing problems. A common sequence is due to fruit, but because of the sequence until shortly, there is a theoretical result ...
For example, the deadlock does not have a practical method to deal with it perfectly.
E.g,......
About dead lock Re: Theory computer science is talking about (6)
I simply think is related to "Entropy". It is not so complicated. Key is efficient: dealing with deadlocks, such as deadlock detection, very seriously reduced efficiency, so that you don't have it, because deadlock is not a frequent occurrence. Therefore, in the global, there is generally used the so-called "ostrich algorithm", which is pretending to happen. On topical, for example, you want to design an algorithm to access shared data, then you have to prove that your algorithm is on the partial DEADLOCK FREE. As for it, it will not lead to a global deadlock, I will not be much more annoying.
