Concertar tutoría: por e-mail Página de entrega de prácticas Página de teoría Parejas prácticas Notas de prácticas
Calendario
| octubre | noviembre | diciembre | enero | ||||||||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| L | M | X | J | V | S | D | L | M | X | J | V | S | D | L | M | X | J | V | S | D | L | M | X | J | V | S | D |
| 1 | 2 | 3 | 4 | 1 | 30 | 1 | 2 | 3 | 4 | 5 | 6 | 1 | 2 | 3 | |||||||||||||
| 5 | 6 | 7 | 8 | 9 | 10 | 11 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
| 12 | 13 | 14 | 15 | 16 | 17 | 18 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 11 | 12 | 13 | 14 | 15 | 16 | 17 |
| 19 | 20 | 21 | 22 | 23 | 24 | 25 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 18 | 19 | 20 | 21 | 22 | 23 | 24 |
| 26 | 27 | 28 | 29 | 30 | 31 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 28 | 29 | 30 | 31 | 25 | 26 | 27 | 28 | 29 | 30 | 31 | ||||
| F | iestas | P | ráctica 1 | P | ráctica 2 | P | roblemas | P | arciales | C | oncurso | ||||||||||||||||||
La asistencia a las horas de problemas y prácticas cuentan en la evaluación contínua
El primer día de la práctica 2 se corrige la prácica 1. Asistencia obligatoria
Problemas
Hoja 1 (6 de noviembre de 2009)
Hoja 2 (15 de enero de 2010)
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 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:
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:
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.
Mis más sinceros agradecimientos a Iván Dotú por su trabajo y asesoramiento
