Podéis consultar en los siguientes enlaces los resultados de vuestras respuestas a la encuesta oficial sobre el profesor y sobre la asignatura:
Está disponible en el foro de moodle la evaluación de la primera convocatoria. Buen verano a todos.
Están disponibles en moodle las notas de prácticas de la primera convocatoria.
.
Quienes tienen su dirección de correo de unizar redirigida a alguna cuenta de hotmail, NO están recibiendo los mensajes enviados desde unizar (debido a un problema de “mala reputación” del servidor de correo de unizar a ojos de hotmail). En particular, no están recibiendo mensajes que estoy enviando con posibles problemas de las prácticas.
El examen escrito tendrá lugar el 14 de junio de 2016 a las 15:30 horas en el aula A.07 del edificio Ada Byron. Ver en la nota (*) 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).
Nota:
(*) 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%.
.
.
Los siguientes párrafos están extraÃdos de este informe de la Oficina Ejecutiva del Presidente de los Estados Unidos: Report to the President and Congress. Designing a digital future: Federally funded research and development in networking and information technology (página 71, diciembre, 2010).
Progress in Algorithms Beats Moore’s Law
Everyone knows Moore’s Law –a prediction made in 1965 by Intel co-founder Gordon Moore that the density of transistors in integrated circuits would continue to double every 1 to 2 years.
Fewer people appreciate the extraordinary innovation that is needed to translate increased transistor density into improved system performance. This effort requires new approaches to integrated circuit design, and new supporting design tools, that allow the design of integrated circuits with hundreds of millions or even billions of transistors, compared to the tens of thousands that were the norm 30 years ago. It requires new processor architectures that take advantage of these transistors, and new system architectures that take advantage of these processors. It requires new approaches for the system software, programming languages, and applications that run on top of this hardware. All of this is the work of computer scientists and computer engineers.
Even more remarkable –and even less widely understood– is that in many areas, performance gains due to improvements in algorithms have vastly exceeded even the dramatic performance gains due to increased processor speed.
The algorithms that we use today for speech recognition, for natural language translation, for chess playing, for logistics planning, have evolved remarkably in the past decade. It’s difficult to quantify the improvement, though, because it is as much in the realm of quality as of execution time.
In the field of numerical algorithms, however, the improvement can be quantified. Here is just one example, provided by Professor Martin Grötschel of Konrad-Zuse-Zentrum für Informationstechnik Berlin. Grötschel, an expert in optimization, observes that a benchmark production planning model solved using linear programming would have taken 82 years to solve in 1988, using the computers and the linear programming algorithms of the day. Fifteen years later –in 2003– this same model could be solved in roughly 1 minute, an improvement by a factor of roughly 43 million. Of this, a factor of roughly 1,000 was due to increased processor speed, whereas a factor of roughly 43,000 was due to improvements in algorithms! Grötschel also cites an algorithmic improvement of roughly 30,000 for mixed integer programming between 1991 and 2008.
The design and analysis of algorithms, and the study of the inherent computational complexity of problems, are fundamental subfields of computer science.
.
Veremos en clase alguna de las ideas básicas del algoritmo del simplex (ver transparencias 54 a 70 de la asignatura, o transparencias 16 a 36 de estas otras del material adicional).
No obstante, su implementación detallada dista de ser sencilla. Por ejemplo, en esta anotación del blog de Jeremy Kun puede encontrarse una descripción más detallada, con enlaces a temas relacionados y al código escrito por el autor del blog:
En cuanto a la solución en tiempo polinómico de los problemas de programación lineal, en esta anotación puede leerse algún párrafo extraÃdo del libro de Dasgupta, Papadimitriou y Vazirani sobre los algoritmos de Khachiyan y Karmarkar:
Desde ayer, 9 de mayo, hasta el próximo dÃa 27, está abierto el periodo de realización de encuestas sobre la docencia de la asignatura:
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.
El curso pasado alcanzamos un 50% de respuestas en esta asignatura. Nos gustarÃa superar esa cifra.
La semana próxima empezamos con la técnica de ramificación y poda, una estrategia de búsqueda informada especialmente adecuada para problemas de optimización para los que las técnicas anteriores (dividir para vencer, voraz, programación dinámica, u otras) no dan una solución satisfactoria.
Un ejemplo reciente de aplicación es el planteado en este artÃculo, en el que se presenta un algoritmo de ramificación y poda para la solución del problema de balance de flota en un sistema de bicicletas de uso compartido:
“A branch-and-bound algorithm for solving the static rebalancing problem in bicycle-sharing systems”, por A.A. Kadri, I. Kacem y K. Labadi; en Computers & Industrial Engineering, Vol. 95, May 2016, Pág. 41–52 (el artÃculo puede verse completo o descargar el PDF de forma gratuita desde la red de Unizar).
Sistema de bicicletas de uso compartido (© artÃculo enlazado arriba)
.
No es extraño que en entrevistas de trabajo relacionadas con la Computación aparezcan problemas resolubles mediante programación dinámica.
Aquà hay algunos de ellos:
What are the top 10 most popular dynamic programming problems among interviewers?
