| |
VIRTUAL LIBRARY
for Bachelor and Master Degree Students
Course: Formal Languages and Computability |
| Showing URLs 1 to 1 of 1 |
|
http://www.cs.auc.dk/~luca/SS-INF/SS04/
|
| Available in: |
English |
| Anotation: |
The goal of this course is to introduce three central areas of the theory of computation that anybody with a serious interest in computers should know about: the theories of automata, computability and complexity. These fundamental scientific areas study the main computational models that underlie the world of computing, their capabilities and their inherent limitations. As you will discover during this semester and in the remainder of your studies, apart from its intrinsic intellectual interest, the theory that we shall cover in this course has important practical applications in, e.g., compiler design, various design methodologies and notations (for instance, the UML notation you have met in passing in your Object-Oriented Analysis and Design course), speech recognition (which is partly addressed in the course Verbal interaktion i multimodal kontekst), text processing, and many facets of program analysis and implementation.
At the end of the course, you will be familiar with the basic computational models of Finite State and Pushdown Automata and with the classes of grammars that generate the languages recognized by these abstract computational devices. We shall also 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. In the process of developing such a theory, we shall touch upon topics such as:
- Models for the description of algorithms (with special emphasis on Turing Machines) and their equivalence,
- Church-Turing's thesis,
- Unsolvable problems.
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.
As an alternative, excellent description of this course I strongly recommend the preface of Computers Ltd.: What They Really Can't Do (Oxford University Press) by David Harel. This lovely little book by one of Computer Science's best expositors is highly recommended reading. (See the review of this book in Plus magazine.) |
| ECTS credits: |
Not Specified |
| Entered on: |
20 September 2004 |
|
|
|
|
