• Portada
    • Recientes
    • Usuarios
    • Registrarse
    • Conectarse

    Ayuda con algoritmo

    Programado Fijo Cerrado Movido
    Software
    4
    9
    1.4k
    Cargando más mensajes
    • Más antiguo a más nuevo
    • Más nuevo a más antiguo
    • Mayor número de Votos
    Responder
    • Responder como tema
    Accede para responder
    Este tema ha sido borrado. Solo los usuarios que tengan privilegios de administración de temas pueden verlo.
    • albertpgA
      albertpg
      Última edición por

      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:(

      1 Respuesta Última respuesta Responder Citar 0
      • IstarionI
        Istarion
        Última edición por

        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 😛

        Intel Xeon E3 1231v3 @ 3.4Ghz / 16GB DDR3 2133Mhz 11-11-11 / R290 PRO / Samsung 970 Evo 500GB / Samsung 840 250GB / 2xHDD / Netway 700w

        albertpgA DixmanD 2 Respuestas Última respuesta Responder Citar 0
        • albertpgA
          albertpg @Istarion
          Última edición por

          :(:( 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

          1 Respuesta Última respuesta Responder Citar 0
          • DixmanD
            Dixman Mercaderes HL @Istarion
            Última edición por

            @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

            IstarionI 1 Respuesta Última respuesta Responder Citar 0
            • IstarionI
              Istarion @Dixman
              Última edición por

              @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

              Intel Xeon E3 1231v3 @ 3.4Ghz / 16GB DDR3 2133Mhz 11-11-11 / R290 PRO / Samsung 970 Evo 500GB / Samsung 840 250GB / 2xHDD / Netway 700w

              lforosL 1 Respuesta Última respuesta Responder Citar 0
              • lforosL
                lforos Veteranos HL @Istarion
                Última edición por

                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.

                IstarionI 1 Respuesta Última respuesta Responder Citar 0
                • IstarionI
                  Istarion @lforos
                  Última edición por

                  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 😛

                  Intel Xeon E3 1231v3 @ 3.4Ghz / 16GB DDR3 2133Mhz 11-11-11 / R290 PRO / Samsung 970 Evo 500GB / Samsung 840 250GB / 2xHDD / Netway 700w

                  lforosL 2 Respuestas Última respuesta Responder Citar 0
                  • lforosL
                    lforos Veteranos HL @Istarion
                    Última edición por

                    ¡Esta publicación está eliminada!
                    1 Respuesta Última respuesta Responder Citar 0
                    • lforosL
                      lforos Veteranos HL @Istarion
                      Última edición por

                      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)

                      1 Respuesta Última respuesta Responder Citar 0
                      • 1 / 1
                      • First post
                        Last post

                      Foreros conectados [Conectados hoy]

                      1 usuarios activos (0 miembros e 1 invitados).
                      febesin, pAtO,

                      Estadísticas de Hardlimit

                      Los hardlimitianos han creado un total de 543.3k posts en 62.8k hilos.
                      Somos un total de 34.8k miembros registrados.
                      xenium_digital ha sido nuestro último fichaje.