Ayuda con algoritmo

[albertpg]

Tengo que presentar una memoria explicativa sobre el problema de la mochila 0-1 con estos apartados:

• Justificar la complejidad i el coste de memoria, ja sea analiticamente, con tablas de tiempo o estudiando el nombre de movimentos o el número de nodos manipulados.

Esto para cada tipo de algorismo: Backtracking, Programación Dinámica y Greedy.

La complejidad para cada uno de ellos lo tengo, pero no tengo ni zorra de como demostrarlo.

Alguien me puede ayudar?? Lo tengo que entregar mañana!!

Gracias:(

[Istarion]

Uhmm esto me recuerda a TriPi xD Bueno la cuestion, no me acuerdo de cual era el algoritmo de mochila osea que vamos bien xD

La cuestion, no os han explicado los teoremas de calculo asintotico?? son vitales, te pego un par de paginas:
http://www.lsi.upc.edu/~duch/home/duch/analisis.pdf (basicamente teoria)
http://www.di.uniovi.es/~dani/asignaturas/transparencias-leccion14.PDF (aqui hay un ejemplo de como aplicarlo)

La idea es que has de saber si divides cada vez, o si restas, porque el limite asintotico es mucho menor en caso de dividir. Por ejemplo, el factorial seria de resta, porque cada vez has de calcular una solucion menos. Por otro lado, en el caso de la division (este en que partes por dos el numero a dividir en cada llamada) se trata de partir entre 2 el numero de soluciones a calcular.
Tengo los apuntes desaparecidos en combate, asi que intentare explicarte un poco como va lo de los teoremas porque es un poco raro al principio:
-Lo que le quitas a n (sea dividiendo o restando) es como se va reduciendo la funcion (-1 en factorial, /2 en division).
-a si no me equivoco es el numero de llamadas recursivas.

Anda mira que casualidad, mi profe xD Y esta el ejemplo de mochila! xD aunque un poco mal explicado:
http://dmi.uib.es/~mascport/tp/presentacions/TP3.pdf
Pagina 389 (45 del pdf) ejemplo bien explicado
http://marmota.act.uji.es/MTP/pdf/tema14.pdf

Bueno espero que te sirva

[albertpg]

:(:( Gracias pero no me ha servido de nada. EL problema es que los algoritmos los tengo hechos los 3. Y la complejidad la se. Lo que no sé es como demostrarlo.

Y el coste en memoria eso si que ni lo sé ni lo encuentro por ninguna parte

[Dixman]

@Istarion:

Uhmm esto me recuerda a TriPi xD Bueno la cuestion, no me acuerdo de cual era el algoritmo de mochila osea que vamos bien xD

El problema de la mochila es basicamente este:
Tiene suna mochila con capacidad finita
Unos objetos con un determinado tamaño y valor.

Tienes que hacer un algonitmo para meter en la mochila el mayor valor posible teniendo en cuenta le tamaño de los objetos.

Mejor explicado http://es.wikipedia.org/wiki/Problema_de_la_mochila

[Istarion]

@Dixman:

El problema de la mochila es basicamente este:
Tiene suna mochila con capacidad finita
Unos objetos con un determinado tamaño y valor.

Tienes que hacer un algonitmo para meter en la mochila el mayor valor posible teniendo en cuenta le tamaño de los objetos.

Mejor explicado http://es.wikipedia.org/wiki/Problema_de_la_mochila

Ok, justo lo encontre en la web de mi profe xD Es que habia dado bastantes en clase (un año con un profe hicimos unos y al siguiente cambiaron de profe y eran todos nuevos) y no me acordaba bien. Viene a ser como una "broma" del problema de los horarios, a no ser que tengas muchos tamaños de objetos
Gracias por la informacion de todas formas ;D

[lforos]

No sé si entiendo el problema, pero la justificación más simple de la complejidad si ya tienes el algoritmo en código o en pseudocódigo, lo más fácil es analizar los bucles.

Por ejemplo (extremadamente sencillo), si tienes un algoritmo de mezcla de listas de tamaños x e y respectivamente y utilizas un bucle for-next para y anidado dentro de otro for-next para x, significa que operas y+y+y+y+y … x veces, la complejidad es y*x que normalmente se expresa (como si la dimensión fuera la misma) "n al cuadrado".

Así tendrás complejidades "n", "n al cuadrado", "n elevado a n", "n factorial", "n/2", y cosas de este tipo.

[Istarion]

En este caso se trata de algoritmos recursivos, como este del factorial:

int factorial(int n) {
if (n==1)
return 1;
else
return n*factorial(n-1);
}

Asi si llamas a factorial(5) se haria:

• 5 x fact(5-1)
• 5 x (4 x fact(4-1))
• 5 x (4 x (3 x fact(3-1) ) )
• 5 x (4 x (3 x (2 x fact(2-1)) ) )
• 5 x (4 x (3 x (2 x (1)) ) )
• 5x4x3x2x1 = 120

Son raros al principio pero son muy elegantes y van muy bien para segun que los algoritmos recursivos. Ademas son muy "naturales". El calculo de complejidad es un poco mas complejo :risitas:, pero en este caso se ve claramente que es de coste lineal T(n), pero normalmente son mas dificiles y llegan a salir costes logaritmicos (tampoco muy dificiles de ver), u otros algo mas feos :S

En backtracking lo que se hace es probar todas las posibilidades, asi que en memoria tendras toda la informacion (bueno tiendes a tenerla, que es lo que cuenta), y el calculo sera enorme (por ejemplo, backtracking de un sudoku seria ir probando en todas las casillas de cada uno de los cuadrados todos los numeros, hasta que te quedas sin numeros, y pasar al siguiente; la primera "solucion parcial" del siguiente tendra exactamente el mismo contenido que el anterior, asi que habra que volver para atras a recolocar los ultimos 2 numeros, si sigue sin ir, recolocas los 3 ultimos numeros con sus combinaciones, etc, etc.).

Bueno creo que lo del sudoku esta un poco mal explicado pero por aqui no va muy bien

[lforos]

¡Esta publicación está eliminada!

[lforos]

Este tema lo tengo bastante oxidado, pero creo recordar que la complejidad del backtracking depende del problema que tengas que resolver. Si haces un árbol de posibilidades en un caso sencillo puede tener un máximo de complejidad de n! o incluso n elevado a n.

De todas formas, había condiciones de poda (puntos en los que no continuabas el proceso y hacías la "marcha atrás" del backtracking) para no seguir explorando posibilidades que ya se saben incorrectas, aunque no recuerdo si a eso se le seguía llamando backtracking o era otro algoritmo distinto.

En el ejemplo del sudoku de Istarion, sabiendo que en la misma fila (o columna o cuadro, según estés generando el árbol de la solución) no puedes repetir un número, cuando el siguiente paso del algoritmo implica repetir puedes "hacer la poda".

Todo esto suponiendo, claro, que el problema sea computable.

Por cierto, en casos de recursividad, creo que la mejor forma de analizar la complejidad es por los nodos computados poniendo un ejemplo sencillo (por ejemplo, mezcla ordenada de dos listas de tres elementos)