Apuntes Algoritmos

Links: University

Prácticas

T1 Verificación empírica y análisis

El resto del tema parece estar orientado a las prácticas.

Calcular O

// donde "c" NO varia con la entrada
for (int i =1; i < c; i++){          // O(1)
  //cualquier sentencia 0(1)
}
 
// donde "n" es la entrada
for (int i =1; i <= n; i += c){      // O(n)
  //cualquier sentencia 0(1)
}
 
// donde "n" es la entrada
for (int i =1; i <= n; i *= c){      // O(log(n))
  //cualquier sentencia 0(1)
}
 
// donde "n" es la entrada
for (int i =1; i <= n; i += c){
  for (int i =1; i <= n; i += c){    // O(n^2)
  //cualquier sentencia 0(1)
  }
}

T2 Estructuras de datos

árboles

Recorridos

me parece la única parte que es posible que caiga en el examen

• En orden O(n)

  function Visualizar (A)
    if A <> nil then
      Visualizar (A^.izq);
      Escribir (A^.elemento);
      Visualizar (A^.der);
  end function

• Post-orden O(n)

  function Altura (A) : número
    if A = nil then return -1
    else  return 1 + max (Altura (A^.izq), Altura (A^.derecho))
  end function

• Orden de nivel O(n)

  function OrdenDeNivel (A)
    CrearCola(C);
    if A <> nil then InsertarEnCola(A, C);
    while no ColaVacia(C) do
      p:= QuitarPrimero(C);
      escribir(pˆ.Elemento); {Operacion principal}
      if pˆ.Izq <> nil then InsertarEnCola(pˆ.Izq, C);
      if pˆ.Der <> nil then InsertarEnCola(pˆ.Der, C);
    end while
  end function

tablas de disperión

Dispersión abierta

Se hace una lista enlazada en cada una de las posiciones

Dispersión cerrada

• Exporacion lineal
  Cuando hay colisión se pasa a la siguiente posición
• Exporacion cuadrática
  Cuando hay colisión se mueve i^2 posiciones
• Exporacion doble
  Cuando hay colisión se le suma un numro derivado de una función dada

conjuntos disjustos

Primer enfoque

• Elementos de 1 a n
• Cada subconjunto tomará el nombre de uno de sus elementos
• Mantenemos en un vector el nombre del conjunto al que pertenece cada elemento.

type
  Elemento = entero;
  Conj = entero;
  ConjDisj = vector [1..N] of entero
 
function Buscar1 (C, x) : Conj
  return C[x]
end function
 
function Unir1 (C, a, b)
  i := min (C[a], C[b]);
  j := max (C[a], C[b]);
  for k := 1 to N do
    if C[k] = j then C[k] := i
  end for
end function

Segundo enfoque

• Cada subconjunto es un arbol
• La raiz nombra al subconjunto
• Cada entrada p[i] en el vector contiene el padre del elemento i

function Buscar2 (C, x) : Conj
  r := x;
  while C[r] <> r do
    r := C[r]
  end while
  return r
end function
 
function Unir2 (C, raiz1, raiiz2)
    { supone que raiz1 y raiz2 son raices }
  if raiz1 < raiz2 then C[raiz2] := raiz1
  else C[raiz1] := raiz2
end function

• Unión por alturas
  Hace el árbol menos profundo un subárbol del más profundo
  O(m * log(n) + n)

function Unir por altura (C, A, raiz1, raiz2)
  if A[raiz1] = A [raiz2] then
    A[raiz1] := A[raiz1] +1
    C[raiz2] := raiz1
  else if A[raiz1] > A[raiz2] then C[raiz2] := raiz1
  else C[raiz1] := raiz2
end function

• Compresión de caminos
  Al muscar x, todo nodo en el camino de x a la raiz cambia su padre por la raiz

function Buscar con compresión de caminos (C, x) : Conj
  r := x;
  while C[r] <> r do
    r := C[r]
  end while
  i := j
  while i <> r do
    j := C[i];
    C[i] := r;
     i := j;
  end while
  return r
end function

pilas-colas-listas

grafos

montículos

T3 Algoritmos de ordenación

Inserción

O(n^2)
mejor caso (n)

function Ordenación por Inserción (var T[1..n])
  for i:=2 to n
    x:=T[i];
    j:=i-1;
    while j>0 and T[j]>x do
      T[j+1]:=T[j];
      j:=j-1;
    end while;
    T[j+1]:=x;
  end for;
end function;

Selección

O(n^2)

function Ordenación por Selección (var T[1..n])
  for i:=1 to n-1
    minj:=i;
    minx:=T[i];
    for j:=i+1 to n
      if T[j]<minx then
        minj:=j;
        minx:=T[j];
      end if;
    end for;
    T[minj]:=T[i];
    T[i]:=minx;
  end for;
end function;

Shell

O(n log^2 n)

function Ordenación por Shell (var T[1..n])
  incremento := n;
  do
    increment := increment div 2;
    for i := incremento+1 to n
      tmp := T[i];
      continue := true;
      while j-increment > 0 and continue do
        if tmp < T[j-increment] then
          T[j] := T[j-increment];
          j := j-increment;
        else continue := false;
      T[j] := tmp;
  while increment = 1;
end function;

Montículos

O(n log(n))

function Ordenación por Montículos (var T[1..n])
  crear_montículo (T, M);
  for i := i to n
    T[n-i+1] := max(M);
    delete_max(M)
  end for;
end function;
 
// V[1..n] : vector con los datos
// M : montículo a crear
function Crear_montículo (V[1..n], var M)
  Copy V[1..n] in M[1..n];
  for i := n div 2 downto 1
    hundir(M,i)
  end for
end function;

Fusión

O(n log(n))

function Fusión (var T[izq..der], Centro:izq..der)
  i := izq; j := Centro+1; k := izq;
  while i < Centro and j <= der do
    if T[i] <= T[j] then
      aux[k] := T[i]; i := i+1;
    else Aux[k] := T[j]; j := j+1;
    k := k+1;
  while i <= Centro do
    aux[k] := T[i]; i := i+1; k := k+1;
  while j <= der do
    aux[k] := T[j]; j := j+1; k := k+1;
  for k := izq to der
    T[k] := aux[k];
end function;

Mejora:

function Fusión_recursivo (var T[izq..der])
  if izq+UMBRAL < der then
    Centro := (izq+der) div 2;
    Fusión_recursivo (T[izq..Centro]);
    Fusión_recursivo (T[Centro+1..der]);
    Fusión (T[izq..der], Centro)
  else Inserción (T[izq..der])
end function;
 
function Fusión (var T[1..n])
    Fusión_recursivo (T[1..n]);
end function;

Quicksort

mejor (n log(n))
media (n log(n))
O(n^2)

function Qsort (var T[i..j])
  if i+UMBRAL <= j then
    Mediana3(T[i..j]);
    pivote := T[j-i]; k := i; m := j-1;
    do
      do k := k+1 while T[k] >= pivote;
      do m := m-1 while T[m] >= pivote;
      intercambiar (T[k], T[m]);
    while m <= k;
    intercambiar (T[k], T[m]);
    intercambiar (T[k], T[j-1]);
    Qsort (T[i..k-1]);
    Qsort (T[k+1..j]);
end function;
 
function Quicksort (var T[1..n])
  Qsort (T[1..n]);
  Inserción (T[1..n]);
end function;

pivote aleatorio

function ordenarAux (v[izq..der])
    if izq+UMBRAL <= der then
        x := aleatorio en el rango(izq..der);
        pivote := v[x];
        intercambiar(v[izq],v[x]);
        i := izq+1;
        j := der;
        while i <= j do
            while i<=der y v[i]<pivote do
                i := i + 1;
            end while;
            while v[j]>pivote do
                j := j - 1;
            end while;
            if i<=j then
                intercambiar(v[i],v[j]);
                i := i + 1;
                j := j - 1;
            end if;
        end while;
        intercambiar(v[izq],v[j]);
        ordenarAux(v[izq..j-1]);
        ordenarAux(v[j+1..der]);
    end if;
end function;

T4 Algoritmos voraces

Resuelven problemas de optimización:

En cada fase toman una decisión (selección de un candidato), saisfaciendo un óptimo local seguún la
información disponible, esperando así en conjunto satisfacer un óptimo global.

Manejan un conjunto de candidatos C:

En cada fase, retiran el candidato seleccionado de C, y si es aceptado se incluye en S, el conjunto donde
se construye la solución.

4 funciones (no todas aparecen):

S es solución?
S es factible? (nos lleva hacia una solución?)
Seleción: determina el mejor candidato
Objetivo: valora S

Pseudocódigo esquema

function Voraz (C:conjunto) : conjunto
  S := conjunto vacío;
  while C <> conjunto vacío && no solución(S) do //bucle voraz
    x := seleccionar(C);
    C :- C-{x};
    if factible(SU{x}) then S := SU{x}
  end while;
  if solución(S) then return S
  else return "no hay soluciones"
end function
 

Devolver cambio

No siempre da el mejor resultado a menos que el sistema monetario esté pensado para ello

Mochila

No siempre da el mejor resultado

Ordenación topológica

function Ordenació topológica 1 (G:grafo) : orden[1..n]
  Grafo Entrada [1..n] := Calcular Grafo Entrada (G);
  for i := 1 to n do Número tomológico [i] := 0;
  contador := 1;
  while contador <= b do
    v := Buscar node del grado 0 sin número topológico asignado;
    if v no encontrado then
      return error "el grafo tiene un ciclo"
    else
      Número topológico [v] := contador;
      incrementar contador;
      for each w adyacente a v do
        Gredo ENtrada [w] := Grado Entrada [w] -1
    end if
  end while
  return Número topológico;
end function

Árbol expandido mínimo

Kruskal

O(n log(n))

function kruskal (G=(N,A)) : árbol
  ordenar A según longitudes crecientes;
  n := |N|;
  T := conjunto vacío;
  inicializar n conjuntos, cada uno con un nodo de N;
  //bucle voraz
  do
    a := (u,v) //arista más corta de A aun sin considerar
    Conjunto U := Buscar (u);
    Conjunto V := Buscar (v);
    if Conjunto U <> Conjunto V then
      Fusionar (Conjunto U, Conjunto V);
      T := T U //a
    end if
  while |T| = n-1;
  return T;
end function;

Prim

O(n^2)

function prim (L[1..n,1..n]) : árbol
  distanciaMinima[1] := -1;
  T := conjunto vacío;
  for i := 2 to n do
      masProximo[i] = 1;
      distanciaMinima[i] = L[i,1];
  end for;
  repeat n-1 times:
      min = INFINITO;
      for j := 2 to n do
          if 0 <= distanciaMinima[j] < min then
              min := distanciaMinima[j];
              k:=j;
          end if;
      end for;
      T := T U; //más proximo [k], k
      distanciaMinima[k] := -1;
      for j := 1 to n do
          if L[j,k] < distanciaMinima[j] then
              distanciaMinima[j] := L[j,k];
              masProximo[j] := k;
          end if;
      end for;
  end repeat;
  return T;
end function;

Caminos mínimos

Dijkstra

function dijkstra (L[1..n,1..n]) : vector[1..n]
  C := (2,3,...,n);
  for i := 2 to n do
    D[i] := L[1,i];
  //bucle voraz
  repeat n-2 times:
    v := nodo de C que minimiza D[v];
    C := C-(v);
    for each w in C do
      D[w] := min (D[w],D[v]+L[v,w]);
  end repeat;
  return D;
end function;

T5 Algoritmos por inducción

Divide y vencerás

function DivideYVenceras (x): solución
  if x es suficientemente pequeño then return ad-hoc(x)
  else
    desomponer x en casos más pequeños x1, x2... xa;
    for i := 1 to a do
      yi := DivideYVenceras(xi)
    end for;
    combinar los yi para obtener la solución y de x;
    return y;
  end if;
end function;

Programación dinámica

Devolver cambio

function moneda (M[1..n,0..W], w[1..n]) : C[1..n]
  for i:=1 to n do C[i]:=0;
  v:=M[n,W];
  i:=n; j:=W;
  while i>1 and v>0 do
    if M[i,j] <> M[i-1,j] then //i esta en la configuración
      C[i] := C[i] + 1;
      j := j - v[i];
      v := M[i-1,j]; //leer el valor de la tabla
    else
      i := i-1;
    end if;
  end while;
  if v>0 then C[1] := C[1] +1; //caso particular i=1
  return C;
end function;

Mochila

function mochila (M[1..n,0..W], w[1..n]) : C[1..n]
  for i:=1 to n do C[i]:=false;
  v:=M[n,W];
  i:=n; j:=W;
  while i>1 and v>0 do
    if M[i,j] <> M[i-1,j] then //i esta en la configuración
      C[i] := true;
      j := j - w[i];
      v := M[i-1,j]; //leer el valor de la tabla
    end if;
    i := i-1;
  end while;
  if v>0 then C[1]:=true; //caso particular i=1
  return C;
end function;

T6 Grafos

Recorrido en profundidad

O(n+m)

function rp (v) {v no ha sido visitado anteriormente}
  marca[v] := visitado;
  for each w adyacente a v do
    if marca[w] != visitado then rp(w)
end function

con pila:

function rp (v)
  crear pila (P);
  marca[v] := visitado;
  apilar(v,P)
  while not pila vacia (P) do
    while exista w adyacente a cima(P): marca[w] != visitado;
    do
      marca[v] := visitado;
      apilar(w,P)
    end while
    desapilar (P)
  end while
end function

Recorrido en anchura

O(n+m)
con cola:

function ra (v)
  crear Cola (C);
  marca[v] := visitado;
  insertar cola(v,C)
  while not cola vacia (C) do
    u := eliminar cola (C);
    for each nodo w adyacente a u do
      if marca[w] != visitado then
        marca[w] := visitado;
        insetar cola (w,C);
      end if
    end for
  end while
end function

Juego de Nim

• Un montón de n palillos
• 2 jugadores, alternativamente
• 1a jugada: coger [1 .. n-1] palillos
• jugadas siguientes: coger [1 .. 2*jugaga anterior] palillos
• Objetivo: coger el último palillo (?)

0,0 es derrota, todos los nodos que apuntan a 0,0 son ganadores, los que apunten a solo ganadores seran derrotas.

T7 Complegidad computacional

Máquina de Turing

NP-completitud