Práctica Algorítmica y Complejidad

Actualización: La solución para el problema añadido de la busqueda del número de caminos entre los nodos de un grafo para la práctica del curso 2013-1014 se encuentra en el siguiente link: http://alejandromoran.com/numero-de-caminos-entre-nodos-de-un-grafo/

Práctica propuesta en la UPM para la asignatura “Algorítmica y Complejidad” en el curso 2012-2013:

Link al enunciado de la práctica en formato pdf

Aquí dejo la solución propuesta por mi compañero David Álvarez , bastante mejor que la que yo propuse hace tiempo:

 

Tagged with: , , ,
37 comments on “Práctica Algorítmica y Complejidad
  1. pedro says:

    El link de descarga esta roto.

    • AlejandroMoran says:

      Muchas gracias por avisar Pedro, ya está solucionado, en caso de necesitar algo puedes contactarme, un saludo.

  2. Pedro says:

    Muchas gracias a ti. Yo estudio en la upm de boadilla del monte y nos pusieron una practica similar q ya entregue y evaluaron y al parecer tenia una serie de fallos pero no entregaron corrección ni nada por el estilo para ver fallos y tal y la verdad que me sirvió de mucho la solución de tu amigo para entender ciertas partes. Lo mismo me sucedió con una practica en la que tengo que hallar la complejidad de un algoritmo a través de sus tiempos, tengo un 8 pero desconozco mis fallos, si tuvierais algo parecido os agradecería que me lo pasarais. Si necesitais ayuda en cualquier cosa contar conmigo :).

  3. AlejandroMoran says:

    Yo estudio Ingeniería del Software en el Campus Sur (Vallecas). Nosotros teníamos que escoger entre dos opciones, la práctica de grafos o esa que mencionas de hallar la complejidad de un algoritmo a través de sus tiempos. Mañana intentaré conseguirte la solución y la subo para que la tengas.

    Lo mismo te digo, si necesitas cualquier cosa ya sabes donde encontrarme 🙂 un saludo y muchas gracias!!

  4. Pedro says:

    Encuentras alguna solucion Alejandro es que tengo examen de esa practica el prox viernes si quieres q te facilite correo o algo dime :). Gracias.

    • AlejandroMoran says:

      Hola Pedro, no me he olvidado de ti, estoy intentando conseguirla aún, está resultando algo difícil ya que no la hizo mucha gente, estoy trabajando en ello 🙂

  5. Anon says:

    Hola, te dejo la práctica de complejidad: http://pastebin.com/0txyTJww

  6. Pedro says:

    Gracias Anon me ha sido de gran ayuda 🙂 y muchas gracias Alejandro por tu esfuerzo de conseguirla ;). Yo tambien si pudiera elegir me hubiera quedado con la segunda practica. Gracias.

  7. Pedro says:

    Oye Alejandro, no se si tienes la asignatura “Teoría y gestión de la información” pero te comento el problema: tengo que hacer una practica de manejo de Registros y Archivos(Conjunto de registros básicamente) pero dentro de una clase, concretamente, ArchivoDeListaDeHuecos hay unos métodos que no se implementar, cuyo funcionamiento conozco pero que no se pasar a código y son borrar mediante lista de huecos y escribir en lista de huecos fundamentalmente. Si pudieras decirme algo que me ayude a guiarme te lo agradecería mucho. Gracias de antemano 🙂

    • AlejandroMoran says:

      Estás de suerte Pedro jeje, la tengo hecha, ¿en que lenguaje la quieres? la tengo en java pero vamos, lo que necesites, abriré una entrada nueva esta noche en el blog para poner esa práctica =)

  8. Pedro says:

    Tambien nosotros usamos java como lenguaje de la asignatura :). Muchas gracias Alejandro 😉

  9. pedro says:

    Alejandro en la linea 20 de la practica de grafos (“Text_IO.Open(fich,Text_IO.In_File,Argument (1));”) no entiendo el tercer parametro (Argument (1)) porque yo tenía puesto “entrada.txt” aunque tampoco de esa manera me lee el fichero de entrada.

    • AlejandroMoran says:

      Ese Argument(1) es porque a este programa en cuestión se le llamaba de la forma “programa.adb argumento1 argumento2” desde línea de comandos dónde argumento1 era el nombre de entrada si no me equivoco y argumento2 el nombre del fichero de salida. Que no te lea el fichero de entrada pues puede ser por varios motivos, asegúrate de que el fichero que abres existe, que está en la ruta correcta, que tiene el mismo formato que se espera de él, etc… 🙂 Un saludo.

  10. pedro says:

    Si tienes razón Alejandro pero mi practica difiere en algunos aspectos a la tuya y no se como realizarla…..te paso el link del enunciado http://www.dia.eui.upm.es/cgi-bin/asigfram.pl?cual=ISalg_com&nombre=Algor%EDtmica-y-Complejidad

  11. raul says:

    Has empezado con la practica de Algoritmica de este año porque me seria de gran ayuda ya que estoy un poco perdido.

    Muchas gracias de antemano 😉

    • AlejandroMoran says:

      Yo no tengo algorítmica, la aprobé hace un año jeje, pero como respondí anteriormente, esta tarde subiré algo de esa práctica, un saludo.

  12. Pedro says:

    Eyy Alejandro podría decirme como puedo programar, en la practica de grafos, una columna que me calcule el numero de caminos validos diferentes entre nodos?
    Gracias

    • AlejandroMoran says:

      Hola Pedro, si no me equivoco esa es la segunda parte de la práctica, ¿no?, lo único que tienes que hacer son dos “for” que vayan recorriendo cada combinación de números entre el total de nodos y, por cada combinación, aplicar la función que has desarrollado para el apartado 1 que te devuelve el mejor camino entre esos dos nodos, un saludo.

  13. pedro says:

    Alguien puede responder mi duda por favor?

  14. Reaper says:

    Muchas gracias Alejandro por tu esfuerzo y tu tiempo.
    Me ha servido mucho de ayuda para las practicas de algorítmica,el único problema que tengo es una practica que hay que calcular el tipo de complejidad dados unos tiempos de ejecución.
    Te dejo el enlace de la practica por si cuando tengas tiempo poder ayudarme.
    http://www.dia.eui.upm.es/asignatu/alg_com/Pr%C3%A1cticas/Practica%20_1.rar
    Gracias de antemano.

  15. Margaret says:

    Muchas gracias por la practica !, una gran ayuda 😉

    • AlejandroMoran says:

      De nada Margaret, me alegro de haber podido ayudarte, para lo que necesites me puedes contactar por aquí, un saludo.

  16. David says:

    No Alejandro, te explico:
    En el apartado 1 nos piden sacar cuatro columnas, la primera el nodo origen, la segunda el nodo destino, la tercera el ancho de banda y la cuarta (que era lo q te preguntaba) el numero de caminos validos de el nodo origen al destino, sabiendo que cuando nodo origen=nodo destino el numero de caminos es 0. Te pongo un ejemplo:

    Entrada:

    5
    124
    132
    241
    256
    343
    417
    456

    Resultado del Apartado 1:
    1 1 0 0
    1 2 6 5
    1 3 3 4
    1 4 7 4
    1 5 6 6
    2 1 6 5
    2 2 0 0
    2 3 3 6
    2 4 6 4
    2 5 6 4
    3 1 3 4
    3 2 3 6
    3 3 0 0
    3 4 3 4
    3 5 3 7
    4 1 7 4
    4 2 6 4
    4 3 3 4
    4 4 0 0
    4 5 6 4
    5 1 6 6
    5 2 6 4
    5 3 3 7
    5 4 6 4
    5 5 0 0

    Es decir el numero de caminos distintos entre el nodo origen:5 a el nodo destino:4 son 4.

  17. Alvaro says:

    Hola Alejandro.

    Decirte de antemano que muchisimas gracias por tu aportacion.

    Yo tengo el mismo problema que dice aqui arriba David. No se como adaptar el programa que nos das para que ademas pueda devolvernos la 4ª columna con los posibles caminos. (En el enunciado dice que no se puede pasar dos veces por el mismo nodo).
    Si tuvieras una posible solucion o alguna idea la verdad es que te lo agradeceria muchisimo.

    Un saludo y otra vez, muchas gracias.

  18. El Faker says:

    Ay… Alejandro, Alejandro …

    ¿Soy el único que se ha dado cuenta de que tu nuevo amigo de boadilla del monte es en realidad un compañero de tu facultad que no quiere más que pedirte las prácticas por la cara?

    Haciendo referencia a un comentario anterior:
    Pedro dice:
    octubre 8, 2013 a las 10:57 am
    Muchas gracias a ti. Yo estudio en la upm de boadilla del monte y nos pusieron una practica similar q ya entregue y evaluaron y al parecer tenia una serie de fallos pero no entregaron…

    ¿Una pregunta, esa práctica similar es casualmente la misma que te han mandado? Joder que casualidad, en TGI, en Algorítmica, hasta la página web de la asignatura de algorítmica de boadilla es idéntica a la del campus sur…

    No me extraña que la gente luego salga mal preparada, si os están dando la práctica del año pasado (las 2) y encima queréis que os haga la de este año también, estudiad un poco y aprended que de cara al futuro no va a servir copiar todo.

    (Entiendo que dejarte una cosa que no entiendas o que te expliquen cierta cosa pueda estar bien pero lo que estáis pidiendo es que os haga hasta la cama)

    De modo que Alejandro, no creo que publicar en internet 2 prácticas que siguen en vigor en la upm, sea la opción más correcta, al fin y al cabo las prácticas son propiedad de la upm y en cierto modo sería un sabotaje a la asignatura en curso…

    Creo que sería más recomendable publicar la práctica omitiendo cosas que requieran algo de esfuerzo para no dar todo el trabajo hecho o directamente explicar la practica con lenguaje verbal o en pseudocódigo (Que te falta adjuntar el .adb para poner la guinda)

    No te lo tomes como alguien frustrado por no dar la solución de la cuarta columna (faltaría más…), pero si quiero que lo tomes como consejo para evitar abusos, seguro que la mitad de los que te han puesto un comentario no son amigos tuyos y van a tu misma clase y si lo fuesen no creo que te lo hubiesen pedido por aquí…

    • AlejandroMoran says:

      Buenas noches, en primer lugar me gustaría agradecerte el tiempo que te has tomado en redactar tu crítica, mostrar los aspectos positivos y negativos del asunto puede revertir en un beneficio para todos, objetivo de mis entradas del blog.

      Tranquilo que no eres el único que se ha dado cuenta de lo que comentas sobre el compañero “Pedro”, pero aún conociendo el engaño no me importa ayudar a una persona que me lo pide.

      Si la gente sale bien o mal preparada dudo mucho que sea por copiar una o varias practicas, quizás ese problema se debe a causas mayores que no son objeto de estudio en este blog. En cualquier caso, copiar la práctica es decisión de cada uno y, tratándose de alumnos universitarios considero que cada uno tiene la capacidad de razonamiento suficiente para determinar el beneficio o perjuicio que copiar la práctica le supone.

      Cualquier persona que acuda a mí en busca de ayuda será correspondido de la manera que el trabajo y el tiempo me permita, se trata de compartir conocimiento y no de poner barreras.

      Para terminar y en referencia a tu último párrafo puedo decirte únicamente que a la hora de ayudar no me importa que la gente a la que ayudo sean amigos míos o no, si van a mi clase o van a cualquier otra, es un trabajo voluntario y desinteresado que me causa satisfacción cuando alguien me lo agradece.

      Un cordial saludo,
      Alejandro Morán.

  19. Alvaro says:

    Alejandro, en cuanto al comentario de El Faker he de decir que no le quito razon, pero no estoy del todo de acuerdo con el.

    Sobre todo en el tema de que si la practica es la misma que el año pasado no es culpa tuya que, como buena persona, quieras compartir con los demas su practica. Y sino, que el año que viene se molesten los profesores en trabajar un poco y hagan una nueva, que igual que ellos no se han molestado en proponer una nueva practica entiendo que los alumnos por su parte podran intentar hacer lo mismo.

    Yo por mi parte entregue la primera practica el año pasado, ya que no era obligatorio hacer las dos, y este año obligan a entregar las dos. Vamos, que encima de que ellos no hacen nada, te obligan a hacer el doble.
    No pido a Alejandro que me haga la practica porque ni esta bien ni el profesor la va a aceptar ya que no seria el unico que iba a tener la misma… Asiq por mi parte, si pudieras decirme Alejandro si se puede añadir algo al codigo que pones y asi solucionar lo que te comentamos o es necesario hacer una funcion a parte te lo agradeceria.

    Un saludo y muchas gracias.

  20. David says:

    Hola,

    Soy el compañero de Alejandro, el que hizo la práctica que ha publicado en la web, y en mi opinión el problema de que la gente salga como sale de la UPM no es por copiar una práctica o no…

    Los problemas en el caso de esta asignatura son:
    a) Se han empeñado en hacerla en un lenguaje de programación que nadie usa para nada, esto provoca que en muchos casos tengas mas problemas por el propio ADA en si que por solucionar el algoritmo que te piden.

    b) Que se molesten un poquito en pensar otra práctica y así no habrá problemas con copiar la práctica de años anteriores, porque en una asignatura que se llama Algorítmica, digo yo que habrá infinitos algoritmos que te podrán pedir… pero claro, es más fácil dejar las mismas (muy habitual en la UPM, y ya es de chiste que se compartan los enunciados de las prácticas entre la Escuela de Vallecas y la de Boadilla…)

    Para completar un poco más el razonamiento, tal vez los alumnos sabrían hacer la práctica si les explicaran algún algoritmo más ¿no? Ejemplo: http://es.wikipedia.org/wiki/Algoritmo_de_Floyd-Warshall

    Si gracias a este blog, Alejandro consigue que los profesores de la UPM cambien las prácticas cada año pues mejor, que con lo que pagamos de matrícula, es lo mínimo exigible…

    Slds.

Leave a Reply

Your email address will not be published. Required fields are marked *

*