Presentació. Teoria de Llenguatges
Teoria de la Computación
Por qué estudiarla?
The Theory of Computation, since its inception by Turing in 1936, is as revolutionary, fundamental and beautiful as major theories of mathematics, physics, biology, economics… that are regularly hailed as such. Its impact has been similarly staggering. The mysteries still baffling ToC are as challenging as those left open in other fields. And quite uniquely, the theory of computation is central to most other sciences.
(Avi Wigderson)
-
Mathematics and Computation
Avi Wigderson, Princeton University Press, 2019
Chapter 20.2 What is computation?
Chapter 20.3 ToC methodology
Chapter 20.4 The computational complexity lens on the sciences
Principales subramas
- Autómatas
- en este curso
- Computabilidad
- en este curso.
- Complejidad Computacional
- no en este curso, un poco en Advanced Algorithmics (AA) o en cursos de master. Area de investigación muy activa.
Referencias sobre Teoria de Lenguajes
-
Teoria de la Computació - Llenguatges regulars i incontextuals (Catalan)
Rafel Cases, Lluís Màrquez
Capitulo 1 - Llenguatges formals -
Introduction to the Theory of Computation (English)
M. Sipser. Third Edition, Cengage, 2012
Chapter 0 - Introduction -
Automata and Computability (English)
Dexter C. Kozen, Springer, 1997
Lectures 1 – 2