Loading presentation...

Present Remotely

Send the link below via email or IM

Copy

Present to your audience

Start remote presentation

  • Invited audience members will follow you as you navigate and present
  • People invited to a presentation do not need a Prezi account
  • This link expires 10 minutes after you close the presentation
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

DeleteCancel

Make your likes visible on Facebook?

Connect your Facebook account to Prezi and let your likes appear on your timeline.
You can change this under Settings & Account at any time.

No, thanks

Untitled Prezi

No description
by

Elmer Sanchez

on 8 April 2013

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of Untitled Prezi

Clase de Análisis de Algoritmos Divide y Vencerás Divide y Vencerás 1. En primer lugar ha de plantearse el problema de forma que pueda ser descompuesto en k subproblemas del mismo tipo, pero de menor tamaño. Es decir, si el tamaño de la entrada es n, hemos de conseguir dividir el problema en k subproblemas (donde 1 ≤ k ≤ n), cada uno con una entrada de tamaño nk y donde 0 ≤ nk < n. A esta tarea se le conoce como división.
2. En segundo lugar han de resolverse independientemente todos los subproblemas, bien directamente si son elementales o bien de forma recursiva. El hecho de que el tamaño de los subproblemas sea estrictamente menor que el tamaño original del problema nos garantiza la convergencia hacia los casos elementales, también denominados casos base.
3. Por último, combinar las soluciones obtenidas en el paso anterior para construir la solución del problema original. Búsqueda Binaria Este algoritmo es un ejemplo claro de Divide y Vencerás.
Se parte en decidir si existe un elemento dado "X" en un vector de enteros Ordenados Búsqueda Ternaria Podemos plantearnos también diseñar un algoritmo de búsqueda “ternaria”, que primero compara con el elemento en posición n/3 del vector, si éste es menor que el elemento x a buscar entonces compara con el elemento en posición 2n/3, y si no coincide con x busca recursivamente en el correspondiente subvector de tamaño 1/3 del original. Producto de Matrices Cuadradas Supongamos que necesitamos calcular el producto de matrices cuadradas de orden n, donde n es una potencia de 3. Usando la técnica de Divide y Vencerás, el problema puede ser reducido a una multiplicación de matrices cuadradas de orden 3. El método tradicional para multiplicar estas matrices requiere 27 multiplicaciones. Ejemplos de Multiplicación de enteros Multiplicación de enteros de n cifras:
Algoritmo clásico

1234*5678 = 1234* (5*1000 + 6*100+7*10+8)
= 1234*5*1000 + 1234*6*100 + 1234*7*10 + 1234*8

Operaciones básicas:
Multiplicaciones de dígitos: O(1)
Sumas de dígitos: O(1)
Desplazamientos: O(1)
Eficiencia algoritmo: O(n2) Búsqueda Binaria no Centrada Una de las cuestiones a considerar cuando se diseña un algoritmo mediante la técnica de Divide y Vencerás es la partición y el reparto equilibrado de los subproblemas. Más concretamente, en el problema de la búsqueda binaria nos podemos plantear la siguiente cuestión: supongamos que en vez de dividir el vector de elementos en dos mitades del mismo tamaño, las dividimos en dos partes de tamaños 1/3 y 2/3. Algoritmo Divide y Vencerás Multiplicación de Enteros Multiplicación de Enteros Sean u y v dos números naturales de n bits donde, por simplicidad, n es una potencia de 2. El algoritmo tradicional para multiplicarlos es de complejidad O(n2). Catedrático: Ing. Carlos Oliva Mediana de dos Vectores Sean X e Y dos vectores de tamaño n, ordenados de forma no decreciente. Necesitamos implementar un algoritmo para calcular la mediana de los 2n elementos que contienen X e Y. Recordemos que la mediana de un vector de k elementos es aquel elemento que ocupa la posición (k+1)÷2 una vez el vector está ordenado de forma creciente. Dicho de otra forma, la mediana es aquel elemento que, una vez ordenado el vector, deja la mitad de los elementos a cada uno de sus lados. Como en nuestro caso k = 2n (y por tanto par) buscamos el elemento en posición n de la unión ordenada de X e Y. Repetición de Cálculos de Fibonacci En el cálculo recursivo del n-ésimo número de Fibonacci, fib(n), necesitamos determinar para cada 0 ≤ k < n el número de veces que se calcula fib(k). El Elemento Mayoritario Sea a[1..n] un vector de enteros. Un elemento x se denomina elemento mayoritario de a si x aparece en el vector más de n/2 veces, es decir, Card{i | a[i]=x} > n/2. Necesitamos implementar un algoritmo capaz de decidir si un vector dado contiene un elemento mayoritario (no puede haber más de uno) y calcular su tiempo de ejecución La Moda de un Vector Deseamos implementar un algoritmo Divide y Vencerás para encontrar la moda de un vector, es decir, aquel elemento que se repite más veces.
La primera solución que puede plantearse para resolver este problema es a partir de la propia definición de moda. Se calcula la frecuencia con la que aparece cada uno de los elementos del vector y se escoge aquel que se repite más veces. Multiplicación de enteros de n cifras:
Algoritmo “divide y vencerás” simple

1234 = 12*100 + 34 5678 = 56*100 + 78 1234*5678
= (12*100 + 34)*(56*100 + 78)
= 12*56*10000 + (12*78+34*56)*100 + (34*78)

Idea: Se reduce una multiplicación de 4 cifras a cuatro multiplicaciones de 2 cifras, más tres sumas y varios desplazamientos. función multiplica (X,Y,n)
{
if (P es pequeño) {
return X*Y;
}
else {
Obtener xi, xd, yi, yd; yd;
z1 = multiplica (xi, yi, n/2);
z2 = multiplica (xi, yd, n/2);
z3 = multiplica (xd, yi, n/2);
z4 = multiplica (xd, yd, n/2);
aux = suma(z2,z3);
z1 = desplaza_izq(z1,n);
aux = desplaza_izq(aux,n/2);
z = suma(z1,aux);
z = suma(z,z4);
return z;
}
} Dividir Combinar El problema se puede descomponer en otros del mismo tipo que el original y de tamaño más pequeño (formulación recursiva).
Los subproblemas pueden resolverse de manera independiente.
Los subproblemas son disjuntos, sin solapamiento.
La solución final se puede expresar como combinación de las soluciones de los subproblemas. Características de los problemas resolubles utilizando “divide y vencerás”
Full transcript