Teoría de la Computación 2018-11-14T10:56:21+00:00

TEORÍA DE LA COMPUTACIÓN

La teoría de la computación se ocupa de determinar qué problemas pueden ser resueltos computacionalmente y con qué eficiencia. La teoría considera distintos modelos de cómputo, como los autómatas finitos (que son los más sencillos), las máquinas de Turing (que son las computadoras usuales de hoy en día) y las computadoras cuánticas (cuyo funcionamiento no es digital). Las lógicas y los lenguajes formales juegan un rol central en la teoría de la computación porque permiten expresar propiedades de los programas y razonar sobre su comportamiento. La teoría de la computación también se encarga de entender el límite entre los problemas computables y los no-computables y, dentro del mundo de lo computable, clasificarlos de acuerdo a su grado de simpleza o dificultad.

En particular, estudiamos lógicas con buen comportamiento computacional, como las lógicas modales, tanto desde el punto de vista de la teoría de modelos como desde el de la teoría de prueba. Analizamos lenguajes eficientes de consultas que permiten razonar sobre distintas estructuras de representación del conocimiento. A un nivel más abstracto, investigamos las propiedades teóricas de los sistemas de reescritura y los modelos de cómputo fuertes, como el cálculo lambda. A la inversa, estudiamos modelos de cómputo débiles, como los autómatas finitos y sus numerosas variantes. Nos ocupamos también de la noción de aleatoriedad en relación a los distintos modelos de cómputo y a los  grados de dificultad de los problemas. Por último, introducimos nociones provenientes de la teoría de funciones computables y de la teoría de la aleatoriedad en el procesamiento cuántico de la información y en algunos modelos computacionales que intentan explicar ciertas características de la cognición humana.

Keywords: Lógicas Modales, Complejidad, Cuántica

Investigadores Consolidados

Abriola, Sergio
Becher, Veronica Andrea
Bendersky, Ariel
Diaz Caro, Alejandro
Figueira, Santiago
Heintz, Joos Ulrich
Rios, Alejandro Norberto

Investigadores en Formación

Barenbaum, Pablo
Bellomo, Guido
Descotte, María Emilia
Viso, Andres Ezequiel

Más información del área.

  • Algoritmos eficientes para (casi) todo_icc

Algoritmos eficientes para (casi) todo

22/abril/2018|0 Comments

En Ciencias de la Computación, una tarea básica es la creación de nuevos métodos denominados “algoritmos”. Pero, ¿de qué hablamos cuando hablamos de  “algoritmos”? Se trata ni más ni menos que una secuencia de instrucciones

Comunicate con el ICC