Theoretical Computer

Theoretical computer science is the precise mathematical study of the problems and phenomena of calculation. The focus is not on specific programs, but rather on the basic ideas that allow the solution of computer problems. One of the basic concepts is that of a formal computer model that would be broad enough to be equivalent, in principle, to any real computer, but simpler and not cluttered with details. An important aspect of this concept is problems that can not be solved by computers at all or that require too much time to be solved in practice. Other branches of the field deal with the representation of programming languages ​​and the methodical proof that a program is working properly.

The main aspect of theoretical computing is probably the design of efficient algorithms and data structures. The central point is at the level of information organization techniques that promote fast searches by taking as little space as possible, and at the level of key ideas that are behind the execution of calculations so that they are not only achievable, but they are often instantaneous, even for huge amounts of data. Within this aspect of the theoretical studies, there is a wide range of products and services that are the subject of techniques developed at Canadian universities, including Internet searches, air link schedules, database searches. geographic,

Other aspects of the subject are more abstract. One of the most fundamental conclusions in theoretical computer science is that there are computer problems that no program can solve. Many of these theoretical conclusions date back to the 1930s, ten years before the invention of the electronic computer. There is evidence, for example, that no computer program can inspect another program and determine whether it will stop or not. Several other problems are also intractable, including checking whether a program meets the required specifications.

Although a problem can not be solved in every case, there are tools that can be very useful. For example, the areas of semantics and program accuracy focus on developing methods that can be used to formally prove that a program is working properly.

Even if, in principle, a problem can be solved by a computer, the solution may take too much time to be feasible in practice. For example, suppose there are objects and everyone has a price. We must see if these objects can be divided into two piles so that the total price of each one is the same. If n equals 100 and one billion possible partitions were attempted every second, the entire process would take a much longer time than the age of the universe. The execution of this task is obviously impossible. More generally, this approach would require 2 ntrials. This sum of work is exponential to the number of input data, instead of being a polynomial like nk (for a small constant k). In the 1960s, several researchers, including Jack Edmonds of U. from Waterloo, point out that a program taking polynomial time can be used for problems involving a large amount of input data, whereas a program taking an exponential time can not be. In this case, all the problems to be solved in practice have no known polynomial time algorithm.

In 1971, Stephen Cook of U. from Toronto asks the question: “If we can verify a solution proposed in polynomial time, can we necessarily find a solution in polynomial time? The problem of dividing prices into two piles is a problem of this kind. Each proposed solution is checked easily and quickly, but if n is large enough, there are too many possible solutions for all to be verified. Cook demonstrates that some problems have the following characteristic: if one of these can be solved in polynomial time, then all these easy-check problems can be solved in polynomial time. These NP-complete problems include, for example, the establishment of a schedule of school exams in the smallest possible time slot, without any conflict, determining the shortest path through a group of cities and placing a series of objects of different sizes in a minimum number of containers. Hundreds of similar programming problems occur in practice. Many problems have been studied for years before Cook’s labors, and more than a quarter of a century of hard work has passed since then. It is therefore unlikely that there is a polynomial time algorithm that can solve these problems. Many problems have been studied for years before Cook’s labors, and more than a quarter of a century of hard work has passed since then. It is therefore unlikely that there is a polynomial time algorithm that can solve these problems. Many problems have been studied for years before Cook’s labors, and more than a quarter of a century of hard work has passed since then. It is therefore unlikely that there is a polynomial time algorithm that can solve these problems.

NP-completeness has two particularly interesting and practical consequences. First, even if we do not know an effective algorithm to solve a problem, the question still remains pressing in practice. So, looking for methods that can solve most of these problems or that provide good approximate solutions is a key area of ​​theoretical computing. Another point of view is that of asking what is the advantage of making certain calculations difficult to execute. An important example of this kind of application is cryptography. This application is of growing importance because of the current use of unsafe Internet transmission lines for financial transactions.

The idea of ​​a public-key cryptographic system is to send a message that can not be read unless the user has the decoding key (only the designated recipient knows it) or is able to resolve a problem. computer problem for which there is no known polynomial time algorithm. Many Canadian universities are doing important research in this area. At U. from Toronto and U. In Moncton, the development of a secure protocol, applicable to many basic cryptographic methods, is a topic of primary importance. In Waterloo, research is focused on the development and commercialization of effective and safe systems. It has been demonstrated (before being put into public service,