A core problem of computer theory - from the math to talk about:
I remember when the freshman year of school, six hours a week of advanced mathematics, every day homework constantly (at that time it was a six-day work system). Some of the students exclaimed that the wrong door: what in the world are we reading in the Department? Yes, you are not wrong, this is the Department of Computer Science and Technology. China's computer science department tradition is to train people to do academic research, especially theoretical research (the direction does not necessarily have problems, but do not do so satisfactory). Theoretical computer research, after all, such as network security, graphics and imaging, video and audio processing, which direction has a lot to do with mathematics, although perhaps the eyes of orthodox mathematicians non-mainstream mathematics. Here I would also like to clarify my point of view: we all know that mathematics is abstracted from the theory of real life, the reason why people want to abstract the actual theory, the purpose is to abstract the theory to better guide practice, some mathematical research workers like to use some of the existing theoretical knowledge to derive a number of inferences, unaware that one: the problem is not fully considered is likely to be a false inference, and two: his inference in the case of a number of existing theoretical knowledge to derive a number of inferences, and the inference that the problem is not fully considered may be an error. Secondly, his deduction can not be found in real life prototype, can not guide the practice. Strictly speaking, I'm not an idealist, the theory of political class has always been to guide me to learn the scientific and cultural knowledge of the beacon (at least I think the computer science and technology should be in this direction).
In fact, our computer science department to learn math optics advanced mathematics is not enough (typical engineering colleges and universities are generally open to advanced mathematics), we should be like the Department of Mathematics to learn about mathematical analysis (Tsinghua Computer Science Department seems to be open to mathematical analysis), mathematical analysis of this science, we learn computer people have very complex feelings about it. We computer science people have very complicated feelings about it, in that it is a proof-oriented math course, which is extremely helpful for us to develop good analytical skills. My software engineering mentor, Mr. Wang Yihua of the School of Mathematics and Science of the North Polytechnic University has taught us that most of the students of the Department of Mathematics to software companies for software design and analysis, while most of the students of the Department of Computer Science to do programmers, the reason lies in the Department of Mathematics students analytical reasoning, from the point of view of the training to be far above us. The strange phenomenon that year is: computer science students of the high school mathematics foundation in the university's first and second (I hope no offense to other departments of students), the number of hours of teaching is second only to the Department of Mathematics, but after learning the results are not as satisfactory. Is it all because the students do not work hard, I do not see, the wrong direction is not necessarily, the reason why, it is thought-provoking.
My personal opinion is: computer science students, the requirements of math is certainly different from the math department, and the difference with the physical class is even greater. Usually non-mathematical majors of the so-called "advanced mathematics", is only the mathematical analysis of the more difficult theoretical part of the deletion, emphasizing the use of formulas to calculate only. For computer science departments, the most useful part of mathematical analysis is the theoretical part that has been removed. To put it bluntly, for computer science students, the pursuit of the so-called "engineering math" has gone completely astray. Memorize a bunch of surface integral formulas, can you understand the math? Why don't you just look it up and use it? Or why not just use Mathematics or Matalab?
My favorite thing to do in the department is to recommend reference books to students. I'm not sure if you're going to be able to find the right one, but I'm sure you're going to be able to find the right one, and I'm sure you're going to be able to find the right one. In case your math is too good, then go to see Fichkingolz's "calculus tutorial" - but I think it is not necessary, after all, you do not want to transfer to the Department of Mathematics. The "Mathematical Analysis Workbook" by Jimmie Dovic is also basically computational. The name of the book is very famous, but it may not be suitable for us, but still, the important thing is the establishment of mathematical ideas, living in the information society we are looking for efficiency, the calculation of this stuff is better to leave to the computer. However, it seems that now more used is Fudan University's "mathematical analysis" is also a very good textbook.
The so-called higher algebra in China is linear algebra with a bit of polynomial theory. I thought this had a good side, as it allows students to get an earlier sense of algebra as a structure, rather than a bunch of matrices flipped around. Here I have to mention the Nanjing University, Lin Chengsen, Sheng Songbai two teachers edited "Advanced Algebra", feel quite comfortable. This book is quite comprehensive, including the basic elementary results on polynomials and linear algebra, but also provides some useful and deeper content, such as Sturm series, Shermon-Morrison formula, generalized inverse matrices and so on. It can be said that as an undergraduate if you can eat through this book, you can be considered a master. Domestic better higher algebra textbook and Tsinghua computer department with the book, Tsinghua publishing house, bookstore more than one, a look know. From the point of view of abstract algebra, the results in higher algebra are just some examples of the nature of algebraic systems. This is y discussed in Mr. Zongjian Mo's Algebra. However, Mr. Mok's book is so deep that I am afraid it is difficult for undergraduates to accept it, so I might as well wait until I am a bit more mature to read it later.
As discussed above, computer science students learn advanced mathematics: it is more important to know what you know. The purpose of your study should be: the abstract theory and then applied to practice, not only to master the topic of the solution, but also to master the idea of solving the problem, the study of theorems: not a simple application, but to master the process of proving that master the origin of the theorem, to train their own reasoning ability. Only in this way to achieve the purpose of learning this science, but also narrow the gap between us and the students of the Department of Mathematics thinking.
Probability and mathematical statistics is a very important course, but unfortunately, most of the institutions teaching this course will be missing something. Less things now look at least stochastic processes. To graduation has not heard of Markov process, this is the shame of computer science students. How do you analyze networks and distributed systems without random processes? How to design randomized algorithms and protocols? It is said that Tsinghua Computer Science Department has a "stochastic mathematics", has long been a required course. In addition, discrete probability theory is of special importance to computer science students. In our country, engineering math is all about continuous probability. Now, some schools in the United States have opened a simple "discrete probability theory" course, simply delete the continuous probability, discrete probability deeper. We do not have to do this, but we should emphasize that there is no doubt about discrete probability. This is a task that I think is better done sooner rather than later.
Computational Methodology (also known as Mathematical Analysis in some schools) is the last class given to us by the School of Mathematical Sciences. The average student pays limited attention to this course, thinking that it is not useful. It is just a set of formulas! In fact, it is indispensable to do graphic images, and it is also indispensable to deepen cryptography. Moreover, in many applications of scientific engineering calculations, are mainly numerical. This course has two extremes: one is the classical "numerical analysis", completely mathematical principles and algorithms; the other is now increasingly popular "scientific and engineering computing", simply teach students to use software packages programming. Personally, I think that computer science students must realize why our computer science students have to learn this course, I am very inclined to learn the theory and then use the computer to achieve, preferably using C language or C++ programming to achieve. To this direction is still quite a lot of books, here we recommend Higher Education Press (CHEP) and Springer Publishing House (Springer) jointly published "Computational Methods (Computational Methods)", written by the Department of Mathematics of Huazhong University of Science and Technology (now the Huazhong University of Science and Technology), this aspect of the Huazhong University of Science and Technology to do the work in the country should be considered more, and the Personally, I think this book is the best, at least in terms of programming involves: the value of any mathematical function, equation rooting, linear equations, interpolation methods, numerical integration, field differential equations numerical solution. Li Qingyang's book is too theoretical and not too tightly integrated with practical applications.
Every school has a discrete math course in their department that involves set theory, graph theory, and abstract algebra, mathematical logic. However, is it a bit too tight to squeeze so much into one discrete math course? Also, the fact that computer science students don't know combinatorics or number theory is a huge drawback. To do theory, not knowing combinatorics or number theory can be too big of a disadvantage. Ideally, it would be better to have six separate courses: sets, logic, graph theory, combinatorics, algebra, and number theory. This is of course unrealistic, because there are not that many hours. Maybe in the future we could have three courses: sets and logic, graph theory and combinatorics, and algebra and number theory. (We have already begun to do this in our school.) No matter how the classes are organized, the students will have to learn them all the same. Here is a discussion of each of the three groups above.
Classical set theory, the North Normal University issued a book "basic set theory" is good. Mathematical logic, the Chinese Academy of Sciences Software Professor Lu Zhongwan's "computer science-oriented mathematical logic" is good. Now you can find the video of Prof. Lu Zhongwan's lecture, /html/Dir/2001/11/06/3391.htm to see for yourself. In general, learning set/logic is not difficult to start, the average high school student can understand. But the further you go, the more you feel that it is unfathomable.
After learning the above books, if you still have the energy and interest to explore further, then you can try the GTM series of Introduction to Axiomatic Set Theory and A Course of Mathematical Logic. Both of these are available in introductory editions from World Book Publishing. If you can handle these two books, you can be said to have really started in logic, and you don't have to waste your time listening to my nonsense.
It is said that there are at most thirty people in China who understand graph theory. I'm not sure if this is the case, but I'm sure it is. The first thing I'd like to say is that I don't know how to do this, but I'd like to say that I'm not sure how to do it. However, this is also its charm: as long as you are creative, it can give you a sense of achievement. My tutor said that you could write a paper on any piece of graph theory. You can appreciate the depth and breadth of the content! Among the domestic graph theory books, Mr. Wang Shuho's "graph theory and its algorithms" is very successful. On the one hand, its content is very comprehensive in the domestic textbooks. On the other hand, its emphasis on algorithms is very suitable for the Department of Computer Science (originally is the Department of Computer Science textbook). With this book as the main reference, and then refer to a few translations, such as Bondy & Murty's "Graph Theory and its Applications", the People's Posts and Telecommunications Publishing House translation of the "Graph Theory and Circuit Networks", etc., on the sloppy enough for undergraduates. Further, World Book has introduced "Modern Graph Theory" in the GTM series. This book is really a classic! It seems that there is also a domestic publication of a translated version. However, at this level, it is better to read the original version. The book, also marks the graph theory into the door.
Discrete mathematics, we have a world-class expert in the Beijing Institute of Technology Experimental College, called Shao Xuecai, Fudan University, graduated in probability theory, taught higher mathematics, linear algebra, probability theory, and finally turned to discrete mathematics, published numerous works, thesis collection of Singapore has a book, can be called a classic, we would like to learn the true meaning of discrete mathematics may wish to find to look. This teacher's class I specifically went to listen to, extremely classic. But you have to dig out the essence from his unconscious words. In the conversation with him, I y found a problem, although Mr. Shao wrote countless books, but according to his own account of each book are almost the same, I am really surprised, he said that the main outline of the limitations of the inconvenience of writing more. This is no wonder, rarely heard of foreign books to write a book based on what the outline (even if there is, the content is also much broader), do not dare to cross the minefield half a step, so it is not to see who are the same. The foreign version of the book is good here, the latest scientific and technological achievements are discussed inside, not to mention the other first, at least "keep up with the times of theoretical knowledge".
The portfolio doesn't feel like there's a domestic book that's too good for it. Still read Graham and Knuth et al. co-authored the classic "concrete math", Xi'an University of Electronic Science and Technology Press has a translated version. Abstract algebra, the domestic classics for Mr. Mo Zongjian's "algebra". This book is the textbook of the Department of Mathematics of Peking University, and it is highly praised. However, for undergraduates, this book is too deep. You can study some other textbooks first, and then come back to "Algebra". There are many international classics, including the GTM series. Recommended a talk about the classics, but the most simple
simple, the most easy to learn: computer science (mathematical foundations of computer science), that is, theoretical computer science. I used to read a translation of the book in the 1970s (the book cover is gone, but I love to pay attention to this kind of book) in the library of the University of the East, which was probably called "Computer Mathematics". It was a good book at the time, but now it seems to cover a wide range of topics, and the depth is much less, but it is recommended for freshmen to take a look at it, so you can at least get started in computational math.
What is the term most often associated with theoretical computer science? A: Discrete mathematics. The two are so closely related that they have become synonymous on quite a few occasions. (This is also reflected in that earlier book.) Traditionally, mathematics has been centered on analysis. Mathematics students take three or four semesters of mathematical analysis, followed by functions of a complex variable, functions of a real variable, generalized functions, and so on. Real variables and generalized functions are considered by many to be the introduction to modern mathematics. Those applied in physics, chemistry, and engineering are also predominantly analytic.
With the advent of computer science, some branches of mathematics that had previously received less attention suddenly became important. It was discovered that these branches dealt with mathematical objects that were distinctly different from traditional analysis: the solutions to the problems studied in analysis were continuous, and thus differentiation and integration became the basic operations; whereas the objects studied in these branches were discrete, and thus there was little opportunity for such calculations to be performed. These branches are thus called "discrete mathematics". The name "discrete mathematics" became more and more popular, eventually leading to the traditional branch of mathematics centered on analysis being called "continuous mathematics" in contrast.
Discrete mathematics has largely stabilized over the decades. It is generally recognized that discrete mathematics encompasses the following disciplines:
1) Set theory, mathematical logic and metamathematics. This is the foundation of the whole of mathematics, and also the foundation of computer science.
2) Graph theory, algorithmic graph theory; combinatorial mathematics, combinatorial algorithms. The core of computer science, especially theoretical computer science, is
algorithms, and a large number of algorithms are built on the basis of graphs and combinations.
3) Abstract algebra. Algebra is ubiquitous and was already very important in math. In computer science, one is surprised to find so many applications for algebra.
But is theoretical computer science just math with a "discrete" label on top? It wasn't until about a decade ago that one of the greats finally told us: no. D.E. Knuth (I don't think I need to tell you how great he was) started a brand new course at Stanford, Concrete Mathematics. The word "concrete" in this context has two meanings:
First, it means "abstract". ...Knuth argued that the objects of traditional mathematical research were too abstract, leading to insufficient concern for the concrete. He complained that the math he needed in his research often did not exist, so he had to create some of it himself. In order to be directly oriented to the needs of applications, he wanted to promote "concrete" mathematics. Let me explain this briefly. For example, in set theory, mathematicians are concerned with the most fundamental problems - the various properties of axiomatic systems and so on. The properties of specific sets, what the common sets, relations, mappings are like, are not important to mathematicians. However, it is precisely these concrete things that are used in computer science, and Knuth was able to see this first, deserving to be the first computer man in the world. Second, Concrete is Continuous plus discrete. Whether continuous or discrete math, it is useful math!
Integration of theory and practice - the scope of computer science research
The previous is mainly from a mathematical point of view. From the computer point of view, theoretical computer science is currently the main research areas 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 being proposed, so it is very difficult to make sense of them. If you want to do some work in this area, we recommend reading a series of books by the Chinese Computer Society, which at least represent the authority in China. Here are some examples.
Cryptography is now a research hotspot, driven by application needs. Cryptography is based on number theory (especially computational number theory), algebra, information theory, probability theory and stochastic processes, and sometimes graph theory and combinatorics. Many people think that cryptography is all about encryption and decryption, and that encryption is all about using a function to scramble data. Such an understanding is too shallow.
Modern cryptography consists of at least the following levels:
First, the foundations of cryptography. For example, is it really hard to decompose a large number? Can there be general tools to prove that the protocol is correct?
Second, fundamental topics in cryptography. For example, better one-way functions than before, signature protocols, and so on.
Third, advanced topics in cryptography. For example, length of zero-knowledge proofs, methods for secret sharing.
Fourth, new applications of cryptography. For example, digital cash, traitor tracking, and so on.
There are also many important theoretical issues in distributed systems. For example, synchronization between processes, mutual exclusion protocols. A classical result is that no deterministic algorithm can achieve inter-process synergy when the communication channel is unreliable. Therefore, it is almost meaningless to improve TCP three times handshake. An example is the problem of timing order. A common type of ordering is causal ordering, but causal ordering didn't have a theoretical result until a while ago .... For example, deadlocks have no practical way to deal with them perfectly. For example,...... Operating systems are studied to cite themselves!
If computers were only theoretical, then they would be nothing more than a branch of mathematics, without becoming a separate science. In fact, there is a wider sky for computer science beyond theory.
I've always thought that 4 years is simply not enough to learn the basics of computing, because the surface is so broad ......
In this regard I would like to start with Computer Fundamentals, which is commonly offered in our department in all schools. In schools of higher learning to open the "basic computer courses" is China's Department of Higher Education expressly mandatory course requirements for all majors. The main content is to enable students to initially grasp the history of the development of computers, learn the simple use of operating systems, word processing, form processing functions and preliminary network applications. However, the goal of teaching this course in the Department of Computer Science must not be the same. In the Department of Computer Science courses should be: to enable students to more comprehensive understanding of the development of computer science, a clear grasp of the direction of research in computer science, the development of the forefront of each course that is the status of the entire system of disciplines. Figure out the purpose of each discipline, learning content, application areas. So that students in the early stages of learning in the discipline has a holistic understanding of the entire discipline, in order to do in the future learning clearly what to learn, how to learn. The position of basic computer application skills should be placed second or further back, because this point for the department's students should have the ability to figure out. This is important. Recommended to you a book: Mechanical Industry Press, "Computer Culture" (New Perspective of Computer Science), read this book I just y realize that I am still a computer science beginner, only a more thorough understanding of what is computer science. In addition, in Xiamen University, Mr. Zhao Zhi Zhuo's book "Introduction to Computational Science", many of the classical theories are very difficult to find in similar books. If you look at him, you may understand one of the most basic questions: why computer science is more accurately called computational science. This book is one of the best in the world.
A top computer science student should never be just a programmer, but he must be a programmer first. When I went to college, the first professional course is the C language programming, reading computer people from a certain point of view, a considerable part of the people are to write programs to eat. In the computer department of the Experimental College of Beijing Institute of Technology, there has been such a debate (and to this day there is one on CSDN) about which programming language should be used as the first one. I personally believe that which language to use belongs to the end, the key is to develop good programming habits. Back then, my teacher told us that it only takes a week to learn a new language after laying a good foundation. Now I think it doesn't take a week at all, provided that the foundation is built first. Don't hesitate to learn it. When you make a good choice, someone else will already know a few languages.
Assembly language and microcomputer principles are two very annoying classes. Your math/theory foundation is good, but you won't be able to take advantage of it. The order between these two courses is also like the chicken or the egg first, no matter which one you learn first, it will involve the other course. So it's just a matter of sitting down and figuring it out. This is a typical engineering class that doesn't require much cleverness or epiphany, but requires the gradual realization that water drips over a stone. It is not difficult to find books about these two courses in computer bookstores. Get a couple of the latest ones and read them against each other. The principle of composition is recommended "Computer Composition and Architecture" written by Prof. Wang Aiying of Tsinghua University. Assembly language everyone take 8086/8088 into a door, after that must learn 80x86 assembly language. Practical value, not backward, the structure is good, write efficient viruses, high-level language embedded in a little assembly, the bottom of the development, always can not be separated from him, recommended Tsinghua University Shen Meiming's "IBM-PC assembly language programming. Some people say that they do not want to understand the computer architecture, and do not want to manufacture computers, so such as computer principles, assembly language, interfaces and other classes do not feel the need to learn, so reasonable? Obviously unreasonable, these things sooner or later have to master, certainly have to contact, and, this is a computer science major and other majors compared to the few advantages of the students. Doing projects, understanding these is very important, it is impossible to say, just for the technology and technology, only understand the technology of the people at most do a coding workers, and never fully understand the design of the entire system, and coding workers is the older the less valuable. On the principle of composition there is a teaching problem, in my study of this course when the teacher taught the CPU principle of work reputation microprogramming this piece of omitted, the reason is that our country engaged in the CPU technology is not as good as other countries, engaged in such a long time it is not easy to come out of a dragon core than Intel's is still worse than a hundred thousand eighty-thousand miles, so it is recommended that we do not learn. I do not see this in the schools is not a problem! If it is really as he said, that China's computer science which direction can be stopped, hardware and software, applications, there are a few to get over the United States, but not others do not engage in, then what are we sitting here? The concept of teaching needs to be changed.
Analog circuits, this thing, now not only computer students can not handle, electronics students are mostly afraid. If you really want to eat hardware and software, then it is recommended that you take a look at Qiu Guanyuan's "Principles of Circuits", and perhaps then look at the analog circuits will have more confidence. Textbook: Kang Huaguang's "Fundamentals of Electronic Technology" (Higher Education Press) is still good (my school electronics department is using). Interested can also refer to the book of Tong Shibai.
Digital circuits are much better than analog circuits. Recommended to take a look at our NIT Professor Liu Yingxian wrote "digital logic" performance people say that this book is very valuable reference (Mechanical Industry Press). The reason is very clear, high practical value, can listen to her courses is to have a kind of "enjoy science" feeling. Tsinghua University Yan Shi's book is also considered a good textbook, unfortunately, the integrated circuit to speak less. Really interested, take a look at the design of large-scale digital systems (Beihang that book is still used more).
How to teach computer system architecture is still debated internationally. Domestic can find a better textbook for Stallings "Computer Organization and Architectureesigning for Performance" (Tsinghua photocopy
this). The most popular one is "Computer architecture: aquantitative approach", by Patterson & Hennessy.
The operating system can be chosen from one of the two books, "Kernel Design and Implementation of Operating Systems" and "Modern Operating Systems". Both can be considered classics, with the only drawback being a lack of theoretical rigor. However, this field belongs to the Hardcore System, so a little sloppy in the theory is also excusable. Want to see the theoretical aspects of the recommended Tsinghua University Press, "Operating System" it, the Director of the Department of Higher Education, Mr. Zhang Yaoxue wrote, our textbook with that book. In addition to recommending a "Windows Operating System Principles" Mechanical Press, this book is our operating system experts in Microsoft zero distance investigation half a year, writing lasted more than a year to write, teaching operating system experts in addition to Tsinghua University's Zhang Yaoxue (now Director of the Department of Higher Education), almost everyone participated in the Bill Gates personally wrote the preface. Bill Gates himself wrote the preface. It not only combines windows2000,xp detailing the kernel of the operating system, and the back of some of the windows programming fundamentals, there is the flavor of the book, and some of the content above can be said to be at home and abroad, only that book to have the windows kernel detailed introduction,
If you first learn the formal language, then the principle of compilation of the front-end as long as I see the The front end of the compilation principle I see only four algorithms to learn: the easiest to implement recursive descent; the best top-down algorithm, LL(k); the best bottom-up algorithm, LR(k); and a simplified SLR (and maybe another simplified LALR) for LR(1). The back-end belongs entirely to the nature of the project, and naturally, it is another story.
Recommended textbook: Kenneth C. Louden wrote "Compiler Construction Principles and Practice" that is, "Compilation Principles and Practice" (Mechanical Press translation)
Learning database to remind everyone is, will use VFP, VB, Power builder does not equal to understand the database. (There are too many people in the world who think they know about databases!) Database design is both science and art, database implementation is typically engineering. So in a sense, the database is the most typical of a computer course - the combination of science and technology, mutual penetration. In addition, we recommend that you learn software engineering and then turn over to look at the database technology, and will be a new feeling. Recommended textbook: Abraham Silberschatz et al. "Database System Concepts". As the completeness of knowledge, but also recommended to take a look at the Mechanical Industry Press "Data Warehouse" translation.
The standard textbook for computer networks is still from Tanenbaum's "Computer Networks" (Tsinghua University has a translation). There is also the recommended Xie Xiren's "Computer Networks Tutorial" (People's Posts and Telecommunications Publishing House) issues are more clearly stated, and the references are more authoritative. However, the network also belongs to the Hardcore System, so just read the book is not enough. It is recommended to read more RFC, http://www.ietf.org/rfc.htm里可以按编号下载RFC文档. Read from the IP's. Wait until you can master about 10 kinds of common protocols, there are not many people dare to underestimate you. Then do the work I see on the network design is better.