2026-08-11 ADA - Introducción al curso

Pregunta central

¿Qué propiedades permiten entender si un algoritmo funciona, si es eficiente y cómo puede diseñarse una solución nueva?

Apuntes rápidos

Un algoritmo es una secuencia finita y bien definida de instrucciones para solucionar un problema; se puede pensar como una receta especificada con precisión.
La algoritmia es un pilar de la computación y tiene aplicaciones en muchas áreas del conocimiento.
El objetivo del curso no es memorizar todos los algoritmos, sino aprender técnicas generales para analizarlos y diseñarlos.
Que un algoritmo produzca la respuesta correcta no garantiza que sea útil: también importa la cantidad de tiempo y memoria que requiere.

Análisis de algoritmos

El análisis busca justificar cuatro propiedades principales:

Propiedad	Pregunta
Terminación de un algoritmo	¿Finaliza para cualquier entrada?
Validez de un algoritmo	¿Calcula la salida correcta para toda entrada?
Complejidad temporal	¿Cuánto tiempo requiere al crecer la entrada?
Complejidad espacial	¿Cuánta memoria de trabajo utiliza?

Estas técnicas deben poder aplicarse a cualquier tipo de algoritmo.

Ejemplo: búsqueda en un arreglo

Busca(A, n, x):
    para c = 1 hasta n:
        si A[c] = x:
            devolver c
    devolver NULL

Termina porque el ciclo ejecuta como máximo $n$ iteraciones.
Es válido porque revisa cada posición: devuelve una posición que contiene $x$ o NULL si $x$ no aparece.
Ejecuta a lo más $d n$ instrucciones para alguna constante entera $d$ ; por ello tiene tiempo lineal, $O (n)$ .
Solo conserva el contador $c$ además de la entrada; usa espacio de trabajo constante, $O (1)$ .

Diseño de algoritmos

No es posible aprender todos los algoritmos, pero sí estudiar paradigmas de diseño reutilizables:

Estas técnicas funcionan como herramientas generales para resolver problemas en distintos ámbitos.

Eficiencia y dificultad

En el curso se usará, a grandes rasgos, tiempo polinomial como criterio de eficiencia. La búsqueda en un arreglo es eficiente porque su tiempo es lineal.

Ruta más corta por búsqueda exhaustiva

El algoritmo presentado enumera secuencias de ciudades, conserva las que forman un camino entre el origen y el destino y elige la de menor longitud. Aunque es correcto, puede examinar más de $n!$ caminos; por ejemplo, $30! \approx 2.65 \times 1 0^{32}$ . El problema sí admite algoritmos eficientes, de modo que la ineficiencia pertenece a ese enfoque concreto y no necesariamente al problema.

Satisfacibilidad de circuitos

El procedimiento exhaustivo prueba hasta $2^{n}$ asignaciones de entrada y acepta cuando alguna hace verdadera la salida del circuito. Para $n = 256$ , el número de asignaciones es aproximadamente $1.16 \times 1 0^{77}$ . No se conoce un algoritmo de tiempo polinomial para este problema; esta dificultad conduce a la pregunta P = NP.

Límites de la computación

Hay problemas para los que no existen soluciones eficientes en el modelo considerado; la presentación menciona ajedrez y Go como ejemplos de enorme dificultad.
Hay problemas que no pueden resolverse algorítmicamente en general, como el problema de la parada.
Ante estas limitaciones puede ser necesario aceptar soluciones aproximadas, parciales o probabilísticas.

Aclaraciones después de clase

Tiempo polinomial. Un algoritmo corre en tiempo polinomial si existen constantes $c > 0$ , $k \geq 0$ y $n_{0}$ tales que, para toda entrada de tamaño $n \geq n_{0}$ ,
$T (n) \leq c n^{k} .$
En notación asintótica, esto equivale a escribir $T (n) = O (n^{k})$ para alguna constante $k$ . La presentación usa este criterio “a grandes rasgos” para distinguir algoritmos eficientes.
Terminación, validez y corrección. La presentación separa las preguntas “¿termina con cualquier entrada?” y “¿calcula la salida correcta para toda entrada?”. En terminología estándar, la corrección parcial garantiza que, si el algoritmo termina, su respuesta es correcta; la corrección total combina corrección parcial y terminación. En las diapositivas del curso, validez se utiliza para la propiedad de producir la salida correcta y se analiza junto con la terminación.
Referencias. La diapositiva 36 identifica como material principal Algorithm Design, de Kleinberg y Tardos, junto con sus diapositivas de Princeton. Los demás títulos ya registrados se conservan como referencias complementarias; la presentación no muestra otro título adicional legible.
Política de uso de IA. La diapositiva 38 la presenta como una política “anti-déficit cognitivo”: el promedio aprobatorio de los exámenes es requisito para aprobar el curso. Esto permite utilizar herramientas de IA, pero impide que sustituyan el dominio individual evaluado en los exámenes.

Conceptos para extraer

Referencias mencionadas

Kleinberg, J. y Tardos, É., Algorithm Design.
Materiales de Kleinberg–Tardos de Princeton.
Cormen, T. H., Leiserson, C. E., Rivest, R. L. y Stein, C., Introduction to Algorithms, 2.ª ed.
Mitzenmacher, M. y Upfal, E., Probability and Computing: Randomization and Probabilistic Techniques in Algorithms and Data Analysis, 2.ª ed.
Presentación introductoria de Análisis y Diseño de Algoritmos 2027-I, diapositivas 1–38.

Resumen después de clase

Un algoritmo debe estudiarse tanto por su corrección como por los recursos que consume. La búsqueda lineal muestra cómo demostrar terminación y validez y cómo calcular complejidad temporal y espacial. Los paradigmas de diseño permiten crear soluciones sin memorizar algoritmos aislados. La comparación entre ruta más corta, satisfacibilidad y problemas no computables muestra que una solución correcta puede ser impráctica o incluso imposible de obtener algorítmicamente en general.

Acciones adicionales

Resolver las dudas pendientes.
Contrastar las referencias y la política de IA con las diapositivas 36 y 38.

PCIC — Notas de clase

Explorador