Glosario

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

De C a C++ y costos

Término	English	Definición
Referencia	reference	Otro nombre para un objeto que ya existe. No puede ser nula ni cambiar de objeto.
Clase	class	Tipo con datos privados y métodos que los usan.
Método `const`	const method	Método que promete no modificar el objeto.
Destructor	destructor	Método que corre cuando un objeto deja de existir.
Owner, ownership	owner, ownership	El owner de un recurso es quien debe liberarlo, y el ownership es esa responsabilidad.
RAII	RAII	Adquirir un recurso en el constructor y liberarlo en el destructor.
Constructor de copia	copy constructor	Crea un objeto nuevo como copia independiente de otro.
Copia superficial	shallow copy	Copia que duplica un puntero, pero no aquello a lo que apunta.
Mover	move	Pasar los recursos de un objeto a otro sin copiarlos.
Regla de cinco	rule of five	Si una clase define destructor, copia o movimiento, normalmente debe definir los cinco.
Template	template	Código que el compilador genera para cada tipo con que se usa.
Tipo abstracto de datos	abstract data type	Las operaciones de un tipo y lo que prometen, sin decir cómo se implementan.
Invariante	invariant	Condición que siempre se cumple entre dos operaciones de una estructura.
Análisis asintótico	asymptotic analysis	Describir cómo crece el costo de un programa cuando la entrada crece.
O, Ω, Θ	big O, big Omega, big Theta	Cota superior, cota inferior y crecimiento exacto de una función, salvo constantes.
Peor caso	worst case	La entrada de un tamaño dado que más cuesta.
Experimento de duplicar	doubling experiment	Medir con n y 2n, y usar la razón de los tiempos para estimar el crecimiento.

Secuencias y ordenamiento

Término	English	Definición
Arreglo dinámico	dynamic array	Arreglo que cambia de capacidad al llenarse.
Capacidad	capacity	Cuántos elementos caben antes de tener que crecer.
Costo amortizado	amortized cost	Costo promedio por operación en el peor caso de una serie de operaciones.
Pila	stack	Tipo abstracto donde el último en entrar es el primero en salir.
Cola	queue	Tipo abstracto donde el primero en entrar es el primero en salir.
Deque	deque	Tipo abstracto que inserta y saca por los dos extremos.
Buffer circular	circular buffer	Arreglo cuyos índices dan la vuelta al llegar al final.
Lista enlazada	linked list	Secuencia de nodos unidos por punteros.
Nodo centinela	sentinel node	Nodo sin dato que evita casos especiales en una lista.
Iterador	iterator	Objeto que señala un elemento de un contenedor y avanza al siguiente.
Mergesort	mergesort	Ordena dividiendo en dos, ordenando cada parte y mezclándolas.
Quicksort	quicksort	Ordena separando los elementos alrededor de un pivote.
Pivote	pivot	Elemento con el que quicksort separa los menores de los mayores.
Ordenamiento estable	stable sort	Conserva el orden original de los elementos iguales.
Búsqueda binaria	binary search	Busca en un arreglo ordenado, descartando la mitad en cada paso.

Diccionarios

Término	English	Definición
Diccionario	dictionary, map	Tipo abstracto que guarda y busca valores por su clave.
Tabla hash	hash table	Diccionario que usa una función hash para ubicar cada clave en un arreglo.
Función hash	hash function	Convierte una clave en un número, siempre el mismo para claves iguales.
Colisión	collision	Dos claves distintas que caen en la misma casilla.
Factor de carga	load factor	Elementos guardados entre número de casillas.
Encadenamiento	chaining	Cada casilla guarda una lista con sus claves.
Direccionamiento abierto	open addressing	Las claves se guardan en el mismo arreglo, buscando otra casilla al chocar.
Probing	probing	Probar casillas, en cierto orden, hasta dar con la clave o con una vacía.
Linear probing	linear probing	Direccionamiento abierto que prueba la casilla siguiente.
Tombstone	tombstone	Marca de una casilla borrada, para no cortar las búsquedas.
Swiss Table	Swiss Table	Tabla con direccionamiento abierto y un byte de metadatos por casilla, que se compara por grupos.
Árbol binario de búsqueda	binary search tree	Árbol donde, en cada nodo, las claves menores van a la izquierda y las mayores a la derecha.
Altura	height	Cantidad de aristas en el camino más largo de la raíz a una hoja.
Recorrido en orden	in-order traversal	Visita el subárbol izquierdo, el nodo y el subárbol derecho.
Sucesor	successor	La menor clave mayor que una clave dada.
Rotación	rotation	Cambio local de forma de un árbol que conserva el orden de sus claves.
Árbol AVL	AVL tree	Árbol de búsqueda donde las alturas de los dos subárboles de cada nodo difieren en 1 como máximo.
Árbol 2-3-4	2-3-4 tree	Árbol de búsqueda con nodos de 2 a 4 hijos, y todas las hojas a la misma profundidad.
Árbol rojinegro	red-black tree	Árbol binario de búsqueda con nodos pintados, que representa un árbol 2-3-4.
B-tree	B-tree	Árbol balanceado con nodos de muchas claves, pensado para disco.

Prioridades y grafos

Término	English	Definición
Cola de prioridad	priority queue	Tipo abstracto que inserta y saca el elemento de mayor prioridad.
Heap binario	binary heap	Árbol completo guardado en un arreglo, donde cada padre es menor o igual que sus hijos.
Heapsort	heapsort	Ordena usando un heap, en el mismo arreglo.
Código de Huffman	Huffman code	Código sin prefijos comunes, con palabras más cortas para los símbolos más frecuentes.
Grafo	graph	Conjunto de nodos unidos por aristas.
Lista de adyacencia	adjacency list	Por cada nodo, la lista de sus vecinos.
Matriz de adyacencia	adjacency matrix	Tabla de n × n que dice si hay arista entre cada par de nodos.
BFS	breadth-first search	Recorrido por niveles, con una cola.
DFS	depth-first search	Recorrido que baja todo lo posible antes de retroceder.
Componente conexa	connected component	Grupo máximo de nodos conectados entre sí.
Union-find	union-find, disjoint sets	Estructura que une conjuntos y dice si dos elementos están en el mismo.
Compresión de caminos	path compression	Hacer que los nodos visitados por `find` apunten directo a la raíz.
Camino mínimo	shortest path	Camino de menor peso total entre dos nodos.
Relajar	relax	Actualizar la distancia a un nodo si una arista da un camino más corto.
Dijkstra	Dijkstra’s algorithm	Halla caminos mínimos con pesos no negativos, usando una cola de prioridad.
Trie	trie	Árbol donde cada camino desde la raíz representa un prefijo.
Filtro de Bloom	Bloom filter	Conjunto aproximado en un arreglo de bits, con falsos positivos y sin falsos negativos.