Conceptos Fundamentales de Algoritmos y Estructuras de Datos

JUL

2025

Portada » Informática » Conceptos Fundamentales de Algoritmos y Estructuras de Datos

Conceptos Fundamentales de Algoritmos y Estructuras de Datos

by estudiapuntes

algoritmos, complejidad algorítmica, estructuras de datos, tablas de dispersión

Tabla de Dispersión Cerrada

En una tabla de dispersión cerrada, los elementos se almacenan directamente en el arreglo. Cuando ocurre una colisión, se utiliza una función de resolución para encontrar la siguiente posición disponible.

Tipo de Datos

tipo
  ClaseDeEntrada = (legítima, vacía, borrada);
  Indice = 0 .. N-1;
  Posicion = Indice;
  Entrada = registro
    Elemento: TipoElemento;
    Información: ClaseDeEntrada;
  fin registro;
TablaDispersion = vector [Indice] de Entrada;

Procedimiento InicializarTabla (D)

procedimiento InicializarTabla (D)
  para i := 0 hasta N-1 hacer
    D[i].Información := vacía;
  fin para;
fin procedimiento;

Función Buscar (Elem, D): Posición

función Buscar (Elem, D): Posición
  i := 0;
  x := Dispersión(Elem);
  PosActual := x;
  mientras D[PosActual].Información <> vacía y
          D[PosActual].Elemento <> Elem hacer
    i := i + 1;
    PosActual := (x + FunResoluciónColisión(x, i)) mod N;
  fin mientras;
  devolver PosActual;
fin función;

Procedimiento Insertar (Elem, D)

procedimiento Insertar (Elem, D)
  pos := Buscar(Elem, D);
  si D[pos].Información <> legítima entonces <em>{Bueno para insertar}</em>
    D[pos].Elemento := Elem;
    D[pos].Información := legítima;
  fin si;
fin procedimiento;

Procedimiento Eliminar (Elem, D)

procedimiento Eliminar (Elem, D)
  pos := Buscar(Elem, D);
  si D[pos].Información = legítima entonces
    D[pos].Información := borrada;
  fin si;
fin procedimiento;

Funciones de Resolución de Colisiones

Función FunResoluciónColisión (x, i): Posición (Exploración Lineal)

función FunResoluciónColisión (x, i): Posición
  <em>/* Para exploración lineal */</em>
  devolver i;
fin función;

Función FunResoluciónColisión (x, i): Posición (Exploración Cuadrática)

función FunResoluciónColisión (x, i): Posición
  <em>/* Para exploración cuadrática */</em>
  aux := i^2;
  devolver aux;
fin función;

Función FunResoluciónColisión (x, i, y): Posición (Exploración Doble)

función FunResoluciónColisión (x, i, y): Posición
  <em>/* Para exploración doble */</em>
  aux := y - (x mod y);
  devolver aux;
fin función;

Conjuntos Disjuntos

Los conjuntos disjuntos son una estructura de datos que mantiene una colección de elementos particionados en un número de subconjuntos disjuntos.

Tipo de Datos

tipo
  Elemento = entero;
  Conj = entero;
  ConjDisj = vector [1..N] de entero;

Procedimiento Unir (C, raiz1, raiz2)

procedimiento Unir (C, raiz1, raiz2)
  si raiz1 < raiz2 entonces C[raiz2] := raiz1
  sino C[raiz1] := raiz2;
fin procedimiento;

Función Buscar (C, x): Conj

función Buscar (C, x): Conj
  r := x;
  mientras C[r] <> r hacer
    r := C[r];
  fin mientras;
  devolver r;
fin función;

Compresión de Caminos en Conjuntos Disjuntos

La compresión de caminos es una optimización utilizada en la operación <code>Buscar</code> de la estructura de datos de conjuntos disjuntos para aplanar la estructura del árbol, mejorando la eficiencia de futuras búsquedas.

Función Buscar con Compresión de Caminos (C, x): Conj

función BuscarConCompresion (C, x): Conj
  r := x;
  mientras C[r] <> r hacer
    r := C[r];
  fin mientras;
  i := x;
  mientras i <> r hacer
    j := C[i];
    C[i] := r;
    i := j;
  fin mientras;
  devolver r;
fin función;

Análisis de Complejidad

La complejidad de las operaciones con compresión de caminos es casi constante, específicamente O(α(n)), donde α es la función inversa de Ackermann, que crece extremadamente lento.

La nota original «Complejidad O(m*n), ya que por cada una de esas «m» búsquedas, hay «n» uniones.» parece referirse a un contexto diferente o ser un error, ya que la compresión de caminos mejora drásticamente la complejidad. Mantendré la corrección para la compresión de caminos.

Comparación de Algoritmos: Kruskal, Prim y Dijkstra

Estos tres algoritmos son fundamentales en la teoría de grafos para resolver problemas de caminos mínimos y árboles de expansión mínima.

	Inicialización	Selección	Solución
<strong>Kruskal</strong>	<ul> <li>T inicialmente vacío.</li> <li>Almacena aristas seleccionadas.</li> <li>(N, T) define un conjunto de componentes conexas.</li> </ul>	Arista más corta que no forma ciclo.	T → Árbol de Expansión Mínima
<strong>Prim</strong>	<ul> <li>T inicialmente vacío.</li> <li>Almacena nodos seleccionados.</li> <li>B = nodo seleccionado aleatoriamente.</li> </ul>	Arista más corta partiendo de un nodo en B a uno fuera de B.	T → Árbol de Expansión Mínima del subgrafo (B, A)
<strong>Dijkstra</strong>	<ul> <li>C → conjunto de nodos candidatos.</li> <li>Distancias inicializadas (0 para origen, ∞ para otros).</li> </ul>	Menor distancia de nodo ‘x’ a sus vecinos no visitados.	S → Camino establecido como mínimo desde el origen a todos los nodos.

Ordenación Topológica

La ordenación topológica es una ordenación lineal de los vértices de un grafo acíclico dirigido (DAG) tal que para cada arista dirigida uv del grafo, el vértice u viene antes que v en la ordenación.

Función OrdenaciónTopológica (G: grafo): orden[1..n]

función OrdenaciónTopológica (G: grafo): orden[1..n]
  GradoEntrada[1..n] := CalcularGradoEntrada(G);
  para i := 1 hasta n hacer
    NumeroTopologico[i] := 0;
  fin para;
  contador := 1;
  mientras contador <= n hacer
    v := BuscarNodoGradoCeroSinAsignar();
    si v no encontrado entonces
      devolver error "El grafo tiene un ciclo";
    sino
      NumeroTopologico[v] := contador;
      incrementar contador;
      para cada w adyacente a v hacer
        GradoEntrada[w] := GradoEntrada[w] - 1;
      fin para;
    fin si;
  fin mientras;
  devolver NumeroTopologico;
fin función;

Análisis de Complejidad

<ul>
<li>Complejidad: O(n+m) con listas de adyacencia.</li>
<li>Peor Caso: Grafo denso [m → n(n-1)] y visita todas las aristas.</li>
<li>Mejor Caso: Grafo disperso [m → 0, m → n].</li>
</ul>

Composición

Este algoritmo parece resolver un problema de optimización, posiblemente relacionado con la selección de elementos o la devolución de cambio, utilizando una matriz de programación dinámica.

Función Composición (M[1..n,0..m], V[1..n]): C[1..n]

función Composición (M[1..n,0..m], V[1..n]): C[1..n]
  para i := 1 hasta n hacer C[i] := 0; <em>{Corregido C[j] a C[i]}</em>
  v := M[n,m];
  i := n; j := m;
  mientras i > 1 y v > 0 hacer
    si M[i,j] <> M[i-1,j] entonces
      C[i] := C[i] + 1;
      j := j - V[i];
      v := M[i,j];
    sino
      i := i - 1;
    fin si;
  fin mientras;
  si v > 0 entonces C[1] := C[1] + 1;
  fin si;
  devolver C;
fin función;

Análisis de Complejidad

T(n) = Θ(mn)

Problema Relacionado: Conjunto de Monedas

<ul>
<li>Algoritmo Voraz: Recorrido de camino c[m,n] → c[0,0]</li>
<li>m pasos hacia arriba: Implica «no utilizar más vi»</li>
<li>+c[m,n] «saltos» hacia la izquierda: Implica «utilizar una vi más»</li>
<li>Complejidad Adicional: Θ(m + c[m,n]) adicional a la construcción de la tabla.</li>
</ul>

Identificación de Funciones en Problemas Algorítmicos

En el diseño de algoritmos, especialmente los voraces, es útil identificar las funciones clave que definen su comportamiento.

a) Problema del Cambio o Devolución

<ul>
<li>Función Objetivo: Minimizar el número de monedas necesarias para dar el cambio exacto.</li>
<li>Función de Selección: Elegir la moneda de mayor valor que no supere el importe restante.</li>
<li>Función Factible: Comprobar que la moneda seleccionada no excede la cantidad de cambio que queda por dar.</li>
<li>Función de Solución: Se alcanza una combinación de monedas cuya suma es exactamente igual al valor del cambio.</li>
</ul>

b) Problema de la Mochila con Objetos Fraccionables

<ul>
<li>Función Objetivo: Maximizar el valor total de los objetos introducidos en la mochila.</li>
<li>Función de Selección: Elegir el objeto con la mejor relación valor/peso.</li>
<li>Función Factible: Comprobar que queda capacidad en la mochila para introducir el objeto total o parcialmente.</li>
<li>Función de Solución: Se completa la mochila (se alcanza su capacidad máxima) o no quedan objetos disponibles.</li>
</ul>

c) Cálculo del Árbol de Expansión Mínima

<ul>
<li>Función Objetivo: Minimizar la suma total de los pesos de las aristas del árbol.</li>
<li>Función de Selección: Escoger la arista de menor peso que conecte un nodo del árbol con otro que aún no esté incluido (en Prim) o que no forme un ciclo (en Kruskal).</li>
<li>Función Factible: Comprobar que la arista seleccionada no forma ciclos y es válida para ampliar el árbol.</li>
<li>Función de Solución: Se han incluido exactamente (n – 1) aristas y el árbol conecta todos los vértices del grafo.</li>
</ul>

Búsqueda Binaria

La búsqueda binaria es un algoritmo eficiente para encontrar un elemento en una lista ordenada de elementos. Funciona dividiendo repetidamente a la mitad la porción de la lista que podría contener el elemento, hasta reducir las ubicaciones posibles a solo una.

Análisis de Complejidad

<ul>
<li>Peor Caso: Es el mismo que el caso promedio.</li>
<li>Recurrencia: T(n) = { 1 si n = 0, 1; T(n/2) + 1 si n > 1 } ⇒ T(n) = O(log n)</li>
<li>Mejor Caso: Ocurre cuando el elemento buscado se encuentra en la primera iteración (el elemento del medio). Por lo tanto, es O(1).</li>
</ul>

Ordenación Rápida con Pivote Aleatorio (Quicksort)

Quicksort es un algoritmo de ordenación eficiente basado en la estrategia «divide y vencerás». Selecciona un elemento como «pivote» y particiona el resto de la lista en dos sublistas, según si sus elementos son menores o mayores que el pivote.

Procedimiento OrdenarAux (V[izq..der])

procedimiento OrdenarAux (V[izq..der])
  si izq <= der entonces <em>{Corregido UMBRAL a una condición más general}</em>
    x := número aleatorio en el rango [izq..der];
    pivote := V[x];
    intercambiar (V[izq], V[x]);
    i := izq + 1;
    j := der;
    mientras i <= j hacer
      mientras i <= der Y V[i] < pivote hacer
        i := i + 1;
      fin mientras;
      mientras V[j] > pivote hacer
        j := j - 1;
      fin mientras;
      si i <= j entonces
        intercambiar (V[i], V[j]);
        i := i + 1;
        j := j - 1;
      fin si;
    fin mientras;
    intercambiar (V[izq], V[j]);
    OrdenarAux (V[izq..j-1]);
    OrdenarAux (V[j+1..der]);
  fin si;
fin procedimiento;

Procedimiento OrdenaciónRápida (V[1..n])

procedimiento OrdenaciónRápida (V[1..n])
  OrdenarAux(V[1..n]);
  si (UMBRAL > 1) entonces <em>{UMBRAL se refiere a un tamaño mínimo para usar Quicksort, y luego cambiar a Inserción}</em>
    OrdenaciónPorInsercion (V[1..n]);
  fin si;
fin procedimiento;

Análisis de Complejidad

<ul>
<li>Peor Caso: T(n) = O(n²), cuando el pivote es siempre el menor o el mayor elemento.</li>
<li>Mejor Caso: T(n) = O(n log n), cuando el pivote siempre coincide con la mediana.</li>
</ul>

Máquina de Turing y Clases de Complejidad (P vs NP)

La teoría de la complejidad computacional clasifica los problemas computacionales según los recursos (tiempo y espacio) necesarios para resolverlos. Las clases P y NP son fundamentales en este campo.

<ul>
<li>Se cree que P ≠ NP, pero hasta ahora no se ha logrado demostrarlo.</li>
<li>Si efectivamente P ≠ NP, nunca encontraremos soluciones polinómicas al problema de las sumas de subconjuntos, porque sabemos que no existen.</li>
<li>Si P = NP, existirán soluciones polinómicas al problema de las sumas de subconjuntos y todos los demás problemas de NP.</li>
</ul>

Problema de Satisfacibilidad Booleana (SAT)

El problema SAT (Satisfiability) es un problema de decisión en lógica booleana que pregunta si las variables de una fórmula booleana pueden ser asignadas de tal manera que la fórmula sea verdadera.

Como SAT es NP-Completo, es uno de los problemas más difíciles de la clase NP. Si existe un algoritmo polinómico para resolver SAT, entonces todos los problemas de NP pueden resolverse también en tiempo polinómico (por las reducciones polinómicas). Por lo tanto, P sería igual a NP, resolviendo uno de los mayores problemas abiertos de la informática.

Divide y Vencerás

La estrategia «Divide y Vencerás» es un paradigma de diseño de algoritmos que consiste en resolver un problema grande dividiéndolo en subproblemas más pequeños del mismo tipo, resolviendo estos subproblemas de forma recursiva y luego combinando sus soluciones para obtener la solución del problema original.

Ordenación Topológica Usando Cola (Algoritmo de Kahn)

Una alternativa a la ordenación topológica basada en DFS es el algoritmo de Kahn, que utiliza una cola para procesar los nodos en orden de grado de entrada.

a) Implementación con Cola

función OrdenaciónTopológicaKahn(G: grafo): orden[1..n]
  GradoEntrada[1..n] := CalcularGradoEntrada(G);
  Cola := ColaVacia();
  para i := 1 hasta n hacer
    NumeroTopologico[i] := 0;
  fin para;
  contador := 0;
  para cada v en G hacer
    si GradoEntrada[v] = 0 entonces
      Cola.InsertarEnCola(v);
    fin si;
  fin para;

  mientras Cola no esté vacía hacer
    v := Cola.QuitarPrimero();
    NumeroTopologico[v] := contador;
    incrementar contador;

    para cada w adyacente a v hacer
      GradoEntrada[w] := GradoEntrada[w] - 1;
      si GradoEntrada[w] = 0 entonces
        Cola.InsertarEnCola(w);
      fin si;
    fin para;
  fin mientras;

  si contador &#x2260; n entonces
    devolver error "El grafo tiene un ciclo";
  fin si;

  devolver NumeroTopologico;
fin función;

b) Eficiencia del Enfoque con Cola

La eficiencia en el acceso a los nodos es notable. El uso de una cola permite seleccionar nodos de grado 0 de forma directa, sin necesidad de recorrer toda la lista de nodos. Esto contribuye a una complejidad temporal de O(V + E), donde V es el número de vértices y E el número de aristas.

c) Implementación con DFS (Búsqueda en Profundidad)

función OrdenaciónTopológicaDFS(G: grafo): orden[1..n]
  visitados[1..n] := falso;
  pila := PilaVacia();

  función DFS(v)
    visitados[v] := Verdadero;
    para cada w en Adyacentes(v) hacer
      si no visitados[w] entonces
        DFS(w);
      fin si;
    fin para;
    pila.InsertarEnPila(v);
  fin función;

  para cada nodo v en G hacer
    si no visitados[v] entonces
      DFS(v);
    fin si;
  fin para;

  pila.Invertir(); <em>{La pila contiene los nodos en orden topológico inverso}</em>
  devolver pila;
fin función;

d) Ventajas del Enfoque con DFS

<ul>
<li>Eficiencia en grafos dispersos: Adecuado para grafos con pocas aristas.</li>
<li>Simplificación en la detección de ciclos: Los ciclos se detectan si se visita un nodo ya en el camino actual de DFS.</li>
<li>Memoria optimizada: Generalmente requiere menos memoria que el enfoque basado en grados de entrada para ciertos tipos de grafos.</li>
</ul>

Comparación: Ordenación por Fusión (Mergesort) vs. Ordenación Rápida (Quicksort)

Ambos algoritmos son ejemplos clásicos de la estrategia «Divide y Vencerás» para la ordenación de datos.

<strong>Criterio</strong>	<strong>Ordenación por Fusión (Mergesort)</strong>	<strong>Ordenación Rápida (Quicksort)</strong>
Técnica de diseño	Divide y vencerás	Divide y vencerás
Estrategia principal	Divide el problema en subproblemas de igual tamaño y fusiona resultados.	Divide el problema con un pivote y particiona en subproblemas.
Método de Subinstancias	Divide el arreglo en 2 mitades iguales, resolviendo cada una de manera independiente y combinando los resultados al final.	Divide el arreglo alrededor de un pivote aleatorio, separando los elementos menores y mayores con respecto al pivote.
Cantidad/Tamaño de Subinstancias	Siempre se crean 2 subinstancias de tamaño aproximadamente n/2 en cada llamada recursiva.	Se crean 2 subinstancias, pero su tamaño depende de la posición del pivote.
Método de Solución	Combina las sublistas ordenadas mediante la operación de fusión, comparando elementos de ambas mitades.	No se requiere combinación, ya que la ordenación ocurre «en su lugar» dividiendo los elementos con respecto al pivote.
Estrategia Base	Si el tamaño de las sublistas es 1, se retorna directamente sin más procesamiento.	Si el tamaño de las sublistas es 0 o 1, se retorna sin más procesamiento.
Caso promedio	Θ(n log n)	Θ(n log n)
Peor caso	Θ(n log n)	Θ(n²) (si el pivote es mal seleccionado)
Mejor caso	Θ(n log n)	Θ(n log n) (si el pivote es bien seleccionado)
Espacio Adicional	O(n) (requiere un arreglo auxiliar para la fusión)	O(log n) en promedio (por la pila de recursión), O(n) en el peor caso.

Árbol Binario de Búsqueda (ABB)

Un Árbol Binario de Búsqueda es una estructura de datos de árbol en la que cada nodo tiene como máximo dos hijos. Para cada nodo, todos los elementos en su subárbol izquierdo son menores que el nodo, y todos los elementos en su subárbol derecho son mayores.

Tipo de Datos

tipo
  PNodo = ^Nodo;
  Nodo = registro
    Elemento: TipoElemento;
    Izquierdo, Derecho: PNodo;
  fin registro;
ABB = PNodo;

Procedimiento OrdenPorNivel (A)

Este procedimiento realiza un recorrido por niveles (BFS) en un Árbol Binario de Búsqueda, utilizando una cola.

procedimiento OrdenPorNivel (A)
  CrearCola(C);
  si A &#x2260; nil entonces InsertarEnCola(A, C);
  mientras no ColaVacia(C) hacer
    p := QuitarPrimero(C);
    escribir(p^.Elemento); <em>{Operación principal}</em>
    si p^.Izquierdo &#x2260; nil entonces InsertarEnCola(p^.Izquierdo, C);
    si p^.Derecho &#x2260; nil entonces InsertarEnCola(p^.Derecho, C);
  fin mientras;
fin procedimiento;

Tipo de Datos: Cola

tipo Cola = registro
  CabeceraDeCola, FinalDeCola: 1..TamañoMaximoDeCola;
  TamañoDeCola: 0..TamañoMaximoDeCola;
  VectorDeCola: vector [1..TamañoMaximoDeCola] de TipoDeElemento;
fin registro;

Procedimiento CrearCola (C) {O(1)}

procedimiento CrearCola (C)
  C.TamañoDeCola := 0;
  C.CabeceraDeCola := 1;
  C.FinalDeCola := TamañoMaximoDeCola;
fin procedimiento;

Función ColaVacia (C): Booleano {O(1)}

función ColaVacia (C): Booleano
  devolver C.TamañoDeCola = 0;
fin función;

Procedimiento Incrementar (x) {Privado, O(1)}

procedimiento Incrementar (x)
  si x = TamañoMaximoDeCola entonces x := 1
  sino x := x + 1;
fin procedimiento;

Procedimiento InsertarEnCola (x, C) {O(1)}

procedimiento InsertarEnCola (x, C)
  si C.TamañoDeCola = TamañoMaximoDeCola entonces
    error "Cola llena";
  sino
    C.TamañoDeCola := C.TamañoDeCola + 1;
    Incrementar(C.FinalDeCola);
    C.VectorDeCola[C.FinalDeCola] := x;
  fin si;
fin procedimiento;

Algoritmo de Kruskal

El algoritmo de Kruskal es un algoritmo para encontrar un Árbol de Expansión Mínima (AEM) en un grafo conexo y ponderado. Es un algoritmo voraz que construye el AEM añadiendo aristas de menor peso que no formen ciclos.

a) Tipo de Datos de Salida

El tipo de datos de salida de la función {t} es un Árbol de Expansión Mínima (AEM), que es un subgrafo acíclico que conecta todos los vértices con el menor peso total de aristas.

b) Reescritura con Montículo

Para optimizar la selección de la arista más corta, se puede utilizar un montículo de mínimos (min-heap). Las instrucciones {2} y {3} se reescribirían así:

{2}: M := CrearMontículoDeAristas(A); <em>{Se insertan todas las aristas en el montículo, ordenadas por peso}</em>
{3}: arista_minima := EliminarMin(M); <em>{Se extrae la arista de menor peso del montículo}</em>

c) Problema Resuelto por Kruskal

El algoritmo de Kruskal resuelve el problema de encontrar un Árbol de Expansión Mínima (AEM) en un grafo conexo y ponderado. Su objetivo es seleccionar un subconjunto de aristas que conecte todos los vértices del grafo, sin formar ciclos, y cuya suma total de pesos sea la mínima posible.

d) Elementos Característicos de la Técnica Voraz

<ul>
<li>Inicialización: El conjunto de aristas del árbol (T) está inicialmente vacío.</li>
<li>Invariante: En cada paso, el conjunto {N, T} define un conjunto de componentes conexas, y todas las aristas en T son parte de un AEM.</li>
<li>Condición de Finalización: Se alcanza cuando solo queda una componente conexa, que es el Árbol de Expansión Mínima.</li>
<li>Criterio de Selección: Se elige la arista de menor peso que no forme un ciclo con las aristas ya seleccionadas.</li>
</ul>

e) Análisis de Complejidad

Considerando |N|=n (número de vértices) y |A|=m (número de aristas):

<ul>
<li>Ordenación de Aristas: O(m log m) = O(m log n), ya que n – 1 ≤ m ≤ n(n-1)/2.</li>
<li>Inicialización de Conjuntos Disjuntos: Θ(n).</li>
<li>Operaciones de Conjuntos Disjuntos: 2m operaciones de búsqueda (peor caso) y n – 1 operaciones de unión, resultando en O(m α(m, n)), donde α es la función inversa de Ackermann, que es prácticamente una constante.</li>
<li>Resto de Operaciones: O(m) en el peor caso.</li>
</ul>

Complejidad Total: La complejidad dominante es la ordenación de las aristas, por lo que T(n) = O(m log m) o O(m log n).

Montículos (Heaps)

Un montículo es una estructura de datos basada en árboles que satisface la propiedad de montículo: si P es un nodo padre de C, entonces el valor de P es mayor o igual que el valor de C (para un montículo máximo) o menor o igual (para un montículo mínimo).

Tipo de Datos: Montículo

tipo Montículo = registro
  TamM: 0..TamMax;
  vectorM: vector[1..TamMax] de TipoElem;
fin registro;

Procedimiento InicializarM (M)

procedimiento InicializarM (M)
  M.TamM := 0;
fin procedimiento;

Función MVacio (M): Booleano

función MVacio (M): Booleano
  devolver M.TamM = 0;
fin función;

Procedimiento Flotar (M, i)

procedimiento Flotar (M, i)
  mientras i > 1 y M.vectorM[i div 2] < M.vectorM[i] hacer
    intercambiar(M.vectorM[i div 2], M.vectorM[i]);
    i := i div 2;
  fin mientras;
fin procedimiento;

Procedimiento Insertar (x, M)

procedimiento Insertar (x, M)
  si M.TamM = TamMax entonces
    error "Montículo lleno";
  sino
    M.TamM := M.TamM + 1;
    M.vectorM[M.TamM] := x;
    Flotar(M, M.TamM);
  fin si;
fin procedimiento;

Procedimiento Hundir (M, i)

procedimiento Hundir (M, i)
  repetir
    j := i;
    HijoIzq := 2 * i;
    HijoDer := 2 * i + 1;

    si HijoDer <= M.TamM y M.vectorM[HijoDer] > M.vectorM[j] entonces
      j := HijoDer;
    fin si;

    si HijoIzq <= M.TamM y M.vectorM[HijoIzq] > M.vectorM[j] entonces
      j := HijoIzq;
    fin si;

    si j &#x2260; i entonces
      intercambiar(M.vectorM[i], M.vectorM[j]);
      i := j;
    fin si;

  hasta j = i;
fin procedimiento;

Función EliminarMax (M): TipoElem

función EliminarMax (M): TipoElem
  si MVacio(M) entonces
    error "Montículo vacío";
  sino
    x := M.vectorM[1];
    M.vectorM[1] := M.vectorM[M.TamM];
    M.TamM := M.TamM - 1;
    si M.TamM > 0 entonces
      Hundir(M, 1);
    fin si;
    devolver x;
  fin si;
fin función;

Tabla de Dispersión Abierta (Encadenamiento)

En una tabla de dispersión abierta, cada entrada del arreglo es una lista (o «cubeta») que almacena todos los elementos que dispersan a esa posición. Esto resuelve las colisiones permitiendo que múltiples elementos compartan la misma posición de dispersión.

Tipo de Datos

tipo
  Indice = 0..N-1;
  Posicion = ^Nodo;
  Lista = Posicion;
  Nodo = registro
    Elemento: TipoElem;
    Siguiente: Posicion;
  fin registro;
TablaDispersion = vector[Indice] de Lista;

Procedimiento InicializarTabla (T)

procedimiento InicializarTabla (T)
  para i := 0 hasta N-1 hacer
    CrearLista(T[i]);
  fin para;
fin procedimiento;

Función Buscar (x, T): Posicion

función Buscar (x, T): Posicion
  i := Dispersión(x);
  devolver BuscarLista(x, T[i]);
fin función;

Procedimiento InsertarElemento (x, T)

procedimiento InsertarElemento (x, T)
  pos := Buscar(x, T);
  si pos = nil entonces
    i := Dispersión(x);
    InsertarLista(x, T[i]);
  fin si;
fin procedimiento;

Coeficiente Binomial C(n, k)

El coeficiente binomial C(n, k), también conocido como «n sobre k», representa el número de formas de elegir k elementos de un conjunto de n elementos distintos sin importar el orden.

Función C(n, k): Entero (Recursiva)

función C(n, k): Entero
  si k = 0 o k = n entonces devolver 1;
  sino devolver C(n-1, k-1) + C(n-1, k);
  fin si;
fin función;

a) Representación en Tabla (Programación Dinámica)

La función recursiva para C(n, k) tiene subproblemas superpuestos, lo que la hace ideal para la programación dinámica. Se puede construir una tabla (similar al Triángulo de Pascal) para almacenar los resultados intermedios y evitar recálculos.

      0   1   2   ...   k-1   k   ...
    -----------------------------------
  0 | 1
  1 | 1   1
  2 | 1   2   1
  ... |
n-1 | ...       C(n-1, k-1)   C(n-1, k)
  n | ...                       C(n, k)

b) Análisis de Complejidad

La complejidad temporal es T(n) = O(nk) y la complejidad espacial también es O(nk), si se utiliza programación dinámica para almacenar los resultados intermedios.

Conceptos Fundamentales de Algoritmos y Estructuras de Datos

Tabla de Dispersión Cerrada

Tipo de Datos

Procedimiento InicializarTabla (D)

Función Buscar (Elem, D): Posición

Procedimiento Insertar (Elem, D)

Procedimiento Eliminar (Elem, D)

Funciones de Resolución de Colisiones

Función FunResoluciónColisión (x, i): Posición <em>(Exploración Lineal)</em>

Función FunResoluciónColisión (x, i): Posición <em>(Exploración Cuadrática)</em>

Función FunResoluciónColisión (x, i, y): Posición <em>(Exploración Doble)</em>

Conjuntos Disjuntos

Tipo de Datos

Procedimiento Unir (C, raiz1, raiz2)

Función Buscar (C, x): Conj

Compresión de Caminos en Conjuntos Disjuntos

Función Buscar con Compresión de Caminos (C, x): Conj

Análisis de Complejidad

Comparación de Algoritmos: Kruskal, Prim y Dijkstra

Ordenación Topológica

Función OrdenaciónTopológica (G: grafo): orden[1..n]

Análisis de Complejidad

Composición

Función Composición (M[1..n,0..m], V[1..n]): C[1..n]

Análisis de Complejidad

Problema Relacionado: Conjunto de Monedas

Identificación de Funciones en Problemas Algorítmicos

a) Problema del Cambio o Devolución

b) Problema de la Mochila con Objetos Fraccionables

c) Cálculo del Árbol de Expansión Mínima

Búsqueda Binaria

Análisis de Complejidad

Ordenación Rápida con Pivote Aleatorio (Quicksort)

Procedimiento OrdenarAux (V[izq..der])

Procedimiento OrdenaciónRápida (V[1..n])

Análisis de Complejidad

Máquina de Turing y Clases de Complejidad (P vs NP)

Problema de Satisfacibilidad Booleana (SAT)

Divide y Vencerás

Ordenación Topológica Usando Cola (Algoritmo de Kahn)

a) Implementación con Cola

b) Eficiencia del Enfoque con Cola

c) Implementación con DFS (Búsqueda en Profundidad)

d) Ventajas del Enfoque con DFS

Comparación: Ordenación por Fusión (Mergesort) vs. Ordenación Rápida (Quicksort)

Árbol Binario de Búsqueda (ABB)

Tipo de Datos

Procedimiento OrdenPorNivel (A)

Tipo de Datos: Cola

Procedimiento CrearCola (C) <em>{O(1)}</em>

Función ColaVacia (C): Booleano <em>{O(1)}</em>

Procedimiento Incrementar (x) <em>{Privado, O(1)}</em>

Procedimiento InsertarEnCola (x, C) <em>{O(1)}</em>

Algoritmo de Kruskal

a) Tipo de Datos de Salida

b) Reescritura con Montículo

c) Problema Resuelto por Kruskal

d) Elementos Característicos de la Técnica Voraz

e) Análisis de Complejidad

Montículos (Heaps)

Tipo de Datos: Montículo

Procedimiento InicializarM (M)

Función MVacio (M): Booleano

Procedimiento Flotar (M, i)

Procedimiento Insertar (x, M)

Procedimiento Hundir (M, i)

Función EliminarMax (M): TipoElem

Tabla de Dispersión Abierta (Encadenamiento)

Tipo de Datos

Procedimiento InicializarTabla (T)

Función Buscar (x, T): Posicion

Procedimiento InsertarElemento (x, T)

Coeficiente Binomial C(n, k)

Función C(n, k): Entero <em>(Recursiva)</em>

a) Representación en Tabla (Programación Dinámica)

b) Análisis de Complejidad

Relacionados

Publicidad

Temas