INDICE VIDEOS TEORIA 2025

Clase 1

• ENLACE Introducción al curso: Presentación de la materia, la cátedra y los docentes.
• ENLACE Evaluación del curso: Fechas y detalles sobre parciales y trabajos prácticos.
• ENLACE Contenido del curso: Temas a tratar, incluyendo listas, árboles y conjuntos.
• ENLACE Videos y recursos: Enlaces a clases y material de apoyo.
• ENLACE Instrucciones para TPL1: Explicación del primer trabajo práctico.
• ENLACE Diseño y análisis de algoritmos: Definición y analogías de algoritmos.
• ENLACE Ejemplos de problemas: "Problema del Agente Viajero" y "caballo de ajedrez".
• ENLACE Estrategias para resolver problemas: Búsqueda exhaustiva y algoritmos heurísticos.
• ENLACE Sincronización en cálculo distribuido: Procesamiento con memoria compartida.
• ENLACE Introducción básica a grafos: Definición y representación de grafos.
• ENLACE Planteo del problema mediante grafos: Modelado de problemas de sincronización.
• ENLACE Generación de coloraciones: Explicación de coloraciones en grafos.
• ENLACE Crecimiento del tiempo de ejecución: Análisis del crecimiento exponencial en algoritmos.
• ENLACE Algoritmo heurístico ávido: Introducción a una estrategia de solución eficiente.
• ENLACE Tiempo de ejecución del algoritmo ávido: Comparación de eficiencia con búsqueda exhaustiva.
• ENLACE Tiempos de ejecución de un programa: Análisis de eficiencia en términos de recursos.
• ENLACE Notación asintótica: Introducción a la notación "O" para comparar algoritmos.

Clase 2

• ENLACE Clase de complejidad NP: Introducción al tema principal del video.
• ENLACE Reducción de problemas: Análisis de cómo se comporta un problema al reducirse a otro.
• ENLACE Método de la burbuja: Explicación de este algoritmo de ordenamiento simple.
• ENLACE Llamadas a funciones y bucles: Discusión sobre las estructuras "for" y "while".
• ENLACE Ventajas del método de la burbuja: A pesar de ser un algoritmo lento, se mencionan casos donde puede ser útil.
• ENLACE Concepto de "wrapper": Presentación de esta función que adapta argumentos para llamar a otra función.

Clase 3

Parte 1: Implementación de Listas con Arreglos

• ENLACE - Introducción: Se comienza explicando cómo representar listas utilizando arreglos.
• ENLACE - Diseño de la Clase `List`: Se presenta la estructura de la clase en C++, incluyendo sus miembros privados (`MAX_SIZE`, `elems`, `size`).
• ENLACE - Métodos Públicos: Se detallan las funciones principales de la clase, como `insert`, `erase`, `clear`, `begin`, `end` y `next`.
• ENLACE - Operación `insert`: Se explica cómo funciona la inserción de un elemento y el desplazamiento necesario en el arreglo.
• ENLACE - Código C++: Se muestra un fragmento de código con la implementación de la clase y sus métodos.
• ENLACE - Iteradores `begin()` y `end()`: Se explica la función de los iteradores para marcar el inicio y el fin de la lista.
• ENLACE - Método `insert` (en detalle): Se profundiza en la implementación del método, incluyendo validaciones.
• ENLACE - Método `erase`: Se describe el proceso de eliminación de un elemento y el reajuste del arreglo.
• ENLACE - Función `clear`: Se introduce cómo eliminar todos los elementos de la lista.

Parte 2: Desventajas y Alternativas

• ENLACE - Limitaciones de los Arreglos: Se discuten los problemas de usar un almacenamiento rígido.
• ENLACE - Complejidad de `insert` y `erase`: Se menciona que estas operaciones tienen un costo promedio de O(n).

Parte 3: Listas por Celdas Enlazadas

• ENLACE - Introducción a Celdas Enlazadas: Se presenta un nuevo enfoque para implementar listas.
• ENLACE - Estructura `cell` y Clase `List`: Se define cómo se estructura una celda y la lista con punteros.
• ENLACE - El Concepto de "Posición": Se explica cómo se manejan las posiciones en este tipo de listas.
• ENLACE - Inserción en Listas Enlazadas: Se ilustra el proceso de añadir un nuevo elemento.
• ENLACE - Celda de Encabezamiento: Se introduce un objeto para gestionar los punteros al primer y último elemento.
• ENLACE - Ejemplos de `retrieve`: Se muestra cómo recuperar elementos en diferentes posiciones.
• ENLACE - Implementación General: Se presenta el código para listas con celdas enlazadas.
• ENLACE - Inicialización: Se explica cómo crear una lista enlazada desde cero.
• ENLACE - Función `clear()`: Se detalla cómo vaciar una lista enlazada.
• ENLACE - Iterador `prev`: Se muestra la implementación del iterador para retroceder en la lista.
• ENLACE - Método `insert` (en detalle): Se profundiza en la inserción para listas enlazadas.
• ENLACE - Método `erase` (en detalle): Se describe el proceso de eliminación en este tipo de listas.
• ENLACE - `clear()` con `erase`: Una forma alternativa de implementar la función de limpieza.
• ENLACE - Implementación de `begin()` y `end()`: Cómo funcionan los iteradores en listas enlazadas.

Parte 4: Listas por Cursores

• ENLACE - Introducción a Listas por Cursores: Se presenta este concepto como una alternativa a los punteros.
• ENLACE - Asignación de Memoria: Se explica cómo se gestionan las celdas en un área de memoria dinámica.
• ENLACE - Beneficios de los Cursores: Se analizan las ventajas, como una gestión de memoria más eficiente.

Clase 4

Parte 1: Correspondencias

• ENLACE - Introducción a las Correspondencias: Se explica que son estructuras similares a una base de datos que almacenan pares de clave-valor.
• ENLACE - Definición de una Clase: Se muestra cómo definir una clase para una correspondencia, incluyendo su constructor y características.
• ENLACE - Acceso a Clave y Valor: Se destaca que los métodos para acceder a los datos dependen de si la correspondencia está ordenada o no.
• ENLACE - Clase `Map`: Se introduce `Map` como un tipo de plantilla con dos argumentos.
• ENLACE - Rendimiento de Operaciones: Se presenta una tabla comparando la complejidad temporal de operaciones (`find`, `insert`, `erase`, `clear`) para listas y vectores.
• ENLACE - Vectores Ordenados: Se discuten las ventajas de usar vectores ordenados, especialmente para la búsqueda binaria.
• ENLACE - Clase `Element_t`: Se define la clase `element_t`, que contiene los campos `first` y `second`.
• ENLACE - Sobrecarga de Operadores: Se explica cómo sobrecargar el operador `<` para permitir el ordenamiento de clases personalizadas.

Parte 2: Árboles

• ENLACE - Introducción a los Árboles: Se explica el concepto de árbol y su definición recursiva.
• ENLACE - Organización Jerárquica: Se muestra cómo se organizan los nodos en una estructura jerárquica.
• ENLACE - Conceptos Fundamentales: Se definen términos clave como padre, hijo, hojas, nivel y profundidad.
• ENLACE - Recorridos de Árboles: Se explican diferentes formas de recorrer un árbol:

Parte 3: Aplicaciones Prácticas

• ENLACE - Calculadora RPN con una Pila: Se detalla la implementación de una calculadora de Notación Polaca Inversa (RPN) utilizando una pila, explicando cómo se manejan los operandos y operadores.

Parte 4: Tipos de Datos (en detalle)

• ENLACE en adelante: Se realiza una discusión extensa sobre diversos tipos de datos y sus propiedades.

Clase 5

• ENLACE Notación Lisp para árboles: Se explican las expresiones matemáticas complejas, con ejemplos de notación Lisp y sus ventajas.
• ENLACE Reconstrucción del árbol: Se plantea si es posible reconstruir un árbol a partir de su listado y se propone el desafío de encontrar el árbol.
• ENLACE Inserción en árboles: Se detallan las operaciones de inserción con ejemplos.
• ENLACE Algoritmo para copiar árboles: Se explica el algoritmo de copia, con ejemplos y la variante de copia espejo.
• ENLACE Supresión en árboles: Se abordan las operaciones de supresión y la poda de nodos impares.
• ENLACE Operaciones básicas sobre árboles: Se describen las operaciones fundamentales.
• ENLACE Implementación por punteros: Se profundiza en la clase `iterator_t`, sus campos, la implementación de la clase `Tree` y sus constructores.
• ENLACE Tiempos de ejecución: Se analizan los tiempos de ejecución de las operaciones básicas.
• ENLACE Árboles binarios: Se define qué son los árboles binarios y sus diferencias con los árboles generales.

Clase 6

• ENLACE Árboles Binarios:
• ENLACE Listado Simétrico en Árboles Ordenados:
• ENLACE Notación Lisp:
• ENLACE Operaciones de Árboles Abstractos:
• ENLACE Interfaz Básica en Programación:
• ENLACE Programación Funcional en Árboles Binarios:
• ENLACE Árboles de Huffman:
• ENLACE Condición de Prefijo en Árboles de Huffman:
• ENLACE Representación de Árboles de Huffman:
• ENLACE Códigos Redundantes en Árboles de Huffman:

Clase 7

• 00:00 Presentación inicial e introducción al tema.
• 03:15 Explicación detallada del algoritmo de Huffman.
• 26:22 Discusión sobre la notación y operaciones de conjuntos.
• 54:49 Implementación de conjuntos mediante vectores de bits.
• 01:28:13 Explicación sobre las relaciones de orden en los conjuntos.
• 01:31:01 Definición y ejemplos de una relación de orden en programación.
• 01:35:10 Discusión sobre el uso de la clase "A" en relaciones de orden.
• 01:38:59 Interfaz avanzada para la gestión de conjuntos.
• 01:54:50 Análisis del flujo de datos en un programa de compresión de archivos.
• 02:08:38 Introducción a los diccionarios en el contexto de algoritmos y estructuras de datos.

Clase 8 2025-10-21. Parte 1

• Introducción y Conceptos Básicos Contexto del TAD Diccionario y presentación de las Tablas de Dispersión (Hash Tables). [01:51]
• Cubetas y Función de Dispersión Definición de las Cubetas (Buckets) y la Función de Dispersión ($H(x)$). Uso de la operación módulo. [03:17]
• Colisiones y Efecto Cumpleaños Definición y riesgo de Colisiones. Explicación del Efecto Cumpleaños (Birthday Effect) y el Birthday Attack (cálculo de probabilidad por raíz cuadrada). [11:36]
• Tablas Abiertas (Separate Chaining) Implementación con Vector de Listas. Discusión sobre el costo promedio de operaciones: $O(1 + n/B)$. [20:00]
• Implementación y `next_out` Estructura del iterador y las funciones `insert`, `find`, y la complejidad del iterador (`begin`, `next_out`) cuando la tabla está vacía o llena. [29:05]
• Funciones Hash de Calidad Importancia de la uniformidad y el Efecto Cascada. Ejemplo de función hash sumando caracteres de un `string`. [51:11]
• Tablas Cerradas (Open Addressing) Implementación con Vector de Elementos. Uso de valor especial `undef` y la estrategia de Sondeo Lineal (búsqueda circular). [01:01:03]
• Costo de Inserción Exitosa Análisis del costo de la inserción exitosa en tablas cerradas en función de la Tasa de Ocupación ($\alpha$): $\frac{1}{1-\alpha}$. [01:14:48]
• Costo de Búsqueda y Supresión Costo de la Búsqueda Exitosa e Inserción No Exitosa (fórmula con logaritmo). Problema de la supresión y el uso del valor `deleted`. [01:22:29]
• Reinserción Continua y Vicios Concepto de "envenenamiento" de la tabla y la solución de Reinserción Continua para evitar el uso de `deleted`. [01:31:10]
• Hash Criptográfico y Seguridad Aplicaciones de las funciones hash (SHA-256, MD5) en Firma Digital. Explicación del Ataque por Colisión y cómo se explota el Birthday Attack. [01:46:42]

Clase 9 2025-10-21. Parte 2

• I. Aplicación Criptográfica de Funciones Hash (Blockchain)
  • Hash en Blockchain Uso del hash para asegurar que todas las copias del Libro Contable (Ledger) de la red sean idénticas. [00:22]
  • Bloques y Encadenamiento Las transacciones se agrupan en Bloques, y cada bloque incluye el hash del bloque anterior, creando una Blockchain. [04:00]
  • Prueba de Trabajo (Proof of Work) Mecanismo para evitar ataques: se requiere encontrar un número (Nonce) tal que el hash del bloque cumpla con una condición (ej. una cantidad de ceros iniciales). [05:35]
  • Minado y Dificultad El proceso de Minado consiste en la búsqueda por fuerza bruta de ese Nonce, regulado por el Grado de Dificultad. [07:06]
  • Explorador de Blockchain Visualización en tiempo real de los bloques, transacciones y hashes. [09:33]

• II. Conjuntos con Árboles Binarios de Búsqueda (BST)
  • Definición de BST Un nodo separa a elementos menores a la izquierda y mayores a la derecha; la condición se aplica recursivamente. [12:59]
  • Propiedades y Costo La longitud de los caminos es $O(\log N)$ si el árbol está balanceado. El listado en orden simétrico produce los elementos ordenados. [14:55]
  • Operación Find e Insert El costo de buscar o insertar un elemento es proporcional a la longitud del camino recorrido. [21:44]
  • Operación Erase (Borrado) Se distinguen y resuelven los tres casos de borrado: 0 hijos (hoja), 1 hijo (sube el subárbol), y 2 hijos (se reemplaza por el mínimo del subárbol derecho). [24:49]
  • Recorrido (Operador `P++`) Lógica para encontrar el siguiente elemento en orden (sucesor) para el iterador. [29:41]
  • Peor Caso y Balanceo El peor caso ocurre cuando el BST degenera en una lista (ej. al insertar elementos ordenados), llevando el costo a $O(N)$. [48:23]
  • Árboles Autobalanceados Introducción a los algoritmos (ej. AVL) basados en Rotaciones para mantener el árbol balanceado y el costo en $O(\log N)$. [51:38]

• III. Introducción a Ordenamiento (Sorting)
  • Conceptos Iniciales Enfoque en el Ordenamiento Interno (datos en memoria principal) y la diferencia de algoritmos para vectores vs. listas. [57:28]
  • Costo Algorítmico El piso teórico de complejidad para algoritmos de ordenamiento por comparación es $O(N \log N)$. [01:03:00]
  • Estabilidad Definición y utilidad de un algoritmo estable: los elementos equivalentes mantienen su orden relativo original. [01:08:38]
  • Funciones de Comparación Generalmente, solo se necesita definir la relación de "menor" (predicado binario) para derivar las demás comparaciones. [01:15:57]
  • Operador Nave Espacial Presentación del operador `operator<=>` (spaceship operator) de C++ que retorna $-1$, $0$ o $1$ y simplifica todas las comparaciones. [01:18:15]

Clase 10 2025-10-29

I. Ordenamiento. Introducción y Conceptos Fundamentales

• [00:03] Introducción al capítulo de Ordenamiento (Sorting).
• [00:19] Repaso de la Relación de Orden y eficiencia esperada.
• [01:45] El operador "Nave Espacial" (`operator<=>`) y su uso para comparación.
• [04:10] Implementación de `operator<=>` para clases compuestas.
• [09:46] Introducción a los Métodos de Ordenamiento Lentos ($\mathcal{O}(N^2)$).

II. Métodos de Ordenamiento Lentos ($\mathcal{O}(N^2)$)

• [10:16] Método de la Burbuja (Bubble Sort): Funcionamiento conceptual.
• [13:39] Implementación de las funciones de ordenamiento: Uso de Rangos (`first`, `last`) y Función de Comparación (`comp`).
• [16:19] Ejemplos de uso (ej. ordenar por valor absoluto) y sobrecarga con `std::less`.
• [19:25] Uso de Aritmética de Punteros para Iteradores en la implementación de los algoritmos.
• [27:54] Método de Inserción (Insertion Sort).
• [32:05] Método de Selección (Selection Sort).
• [34:14] Comparación de métodos lentos: Complejidad en el mejor y peor caso (Anomalía de Insertion Sort en caso ordenado: $\mathcal{O}(N)$).
• [36:21] Cantidad de intercambios (swaps): Ventaja de Selection Sort ($\mathcal{O}(N)$).
• [38:09] Ordenamiento Indirecto para minimizar el movimiento de objetos grandes.

III. Algoritmos de Ordenamiento Rápido ($\mathcal{O}(N \log N)$)

• [42:37] Quicksort: Estrategia "Dividir para Vencer" y el concepto de Pivote.
• [47:34] Análisis de Complejidad de Quicksort (Caso balanceado: $\mathcal{O}(N \log N)$).
• [56:41] Implementación de la función auxiliar `particiona` (Partition).
• [01:03:59] Costo del particionamiento: $\mathcal{O}(N)$.
• [01:04:05] Estrategia para elegir el pivote (Mediana).
• [01:08:14] Optimización: Switcheo de algoritmos para arreglos pequeños (ej. Quicksort a Bubble Sort).
• [01:12:49] Peor caso de Quicksort: degeneración a $\mathcal{O}(N^2)$ (ej. arreglo ordenado).
• [01:20:20] Animación comparativa de Bubble Sort vs Quicksort.

IV. Heapsort y Solución de la STL

• [01:21:58] Heapsort: Estructura ideal y operaciones deseadas en $\mathcal{O}(\log N)$.
• [01:25:27] La estructura de Montículo (`Heap`): Parcialmente ordenado y parcialmente completo.
• [01:28:49] Implementación del montículo en un Vector (cálculo de hijos/padre por aritmética).
• [01:31:36] Operación `Insert` en un montículo.
• [01:33:23] Operación `Erase` (extracción del mínimo) y el procedimiento Reheap (`remonticulizar`).
• [01:41:21] Aplicación: Cola de Prioridad (`std::priority_queue`).
• [01:44:23] Inicialización del montículo: MakeHeap (de abajo hacia arriba).
• [01:46:56] Costo de `MakeHeap`: $\mathcal{O}(N)$.
• [01:52:56] El algoritmo Heapsort (ordenamiento in place).
• [01:56:34] Comparación Quicksort vs Heapsort (Heapsort garantiza $\mathcal{O}(N \log N)$).
• [01:58:55] Solución de la STL: Introsort (Quicksort con fallback a Heapsort para evitar el peor caso).
• [02:02:28] Cierre de la clase.