Manuel García-Herranz

TALF 2 – Prácticas 2011-2012

Concertar tutoría por e-mail 

Página de entrega de prácticas 

Página de teoría

Parejas de prácticas

 Notas finales 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.

The metaheuristic Network

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.

CloteLab RNA CP Design


Mis más sinceros agradecimientos a Iván Dotú por su trabajo y asesoramiento