GUÍA 17-08-26 Teoría de la Computación

NE111 · lunes 17/08/2026 · 16:00-17:15 · Sesión 3

Qué es un algoritmo · Las tres áreas del curso

PUNTO DE PARTIDA: QUÉ ES UN ALGORITMO

Un algoritmo es un conjunto finito de instrucciones no ambiguas que, a partir de una entrada, termina produciendo una salida. Cada palabra de la definición carga peso.

• Finito — el texto del algoritmo se escribe completo; no es una lista infinita de casos.
• No ambiguo — no puede ser una instrucción vaga. «Ordena los datos» no sirve; «compara a[i] con a[i+1] e intercámbialos si a[i] > a[i+1]» sí.
• Termina — un procedimiento que nunca se detiene no resuelve nada. Esta condición reaparecerá en el problema de Halting.

Ojo con una confusión frecuente: el algoritmo es finito, no la entrada. Un algoritmo de cinco líneas debe funcionar para entradas de cualquier tamaño.

TRES ÁREAS PRINCIPALES

1. Autómatas — reconocen patrones. Se les da una cadena y responden si pertenece o no a un lenguaje.

2. Computabilidad — buscan un algoritmo general para un problema, para saber si es computable.

3. Complejidad — cuántos recursos, en tiempo y memoria, se necesitan para resolver un problema.

EL ORDEN EN QUE LAS VAMOS A VER

Este curso no las recorre en ese orden. Empieza por el modelo más potente —la máquina de Turing— y sus límites, sigue con complejidad, y hasta después baja a los modelos restringidos: autómatas, expresiones regulares y gramáticas. Termina en compiladores, que es donde todo se usa junto.

La razón es que así se ve primero el techo y luego los pisos. Cuando lleguemos a los autómatas finitos ya vas a saber exactamente qué les falta respecto a una máquina de Turing.

POR QUÉ IMPORTA

El resultado práctico es saber cuándo dejar de buscar. Si un problema es indecidible, no hay ingeniería que lo salve; si es NP-completo, conviene cambiar a una heurística en vez de perseguir el algoritmo exacto. La teoría ahorra el trabajo de intentar lo imposible.

AUTOEVALUACIÓN

1. ¿Por qué «encuentra el número más grande» no califica como algoritmo sin más contexto?

2. Si un algoritmo es finito, ¿cómo maneja entradas arbitrariamente grandes?

3. ¿Qué diferencia hay entre «no sé resolver este problema» y «este problema no es computable»?