INDICE VIDEOS TEORÍA 2026

CLASE TEORÍA MARTES 2026-08-12

• [00:00:02] — Presentación del Equipo Docente y Cuestiones Administrativas
  • Matriculación en el entorno virtual (IFICH / Moodle) para la Licenciatura en Ciencia de Datos.
  • Uso del foro de novedades y canal oficial de comunicaciones.
• [00:05:04] — Recursos y Plataformas de la Cátedra
  • Página pública Wiki de la materia (cimec.org.ar/ed).
  • Uso del libro de apuntes vs. transparencias de clase.
  • Histórico de clases grabadas en YouTube con índices generados por IA.
  • Horarios de comisiones de prácticas.
• [00:12:02] — Régimen de Cursado y Evaluación 2026
  • Eliminación de los Trabajos Prácticos de Laboratorio (TPLs).
  • Estructura de las evaluaciones: 2 parciales presenciales + 1 recuperatorio.
  • División de los exámenes en 3 secciones independientes (Clases, Operativos y Preguntas teóricas).
  • Cálculo del promedio pesado y requisitos para Regularizar (≥40) y Promocionar (≥70).
  • Mecánica de recuperación y mejora de notas por secciones.
• [00:24:14] — Introducción a los Algoritmos
  • Definición formal de algoritmo y estado inicial/final.
  • Origen histórico: Alan Turing, Máquina de Turing y Doodle de Google.
  • Condición de terminación finita y estrategias de resolución de problemas.
• [00:31:37] — Ejemplo 1: Problema del Agente Viajero (TSP)
  • Planteo del recorrido mínimo pasando por $N$ ciudades.
  • Estrategia de búsqueda exhaustiva vs. Estrategia heurística.
• [00:38:37] — Ejemplo 2: Planificación y Sincronización de Tareas
  • Ejecución de $M$ tareas sobre objetos en memoria sin solapamiento.
  • Ejecución secuencial vs. ejecución paralela multinúcleo en etapas.
  • Partición admisible de conjuntos de tareas.
• [00:47:20] — Abstracción mediante Teoría de Grafos
  • Modelado mediante Grafos de Incompatibilidad (vértices y aristas).
  • Equivalencia del problema de particionado con el Coloreado de Grafos.
  • Teorema de los Cuatro Colores en grafos planos.
• [00:56:31] — Análisis de Estrategia 1: Búsqueda Exhaustiva
  • Generación de todas las combinaciones de colores posibles.
  • Cálculo de combinaciones totales ($NC^{NB}$) y reducción por redundancia.
  • Cálculo de la complejidad algorítmica ($O(N^N)$ / $O(N^{N+2})$).
  • Demostración práctica de imposibilidad temporal (ejemplo con 20 vértices vs. la edad del universo y supercomputadoras).
• [01:22:43] — Análisis de Estrategia 2: Algoritmo Heurístico Ávido (Greedy)
  • Definición de algoritmos ávidos y toma de decisiones locales.
  • Pasos del algoritmo ávido para colorear un grafo.
  • Ejemplo práctico ordenado alfabéticamente ($A, B, C, D, E$).
  • Diferencia entre solución obtenida por el algoritmo ávido vs. solución óptima.
  • Complejidad algorítmica polinomial $O(N^3)$ y rendimiento computacional.
• [01:38:30] — Estudio de la Complejidad Algorítmica y Eficiencia
  • Concepto de eficiencia en uso de CPU y memoria.
  • Cuándo y dónde optimizar código (módulos críticos vs. legibilidad).
  • Factores que afectan el tiempo de ejecución (Hardware, Compilador, Datos, Complejidad).
  • Análisis según casos: Mejor caso, Peor caso y Caso promedio.
• [01:50:37] — Consultas Finales y Cierre de Clase

🔗 Video completo en YouTube: https://www.youtube.com/watch?v=OaC2Jx6ZrMA

CLASE TEORÍA MARTES 2026-08-19

• [00:00:06] — Repaso: Tiempos de Ejecución y Medida de Eficiencia
  • Dependencia del tiempo según el tamaño de entrada $N$ (búsqueda lineal en arreglos).
  • Significado de la constante $C$ (costo por iteración e instrucciones de máquina).
  • Casos de análisis: mejor caso, peor caso y caso promedio.
• [00:06:06] — Notación Asintótica: Definición Formal de Big-O ($\mathcal{O}$)
  • Definición formal: existencia de constantes positivas $C$ y $n_0$.
  • Ejemplo gráfico y analítico: $(n+1)^2 = \mathcal{O}(n^2)$ con $C=2$ y $n_0=3$.
  • Comportamiento asintótico para $n$ grande e independencia de constantes.
• [00:10:42] — Propiedades de la Notación Big-O
  • Invariancia ante constantes multiplicativas ($k \cdot f(n) = \mathcal{O}(f(n))$).
  • Invariancia ante modificación de valores en un conjunto finito de puntos.
  • [00:14:17] Propiedad de transitividad y relación de orden asintótico.
  • Uso en la STL de C++ (complejidades de vector, list, set, map).
  • [00:16:05] Regla de la suma (término dominante) y regla del producto.
• [00:19:18] — Jerarquía y Familias de Funciones Asintóticas
  • Constantes $\mathcal{O}(1) < \log n < \sqrt{n} < n < n^p < 2^n < n! < n^n$.
  • El poder del orden logarítmico $\mathcal{O}(\log n)$ (ejemplo: buscar entre los átomos del universo).
  • Equivalencia entre bases de logaritmos por cambio de base.
  • [00:28:12] Aproximación de Stirling para $n!$ y su relación con $n^n$.
  • [00:30:28] Elección de la cota superior más ajustada (analogía meteorológica).
  • [00:32:52] Ejemplo de simplificación de expresiones algebraicas complejas.
• [00:36:43] — Determinación Experimental de Complejidad
  • Gráficos en escala doble logarítmica ($\log(t)$ vs. $\log(N)$).
  • Identificación del exponente a partir de la pendiente de la recta.
  • Complejidad espacial (consumo de memoria).
• [00:44:46] — Clases de Complejidad: P vs. NP y NP-Completitud
  • Definición de clase $\text{P}$ (tiempo polinomial).
  • Definición de clase $\text{NP}$ (verificación polinomial / Máquinas de Turing no determinísticas).
  • Problemas indecidibles (Halting Problem).
  • [01:01:32] El problema del milenio $P \stackrel{?}{=} NP$.
  • [01:04:01] Reducción polinomial de problemas (ej. Mediana a Ordenamiento).
  • Problemas $\text{NP}$-Completos ($\text{NPC}$) como el "techo" de $\text{NP}$ (TSP, Coloreo de Grafos).
  • Perspectiva de la computación cuántica (Algoritmo de Grover).
• [01:13:31] — Conteo de Operaciones en Código
  • Estrategia de conteo: de lo más interno a lo más externo.
  • Estructuras condicionales (if-else: peor caso y caso promedio).
  • Bucles simples (for / while: inicialización, condición, incremento y cuerpo).
  • [01:20:43] Caso de Estudio: Bubble Sort (Ordenamiento Burbuja)
    • Mecánica del algoritmo con lazos anidados.
    • Conteo formal de pasos en intervalos cerrados $[a, b]$.
    • Cálculo de la sumatoria $\sum (N - j - 1)$ y deducción analítica de $\mathcal{O}(N^2)$.
  • [01:44:14] Grafo de llamadas y funciones sin recursión.
• [01:48:51] — Algoritmos Recursivos: Búsqueda Binaria (Binary Search / Lower Bound)
  • Implementación con función wrapper y función auxiliar recursiva.
  • Uso de rangos semiabiertos $[J_1, J_2)$.
  • Condición de parada ($J_1 = J_2 - 1$) y bisección del intervalo.
  • Deducción intuitiva de la complejidad $\mathcal{O}(\log_2 N)$.
• [02:01:56] — Consultas Finales y Orientación sobre la Guía TP1

🔗 Video completo en YouTube: https://www.youtube.com/watch?v=Yx1f6PPYGRo

CLASE TEORÍA MARTES 2026-08-26

• [00:00:02] — Repaso: Complejidad en Algoritmos sin Recursión
  • Grafo de llamadas dirigido acíclico (DAG) y análisis de complejidad de abajo hacia arriba ($S_0 \to S_1 \to \dots$).
• [00:02:25] — Análisis de Complejidad en Algoritmos Recursivos: Búsqueda Binaria (Binary Search)
  • Estructura con función wrapper y función auxiliar recursiva en rangos semiabiertos $[J_1, J_2)$.
  • [00:05:57] Deducción formal de la ecuación de recurrencia $T(N) = D + T(N/2)$ en potencias de 2 ($N = 2^p$).
  • Deducción analítica de la complejidad logarítmica $\mathcal{O}(\log_2 N)$.
  • [00:18:14] Comparación de cotas: evaluación de rama condicional mediante max ($\mathcal{O}(\log N)$) vs. suma de ramas ($\mathcal{O}(N)$).
• [00:21:45] — Introducción a los Tipos Abstractos de Datos (TAD) y Contenedores
  • Ventajas de utilizar contenedores estándar (reutilización, modularidad, robustez y estimaciones de complejidad uniformes).
  • Niveles de estudio de los TADs: operaciones abstractas $\to$ interfaz C++ $\to$ implementaciones concretas.
  • Enfoque pedagógico: interfaz básica vs. interfaz avanzada (STL con templates y clases anidadas).
• [00:28:50] — El Tipo Abstracto de Datos: Listas (Definición Conceptual)
  • Secuencia lineal finita de elementos ($a_0, a_1, \dots, a_{n-1}$).
  • Posición ficticia end ($n$) y clasificación: posiciones derreferenciables vs. no derreferenciables.
  • Concepto de punteros nulos (nullptr / NULL) y memoria en la dirección cero.
  • [00:36:29] Operaciones abstractas: supresión (erase) e inserción (insert).
• [00:43:15] — Interfaz Básica de Listas en C++
  • Clase iterator como objeto opaco y métodos fundamentales: insert, erase, retrieve, next, begin y end.
  • [00:46:41] Retorno por referencia (LMT&) en retrieve() para su uso como l-value a la izquierda de la asignación.
  • [00:48:39] Invalidación y Refresco de Iteradores: consecuencias de modificar el contenedor y manejo seguro de punteros.
  • [01:01:42] Profundización en funciones que retornan referencias vs. punteros (ejemplo de duplicación del valor mínimo min(v)).
• [01:10:28] — Ejemplo Práctico: Eliminación de Duplicados In-Place (Purge)
  • Recorrido con doble iterador ($P$ y $Q$) y actualización condicional del iterador (erase vs. next).
  • Análisis de condiciones de borde y prevención de errores en tiempo de ejecución.
• [01:16:07] — Implementación 1: Listas por Arreglos (Vectores Contiguos)
  • Estructura con tamaño máximo MAX_SIZE, puntero elems y contador size.
  • Constructores, destructores y liberación de memoria con delete[].
  • Desventajas: rigidez en memoria y complejidad $\mathcal{O}(N)$ para inserción y borrado.
• [01:34:31] — Implementación 2: Listas por Celdas Simplemente Enlazadas
  • Estructura de la clase Cell (campo de dato elem, puntero next y clases amigas friend).
  • Declaraciones adelantadas (forward declarations).
  • [01:44:09] Convención de Posición Adelantada: por qué el iterador a un elemento apunta a la celda anterior.
  • [01:50:03] Celda de Encabezamiento (Header Cell): punteros first y last.
  • [01:54:45] Acceso con operador flecha (->) en retrieve(): q->next->elem.
• [01:57:29] — Consultas Finales y Cierre

🔗 Video completo en YouTube: https://www.youtube.com/watch?v=OsX9_2l2aD4

CLASE TEORÍA MARTES 2026-09-01

• [00:00:01] — Repaso: TAD Lista y Celdas Simplemente Enlazadas
  • Condición de diseño de listas: operaciones de inserción y borrado en tiempo $\mathcal{O}(1)$.
  • Limitaciones de la implementación por arreglos contiguos.
  • [00:02:46] Convención de Posición Adelantada: necesidad del enlace anterior para insert en listas simplemente enlazadas.
  • [00:04:06] Celda de Encabezamiento (Header Cell): punteros first y last, y su correspondencia con begin() y end().
• [00:09:26] — Implementación en C++ de Listas por Celdas
  • Constructor y cadena de inicialización (first = new Cell; last = first;).
  • Destructor y liberación con clear() y delete escalar.
  • [00:12:19] Acceso al elemento mediante operador flecha en retrieve(): p->next->elem.
  • [00:13:06] Mecánica del Método insert(p, k): reacomodamiento de enlaces con new Cell, actualización de last y retorno de iterador refrescado.
  • Asignación de memoria dinámica en el heap y excepciones en new.
  • [00:20:07] Implementación de clear() como erase(begin(), end()) en rangos semiabiertos $[a, b)$.
• [00:23:04] — Implementación Alternativa: Listas por Cursores
  • Almacenamiento de celdas en un arreglo global estático (cellspace) mediante enteros como cursores.
  • Ventajas: independencia de punteros y mitigación de la fragmentación de memoria.
  • [00:35:39] Gestión de Memoria Libre: lista enlazada de celdas disponibles encabezada por topFreeCell y marca nullCell ($-1$).
  • Funciones auxiliares new_cell(), delete_cell() y rutina de inicialización cellspace_init().
  • [00:41:20] Tabla de equivalencias entre listas por punteros y listas por cursores.
• [00:43:09] — Comparativa de Complejidades Algorítmicas de los Métodos de Lista
  • Comparación entre implementaciones (Arreglos vs. Punteros vs. Cursores): insert, erase, clear, size y prev.
  • Diferencias entre normas anteriores y el estándar C++11 (complejidad de size() vs. splice()).
• [00:47:56] — Transición a la Interfaz STL Avanzada
  • Plantillas de clases (templates: list<T>).
  • Sobrecarga de operadores: incremento prefijo y postfijo (++p vs. p++), derreferenciación (*p).
  • Clases anidadas (nested classes): aislamiento de list::iterator frente a otros contenedores.
  • [00:52:54] Listas Doblemente Enlazadas (std::list): punteros next y prev, análisis de carga útil (payload) vs. sobrecarga de memoria (overhead de alineación de 8 bytes).
• [00:56:47] — El Tipo Abstracto de Datos: Pila (Stack)
  • Principio LIFO (Last-In, First-Out) y operaciones abstractas: push, pop, top, empty.
  • [01:00:40] Recorrido destructivo vs. no destructivo: preservación de orden usando una pila auxiliar (doble inversión).
  • Concepto de algoritmo in-place para estructuras enlazadas.
  • [01:03:26] Implementaciones: sobre lista (tope en begin vs. end) y sobre arreglo continuo (adaptador). Complejidades asociadas.
• [01:08:39] — El Tipo Abstracto de Datos: Cola (Queue)
  • Principio FIFO (First-In, First-Out) y operaciones abstractas: front, back, push, pop.
  • Uso como amortiguador (buffer de E/S).
  • Implementación sobre lista (front en begin y back en end) para garantizar $\mathcal{O}(1)$.
  • Recorrido de colas mediante cola auxiliar y preservación de orden nativo.
• [01:13:52] — El Tipo Abstracto de Datos: Correspondencia (Map / Memoria Asociativa)
  • Definición matemática: función unívoca del dominio (claves) al contradominio (valores).
  • Representación de pares clave-valor (pair<first, second>).
  • [01:16:33] Ejemplo aplicativo: liquidación de sueldos (payroll).
  • Operaciones abstractas: find, insert, erase.
  • [01:24:32] Comportamiento de retrieve(): creación implícita con valor por defecto cuando la clave no existe.
  • Retorno de claves por copia (inmutabilidad para mantener el orden) y valores por referencia.
  • Implementación inicial sobre contenedores lineales.
• [01:30:56] — Consultas Finales: Modalidad de Exámenes Parciales 2026
  • Eliminación de los exámenes de programación en máquina (TPLs) ante el impacto de herramientas de IA.
  • Estructura del parcial presencial en papel: preguntas de teoría, ejercicios operativos (ej. pasos de HeapSort) y análisis/seguimiento de código con foco en complejidad algorítmica.

🔗 Video completo en YouTube: https://www.youtube.com/watch?v=KHQI-yj6ZuQ

CLASE TEORÍA MARTES 2026-09-08

• [00:00:00] — Implementación del TAD Correspondencia (Map) en Contenedores Lineales
  • Representación mediante pares clave-valor (pair<first, second>) almacenados en listas o vectores[cite: 7].
  • [00:03:08] Contenedores Lineales Desordenados:
    • Costo de búsqueda secuencial find(k) en el peor caso $\mathcal{O}(N)$[cite: 7].
    • Inserción insert(k, v): búsqueda previa $\mathcal{O}(N)$ y sobreescritura/inserción al final $\mathcal{O}(1)$[cite: 7].
    • Borrado erase(p): $\mathcal{O}(1)$ en listas vs. $\mathcal{O}(N)$ en vectores por corrimiento de memoria[cite: 7].
  • [00:09:34] Contenedores Lineales Ordenados por Clave:
    • Requisito de relación de orden sobre el dominio (sobrecarga de operator<, orden lexicográfico en strings)[cite: 7].
    • Corte temprano en búsquedas al encontrar claves mayores[cite: 7].
    • [00:15:09] Método auxiliar interno lower_bound(k) (primera posición donde insertar preservando el orden)[cite: 7].
    • Diferencia conceptual y funcional entre lower_bound(), find(), insert() y retrieve()[cite: 7].
    • Inserción implícita por defecto de retrieve() (o operator[]) ante claves inexistentes[cite: 7].
    • Retorno de key() por copia (inmutabilidad de la clave ordenada) vs. value() por referencia (l-value modificable)[cite: 7].
  • [00:25:17] Interfaz STL Avanzada y Complejidad Comparada:
    • Uso de std::pair templatizado y sobrecarga del operator[][cite: 7].
    • Análisis de complejidad: búsqueda binaria en vectores ordenados $\mathcal{O}(\log N)$ por acceso aleatorio[cite: 7].
    • Imposibilidad de aplicar búsqueda binaria en listas enlazadas (acceso estrictamente secuencial)[cite: 7].
    • Costo de inserción en vector ordenado: búsqueda $\mathcal{O}(\log N)$ + corrimiento físico $\mathcal{O}(N) \Rightarrow \mathcal{O}(N)$[cite: 7].
• [00:36:52] — Introducción al TAD Árbol (Tree)
  • Concepto de estructura jerárquica y aplicaciones (sistemas de archivos, jerarquías organizacionales, expresiones algebraicas)[cite: 7].
  • Definición recursiva: colección de nodos, nodo raíz y subárboles disjuntos; noción de árbol vacío ($\Lambda$)[cite: 7].
  • [00:40:44] Terminología Fundamental:
    • Caminos y longitud (número de aristas)[cite: 7].
    • Relaciones de parentesco: padre, hijo, antecesor y descendiente; antecesores y descendientes propios[cite: 7].
    • Nodos hoja (sin descendientes) vs. nodos interiores[cite: 7].
    • Altura de un nodo: longitud máxima hacia una hoja (definición recursiva $h(n) = 1 + \max(h(c_i))$)[cite: 7].
    • Profundidad y niveles: distancia desde la raíz (raíz a profundidad 0)[cite: 7].
    • Nodos hermanos (mismo padre directo) vs. nodos al mismo nivel[cite: 7].
  • [00:47:20] Árboles Ordenados y Orientados (AOO):
    • Importancia del orden entre hermanos: hijo más a la izquierda (leftmost child) y hermano derecho (right sibling)[cite: 7].
    • Modelo de lista bidimensional y propagación de lambdas ($\Lambda$) al agotar direcciones[cite: 7].
    • Partición de los nodos respecto a un nodo $N$ en 5 conjuntos disjuntos (nodo, antecesores propios, descendientes propios, izquierda y derecha)[cite: 7].
  • [00:54:31] Antecesor Común Más Bajo (LCA - Lowest Common Ancestor):
    • Definición formal y caracterización de parentesco mediante las distancias relativas al LCA[cite: 7].
    • Propiedades de asociatividad y conmutatividad del operador LCA para múltiples nodos[cite: 7].
• [01:00:38] — Recorridos de Árboles (Traversals) y Aplicaciones
  • Orden Previo (Preorder): definición recursiva (nodo $\to$ hijos de izquierda a derecha) y método gráfico del barco en sentido antihorario[cite: 7].
  • [01:04:59] Orden Posterior (Postorder): definición recursiva (hijos $\to$ nodo) y última visita en el contorno del árbol[cite: 7].
  • [01:06:06] Árboles de Expresión Sintáctica:
    • Modelado de expresiones aritméticas y correspondencia con la Notación Polaca Inversa (RPN)[cite: 7].
  • [01:08:34] Notación Lisp para Árboles:
    • Sintaxis prefija con paréntesis y definición recursiva[cite: 7].
    • Relación biunívoca entre el árbol y su cadena Lisp; concepto de serialización de estructuras bidimensionales a texto/bytes[cite: 7].
  • [01:17:23] Reconstrucción de Árboles a partir de Preorder + Postorder:
    • Demostración de no-unicidad con un único recorrido y suficiencia al combinar Preorder y Postorder[cite: 7].
    • Algoritmo de reconstrucción paso a paso identificando raíz y delimitando subárboles recursivamente[cite: 7].
  • [01:23:40] Implementación Recursiva de Algoritmos sobre Árboles:
    • Rutinas en pseudocódigo: preorder(), postorder() y lisp_print()[cite: 7].
• [01:26:59] — Consultas Finales sobre Parciales y Cierre
  • Aclaración sobre la evaluación: foco en análisis y complejidad algorítmica de fragmentos de código sin escritura de programas completos en máquina[cite: 7].

🔗 Video completo en YouTube: https://www.youtube.com/watch?v=ciJvMzX0qfI