| |
VIRTUAL LIBRARY
for Bachelor and Master Degree Students
Course: Computability and Complexity |
| Showing URLs 1 to 1 of 1 |
|
http://www.cs.auc.dk/~luca/FS2/kb2002-text.html
|
| Available in: |
English |
| Anotation: |
The goal of this course is to explain and illustrate one of the most important and fundamental facets of the world of computing --- its inherent limitations. We shall see that there are problems for which no algorithmic solution will ever exist, and realizing the existence of such inherently unsolvable problems has been one of the main achievements of 20th century mathematics. Roughly speaking, the subject matter of the theory of computability is the precise definition of the informal concept of algorithm, and the characterization of those problems that can (or, perhaps more intriguingly, cannot) conceivably be solved by means of algorithms. The last part of the course will be devoted to a brief introduction to the theory of computational complexity. In a nutshell, one may say that, whereas computability theory is concerned with the class of problems that can or cannot be solved algorithmically, complexity theory aims at characterizing the problems for which efficient algorithmic solutions can conceivably be found. The key concept that we shall touch upon in this part of the course is that of NP-complete problem. We shall also touch upon the important topic of space complexity, where we classify the difficulty of solving a computational problem based on a measure of the amount of memory that it takes to compute the solution in the worst case. |
| ECTS credits: |
3 |
| Entered on: |
26 October 2002 |
|
|
|
|
