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:
with Text_IO; use Text_IO;
with Ada.Command_Line; use Ada.Command_Line;
procedure practica is
type lista is array(1..100) of Boolean;
type matriz_adyacencia is array(1..100,1..100) of Integer;
mat_ady : matriz_adyacencia := (others => (others => 0));
num_nodos : Integer := 0;
package Int_IO is new Text_IO.Integer_IO (Integer); use Int_IO;
--Proc. Carga Datos desde el fichero en matriz
procedure CargarDatos (mat_ady : in out matriz_adyacencia; num_nodos : in out Integer) is
fich : Text_IO.File_Type;
fil, col, peso : Integer;
begin
put_line("Cargando datos desde el fichero...");
--Abro fichero
Text_IO.Open(fich,Text_IO.In_File,Argument (1));
--Guardo nº nodos
get(fich,num_nodos);
while not Text_IO.End_Of_File (fich) loop
get (fich, fil);
get (fich, col);
get (fich, peso);
--Simetrica
mat_ady(fil,col) := peso;
mat_ady(col,fil) := peso;
end loop;
--Cierro fichero
Text_IO.Close(fich);
end CargarDatos;
--Proc. Calcula Apartado 1
procedure Ap1 (mat_ady : matriz_adyacencia; num_nodos : Integer) is
fila, columna, cont, dist : Integer;
mat_resul : matriz_adyacencia;
fich_ap1 : Text_IO.File_Type;
begin
--Copiamos datos de matriz
mat_resul := mat_ady;
put_line("Calculando Ap1...");
fila := 1;
columna := 1;
cont := 1;
while (cont < num_nodos + 1) loop
while (fila < num_nodos + 1) loop
while (columna < num_nodos + 1) loop
--Me quedo con el menor
if (mat_resul(fila,cont) <= mat_resul(cont,columna)) then
dist := mat_resul(fila,cont);
else
dist := mat_resul(cont,columna);
end if;
-- Actualizo si dist es mayor
if(mat_resul(fila,columna) < dist) then
mat_resul(fila,columna) := dist;
end if;
columna := columna + 1;
end loop;
-- Pongo a 0 el valor de la diagonal
mat_resul(fila,fila) := 0;
fila := fila + 1;
columna := 1;
end loop;
cont := cont + 1;
fila := 1;
end loop;
--Crea fichero
Text_IO.Create(fich_ap1, Text_IO.Out_File, "apartado1.txt");
for fila in 1..num_nodos loop
for columna in 1..num_nodos loop
--Escribo cada linea del ap1 en el fichero
put (fich_ap1, fila);
put (fich_ap1, columna);
put (fich_ap1, mat_resul(fila,columna));
put_line (fich_ap1,"");
end loop;
end loop;
--Cierro fichero
Text_IO.Close(fich_ap1);
end Ap1;
--Proc. Calcula Apartado 2
procedure Ap2 (mat_ady : matriz_adyacencia; num_nodos : Integer) is
aux_i, aux_j : Integer := 1;
max, contador : Integer := 0;
visitados : lista := (others => false);
fich_ap2 : Text_IO.File_Type;
begin
put("Calculando Ap2...");
new_line;
--Creo fichero
Text_IO.Create(fich_ap2, Text_IO.Out_File, "apartado2.txt");
--Escribo num_nodos
put (fich_ap2, num_nodos);
put_line (fich_ap2, "");
--Pongo el primero como visitado
visitados(1) := true;
while (contador < num_nodos - 1) loop
max := 0;
for i in 1..num_nodos loop
for j in 1..num_nodos loop
if ((visitados(j) = false) And visitados(i) = true And max < mat_ady(i,j) And (mat_ady(i,j)/= 0) ) then
--Como es el maximo, se cambia
aux_i := i;
aux_j := j;
max := mat_ady(i,j);
end if;
end loop;
end loop;
contador:= contador + 1;
visitados(aux_j) := true;
--Escribo en el fichero
put (fich_ap2, aux_i);
put (fich_ap2, aux_j);
put (fich_ap2, max);
put_line (fich_ap2, "");
end loop;
end Ap2;
begin
--Cargo Datos
CargarDatos(mat_ady,num_nodos);
--Apartado1
Ap1(mat_ady,num_nodos);
-- Apartado 2
Ap2(mat_ady,num_nodos);
end practica;
El link de descarga esta roto.
Muchas gracias por avisar Pedro, ya está solucionado, en caso de necesitar algo puedes contactarme, un saludo.
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 :).
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!!
Muchas gracias y perdón por las molestias ^^.
Encuentras alguna solucion Alejandro es que tengo examen de esa practica el prox viernes si quieres q te facilite correo o algo dime :). Gracias.
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 🙂
Hola, te dejo la práctica de complejidad: http://pastebin.com/0txyTJww
Hola Anon, podrias volver a subir la practica de compejidad? que el archivo del pastebin ha sido borrado. Muchas gracias 🙂
Hola Jaime, como ya dije, me encargo de poner algo esta tarde 🙂
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.
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 🙂
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 =)
Tambien nosotros usamos java como lenguaje de la asignatura :). Muchas gracias Alejandro 😉
Hola Pedro, ya tienes disponible la práctica de TGI y un breve resumen del funcionamiento, un saludo =) http://alejandromoran.com/manejo-de-archivos-de-registros-con-gestion-de-lista-de-huecos/
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.
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.
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
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 😉
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.
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
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.
Alguien puede responder mi duda por favor?
En una nueva de entrada está la solución al apartado nuevo de este año y una breve explicación, un saludo.
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.
Hola, esta tarde si puedo subiré algo referente a la práctica de complejidad de algoritmos, un saludo.
En una nueva de entrada está la solución al apartado nuevo de este año y una breve explicación, un saludo.
Muchas gracias por la practica !, una gran ayuda 😉
De nada Margaret, me alegro de haber podido ayudarte, para lo que necesites me puedes contactar por aquí, un saludo.
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.
En una nueva de entrada está la solución al apartado nuevo de este año y una breve explicación, un saludo.
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.
En una nueva de entrada está la solución al apartado nuevo de este año y una breve explicación, un saludo.
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í…
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.
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.
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.