Algoritmos_Avanzados

Vicerrectorado de Profesorado, Titulaciones,

Ordenación Académica, Coordinación y Campus.

1 Última actualización: 06 de junio de 2012

GUÍA DOCENTE DE

ALGORITMOS AVANZADOS

Curso 2012-2013




TITULACION

Máster en Sistemas Telemáticos e Informáticos

GUIA DOCENTE DE LA ASIGNATURA

Algoritmos Avanzados

Profesores

Nombre y apellidos:

Abraham Duarte Muñoz ([email protected])

Micael Gallego Carrillo ([email protected])

Christopher Thraves ([email protected])

Coordinador/a de la asignatura:

Abraham Duarte Muñoz

I.- Identificación de la asignatura

Tipo Obligatoria

Materia

Período de impartición 2º cuatrimestre

Nº Créditos 3

Idioma en el que se imparte Español

Departamento Ciencias de la Computación y Departamento de Sistemas

Telemáticos y Computación




II.- Presentación

El objetivo fundamental de esta asignatura es la adquisición de las competencias necesarias para el

diseño y análisis de algoritmos, en especial aquellos para la resolución de problemas de optimización.

Como requisito previo para cursar esta asignatura es necesario disponer de los conocimientos y

competencias adquiridos en las asignaturas de grado de:

− Introducción a la Programación

− Estructuras de Datos

Se recomienda haber cursado la asignatura de Optimización de Sistemas de Comunicación del Máster

en Sistemas Telemáticos e Informáticos.

Además, es recomendable disponer de un nivel de comprensión escrita del idioma inglés que permita

comprender artículos científico-técnicos escritos en esta lengua.

III.- Competencias

Competencias transversales CG.1- Que los estudiantes sepan aplicar los conocimientos adquiridos y

su capacidad de resolución de problemas en entornos nuevos o poco

conocidos dentro de contextos más amplios (o multidisciplinares)

relacionados con su área de estudio

CG.3- Que los estudiantes sepan comunicar sus conclusiones –y los

conocimientos y razones últimas que las sustentan– a públicos

especializados y no especializados de un modo claro y sin

ambigüedades;

CG.4- Que los estudiantes posean las habilidades de aprendizaje que

les permitan continuar estudiando de un modo que habrá de ser en gran

medida autodirigido o autónomo.

CG.6- Capacidad para presentar un proyecto, defenderlo públicamente,

argumentar la confección del presupuesto asociado y presentar

mejoras o innovaciones añadidas al proyecto inicial.

CG.7- Capacidad para elaborar artículos científicos que expongan un

trabajo original llevado a cabo por los estudiantes. Conocimiento de las

tareas que conlleva una investigación a un nivel introductorio y será

consciente de la conexión con otras disciplinas para detectar

implicaciones.

Competencias específicas SI.1- Capacidad para diseñar, analizar y aplicar algoritmos para resolver

mecánicamente problemas matemáticos




SI.4- Capacidad para valorar las diferentes estrategias aplicables a un

problema de optimización y decidir el enfoque de mayor calidad a través

del desarrollo de un diseño experimental apropiado.

IV.- Contenido

IV. A. Temario de la asignatura

Bloque temático Tema Apartados

I.- Programación

Matemática

Tema 1. Introducción a la

Modelización Matemática

Problema de la modelización en el contexto

de la Programación Matemática en general y

en particular en Excel. Definición de variables,

restricciones y función objetivo que conforman

un problema de optimización. Uso de los

diferentes solvers que ofrece Excel y su

adecuación a los modelos matemáticos.

Tema 2. Programación Lineal

y método del simplex

Descripción del método Simplex. Método de

las dos fases para determinar la infactibilidad

del problema o, alternativamente, determinar

una solución posible básica inicial. Problemas

de la finitud y eventual ciclado del algoritmo,

mostrando el ejemplo de Beale y la regla de

Bland.

Tema 3. Programación Lineal

Entera y Programación

Solución óptima con valores enteros para

algunas de las variables. Adaptación de los

métodos lineales por truncamiento.

Algoritmos de resolución exacta

(Ramificación y Poda o Branch and Bound

por su nombre en inglés). Implementación con

el solver de Excel. Introducción a la

programación no lineal.

II.- Análisis de

Algoritmos

Tema 4. Problemas de

decisión versus problemas de

optimización; P, NP, NP-Hard,

NP-Complete.

Comprenda la diferencia entre un problema

de decisión y un problema de optimización.

Comprender la diferencia entre las familias

de problemas P y NP. Además, dentro de los

problemas NP, identificar aquellos de mayor

dificultad. Implicancias de una respuesta para

la pregunta clásica (todavía abierta), ¿P =

NP?




Tema 5. Algoritmos de

Aproximación

Entender qué quiere decir que un algoritmo

entregue una solución aproximada para un

problema de optimización. Saber demostrar

cotas de aproximación. Conocer resultados

clásicos.

Tema 6. Algoritmos Aleatorios Diseño y análisis de algoritmos aleatorios.

¿Cuándo son útiles? ¿Qué tipo de garantías

podemos esperar de ellos?

IV. B. Actividades obligatorias (evaluables):

1. Lecturas

Lectura de un

artículo científico

obligatoria.

La lectura de un artículo científico tiene como objetivo demostrar la comprensión

de los conceptos cubiertos en las clases teóricas. Particularmente, se espera que

el estudiante sea capaz de leer, comprender y exponer las ideas presentadas en

algún artículo científico en donde se presente un algoritmo, y se haga un análisis

teórico del mismo.

Cada estudiante deberá leer un artículo científico para luego presentarlo frente a

la clase. No obstante, si la comprensión de dicho artículo requiere de una revisión

de artículos previos, se espera que el estudiante así lo haga. Lo artículos

científicos para esta lectura deberán ser elegidos de entre una lista propuesta por

el profesor en clase. La evaluación de esta lectura será a criterio del profesor en

base a una presentación del artículo hecha por el estudiante para toda la clase.

2. Prácticas

Prácticas obligatorias

Las prácticas tendrán como objetivo fundamental aplicar los conocimientos adquiridos en clase en la

resolución de ejercicios y en el diseño e implementación de algoritmos de diversa índole. En concreto,

las prácticas estarán focalizadas en algoritmos y métodos de resolución de problemas de optimización.

Se realizarán 2 prácticas obligatorias de carácter individual. Cada una de ellas será introducida por el

profesor en clase. Se dará asesoramiento y una guía de cómo abordar la práctica. Queda como

responsabilidad del alumno la finalización de dicha práctica.

Para aprobar la asignatura todas las prácticas entregadas deberán tener una media igual o superior a 5.




V.- Tiempo de trabajo 1

Clases teóricas 12

Clases prácticas/de resolución de problemas, casos, etc. 0

Prácticas en laboratorios tecnológicos, clínicos, etc. 12

Realización de pruebas 0

Tutorías académicas 3

Actividades relacionadas: jornadas, seminarios, etc. 3

Preparación de clases teóricas 15

Preparación de clases prácticas/problemas/casos 30

Preparación de pruebas 0

Total de horas de trabajo del estudiante 75

VI.- Metodología y plan de trabajo

Clases teóricas

Periodo2 Contenidos

Semana 1 Tema 1

Semana 3 Tema 2

Semana 5 Tema 3

Semana 7 Tema 3

Semana 9 Tema 4 y 5

Semana 10 Tema 6

1 El volumen de trabajo está referido al trabajo del estudiante. La dedicación de los profesores a las diferentes actividades

docentes permite reconocer y valorar más adecuadamente su carga de trabajo, y por ello es conveniente desarrollar

herramientas que permitan conocer el tiempo que efectivamente dedica a sus alumnos más allá de las horas lectivas, pero no

son objeto de las guías docentes. Todas las actividades previstas deben tener una preparación mínima previa para el mejor

aprovechamiento del trabajo del alumno y para el control del responsable de la asignatura y del coordinador de titulación.

2 Especificar la semana en que está previsto desarrollar el tema.




Prácticas/de resolución de problemas, casos, etc.

Periodo Contenidos

Semana 2 Tema 1

Semana 4 Tema 2

Semana 6 Tema 3

Semana 8 Tema 3

Semana 11 Tema 4, 5 y 6

Tutorías académicas

Periodo

Sem. 3-13 Asesoramiento para la realización de las prácticas obligatorias

Pruebas

Fecha Contenidos

Semana 12 Presentación de artículo de investigación




VII.- Métodos de evaluación

VII. A. Ponderación para la evaluación continua

Actividad evaluadora Tipo3 Ponderación Periodo Contenido

Prueba:

Preguntas de

desarrollo escritas

Acumulativa

Liberatoria

Puntuación mínima

(de 1 a 10): 5

Reevaluable

(podrá reevaluarse

en la 2ª convocatoria)

No reevaluable

11% Semana

13

Temas 4, 5, 6

Prueba:

Presentación oral

Acumulativa

Liberatoria

Puntuación mínima

(de 1 a 10): 5

Reevaluable

(podrá reevaluarse

en la 2ª convocatoria)

No reevaluable

11% Semana

12

Temas 4, 5, 6

Prácticas fuera del aula:

Resolución de

problemas

Acumulativa

Liberatoria

Puntuación mínima

(de 1 a 10): 5.

Reevaluable

(podrá evaluarse en

la 2ª convocatoria)

No reevaluable (si

no supera la prueba,

repite curso)

11% Semanas

6-12

Temas 4, 5 y 6

Prácticas fuera del aula:

Resolución de

problemas

Liberatoria

Puntuación mínima

(de 1 a 10): 5.

Reevaluable

(podrá evaluarse en

la 2ª convocatoria)

No reevaluable (si

no supera la prueba,

repite curso)

66% Semanas

6-12

Temas 1, 2, 3

Total 100%

3 Cada una de las actividades evaluables pueden tener una calificación liberatoria o acumulativa para la calificación final. Se indicará, si hay una puntuación mínima exigida a las pruebas para que se consideren aprobadas y sean liberatorias. Se especificará si las pruebas son orales o escritas, y si son o no reevaluables.




VII. B. Ponderación para la evaluación de alumnos a tiempo parcial

Para que un alumno pueda optar a esta evaluación, tendrá que obtener la “Dispensa Académica” para la

asignatura, que habrá solicitado al Director de la Escuela Técnica Superior de Ingenieros de

Telecomunicación.

La “Dispensa Académica” no excluye de la evaluación continua. Dicha evaluación se acomodará por el

profesor, asistido por el director del máster, estableciéndose la adaptación curricular según las

características de cada caso concreto.

Para el caso de alumnos con “Dispensa Académica”, la evaluación de la actividad “Prácticas dentro del

aula: presentación de trabajos en grupo”, con un valor del 20% se sustituirá por una práctica de

resolución de problemas adicional a realizar fuera del aula.

VII. C. Revisión de las pruebas de evaluación.

Las prácticas presentadas por los alumnos son corregidas por los profesores y posteriormente se

establece un plazo de revisión durante el cual aquellos alumnos que lo deseen pueden solicitar la revisión

de sus prácticas.

VIII.- Recursos y materiales didácticos4

General

Título Programación lineal: Una introducción a la toma de decisiones cuantitativa

Autor Jesús S. Arreola Risa, Antonio Arreola Risa

Editorial Cengage Learning Editores, 2003

Título Computers and intractability: a guide to the theory of NP-completeness

Autor Michael R. Garey, David S. Johnson

Editorial W. H. Freeman

Complementaria

Título Introduction to Algorithms (2nd ed)

Autor COMEN, LEISERSON, RIVEST, STEIN

Editorial MIT Press

4Se recomienda no exceder de 20 títulos




Título The Design of Approximation Algorithms

Autor David P. Williamson, David B. Shmoys

Editorial Cambridge University Press

Título Probability And Computing: Randomized Algorithms And Probabilistic Analysis

Autor Michael Mitzenmacher, Eli Upfal

Editorial Cambridge University Press

Direcciones web de interés

IX.- Profesorado

Nombre y apellidos Abraham Duarte Muñoz

Horario de tutorías

académicas

Correo electrónico [email protected]

Departamento/área de

conocimiento

Ciencias de la Computación / Ciencia de la Computación e Inteligencia

Artificial

Categoría Prof. Titular de Universidad

Titulación Académica Licenciado en Físicas y Doctor por la URJC

Experiencia Docente

(Indicar la antigüedad en

el área y en la

asignatura. Incluir tramos

de docencia.)

11 años de experiencia docente universitaria (Universidad Rey Juan Carlos,

Universidad Nacional de Educación a Distancia y Universidad Complutense

de Madrid) impartiendo diversas asignaturas, como: Optimización de

Sistemas de Comunicación, Metaheurísticas, Estructuras de Datos y de la

Información, Bases de Lenguajes de Programación, Metodología y

Tecnología de la Programación, Redes, Estructuras de Datos Avanzadas,

Tratamiento Inteligente de Imágenes, Programación III, Web para Usuarios ,

Computación Neuronal y Evolutiva, Laboratorio de Programación ,




Electrónica de Potencia y Electrónica III, entre otras.

Tiene dos tramos docentes reconocidos.

Experiencia profesional

(Indicar la actividad

profesional y la

antigüedad en la misma)

Ha desarrollado labores de becario en la Universidad Complutense de

Madrid y en el instituto de Automática Industrial en el CSIC.

Participación en diversos convenios de investigación con empresas.

En torno a la treintena de publicaciones en diversos congresos nacionales,

internacionales, y revistas relacionados con Metaheurísticas, Visión Artificial,

Reconocimiento de Patrones, Electrónica, etc.

Participación en 9 proyectos de investigación y dirección de 1 proyecto de

investigación competitivo (CAM). Ha realizado estancias de investigación en

la Universidad de Colorado en Boulder y la Universidad de Valencia para

trabajar en problemas de optimización.

Nombre y apellidos Micael Gallego Carrillo


académicas

Lunes y miércoles, 16-18



conocimiento

Ciencias de la Computación / Ciencia de la Computación e Inteligencia

Artificial

Categoría Profesor Contratado Doctor

Titulación Académica Doctor en Ciencias de la Computación por la URJC

Experiencia Docente


el área y en la


de docencia.)

Profesor de la Universidad Rey Juan Carlos desde Febrero de 2007. Ha

impartido asignaturas de grado y postgrado en las temáticas de: Paradigmas

de programación (Funcional, Concurrente, Orientado a Objetos, Orientado a

Eventos), Procesadores de Lenguajes, Seguridad Informática, Ingeniería del

Software, Software avanzado, Diseño de Algoritmos e Investigación Operativa

(Optimización).

Ha obtenido en el año 2011 la evaluación positiva del programa Docentia de la

URJC. Dentro de sus intereses se encuentra la mejora en la docencia,

habiendo participado en dos proyectos de innovación educativa, la

elaboración de dos libros docentes y en el desarrollo de herramientas

educativas (entre las que destaca EclipseGavab:

http://code.sidelab.es/projects/eclipsegavab)

Tiene un tramo docente reconocido.



Pertenece al grupo de investigación Gavab (http://www.gavab.es) desde 2005

y su investigación se centra en el diseño, implementación y validación de




profesional y la


algoritmos de resolución aproximada de problemas de optimización, usando

las novedosas técnicas metaheurísticas. Codirige el laboratorio de desarrollo

software Sidelab (http://www.sidelab.es), que actúa como punto de encuentro

de desarrolladores y entusiastas de la programación con la impartición de

seminarios, desarrollo de herramientas con licencias libres, desarrollo de

proyectos de fin de grado y máster, etc.

De forma complementaria, desde 2006 colabora activamente con empresas

del sector de las tecnologías de la información prestando servicios de

consultoría y dirección de proyectos. Cabe destacar la colaboración entre los

años 2007 y 2010 con la empresa Solaiemes (http://www.solaiemes.com) en

el desarrollo de sistemas de emisión y gestión de video en tiempo real en

Internet y teléfonos móviles. Actualmente es asesor de investigación y

desarrollo de TS Company (http://www.tscompany.es), empresa tecnológica

especializada en software relacionado con la actividad física y el deporte.

Nombre y apellidos Christopher Thraves Caro


académicas



conocimiento

Departamento de sistemas telemáticos y computación GSyC

Categoría Investigador Juan de la Cierva

Titulación Académica Licenciado en Ciencias con mención en Matemáticas

Doctorado en Ingeniería Informática y Nuevas Tecnologías de la Información

Experiencia Docente


el área y en la


de docencia.)

Ha trabajando dos años (2001 y 2002) como profesor ayudante para

asignaturas introductorias de cálculo y álgebra en el Departamento de

Matemáticas, Facultad de Ciencias, Universidad de Chile.



profesional y la


Actualmente es investigador en el Departamento de Sistemas Telemáticos y Computación (GSyC) de la URJC. Dicho puesto ha sido financiado por el programa Juan de la Cierva del Gobierno español.

Previamente Christopher ha ejercido durante tres años como investigador para el INRIA (Instituto Nacional de Investigación en Informática y Aplicaciones, siglas en francés) primero en Burdeos y luego en Rennes, Francia. Christopher además ha realizado estancias laborales en los




laboratorios de Deutsche Telekom en Berlin, y estancias de investigación en Charles University, Praga, la Universidad Politécnica de Cataluña, Barcelona o la Universidad de Chile, Santiago de Chile.

Christopher cuenta en este momento con al rededor de 15 publicaciones científicas en conferencias o revistas internacionales. Todas ellas en el área de diseño y análisis de algoritmos. Además de haber participado en proyectos de investigación europeos y actualmente formar parte de un proyecto regional (CAM).

Algoritmos_Avanzados

Documents

Transcript of Algoritmos_Avanzados