I Campeonato de Programación de MV

bLaKnI

Pues a mi me molaba lo del generador de laberintos... xD

Ademas, era buena idea, pues se podria haber visto la imaginacion de cada uno a la hora de hacerlos...
Yo pense en hacerlo mediante matrices de 0 y 1. xD

Bueno... no se...

Acerca de la propuesta actual, solo comentar que me parece que es algo "loco" intentarlo y basicamente, lo afirmo por una razón simple:

  • Actualmente, NO EXISTE un programa en el mercado ni en empresas privadas de autoproduccion, que realize dicha tarea. El porque, es muy simple aunque dificil de explicar, pues se basa en Estadistica. Existen resoluciones aproximadas con bastante precisión, pero ni mucho menos algo fiable. Pensad que, si este programa existiera, se terminarian los problemas de verificación en el mundo del Arte. De esta forma, se podria saber por el escaneado de una obra (pintura) si se trata de una original, o de una copia / duplicado / falsificación. ESTE ES, actualmente, el GRAN PROBLEMA de los que se dedican a ello (seguridad de museos, investigación artística, etc...).
    Hemos visto aproximaciones a la resolución, en una mezcla de classes entre Estadística aplicada y Automatas II.
    Claro está que, algo aproximado si se podria hacer, de hecho, con Matlab o Octave (para los GNU fashionists... xD) las opciones de redimensionado de imagen + descomposicion matricial mediante tecnicas como FFT & others, son de rapido acceso aunque insistio, (y por experiencia personal lo digo), redimensionar una imagen, significa encontrar aliasing a la larga, lo cual significa ue habrá perdidas siendo asi pues, una efectividad del algoritmo de un 85% aproximadamente. Con lo qual, de aqui no salimos.

Si alguien consigue una resolucion eficaz, que ralle el 50 % de efectividad, habremos hecho mucho.

Pienso que, seria genial que nos dedicaramos a buscar un objetivo comun, es decir, un problema realmente provocativo (xD) que lo sacaramos ENTRE TODOS. Si trabajamos en un codigo limpio y depurado, que nos vaya llegando a las manos de todos, y entre todos, intentemo solucionar partes del problema, podriamos hacer un gran programa.

Que hacer? No lo se... Pero podria ser una buena experiencia, antes que dividirnos en muchos grupos para ver "diferentes" soluciones.

Seria algo asi como "Todos para uno, y uno para todos" y no un "Unos cuantos para uno, y y varios de los que saldran para estos cuantos". No se si me explico... ¬¬ xDDD

gF

#31 estoy contigo por eso creo que el reto que yo propongo es mucho más adecuado ya que se puede ir mejorando entre todos el código y se puede ir comprobando si las soluciones encontradas son cada vez mejores, además el problema del viajante que es como se lo conoce, es un problema con muchas aplicaciones y para el cual no existe un algoritmo eficaz que lo resuelva, la única forma de encontrar la solución óptima es probar todas las posibles combinaciones y estas son billones o más en los ejercicios mas simples, para lo cual se necesitan supercomputadoras...
De hecho, si conseguiamos un algoritmo que consiguiera dar la solución óptima, la universidad nos propondría para el premio Turing, que para los que no lo conozcan sería como el Nobel de la informática...

Os animo a que probeis este problema, que encontremos la solución óptima es, diria yo, imposible pero intentar mejorar la mejor encontrada es un buen reto. Yo, como dije, conseguí un coste de 24597

Soltrac

A ver...no confundamos.

Podeis empezar por la parte sencilla. 2 imagenes del mismo tamaño y misma resolucion y compararlas pixel a pixel.

Eso sabeis hacerlo cualquiera.

A partir de ahi, exadle imaginacion.

PD: Mi proyecto de fin de carrera se basa en esto, así que con un poco de modificaciones tendría el programa en 0,1 listo XDDDD

PD2: Si quereis hacer un trabajo entre todos, lo mas interesante es hacer un programa de inteligencia artificial.

Yo tuve q hacer uno (q por supuesto no funciono) que resolvia puzles con piezas de diferentes tamaños. Si quereis, lo busco y os lo enseño para que entre todos lo intenteis hacer.

HangmaN

#33 claro eso esta muy bien, pero el problema es q luego nadie se apunta al concurso, tu estas terminando ingenieria informatica (x lo del programa de ia, q eso no se da en las tecnicas) y no creo q haya muxa gente con esos mismos conocimientos... :P asi que yo propondria empezar con problemas mas basicos y luego ir aumentando la dificultad :)

BlisZ

Normal que nadie se apunte, ingenieros aqui pocos xD

A

Vaya mierda de forma de puntuar.

Utilidades de la aplicacion: la aplicacion solo consta de una utilidad y es decir que % se parecen

Diseño:

15 puntos lol. en fin sin chorrada.

y recursos que gasta del pc 5 puntos. es decir que te curras tu diseño 3d con flash peliculas sin divx a pelo mil movidas que no tira en ningun ordenador y te llevas todos los puntos menos 5 ultimos no?

en fin sin chorrada.

X cierto gente a quien compare 1 pìxel con el resto buscando coincidencias asi buscando todos los pixels de la foto gl....

Soltrac

#34 yo he terminado la tecnica, q no la superior y si di IA. Te puedo asegurar q no me enseñaron nada, es mas, el examen fue un aprobado general pq el profesor se kedo sin tiempo para corregirlos (si no, suspenso). Eso si, los algoritmos de IA que se curre cada uno serian interesantes.

Te pongo un ejemplo. Un programa que sepa jugar al 3 en raya. Cada uno puede desarrollarlo de 300 maneras diferentes, algunos seran mas inteligentes q otros, pero ahi esta la gracia :)

y #36, nadie te dice q compares con el resto. Eso ya depende de cada uno.

Yo por ejemplo, pondria una opcion de que si queremos una comparativa perfecta. Entonces comparariamos los pixeles 1 a 1, es decir, pixel 1 de imagen A con pixel 1 de imagen B.

Si queremos darle mas margen, por ejemplo seria pixel 1 de imagen a con todos los de alrededor de imagen b.

gF

Bueno y que os parece el reto que he propuesto en el #30? En principio cualquiera que sepa programar podría empezar a pensar como resolverlo...

LOc0

Programas que no existen en el mercado, problema del viajante, inteligencia artificial. Creo que estamos apuntando un poquillo alto xD...

Salu2 ;)

PD: ya puestos a pedir podríamos entre todos sacar un algoritmo de factorización rápida y joderle el invento al amigo Rony xD (http://img87.imageshack.us/img87/2347/ronrivest8qf.jpg)

E

Veamos Idako, cito directamente lo que propones:

"En un principio la aplicación consistia en crear un generador de informes, es decir tu le pasas x datos estadísticos y se te genera un informe con gráficas y demás, pero creo que no es excesivamente complicado"

No es por tocar los huevillos, pero yo he trabajado 5 años en el sector del marketing relacional elaborando módulos OLAP para un par de aplicaciones de CRM. Y claro, eso de pasar datos y que saque un informe.... ES MUY GENÉRICO!!

Hay muchísima variedad de tipos de datos para representar, muchísimos estadísticos que obtener sobre esos datos y muchísimos tipos de gráficos. Con lo cual, no sé, o concretamos o el tema no está muy clarito.

El programa perfecto que tú propones (yo he hecho algo parecido) es aquel que analice la naturaleza de los datos que se le pasan (mediante técnicas estadísticas) y entonces determine qué gráficas y qué tipo de tablas son las adecuadas para mostrar la información. Si ese es el programa que buscas, no es por desmerecer a los foreros de MV/Desarrollo, pero no creo que lleguen a algo decente. Sobre todo pq requiere unas técnicas de data minning (minería de datos) de "agárrate y no te menees". Pero vamos, que sea cual sea la solución que la gente proponga, me parece que es mejor usar el coco y escribir un programa que estar jugando con la play o dejando que la TV te haga papilla el cerebro xDD

En cuanto a la 2ª idea me va mucho más, aunque también la veo como una propuesta muy poco específica. Yo no soy un experto en el tratamiento de imágenes. Pero últimamente he estado interesándome en algunas técnicas que se utilizan para el reconocimientos de caracteres manuscritos. Hay ciertas técnicas de IA como las redes neuronales, pero sobre todo los modelos ocultos de markov muy útiles. Pero antes de poder ser aplicados, hay unas 3 ó 4 técnicas de tratamiento gráfico que se acercan a lo que tú propones. Por ejemplo, un algoritmo que existe para "adelgazar" las letras y así poder aplicar esos métodos de IA que he mencionado.

Ahora bien, eso de que 2 imágenes se parezcan... yo me pregunto ¿en qué se tienen que parecer? ¿En el color? ¿En la posición de puntos negros y blancos? ¿En el tamaño? ¿En ....? Es que el concepto de "parecerse" es algo que la IA lleva años investigando. Justamente en técnicas de reconocimiento de patrones invariantes, es decir, que independientemente de la posición, color, o detalles, un sistema sepa reconocer qué es lo que está viendo.

Bueno, con esta parrafada no quiero criticar la idea del concurso, que me parece bueníiisima (pena no tener 15 años), sino simplemente que se propongan problemas más concretos y definidos.

Además, si me aceptáis una sugerencia, creo que es mejor comenzar por problemas sencillos y en los siguientes concursos ir añadiendo complejidad para de estar manera atraer a más gente. Si empezáis con algo jodido, no se apunta ni el tato.

Salu2 y al toro!

ReMaTxEs

El problema del viajante con tantos nodos... Oti!!! Aparte de que aplicando Prim a semejante grafo la solución no tiene xq ser la mas óptima.

El planteamiento del problemas es muy simple, comprobar todas las posibilidades, xo los recursos que necesitasen tal vez fuesen un pelín altos... xD

LOc0

#40 for president xD

Salu2 ;)

gF

Yo pienso que el del viajante es ideal para competir a ver quien consigue una mejor solución ya que se pueden usar algoritmos distintos, Floyd, Prim... o combinarlos, incluso en el fichero de entrada vienen las coordenadas de cada nodo con lo cual se podria intentar ya algo más complicado intentando dividir el problema en regiones para que fuera menos aleatorio...

E

#42 xDDDDDDDDDD Serás un tío grande, pero estudia!!!!!! (vena paternalista mode ON)
Asias por el cumplido jejejje. Oye, vas a participar en el concurso? ...

LOc0

#44 Jajajaja, ya hasta en MV me dicen que estudie más xD (En teoría ya estoy apuntado al concurso)

A ver gente, creo que tengo una proposición más "asequible" en la línea de lo que proponía Is4ko (tratamiento de imágenes).

Un lector de CAPTCHA

Para los que no sepan qué son los CAPTCHA -> http://en.wikipedia.org/wiki/Captcha

La idea sería crear una aplicación que introduciéndole CAPTCHAs de diferentes dificultades los "descifre". Así podríamos competir por ver quién consigue leer el CAPTCHA más "jodido". (O unir nuestras fuerzas y sacarlo entre todos).

¿Qué opináis?

Salu2 ;)

E

LoCo, no sé si te das cuenta (obviamente sí) de lo que propones. Propones un programa que prácticamente intente reconocer caracteres manuscritos. Cuando digo manuscritos, digo caracteres no iguales. Manuscritos no son, puesto que son caracteres tipográficos desvirtuados. Pero eso es a lo que me refería en un post que he puesto antes: LA INVARIANZA.

A mí lo que propones me parece un reto interesantíiiiiiisimo. De hecho, llevo tiempo buscando un algoritmo para hacer eso mismo pero con caracteres manuscritos, que viene a ser lo mismo.
Y te aseguro que el tema es jodido. Ya no por la búsqueda de algoritmo en sí, que es apasionante, sino por las técnicas de tratamiento gráfico que hay que aplicar a la imagen.

Creo que nadie se va a lanzar a ese reto, casi seguro. Bueno, quien sabe.

Te propongo una modificación del tuyo con una variación importante:

Un OCR universal. Te cuento:

Un programa que tenga como entrada una imagen escaneada con letras, vale? Imaginemos la página de un libro. Esos caracteres sí son lineales y repetidos. Y además hay miles de códigos por ahí, sobre todo de proyectos fin de carrera, que de manera más o menos cutre son capaces de reconocer el texto (el típico OCR). Sin embargo, lo reconocen porque comparan cada caracter mediante, normalmente redes neuronales, con una base de datos de caracteres estándar.

Ahora bien, yo lo que propongo es un programa que como entrada tenga una imagen escaneada de cualquier página de un libro con letras (pueden ser símbolos chinos, árabes, no tienen pq ser sólo latinos), y a partir de ahí sea capaz de ver cuáles se repiten y obtener el abecedario de los símbolos que encuentre.

El problema hay que verlo desde una perspectiva distinta a la clásica del OCR, porque en este caso no se compara la imagen con otras. Se compara la imagen con todas las que se van encontrando y se busca el parecido para catalogarlas. Además, como hablamos de una imagen escaneada de un libro, los caracteres son "fáciles de comparar", es decir, la técnica que utilicemos dificilmente nos va a engañar pq una "a" va a ser siempre una "a", no como en un texto escrito a mano. La clave está en cómo "almacenar" o "describir" las características de un símbolo para poder ser comparado con otro. He ahí el quid del asunto. (Hasta aquí puedo leer como decía aquel... no voy a revelar mi secreto xDDDDD)

A que este te mola más?

El pavo que haga eso habrá hecho un OCR universal. Le sudará la polla que el texto sea en castellano, alemán, chino mandarín o persa antiguo. ¿Pilláis la idea? Yo planteo esto pq ya tengo pensado un algoritmo que creo que es capaz de ello, me hace falta modelizarlo matemáticamente, probarlo sobre el papel y después programarlo.

Creo que para el concurso a lo mejor es muy ambicioso, pero si queréis demostrar que tenéis un buen coco, al toro!!

Salu2

P.D.: Por cierto, esto que prongo tiene cierto aire a lo que proponía Idako de comparar 2 imágenes, o sea, que no es tan descabellado. Aunque el fin es distinto.

P.D.2: Ahora que leo por ahí arriba propuestas para unir las fuerzas y hacer algo conunto, creo que si se hiciera algo de esa forma (que al final nunca, se hace, pero wno...) el lenguaje debería ser C# y la plataforma .NET Y no voy a argumentar el porqué, ya que tendríais que leer un post de 4242435243243 líneas. Además, con SharpDevelop, tenemos una plataforma .NET opensource.

E

#30, mala suerte, los hay qlo han hecho con un coste menor:

http://dis.um.es/ginesgm/retoviajante.html

Y son de tu uni.

Aunque ya veo que sí ganaste el año pasado, es por ello que fijaron un coste menor al que tu indicas.

;)

IS4kO

Wenas a todos, no he podido contestar post's antes por falta de tiempo, pero resumiendo:

Los dos proyectos que expuse, tienen como unico objetivo especificar un punto de partida, a partir del cual poder crear, ser original, que no tengas pq basarte en las ideas de probabilidad de Markov, sino que tengas toda la vía libre posible.

Si Pepito Perez, ha trabajado dos lustros realizando generaciones de informes con módulos OLAP para aplicaciones CRM me parece fantástico, genial, divertido, entrentenido, educativo y no se que más... pero como comentaba anteriormente, el objetivo es tener un punto de partida, y voy a explicar el pq del proyectito de las gráficas.

El principal motivo que me movió a pensar en ello, fue que por este foro la tecnología predominante es php y lenguajes dinámincos dirigidos a web, bien, pues cualquier persona que sepa un poquito de javascript, o un poquito de php, o un poquito de html o un muchito de cualquier otro lenguaje, es capaz de que pasando un número X por una caja de texto, se me genere una gráfica que represente dicho número X afectando a conjuntos de datos que no tienen pq ser ni reales ni complejos, por ejemplo el usuario A ha metido 5 goles de los 78 que ha metido su equipo de futbol... que más da los datos siempre y cuando sean claros y legibles

AHORA, ese es el punto de partida, lo más básico, pero y si de esa simple gráfica de los goles, empezamos a meterle por ejemplo, que dichos resultados puedan ser expuestos en una gráfica de barras, en una gráfica lineal, o que dicha gráfica sea un archivo swf con su correspondiente interacción animada en flash, o incluso, y si permitimos que esa gráfica y sus datos puedan exportarse a excell, o que los datos devueltos esten encriptados y se metan en una cookie o en un soporte físico......

En fin, que de un mero punto de partida simple, cada uno atendiendo a sus capacidades podría haberlo complicado, muchisimo mas, resultando un verdadero proyecto INTIMO Y PERSONAL, no teniendo que estar atadado a ninguna espeficación típica de proyecto a la que por lo que veo algunos podemos estar sujetos normalmente, o incluso teniendo que inventar tus propios algoritmos no teniendo que copiar a Markov, Stallman, Mitnick, Minski, Cox, ...

Y de ahí que se pudieran valorar varios aspectos de la aplicación: las utilidades que pudiera tener, el aspécto estético de la misma etc...

De todas formas, una vez dicho esto, y atendiendo a que no todo el mundo en esta comunidad tiene una carrera, y puede pilotar temas de IA, de recursividad, de automatismos, o de logaritmos de reducción de recursos o de estadística avanzada.... daremos desde hoy hasta el miercoles 22 de marzo para que se voten los posibles proyectos que habeis propuesto, atendiendo a que si se prefiere en vez de un concurso puede elaborarse un proyecto conjunto, aunque, esto ya se ha intentado otras veces y no es que haya tenido mucho éxito.

E

Aquí el problema que percibo es el siguiente. La gente demanda programas donde se pueda competir objetivamente, es decir, de una única solución optimizada.
Nadie juzgará tu trabajo.
Y, por otro lado, se proponen programas de solución subjetiva, aunque eso sí, con más libertad de creación.
Podría haber 1 de cada tipo para que la gente tuviera donde elegir.

Salu2

EnZo

El problema real esque aqui cada uno quiere proponer un reto en su campo. Y cuanto mas dificl mejor.

Pero esto no es un foro de ingenieros. Y no podeis proponer un juego en el que participen 3 personas contadas, por muy excitante que os parezca la idea.

Hay que hacer algo generico que valga para todos o para casi cualquier lenguaje decente. Y si quereis hacer lo de comparar dos imagenes o leer un documento manuscrito, deberiais quedar en el msn y desarrollarlo entre vosotros porque aqui en este foro no podriamos participar ni la mitad.

Los mas adecuados son el que propuso isako en un principio o el del viajante, que en principio casi todo el mundo puede hacerlo, aunque el del viajante tiene mucho nivel.

LOc0

Haya paz. Creo que lo mejor sería que empezáramos con algo sencillo y en función de la respuesta que tenga el concurso complicarlo más después (o no).

El problema del viajante de la uni de gf me parece de sobra para empezar.

Mi voto por él.

Salu2 ;)

PD: Es obvio que para hacer algo competitivo se deben tener conocimientos de grafos. (Es jodido separar la programación de las matemáticas cuando se plantea programar algo medianamente "serio" )

Sagrath

pero entonces se va a hacer alguno?

E

#52, .NET es una plataforma de desarrollo multilenguaje made in Microsoft y C# es uno de los lenguajes que soporta. Pero C# no está vinculado a Microsoft. Es una evolución de C++.
Como ejemplo: http://www.borland.com/downloads/download_csharpbuilder.html

IS4kO

Acabado el plazo de votación, el proyecto ganador ha sido el de gF. Se abre el plazo de inscripción hasta el sábado 25/03/2006 a las 24:00.

El proyecto queda definido de la siguiente forma, he metido alguna pequeña compliación más para que resulte un poco más entretenido, el fin es el mismo, solo que ahora tendremos 3 grafos correspondientes a 3 paises, divididos en 3 ficheros de texto:

PRESENTACION

Un maestro decide aprovechar sus proverbialmente largas vacaciones para hacer turismo por Europa (España, Francia e Italia); tanto que piensa que tendrá tiempo suficiente para visitar varios pueblos y pasises. Pero como no tiene el sueldo de un ministro y el precio del petróleo está por las nubes (antes cúmulos, ahora cirros) tendrá que planificar al milímetro la ruta a seguir para minimizar la distancia total recorrida. Con mucha paciencia se ha creado un mapa con los más de 1000 sitios a visitar, incluyendo las carreteras nacionales y comarcales que los unen. Comoquiera que reside en Murcia, su ruta deberá empezar y acabar en la capital murciana.

EL PROBLEMA

Dado un grafo no dirigido, conexo y etiquetado con pesos enteros, encontrar el ciclo de menor coste resultante de ir de un nodo a otro, es decir dado que la salida se realiza desde murcia calcular el coste minimo posible para llegar a un nodo Destino, o dicho de forma mas simple, encontrar el camino más corto entre dos puntos

imagen de ejemplo: http://dis.um.es/ginesgm/grafopeque.gif

ENTRADA

a) Ficheros

La entrada se realizará mediante varios ficheros de texto:
Fichero A en el que como se explica en el punto b aparecen las ciudades de España
Fichero B en el que como se explica en el punto b aparecen las ciudades de Francia
Fichero C en el que como se explica en el punto b aparecen las ciudades de Italia

b) Descripcion

La descripción del grafo de ciudades y carreteras viene dada en el fichero de texto (A,B,C), que tiene el siguiente formato. La primera línea contiene un único número, N, que indica el número total de nodos del grafo (Ciudades). La siguiente línea contiene otro entero, M, que indica el número de aristas del grafo(Carreteras). La tercera línea también contiene un único entero, F, que indica el nodo que debe ser inicio y fin del ciclo (atendiendo a que si viajamos a otro pais, el fin de ciclo de ese fichero será el nodo que haga de frontera y empalme con el nodo inicio del siguiente fichero). Los nodos del grafo son numerados desde 1 hasta N.

A continuación vienen N líneas, una por cada nodo. Cada línea i-ésima contiene dos enteros separados por un espacio en blanco: Xi, Yi, que indican las coordenadas relativas de la ciudad i-ésima en el mapa. Esta información se ofrece simplemente a efectos de visualización del grafo.

Finalmente vienen M líneas, una por cada arista del grafo. Cada línea contiene tres enteros separados por espacios en blanco: U, V, C, siendo U y V los nodos unidos por la arista y C el coste de la misma. Recordar que el grafo es no dirigido, por lo que la arista (U, V) y la (V, U) son la misma.

SALIDA

La salida debe ser un fichero de texto con el siguiente formato. La primera línea contendrá un único número entero, P, que indicará el coste total del ciclo encontrado (es decir, la suma de los costes de las aristas por las que pasa). La siguiente línea contendrá otro entero, T, que indicará el número total de nodos del ciclo, contando dos veces el nodo de comienzo y fin del ciclo. A continuación vendrán T líneas, cada una con un entero entre 1 y N, que indicarán los sucesivos nodos del ciclo encontrado. La primera y la última de estas líneas deberán tener necesariamente el valor F, que corresponde al nodo de Murcia.

E

Más info:
http://dis.um.es/ginesgm/retoviajante.html

...

...

BlisZ

entonces .net que lenguaje es? xD

Tema cerrado