\documentclass[11pt]{article}
\usepackage[utf8]{inputenc}
\usepackage[spanish]{babel}
\usepackage{amsmath, amssymb}
\usepackage{graphicx}
\usepackage{hyperref}
\usepackage{geometry}
\geometry{margin=2.5cm}
\title{Tarea 2: Delete Insert Edit Distance \\ \large Análisis de Algoritmos
(501.404) - 2025A}
\author{Javier Ignacio Reyes Gunther, Nombre2, Nombre3}
\date{\today}
\begin{document}
\maketitle
\section*{Integrantes y liderazgo por sección}
\begin{itemize}
\item Sección 1: Javier Ignacio Reyes Gunther
\item Sección 2: Nombre2
\item Sección 3: Nombre3
\item Sección 4: Javier Ignacio Reyes Gunther
\item Sección 5: Nombre2
\item Sección 6: Nombre3
\item Sección 7: Javier Ignacio Reyes Gunther
\end{itemize}
\section{Casos de Prueba}
Se eligieron las siguientes 4 cadenas:
\\\texttt{casa, caza, cansado, asa}
Se construyeron los 12 casos de prueba considerando todas las combinaciones
posibles de pares ordenados distintos. La distancia de edición se justifica
considerando únicamente operaciones de inserción y eliminación. Se muestra una
tabla con los resultados esperados.
\begin{center}
\begin{tabular}{|c|c|c|c|}
\hline
\# & S & T & Distancia Justificada \\
\hline
1 & casa & caza & Reemplazo de 's' por 'z' mediante Delete + Insert $\Rightarrow$ 2
\\
2 & casa & cansado & Insertar 'n', 'd', 'o' $\Rightarrow$ 4 \\
3 & casa & asa & Eliminar 'c' $\Rightarrow$ 1 \\
4 & caza & casa & Reemplazo de 'z' por 's' $\Rightarrow$ 2 \\
5 & caza & cansado & Varias inserciones y eliminaciones $\Rightarrow$ 5 \\
6 & caza & asa & Eliminar 'c', 'z', insertar 's' $\Rightarrow$ 3 \\
7 & cansado & casa & Eliminar 'n', 'd', 'o' $\Rightarrow$ 3 \\
8 & cansado & caza & Eliminar 'n', 's', 'd', 'o', insertar 'z' $\Rightarrow$ 5 \\
9 & cansado & asa & Eliminar 'c', 'n', 'd', 'o' $\Rightarrow$ 4 \\
10 & asa & casa & Insertar 'c' $\Rightarrow$ 1 \\
11 & asa & caza & Insertar 'c' y 'z' $\Rightarrow$ 2 \\
12 & asa & cansado & Insertar 'c', 'n', 'd', 'o' $\Rightarrow$ 4 \\
\hline
\end{tabular}
\end{center}
\section{Fórmula Recursiva}
La distancia de edición \texttt{EditDistanceDeleteInsert(i, j)} entre los prefijos
de longitud \texttt{i} de S y \texttt{j} de T se define como:
\[
EditDistance(i, j) =
\begin{cases}
j & \text{si } i = 0 \\
i & \text{si } j = 0 \\
EditDistance(i{-}1, j{-}1) & \text{si } S[i{-}1] = T[j{-}1] \\
1 + \min\left\{EditDistance(i{-}1, j), EditDistance(i, j{-}1)\right\} & \
text{si } S[i{-}1] \neq T[j{-}1]
\end{cases}
\]
\section{Implementación}
Se implementó la función en C++ utilizando cuatro paradigmas:
\subsection*{a. Recursiva pura}
\begin{verbatim}
int editDistanceRecursive(string S, string T, int i, int j) {
if (i == 0) return j;
if (j == 0) return i;
if (S[i-1] == T[j-1])
return editDistanceRecursive(S, T, i-1, j-1);
return 1 + min(editDistanceRecursive(S, T, i-1, j),
editDistanceRecursive(S, T, i, j-1));
}
\end{verbatim}
\subsection*{b. Recursiva con memoización}
\begin{verbatim}
int editDistanceMemo(string S, string T, int i, int j, vector<vector<int>>& memo) {
if (i == 0) return j;
if (j == 0) return i;
if (memo[i][j] != -1) return memo[i][j];
if (S[i-1] == T[j-1])
return memo[i][j] = editDistanceMemo(S, T, i-1, j-1, memo);
return memo[i][j] = 1 + min(editDistanceMemo(S, T, i-1, j, memo),
editDistanceMemo(S, T, i, j-1, memo));
}
\end{verbatim}
\subsection*{c. Programación dinámica}
\begin{verbatim}
int editDistanceDP(string S, string T) {
int n = [Link](), m = [Link]();
vector<vector<int>> dp(n+1, vector<int>(m+1));
for (int i = 0; i <= n; ++i)
for (int j = 0; j <= m; ++j)
if (i == 0) dp[i][j] = j;
else if (j == 0) dp[i][j] = i;
else if (S[i-1] == T[j-1]) dp[i][j] = dp[i-1][j-1];
else dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1]);
return dp[n][m];
}
\end{verbatim}
\subsection*{d. Dinámica optimizada}
\begin{verbatim}
int editDistanceDPOptimized(string S, string T) {
int n = [Link](), m = [Link]();
vector<int> prev(m+1), curr(m+1);
for (int j = 0; j <= m; ++j) prev[j] = j;
for (int i = 1; i <= n; ++i) {
curr[0] = i;
for (int j = 1; j <= m; ++j)
if (S[i-1] == T[j-1]) curr[j] = prev[j-1];
else curr[j] = 1 + min(prev[j], curr[j-1]);
prev = curr;
}
return prev[m];
}
\end{verbatim}
\section{Complejidad}
\begin{center}
\begin{tabular}{|l|c|c|}
\hline
Versión & Tiempo & Espacio \\
\hline
Recursiva pura & $\mathcal{O}(2^{n+m})$ & $\mathcal{O}(n+m)$ \\
Memoización & $\mathcal{O}(n \cdot m)$ & $\mathcal{O}(n \cdot m)$ \\
DP clásica & $\mathcal{O}(n \cdot m)$ & $\mathcal{O}(n \cdot m)$ \\
DP optimizada & $\mathcal{O}(n \cdot m)$ & $\mathcal{O}(m)$ \\
\hline
\end{tabular}
\end{center}
\section{Protocolo Experimental}
Se seleccionaron 4 textos del Proyecto Gutenberg de distintos tamaños (100, 300,
500 y 1000 caracteres). Se generan los 12 pares (S, T) y se mide tiempo y uso de
memoria para las versiones memoizada y dinámicas. Se usa \texttt{chrono} para
tiempo y herramientas como \texttt{valgrind} para memoria.
\section{Experimentación}
Se representaron gráficamente los resultados promedio de tiempo (ms) y uso de
memoria (KB) en gráficos de barras agrupadas. Se observó que \texttt{DP Optimizada}
mantuvo bajo consumo de memoria y rendimiento similar a \texttt{DP}. La versión \
texttt{Memo} fue más lenta en textos grandes.
\section{Conclusión}
Los resultados experimentales confirman el análisis teórico. La complejidad \( \
mathcal{O}(n \cdot m) \) se observa empíricamente en las versiones eficientes. La
versión optimizada en espacio destaca por su bajo consumo sin sacrificar velocidad.
La recursiva pura es inviable para entradas grandes, como se esperaba.
\end{document}