Copyright statement: This article is the original article for the blogger, without permission may not be reproduced.
A preface to the book "algorithm: the principle behind the data structure"
The winter of the year 2014, a computer science about the father of Alan Turing, the legendary life biographical film released in the United States, the film is the imitation game ". Next year, the film won the 87th session of the Academy Award for best adapted screenplay, and seven nominations including best picture, best director, best actor, best supporting actress, 1:00 scenery unlimited. Although modern computers have become ubiquitous, but due to Turing's era from us too long. Now people are for his research work already know little about.
Speaking of his outstanding contribution, we have to take time to push forward. In 1900, the German mathematician David Hilbert in Paris at the International Congress of mathematicians were entitled "math problem" speech. In this important speech, he put forward the famous Hilbert 23 problems. Despite the subsequent development of mathematics far beyond Hilbert's expectations, but the 23 questions he raised still played a very positive role in promoting the development of mathematics in twentieth Century.
Hilbert's tenth problem is to design an algorithm to test whether there is an integer polynomial polynomial root. Instead of using the term algorithm, he uses the following expression: "a process that can be determined by a finite number of operations". What is interesting is that from Hilbert's statement of the problem can be seen, he explicitly asked to design an algorithm. So it is clear to him that such an algorithm is present, and what people are going to do is just find it. Now we know that this task is not complete, that is, it is an algorithm that can not be solved. But for that period of time, it is not possible to draw such a conclusion to the intuitive understanding of the algorithm.
In a non formal way, the algorithm is a simple instruction set to construct a task. In everyday terms, the algorithm is also called a process or method. Algorithm plays a very important role in mathematics. In the ancient literature, there is a description of the algorithm that performs a variety of computational tasks. For example, ancient mathematics of China classic "nine chapter arithmetic, on account of the including for greatest common divisor and least common multiple, square root, open the cube root, many algorithms. In modern computer science, it is full of all kinds of algorithms. For example, the shortest path to solve the Stella Dick algorithm, string matching KMP algorithm, and so on.
Although the algorithm has a long history in mathematics, but in twentieth Century, the concept of algorithm itself has not been precisely defined. Mathematicians face Hilbert's tenth problems, it is helpless. Due to the lack of precise definition of the algorithm itself, it is impossible to prove that a particular task does not exist. In order to solve the tenth problems of Hilbert, people have to wait for the emergence of the precise definition of the algorithm.
Until 1936, the dawn appeared. The authority of the London Mathematical Journal Turing submitted a paper entitled "on the digital computing application" in the thesis in the decision problem. The paper was finally published in 1937 and immediately aroused widespread attention. In the paper, Turing described a can be assisted mathematics study machine, that came to be known as the "Turing machine" of the abstract system. At the same time, another mathematician Alonzo Chch also independently proposed another set of systems, which is calledLambdaCalculus. The Turing Turing machine to define his algorithm, and the churchLambdaTo define the calculus algorithm, then Turing proved that these two definitions are equivalent. As a result, people between the algorithm for non formal concept and a precise definition established contact, algorithm that intuitive concept equivalent to Turing machine algorithm, this is the so-called Church - turing topic.
The church Turing thesis - defined algorithm is proposed to solve the problem of Hilbert tenth required. And the real solution of the problem will have to until 1970, with outstanding contributions to the church and Turing, Matthias Severus Qi in Davis, Putnam and Robinson et al's work on the basis, the ultimate proof check whether the polynomial with integer root algorithm is not exist.
From Turing began, has the same algorithm of computer science has a close contact between. Of course, the content of the book is not intended to start from the Turing machine. History review, constructs a algorithm formal definition and Hilbert to the problems during the like a rising wind and scudding clouds, more is to illustrate the algorithm in our world is how important.
Whether you are the information technology practitioners, or computer professionals in school students, or engaged in the relevant professional researchers, proficient in a computer language are all important. But is not the master of this one of the rules of grammar can be able to write a beautiful program it? The answer, of course, is negative. Because you need to be at least as important as the other tools at least. Algorithms and language, in fact, is very much like the relationship between "Tao" and "art". To master a language is like learning a skill, it can become a craftsman. But in order to become master from the craftsman, just stay at the level of the operation is clearly not enough, it is more important to realize the road". And the algorithm is no doubt that the "Tao" in the design of computer program".
When it comes to the importance of the algorithm, we have to mention a computer scientist Andrew Apel in 1985 to carry out a research work, which is a classic case of the field of program performance optimization. At that time, aipei'er wrote a program for calculation of interaction between objects in the gravitational field. In a given field, the quality of the object, the initial position and velocity, etc., the program can simulate and simulate the running state of the two objects in the interaction of 10000 celestial bodies. Because the amount of calculation is too large, the initial program to complete the calculation about the need to take a year. After a series of improvements, aipei'er will effectively shorten the process time of a day! In this improvement process, algorithm and data structure optimization for the main proportion.
And another example that happened to me. Once in school, the teacher arranged a programming operation. Used to simulate a guessing game of three chords. A triad refers to from a, B, C, D, e, F, g the seven note optional three consisting of a melody, and every note and three soprano, Alto, bass (respectively, with 1, 2, 3 to represent). Now suppose a composer has a melody in mind, and then a piano player tries to guess the answer. Whenever the player gives a guess, for example, "A1, B2, C3". Then composer will only reply which completely guess tone (i.e., notes and pitch guess) has several, in addition to guess the tone, notes guessed several pitch guessed. Then the player to guess, until completely guess so far. You know, all of the speculation that there may be a total of 1330 kinds of! And we hope that with less number of guess better. Do not know whether the readers of this book have been thinking about what methods to solve this problem. But I finally realize the procedures can be done with an average of 4.2 times can guess the answer. In this process, the design of an algorithm is undoubtedly the best choice.
Speaking of algorithms and have to mention the data structure, the two are complementary and inseparable. On the one hand, the algorithm must use the corresponding data structure can be realized, on the other hand, we define a data structure in fact also has been defined with the relevant operation. The steps in the implementation of these operations are algorithms.
In general, the book around the issue of algorithm and data structure, step by step, and to explain the profound things in a simple introduced ideas of design of modern computer technology commonly used more than 40 classic algorithm (including pattern matching algorithm, sorting algorithm, hash algorithm, the shortest path algorithm, etc.), and trace method, divide and conquer, greedy method and dynamic programming algorithm. The book also systematically explain the list, including one-way linked list, one-way circulation list and double circular linked list, stack, queue, including common queue and priority queue), trees (including the binary tree, Huffman tree, heap, red black tree, AVL tree and dictionary tree), the graph, the set (including disjoint sets, etc.) and dictionary and other commonly used data structures. At the same time, through to twenty two classical problems (including Josephus problem, tower of Hanoi problem, eight queens problem and the knight tour problem) to explain, gradually uncover hidden in the data structure behind the algorithm principle, in a bid to help readers to reinforce the knowledge reserve, activate thinking skills, and eventually breaks the block programming to enhance the ability of many barriers.
The paper come Zhongjue shallow, and must know this to practice. To understand the degree of temper data structure using ability and deepen the thought of the algorithm depends on the programming practice. This book uses C++ as the description language, and provides all the data structure and algorithm to achieve the code, for the reader to learn. These codes are compiled in DEV-C++ 5.11 and VisualStudio 2013 environment based on 4.9.2 TDM-GCC. Supporting code readers can from the http://prog3.com/sbdm/blog/baimafujinji download to get the book. The book errata will also be released in real time on this blog on. At the same time, readers are welcome to discuss the problems and deficiencies in this book.
It must consider a few degrees on the road, a sleepless. Because of limited time and ability, in the book. I sincerely hope all the readers can hardly be avoided, and experts hesitate to criticism.
- top
- One
- step on
- Zero
- Guess you're looking for