Concertar tutoría por e-mail
Página de entrega de prácticas
Problemas
El día de entrega de problemas la clase de prácticas será en el aula de teoría.
Hoja 1 de problemas pdf (entrega: 4 de noviembre de 2011)
Prácticas
La asignatura TALF II estudia los esfuerzos del ser humano por establecer los límites de lo que se puede conocer, comprender y definir. Esta búsqueda de la definición de Verdad y de los límites humanos para capturarla culmina en el siglo XX unificando a filósofos, matemáticos y lingüistas en una nueva disciplina: la Computación. De esta forma la pregunta ¿Qué es verdad? se transforma en ¿Qué es computable? en un intento de conseguir la misma respuesta.
Tras los jarros de agua fría que suponen hallazgos como los de Kurt Gödel, Alonzo Church o Alan Turing, limitando cada vez más la capacidad del ser humano de capturar la Verdad, nos encontramos con que ni siquiera todo aquello que es computable en la teoría lo es, a escala humana, en la práctica: la Tratabilidad. Dos preguntas, abiertas a día de hoy, surgen de aquí: ¿Cuándo es un problema tratable? y ¿Cómo hacer frente a aquellos problemas no tratables?
Por extraño que pueda parecer, la cantidad de problemas no tratables presentes en la vida cotidiana es inmensa. El objetivo de las prácticas de TALF II es comprender las implicaciones de la No Tratabilidad y aprender algunas técnicas para hacerle frente. Para ello trabajaremos con uno de los problemas más extendidos: el Travelling Salesman Problem o problema del viajante. “¿Cuál es la ruta más corta que debe seguir el viajante para visitar sólo una vez todas las ciudades de una lista dada?” Este problema, bajo diferentes caras , se encuentra de forma directa en campos tan diversos como la logística, el diseño de circuitos, la genética y la proteómica, la orientación de satélites, el despegue de aviones, la gestión de redes y tantos otros más que “exigen” una solución.
Práctica 1 (entrega el 21 de octubre):
Enunciado: pdf
Ficheros necesarios:
p1ap1.dat Fichero de entrada para el apartado 1
p1ap2.dat Fichero de entrada para el apartado2
DOC.pdf Descripción del formato de los ficheros de mapas y cálculo de distancias de TSPLIB
Práctica 2 (entrega el 16 de diciembre):
Introducción a los algoritmos heurísticos
Enunciado: pdf
Ficheros necesarios:
Librería de problemas de TSPLIB
Mejores soluciones conocidas de TSPLIB
Webs de interés:
TSP Universität Heidelberg, Discrete Optimization Research Group.
Links interesantes
EteRNA: Juego diseñado por la Carnegie Mellon University para ayudar a resolver el problema del plegamiento de cadenas de ARN
Online Gamers Solve Structure: Artículo de Nature (Nature 477, 373, 22 September 2011). Jugadores on-line de Foldit encuentran el plegamiento de una proteína para la que no había solución.
Mis más sinceros agradecimientos a Iván Dotú por su trabajo y asesoramiento
Manuel García-Herranz 