Máster en tecnología Blockchain y Criptoeconomía

Teoría de la Computación

Calendario

Enero
LMMJV
[1]34567
[2]1011121314
[3]1718192021
[4]2425262728
[5]31    
Febrero
LMMJV
[5] 1234
[6]7891011
[7]1415161718
[8]2122232425
[9]28    
 N  no lectivo,  N  fiesta,  N  estudio,  N  exámenes, N N clase, N clase anulada

Programa

Intro
Qué es la Teoría de la computación. Teoría de la computación y Blockchain.
I - Lenguajes y Autómatas
Autómatas regulares, a pila, acotados linealmente y máquinas de Turing. La jerarquía de Chomsky. Indeterminismo. El Problema de la Parada. La máquina Universal de Turing. Turing completitud.
II - Problemas difíciles (Hard)
Problemas tratables e intratables. Las clases P, NP, NP-Hard y NP-Completa. El problema ¿P=NP?. Problemas de decisión y "reducciones". El problema de la "Satisfacibilidad". Algunas reducciones.
III- Los límites del conocimiento
El método axiomático. La axiomatización del conocimiento, teoría de conjuntos. La paradoja de Russell. El teorema de Gödel. La conjetura de Church-Turing.

Evaluación

Aunque veremos conceptos de Teoría de la Computación de un modo teórico, como lo haremos de un modo muy descriptivo, sin entrar en el formalismo, la evaluación no será nada teórico. En cierto modo será algo totalmente conectado con la Complejidad Algorítmica: estudiar experimentalmente el comportamiento de un par de soluciones propuestas para un problema concreto.

El peso de la nota obtenida, para el cálculo de la nota final en la asignatura, será proporcional a la carga horaria de esta parte (1/3).

Desarrollo

Pdf utilizado en clase

(Sufrirá cambios a lo largo del curso)

ENERO

lunes 31 de enero de 2022

Hemos llegado hasta la página 16

Se ha quedado en el tintero la pregunta "¿Ser finito es condición suficiente para que un lenguaje sea regular?"

FEBRERO

martes 01 de febrero de 2022

Nos hemos quedado justo a punto de practicar con el simulador de máquina de Turing

miércoles 02 de febrero de 2022
  • Comenzamos practicando con la Máquina de Turing (recursos y ejercicios justo aquí abajo)
  • Y siguiendo con el temario nos quedamos a las puertas de comenzar con "Problemas difíciles", pero quedan por ver las tres páginas anteriores.

Prácticas con la Máquina de Turing

Descargar el simulador de Máquina de Turing (Hay algunos ejemplos disponibles -¡ojo! entre ellos está la solución a los ejercicios propuestos aquí abajo- )

1) Construir una Máquina de Turing que entre en un ciclo infinito en caso de encontrarse situada frente a un “0” y termine en caso de encontrarse frente a un “1”.

2) Para un alfabeto binario, construir una Máquina de Turing que duplique la entrada.


Ejercicios propuestos...

1.- Diseñar una Máquina de Turing que desplace hacia la izquierda una posición un patrón binario {0,1} de longitud indeterminada. El resultado deberá ocupar las mismas posiciones en la cinta que el patrón original. En la posición extrema de la derecha se situará un cero. Interpretando el patron binario como un número entero en base 2, esto equivale a un producto por 2. En caso de que el primer elemento sea un uno, no se realizará la operación y se marcará esto sustituyendolo por un símbolo "z"

Ejemplo:

2.-Diseñar una máquina de Turing para restar 1 a un patrón binario {1,0} que representa un número entero.

Ejemplo:

3.- Combinar las dos máquinas anteriores en una que aplique tantos desplazamientos a un patrón binario (según enunciado del problema 1) como indique un entero (que se irá descontando como se indica en el ejercicio 2). La ejecución terminará al realizarse todos los desplazamientos (llegar el contador a cero) o al abortarse un desplazamiento por encontrar un 1 en la primera posición. La situación inicial de los datos será la presentada en el ejemplo (separados por un solo espacio en blanco y con el contador a la izquierda.

Ejemplo:

jueves 03 de febrero de 2022

Hemos visto las tres páginas que nos faltaron ayer, y todo el punto "Problemas difíciles"

viernes 04 de febrero de 2022

Tema 3 - Los límites del conocimiento

Extras

Relativos a cuestiones mensionadas en el curso:

Con "cierta" relación con cuestiones mensionadas en el curso

Del trabajo de Turing pasamos a la inteligencia artificial, la computación y la conciencia,...
Otros temas

"Not So Frequently Asked Questions"
En ocasiones alguna pregunta nada habitual puede ser de interés general....