Está disponible en el foro de moodle la evaluación de la segunda convocatoria.

Examen: 15 de septiembre de 2015, a las 9:00 de la mañana, en aula 4 del edificio Ada Byron. (Web EINA). Sirven las mismas aclaraciones y notas que en la convocatoria de junio.

Podéis consultar en los siguientes enlaces los resultados de vuestras respuestas a la encuesta oficial sobre la asignatura y sobre el profesor:

• encuesta sobre la asignatura
• encuesta sobre el profesor

Está disponible en el foro de moodle la evaluación de la primera convocatoria. Buen verano a todos.

El examen escrito tendrá lugar el 13 de junio de 2015 a las 9:00 horas en el aula A.15 del edificio Ada Byron. Ver en nota (1) lo que dice la normativa de evaluación en relación con este examen.

El examen práctico tendrá lugar el 16 de junio en el despacho del profesor a las 10:00. Están exentos de realizar este examen quienes hayan cumplido con los plazos de entrega fijados para las prácticas de laboratorio. Quienes deseen presentarse deberán entregar previamente en Hendrix las prácticas 1 y 2 resueltas. Ver en nota (2) lo que dice la normativa de evaluación en relación con este examen.

Aclaraciones:

• Se debe ir provisto del DNI o carnet universitario.
• Se permite llevar al examen los apuntes que se desee.
• No se permite utilizar ningún dispositivo electrónico (teléfonos, tabletas, lectores electrónicos, portátiles, etc).

Notas:

1. Examen escrito en el que se deberán resolver problemas de naturaleza similar a los ejercicios planteados en clase durante el cuatrimestre, a los problemas planteados en la prueba escrita intermedia y, en su caso, responder preguntas conceptuales o resolver algún ejercicio en el que se demuestre haber logrado los resultados de aprendizaje requeridos en la asignatura. La calificación obtenida pondera un 70% de la nota final de la asignatura. Los alumnos que hayan realizado la prueba escrita intermedia serán exentos de realizar una parte del examen escrito, debiendo realizar sólo una parte obligatoria del examen, que se determinará en ese mismo momento. En ese caso, la calificación obtenida en la prueba escrita intermedia pondera un 30%, y la de la parte obligatoria del examen escrito final un 40%.
2. Examen práctico de programación en laboratorio e individual. En cada convocatoria se realizará un examen práctico de programación en laboratorio, en el que se le plantearán al alumno ejercicios de naturaleza similar a los realizados en las prácticas o vistos en clase. La calificación obtenida pondera un 30% de la nota final de la asignatura. Los alumnos que hayan cumplido con los plazos de entrega fijados para las prácticas de laboratorio, serán exentos de la realización del examen práctico de programación en laboratorio convirtiéndose automáticamente la nota numérica obtenida en la evaluación de sus prácticas de laboratorio en su nota final de examen práctico de programación. No obstante, para los alumnos exentos del examen práctico que se presenten al mismo, en cualquier convocatoria, prevalecerá la nota obtenida en el examen práctico individual de programación.

“Simplex is not a polynomial time algorithm. Certain rare kinds of linear programs cause it to go from one corner of the feasible region to a better corner and then to a still better one, and so on for an exponential number of steps. For a long time, linear programming was considered a paradox, a problem that can be solved in practice, but not in theory!

Then, in 1979, a young Soviet mathematician called Leonid Khachiyan came up with the ellipsoid algorithm, one that is very different from simplex, extremely simple in its conception (but sophisticated in its proof) and yet one that solves any linear program in polynomial time. Instead of chasing the solution from one corner of the polyhedron to the next, Khachiyan’s algorithm confines it to smaller and smaller ellipsoids (skewed highdimensional balls). When this algorithm was announced, it became a kind of “"mathematical Sputnik", a splashy achievement that had the U.S. establishment worried, in the height of the Cold War, about the possible scientific superiority of the Soviet Union. The ellipsoid algorithm turned out to be an important theoretical advance, but did not compete well with simplex in practice. The paradox of linear programming deepened: A problem with two algorithms, one that is efficient in theory, and one that is efficient in practice!

A few years later Narendra Karmarkar, a graduate student at University of California, Berkeley, came up with a completely different idea, which led to another provably polynomial algorithm for linear programming. Karmarkar’s algorithm is known as the interior point method, because it does just that: it dashes to the optimum corner not by hopping from corner to corner on the surface of the polyhedron like simplex does, but by cutting a clever path in the interior of the polyhedron. And it does perform well in practice.

But perhaps the greatest advance in linear programming algorithms was not Khachiyan’s theoretical break through or Karmarkar’s novel approach, but an unexpected consequence of the latter: the fierce competition between the two approaches, simplex and interior point, resulted in the development of very fast code for linear programming.”

(Credit: S. Dasgupta, C. H. Papadimitriou, and U. V. Vazirani, Algorithms, McGraw-Hill, 2008.)

Se ha creado una página que contendrá información sobre la nueva asignatura de la especialidad de Computación: Bioinformática.

photo credit: Leigh Prather/ Shutterstock

Utilización de programación lineal para organizar la carga de un avión. Lo escribimos aquí hace ya un tiempo.

El problema del viajante de comercio se conoce en la literatura internacional como TSP (traveling salesman problem).

1. Libro de William J. Cook: In Pursuit of the Traveling Salesman: Mathematics at the Limits of Computation.
   • Página web del libro (incluye tabla de contenidos y PDF del primer capítulo).
2. Libro de David L. Applegate, Robert E. Bixby, Vašek Chvátal y William J. Cook: The Traveling Salesman Problem: A Computational Study.
   • Página web del libro (incluye tabla de contenidos y PDF del primer capítulo).
3. Premio de un millón de dólares USA a quien diseñe una solución “eficiente” del TSP o demuestre que es imposible encontrarla:
   • Problema P vs NP.
4. Un sitio web sobre el TSP:
   • TSP en la Universidad de Waterloo.
5. TSP en el cine:
   • Artículo: ‘Travelling Salesman’ movie considers the repercussions if P equals NP.
   • La película: trailer oficial.

Christos Papadimitriou told me that the traveling salesman problem is not a problem, it’s an addiction. (Jon Bentley, 1991)

Desde hoy, 11 de mayo, hasta el próximo día 29, está abierto el periodo de realización de encuestas sobre la docencia de la asignatura:

http://encuestas.unizar.es/

Las encuestas son muy importantes para facilitar la mejora, año a año, de la asignatura. Os rogamos dediquéis unos minutos de vuestro tiempo para responderlas.