Teoría de la Computación

2025-2026 Q2

Ilario Bonacina
ilario.bonacina@upc.edu

Despacho \Omega-223

10 de febrero de 2026

Esta clase

  • Informaciónes administrativas del curso
  • Introducción a ToC
    • principalmente terminología

Al final de cada clase, cada uno de vosotros dirá o bien un tema que recuerde de esta clase o hará una pregunta.

Info del curso

Importante

Aseguraos de que podéis iniciar sesión en RACSO; si no, enviad un correo a ilario.bonacina@upc.edu
usuario: el mismo que en la FIB
contraseña: DNI sin letra

Recursos Salud UPC

25 de Febrer
Estratègies i tècniques per facilitar la concentració i l’atenció (de 12 a 14h) Inscripcions
11 de Març
Ansietat davant dels exàmens i lliurament treballs (de 12 a 14h)

Es faran a l’aula B4 002.

Introducción

¿Qué es la computación?

La computación es el proceso de evolución de algún entorno, mediante una secuencia de pasos “simples y locales”.
– Avi Wigderson (Math and Computation)

  • cómo evolucionan los bits en un ordenador o en un circuito booleano
  • estados de procesadores en una red, bajo (por ejemplo) comunicación por pares
  • ¡muchos más ejemplos!
    Átomos en la materia, neuronas en el cerebro, proteínas en una célula, células en un tejido, bacterias en una placa de Petri, deducciones en sistemas de prueba, precios en un mercado, individuos en una población, estrellas en galaxias, amigos en Facebook, qubits en estados entrelazados …

Metodología de ToC

Modelado computacional
Descubrir y articular formalmente las operaciones básicas subyacentes, el flujo de información y los recursos de procesos dados.
Eficiencia algorítmica
Intentar minimizar los recursos relevantes usados por los procesos computacionales y estudiar sus compromisos.
Pensamiento asintótico
Estudiar problemas sobre objetos cada vez más grandes, ya que la estructura suele revelarse en el límite.
Clasificación
Organizar tareas computacionales en clases (de complejidad) según la cantidad de diversos recursos que requieren en distintos modelos.

Reducciones
Ignorar tu ignorancia y, incluso si no puedes resolver eficientemente un problema, asumir que puedes hacerlo y explorar qué otros problemas ayudaría a resolver eficientemente.
Completitud
Identificar los problemas más difíciles dentro de una clase de complejidad.
Dureza
Probar resultados de intratabilidad — ¡son útiles!
Barreras
Cuando se está bloqueado durante mucho tiempo en una cuestión importante, abstraer todas las técnicas conocidas usadas hasta el momento e intentar argumentar formalmente que no serán suficientes para su resolución.

¿Qué problemas pueden resolver los ordenadores (eficientemente)?

  • ¿Comprobar si un número es primo?
  • ¿Decidir si una cadena de caracteres es un palíndromo? (por ejemplo oso o radar)
  • ¿Ordenar una lista de números?
  • ¿Encontrar la distancia entre dos nodos en un grafo dado?
  • Dado un código en C++ y una entrada, ¿decidir si la ejecución termina?

Teoría de autómatas
problemas que pueden resolverse con muy poca memoria
Computabilidad
problemas que un ordenador puede resolver (con tiempo/recursos ilimitados)
Complejidad
problemas que pueden resolverse (o no) dependiendo de los recursos

Problemas de decisión

Problemas con respuesta Sí/No

¿Cuáles son problemas de decisión?

  • Dado un número n, ¿es primo?
  • Dados números x,y, calcular x\cdot y.
  • Dada una cadena de caracteres, ¿es palíndromo?
  • Dada una lista de números, ordenarla de forma creciente.

Habéis visto muchos tipos de datos:
enteros, números en coma flotante, vectores, grafos, código de otros programas, …

Todos ellos pueden codificarse como cadenas de caracteres.

Los caracteres que eliges determinan el alfabeto.

  • Código ASCII
  • Código Morse \{. , _\}: ...___...
  • \{0, 1\}: 101
  • \{0, 1, 2 ,3 ,4 ,5 ,6 ,7 , 8 , 9, +, - , ( , )\}: (1+2)-3
  • \{a , b, c\}: aaabbbccc

¡El alfabeto no debe ser vacío ni infinito!

Lenguajes formales

  • Cualquier conjunto finito (no vacío) puede tomarse como un alfabeto. Normalmente los alfabetos se denotan por \Sigma.

  • Concatenaciones finitas de caracteres (o símbolos) de \Sigma son palabras (o cadenas).

  • \Sigma^* = el conjunto de todas las palabras sobre \Sigma

¿Es \Sigma^* finito?

Problemas de decisión (otra vez)

  • ¿Tiene w\in \Sigma^* la propiedad lógica P?

  • ¿Es w\in \{x\in \Sigma^* \mid P(x)\}?

El estudio de los subconjuntos de \Sigma^* es lo mismo que estudiar problemas de decisión.

Un lenguaje sobre \Sigma es cualquier subconjunto de \Sigma^*.

¿Cuántos de los siguientes son lenguajes sobre \Sigma?

\emptyset (el conjunto vacío)
\{\lambda\}
\Sigma^*
\lambda

Ejemplos de lenguajes

  • \Sigma=\{a,b, c, \dots, z\}.
    L= todas las palabras del diccionario de la RAE en español
  • \Sigma=\{0,1\}.
    L=\{w\in \Sigma^* \mid w \text{ es palíndromo}\}
    L=\{w\in \Sigma^* \mid w \text{ representa un número primo en binario}\}
    L=\{w\in \Sigma^* \mid w \text{ representa un grafo 3-coloreable}\}
  • \Sigma= conjunto de todos los caracteres ASCII.
    L= todos los programas válidos en C++

Operaciones sobre palabras

  • \lambda (o \epsilon) = la palabra vacía

  • w=s_1s_2\cdots s_n, u=t_1t_2\cdots t_m
    (donde cada s_j,t_i\in \Sigma)
    pueden ser concatenadas y dan la palabra w\cdot u = wu = s_1s_2\cdots s_n t_1t_2\cdots t_m

  • (exponenciación) w\in \Sigma^* \begin{align*} w^0&=\lambda\\ w^{n+1}&=w^n\cdot w \end{align*}

  • w es una subpalabra de u si \exists x,y\in \Sigma^*, u=xwy

  • La longitud de w=s_1s_2\cdots s_n (donde cada s_i\in \Sigma) es |w|=n.

  • para palabras u,w\in \Sigma^*, |w|_u = número de apariciones de u en w como subpalabra.

  • (reverso) w^R = lo mismo que w pero con los símbolos escritos en orden inverso

Operaciones sobre lenguajes

  • los lenguajes son conjuntos, así que todas las operaciones sobre conjuntos están permitidas: unión \cup, intersección \cap, complemento \overline L
  • (reverso) L^R=\{w\in\Sigma^* \mid w^R\in L\}.

Concatenación

L\cdot M = \{x\cdot y \mid x\in L \land y\in M\}

¿Es la concatenación conmutativa?

¿Cuál es el elemento neutro de la concatenación?

L\cdot \emptyset= ?

Exponenciación y estrella de Kleene

(exponenciación) L^0=\{\lambda\}, L^{n+1}=L^n\cdot L

(estrella de Kleene) L^*=\bigcup_{n\in \mathbb N}L^n

(más de Kleene) L^+=\bigcup_{n\geq 1}L^n

Para comprobar: la estrella de Kleene de \Sigma es el conjunto de todas las palabras sobre \Sigma.
En otras palabras, hemos usado * con dos significados distintos, pero esto está bien.

  • ¿Cuántas palabras de tamaño k pertenecen a \{1\}^* y a \{0,1\}^*?
  • \emptyset^*= ?

Clases de lenguajes

  • los más simples de todos: \emptyset y \Sigma^*
  • \mathbf{FIN} = el conjunto de todos los lenguajes finitos
  • \mathbf{co\text{-}FIN} = el conjunto de todos los lenguajes cuyo complemento es finito
  • \mathbf{REGULAR} = el conjunto más pequeño de lenguajes que contiene \emptyset, \{\lambda\}, \{s\} para todo s\in \Sigma y es cerrado bajo unión, concatenación y estrella de Kleene.

Las próximas semanas nos centraremos en estudiar \mathbf{REGULAR}.

  • \mathbf{FIN}\subseteq \mathbf{REGULAR}. ¿Por qué?
  • \mathbf{co\text{-}FIN}\subseteq \mathbf{REGULAR}. Cierto, pero necesitamos más teoría.

Próximas clases

  • Mañana
  • El próximo martes
    • técnicas de demostración / homomorfismos / diagonalización de Cantor
    • más ejercicios de PS 0

“Homeworks” para la proxima clase

  • Dado L_1,L_2 tales que \emptyset \subsetneq L_1\subseteq L_2\subseteq \Sigma^*, ¿son verdaderas las siguientes dos implicaciones? \forall A,B\in \Sigma^*\quad A\subseteq B \implies AL_1\subseteq BL_2 \tag{1}

\forall A,B\in \Sigma^*\quad AL_1\subseteq B L_2 \implies A\subseteq B \tag{2}

  • ¿Cuáles de las siguientes igualdades son ciertas para todo lenguaje L?
    L^+=L\cdot L^*, \qquad L^*=L^+\cup\{\lambda\}, \quad L^+=L^*\setminus \{\lambda\}, \qquad \{\lambda\}=L^*\setminus L^+

PS 0 – Exercici 2 (Concatenació — propietats bàsiques)

PS 0 – Exercici 3 (Estrella de Kleene — propietats bàsiques)

PS 0 – Exercici 5 (Revessat – propietats bàsiques)

PS 0 – Exercici 8 (Sobre la mida dels llenguatges)