resumen.tex

\documentclass[10pt,a4paper]{article}
\usepackage{blindtext}
\usepackage{subcaption}
\usepackage{graphicx}
\usepackage{tikz}
\usepackage{amssymb}
\usepackage{caption}
\usepackage{amsmath}
\usepackage{circuitikz}
\usepackage{hyperref}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{listings}

\lstset{
    inputencoding=utf8,
    extendedchars=true,
    literate={á}{{\'a}}1 {é}{{\'e}}1 {í}{{\'i}}1 {ó}{{\'o}}1 {ú}{{\'u}}1 {ñ}{{\~n}}1 {Á}{{\'A}}1 {É}{{\'E}}1 {Í}{{\'I}}1 {Ó}{{\'O}}1 {Ú}{{\'U}}1 {Ñ}{{\~N}}1
}
\input{AEDmacros}
\newcommand{\notimplies}{\;\not\!\!\!\implies}
\title{Algoritmos y Estructuras de Datos II}
\author{Tomás Agustín Hernández}
\date{}

\begin{document}
\maketitle

\begin{figure}[b]
    \centering
    \begin{tikzpicture}[remember picture,overlay]
        \node[anchor=south east, inner sep=0pt, xshift=-1cm, yshift=2cm] at (current page.south east) {
            \begin{minipage}[b]{0.5\textwidth}
                \includegraphics[width=\linewidth]{logo_uba.jpg}
                \label{fig:bottom}
            \end{minipage}
        };
    \end{tikzpicture}
\end{figure}

\newpage
\section{Especificación}
\subsection*{Consideraciones importantes / Reminders}
\begin{itemize}
    \item Utilizar operadores luego: Si estoy en LPO (Lógica de Primer Orden) utilizar los operadores luego si vemos que hay una posible indefinición como una división, o ingresar a una lista a un índice. Recordar que el para todo y un existe, aunque esté acotado por un rango, los cuantificadores predican IGUAL para todos los valores. Entonces, aunque diga que x es positivo, también probará dividir inclusive por 0 y estallará.
    \item Recordar las condiciones bidireccionales
        \begin{itemize}
            \item Si por algún motivo tengo que armar una “lista”, como, por ejemplo, los divisores de un número x tengo que indicar que, si el número divide a x, entonces ese número está en res, pero además todos los valores que están en res DIVIDEN a x. Es una condición bidireccional. 
            \item Otro ejemplo puede ser que tenga que considerar el máximo de una lista, si todos los valores y que están en la lista son menores que res entonces significa que res también pertenece a esa lista original.
        \end{itemize}
    \item Recordar el significado de los cuantificadores con dos variables al mismo tiempo: En la lógica se ejecutan todos de uno a la vez. Es decir, si tengo que poner un para todo adentro de un para todo entonces hago un para todo solo con dos variables y listo.
    \item Recordar que cuando en un procedimiento llamo a un predicado y ese predicado devuelve algo de un para todo, existe (básicamente un valor de verdad) tengo que castear ese valor en el procedimiento porque son dos mundos distintos.
    Ej: asegura: { res = True \(\iff\) predicado}
    \item Los predicados y funciones auxiliares no describen problemas. Son herramientas sintácticas para descomponer predicados.
    \begin{itemize}
        \item Los procedimientos pueden llamar a funciones auxiliares o predicados. Un procedimiento no puede llamar a otro procedimiento.
        \item Los predicados pueden llamar a predicados o auxiliares. 
        \item Las auxiliares solo pueden llamar auxiliares.
    \end{itemize}
    \item No usamos nunca \(==\) en especificación, usamos siempre \(=\) y estamos comparando, no asignando.
    \item No existe el guardar o asignar en el mundo de la lógica. No puedo guardar en una lista en un índice específico porque si un valor. Para esto solemos usar que x valor pertenecerá a esta lista, por ejemplo.
    \item Si tengo un algoritmo que cumple una funcionalidad específica con un require más débil, puedo poner el require más restrictivo y va a funcionar igual pero NO al revés.
\end{itemize}
\subsection*{Fórmulas compuestas}
Decimos que una fórmula es compuesta a una fórmula que tiene más de una operación y esa operación necesita realizarse antes de conocer su valor.
\begin{itemize}
    \item \((p \land q) \lor m\)
    \item \(((p \land q) \lor m) \implies n\)
\end{itemize}
\subsection*{Fórmula atómica}
Decimos que una fórmula es atómica si se puede inferir su valor con una, o ninguna operación. Es irreducible.
\begin{itemize}
    \item p
    \item \(p \land q\)
\end{itemize}
\subsection*{Fórmulas bien definidas}
Decimos que una fórmula está bien definida cuando el orden que hay que hacer las operaciones es clara. Es decir, cuando cada operación toma dos variables proposicionales, y al realizar la operación termina siendo una fórmula atómica.
\begin{itemize}
    \item \(p \land q \lor r\) está mal formada. No se especifica si primero se realiza el \(\land\) o el \(\lor\).
    \item \((p \land q) \lor r\) está bien formada.
    \item \(p \land q \land r \land m\) está bien formada porque son todas conjunciones.
    \item \(p \lor q \lor r \lor m\) está bien formada porque son todas disyunciones.
\end{itemize}
\subsection*{Cuantificadores}
\begin{itemize}
    \item Para todo: \(\forall\)
    \begin{itemize}
        \item \(Garantiza \ la \ \text{conjunción}: p(1) \land p(2) \land p(3) \dots \land p(m) \). Todos los casos deben ser \True \ para que el cuantificador sea \True.
        \item Se acompaña por un \(\implica\) a la hora de predicar sobre los elementos.
        \item \((\forall i: \ent)(0 \le i < \longitud{s} \implicaLuego \ s[i] \ mod \ 2 = 0)\). Todos los elementos de la lista son divisibles por 2.
        \item Estructura: \(\forall\) + rango + \(\implicaLuego\)
    \end{itemize}
    \item Existe: \(\exists\)
    \begin{itemize}
        \item \(Garantiza \ la \ \text{disyunción}: p(1) \lor p(2) \lor p(3) \dots \lor p(m) \). Con un caso \True \ el cuantificador es \True.
        \item Se acompaña por un \(\land\) a la hora de predicar sobre los elementos.
        \item \((\exists i: \ent)(0 \le i < \longitud{s} \yLuego s[i] \ge 0)\). Existe algún elemento en la lista que es mayor o igual a 0.
        \item \(\exists\) + rango + \(\yLuego\)
    \end{itemize}
\end{itemize}
\subsection*{Equivalencias entre fórmulas}
Decimos que dos fórmulas son equivalentes \(\iff\) los valores de la tabla de verdad al aplicar la operación arroja el mismo resultado.

\subsection*{Valuaciones}
Las valuaciones surgen en base a la tabla de verdad. Las valuaciones serian darle valor a las variables proposicionales y ver el resultado de la operación. Solo hacen referencias a fórmulas atómicas.

\subsection*{Tautologias, contradicciones y contingencias}
\begin{itemize}
    \item Una fórmula es tautología \(\iff\) el resultado de la operación en cada fila arroja siempre V.
    \item Una fórmula es contradicción \(\iff\) el resultado de la operación en cada fila arroja siempre F.
    \item  Una fórmula es contradicción \(\iff\) el resultado de la operación en cada fila arroja siempre V y F.
\end{itemize}

\subsection*{Relaciones de fuerza entre fórmulas}
Decimos que una fórmula es más fuerte que la otra \(\iff\) una fórmula es más restrictiva que la otra, o está incluida en la otra. \\
En el mundo de la lógica, decimos que A es más fuerte que B \(\iff A \implies B\)

\begin{itemize}
    \item Si (\(A \implies B\)) y (\(B \implies A\)) son tautologías, entonces A y B son equivalentes.
    \item Si (\(A \implies B\)) es tautología y (\(B \notimplies A\)) no es tautología, entonces decimos que A es más fuerte que B.
    \item Si (\(A \notimplies B\)) y (\(B \notimplies A\)) son contigencias, entonces no existe relación de fuerza entre A y B.
\end{itemize}

Algunos ejemplos:

\begin{itemize}
    \item \(\longitud{s} = 0 \implies \longitud{s} \ge 0\). En este caso vemos que \(\longitud{s} = 0\) es más fuerte que \(\longitud{s} \ge 0\) pues \(\longitud{s} = 0\) está incluido en \(\longitud{s} \ge 0\). Por lo tanto, \(A \implies B\)
    \item \(\longitud{s} = 0 \implies \longitud{s} \ge 3\). En este caso vemos que \(\longitud{s} = 0\) no es más fuerte que \(\longitud{s} \ge 3\) pues \(\longitud{s} = 0\) no está incluido en \(\longitud{s} \ge 3\). Por lo tanto, \(A \notimplies B\)
    \item \(2 \le i < \longitud{s} \implies 1 \le i < \longitud{s}\). En este caso A \(\implies\) B, pues i = 2 está incluido en el rango de B. Por lo tanto, \(A \implies B\)
    \item \(0 \le i < \longitud{s} \implies 1 \le i < \longitud{s}\). En este caso A \(\notimplies\) B, pues el 0 de A no es parte de B. Por lo tanto, \(A \notimplies B\)
\end{itemize}

\subsection*{Tipos de parámetros en especificacion}
\begin{itemize}
    \item in: Solo nos interesa el valor de entrada de una variable. No la vamos a modificar. Ya están inicializados
    \item out: Donde se retornará el resultado. No nos importa el valor inicial ni tampoco determina nada en nuestra función.
    \item inout: Necesitamos el valor original por referencia el cual podrá ser modificado durante el procedimiento. Que sea inout no significa que siempre será modificado, sino que NO se garantiza que el valor al salir del procedimiento sea el mismo que cuando ingresó. Ej: Añadir un valor a un conjunto es inout pues hay casos donde no se modifica (pues el elemento ya está) y en otros sí (se agrega).
\end{itemize}
\subsection*{Lógica trivaluada}
También llamada lógica secuencial porque se procesa de izquierda a derecha; Nos introduce los conceptos de \(\yLuego \ \oLuego \ \implicaLuego\) y el valor de indefinido \(\bot\).

Se termina de evaluar una expresión cuando se puede deducir el valor de verdad. \\


Considere \(x = \True \land y = \bot \land z = \False \)
\begin{itemize}
    \item \(x \oLuego y\): Como el \(\oLuego\) necesita uno solo para ser verdadero, entonces como x ya es \(\True\) entonces toda la fórmula es verdadera.
    \item \(x \yLuego y\): Como el \(\yLuego\) necesita que ambas variables sean verdaderas, evalúa indefinido y el programa estalla.
    \item \(\neg x \implicaLuego y\): Como el \(\implicaLuego\) solo es falso si el antecedente es  \(\True\) y el consecuente \(\False\), como en este caso el antecedente ya es falso, toda la implicación es verdadera.
    \item \((x \land z) \yLuego y\): Como el \(\yLuego\) necesita que ambas fórmulas sean \(\True\), en este caso, como \((x \land z)\) es falso, entonces ya toda la fórmula es falsa. Nótese que el \(\land\) de la condición interna no contiene el luego porque jamás se indefinirá.
    \item \((\forall i: \ent)(0 \le i < \longitud{s} \implicaLuego s[i] \ge 0)\) Nótese que aquí usamos un \(\implicaLuego\) porque podría ser que la lista esté indefinida o no exista el valor en s[i]
\end{itemize}

\subsection*{Predicados}
\begin{itemize}
    \item Viven en el mundo de la lógica. 
    \item Nos sirven para poder modularizar nuestras especificaciones. 
    \item Solamente devuelven valores de verdad True y False y es necesario castearlos en caso de querer devolver bool como tipo de dato.
    \item Los predicados pueden llamar a otros predicados o funciones auxiliares.
    \item Pueden utilizar cuantificadores.
    \item No tienen requiere ni asegura.
    \item No admite parámetros in, out, inout.
\end{itemize}

\leavevmode
\\
Ejemplo cuando tenemos que transformar el valor de verdad a tipo de dato: 
\leavevmode
\\
\pred{divisiblePorDos}{n: \ent}{
    n \ mod \ 2 = 0
}

\begin{proc}{esMultiploDeDos}{\In n: \ent}{\bool}
    \requiere{\True}
    \asegura{res = true \iff divisiblePorDos(n)}
\end{proc}
\leavevmode
\\ 
Ejemplo usando un predicado sin necesidad de transformar el valor de verdad a tipo de dato: 

\leavevmode
\pred{todosSonPares}{l: \TLista{\ent}}{
    \paraTodo[unalinea]{i}{\ent}{0 \le i < \longitud{l}  \implicaLuego l[i] mod 2 = 0}
}

\begin{proc}{todosPares}{\In l: \TLista{\ent}}{\bool}
    \requiere{todosSonPares(l)}
\end{proc}
\newpage
\subsection*{Funciones Auxiliares}
\begin{itemize}
    \item Son reemplazos sintácticos. 
    \item Nos ayudan a modularizar las especificaciones.
    \item No pueden ser recursivas.
    \item Solo hacen cuentas.
    \item No pueden utilizar cuantificadores.
    \item Pueden llamar a predicados.
    \item Devuelven un tipo de dato.
    \item No tienen requiere ni asegura.
    \item No admite parámetros in, out, inout.
\end{itemize}

\leavevmode
\aux{sumar}{n: \ent, m: \ent}{\ent}{
    n + m
}

\aux{sumarTodos}{s: \TLista{\ent}}{\ent}{
    \sum_{i=0}^{\longitud{s}-1}{s[i]}
}


\subsection*{Aridad}
Decimos que una función es de aridad \(n\) cuando la función recibe \(n\) cantidad de parámetros.

\subsection*{Variables Ligadas y Libres}
Las variables son ligadas \(\iff\) están dentro de un cuantificador mientras que son libres cuando no lo están.
\begin{itemize}
    \item \((\forall i: \ent)(0 \le i < \longitud{s} \implicaLuego n \ge s[i])\) i es una variable ligada mientras que n y s son variables libres.
    \item \((\exists j: \ent)(0 \le j < \longitud{s} \yLuego n \ge s[i])\) j es una variable ligada mientras que n y s son variables libres.
    \item \((\forall i: \ent)(0 \le i < \longitud{s} \implicaLuego n \ge s[i]) \land P(i)\) Ojo acá. i es una variable ligada, pero la i que está fuera del cuantificador \(P(i)\) no está ligada. Esta última debería ser renombrada para no tener problemas y confusiones.
\end{itemize}

Cuando tenemos variables ligadas \textbf{no} podemos hacer nada sobre ellas, entre esas cosas, no podemos reemplazarlas porque no dependen de nosotros sino de los cuantificadores.

\subsection*{Cuantificadores anidados}
Anidamos cuantificadores cuando el rango de las variables es exactamente el mismo.
\begin{itemize}
    \item \((\forall i, j: \ent)(0 \le i, j < \longitud{s} \implicaLuego n \ge s[i][j]) \equiv (\forall i: \ent)((0 \le i < \longitud{s}\implicaLuego (\forall  j: \ent)(0 \le j < \longitud{s} \implicaLuego n \ge s[i][j]))) \) 
\end{itemize}

\subsection*{Estado}
Llamamos estado a los valores de las variables en un punto de ejecución específico. El estado de un programa es importante porque muta al asignar valores a las variables.
Cuando necesitamos hablar del estado de una variable en un instante específico, hablamos de \textbf{metavariables} \\ 

\subsection*{Metavariables}
Llamamos metavariable a una variable en un instante dado. Es útil cuando tenemos que predicar como cambio el valor de una variable con respecto al inicial. \\
Cuando tenemos que utilizar metavariables, sea S una variable cualquiera podemos referirnos al instante de tiempo de S como \(S_{t}\) donde t indica el momento. \\ \\ 
Notación \(S = S_{0}\)

\begin{proc}{multiplicarPorDosAImpares}{\Inout l: \TLista{\ent}}{}
    \requiere{l = l_{0}}
    \asegura{\longitud{l} = \longitud{l_{0}}}
    \asegura{(\forall i: \ent)(0 \le i < \longitud{s} \implicaLuego if(s_{0} [i] \ mod \ 2 \neq 0) \ then \ (s[i] = s_{0}[i] \ast 2) \ else \ (s[i] = s_{0}[i]) \ fi)}
\end{proc}
\leavevmode
\\
Nota: Cuando utilizamos metavariables tenemos que indicar que al modificar algo directamente, si no modificamos todo el conjunto de valores tenemos que indicar que los demás permanecen inalterados. En este caso, como estamos editando los valores, no tendría sentido que la lista salga con mayor longitud, es por eso que garantizamos que no cambia. 

Otra manera de resolver el ejemplo anterior es utilizando old(s)
\begin{proc}{multiplicarPorDosAImpares}{\Inout l: \TLista{\ent}}{}
    \asegura{\longitud{l} = \longitud{old(l)}}
    \asegura{(\forall i: \ent)(0 \le i < \longitud{s} \implicaLuego if(old(s)[i] \ mod \ 2 \neq 0) \ then \ (s[i] = old(s)[i] \ast 2) \ else \ (s[i] = old(s)[i]) \ fi)}
\end{proc}
\leavevmode
\\

\section*{Correctitud de un Programa}
Decimos que un programa S es correcto respecto a una especificación si se cumple la precondición P, el programa termina su ejecución y se cumple la postcondición Q.
\subsection*{Tripla de Hoare}
Notación para indicar que S es correcto respecto a la especificación (P, Q) \\ 
\[\{P\} \ S \ \{Q\}\]

\subsection*{SmallLang}
Es un lenguaje que nos permitirá poder validar la correctitud de un programa.
Solo tiene dos operaciones: 
\begin{itemize}
    \item x := E \(\equiv\) asignación
    \item skip \(\equiv\) no hace nada
\end{itemize}

Nota: E es una expresión cualquiera. Un valor, una función, cualquier cosa.

\subsection*{Estructuras de Control en SmallLang}
\begin{itemize}
    \item Secuencia de pasos: S1; S2 es un programa \(\iff\) S1 y S2 son dos programas.
    \item Condicionales: if B then S1 else S2 endif es un programa \(\iff\) B es una condición lógica (guarda) y S1 y S2 son programas.
    \item Ciclo: while B do S endwhile es un programa \(\iff\) B es una condición lógica y S un programa.
\end{itemize}

\subsection*{Validez de una tripla de Hoare}
\(\{x \ge 4\} \ x := x+1 \ \{x \ge 7\}\)
Donde, 
\begin{itemize}
    \item P = \(\{x \ge 4\}\)
    \item S = \(x := x+1\)
    \item Q = \(\{x \ge 7\}\)
\end{itemize}

¿Vale que \(\{P\} \ S \ \{Q\}\)?
Solo vale \(\iff x \ge 6\) por lo tanto, como la precondición P falla en los casos de x = 4, x = 5 podemos decir que la tripla de Hoare no es válida.\\

Esto que acabamos de hacer se llama demostrar la correctitud de un programa, y acabamos de demostrar que la precondición P para el programa S es demasiado débil pues no nos garantiza que llegaremos a Q cumpliendo P. \\

Existe una manera formal que nos permite conocer la precondición más débil de un algoritmo.
\newpage
\subsection*{Predicado def(E)}
Dada una expresión E, llamamos def(E) a las condiciones para que E esté definida. Todas las constantes están definidas, por lo tanto def(x) \(\equiv\) True. La idea es ir separando en términos e ir colocando las definiciones necesarias para esa operación específica.
\begin{itemize}
    \item \(def(x+1) \equiv def(x) \land def(1) \equiv True \land True \equiv True\)
    \item \(def(x/y) \equiv def(x) \land (def(y) \land y\neq0) \equiv True \land (True \land y>0) \equiv y\neq0\)
    \item \(def(\sqrt{x}) \equiv (def(x) \land x\ge0)\)
    \item \(def(a[i]+3) \equiv (def(a) \land def(i)) \yLuego 0 \le i<\longitud{a} \land def(3) \equiv (True \land True) \yLuego 0\le i<\longitud{a} \land True \equiv 0\le i<\longitud{a}\)
\end{itemize}

\subsection*{Predicado \(Q^{x}_{E}\)}
Cuando hablamos de este predicado hablamos de reemplazar las ocurrencias de x por E en el programa. Solo se reemplazan las ocurrencias libres, no las ligadas.
\subsection*{Axiomas}
\begin{itemize}
    \item Axioma 1: \(wp(x := E, Q) \equiv def(E) \yLuego Q^{x}_{E}\)
    \item Axioma 2: \(wp(skip, Q) \equiv Q\)
    \item Axioma 3: \(wp(S1; S2, Q) \equiv wp(S_{1}, wp(S_{2}, Q))\)
    \item Axioma 4: \(wp(S, Q) \equiv def(B) \yLuego ((B \land wp(S_{1}, Q)) \lor (\neg B \land wp(S_{2}, Q)))\)
\end{itemize} 

\subsection*{Axioma 1 con secuencias}
El axioma 1 nos sirve para asignar una expresión a una variable; Sin embargo, si tenemos que guardar algo en una secuencia debemos utilizar el setAt.
\begin{itemize}
    \item \(wp(b[i]:=E, Q) \\
    \equiv def(setAt(b, i, E)) \yLuego Q^{b[i]}_{setAt(b, i, E)} \\
    \equiv (def(b) \land def(i) \land def(E)) \yLuego 0\le i < \longitud{b} \yLuego Q^{b[i]}_{setAt(b, i, E)} \\
    \equiv 0\le i < \longitud{b} \yLuego Q^{b[i]}_{setAt(b, i, E)}   \\
    \equiv setAt(b, i, E)[j] = \{E \ si \ i = j, b[j] \ si \ i \neq j\}\)
\end{itemize}

Algunos ejemplos:\\
\(wp(s[i]:=s[i-1], Q) \\
wp(setAt(s, i, s[i-1]), Q) \equiv \\
def(setAt(s, i, s[i-1])) \equiv (def(s) \land def(i)) \yLuego 0 \le i < \longitud{s} \yLuego def(s[i-1]) \equiv \\ 0\le i < \longitud{s} \yLuego (def(s) \land def(i)) \yLuego 0\le i-1 < \longitud{s} \equiv  0\le i < \longitud{s} \yLuego 1\le i < \longitud{s} + 1 \equiv  \textcolor{blue}{1 \le i < \longitud{s}}
\)


TODO: Luego mostrar un ejercicio y aclarar que por cada condición se separan n cuantificadores.

\subsection*{Precondición más débil (Weakest Precondition)}
Es la precondición más débil que se necesita para poder ejecutar un algoritmo y satisfacer la postcondición Q. \\ \\
Notación: \(wp(S, Q)\) donde S es el programa y Q la postcondición. \\ \\
Teorema: Una tripla de Hoare \(\{P\} \ S \ \{Q\}\) es válida \(\iff P \implicaLuego wp(S, Q)\). \\ \\ 
Sea el siguiente enunciado, calcule la precondición más debil.
\begin{itemize}
    \item P = \(\{x \ge 4\}\)
    \item S = \(x := x+1\)
    \item Q = \(\{x \ge 5\}\)
\end{itemize} 
\(P \implicaLuego wp(S, Q) \equiv wp(x := x+1, x \ge 5) \equiv def(x+1) \yLuego Q^{x}_{x+1} \equiv def(x) \yLuego def(1) \yLuego x+1 \ge 5 \\ \equiv True \yLuego True \yLuego x \ge 4 \equiv x \ge 4\)

Luego, \(\{x \ge 4\} \implicaLuego \{x \ge 4\}\) es \(\True\)

Por lo tanto, \(wp(x:=x+1, x \ge 5) \equiv \{x \ge 4\}\)

Finalmente, probamos que para poder satisfacer Q la precondición más debil que cumple P es cuaqluier \(x \ge 4\). \\

Nota importante: Muchas veces puede ser que se nos solicite indicar que \(wp\) es incorrecta. Cuando se dice esto, significa que son precondiciones válidas pero hay algunas que no son la más débil.

\newpage 
\section*{Precondición más débil en ciclos}
Consideremos el siguiente ejemplo
\(\{???\} S \{x=0\}\)
donde S es el siguiente programa 

\begin{lstlisting}
     while(x>0) do
        x := x-1
    endwhile
 \end{lstlisting}

 Recordemos que esto es una tripla de Hoare, pero no podemos utilizar wp(S, Q) porque el programa es en base a ciclos. La precondición P más débil acá sería que x\(\ge\)0 porque para cumplir la postcondición Q me da igual si entra al ciclo o no.
 Eso tiene que quedar siempre claro, cuando estamos hablando en ciclos, si no entra al ciclo y satisface igual ya está.
 \subsection*{Predicado \(H_{k}\)}
 Definimos el predicado \(H_{k}\) para poder controlar la cantidad de iteraciones que hace un ciclo y poder calcular la precondición más débil.
 \begin{itemize}
    \item \(H_{0}(Q) \equiv def(B) \land \neg B \land Q\)
    \item \(H_{k+1}(Q) \equiv def(B) \land B \land wp(S, H_{k}(Q)) \ para \ k \ge 0\) 
\end{itemize} 
\subsection*{Axiomas}
Definimos el Axioma 5 para poder verificar la correctitud de ciclos que hacen una cantidad de iteraciones fijas como \\
\[wp(while \ B \ do \ S \ endwhile, Q) \equiv (\exists_{i\ge0})(H_{i}(Q))\]

¿Cual es el problema del Axioma 5 y el Predicado \(H_{k}\)? El problema es que ambos nos sirven para poder validar la precondición de un ciclo que sabemos que finaliza luego de \(n\) iteraciones.

\subsection*{Predicado \(I\) - Invariante}
Definimos el Invariante de un ciclo como un predicado que:
\begin{itemize}
    \item Demuestra que el ciclo realmente funciona y nos ayuda a demostrar la correctitud parcial "si termina el ciclo... entonces se cumple Q"
    \item Vale antes de entrar al ciclo y luego de salir del ciclo.
    \item En cada iteración, el invariante debe volver a ser válido. En el medio de la iteración puede que deje de valer.
    \item Un buen invariante incluye el rango de la(s) variable(s) de control del ciclo.
    \item Un buen invariante tiene alguna afirmación sobre el acumulador del ciclo.
\end{itemize} 

\subsection*{Teorema del Invariante}
Para poder probar que un ciclo es correcto, usamos el teorema del invariante.
\begin{itemize}
    \item \(P \equiv \) Las condiciones del requiere
    \item \(P_{c} \equiv\) Las precondiciones que necesita el ciclo para poder ingresar, muchas veces son las líneas que están por encima del while y el requiere (¡no todas las del requiere!)
    \item \(I \equiv \) Las condiciones que suceden antes y después de entrar al ciclo
    \item \(B \equiv \) La guarda del ciclo
    \item \(Q_{c} \equiv\) La postcondición del ciclo
  
\end{itemize} 
Luego, 
\begin{itemize}
    \item \(\ \{P\} \ S \ \{P_{c}\}\)
    \item \(\ P_{c} \implies I\)
    \item \(\{I \land B\} \ S \ \{I\}\)
    \item \(\{I \land \neg B\} \implies Q_{c}\)
\end{itemize} 
\textbf{Recordatorio}: Si aparece la S es que tenemos que calcular la wp porque es parte de la Tripla de Hoare. \\
\textbf{Recordatorio importante}: Para todo lo que es wp usamos SmallLang, es decir, cuando tenemos que validar la tripla de Hoare. En todos los demás casos usamos lógica. \\
Ej: No sería válido tener un if en un invariante.
\subsection*{Teorema de Terminación de Ciclo}
Utilizamos el teorema de terminación de ciclo para garantizar que cumpliendo la precondición de un ciclo, el programa siempre termina.
Para poder probar esto, necesito una función variante \(f_{v}\). \\
Llamamos función variante \(f_{v}\) a una función que es siempre estrictamente decreciente y representa una cantidad que se va reduciendo a lo largo de las iteraciones.
La función \(f_{v}\) debe garantizar
\begin{itemize}
    \item \(\{I \land B \land v_{0} = f_{v}\} \ S \ \{f_{v} < v_{0}\}\)
    \item \(\{I  \land f_{v} \le 0 \implies \neg B\}\)
   
\end{itemize}
\subsection*{Reglas generales para validar correctitud de ciclo y terminación}
\begin{itemize}
    \item Cuando tenemos que iterar sobre listas, tendremos un índice i que irá hasta incluida la longitud (pues nos sirve) para negar la guarda, mientras que el j será para usar dentro del ciclo. 
    \((0\le i \le \longitud{s} \yLuego (0 \le j < i \implicaLuego res = \sum_{j=0}^{i}{s[j]}))\)
    \item Si tengo algo en \(I\) deberá estar en \(P_{c}\) y/o \(Q_{c}\). Esto es porque cuando tengamos que hacer las implicancias, deberíamos comparar de ambos lados y si el invariante tiene algo que los demás no, es siempre falso. 
    \item Si tengo algo en \(P_{c}\) o \(Q_{c}\) no necesariamente tiene que estar en \(I\)
    \item En \(Q_{c}\) se acostumbra a colocar que \(i = \longitud{s}\) porque nos ayuda a demostrar la terminación del ciclo.
    \item En la función variante: i va negada si i crece en el ciclo; i va positivo si i decrece en el ciclo.
    \item En \(Q_{c}\) rara vez tenemos que hablar de rangos de variables.
\end{itemize} 

\section*{TADs (Tipos Abstractos de Datos)}
Es un tipo de datos porque define un conjunto de valores y las operaciones que se pueden realizar sobre ellos. Es abstracto ya que para utilizarlos no necesitamos saber como está implementado.
Describe el qué y no el cómo.
Son una forma de modularizar a nivel de los datos.  \\ \\
Importante: En todo enunciado ambiguo, queda en nosotros interpretarlo y eliminar esas ambiguedades decidiendo como lo vamos a considerar.\\ \\
Ej: En varios ejercicios te piden que un punto deba cambiarse el centro y hay dos maneras de plantearlo
\begin{itemize}
    \item Agarrar el centro que vienen por parámetro y sumar coordenada a coordenada con respecto a las de la instancia de mi TAD. 
    \item Agarrar el centro que viene por parámetro y considerarlo como el centro final en la instancia del TAD.
\end{itemize}
Importante: En un TAD podemos usar todos los mismos tipos de datos de especificación y sus funciones correspondientes.

\subsection*{Observadores}
Los observadores son una especie de atributo en un objeto en POO.
Nos permiten saber qué valores tienen y en qué momento.
\begin{itemize}
    \item Sirven para describir el estado de una instancia de un TAD y nos permiten consultar su estado virtual.
    \item Tenemos que poder observar todas las características que nos interesan de las instancias.
    \item En un instante de tiempo, el estado de una instancia del TAD estará dado por el estado de todos sus observadores (como un debugger).
    \item Nos permiten distinguir si dos instancias son distintas.
    \item Todas las operaciones tienen que poder ser descriptas a partir de los observadores.
\end{itemize} 
Ejemplo de un TAD con observadores de tipo dato:
\begin{lstlisting}
    TAD lista {
        obs elems: conj<T>
        obs cantElems: int
    }
\end{lstlisting}

Los observadores también pueden ser funciones auxiliares.
\begin{itemize}
    \item Son las auxiliares de nuestro lenguaje de especificación 
    \item No pueden tener efectos colaterales ni modificar los parámetros
    \item Pueden usar tipos de nuestro lenguaje de especificación 
\end{itemize} 
Ejemplo de un TAD con observadores de tipo dato:
\begin{lstlisting}
    TAD lista {
        obs elems: conj<T>
        obs estaElem(e: T): bool
    }
\end{lstlisting}

\subsection*{Igualdad Observacional}
Decimos que dos TADs son iguales \(\iff\) todos sus observadores son iguales.\\
Muchas veces no nos basta con la igualdad por defecto con los observadores, y tenemos que declarar nuestra propia igualdad observacional.

\subsection*{Operaciones de un TAD}
Las operaciones de un TAD deben estar especificadas y nos indican qué se puede hacer con una instancia.
Antes y una vez aplicada una operación tenemos que hablar del estado en el que quedó el TAD con respecto a sus observadores.
\section*{Diseño de un TAD}
Es una estructura de datos y una serie de algoritmos que nos indica cómo se representa y cómo se codifica alguna implementación del TAD.
\begin{itemize}
    \item Debemos elegir la estructura de representación con tipos de datos.
    \item Tendremos que escribir algoritmos para todas las operaciones.
    \item Los algoritmos deben respetar la especificación del TAD. Es decir, cada procedimiento que hagamos debemos conocer los requiere y cumplir los asegura.
\end{itemize}
Nota: como hay diversas maneras de implementar un TAD, cada una puede diferir en complejidad espacial, tiempo, o sencillez de lectura / mantenibilidad.
\subsection*{Módulos}
\begin{itemize}
    \item Son la representación / implementación física en código de un TAD.
    \item Los módulos implementan el TAD.
    \item Un procedimiento de un módulo puede llamar a otros procedimientos del módulo.
\end{itemize}
\subsection*{Variables de Estado}
Lo que en los TADs eran observadores, acá son variables de estado. Serán manipuladas por las operaciones mediante el código de los algoritmos. 
Tipos válidos para variables de estado: 
\begin{itemize}
    \item int, real, bool, char, string
    \item tupla\(<\)T1, T2, T3\(>\), struct\(<\)campo1: val1, campo2: val2\(>\)
    \item Array\(<\)T\(>\) (arrays de tamaño fijo)
    \item No es posible usar tipos de especificación como conj\(<\)T\(>\) o seq\(<\)T\(>\)
\end{itemize}
El módulo puede tener variables de estado que no hagan referencia a ningún observador de un TAD, por ejemplo: guardar un máximo en un módulo aunque el TAD no lo pida. A veces estas cosas se hacen solo por temas de a la hora de implementarlo en un lenguaje de programación. \\ 
\textbf{Nota: Una variable de estado también puede contener otro módulo.}
\subsection*{Invariante de Representación}
\begin{itemize}
    \item Es un predicado.
    \item Nos indica qué conjuntos de valores son instancias válidas de la implementación de un TAD.
    \item Es equivalente al invariante en ciclos, pero acá aplicado a TAD's
    \item Este es inicializado en el constructor una vez realizada la instancia
    \item Es invariante pues vale siempre antes de llamar a los métodos y luego de cada método. 
    \begin{itemize}
        \item Siempre y cuando tenemos un parámetro inout, tenemos que ver que los cambios que hagamos hagan seguir valiendo al invrep.
    \end{itemize}
    \item Todos los métodos pueden asumir que el invariante de representación siempre vale al ser llamados.
    \item El parámetro que recibe el predicado de InvRep es una instancia del módulo. Esto nos sirve para poder utilizar sus variables de estado y colocarles las restricciones.
\end{itemize}
Para cualquier operación del módulo se debe de verificar la siguiente tripla de Hoare: $ \{InvRep(p')\} \ Operacion(p', ..) \ \{InvRep(p')\}$ \\ \\
Tips varios: 
\begin{itemize}
    \item ¡Prestar atencion a las verificaciones bidireccionales! En el sentido de que si tengo \(dict<Alarma, Conj<Sensores>>\) y \(dict<Sensor, Conj<Alarmas>>\) si en \(dict<Alarma, ...>\) tengo varios sensores, esos sensores estan en Sensor y ademas, si busco en las alarmas de cada sensor deberia estar la \(dict<Alarma, ...>\)
    \item Cuando tengo un diccionario tengo que usar un cuantificador para hablar y tengo que acceder y hablar si o si por la key.
\end{itemize}
\subsection*{Función de Abstracción}
Dado el TAD y la implementación (módulo) podemos relacionarlos a ambos utilizando la función (predicado) de abstracción. Dada una instancia del módulo podemos ver a qué instancia del TAD corresponde y/o representa vinculando las variables de estado del módulo con los observadores del TAD.
\begin{itemize}
    \item Es un predicado.
    \item A la hora de definirlo, podemos asumir que vale el invrep. Es decir, no hace falta volver a mencionar cosas que ya están explícitos en el invrep.
    \item Toma como parámetro una instancia del módulo y una instancia del TAD.
    \item Hacemos referencia a observadores y a otros predicados, no procs
    \item Todos los observadores del TAD deben tener un vinculo con una variable de estado pero no necesariamente al revés
    \item Para poder escribir, usamos lenguaje de especificación como lo conocemos. Podemos usar por ejemplo $|a.data|$ o a.data.length da igual, pero hay que ser consistentes
    \item Rara vez se colocan rangos acá, casi nunca, excepto cuando hay alguna variable de estado y observadora que hablan de capacidades.
\end{itemize}
Es importante considerar que todo lo que está en el invariante de representación ya está implícito en la función de abstracción. \\
Ej: Tenemos un módulo que tiene ventas, mayorProductoVentas, y mayorPrecio pero el TAD solo tiene ventas. En este caso, en el invariante de representación hablamos de mayorProductoVentas y mayorPrecio haciendo las relaciones con ventas (en temas de key del producto) pero en el predicado de astracción NO hablás de mayorProductoVentas y mayorPrecio primero porque no son observadores del TAD pero tampoco hay que garantizar nada porque ya está implicado por el invariante de representación

\subsection*{Operaciones de un Módulo}
Como un módulo implementa un TAD, todas sus operaciones deben estar implementados en código.
Para escribir las implementaciones de los procs usamos SmallLang.
\begin{itemize}
    \item Declaración de variables: 
    \begin{itemize}
        \item var x: int
        \item var c: ConjuntoArr$<int>$
    \end{itemize}
    \item Asignación: x := valor
    \item Condicional: if condicion then codigo else codigo endif
    \item Ciclo: while condicion do codigo endwhile
    \item Llamar a un proc:
    \begin{itemize}
        \item c.vacio()
        \item b : = c.vacio();
    \end{itemize}
\end{itemize}
\subsection*{Memoria dinámica}
Los tipos complejos son usados siempre por referencia. El valor indefinido es identificado por la palabra null. Acceder a algo null explota. \\
Las variables de tipos complejos deben ser inicializadas mediante el operador new.
Tipos nativos: 
\begin{lstlisting}
   var a: Array<int>
   var b: int
   if a == null then 
   ...codigo
   endif
   a := new Array<int>(10)
   b := a[0]
\end{lstlisting}
Tipos de otros módulos: 
\begin{lstlisting}
    var a: ConjArr<int>
    a := new ConjArr(10) //longitud 10
\end{lstlisting}
Pasaje por referencia:
\begin{lstlisting}
    var a: ConjArr<int>
    var b: ConjArr<int>
    a := new ConjArr(10); //longitud 10
    b := a
\end{lstlisting}
Nota: El pasaje por referencia, a veces se le conoce comúnmente como aliasing y para evitarlo, hay que crear una nueva instancia con los valores de la otra instancia en vez de asignarla directamente.

\subsection*{Aliasing en procedimientos de Módulo}
Siempre hay que recordar que el módulo es lo más cercano a código que tenemos. Por lo tanto, en operaciones como concatenar, copiar, o quizá mover de un lado al otro para luego borrarlo hay que recordar el aliasing. \\
Porque por ejemplo, si tengo que mover cierta data hacia un lado y luego borrarla de de donde estaba, si la moví por referencia y después la borré, perdí todo. 

\subsection*{Contrato entre métodos de un módulo}
Los métodos de un Módulo tienen un contrato entre sí.
Supongamos que necesitamos que la complejidad de búsqueda de un método de mi módulo sea o(log n) sabiendo que mi lista está ordenada. Aquí, el método busqueda podrá usar la búsqueda binaria para poder hacer el proceso lo más rápido posible, pero ¿qué sucede si al agregar un elemento en el método agregar() la lista de salida que se modifica en el módulo no está ordenada? \\ El contrato de búsqueda no se cumpliría porque la búsqueda binaria no funcionaría porque necesita que la lista esté ordenada. \\

En este caso, que la lista esté ordenada debería ser una condición del invariante de representación para evitar estos problemas. \\

Este módulo es bueno para la búsqueda de un elemento pero el agregar un elemento es mucho más costoso por el tema de reordenar la lista nuevamente. \\

\textbf{Mirada al futuro}: Los métodos deben cumplir una complejidad algorítimica dada. \\
Véase \hyperref[subsec:anexo_invrep_abs]{\underline{anexo}} para ejercicios de invariante de representación y función de abstracción
\section*{Estructuras de Datos}
\subsection*{Colección}
Representa un grupo de objetos. Provee de una arquitectura para su almacenamiento y manipulación.
\begin{itemize}
    \item Secuencia
    \item Conjunto
    \item Multiconjunto
    \item Diccionario
\end{itemize}
¿Por qué una tupla no es parte del grupo? Porque la tupla es fija, una vez definida e inicializada su longitud no cambia.
\subsection*{Tipos paramétricos}
Son variables de tipo, es decir, variables con tipo genérico.
La manera más común de indicar un genérico son T, K o V.  \\
Hay que tener cuidado con las operaciones que se realizan con las variables genéricas porque algunos operadores nos restringuen su uso a ciertos tipos. \\
Ej: No puedo utilizar X - Y si X, Y son genéricos y nos envían X, Y como char.
\subsection*{Iteradores}
Nos permiten recorrer colecciones de una manera abstracta sin saber su estructura. \\
Un buen iterador se distingue de otro iterador por la velocidad de iterar la estructura. \\
Operaciones con iteradores:
\begin{itemize}
    \item ¿Estoy sobre un elemento? 
    \item Obtener el elemento actual
    \item Avanzar al siguiente elemento
    \item Retroceder al elemento anterior (sii es bidireccional)
\end{itemize}
Los Iteradores son una clase privada que van dentro de la clase que queremos que se instancie y se pueda recorrer. \\
Es privada porque no queremos que sea instanciada más que por la instancia de la clase que queremos recorrer. \\
Los Iteradores no van hasta n, van hasta n+1.
\begin{figure}[h]
    \includegraphics[]{assets/iterador.png}
\end{figure}
\begin{lstlisting}
    public class Vector<T> implements List<T>{
        private T[] elementos;
        private int size;
        
        private class Iterador implements Iterator<T>{
            int indice;
            
            Iterador(){
                indice = 0;
            }
            public boolean hasNext(){
                return indice != size;
            }
            public T next(){
                int i = indice;
                indice = indice + 1;
                return elementos[i];
            }
        }

        public Iterator<T> iterator(){
            return new Iterador();
        }
    }

    Iterator it = vector.iterator();
    while(it.hasNext()){
        System.out.println(it.next());
    }
\end{lstlisting}

\subsection*{Singly Linked Lists - Listas simplemente enlazadas}
Es una estructura que sirve para representar una secuencia de elementos donde cada elemento es un Nodo que tiene un valor y una referencia al siguiente. \\ 
Nota: Si el Nodo actual es el último de la Singly Linked List lo notamos porque el ultimo.siguiente = null.
El Nodo debe ser responsable de guardar al siguiente porque caso contrario, no existirá otra referencia al siguiente Nodo.
Ventajas de las Singly Linked Lists:
\begin{itemize}
    \item Mas fino uso de la memoria.
    \item Insertamos fácilmente al principio y al final.
    \item El costo de insertar al final es o(n) pues debemos recorrer todos los nodos para insertar uno nuevo. Es por eso que es común guardar el último nodo almacenado en la clase.
    \item Eficiente para reacomodar elementos.
    \item Es malo en rendimiento o(n) si necesito buscar un elemento en específico. Es decir, perdemos el acceso aleatorio a los elementos.
\end{itemize}
\subsection*{Double Linked Lists - Listas doblemente enlazadas}
Exactamente igual que la Singly Linked Lists pero acá los Nodos tienen almacenado: Referencia al nodo previo, valor y referencia al nodo siguiente. \\ 
Nota: Si el Nodo actual es el último de la Double Linked List lo notamos porque el ultimo.siguiente = null.
\begin{lstlisting}
    public class DoubleLinkedList<T> {
        private Nodo primero;
        private int longitud; 

        private class Nodo {
            Nodo prev;
            Nodo sig;
            T valor; 

            public Nodo(T val){
                this.val = val; 
            }
        }

        public DoubleLinkedList(){
            this.longitud = 0; 
        }
    }
\end{lstlisting}
\subsection*{Listas vs Linked Lists}
Ambas son bastante rápidas a la hora de iterar sobre ellas, sin embargo: 
\begin{itemize}
    \item Las listas nos permiten acceder rápidamente a un elemento mientras que las Linked Lists no.
    \item Las Linked Lists nos permiten agregar elementos rápidamente al inicio (O(1)) y no necesitamos reacomodar nada más que decir que el anterior primero ahora es el segundo mientras que en la lista tenemos que reacomodar todos los elementos como antes pero colocar el nuevo al principio (O(n))
\end{itemize}

\section*{Complejidad Algorítmica}
\subsection*{Analisis de la Complejidad de Algoritmos}
Nos permite elegir entre distintos algoritmos para resolver el mismo problema o distintas formas de implementar un TAD.
Esto es importante porque nos permite optimizar:
\begin{itemize}
    \item Tiempo de ejecución
    \item Espacio (memoria)
    \item Cantidad de procesadores (en caso de algoritmos paralelos)
    \item Utilización de la red de comunicaciones (para algoritmos paralelos)
\end{itemize}

El análisis se puede hacer de forma experimental o teórica \\

\textbf{Ventajas del enfoque teórico}:
\begin{itemize}
    \item Se hace antes de escribir código
    \item Vale para todas las instancias del problema (no en un caso específico)
    \item Es independiente del lenguaje de programación
    \item Es independiente de la máquina donde se ejecuta (el tiempo no varía)
    \item Es independiente del programador
\end{itemize}

\subsection*{Análisis Teórico}
\begin{itemize}
    \item Se realiza en función del tamaño del input 
    \item Para distintos tipos de input 
    \item Análisis asintótico
\end{itemize}

\subsection*{Operaciones Elementales}
T(l) será una función que mida el número de operaciones elementales requeridas para la instancia l.
Las operaciones elementales (OE) serán aquellas que el procesador realiza en tiempo acotado por una constante (no depende del tamaño de la entrada).
Ej: x = 0, if(x = 2).
Es decir, podemos generalizar las operaciones elementales a:
\begin{itemize}
    \item Operaciones aritméticas básicas (suma, resta, división, multiplicación)
    \item Comparaciones y/o operaciones lógicas
    \item Acceder a elemento de array
    \item Asignaciones a variables de tipos básicos (las inicializaciones no consumen tiempo)
\end{itemize}
\subsection*{Cálculo de Operaciones Elementales}
\begin{itemize}
    \item T(If C Then S1 Else S2 Endif;) = T(C) + max\{t(S1), t(S2)\}
    \item T(Case C Of v1:S1 \(|\) v2:S2 \(|\) ... \(|\) vn:Sn End;) = T(C) + max\{t(S1), t(S2), ..., T(Sn)\}
    \item T(While C Do S End;) = T(c) + (nº iteraciones) * (T(S) + T(C))
    \item T(MiFuncion(P1, P2, ..., Pn)) = 1 + T(P1) + T(P2) + ... + T(Pn)
\end{itemize}
\subsection*{Tamaño de la entrada}
\begin{itemize}
    \item T(n): complejidad temporal (o en tiempo) para una entrada de tamaño n
    \item S(n): complejidad espacial para una entrada de tamaño n
\end{itemize}
\textbf{Importante}: NUNCA hay que restringir la longitud de entrada de una lista; Por ejemplo: no tiene decir que el mejor caso sea que la lista esté vacía, porque la complejidad se da en base a listas de longitud n sin ningún tipo de restricción. Por lo tanto, si algo está acotado en una longitud fija, es siempre complejidad O(1). \\
Véase \hyperref[subsec:ejemplos_complejidad_reales]{\underline{casos de uso}} reales en Complejidad Algorítmica.
\subsection*{Análisis de los casos}
\begin{itemize}
    \item T\(_{mejor}(n)\) = min\(_{instancias \ l},\ _{\longitud{l} \ = \ n}\ \) \{t(l)\}. Recorriendo una lista, el mejor caso es que esté en primera posición.
    \item T\(_{peor}(n)\) = max\(_{instancias \ l},\ _{\longitud{l} \ = \ n}\ \) \{t(l)\}. Recorriendo una lista, el peor caso es que el elemento no esté.
    \item T\(_{prom}(n)\) = No lo vamos a usar pero, es algo más parecido a estadística.
\end{itemize}
Cuando el tamaño de datos es grande, los costos de los diferentes algoritmos pueden variar de manera significativa. En tamaño de datos chico, no nos interesa el tiempo de ejecución.
\subsection*{Principio de Invarianza}
Si dos algoritmos solo varían en una constante, entonces no nos importa porque la complejidad es la misma.
\[T_{1}(n) \le cT_{2}(n)\]
c: constante real  \(c>0\) \\
\(n_{0} \in N\) tales que \(\forall n \ge n_{0}\)
\subsection*{Comportamiento Asintótico}
Comportamiento para los valores de la entrada suficientemente grandes. \\
Nota: Las funciones f y g dependen de un n. No existen funciones constantes menores que O(1).
\subsection*{O (cota superior)}
\[ f (n) \in O(g(n)) \iff \exists c \in R>0, n_{0} \in N \ tal \ que \
\forall n \ge n_{0} : f(n) \le c \ast g(n) \]
La notación f \(\in\) O(g) expresa que la función f no crece más rápido que alguna función proporcional a g. f está acotada superiormente por g. \\
\begin{itemize}
    \item \(n \ast log(n) \in O(n^{2})\)
    \item \(n \in O(n)\)
    \item \(n^{2} \notin O(n)\)
\end{itemize}
\[\begin{minipage}[b]{1\textwidth}
    \includegraphics[width=\linewidth]{assets/notacion_o.jpg}
\end{minipage}\]
Nota: Si para un algoritmo sabemos que $T_{peor} \in O(g)$ se puede asegurar que para inputs de tamaño creciente, en todos los casos el tiempo será a lo sumo proporcional a la cota.
\subsection*{\(\Omega\) (cota inferior)}
\[ f (n) \in \Omega(g(n)) \iff \exists c \in R>0, n_{0} \in N \ tal \ que \
\forall n \ge n_{0} : f(n) \ge c \ast g(n) \]
La notación f \(\in \Omega(g)\) expresa que la función f crece al menos como g. f está acotada inferiormente por g.
\begin{itemize}
    \item \(n/2 \in \Omega(n)\)
    \item \(n^{k} \in \Omega(n)\) 
    \item \(log(n) \notin \Omega(n)\) 
\end{itemize}
\[\begin{minipage}[b]{1\textwidth}
    \includegraphics[width=\linewidth]{assets/notacion_omega.jpg}
\end{minipage}\]
Nota: Si para un algoritmo sabemos que $T_{peor} \in \Omega(g)$ se puede asegurar que para inputs de tamaño creciente, el tiempo será en el pero caso al menos proporcional a la cota.
\subsection*{\(\theta\) (orden exacto)}
\[f (n) \in \theta(g(n)) \iff f (n) \in O(g(n)) \ y \ f (n) \in \Omega(g(n)).\ Es \ decir, \ \theta(g(n)) = O(g(n)) \cap \Omega(g(n))\]
Básicamente: Tiene que valer en O y en \(\Omega\), no debe pasarse de \(\Omega\) pero tampoco estar por debajo de O.
\[\begin{minipage}[b]{1\textwidth}
    \includegraphics[width=\linewidth]{assets/notacion_theta.jpg}
\end{minipage}\]
\subsection*{Definición parecida a inducción corrida en Complejidad}
Tanto en la definición de \(O, \ \Omega \ y \ \theta\) se nombra para un \(n > n_{0}\). Esto es porque no todas las funciones cumplirán la definición, sino aquellas que son mayores a \(n_{0}\). Es por eso que en las imágenes se ven como inicialmente no cumple, pero a partir de un \(x_{0} \ (n_{0})\) vale para todo n.
\subsection*{Propiedades}
\(\star\) es comodín de O, $\Omega$, $\Theta$
\begin{itemize}
    \item Suma: \(\star(f) + \star(g) = \star(f+g) = \star(max\{f,g\})\)
    \item Producto: \(\star(f) \ast \star(g) = \star(f \ast g)\)
    \item Reflexividad: \(f \in \star(f)\)
    \item Simetría: Solo vale en \(\theta\) = \(f \in \theta(g) \implies g \in \theta(f)\)
    \item Transitividad: \(f \in \star(g) \land g \in \star(h) \implies f \in \star(h)\)
    \item Inclusión: \(f \in \star(g) \implies \star(f) \subseteq \star(g) \)
    \item Igualdad: \(\star(f) = \star(g) \iff f \in \star(g) \land g \in \star(f)\)
    \item Constantes: \(f \in \star(g) \implies k \ast f \in \star(g)\) k cte.
\end{itemize}
Véase \hyperref[subsec:complejidad_propiedades]{anexo} para ejercicios aplicando propiedades.
\subsection*{Intuición de Análisis de Complejidad posibles}
\begin{itemize}
    \item Mejor caso != Peor caso (cuando el ciclo corta antes)
    \item Mejor caso = Peor caso (cuando el ciclo no tiene condición de corte)
    \item Cuando tengo ramas if else, la complejidad mayor se dará por la rama que tenga mayor cantidad de operaciones en cuanto a ciclos.
    \item Cuando tenga guardas como por ejemplo, while $b>0$ y la variable se va dividiendo entre dos, la complejidad será algo parecida a log n.
    \item Cuando una función recibe dos parámetros, pero uno de ellos no tiene un rol fundamental en algún ciclo o guarda, entonces raramente esté en el cálculo final de la complejidad.
    \item Recordar que es normal ver casos donde se aplique la sumatoria de gauss o tengamos que masajear la expresión para que aparezca.
    \item Si la guarda del ciclo se incrementa de manera: $i*2$ o $i/2$ entonces la complejidad del ciclo será logarítmica.
    \item Para poder calcular la complejidad, si tenemos una suma basta con quedarnos con el término más grande. (ej: n + m tiene 2 casos)
\end{itemize}

\subsection*{Cota Ajustada}
Usamos \(\theta\) para indicar cotas ajustadas al momento de tener que calcular el peor y el mejor caso.
\subsection*{Complejidad Algorítmica en Polinomios}
Usamos límites para estos casos \\

Sean f, g: \(\mathds{N} \implies \float_{>0}\). Si existe:
\[ \lim_{n\to\infty} f(x)/g(n) = l \in \float_{\ge 0} \cup \{ +\infty \} \]
\begin{itemize}
    \item \(f \in \theta(g) \iff 0<l<+\infty\)
    \item \(f \in O(g) \ y \ f \notin \Omega(g) \iff l = 0\)
    \item \(f \in \Omega(g) \ y \ f \notin O(g) \iff l = +\infty\)
\end{itemize}
\section*{Complejidad en procedimientos de módulo}
Se calculan igual que observando una función dada que hace algo. Lo único que quería aclarar acá, es que siempre para las eliminaciones o búsquedas nunca se usen (en caso de haber) punteros que tengan referencia al último valor. El caso excepcional es el primero, pero el último hay que buscarlo con la forma de recorrer la estructura tradicional que haya. \\
Véase \hyperref[subsec:complejidad_modulo_sll]{anexo} para ver un ejemplo al respecto.
\section*{Árboles / Árboles binarios}
Se definen recursivamente y sus operaciones necesitan de ella. Utilizamos nodos. \\
Terminología que vamos a usar: Raíz \& Hoja \\ 
Para poder obtener un elemento de un árbol se debe empezar por la raíz y recorrer cada una de las hojas recursivamente. \\ \\
OBS: Las hojas pueden tener o no nodos hijos; si tienen hijos entonces también son árboles.  \\ 
\textbf{Árboles binarios}
Son aquellos en los cuales cada nodo tiene máximo 2 elementos.
\subsection*{Árboles binarios de búsqueda (ABB)}
Para todo nodo, los valores del subárbol izquierdo son menores que el valor del nodo y los valores del subárbol derecho son mayores. \\ 
\begin{minipage}[b]{0.8\textwidth}
    \includegraphics[width=\linewidth]{assets/abb-1.jpg}
    \centering
    \label{fig:abb-1}
\end{minipage} \\ 
Nótese que de ninguna rama derecha puede haber un número mayor a la raíz; de ninguna rama izquierda puede haber un número menor a la raíz. \\ 
La complejidad de búsqueda en el peor caso es de $O(log n)$
Algoritmos comúnes en árboles binarios de búsqueda:
\begin{itemize}
    \item Arbol vacío: Aquel que tiene la raíz en null
    \item Búsqueda de elemento: Si el nodo es null o el elem es igual al valor del nodo devuelvo n. Caso contrario, si el valor a buscar es menor al dato del nodo entonces busco más a la izquierda, caso contrario busco a la derecha. Cuando busca, habla de llamar a la misma función recursivamente. Complejidad O(n) con n la altura del árbol porque pasa solo una vez por cada nodo.
    \item Insertar elemento: Primero agarro la raiz del árbol, si la raiz es null entonces no hago nada. Si el árbol no tiene una raíz, entonces mi elem es la raíz; Si ya tiene una raíz me fijo si el elem a insertar es menor o mayor a la raíz, si es mayor entonces voy al primer hijo derecho de la raíz (no entiendo la parte final) dice algo como si el elem<prev.dato then padre.izq = newnodo osea tiene sentido pero en el pseudocodigo prev no existe enn ningun lado definido. Complejidad O(n) para agregar, aunque si hay distribución uniforme de las claves O(log n)
    \item Eliminar elemento: hay 3 casos. Sea u una variable cualquiera
    \begin{itemize}
        \item u es una hoja: Si u es una hoja significa que no tiene hijos, por lo tanto lo puedo eliminar sin necesidad de reordenar nada.
        \item u tiene un solo hijo: Si u es una hoja con un solo hijo (a la izq o a la derecha) basta con mover el hijo a la posición del nodo a eliminar.
        \item u tiene dos hijos: Si u es un nodo con dos hijos hay que encontrar al predecesor inmediato (v) de u. \textbf{v no puede tener dos hijos, en caso contrario no es predecesor inmediato}, una vez encontrado copiar la clave de v en lugar de la de u, borrar el nodo v (acá hay que revisar qué sucede si tiene un hijo, iría al caso 2, caso contrario caso 1). Lo mismo se puede hacer con el sucesor inmediato (mismas reglas que predecesor inmediato). 
        \item Complejidad O(n) para cualquier tipo de borrado.
    \end{itemize}
\end{itemize}
\textbf{Aclaración}: Predecesor inmediato (el más grande de los chiquitos), osea rama izquierda busco el último de la der a partir del nodo que estoy. \\ 
\textbf{Aclaración}: Sucesor inmediato (el más chiquito de los grandes), osea rama derecha busco el último a la izquierda a partir del nodo que estoy. \\
\subsection*{ABB con complejidad O(n) en ciertas operaciones}
Árbol binario con n nodos anidados todos mayores o todos menores.
\begin{center}
    \begin{minipage}[b]{0.7\textwidth}
        \includegraphics[width=\linewidth]{assets/peor_caso_abb.jpg}
        \centering
        \label{fig:peor_caso_abb}
    \end{minipage}
\end{center}
¿Cuál es el problema de los ABB? que al hacer inserciones, eliminaciones o ver si un elemento dado pertenece al árbol, el costo en el peor caso es O(n). \\ 
Para optimizar esto, existen los AVL que nos ponen restricciones en base a la cantidad de nodos que puede haber anidados en base ciertas reglas de balanceo.
\subsection*{ABB balanceados (AVL)}
Un árbol AVL es un ABB balanceado en altura. Un árbol binario perfectamente balanceado de n nodos tiene una altura de: $ log_{2}(n) + 1 $ donde las hojas son más del 50\% de los nodos  \\
La inserción y el borrado se hace exactamente igual que en un ABB pero acá, como extra se hace el rebalanceo. \\ 
Se define el factor de balanceo de un nodo v de un árbol binario como: \\
\[fb(v) = A_{D} - A_{I}\] donde $ A_{x}$ es la altura del subárbol x \\
Existen 3 posibles factores de balanceo para cada nodo: 
\begin{itemize}
    \item -1: La cantidad de ramas de la izquierda del nodo son más que la rama derecha.
    \item 0: La cantidad de ramas a la izquierda o derecha del nodo son la misma cantidad.
    \item 1: La cantidad de ramas de la derecha del nodo son más que la rama izquierda.
\end{itemize}
Llamamos entonces, árbol balanceado para cuando para cualquier nodo en él, la diferencia de longitud entre sus ramas izquierda y derecha difiere, a lo sumo, en una unidad. \\ 
\textbf{Nota: los caminos no nos importan mucho, considerar cada nodo como un árbol distinto. Si los tengo en misma altura pero uno está más abajo que otro, está desbalanceado. }
\begin{center}
    \begin{minipage}[b]{0.5\textwidth}
        \includegraphics[width=\linewidth]{assets/avl.png}
        \centering
        \label{fig:avl}
    \end{minipage}
\end{center}
\begin{itemize}
    \item Negro: Factor de balanceo 0.
    \item Rojo: Factor de balanceo -1.
    \item Azul: Factor de balanceo 1.
\end{itemize}
\subsection*{Mantener balanceo de AVL al insertar o eliminar}
Una de las dificultades más grandes de mantener el AVL invariante luego de cada operación es mantenerlo balanceado. \\
Viendo la figura de la izquierda: es un AVL porque si vemos, la rama de la izquierda del 10 son 2 nodos y la derecha 1 y difieren en un solo nodo, por lo tanto está balanceado. 
\begin{center}
    \begin{minipage}[b]{0.7\textwidth}
        \includegraphics[width=\linewidth]{assets/avl_problematica.png}
        \centering
        \label{fig:avl_problematica}
    \end{minipage}
\end{center}
Viendo la figura de la derecha, no está balanceado: porque la rama de la izquierda del 10 son 3 nodos (altura 3) y la derecha 1 (altura 1), y difieren en 2 nodos, por lo tanto no está balanceado. \\
¿Cómo solucionamos esto para mantener el invariante? Rotaciones
\newpage
\subsection*{Rotaciones}
Existen muchas rotaciones posibles para un árbol, pero las elegimos dependiendo de la estructura del árbol que tengamos que rebalancear. \\
Es importante que cada vez que hacemos una rotación, el invariante debe seguir valiendo. \\
\begin{center}
    \begin{minipage}[b]{0.7\textwidth}
        \includegraphics[width=\linewidth]{assets/avl_rotaciones.png}
        \centering
        \label{fig:avl_rotaciones}
    \end{minipage}
\end{center}
Nótese que al rotar el árbol, sigue valiendo el invariante que $ A < x < B < y < C $, esto nos indica que al rotar conseguimos el mismo árbol. \\ \\ 
\textbf{¿Qué rotación tengo que usar?}
\begin{itemize}
    \item Left-Left(LL o II): Ocurre cuando un nodo tiene un subárbol izquierdo que está desbalanceado a la izquierda. La solución es una rotación simple a la derecha. Véase \hyperref[subsec:rotaciones_avl]{anexo}
    \item Right-Right(RR o DD): Ocurre cuando un nodo tiene un subárbol derecho que está desbalanceado a la derecha. La solución es una rotación simple a la izquierda. Véase \hyperref[subsec:rotaciones_avl]{anexo}
    \item Left-Right(LR o ID): Ocurre cuando un nodo tiene un subárbol izquierdo que está desbalanceado a la derecha. La solución son dos rotaciones: primero una rotación a la izquierda en el subárbol izquierdo y luego una rotación a la derecha en el nodo. Véase \hyperref[subsec:rotaciones_avl]{anexo} 
    \item Right-Left(RL o DL): Ocurre cuando un nodo tiene un subárbol derecho que está desbalanceado a la izquierda. La solución son dos rotaciones: primero una rotación a la derecha del subárbol derecho y luego una rotación a la izquierda en el nodo. Véase \hyperref[subsec:rotaciones_avl]{anexo}
\end{itemize}
Consejos útiles:
\begin{itemize}
    \item Muchas veces, una rotación no siempre es suficiente para rectificar un nodo que está desequilibrado. 
    \item El rebalanceo (realiza las rotaciones) se invoca para todos los nodos de la rama hasta la raíz (hay que mandar el árbol entero).
    \item El máximo de rotaciones consecutivas para balancear un árbol es de 2.
    \item Al insertar un nodo en un AVL, el costo es O(log n). El costo de inserción es O(log n) y luego para rebalancear tambien, O(log n).
\end{itemize}
\begin{center}
    \begin{minipage}[b]{0.7\textwidth}
        \includegraphics[width=\linewidth]{assets/balanceo_avl.jpg}
        \centering
        \label{fig:balanceo_avl}
    \end{minipage}
\end{center}
\section*{Cola de Prioridad}
Es exactamente igual que el TAD Cola, pero difiere en la forma en que removemos elementos. No quitamos el primero que ingresó, sino que lo sacamos en base a un factor de prioridad que definimos a la hora de armar el TAD. \\ 
Si llegase a suceder que un mismo elemento tiene la misma prioridad, debería especificarse cual se quitaría. \\ 
La prioridad la expresamos con un entero, pero puede ser cualquier tipo $ \alpha$ que pueda ser comparado con un orden $<_{\alpha}$. \\

\textbf{Ej.}: Imaginemos que vamos a una guardia, y estamos primeros a punto de ser atendidos pero llega alguien que está en estado grave. Esta persona va a ser atendida antes que nosotros aunque hayamos llegado antes. En ese caso, es una cola de prioridad pues la prioridad está dada por la gravedad del paciente. \\ \\ 
Casos de uso: 
\begin{itemize}
    \item Sistemas operativos
    \item Algoritmos de Scheduling
    \item Gestión de colas
\end{itemize}
Véase \hyperref[subsec:cola_de_prioridad_avl]{\underline{anexo}} para un ejercicio de elección de estructuras para armar una cola de prioridad.
\section*{Heaps}
Es la implementación del TAD ColaPrioridad. Tiene la misma complejidad algorítmica que un árbol AVL pero es más fácil y elegante de implementar. \\
Invariante de representación:
\begin{itemize}
    \item Árbol binario perfectamente balanceado (difiere a lo mucho en un único nodo)
    \item El último nivel está lleno de nodos desde la izquierda (es izquierdista). Cuando el nivel del la rama izquierda ya difiere en uno con la derecha, agrego en las hojas de la rama derecha para dejar el árbol con misma altura, pero la idea es agregar de izquierda a derecha siempre. 
    \item La clave (prioridad) de cada nodo es \textbf{mayor o igual} que la de sus hijos (si es que tiene)
    \item Todo súbarbol es otro heap. 
    \item NO es un ABB. En un ABB el hijo derecho es más grande que el padre. En un Heap ambos hijos de un Nodo son menores.
\end{itemize}
Min-Heap: Min hace referencia a que el proceso de extraer, se hace sacando el mínimo en O(1). Si sacamos el mínimo en O(1) significa que todos los nodos debajo de la raíz son menores estrictos a él. \\
Max-Heap: Max hace referencia a que el proceso de extraer, se hace sacando el máximo en O(1). Si sacamos el máximo en O(1) significa que todos los nodos debajo de la raíz son mayores estrictos a él. \\

Véase \hyperref[subsec:operaciones_heaps]{\underline{operaciones heaps}} para un ejemplo más visual de las operaciones \\
Véase \hyperref[subsec:implementaciones_heap]{\underline{implementaciones heaps}} de maneras diversas.
\subsection*{Complejidad en operaciones con Heaps}
Nota: acá hablamos de un max-heap. recordemos que los que están arriba son mayores estrictos que los hijos.
\begin{itemize}
    \item Próximo: O(1) $\rightarrow$ raíz del árbol o primer elemento del array.
    \item Encolar(elemento): O(log n) $\rightarrow$ Sin necesidad de conocer el elemento, lo que tenemos que tratar es llenar el árbol de manera izquierdista. Hay dos casos
    \begin{itemize}
        \item Si el elemento que ingresé en el lugar libre es \textbf{menor a su padre, dejo todo como está.}
        \item Si el elemento que ingresé en el lugar libre es mayor a su padre, \textbf{hago el swap con el padre}. Por lo tanto ahora tengo garantizado que el elemento nuevo es el padre y los hijos son menores a este (vuelve a valer el invariante).
        \item \textbf{Algoritmo}: Insertar elemento al final del heap, y luego subir(elemento)
    \end{itemize}
    \item Subir(elemento) o Sift-Up: Mientras que el elemento no sea la raíz, y la prioridad del elemento sea mayor al padre, entonces intercambio \textbf{el elemento con el padre}.
    \item Desencolar(elemento): O(log n) $\rightarrow$ Son varios pasos 
    \begin{itemize}
        \item Intercambio la raíz con el último elemento ingresado. 
        \item Borro mi anterior raíz.
        \item Mi nueva raíz (el último ingresado), lo comparo con sus dos hijos verificando que 
        \begin{itemize}
            \item si estamos en un max-heap, sea el mayor de los dos hijos, si no lo es, entonces intercambio con el MAYOR/IGUAL HIJO. Hago esto recursivamente. 
            \item si estamos en un min-heap, sea el menor de los dos hijos, si no lo es, entonces intercambio con el MENOR/IGUAL HIJO. Hago esto recursivamente. 
        \end{itemize} 
    \end{itemize} 
    \item Bajar(p): Mientras que p no sea hoja y la prioridad de p sea menor al mayor de sus hijos, intercambio el hijo con p.

\end{itemize}
\subsection*{Transformaciones Array a Heap}
Véase \hyperref[subsec:array_2_heap]{\underline{array $\rightarrow$ heap}}
\section*{Tries}
El Trie es una estructura de datos que se suele utilizar en autocompletado de texto, pattern matching, etc.  \\
La principal característica es que la complejidad depende del tamaño de los elementos (en general, palabras) y no de la cantidad de elementos.
\begin{itemize}
    \item Se implementa sobre árboles n-arios: Donde n sería el tamaño del alfabeto más uno (por el símbolo reservado \$)
    \item Se usan para guardar grandes conjuntos de palabras o secuencias de elementos con un alfabeto reducido
    \item Cada nodo representa un caracter o componente de los elementos guardados.
    \item Se marca con \$ la finalización de la palabra o elemento. Donde el significado \$ es el valor de la palabra entera.
    \begin{itemize}
        \item El camino de la carrera Análisis I, en el valor de I el significado podría ser un objeto de esa materia.
    \end{itemize}
    \item Los caracteres, se van colocando donde se desea completar la palabra, pero no puede tener un hijo derecho y sí un hijo izquierdo.
\end{itemize}
\begin{center}
    \begin{minipage}[b]{0.6\textwidth}
        \includegraphics[width=\linewidth]{assets/trie.jpg}
        \centering
        \label{fig:trie}
    \end{minipage}
\end{center}
Propiedades:
\begin{itemize}
    \item En el nivel i-ésimo del árbol se guarda en el i-ésimo componente de la palabra/secuencia.
    \item La estructura del trie es única, no importa el orden en que se ingresen los valores de los nodos.
    \item Complejidad o(m) donde m es la longitud de la cadena involucrada en el procedimiento.
    \item La raíz de todo Trie es nulo, porque es la palabra vacía.
    \item Las palabras, terminan con \$. Si no hay un camino que termine con \$ entonces no es una palabra válida. 
\end{itemize}
Nota: Hay muchos algoritmos de Trie que tienen buena complejidad temporal pero son muy malos en complejidad espacial. \\ 
\textbf{Casos de uso para Trie}:
\begin{itemize}
    \item Si hay varias letras que se combinan y arman cosas diferentes, lo más seguro es que uses un trie para armar y buscarlas en $O(|palabra|)$. Ej: Nombres de carreras universitarias, o materias que no están acotadas en caracteres.
    \item Si hay varias letras que se combinan y arman cosas diferentes, lo más seguro es que uses un trie para armar y buscarlas en $O(1)$, notése que acá están acotadas, por lo tanto no tenemos que hacernos drama porque nunca va a existir algo más grande. Ej: Nombres de personas con máximo 20 caracteres.
\end{itemize}
La intuición en los casos de uso es cuando tienen que ser palabras (acotadas) o no acotadas. \\
Véase \hyperref[subsec:operaciones_trie]{\underline{casos de uso Trie}} para más ejemplos \\
\section*{Hashing}
Refiere al proceso de tomar una entrada, de cualquier tipo y generar una cadena de caracteres de longitud fija que representa de manera única esta entrada. \\
Son adecuados para representar diccionarios y/o conjuntos. \\
\subsection*{Representación}
Representemos un diccionario con
\begin{itemize}
    \item Tupla $<T, h>$ donde T es un arreglo con N = tamaño(T) celdas
    \item $h \ es \ una \ funcion \ hash:h(k) \rightarrow {0,..., n-1}$
    \begin{itemize}
        \item k: Conjunto de claves posibles 
        \item {0, ..., n-1}: Conjunto de las posiciones de la tabla (pseudoclaves)
        \item Para poder conseguir la posición de un elemento en el arreglo usamos la función h.
    \end{itemize}
\end{itemize}
\subsection*{Colisiones}
Las colisiones en un hash ocurre cuando dos entradas (keys) distintas producen el mismo valor de hash. \\
Un algoritmo de hash debería producir hashes únicos para cada entrada, sin embargo, debido a las limitaciones en la longitud finita de los hashes y a la naturaleza de la función hash es matemáticamente inevitable que ocurran colisiones en algún momento. \\
\textbf{Un buen algoritmo de hash minimiza la probabilidad de colisiones} \\
Maneras de resolver colisiones:
\begin{itemize}
    \item Direccionamiento Cerrado / Encadenamiento: Cada celda de la tabla hash mantiene una lista enlazada de todos los elementos que han colisionado en esa celda. En el mejor caso, el facotr de carga $\alpha =$ cantidad de elementos/cantidad de posiciones. Las operaciones sobre la listas enlazadas tendrán $\Omega(N/\longitud{T})$ y $O(N)$ 
    \begin{center}
        \begin{minipage}[b]{0.5\textwidth}
            \includegraphics[width=\linewidth]{assets/hashing_le.png}
            \centering
            \label{fig:hashing_le}
        \end{minipage}
    \end{center}
    \item Direccionamiento abierto: Cuando ocurre una colisión, se busca otra ubicación vacía dentro de la tabla hash para almacenar el elemento adicional. Este método puede producir deslocalización del elemento ya que cuando vuelva a llamar a la clave, el valor de hash para esa clave no va a coincidir con la posición del elemento, sino que habrá que hacer el mismo recorrido a la hora de setearlo. 
    \begin{center}
        \begin{minipage}[b]{0.5\textwidth}
            \includegraphics[width=\linewidth]{assets/hashing_posicion_vacia.png}
            \centering
            \label{fig:hashing_posicion_vacia}
        \end{minipage}
    \end{center}
\end{itemize}
\subsection*{Barridos}
También conocido como "scanning in hashing", se refiere a la acción de recorrer toda la tabla hash en búsqueda de un elemento específico o en caso de una colisión. Los barridos se diferencian por su complejidad algorítmica.
\begin{itemize}
    \item Barrido lineal: Cuando ocurre una colisión el algoritmo busca secuencialmente la siguiente ubicación disponible en la tabla hash hasta encontrar una celda vacía.
    \begin{itemize}
        \item Fórmula para encontrar la siguiente ubicación: $h(k, i) = (h'(k)+i) \ mod \ m$
        \item h(k, i) = nueva función hash 
        \item h'(k) = función hash original
        \item i = número de intentos de búsqueda 
        \item m = tamaño de la tabla hash
        \item Los elementos se aglomeran por largos tramos y puede surgir \textbf{aglomeración primaria}.
    \end{itemize}
    \item Barrido cuadrático: El incremento de las iteraciones es cuadrático.
    \begin{itemize}
        \item Fórmula para encontrar la siguiente ubicación: $h(k,i) = (h'(k) + c_{1} \ast i + c_{2} \ast i^{2}) \ mod \ m$
        \item El barrido cuadrático reduce el agrupamiento que a veces ocurre con el barrido lineal, sin embargo, puede sufrir de agrupamientos cuadráticos si no se eligen adecuadamente las constantes de incremento.
        \item El agloramiento para este barrido se llama \textbf{aglomeración secundaria}
    \end{itemize}
    \item Hashing doble: Se utiliza una segunda función de hash para calcular una ubicación alternativa cuando ocurre una colisión 
    \begin{itemize}
        \item Fórmula para encontrar la siguiente ubicación: $h(k, i) = (h_{1}(k) + i \ast h_{2}(k)) \ mod \ m$
        \item Donde $h_{1}(k) \ y \ h_{2}(k)$ son dos funciones de hash diferentes
        \item i = número de intentos de búsqueda 
        \item m = tamaño de la tabla hash
        \item El uso de una segunda función de hash reduce las posibilidades de agrupamiento y mejora la distribución de las claves en la tabla hash. 
        \item No se generan esas aglomeraciones o clusters tan frecuentes.
    \end{itemize}
\end{itemize}
\subsection*{Requisitos para una función hash}
\begin{itemize}
    \item Determinismo: Dada una misma entrada, la salida debe ser siempre el mismo hash.
    \item Eficiencia: Debe ser rápido de calcular.
    \item Difusión: Pequeños cambios en la entrada deberían producir cambios significativos y difíciles de predecir en el valor hash. 
    \item No reversibilidad: No se debe ser posible obtener el valor orignal a partir del hash. 
    \item Unicidad: Cada entrada debería producir un hash único. Es decir, no debería haber dos entradas diferentes con el mismo hash (ej: uuid)
    \item Uniformidad de distribución: Los valores hash deberían estar distribuidos uniformemente a lo largo del espacio de salida posible. Esto mejora la eficiencia del hashing y reduce la probabilidad de colisiones
\end{itemize}
\section*{Sorting}
Llamamos sorting al proceso de organizar un conjunto, lista, array u otra estructura de datos en un determinado orden. \\
Existen algoritmos de ordenamiento que lo hacen comparando elementos y otros no. \\ \\
\textbf{Importante}: las funciones de ordenamiento reciben arrays. Por lo tanto, si tengo un diccionario deberia convertirlo a un array de tuplas, y luego, aplico el ordenamiento correspondiente componente a componente. Lo mismo si tendría una lista, debería pasarlo a array. La complejidad es lo de menos por así decirlo porque de lista/diccionario a array es $O(n)$ y lo mismo al revés \\ \\
\textbf{Importante 2}: Si hay un criterio de desempate, primero ordenamos por el criterio de desempate y luego, por el otro.
\begin{itemize}
    \item Ordenar por nota, y si tienen misma nota, por género
    \item entonces: primero ordeno por genéro, y luego, con un algoritmo de sorting estable ordeno por nota.
\end{itemize}
\subsection*{Algoritmo de Barrido}
El término de barrido se lo utiliza para procesos en el que pasamos secuencialmente por cada elemento del conjunto de datos (a menudo, de principio a fin) y durante este recorrido, se pueden realizar diversas acciones como búsqueda, filtrado o cualquier otra operación que dependa de cada elemento. 
\subsection*{Estabilidad}
La estabilidad en un algoritmo de sorting nos garantiza que si existen dos claves que poseen el mismo valor, al ordenarlos poseen el mismo orden relativo original. 
\begin{center}
    \begin{minipage}[b]{0.5\textwidth}
        \includegraphics[width=\linewidth]{assets/estabilidad_sorting.png}
        \centering
        \label{fig:estabilidad_sorting}
    \end{minipage}
\end{center}
Nótese que no tendría sentido que si dos elementos tienen el mismo valor se intercambien entre sí. Si el algoritmo deja suceder esto, entonces es un algoritmo inestable. \\
Esto es de vital importancia cuando tenemos que ordenar en base a un ordenamiento anterior que debemos mantener.
\begin{center}
    \begin{minipage}[b]{0.5\textwidth}
        \includegraphics[width=\linewidth]{assets/estabilidad_sorting_2.png}
        \centering
        \label{fig:estabilidad_sorting_2}
    \end{minipage}
\end{center}
2da columna (estable): Valentina pasó a estar abajo de Federico ordenando correctamente por turno. Esto es porque mantuvo su orden relativo original. \\ 
3era columna (inestable): Valentina pasa a estar arriba de toda la lista, ignorando el orden relativo original, cosa que muestra inestabilidad.
\subsection*{Selection Sort}
\textbf{Es un algoritmo inestable, su complejidad en el mejor y peor caso es $O(n^{2})$ pues realiza comparaciones cuadráticas sin importar si el arreglo está ordenado o no.} \\
Para recordar rápido: comparo cada elem con todos los siguientes y voy moviendo el elem actual gracias al índice del ciclo
\begin{itemize}
    \item 1. Tomo elemento del índice, lo comparo con todos los de la lista hasta encontrar el más chico de la lista. 
    \item 2. Cuando encontré el más chico, reemplazo el elemento que tenía mi índice actual con ese mínimo.
    \item 3. Sumo uno al índice, y hago los pasos 1 y 2 tantas veces como sea necesario.
\end{itemize}
Invariante del Selection Sort
\begin{itemize}
    \item Los elementos entre la posición 0 y la posición i son los i+1 elementos más pequeños del arreglo inicial. 
    \begin{itemize}
        \item Esto puede parecer un poco confuso, pero digamos que estamos en i = 2, se supone que desde 0 hasta i = 2 ya está ordenado y entonces son los más pequeños. 
    \end{itemize}
    \item Los elementos entre la posición 0 y la posición i se encuentran ordenados.
    \item El arreglo es una permutación del arreglo original.
\end{itemize}
\subsection*{Insertion Sort}
\textbf{Es un algoritmo estable, su complejidad en el mejor caso es de $O(n)$ cuando ya está ordenado y el peor caso es $O(n^{2})$ cuando está completamente desordenado.} \\
Para recordar rápido: comparo cada elem con todos los anteriores, cuando encuentro uno que es menor al que estoy parado tengo que ir swappeando todos.
\begin{itemize}
   \item 1. La lista se divide conceptualmente en dos partes: una parte ordenada y una parte no ordenada.
   \item 2. Se selecciona cada elemento de la parte no ordenada y se inserta en la posición correcta dentro de la parte ordenada, desplazando los elementos mayores un lugar hacia la derecha.
   \item 3. Se repite el paso 1 y 2 hasta que todos los elementos estén en la parte ordenada.
\end{itemize}
Invariante del Selection Sort
\begin{itemize}
    \item Los elementos entre la posición 0 y la posición i son los elementos que ocupaban las posiciones 0 a i del arreglo original.
    \item Los elementos entre la posición 0 y la posicion i se encuentran ordenados.
    \item El arreglo es una permutación del arreglo original.
\end{itemize}
Básicamente: A medida que nos movemos, comparamos con todos los anteriores y si encuentro uno que es mayor tengo que swappear uno por uno hasta que quede mi número intercambiado en la posición del mayor que comparamos.
\begin{center}
    \begin{minipage}[b]{0.5\textwidth}
        \includegraphics[width=\linewidth]{assets/insertion_sort.png}
        \centering
        \label{fig:insertion_sort}
    \end{minipage}
\end{center}
\begin{itemize}
    \item 1. Como el 23 es el primer elem no hago nada.
    \item 2. Mi puntero está en el 1: $1>23?$ no, entonces tengo cambio el 1 por el 23.
    \item 3. Mi puntero está en el 10: $10>1?$ sí, entonces queda igual. 10>23? no, entonces los swappeo.
    \item 4. Mi puntero está 5: $5>1?$ sí, entonces queda igual. $5>10?$ no, entonces tengo que ir cambiando el 5 por el 23, el 5 por el 10. Como llegué al 10 que me rompía todo ya está.
    \item 5. Mi puntero está en el 2: $2>1?$ sí, entonces queda igual. $2>5?$ no, entonces swappeo el 2 con el 23, luego con el 10, y luego con el 5. Como llegué al 5 que me rompía todo ya está.
\end{itemize}
\subsection*{Merge Sort}
Es un algoritmo eficiente y recursivo que sigue el paradigma $divide \ \& \ conquer$ para ordenar una lista de elementos. \textbf{Es un algoritmo estable, su complejidad en el peor y mejor caso es $O(n \ log \ n)$}
\begin{itemize}
    \item Dividir recursivamente la lista no ordenada en sublistas más pequeñas hasta que cada sublista contenga un solo elemento (caso base).
    \item Fusiona recursivamente las sublistas ordenadas para crear sublistas más grandes y ordenadas hasta que finalmente se obtenga la lista completa ordenada.
\end{itemize}
Nota: Para mergear las 3 sub-listas usamos 3 punteros (i, j, k)
\begin{center}
    \begin{minipage}[b]{0.7\textwidth}
        \includegraphics[width=\linewidth]{assets/merge_sort.png}
        \centering
        \label{fig:merge_sort}
    \end{minipage}
\end{center}
\subsection*{Quick Sort}
Es un algoritmo eficiente y recursivo que sigue el paradigma $divide \ \& \ conquer$. Para poder realizarlo necesitamos tener un elemento como pivote. \textbf{Es un algoritmo no estable, su peor caso es $O(n^{2})$ (eligiendo el peor pivote) y el mejor es $O(n \ log \ n)$}
\begin{itemize}
    \item 1. Selecciona un elemento de la lista como pivote. Puede ser el primero, el último o cualquiera.
    \item 2. Reordena los elementos de la lista de manera que todos los de la izquierda del pivote sean menores, y los de la derecha mayores.
    \item 3. Aplica recursivamente el mismo proceso a las sublistas de elementos menores y mayores que el pivote.
\end{itemize}
Nota: Si conocemos el elemento mediano del arreglo, entonces podemos hacer el paso 2 y 3 directamente.
\begin{center}
    \begin{minipage}[b]{0.5\textwidth}
        \includegraphics[width=\linewidth]{assets/quick_sort_1.png}
        \centering
        \label{fig:quick_sort_1}
    \end{minipage}
\end{center}
Luego, hacemos el paso de conquistar
\begin{center}
    \begin{minipage}[b]{0.5\textwidth}
        \includegraphics[width=\linewidth]{assets/quick_sort_2.png}
        \centering
        \label{fig:quick_sort_2}
    \end{minipage}
\end{center}
Como nuestro pivote quedó bien posicionado, es decir, todos los elementos de la izquierda son menores y los de la derecha son mayores y están todos ordenados terminamos.
\subsection*{Heap Sort}
\textbf{Es una algoritmo eficiente no estable. Todos sus casos son de complejidad $O(n \ + \ n \ log \ n) \equiv (n \ log \ n) $} \\
La idea es crear un max-heap o min-heap según lo que necesitemos, agregamos los elementos en ese heap, y luego los volvemos a quitar. El costo de agregar cada elemento del array en el heap es de n, mientras que el log n aparece de balancear cada vez que quitamos un elemento o agregamos.
\subsection*{Bucket Sort}
Es un algoritmo eficiente que está diseñado para arrays de cualquier tipo y supone que los elementos pueden separarse según algún criterio en M categorias ordenadas. \\ \textbf{La estabilidad depende del algoritmo que se use para ordenar los buckets.} \\ \textbf{Los elementos se distribuyen en buckets (cajas) donde cada caja se ordena individualmente, generalmente utilizando otro algoritmo de ordenamiento o aplicando recursivamente bucket sort si es necesario.} \\
\textbf{El mejor caso es $O(n+k)$ cuando los elementos están uniformemente distribuidos y con una cantidad parecida en cada bucket.} \\
\textbf{El peor caso es $O(n^{2})$ cuando todos los elementos están en un solo bucket.}
\begin{itemize}
    \item Se conoce de antemano la distribución de los datos y los elementos están distribuidos uniformemente en el rango (esto permite que los buckets tengan un tamaño similar).
    \item El número de elementos es moderado.
    \item Los elementos pueden ser comparados entre sí.
\end{itemize}
\begin{center}
    \begin{minipage}[b]{0.7\textwidth}
        \includegraphics[width=\linewidth]{assets/bucket_sort.png}
        \centering
        \label{fig:bucket_sort}
    \end{minipage}
\end{center}
\textbf{Importante}: Cuando un array pasa por bucket sort, la respuesta es un array de listas enlazadas.
\subsection*{Counting Sort}
\textbf{Es un algoritmo de ordenamiento estable no comparativo}. Solo acepta arrays de números naturales y cuando el rango de los elementos es pequeño en comparación con el número de elementos a ordenar. \\
Asume que los elementos del array son menores que un cierto valor k \\
\textbf{Todos los casos son $O(n+k)$ donde n es el tamaño del arreglo y k es el valor del elemento más grande en el arreglo.}
\begin{itemize}
    \item Busco el máximo elemento del arreglo original, y creo un arreglo vacío con longitud del máximo elemento.
    \item Cada aparición de un elemento hace referencia a incrementar uno ese índice en el array auxiliar.
    \item Luego, recorremos el array auxiliar por cada índice, la cantidad de apariciones (índice 1 representaría el número 1, y el valor representa la cantidad de apariciones) y lo vamos agregando en el array original.
\end{itemize}
\begin{lstlisting}
    Consideremos: [3, 2, 4, 1, 4, 6, 1, 10].
    Paso 1. Como el máximo elemento del array es 10, creo un array auxiliar de 10 posiciones.
    Paso 2. Voy barriendo el arreglo original, y por cada elemento coloco en mi array el índice y le sumo uno.
    [0, 2, 1, 1, 2, 0, 1, 0, 0, 0, 1]
    Paso 3. Cada índice, representa la cantidad de apariciones del número. Los concateno.
    [1, 1, 2, 3, 4, 4, 6, 10]
\end{lstlisting}
\subsection*{Radix Sort}
\textbf{Es un algoritmo de ordenamiento estable no comparativo} que reutiliza counting sort procesando las cifras individualmente. \\ Es eficaz cuando se ordenan elementos que tienen claves que se pueden dividir en cifras individuales, como números enteros o cadenas de caracteres numéricos. \\
Los números deben ser igual en longitud, si no tienen la misma longitud se extienden con 0's desde la cifra menos significativa. \\
Si al querer ordenar los valores mirando los dígitos hay empate, se mantiene el orden de esos elementos. \\
\textbf{El peor caso es $O(d \ast O(n+k))$ donde d es la cantidad de dígitos y (n+k) es haciendo referencia al counting sort donde n es la longitud del arreglo y k es el valor más grande. \\
El mejor caso es de $O(n)$ cuando d y k no dependen de n y son longitud fija. \\}
\textbf{Es importante considerar que cada vez que ordenamos cada cifra, el orden relativo importa. Es decir, tenemos que reordenar en base al ordenamiento anterior.}
\begin{lstlisting}
    Ejemplo: [329, 460, 420, 350]
    Paso 1: Tomo la unidad, y ordeno en base a ellos manteniendo su orden relativo original -> [460, 420, 350, 329]
    Paso 2: Tomo la decena, y reordeno considerando el orden relativo anterior -> [420, 329, 350, 460]
    Paso 3: Tomo la centena, y reordeno considerando el orden relativo anterior -> [329, 350, 420, 460]
\end{lstlisting}
Es útil cuando necesitamos ordenar listas con muchos criterios de orden que consiste en ordenar primero por el criterio menos relevante con cualquier algoritmo y luego el más relevante con un algoritmo estable para no perder el orden anterior
\textbf{Consideraciones importantes}
\begin{itemize}
    \item Todos los algoritmos de sorting requieren arrays (recordar que para pasar de lista a array es $O(n)$) y si necesito pasar de diccionario, lo ideal es para de diccionario a array de tuplas donde la primera componente es la key y el segundo el valor.
    \item En la materia, los algoritmos de ordenamiento ya están implementados porque el objetivo no es aprender a codearlos sino saber como usarlos y cuando. El tipo de ordenamiento descendente/ascendente se lo considera con un comentario antes de llamar a la función que ordena. 
\end{itemize}
\textbf{Importante}: Es útil a la hora de manipular strings porque la tabla ASCII está limitada a 256 caracteres, por lo tanto sería O(1) ordenarlos.
\subsection*{Resumen de complejidades de algoritmos de sorting}
\begin{table}[h!]
    \centering
    \begin{tabular}{|c|c|c|c|c|}
    \hline
    \textbf{Nombre} & \textbf{Mejor caso} & \textbf{Caso promedio} & \textbf{Caso peor} & \textbf{Es estable} \\
    \hline
    Bubble Sort & $O(n)$ & $O(n^{2})$ & $O(n^{2})$ & Si \\
    \hline 
    Bucket Sort & $O(n+k)$ & $O(n+k)$ & $O(n^{2})$ & Depende del algoritmo de sorting \\
    \hline
    Counting Sort & $O(n+k)$ & $O(n+k)$ & $O(n+k)$ & Si \\
    \hline
    Heap Sort & $O(n \ log(n))$ & $O(n \ log(n))$ & $O(n \ log(n))$ & No \\
    \hline
    Insertion Sort & $O(n)$ & $O(n^{2})$ & $O(n^{2})$ & Si \\
    \hline
    Merge Sort & $O(n \ log(n))$ & $O(n \ log(n))$ & $O(n \ log(n))$ & Si \\
    \hline
    Quick Sort & $O(n \ log(n))$ & $O(n \ log(n))$ & $O(n^{2})$ & No \\
    \hline
    Radix Sort & $O(n)$ & $O(d \ast O(n+k))$ & $O(d \ast O(n+k))$ & Si \\
    \hline
    Selection Sort & $O(n^{2})$ & $O(n^{2})$ & $O(n^{2})$ & No \\
    \hline
    \end{tabular}
    \caption{Tabla de complejidades de algoritmos de sorting}
    \label{tab:ejemplo}
    \end{table}
\textbf{Consideraciones importantes útiles}:
\begin{itemize}
    \item Si necesita concatenar arrays, lo mejor sería pasar cada array a una lista enlazada, concatenar las listas enlazadas en O(1) y luego pasarlo a array en O(n) (ya sabiendo la longitud gracias a la lista enlazada)
    \item Es muy común utilizar Listas Enlazadas y sus iteradores en temas de optimización de complejidades por su gran velocidad a la hora de insertar atrás.
    \item Es útil cuando sabemos que tenemos arrays de números continuos ordenados (1113344) y un array todo desordenado (9, 4, 1) agregar en una lista enlazada los primeros elementos del array que tiene elementos continuos almacenarlos de forma (valor, cantidadApariciones), lo mismo con el otro array pero cada elem con una posibilidad de aparición (xq no sabemos con certeza). Luego, esta lista enlazada se pasa a un array de tuplas O(n'+m), se los ordena con el criterio que se necesite, luego se lo pasa a un array plano en O(n'+m). Finalmente, como n' eran los elementos de n colapsados, al ser un array plano vuelve a ser n y la complejidad queda O(n'+m * log(n'+m)).
    \item Si nos dan datos en forma de rango y se nos pide ordenar en O(n), ej: se sabe que tenemos un array de n posiciones donde $\sqrt{n}$ exceden el rango [20, 40]. 
    \begin{itemize}
        \item En este caso tenemos 3 datos, $\sqrt{n}$ son elementos que son menores a 19 o mayores a 40, por otro lado, los que están entre 20 y 40 son acotados (aka: counting sort con k = 40). 
        \item En este caso lo que nos conviene hacer es crear 3 listas enlazadas (para agregar en O(1)) donde cada lista tiene sus elementos (menores a 20, mayores a 40 y en rango). 
        \item Para agregar los elementos en las listas enlazadas basta con hacer un while del array original y verificar que valor tiene, segun qué caso se cumpla lo agregamos a una lista enlazada u otra.
        \item Pasamos cada lista enlazada a array. Menores a 20 y Mayores a 40 como tienen complejidad con la raíz y nos pide O(n) aplicamos un algoritmo cuadrático $ O(\sqrt(n))^{2} \equiv O(n) $ entonces seguro seguro que cuadrático es selection sort. Para los que están en rango podemos usar Counting Sort. 
        \item Luego que los 3 arrays estan ordenados, pasamos a listas enlazadas para concatenar en O(1).
        \item Luego que tenemos, concatenamos en orden, menores20.concatenar(enRango) y luego menores20.concatenar(mayores40).
        \item Luego, pasamos todo esto a un array plano de la longitud original que nos pedia el ejercicio y listo.
    \end{itemize}
    \item Siempre que nos den dos criterios de ordenamiento, primero ordenamos por el de desempate y luego por el inicial. Ej: si nos piden ordenar primero por nota, y en caso de igual nota por género: primero ordenamos con cualquier ordenamiento por género, y luego con un algoritmo estable por nota. 
    \item Siempre que tenga cosas acotadas, considere usar bucket sort o counting sort. Por ejemplo, si nos dicen que tenemos que ordenar en O(n) los alumnos por genéro y luego en caso de desempate por nota: Primero hacemos un bucket sort con 11 elementos para ordenar (supongo que para ordenar por nota, el bucket sort lo hizo con counting) por nota, luego pasamos las listas enlazadas del bucket a array, y luego aplicamos bucket sort otra vez pero ahora por genéro. Finalmente, las listas enlazadas, lo pasamos a array para obtener el resultado.
\end{itemize}
\section*{Anexo}
\subsection*{Invariante de Representación, Función de Abstracción y Memoria Dinámica}
\label{subsec:anexo_invrep_abs}
Ejercicio 1: Con esta estructura, podemos permitir que haya repetidos o no los haya.
\begin{itemize}
    \item ¿Cuál es más eficiente? ¿Cuándo usaría cada una de las dos versiones? 
    \item Escriba el invariante de representación y la función de abstracción en castellano, y luego en especificación formalmente.
    \item Escriba los algoritmos para las operaciones de agregar un elemento y sacar un elemento (para la versión de sin repetidos).
    \item Si está creando un nuevo arreglo cada vez que saca un elemento, piense una solución sin que se necesite copiar el arreglo original.
    \item Intente escribir el invariante de representación y la operación de agregar para el caso de con repetidos. ¿Qué dificultades encuentra?
\end{itemize}
\begin{lstlisting}
    TAD ConjuntoAcotado<T> {
        obs elems: conj<T>
        obs cap: int
        
        proc agregar(inout c: ConjuntoAcotado<T>, in e: T)
            requiere {c = old(c)}
            requiere {|c.elems| < c.cap}
            asegura {c.elems = old(c).elems U <e>}
        
        proc sacar(inout c: ConjuntoAcotado<T>, in e: T)
            asegura {c.elems = old(c).elems - <e>}
    }

    Modulo ConjAcotadoArr<T> implenenta ConjAcotado<T> {
        var datos: Array<T>
        var largo: int
    }
\end{lstlisting}
En el módulo tenemos dos variables: un array y un entero. La variable largo nos servirá para poder saber cuantos espacios de datos están ocupados pues, si recordamos, el array quizá tiene longitud 20 pero no necesariamente los 20 espacios están ocupados. \\
El enunciado nos pide implementar un Conjunto acotado con arrays, ya con decir que queremos implementar un conjunto no deberíamos de permitir repetidos, aún así, podríamos aceptarlos, pero el problema vendría al momento de eliminar. ¿Qué aparición sacaríamos? En este caso, como es un conjunto deberíamos eliminar cada una de las apariciones del elemento. \\
1. La versión más eficiente sería la de sin repetidos pues sabemos que todos los elementos se encuentran presentes una sola vez, y basta con eliminarlos en tiempo O(n) en peor caso y O(1) en mejor caso. Si un elemento estaría repetido, ambos casos serían O(n). Con respecto a la variable largo, al ser una resta de cantidad de apariciones no afecta en temas de complejidad pues es una operación elemental. En ambos casos deberíamos de copiar el arreglo original, porque pensemos que si eliminamos un elemento del medio del conjunto, el largo disminuiría pero eso no significa que sepamos la posición "vacía". \\
Quizá una buena idea sería tener un arreglo más con el mismo tamaño y que en cada posición tengamos un true/false según si el elemento fue borrado o no. Eso nos permitiría reutilizar alguas posiciones de nuestro array original y no copiar el array todo el tiempo. \\
2.
\begin{lstlisting}
    InvRep: 
        Para todo elemento presente en datos, no hay repetidos.
        Largo es mayor que 0 y menor o igual a la longitud de datos.
    Abs: 
        Para todo elemento presente en elems (TAD) está en datos (Módulo).
        Para todo elemento presente en datos (Módulo) está en elems (TAD).
        La longitud de datos (Módulo) es igual a cap (TAD).
        Cap (TAD) es igual a la longitud de datos (Módulo).
        Largo (Módulo) es igual a la cantidad de elems (TAD).
        Cantidad de elems (TAD) es igual a Largo (Módulo).
\end{lstlisting}

\pred{InvRep}{c': ConjAcotadoArr$<T>$}{
    0 \le c'.largo < \longitud{c'.datos} \land
    SinRepetidos(c'.datos)
}
\pred{SinRepetidos}{datos: Array$<T>$}{
    \paraTodo[unalinea]{i}{\ent}{0\le i < \longitud{datos} \implicaLuego 
        \paraTodo[unalinea]{j}{\ent}{0\le j < \longitud{datos} \land datos[i] = datos[j] \implicaLuego i=j }
     }
}

Forma 1: \\
\pred{Abs}{c: ConjAcotado$<T>$, c': ConjAcotadoArr$<T>$}{
    \paraTodo[unalinea]{e}{T}{e \in c'.datos \iff e \in c.elems} \land 
    c'.largo = \longitud{c.elems} \land \longitud{c'.datos} = c.cap
} 

Forma 2: En esta no hace falta indicar la relación entre largo y elems aparte pues queda explícito entre el rango, todos los elementos de la lista están en el conjunto. \\
\pred{Abs}{c: ConjAcotado$<T>$, c': ConjAcotadoArr$<T>$}{
    \paraTodo[unalinea]{i}{T}{0\le i<c'.largo \implicaLuego c'.datos[i] \in c.elems}  \land \longitud{c'.datos} = c.cap
} 
3. Algoritmos: 
\begin{lstlisting}
    La instancia debe ser la misma, requiere me dice que tengo espacio y aseguro insertar el elemento.

    proc pertenece(in c': ConjuntoAcotadoArr<T>, in e: T): boolean{
        var i:int := 0;
        var encontrado:boolean := false;
        while(i<c'.datos && !encontrado) do
            if(c'.datos[i] == e) then
                encontrado := true
            endif
            i++;
        endwhile
        return encontrado; 
    }
    
    //Nótese que aunque no modificamos nada, el procedimiento sigue siendo inout porque hay un caso en el que sí se termina modificando algo.
    proc agregar(inout c': ConjuntoAcotadoArr<T>, in e: T){
        if(c'.pertenece(e) == true) return; 
        c'.datos[largo] = e;
        c'.largo = c'.largo + 1; 
    }

    proc sacar(inout c': ConjuntoAcotadoArr<T>, in e: T){
        var i:int := 0;
        while(i<c'.datos) do
            if(c'.datos[i] == e) then
                c'.datos[i] = c.datos[c'.largo]; //Swappeo el ultimo elem con la pos que tengo que eliminar
                c'.datos[c'.largo] = 0; //Elimino el elemento
                c'.largo--;
            endif 
            i++;
        endwhile 

        [1, 2, 3, 4, 5] -> Eliminar el 4. Largo=5
        [1, 2, 3, 5, 4] -> Swappeo el 5 con el 4. Largo=5
        [1, 2, 3, 5, 0] -> Pongo en 0 el ultimo elem. Largo=4.
        La próxima vez, sé que solo tengo 4 elems válidos. Esta estrategia sirve para poder saber que el ultimo ya no va a contar, y entonces le achicamos la longitud de recorrido.
    }
\end{lstlisting}
4. Hecho en 3.
5. InvRep para el caso con repetidos 
\begin{lstlisting}
    InvRep:
        Largo es mayor que 0 y menor o igual a la longitud de datos.
        
    proc agregar(inout c': ConjuntoAcotadoArr<T>, in e: T){
        c'.datos[largo] = e;
        c'.largo = c'.largo + 1; 
    }

    El problema de acá es que estamos llenando el arreglo de elementos que ya están y no estamos respetando la idea del Conjunto. De alguna manera, si necesitamos devolver el conjunto o el largo, deberíamos contar una única vez la aparición de cada elemento.

\end{lstlisting}
Ejercicio 2: Implemente una pila no acotada utilizando arreglos. Escriba la estructura, el invariante de representación, la función de abstracción en castellano, en especificación y las operaciones de apilar y desapilar. \\

Una pila se caracteriza por los siguientes puntos:
\begin{itemize}
    \item Puede haber repetidos. 
    \item Agrego y saco desde el final.
\end{itemize}
Acá la manera de desapilar es más facil, porque solo sacamos desde el final disminuimos largo e igualmente el orden se mantiene. Es decir, no tenemos que hacer un swap para garantizar que el eliminado estaba al final y tener que reacomodar algún que otro elemento. \\
El único tema sería añadir elementos pues si no tenemos espacio deberíamos copiar la pila entera, duplicar el arreglo, y colocar los elementos en la pila nueva. En este caso, como los elementos de la pila queremos que sean los mismos, tendremos que hacerlo por aliasing.
\begin{lstlisting}
    TAD Pila<T> {
        obs s: seq<T>
        proc pilaVacía(): Pila<T>{
            asegura {res.s = <>}
        }

        proc apilar(inout p: Pila<T>, in e: T){
            asegura {p.s = concat(old(p).s,<e>)}
        }
        proc desapilar(inout p: Pila<T>): T{
            requiere {p.s != <>}
            asegura {p.s = subseq(old(p).s, 0, |old(p).s| - 1)}
            asegura {res = old(p).s[|old(p).s| - 1]}
        }
    }

    Módulo PilaNoAcotadaArr<T> implementa Pila<T> {
        var datos: Array<T>
        var largo: int
    }
\end{lstlisting}
\pred{InvRep}{p': PilaNoAcotadaArr$<T>$}{
    0 \le p'.largo < \longitud{p'.datos} \land \longitud{p'.datos} \ mod \ 2 \ = \ 0
}
A tema de que sacamos por el final y agregamos al final no iría en el invrep porque no es una restricción que pongamos nosotros y podamos detectar que la pila es inválida. \\
\pred{Abs}{p: Pila$<T>$, p': PilaNoAcotadaArr$<T>$}{
    \paraTodo[unalinea]{i}{T}{0\le i<p'.largo \implicaLuego p'.datos[i] = p.s[i]} \land p'.largo = \longitud{p.s}
}
En el ABS garantizo que todos los elementos dentro de largo están en p.s pero además digo que son de la misma longitud. Porque podría pasar que p'.largo sea menor a \longitud{p.s} y que p.s tenga todos los elementos de p'.datos. Acá necesito decir algo más fuerte como que además las longitudes son iguales.
\begin{lstlisting}
    Módulo PilaNoAcotadaArr<T> implementa Pila<T> {
        var datos: Array<T>
        var largo: int

        proc apilar(inout p': PilaNoAcotadaArr, e: T){
            if(p'.largo == p'.datos.length) then
                var nuevoArreglo: Array<T>:= new Array<T>(){p'.largo * 2};
                var i:int := 0;
                
                while(i<p'.datos.length) do
                    nuevoArreglo[i] = p'.datos[i];
                    i++;
                endwhile;
                
                p'.datos = nuevoArreglo;
            endif
              
            p'.datos[p'.largo] = e;
            p'.largo++;

        }

        //Por requiere se asume que no está vacía.
        proc desapilar(inout p': PilaNoAcotadaArr): T{
            var desapilado: T := p'.datos[p'.largo];
            p'.datos[p'.largo] = 0; 
            p'.largo--;
            return desapilado;
        }
    }
\end{lstlisting}
Ejercicio 3: Sea una Pila donde se puede eliminar elementos dado un índice, realice el inv rep y la función de abstracción. Escriba los algoritmos de apilar, desapilar y eliminar. enUso tiene los elementos de datos que no están eliminados.
\begin{lstlisting}
    proc eliminar(inout p: Pila<T>, i: Z){
        requiere {0 <= i < |p.s|}
        asegura {p.s = concat(subseq(old(p).s, 0, i), subseq(old(p).s, i + 1, |old(p).s|))}
    }

    Modulo PilaConElimArr<T> implenenta PilaConElim<T> {
        var datos: Array<T>
        var enUso: Array<boolean>
        var largo: int
    }

    datos: [1, 2, 3, 4] 
    enUso: [T, T, F, F]
    largo: 2

    datos teoricamente sería: [1, 2]
    
    InvRep: 
        La longitud de datos es igual a la de enUso (contando eliminados y no eliminados, tamaño del arr)
        Largo es igual a la cantidad de elementos en true que hay en enUso
    Func Abs:
        El largo es igual a la longitud de p.s
        Todos los elementos que estan en el rango de largo en datos, están en p.s en la misma posición.
\end{lstlisting}
\pred{InvRep}{p': PilaConElimArr$<T>$}{
    \longitud{p'.datos} = \longitud{p'.enUso} \land 
    p'.largo = CantidadElementosValidos(p'.enUso)
}
\aux{CantidadElementosValidos}{l: Array$<T>$}{\ent}{
    \sum_{i=0}^{\longitud{l}-1}{if(l[i] \ == \ true) \ then \ 1 \ else \ 0}
}

//Al eliminar, en el TAD se elimina y se reordena la secuencia. Nosotros no la reordenamos, por lo tanto, los elems podrían no estar en la misma posición \\
\pred{Abs}{p: PilaConElim$<T>$, p': PilaConElimArr$<T>$}{
    p'.largo = \longitud{p.s} \land
    \paraTodo[unalinea]{i}{\ent}{0\le i<p'.datos \land p'.enUso[i] == true \implicaLuego \existe[unalinea]{j}{\ent}{0 \le j<p.s \land p'.datos[i] = p.s[j]}}
}

\begin{lstlisting}
    proc agrandarYCopiar(inout p':PilaConElimArr<T>){
        var nuevoArreglo: Array<T> := new Array<T>(){p'.largo * 2};
        var nuevoArregloEnUso:Array<boolean> := new Array<T>(){p'.largo * 2}; //Se inicializa todo en false

        var i:int := 0;
        while(i<p'.datos.length) do
            nuevoArreglo[i] = p'.datos[i];
            nuevoArregloEnUso[i] = p'.enUso[i];
            i++;
        endwhile;
        
        p'.datos = nuevoArreglo;
        p'.enUso = nuevoArregloEnUso;
    }
    proc apilar(inout p': PilaConElimArr<T>, in e: T){
        if(p'.datos.length == p'.largo){ //No hay ningun borrado, no hay espacio.
            agrandarYCopiar(p');
            p'.datos[p'.largo] = e;
            p'.enUso[p'.largo] = true;

        }else{ //Existe al menos uno borrado y hay espacio para pisarlo. 
            var borrado: T := null;
            var i:int := 0;
            while(i<p'.datos.length) do
                if(p'.enUso[i] == false) then
                    p'.datos[i] = e;
                    p'.enUso[i] = true;
                endif 
                i++;
            endwhile 
        }

        p'.largo++; 

    }    
    //Quito el ultimo no eliminado
    proc desapilar(inout p': PilaConElimArr<T>): T{
        var i:int := p'.largo-1;

        while(p'.enUso[i]==false) do //busco el ultimo que está en true
            i--;
        endwhile
        
        var res:T := p'.datos[i];
        p'.datos[i] = 0;
        p'.enUso[i] = false;
        p'.largo--;

        return res;
    }

    proc eliminar(inout p': PilaConElimArr<T>, in i: int){
        p'.enUso[i] = false;
        if(i == p'.largo-1){ //Solo resto largo si quité el último, sino estaría evitandome obtener el último elemento si no había sido eliminado.
            p'.largo--;
        }
    }
\end{lstlisting}

Ejercicio 4: De parcial 
\begin{center}
    \begin{minipage}[b]{0.8\textwidth}
        \includegraphics[width=\linewidth]{assets/parcial_tad.png}
        \centering
        \label{fig:parcial_tad}
    \end{minipage}
\end{center}
a) Lo primero que puedo observar es que me hablan de conjuntos. Así que tengo que considerar que a la hora de agregar o quitar, debo verificar si algo está o no para no aceptar duplicados (¡cuesta tiempo!). \\ 
Las complejidades observo que son logarítmicas, y que hay dos procedimientos que dado un t1 o un t2, debo devolver un conjunto en tiempo logarítmico. La única estructura que nos permite añadir o verificar en tiempo logarítmico es un AVL ya sea conjunto o diccionario. Necesito si o si guardar un valor dado una clave, según observo en relacionadosDer y relacionadosIzq así que la mejor opción es un DiccionarioLog. El conjunto queda descartado porque no puedo obtener un valor, sino solamente verificar que algo está. \\
El tener relacionadosIzq por un lado, y relacionadosDer por el otro me da la pista de que necesito dos estructuras separadas, es decir, por un lado, los relacionados de cada T1 y por otro, los relacionados de cada T2. \\
El siguiente problema que podemos ver, es que si tenemos que guardar los relacionados de un T1 o un T2 hay que verificar si hay repetidos, porque caso contrario, relacionar no ocuparía tiempo O(log n + log m) pero podemos intuir que como, a lo sumo, los relacionados de T1 tienen todos los T2 o viceversa, el verificar si existe, el costo también será log n o log m según el caso y no afecta en tiempo de inserción. \\
Luego, la estructura podría ser
\begin{lstlisting}
    Módulo RelacionadosImpl<T1, T2> implementa Relacionados<T1, T2> {
        var rt1: DiccionarioLog<T1, ConjuntoLog<T2>>
        var rt2: DiccionarioLog<T2, ConjuntoLog<T1>>
        proc nuevo():RelacionadosImpl<T1, T2>{
            res.rt1 := new DiccionarioLog();
            res.rt2 := new DiccionarioLog();
        }

        proc relacionar(inout r: RelacionadosImpl<T1, T1>, in t1:T1, in t2:T2){
            var t1obj := r.rt1.esta(t1); //O(log n)
            var t2obj := r.rt2.esta(t2); //O(log m)

            if(t1obj == true) then 
                t1obj := r.rt1.obtener(t1); //O(log n)
                tpobj := t1obj.pertenece(t2); //O(log m)
                if(tpobj == false) then
                    t1obj.agregarRapido(t2); //O(log m)
                endif 
                r.rt1.definirRapido(t1, t1obj); //O(log n)
            else 
                r.rt1.definirRapido(t1, new ConjuntoLog().definirRapido(t2)); //O(log n + log m)
            endif 
            

            //Mismo con t2.
            if(t2obj == true) then 
                t2obj := r.rt2.obtener(t2); //O(log m)
                tpobj := t2obj.pertenece(t1); //O(log n)
                if(tpobj == false) then
                    t2obj.agregarRapido(t1); //O(log n)
                endif 
                r.rt2.definirRapido(t2, t2obj); //O(log m)
            else 
                r.rt2.definirRapido(t2, new ConjuntoLog().definirRapido(t1)); //O(log m + log n)
            endif 
        }

        O(log n + log m + (log n + log m + log m + log n + log m) + (log m + log n + log n + log m + log n)) =
        O(log n + log m)
    }

    proc relacionadosIzq(in r:RelacionadosImpl<T1, T2>, in t2:T2): ConjuntoLog<T1>{
        return r.rt2.obtener(t2); //O(log m)
    }

    proc relacionadosDer(in r:RelacionadosImpl<T1, T2>, in t1:T1): ConjuntoLog<t2>{
        return r.rt1.obtener(t1); //O(log n)
    }

\end{lstlisting}
b) Agregaría un campo que tenga una tupla con (T1, max) donde T1 es el elemento que más relacionados tiene, y max es el valor más grande. Como solo me importa uno solo, y sé que las tuplas son inmutables, cada vez que encuentre uno que sea más grande tengo que encontrar una nueva y pisarla. \\
Esto puedo agregarlo al momento de relacionar: 
\begin{lstlisting}
    proc relacionar(inout r: RelacionadosImpl<T1, T1>, in t1:T1, in t2:T2){
           //mismo antes

            if(t1obj == true) then 
                //mismo antes
            else 
                //mismo antes
            endif 

            //Agregar esto
            t1obj := r.rt1.obtener(t1);
            if(t1obj.tamaño() > r.masRt1[1]){
                var nuevaTupla: tupla(T1, int) := (t1, t1.obj.tamaño());
                r.masRt1 = nuevaTupla;
            }
    }
\end{lstlisting}
c) 
\begin{itemize}
    \item Para toda clave en RT1, son únicas y los valores del conjunto asociado a cada clave existen como claves en RT2.
    \item Para toda clave en RT2, son únicas y los valores del conjunto asociado a cada clave existen como claves en RT1.
    \item masRt1, el primer elemento de la tupla existe como clave en RT1 y el segundo elemento de la tupla (el máximo) es el tamaño del conjunto asociado a esa clave T1 en RT1.
\end{itemize}
d) 
\begin{itemize}
    \item Para toda clave y posibles combinaciones con cada uno de los valores asociados en el conjunto para esa clave en RT1 están en alguna tupla que pertenecen a obs elems. 
    \item Para toda posible tupla en elems, el primer elemento existe como clave en RT1 y el segundo valor existe dentro del conjunto asociado a esa clave en RT1.
\end{itemize}
Nota: No mencioné que en elems, T2 es clave en RT2 y T1 es un valor que se encuentra en el conjunto asociado para esa clave en RT2 pues lo deja claro el invariante de representación.
\subsection*{Complejidad - Aplicando Propiedades}
\label{subsec:complejidad_propiedades}
\textbf{1. Demuestre si es verdadero o falso y justifique} $n+m^{5} = O(m^{5})$ \\
Como tenemos una suma, la regla de la suma nos dice que debemos quedarnos con \textbf{la} que mayor complejidad aporte al peor caso.
\begin{itemize}
    \item Si $n > m^{5}$ entonces $ n = O(m^{5})$ lo que es falso.
    \item Si $m^{5} > n$ entonces $ m^{5} = O(m^{5})$ es verdadero pues por reflexividad sabemos que $f \in O(f)$
\end{itemize}
Podemos encontrar un contraejemplo para mostrar su falsedad viendo el primer caso: \\
Contraejemplo: $n=m^{6}$ \\
\textbf{2. Demuestre si es verdadero o falso y justifique} $m^{5} = O(n+m^{5})$ \\
Como dentro de O tenemos una suma, y hablamos del peor caso debemos quedarnos con la que sea mayor.
\begin{itemize}
    \item Si $n > m^{5}$ entonces $m^{5} = O(n)$ lo cual sería cierto pues si $n > m^{5}$ sucede que $m^{5} \in O(n)$
    \item Si $m^{5} > n$ entonces $m^{5} = O(m^5) $ lo cual es cierto pues por reflexividad sabemos que $f \in O(f)$ 
\end{itemize}
Probemos por definición: $ m^{5} \le c \ast (n + m^{5})$ \\
$ \implies \frac{m^{5}}{n+m^{5}} \le c$ \\
$ \implies \frac{m^{5}}{n} + 1 \le c$ como las constantes no afectan en complejidad, las quito  \\
$\implies m^{5} \le c$ \\
TODO \\
\textbf{3. Demuestre si es verdadero, halle un contraejemplo si es falsa y justifique}: $f \in \Omega(n) \implies O(f) \cap \Omega(g) = O(g) \cap \Omega(f)$ \\
Lo primero que puedo ver es que si $ f \in \Omega(g)$ entonces g es una cota inferior de f. \\
Tomo algun ejemplo: $ f = n^{2} \land g = n$ \\
Veo si la fórmula se cumple o si hallamos un posible contraejemplo \\
$\implies O(n^{2}) \cap \Omega(n) = O(n) \cap \Omega(n^{2})$  \\
$\implies \{n, n^{2}\} = \varnothing$ \\
$\implies False$ \\
Luego, hallamos un contraejemplo. Por lo tanto, la afirmación es falsa. \\
\textbf{4. Demuestre si es verdadero o falso y justifique}: $f \in O(g) \iff O(f) \subseteq O(g)$ \\
$\implies)$ Por propiedad, sabemos que si $f \in O(g)$ entonces todo el conjunto de funciones que está acotado superiormente por f están en g. Es decir $O(f) \subseteq O(g)$ \\
$\leftarrow)$ Sabemos que por reflexividad, $f \in O(f)$ entonces si $O(f) \subseteq O(g)$ es cierto que $ f \in O(g)$ \\
\textbf{5. Demuestre si es verdadero o falso y justifique}: $nm = O(n+m)$ \\
Rotundamente falsa. \\
Contraejemplo: $n = n^{2} \land m = n^{3}$ pues $n^{5} \notin O(n^{3})$ \\
\textbf{6. Demuestre si es verdadero o falso y justifique}: $O(n^{2}) \cap \Omega(n) = \Theta(n^{2})$ \\
Falsa, pues $\{n^{2}, n\} \cap \{n, n^{2}\} = \{n^{2}, n\} \neq \Theta(n^{2}) $ \\
El problema radica que $\Theta(n^{2})$ es exactamente $n^{2}$ y acá tenemos n que está fuera de esa cota ajustada.


\subsection*{Complejidad}
\begin{lstlisting}
    void add(int mat1[n][n], mat2[n][n]){
        int ans[n][n];
            for(int i = 0; i < n; i++){
                for(int j = 0; j < n; j = j+1){
                    ans[i][j] = mat1[i][j] + mat2[i][j];
                }
            }
        return ans[0][0];
    }
\end{lstlisting}
$\textbf{Parte 1}$: Comenzamos colocando la cantidad de operaciones que se realizan, línea a línea. Los ciclos, en el caso del for, posee 3 casos: el caso inicial, caso intermedio, caso fin.
\begin{lstlisting}
    void add(int mat1[n][n], mat2[n][n]){
    0    int ans[n][n];
    2 2 2   for(int i = 0; i < n; i++){
    2 3 3       for(int j = 0; j < n; j = j+1){
    8               ans[i][j] = mat1[i][j] + mat2[i][j];
                }
            }
    3    return ans[0][0];
    }
\end{lstlisting}
Obs: j = j+1 $\neq$ j++ en temas de cantidad de operaciones. El j++ es una operación menos aunque hagan lo mismo.
Obs: El return funciona como una asignación, por lo tanto también cuenta en operaciones. \\
$\textbf{Parte 2}$: Elegimos si empezamos por el mejor, o el peor caso. El peor caso suele ser el más tedioso así que empecemos por ese. \\
$\textbf{Parte 2.1: Peor caso}$ \\
$\textbf{Parte 2.1.1 }$: Empezamos considerando el caso intermedio del ciclo.
\begin{lstlisting}
    2 3 3   for(int j = 0; j < n; j = j+1){
    8           ans[i][j] = mat1[i][j] + mat2[i][j];
            }
\end{lstlisting}
$ \sum_{j=0}^{n-1}{(8+3)} $ \\
Ahora consideramos el caso inicial del ciclo, y el final: $ 2 + \sum_{j=0}^{n}{(8+3)} + 3$ \\
Definimos:  $a \equiv 2 + \sum_{j=0}^{n-1}{(8+3)} + 3$ \\
$\textbf{Parte 2.1.2}$: 
\begin{lstlisting}
2 2 2   for(int i = 0; i < n; i++){
            a
        }
\end{lstlisting}
Comenzamos considerando el caso intermedio del ciclo.
$ \sum_{i=0}^{n}{(a+2)} $ \\
Ahora consideramos el caso inicial del ciclo, y el final:
$ 2 + \sum_{i=0}^{n}{(a+2)} + 2 $ \\ 
Definimos:  $b \equiv 2 + \sum_{i=0}^{n-1}{(a+2)} + 2 $ \\
$\textbf{Parte 2.1.3}$: Juntar ambos ciclos
$c \equiv 2 + \sum_{i=0}^{n-1}{((2 + \sum_{j=0}^{n-1}{(8+3)} + 3)+2)} + 2 $ \\ 
$\textbf{Parte 2.4}$: Resolver los ciclos, uniéndolos de alguna forma \\
$\equiv 2 + \sum_{i=0}^{n-1}{((2 + \sum_{j=0}^{n-1}{(\textbf{8+3})} + 3)+2)} + 2 $ \\ 
$\equiv 2 + \sum_{i=0}^{n-1}{((\textbf{2} + \sum_{j=0}^{n-1}{11} + \textbf{3})+2)} + 2 $ \\ 
$\equiv 2 + \sum_{i=0}^{n-1}{((\sum_{j=0}^{n-1}{\textbf{11}} + 5)+2)} + 2 $ \\ 
$\equiv 2 + \sum_{i=0}^{n-1}{((11 * \sum_{j=0}^{n-1}{1} + 5)+2)} + 2 $ \\
$\equiv \textbf{2} + \sum_{i=0}^{n-1}{((11 * n + 5)+2)} + \textbf{2} $ \\  
$\equiv 4 + \sum_{i=0}^{n-1}{(11 * n + 5+2)} $ \\  
$\equiv 4 + \sum_{i=0}^{n-1}{(11 * n + 7)} $ \\
$\equiv 4 + n * (11 * n + 7) $ \\    
$\equiv 4 + 11n^{2} + 7n $ \\   
$\textbf{Parte 2.1.5}$: Agregar el caso del return 
$\equiv 3 + 4 + 11n^{2} + 7n $ \\   
$\equiv 11n^{2} + 7n + 7 $ \\
$\textbf{Parte 2.1.6}$: Observar cual es la variable con mayor exponente.
En este caso, es $11n^{2}$ por lo tanto, $T{peor}(n) = \Theta(max\{11n^{2}, n, 7\})$. Luego,  
$T{peor}(n) = \Theta(n^{2})$ \\ 
Nota: En la materia no utilizan los números de operaciones, pero acá por ejemplo 2, 8, 3, 3, 2 (operaciones elementales) serían $\Theta(1)$, osea nuestro cálculo de la Parte 2.1.5 se vería así: $\Theta(n^{2}) + \Theta(n) + \Theta(1)$ \\ 
$\textbf{Parte 2.2: Mejor caso}$ \\ 
El mejor caso es igual al peor caso porque no tenemos restricciones del ciclo más que las matrices de entradas y tampoco tenemos ninguna condición de corte. Siempre se recorre la misma cantidad de veces.
\subsection*{Ejemplo 2 en cálculo de complejidad}
\begin{lstlisting}
   int russian(int a, int b){
        int res = 0;
        while(b > 0){
            if(b % 2 == 1){
                res = res + a;
            }
            a = a * 2;
            b = b/2;
        }
        return res;
   }
\end{lstlisting}
A simple vista podemos notar algo, estamos usando un while y la guarda depende de un b que desconocemos. Veamos como va variando la variable b; Se observa que se va dividiendo por dos, entonces es algo más rápido que hacer b-1. Seguramente, el peor caso sea logarítmico (como en búsqueda binaria que se va partiendo la lista en dos)
\newpage
\textbf{Parte 1}: Comenzamos colocando la cantidad de operaciones que se realizan, línea a línea. 
\begin{lstlisting}
    int russian(int a, int b){
        1    int res = 0;
        1    while(b > 0){
        2        if(b % 2 == 1){
        2           res = res + a;
                 }
        2        a = a * 2;
        2        b = b/2;
            }
        1   return res;
    }
 \end{lstlisting}
$\textbf{Parte 2}$: Elegimos si empezamos por el mejor, o el peor caso. El peor caso suele ser el más tedioso así que empecemos por ese. \\
$\textbf{Parte 2.1: Peor caso}$ \\
$\textbf{Parte 2.1.1}$: Observamos que nuestro peor caso es que b $>$ 0 y al dividir b por 2 sea impar. \\ Dentro del ciclo tenemos: (1 + (2+2) + 2 + 2) operaciones elementales. \\
Nótese que el 1 es de la condición de la guarda. \\ 
El ciclo es algo inverso, se comienza siendo algo muy grande y se va achicando, y el ciclo termina cuando b = 0. ¿Cuantas veces tengo que dividir b entre 2 para que podamos llegar a 0? El logaritmo base 2 de b, pero acá b lo llamamos n. \\ 
$\textbf{Parte 2.1.2}$: Utilizar logaritmo para hablar del ciclo \\
$\log(n)(1+(2+2) + 2 + 2)$ \\
Nótese que eliminamos la base 2 porque en complejidad, la base del logaritmo da igual.  \\
$\textbf{Parte 2.1.3}$: Considerar la asignación inicial y el return junto al ciclo \\ 
$1 + \log(n)(1+(2+2) + 2 + 2) + 1 \equiv 1 + \log(n)(8) + 1$ \\ 
\textbf{Parte 2.1.4}: Calcular la complejidad
$T_{peor}(n) = \Theta(1) + \Theta(log(n)) + \Theta(1) \equiv \Theta(max\{1, log(n), 1\}) \equiv \Theta(log(n)) $ \\
\textbf{Parte 2.2: Mejor caso} \\
Si b = 0 inicialmente, no entra nunca al ciclo por lo tanto no hay complejidad alguna porque todas son operaciones elementales. \\
$T_{mejor}(n) = \Theta(1) + \Theta(1) + \Theta(1) \equiv \Theta(max\{1, 1, 1\}) \equiv \Theta(1)$ \\
\subsection*{Ejemplo 3 en cálculo de complejidad}
\begin{lstlisting}
    function AlgoritmoQueHaceAlgo(arreglo A)
    int i : = 1; int j := 1;
    int suma := 1; int count := 0;
    while i <= tam(A) do 
        if i != A[i] do 
            count : = count + 1;
        end if 
        j := 1;
        while j <= count do 
            int k := 1;
            while k <= tam(A) do 
                suma := suma + A[k];
                k := k * 2;
            end while 
            j := j+1;
        endwhile 
        i := i + 1;
    endwhile
    return suma
\end{lstlisting}
Lo primero que comenzamos viendo cual es el peor caso de las variables. \\
El ciclo más de adentro con guarda k depende del tamaño de A, por lo tanto el ciclo itera máximo $log(|A|)$ veces (xq k se va duplicando en cada caso). \\
El ciclo con guarda $j <= count$ depende de una variable count. En el peor caso ¿qué valor toma count? bueno, count se incrementa en el peor caso hasta ser $count = |A|$. Una observación importante es que count crece igual que |A| pero el proceso lo hace pasando por i = 0, i = 1 SIEMPRE. \\
El ciclo más de afuera con guarda i depende del tamaño de A, por lo tanto el ciclo itera máximo $|A|$ veces (xq empieza desde i = 1). \\
Luego, quedaría algo así: \\
$ \Theta(1) + \Theta(1) + (\sum_{i=0}^{|A|}{\Theta(1) + \Theta(1) + \Theta(1) + (\sum_{j=1}^{i}{\Theta(1) + (\sum_{k=0}^{log(|A|)}{\Theta(1) + \Theta(1)}) + \Theta(1)})} + \Theta(1)) + \Theta(1)  $ \\
$ \equiv \Theta(1) + \Theta(1) + (\sum_{i=0}^{|A|}{\Theta(1) + \Theta(1) + \Theta(1) + (\sum_{j=1}^{i}{log(|A|) \ast \Theta(1)})} + \Theta(1)) + \Theta(1) $ \\ 
$ \equiv \Theta(1) + \Theta(1) + (\sum_{i=0}^{|A|}{\Theta(1) + \Theta(1) + \Theta(1) + (\sum_{j=1}^{i}{log(|A|) \ast \Theta(1)})} + \Theta(1)) + \Theta(1) $ \\ 
$ \equiv \Theta(1) + \Theta(1) + (\sum_{i=0}^{|A|}{\Theta(1) + \Theta(1) + \Theta(1) + i * log(|A|)} + \Theta(1)) + \Theta(1) $ \\ 
$ \equiv \Theta(1) + (\sum_{i=0}^{|A|}{i * log(|A|)}) \leftarrow $ Como i depende del ciclo, lo dejo adentro pero saco lo demás hacia afuera.  \\ 
$ \equiv \Theta(1) + (log(|A|) * \sum_{i=0}^{|A|}{i}) $ \\ 
$ \equiv \Theta(1) + log(|A|) * |A|(|A|+1)/2  $ \\ 
$ \equiv log(|A|) * |A|^{2}/2 + |A|/2  $ \\ 
$ \equiv log(|A|) * |A|^{2}/2 + log(|A|) * |A|/2   $ \\ 
$ \equiv log(|A|) * |A|^{2} + log(|A|) * |A|  \leftarrow $ Saco denominadores, son constantes. \\ 
$ \equiv log(|A|) * |A|^{2} $ \\ 
$ \equiv \Theta(log(|A|) * |A|^{2}) $ \\
Conclusión: Es importante revisar que si el ciclo depende de una guarda como $ j \le count$ revisar como va creciendo count; como count depende del valor de i, i va siendo 1, 2, 3, 4, osea que no sucede una sola vez y no podemos generalizar. El peor caso sería que i pase por 1, 2, 3, 4, hasta tam(A), entonces el ciclo que depende de count se ejecuta 1 vez, despues 2 veces, después 3 y así.
\subsection*{Ejemplo 3 en cálculo de complejidad}
Recuerdo:
\begin{itemize}
    \item $\Theta(n)$: Cota ajustada, exactamente n. 
    \item $\Omega(n)$: Funciones mayores a n.
    \item $O(n)$: Funciones menores a n.
    \item c: Variable real mayor a 0. Nos basta con que exista una. 
    \item n: Mayor a n0 donde ambas son naturales, donde n es suficientemente grande.
\end{itemize}
Determine la verdad o falsedad de las siguientes afirmaciones: \\ \\ 
\textbf{1.} $ 2^{n} = O(1) $ \\
Para empezar, la igualdad de una función con un grupo de funciones significa lo siguiente $ 2^{n} \le c \ast 1 $ \\ 
Luego, $ 2^{n} = c $ es claramente es falso. \\ 
Contraejemplo: $ n = 4, 2^4 \neq O(1)$ \\ \\
\textbf{2.} $ n = O(n!) $ \\
Esperaría que sea verdadero porque es cierto que el conjunto de funciones menores a n! incluye a n.
$ n \le c * n!$ \\
$ n \le c * (n-1)! * n$ \\
$ 1 \le c * (n-1)! \leftarrow $ trivialmente verdadero para n suficientemente grande y c mayor que cero.\\ \\
\textbf{3.} $ n+m = O(nm) $ \\
Sabemos que n y m son dos valores de salida de una función. Parecería verdadero que una multiplicación de dos cosas incluya a la suma de ambas. \\
$ n+m \le c * nm $ \\
$ n/nm + m/nm \le c $ \\
$ 1/m + 1/n \le c \leftarrow $ trivialmente verdadero porque un $c>0$ siempre va a ser mayor a dos racionales que tienden a 0. \\ \\ 
\textbf{4.} $ f \in O(log \ n) \ entonces \ f \in O(n) $ \\
Esto es trivialmente verdadero a la vista porque sabemos que si f es una función que es menor a O(log n) entonces obligatoriamente f es menor a O(n) por transitividad $ \implies f \le O(log \ n) \le O(n) $ \\ \\  
$ f \in O(log \ n) \equiv f \le c * log(n), \ f \in O(n) \equiv f \le c * n $ \\
$ \implies f \le c * log(n) \implies f \le c * n $ \\
$ \implies c * log(n) \le c * n $ \\
$ \implies log(n) \le n \leftarrow $ trivialmente verdadero.
\newpage
\subsection*{Ejemplos en vida real de complejidades}
\label{subsec:ejemplos_complejidad_reales}
\textbf{1. En una agenda cada actividad tiene un identificador, un horario de inicio y uno de finalización. Las actividades solo pueden comenzar y terminar en horarios en punto. Se pide la hora más ocupada en un día dado}
A simple vista, puede parecer que dado un día de tipo entero, buscar la hora podría ser n, pues los días tienen 24 hs y deberíamos iterar toda una lista por ejemplo. Lo importante acá, es que como los días están acotados a 24hs y nunca van a ser más, un array de 24 posiciones sería $O(1)$ en el peor caso. Esto es porque cuando hablamos de complejidad, la complejidad se calcula en base a un n variable, y acá nuestro arreglo siempre es fijo con la misma longitud. \\
\textbf{2. Se pide implementar un registro de personas, pero por limitaciones del sistema, solo podemos ingresar un máximo de 100 caracteres entre nombre y apellido. ¿Qué estructura usaría, y qué complejidad tiene el peor caso?}
La estructura a utilizar es un Trie pues más de una persona puede contener caracteres en común en el nombre y apellido con otra. El costo de buscar a cualquier persona es $O(1)$ porque la complejidad e buscar en un Trie donde las palabras no están acotadas es $O(|n|)$ pero en este caso, al saber que todas pueden tener máximo 100 caracteres, el costo es $O(1)$.
\subsection*{Single Linked List - Complejidad - Implementación}
\label{subsec:complejidad_modulo_sll}
\begin{lstlisting}
    Struct NodoLista<T> {
        prev: NodoLista<T>
        sig: NodoLista<T>
        val: T
    }

    Módulo LinkedList<T> implementa Secuencia<T> {
        var primero: NodoLista<T>
        var ultimo: NodoLista<T>
        var longitud: int

        Costo peor caso / mejor caso = O(1) xq ya tengo primer puntero y lo peor que tengo que hacer es reordenar 1 solo. 
        proc agregarAdelante(inout l: LinkedList<T>, in e: T) {
            var nuevoNodo: NodoLista<T> = new NodoLista<T>(e);
            var primeroAnt: NodoLista<T> = l.primero;
            nuevoNodo.sig = primeroAnt;
            l.primero = nuevoNodo;
            if(l.longitud == 0){
                l.ultimo = nuevoNodo; 
            }
            l.longitud+=1;
        }

        Costo peor caso / mejor caso = O(1) xq ya tengo el último puntero y lo peor que tengo que hacer es reordenar 1 solo.
        proc agregarAtras(inout l: LinkedList<T>, in e: T){
            if(l.longitud == 0) then
                agregarAdelante(l, e);
            else
                var nuevoNodo: NodoLista<T> = new NodoLista<T>(e);
                var anteriorUlt: NodoLista<T> = l.ultimo; 
                anteriorUlt.sig = nuevoNodo; 
                l.ultimo = nuevoNodo; 
            endif
        }
        
        proc buscar(in l: LinkedList<T>, in e: T): T {
            // Si e == l.primero.val -> costo O(1)
            //Si e NO es el primero, entonces -> costo O(n)

            Aunque tenga el último guardado, no puedo sacarlo como caso aparte porque para calcular la complejidad tendría que aíslar los casos del primero y el último y es un quilombo.
        }
    }
\end{lstlisting}
\subsection*{Rotaciones según desbalance de AVL}
\label{subsec:rotaciones_avl}
\begin{center}
    \begin{minipage}[b]{0.9\textwidth}
        \includegraphics[width=\linewidth]{assets/rotaciones_avl_casos.jpg}
        \centering
        \label{fig:rotaciones_avl_casos}
    \end{minipage}
\end{center}
\subsection*{Elección de estructura para Cola de Prioridad}
\label{subsec:cola_de_prioridad_avl}
La mejor forma y más rápida de implementar una cola de prioridad sería con un árbol AVL. Esto nos garantiza que la búsqueda en el peor caso es O(log n). \\
Además, las inserciones podrían ser en tiempo logarítmico y los borrados también. \\
Una mejor solución y más elegante (que no nos mejora nada en temas de complejidad) podría ser usando Heaps. \\
Nota: El AVL es bueno cuando usamos diccionarios; pero si no usamos diccionarios para la cola de prioridad, en este caso es mejor usar Heaps.
\subsection*{Operaciones Heaps}
\label{subsec:operaciones_heaps}
\textbf{Inserción}:
\begin{center}
    \begin{minipage}[b]{0.5\textwidth}
        \includegraphics[width=\linewidth]{assets/insertando_heaps.jpg}
        \centering
        \label{fig:insertando_en_heaps}
    \end{minipage}
\end{center}
\textbf{Desencolar / Borrar}:
\begin{center}
    \begin{minipage}[b]{0.5\textwidth}
        \includegraphics[width=\linewidth]{assets/borrar_heaps.jpg}
        \centering
        \label{fig:borrar_heaps}
    \end{minipage}
\end{center}
Nota: Nótese que es importante si está implementando un max-heap o un min-heap, porque en el max-heap tenemos que reacomodar de manera que quede en la raíz el más grande mientras que en el min-heap tenemos que dejar el más chico.
\subsection*{Implementacion de Heaps de maneras diversas}
\label{subsec:implementaciones_heap}
\textbf{Sobre Array}
Sabemos que un Heap es lo más cercano a ser implementado con árboles binarios balanceados. \\ 
Consideremos que debemos implementarlo con un array ¿como lo haríamos? \\
La manera de representarlo en un array es: raiz - hijo izq - hijo der - hijo izq de hijo izq, hijo der de hijo izq - hijo izq de hijo der, hijo der de hijo der. \\
Es como que vas tomando misma altura, pero completas primero con izquierda y luego derecha. \\
Fórmula (invariante): 
\begin{itemize}
    \item si v es la raiz, entonces v es el primero del arreglo.
    \item si v es el hijo izquierdo de u entonces 2p(u)+1
    \item si v es el hijo derecho de u entonces 2p(u)+2
\end{itemize}
\begin{center}
    \begin{minipage}[b]{0.6\textwidth}
        \includegraphics[width=\linewidth]{assets/heap.png}
        \centering
        \label{fig:heap}
    \end{minipage}
\end{center}
Transformado a array sería: $[89, 67, 68, 66, 65, 66, 67, 1, 43, 21, 5, 4, 64]$ \\
Ventajas de implementar Heap con Array: 
\begin{itemize}
    \item Ventajas:
    \begin{itemize}
        \item Muy eficiente en términos de espacio.
        \item Es fácil de navegar.
    \end{itemize}
    \item Desventajas:
    \begin{itemize}
        \item Al ser un arreglo, es necesario duplicar el arreglo o achicarlo a medida que se agregan o eliminan elementos.
    \end{itemize}
\end{itemize}
\subsection*{Array $\rightarrow$ Heap (Array2Heap)}
\label{subsec:array_2_heap}
\begin{itemize}
    \item Forma 1 (Costo $\theta(n \ log(n))$): Permutando sus elementos, hasta llevarlo a un heap y que cumpla el invariante de representación. Si no recuerda qué reglas debe cumplir el array, véase \hyperref[subsec:implementaciones_heap]{\underline{implementaciones heap}}.
    \item Forma 2 (Costo $\theta(n)$), Algoritmo de Floyd: Estrategia bottom-up. Desde el último sub-heap de la derecha, voy viendo si cada uno son un heap válido, si no lo son aplico la operación bajar en el elemento padre de ese sub-heap. Si ya llegué al último sub-heap de la izquierda, vuelvo a la derecha pero voy al padre del último padre de la derecha.
\end{itemize}
\subsection*{Casos de uso Trie}
\label{subsec:operaciones_trie}
\textbf{1. Inscribir al estudiante en la materia m de la carrera c $\rightarrow O(|c| + |m|)$ siendo la carrera y materia strings.} \\
Lo primero que hay que notar es que carrera y materia al ser strings, seguramente muchas carreras y materias compartan caracteres entre sí. La segunda pista que tenemos que es las complejidades hablan de longitud de carreras y materias, por lo tanto podemos concluir que dentro del Trie de carreras, el significado de cada carrera es un nuevo Trie pero de materias y el peor caso es $O(|c| + |m|)$\\
\textbf{2. En cada actividad se pueden agregar tags que permiten agrupar las distintas actividades por temáticas. Los tags tienen cómo máximo 20 caracteres}
Lo primero hay que notar es que nos hablan de caracteres, y una longitud fija. En este caso, podemos darnos cuenta que los tags podrían compartir caracteres entre sí. \\
Un ejemplo podría ser el tag important y el tag importante. Ambas comparten muchos caracteres entre sí. \\
La siguiente pista es que la longitud está acotada, así que podemos concluir que efectivamente es un Trie que recorrer en el peor caso cuesta $O(1)$.
\textbf{3. Por restricciones del sistema de la biblioteca, un socio no puede registrarse con un nombre de más de 50 caracteres}
Mismo caso que el anterior, es un trie porque los socios pueden compartir caracteres entre sí, y el peor caso es $O(1)$ porque la cantidad de caracteres está fija.
\end{document}