Glosario

Los términos principales del curso, ordenados por parte.

Demostrar y dividir

Término	English	Definición
Correctitud	correctness	Un algoritmo es correcto si termina y da la respuesta pedida con toda entrada válida.
Invariante de ciclo	loop invariant	Condición que se cumple antes de cada vuelta de un ciclo y que, al salir, da el resultado.
Contraejemplo	counterexample	Una entrada en la que una afirmación falla. Basta uno para refutarla.
Matching estable	stable matching	Asignación de dos grupos con preferencias en la que ningún par preferiría estar junto antes que con lo que le tocó.
Gale-Shapley	Gale-Shapley	Algoritmo de matching estable: un lado propone y el otro se queda con la mejor oferta hasta ahora.
Instancia	instance	Una entrada concreta de un problema.
Prueba de estrés	stress test	Comparar un programa con una solución lenta pero evidente, en miles de entradas pequeñas al azar.
Par inestable	unstable pair	Dos personas que no están juntas y que se prefieren entre sí antes que a su pareja actual.
Aceptación diferida	deferred acceptance	Otro nombre de Gale-Shapley: quien recibe propuestas acepta solo hasta que llegue una mejor.
Tabla de rangos	rank table	Tabla que da en O(1) la posición de cada opción en una lista de preferencias.
Divide y vencerás	divide and conquer	Dividir el problema en partes más pequeñas, resolverlas y combinar los resultados.
Recurrencia	recurrence	Ecuación que da el costo de un algoritmo en función de su costo en entradas más pequeñas.
Árbol de recursión	recursion tree	Dibujo de las llamadas de un algoritmo, para sumar su trabajo por nivel.
Teorema maestro	master theorem	Regla que da la solución de T(n) = a·T(n/b) + f(n) comparando f(n) con n^(log_b a).
Condición de regularidad	regularity condition	En el caso 3 del teorema maestro, exigir a·f(n/b) ≤ d·f(n) con d < 1.
Sustitución	substitution method	Comprobar la solución de una recurrencia por inducción, con la constante explícita.
Inversión	inversion	Par de elementos que está en el orden contrario al esperado.
Quickselect	quickselect	Halla el k-ésimo menor partiendo como quicksort y siguiendo solo por un lado.
Mediana de medianas	median of medians	Elección de pivote que garantiza una partición suficientemente pareja, y selección en tiempo lineal.
Karatsuba	Karatsuba	Multiplicación de números con tres productos en vez de cuatro, en Θ(n^1,585).
Par más cercano	closest pair	Los dos puntos de un conjunto que están a menor distancia.
Franja	strip	Puntos a menos de δ de la línea que divide, los únicos que pueden formar un par mejor que cruce.

Greedy y grafos

Término	English	Definición
Cota inferior	lower bound	Costo mínimo que cualquier algoritmo de un cierto tipo debe pagar en el peor caso.
Árbol de decisiones	decision tree	Modelo de un algoritmo por comparaciones: cada nodo es una comparación y cada hoja, un resultado.
Adversario	adversary	Forma de ver una cota inferior: quien responde las comparaciones para obligar al algoritmo a hacer muchas.
Counting sort	counting sort	Ordena enteros de un rango pequeño contando cuántas veces aparece cada valor, sin comparar elementos.
Greedy	greedy	Técnica que toma en cada paso la mejor opción del momento, sin volver atrás.
Argumento de intercambio	exchange argument	Demostración que transforma una solución óptima en la del greedy, sin empeorarla.
Intervalo semiabierto	half-open interval	[s, f) incluye a s y no a f: una clase que termina a las 10 no se cruza con una que empieza a las 10.
Profundidad	depth	Mayor número de intervalos que contienen un mismo instante. Es el mínimo de aulas necesarias.
Grafo de estados	state graph	Grafo cuyos nodos guardan, además del lugar, lo que el problema necesita recordar.
Árbol de expansión mínima	minimum spanning tree	Conjunto de aristas de costo mínimo que conecta todos los nodos.
Propiedad del corte	cut property	La arista más barata que cruza un corte está en un árbol de expansión mínima.
DAG	directed acyclic graph	Grafo dirigido sin ciclos.
Orden topológico	topological order	Orden de los nodos de un DAG en el que toda arista va de un nodo a otro posterior.
Componente fuertemente conexa	strongly connected component	Grupo máximo de nodos en el que todos pueden llegar a todos.
Plazo	deadline	Instante en que una tarea debería estar terminada.
Retraso	lateness	Lo que una tarea termina después de su plazo; si termina antes, es negativo. El retraso máximo es el mayor de un horario.
Código sin prefijos comunes	prefix-free code	Código en el que ninguna palabra es el inicio de otra.
Árbol binario lleno	full binary tree	Árbol en el que todo nodo interno tiene exactamente dos hijos.
Nodo fijado	settled node	En Dijkstra, nodo cuya distancia ya no cambia.
Borrado perezoso	lazy deletion	Dejar en el heap las entradas viejas y descartarlas cuando salen.
Grafo de estados	state graph	Grafo cuyos nodos llevan, además del lugar, lo que hace falta recordar para decidir. Cada valor de eso forma una capa.
Corte	cut	Partición de los nodos en dos conjuntos no vacíos. Una arista lo cruza si tiene un extremo en cada uno, y lo respeta un conjunto de aristas al que ninguna lo cruza.
Bosque	forest	Grafo sin ciclos: un árbol por cada componente.
Separación	spacing	En una partición, el menor peso entre las aristas con extremos en grupos distintos.
Agrupamiento por enlace simple	single-linkage clustering	Agrupar quitando las aristas más caras de un árbol de expansión mínima.
Tiempos de inicio y de fin	discovery and finish times	Momentos en que DFS empieza y termina cada nodo.
Lema del camino libre	white-path lemma	Si al empezar u hay un camino hasta x por nodos sin visitar, x empieza y termina dentro del intervalo de u.
Arista de árbol, hacia atrás, hacia adelante, de cruce	tree, back, forward, cross edge	Las cuatro clases de arista según el estado de su destino cuando DFS la mira.
Grafo de componentes	component graph	DAG con un nodo por cada componente fuertemente conexa. Una fuente no tiene aristas de entrada, y un sumidero no tiene de salida.
Grafo invertido	reversed graph	El mismo grafo con todas las aristas en sentido contrario.

Programación dinámica

Término	English	Definición
Programación dinámica	dynamic programming	Resolver un problema guardando las respuestas de subproblemas que se repiten.
Subproblema	subproblem	Versión más pequeña del problema, descrita con unos pocos parámetros.
Subestructura óptima	optimal substructure	Una solución óptima se compone de soluciones óptimas de sus subproblemas.
Memoización	memoization	Guardar el resultado de una función recursiva para no volver a calcularlo.
Mochila	knapsack	Elegir objetos con peso y valor que quepan en una capacidad, con el máximo valor total.
Pseudopolinomial	pseudo-polynomial	Costo polinomial en el valor de un número de la entrada, pero exponencial en la cantidad de bits que lo escriben.
Distancia de edición	edit distance	Mínimo de inserciones, borrados y cambios para convertir una cadena en otra.
Subsecuencia común más larga	longest common subsequence	La secuencia más larga que aparece en dos cadenas en el mismo orden, no necesariamente seguida.
Intervalos con pesos	weighted interval scheduling	Elegir intervalos compatibles con la mayor suma de valores.
Subsecuencia	subsequence	Elementos en el mismo orden, no necesariamente contiguos.
Subcadena	substring	Elementos contiguos.
Alineamiento	alignment	Dos secuencias escritas en dos filas, con huecos y sin cambiar el orden.
De arriba hacia abajo, de abajo hacia arriba	top-down, bottom-up	Recursión con memoización, y tabla llenada en orden.
Mochila sin límite de copias	unbounded knapsack	Variante de la mochila en la que cada objeto se puede tomar varias veces.
Bellman-Ford	Bellman-Ford	Caminos mínimos desde un nodo con pesos negativos permitidos, en O(VE).
Ciclo negativo	negative cycle	Ciclo cuyos pesos suman menos que cero. Con él, puede no existir un camino mínimo.
Floyd-Warshall	Floyd-Warshall	Caminos mínimos entre todos los pares, en Θ(V³).
Grafo de subproblemas	subproblem graph	DAG con un nodo por subproblema y una arista por cada dependencia.
Camino más largo	longest path	Camino de mayor peso. Fácil en un DAG; difícil en un grafo general.
Subsecuencia creciente más larga	longest increasing subsequence	La subsecuencia estrictamente creciente de mayor largo.
Cadena de matrices	matrix chain multiplication	Elegir el orden de multiplicar matrices que minimiza las multiplicaciones de números.
Árbol binario de búsqueda óptimo	optimal binary search tree	Árbol con la menor suma de frecuencia × profundidad.
Relajación	relaxation	Mejorar la distancia a un nodo si pasar por otro da un valor menor.
Predecesor	predecessor	Nodo desde el que se mejoró por última vez la distancia a otro.
Vector de distancias	distance vector	Enrutamiento en el que cada router comparte con sus vecinos las distancias que conoce.
Nodo intermedio	intermediate node	Nodo de un camino que no es ni el inicio ni el final.
Arbitraje	arbitrage	Cadena de cambios de moneda que termina con más dinero del inicial.
Máscara de bits	bitmask	Un subconjunto escrito como un entero, con un bit por elemento.
Held-Karp	Held-Karp	Programación dinámica sobre subconjuntos para el viajero, en O(n²·2ⁿ).

Flujo e intratabilidad

Término	English	Definición
Flujo máximo	maximum flow	La mayor cantidad que se puede enviar de una fuente a un sumidero respetando las capacidades.
Corte mínimo	minimum cut	La partición de nodos, con la fuente a un lado y el sumidero al otro, de menor capacidad cruzada.
Red residual	residual network	Red con la capacidad que queda en cada arista y las aristas inversas para deshacer flujo.
Camino de aumento	augmenting path	Camino de la fuente al sumidero en la red residual.
Ford-Fulkerson	Ford-Fulkerson	Empujar flujo por caminos de aumento hasta que no quede ninguno.
Edmonds-Karp	Edmonds-Karp	Ford-Fulkerson con el camino de aumento de menos aristas, en O(VE²).
Valor de un flujo	flow value	Lo que sale de la fuente menos lo que entra en ella.
Conservación	conservation	En cada nodo, salvo la fuente y el sumidero, entra tanto como sale.
Saturada	saturated	Arista cuyo flujo es igual a su capacidad.
Capacidad residual	residual capacity	Cuánto más se puede empujar por un arco de la red residual.
Corte s-t	s-t cut	Partición de los nodos con la fuente en un lado y el sumidero en el otro.
Integralidad	integrality	Con capacidades enteras, existe un flujo máximo entero, y Ford-Fulkerson lo encuentra.
Matching bipartito	bipartite matching	Conjunto de aristas de un grafo de dos lados, sin nodos en común.
Reducción	reduction	Resolver un problema con un algoritmo de otro, transformando la entrada y leyendo la salida.
Caminos disjuntos	disjoint paths	Caminos sin aristas en común, o sin nodos en común salvo los extremos.
Teorema de Menger	Menger’s theorem	La mayor cantidad de caminos disjuntos es igual al menor conjunto que los separa.
Condición de Hall	Hall’s condition	Todos entran si ningún grupo tiene menos lugar del que necesita. Con cupos, el lugar es la suma de cupos.
Eliminación en un campeonato	baseball elimination	Decidir si un equipo ya no puede quedar primero.
Selección de proyectos	project selection	Elegir proyectos con ganancias, costos y prerrequisitos para maximizar el total.
Conjunto cerrado	closed set	Conjunto de proyectos que incluye los prerrequisitos de cada uno.
Problema de decisión	decision problem	Problema cuya respuesta es sí o no.
P	P	Los problemas de decisión que se resuelven en tiempo polinomial.
NP	NP	Los problemas de decisión cuyas respuestas “sí” tienen un certificado verificable en tiempo polinomial.
Certificado	certificate	Dato corto que permite verificar que la respuesta es “sí”.
Reducción polinomial	polynomial-time reduction	Transformación en tiempo polinomial de instancias de A en instancias de B, que conserva la respuesta.
NP-difícil	NP-hard	Al menos tan difícil como todo problema de NP.
NP-completo	NP-complete	Está en NP y es NP-difícil.
SAT	SAT	Decidir si una fórmula booleana, en este curso escrita en CNF, se puede hacer verdadera.
CNF	conjunctive normal form	Fórmula escrita como un Y de cláusulas, cada una un O de literales.
Literal	literal	Una variable o su negación.
Cláusula	clause	Un O de literales.
Solucionador SAT	SAT solver	Programa que decide si una fórmula en CNF se puede satisfacer, y da una asignación si es así.
Principio del palomar	pigeonhole principle	Si hay más palomas que nidos, algún nido tiene al menos dos.
3-SAT, 2-SAT	3-SAT, 2-SAT	SAT con a lo sumo 3 o 2 literales por cláusula. El primero es NP-completo; el segundo se resuelve en tiempo lineal.
Teorema de Cook-Levin	Cook-Levin theorem	SAT es NP-completo.
Gadget	gadget	Pieza de una reducción que representa una variable o una regla del problema original.
Grafo de implicaciones	implication graph	Grafo con un nodo por literal y aristas ¬a → b, ¬b → a por cada cláusula a ∨ b.
Suma de subconjuntos	subset sum	Decidir si algunos números de una lista suman exactamente un objetivo.
Ciclo euleriano, hamiltoniano	Eulerian, Hamiltonian cycle	Ciclo que usa cada arista exactamente una vez; ciclo que pasa por cada nodo exactamente una vez.
Problema de la parada	halting problem	Decidir si un programa termina con una entrada dada. Es indecidible.
Conjunto independiente	independent set	Nodos entre los cuales no hay ninguna arista.
Cobertura de vértices	vertex cover	Nodos que tocan a todas las aristas.
Algoritmo de aproximación	approximation algorithm	Algoritmo rápido cuya respuesta está, con garantía demostrada, a un factor del óptimo.
Matching maximal	maximal matching	Matching al que no se le puede agregar ninguna arista. No es necesariamente el más grande.
Viajero métrico	metric traveling salesman	Viajero con distancias que cumplen la desigualdad triangular.
Desigualdad triangular	triangle inequality	d(a, c) ≤ d(a, b) + d(b, c).
Ramificación y acotamiento	branch and bound	Búsqueda exacta que descarta las ramas cuya cota no puede mejorar la mejor solución conocida.
2-opt	2-opt	Mejora local: quitar dos aristas de un recorrido y reconectarlo, si baja el largo.
Óptimo local	local optimum	Solución que ningún movimiento permitido mejora. No es necesariamente la mejor.
Heurística	heuristic	Método que suele dar buenas respuestas, sin garantía demostrada.
Programación lineal	linear programming	Optimizar una función lineal sujeta a restricciones lineales.
Programación lineal entera	integer linear programming	Programación lineal con variables que deben ser enteras. Es NP-difícil.