GUÍA DOCENTE CURSO: 2015-16 DATOS BÁSICOS DE LA ASIGNATURA Asignatura: Estructura de Datos y Algoritmos II Código de asignatura: 40152203

Plan: Grado en Ingeniería Informática (Plan 2015)

Año académico: 2015-16

Ciclo formativo: Grado

Curso de la Titulación: 2

Tipo: Obligatoria

Duración: Segundo Cuatrimestre

DISTRIBUCIÓN HORARIA DE LA ASIGNATURA SEGÚN NORMATIVA Créditos:

6

UTILIZACIÓN DE LA PLATAFORMA VIRTUAL:

Horas Presenciales del estudiante:

45

Horas No Presenciales del estudiante:

105

Total Horas:

150

Apoyo a la docencia

DATOS DEL PROFESORADO Nombre

Bienvenido Bárcena, José Fernando

Departamento

Dpto. de Informática

Edificio

Edificio Científico Técnico III Matemáticas e Informática (CITE III) 2

Despacho

180

Teléfono

+34 950 015691

Recursos Web personales

Web de Bienvenido Bárcena, José Fernando

Nombre

Flores Parra, Isabel María

Departamento

Dpto. de Informática

Edificio

Edificio Científico Técnico III Matemáticas e Informática (CITE III) 2

Despacho

100

Teléfono

+34 950 015684

Recursos Web personales

Web de Flores Parra, Isabel María

E-mail (institucional)

E-mail (institucional)

[email protected]

[email protected]

Este documento ha sido firmado con el certificado de Sello de Entidad de la UNIVERSIDAD DE ALMERÍA. Puede verificar la autenticidad, validez e integridad de este documento en la dirección: https://verificarfirma.ual.es/verificarfirma/?CSV:=GJ/uct1vFIreGQiTs2xmAQ== VERIFICADOR: https://verificarfirma.ual.es/verificarfirma/

CSV: GJ/uct1vFIreGQiTs2xmAQ==

ORGANIZACIÓN DE LAS ACTIVIDADES Actividades previstas para el aprendizaje y distribución horaria del trabajo del estudiante por actividad (estimación en horas) Gran Grupo

I. ACTIVIDADES DEL ESTUDIANTE (Presenciales / Online)

0,0

Grupo Docente

26,0

Grupo de Trabajo/Grupo Reducido

19,0

Total Horas Presenciales/On line ...

II. ACTIVIDADES NO PRESENCIALES DEL ESTUDIANTE (Trabajo Autónomo)

( Trabajo en grupo, Trabajo individual )

105

Total Horas No Presenciales ...

TOTAL HORAS DE TRABAJO DEL ESTUDIANTE

105 150,0

Este documento ha sido firmado con el certificado de Sello de Entidad de la UNIVERSIDAD DE ALMERÍA. Puede verificar la autenticidad, validez e integridad de este documento en la dirección: https://verificarfirma.ual.es/verificarfirma/?CSV:=GJ/uct1vFIreGQiTs2xmAQ== VERIFICADOR: https://verificarfirma.ual.es/verificarfirma/

45,0

CSV: GJ/uct1vFIreGQiTs2xmAQ==

ELEMENTOS DE INTERÉS PARA EL APRENDIZAJE DE LA ASIGNATURA Justificación de los contenidos Esta asignatura se centra fundamentalmente en el diseño y desarrollo de algoritmos para resolución de problemas complejos, utilizando las técnicas de diseño algorítmico como los algoritmos voraces, divide y vencerás, Programación dinámica, “backtracking” y “Branch-and-Bound”. Realizando los oportunos análisis de eficiencia en casos de aplicación. Para ello se utilizará un lenguaje de programación orientado a objetos como es Java y todo la tecnología que este engloba. Todo el desarrollo a realizar en la asignatura se abordará utilizando herramientas actualizadas y tecnologías propias de la ingeniería informática, basándose en la tecnología vista en cursos anteriores o paralelos.

Materia con la que se relaciona en el Plan de Estudios Continuación de: Estructuras de Datos y Algoritmos I Requiere una buena base de: Introducción a la Programación. Metodología de la Programación. Lógica y Algorítmica. Tiene cierta conexión con: Ingeniería del software. Bases de Datos. Conocimientos necesarios para abordar la Asignatura Para abordar la asignatura el alumno deberá cursar (y a ser posible superar) las asignaturas de Introducción a la Programación, Metodología de la Programación y Lógica y Algorítmica del primer curso del Grado en Ingeniería Informática, así como Estructuras de Datos y Algoritmos I de segundo curso. Los conocimientos previos requeridos suponen que el alumno debe tener conocimientos y práctica consolidada de un lenguaje de programación orientado a objetos, en nuestro case de Java. Requisitos previos recogidos en la memoria de la Titulación Oficialmente ninguno. Aunque sería conveniente haber cursado y a ser posible superado las asignaturas relacionadas del primer curso de la titulación: Introducción a la Programación, Metodología de la Programación, Lógica y Algorítmica, así como la asignatura del primer cuatrimestre del segundo curso, Estructuras de Datos y Algoritmos I.

COMPETENCIAS Competencias Generales Competencias Genéricas de la Universidad de Almería Capacidad para resolver problemas Capacidad de crítica y autocrítica Trabajo en equipo Otras Competencias Genéricas Comprender y poseer conocimientos Aplicación de conocimientos Capacidad de comunicar y aptitud social

Competencias Específicas desarrolladas CC05: Conocimiento, administración y mantenimiento de sistemas, servicios y aplicaciones informáticas. (Java). CC06: Conocimiento y aplicación de los procedimientos algorítmicos básicos de las tecnologías informáticas para diseñar soluciones a problemas, analizando la idoneidad y complejidad de los algoritmos propuestos. (Hecha a propósito para la asignatura; resume sus objetivos de aprendizaje). CC07: Conocimiento, diseño y utilización de forma eficiente de los tipos y estructuras de datos más adecuados a la resolución de un problema. (Se debe empezar a adquirir en EDA I, y en EDA II, perfeccionarse). CC08: Capacidad para analizar, diseñar, construir y mantener aplicaciones de forma robusta, segura y eficiente, eligiendo el paradigma y los lenguajes de programación más adecuados. (Se deberá elegir la técnica algorítmica más adecuada, y realizar los análisis de eficiencia para garantizar la idoneidad de la solución). CT8: Conocimiento de las materias básicas y tecnologías, que capaciten para el aprendizaje y desarrollo de nuevos métodos y tecnologías, así como las que les doten de una gran versatilidad para adaptarse a nuevas situaciones. (Según el problema, una técnica de diseño puede llevar a un algoritmo muy eficiente, mientras que otra, a uno muy poco eficiente. Se necesita capacitación para el aprendizaje, para aplicar el enfoque más adecuado). CT9: Capacidad para resolver problemas con iniciativa, toma de decisiones, autonomía y creatividad. Capacidad para saber comunicar y transmitir los conocimientos, habilidades y destrezas de la profesión de Ingeniero Técnico en Informática. (Se trabaja con supuestos prácticos variados y realistas, que motivan la creatividad del alumno. En las presentaciones de los distintos grupos, los alumnos deben defender sus decisiones, fomentando la transmisión de conocimiento).

OBJETIVOS/RESULTADOS DEL APRENDIZAJE • Proporcionar al alumno las técnicas algorítmicas básicas que le permitirán abordar el desarrollo de programas correctos y eficientes para resolver problemas, siendo capaz de aplicar de forma eficiente los cinco esquemas algorítmicos básicos: divide y vencerás, voraces, programación dinámica, “backtracking” y “branch and bound”. • Profundizar en el diseño y evaluación de los algoritmos. • Proporcionar al alumno la capacidad de seleccionar las estructuras de datos y de las técnicas algorítmicas más adecuadas para la resolución de un problema concreto. • Ampliar el manejo de la recursividad como herramienta para la construcción de programas. •

Este documento ha sido firmado con el certificado de Sello de Entidad de la UNIVERSIDAD DE ALMERÍA. Puede verificar la autenticidad, validez e integridad de este documento en la dirección: https://verificarfirma.ual.es/verificarfirma/?CSV:=GJ/uct1vFIreGQiTs2xmAQ== VERIFICADOR: https://verificarfirma.ual.es/verificarfirma/

CSV: GJ/uct1vFIreGQiTs2xmAQ==

Profundizar en el aprendizaje de la programación orientada a objetos con Java. Introducir técnicas para diseñar programas de tamaño medio. Proporcionar al alumno más experiencia en el campo de la programación mediante la realización de prácticas y de ejecución de pruebas unitarias.

Este documento ha sido firmado con el certificado de Sello de Entidad de la UNIVERSIDAD DE ALMERÍA. Puede verificar la autenticidad, validez e integridad de este documento en la dirección: https://verificarfirma.ual.es/verificarfirma/?CSV:=GJ/uct1vFIreGQiTs2xmAQ== VERIFICADOR: https://verificarfirma.ual.es/verificarfirma/

CSV: GJ/uct1vFIreGQiTs2xmAQ==

BLOQUES TEMÁTICOS Y MODALIDADES ORGANIZATIVAS Bloque Análisis algorítmico. Repaso. Contenido/Tema 1. Presentación de la asignatura. 2. Análisis de algoritmos. 1. Repaso de los conceptos generales. 2. Notaciones asintóticas (repaso). 3. Resolución de ecuaciones recurrentes. Cambio de variable y otras técnicas.

Modalidades Organizativas y Metodología de Trabajo Modalidad Organizativa

Procedimientos y Actividades Formativas

Grupo Docente

Clases magistrales/participativas

Observaciones

Horas Pres./On line 2,0

Descripción del trabajo autónomo del alumno Asistencia Teoría. Estudio personal. Asistencia a tutorías. Consulta de bibliografía. Búsqueda de información en internet. Ejercicios opcionales.

Bloque

Estrategia divide y vencerás.

Contenido/Tema Divide y Vencerás 1. Introducción. 2. Esquema general. 3. Análisis de tiempos de ejecución. 4. Ejemplos: 1. 1. Búsqueda del máximo y del mínimo. El problema de la selección. 2. Multiplicación rápida de matrices. 3. El problema del par más cercano. 4. Otros ejemplos.

Modalidades Organizativas y Metodología de Trabajo Modalidad Organizativa

Procedimientos y Actividades Formativas

Grupo Docente

Clases magistrales/participativas

4,0

Debate y puesta en común

0,5

Exposición de grupos de trabajo

0,5

Aprendizaje basado en problemas

3,0

Debate

0,5

Estudio de casos

0,5

Grupo de Trabajo/Grupo Reducido

Observaciones

Horas Pres./On line

Descripción del trabajo autónomo del alumno Análisis de conceptos y de la información. Análisis y compleción del material de sesiones magistrales. Completar las prácticas de clase. Delimitación de un tema de estudio. Estudio personal y preparación en grupo de prácticas. Elaboración y redacción de los correspondientes trabajos prácticos. Estudio de casos individualizados. Asistencia a tutorías. Consulta de bibliografía. Lecturas complementarias y revisión de vídeos. Recogida de información. Búsqueda de información en Internet. Trabajo en equipo: prácticas, resúmenes y preparación de exposiciones. Resumen grupal del tema.

Bloque

Algoritmos voraces (Greedy)

Contenido/Tema Algoritmos voraces (greedy) 1. Introducción. 2. Esquema general. 3. Análisis de tiempo de ejecución. 4. Ejemplos. 1. 1. Caminos mínimos. Algoritmo de Dijkstra. 2. Árboles de recubrimiento mínimo. Algoritmos de Prim y Kruskal. 3. El problema de la mochila 0/1. 4.

Este documento ha sido firmado con el certificado de Sello de Entidad de la UNIVERSIDAD DE ALMERÍA. Puede verificar la autenticidad, validez e integridad de este documento en la dirección: https://verificarfirma.ual.es/verificarfirma/?CSV:=GJ/uct1vFIreGQiTs2xmAQ== VERIFICADOR: https://verificarfirma.ual.es/verificarfirma/

CSV: GJ/uct1vFIreGQiTs2xmAQ==

4. El problema del viajante. 5. Planificación de tareas. 6. Otros ejemplos.

Modalidades Organizativas y Metodología de Trabajo Modalidad Organizativa

Procedimientos y Actividades Formativas

Grupo Docente

Clases magistrales/participativas

4,0

Debate y puesta en común

0,5

Exposición de grupos de trabajo

0,5

Aprendizaje basado en problemas

3,0

Debate

0,5

Estudio de casos

0,5

Grupo de Trabajo/Grupo Reducido

Observaciones

Horas Pres./On line

Descripción del trabajo autónomo del alumno Análisis de conceptos y de la información. Análisis y compleción del material de sesiones magistrales. Completar las prácticas de clase. Delimitación de un tema de estudio. Estudio personal y preparación en grupo de prácticas. Elaboración y redacción de los correspondientes trabajos prácticos. Estudio de casos individualizados. Asistencia a tutorías. Consulta de bibliografía. Lecturas complementarias y revisión de vídeos. Recogida de información. Búsqueda de información en Internet. Trabajo en equipo: prácticas, resúmenes y preparación de exposiciones. Resumen grupal del tema.

Bloque

Programación Dinámica

Contenido/Tema Programación dinámica 1. Introducción. 2. Esquema general. 3. Análisis de tiempos de ejecución. 4. Ejemplos. 1. 1. Caminos mínimos. Algoritmo de Floyd. 2. El problema de la mochila 0/1. 3. El problema del viajante. 4. Planificación de tareas. 5. Otros ejemplos.

Modalidades Organizativas y Metodología de Trabajo Modalidad Organizativa

Procedimientos y Actividades Formativas

Grupo Docente

Clases magistrales/participativas

4,0

Debate y puesta en común

0,5

Exposición de grupos de trabajo

0,5

Aprendizaje basado en problemas

3,0

Debate

0,5

Estudio de casos

0,5

Grupo de Trabajo/Grupo Reducido

Observaciones

Horas Pres./On line

Descripción del trabajo autónomo del alumno Análisis de conceptos y de la información. Análisis y compleción del material de sesiones magistrales. Completar las prácticas de clase. Delimitación de un tema de estudio. Estudio personal y preparación en grupo de prácticas. Elaboración y redacción de los correspondientes trabajos prácticos. Estudio de casos individualizados. Asistencia a tutorías. Consulta de bibliografía. Lecturas complementarias y revisión de vídeos. Recogida de información. Búsqueda de información en Internet. Trabajo en equipo: prácticas, resúmenes y preparación de exposiciones. Resumen grupal del tema.

Bloque

Backtracking

Contenido/Tema Backtraking 1. Introducción. 2. Esquema general. 3. Análisis de tiempos de ejecución. 4. Ejemplos. 1. 1. Búsqueda exhaustiva en grafos. 2. El problema de la mochila 0/1. 3.

Este documento ha sido firmado con el certificado de Sello de Entidad de la UNIVERSIDAD DE ALMERÍA. Puede verificar la autenticidad, validez e integridad de este documento en la dirección: https://verificarfirma.ual.es/verificarfirma/?CSV:=GJ/uct1vFIreGQiTs2xmAQ== VERIFICADOR: https://verificarfirma.ual.es/verificarfirma/

CSV: GJ/uct1vFIreGQiTs2xmAQ==

3. El problema del viajante. 4. Planificación de tareas. 5. Otros ejemplos.

Modalidades Organizativas y Metodología de Trabajo Modalidad Organizativa

Procedimientos y Actividades Formativas

Grupo Docente

Clases magistrales/participativas

4,0

Debate y puesta en común

0,5

Exposición de grupos de trabajo

0,5

Aprendizaje basado en problemas

3,0

Debate

0,5

Estudio de casos

0,5

Grupo de Trabajo/Grupo Reducido

Observaciones

Horas Pres./On line

Descripción del trabajo autónomo del alumno Análisis de conceptos y de la información. Análisis y compleción del material de sesiones magistrales. Completar las prácticas de clase. Delimitación de un tema de estudio. Estudio personal y preparación en grupo de prácticas. Elaboración y redacción de los correspondientes trabajos prácticos. Estudio de casos individualizados. Asistencia a tutorías. Consulta de bibliografía. Lecturas complementarias y revisión de vídeos. Recogida de información. Búsqueda de información en Internet. Trabajo en equipo: prácticas, resúmenes y preparación de exposiciones. Resumen grupal del tema.

Bloque

Branch and Bound

Contenido/Tema Branch and Bound 1. Introducción. 2. Esquema general. 3. Análisis de tiempos de ejecución. 4. Ejemplos. 1. 1. El problema de la mochila 0/1. 2. El problema del viajante. 3. Planificación de tareas. 4. Otros ejemplos. Conclusiones y aspectos destacables de la materia.

Modalidades Organizativas y Metodología de Trabajo Modalidad Organizativa

Procedimientos y Actividades Formativas

Grupo Docente

Clases magistrales/participativas

3,0

Debate y puesta en común

0,5

Exposición de grupos de trabajo

0,5

Aprendizaje basado en problemas

1,0

Debate

1,0

Estudio de casos

1,0

Grupo de Trabajo/Grupo Reducido

Observaciones

Horas Pres./On line

Descripción del trabajo autónomo del alumno Análisis de conceptos y de la información. Análisis y compleción del material de sesiones magistrales. Completar las prácticas de clase. Delimitación de un tema de estudio. Estudio personal y preparación en grupo de prácticas. Elaboración y redacción de los correspondientes trabajos prácticos. Estudio de casos individualizados. Asistencia a tutorías. Consulta de bibliografía. Lecturas complementarias y revisión de vídeos. Recogida de información. Búsqueda de información en Internet. Trabajo en equipo: prácticas, resúmenes y preparación de exposiciones. Resumen grupal del tema.

Este documento ha sido firmado con el certificado de Sello de Entidad de la UNIVERSIDAD DE ALMERÍA. Puede verificar la autenticidad, validez e integridad de este documento en la dirección: https://verificarfirma.ual.es/verificarfirma/?CSV:=GJ/uct1vFIreGQiTs2xmAQ== VERIFICADOR: https://verificarfirma.ual.es/verificarfirma/

CSV: GJ/uct1vFIreGQiTs2xmAQ==

PROCEDIMIENTO DE EVALUACIÓN DE LAS COMPETENCIAS Criterios de Evaluación Superar el examen escrito (ejercicios). (60% de la nota). Interviene en la evaluación de las competencias UAL3, CB1, CB2, CB4, CC05, CC06, CC07, CC08, mediante el instrumento de evaluación Pruebas finales (escritas u orales).

Realización de los ejercicios prácticos (prácticas). (25%, 20% portfolio y 5% pruebas). Intervienen en la evaluación de todas las competencias reflejadas en esta guía docente, mediante los instrumentos de evaluación: Pruebas, ejercicios, problemas. Valoración final de informes, trabajos, proyectos, etc. Portafolio del estudiante. Otros: - Preguntas y respuestas en clase. - Actitud participativa en clase, asistencia activa. - Resolución de casos prácticos en grupo - evaluación continua y entrega de memoria. Trabajo en grupo. - Prácticas de laboratorio. Presentaciones y discusión en clase. - Realización de trabajos optativos en grupo. - Resumen en grupo a través de un foro de los temas (a utilizar en los exámenes).

Necesidad de aprobar tanto los exámenes como las prácticas. Exámenes parciales eliminatorios (2). (Eliminan la parte correspondiente del examen final). Participación en clase (puntos de participación activa en clase) y trabajos opcionales (resumen grupal de los temas y participación en foros). (15% de la nota, Otros instrumentos de evaluación). Intervienen en la evaluación de todas las competencias reflejadas en esta guía docente. Porcentajes de Evaluación de las Actividades a realizar por los alumnos Actividad Gran Grupo

I. ACTIVIDADES DEL ESTUDIANTE (Presenciales / Online)

II. ACTIVIDADES NO PRESENCIALES DEL ESTUDIANTE (Trabajo autónomo)

(Nº horas)

Porcentaje

(0)

0%

Grupo Docente

( 26 )

20 %

Grupo de Trabajo/Grupo Reducido

( 19 )

30 %

( Trabajo en grupo, Trabajo individual )

(105)

50 %

Instrumentos de Evaluación Pruebas, ejercicios, problemas. Valoración final de informes, trabajos, proyectos, etc. Pruebas finales (escritas u orales). Portafolio del estudiante. Otros: - Preguntas y respuestas en clase. - Actitud participativa en clase, asistencia activa. - Resolución de casos prácticos en grupo - evaluación continua y entrega de memoria. Trabajo en grupo. - Prácticas de laboratorio. - Presentaciones y discusión en clase. - Realización de trabajos optativos en grupo. - Resumen en grupo a través de un foro de los temas (a utilizar en los exámenes). Mecanismos de seguimiento Asistencia a tutorías Alta y acceso al aula virtual Participación en herramientas de comunciación (foros de debate, correos) Entrega de actividades en clase Entrega de actividades en tutorías Entrega de actividades en aula virtual Otros: Propuesta de mejoras en el desarrollo de la asignatura. De acuerdo con los alumnos, se podrá modificar la planificación de los temas, de las fechas de los exámenes parciales y de la distribución del esfuerzo, para adaptarse a los requerimientos específicos del grupo y a la posible aparición de nuevo material o tecnología (por ejemplo un vídeo explicativo).

Este documento ha sido firmado con el certificado de Sello de Entidad de la UNIVERSIDAD DE ALMERÍA. Puede verificar la autenticidad, validez e integridad de este documento en la dirección: https://verificarfirma.ual.es/verificarfirma/?CSV:=GJ/uct1vFIreGQiTs2xmAQ== VERIFICADOR: https://verificarfirma.ual.es/verificarfirma/

CSV: GJ/uct1vFIreGQiTs2xmAQ==

BIBLIOGRAFÍA Bibliografía recomendada Básica Data structures, algorithms, and applications in Java (Sahni, Sartaj ) - Bibliografía básica Esquemas algorítmicos : Enfoques metodológico y problemas resueltos (Julio Gonzalo Arroyo, Miguel Rodríguez Artacho) - Bibliografía básica Estructuras de datos en Java (Mark Allen Weiss) - Bibliografía básica Fundamentos de algoritmia (Brassard, Gilles ) - Bibliografía básica

Complementaria Estructuras de datos y algoritmos (ALFRED V. AHO; JOHN E. HOPCROFT; JEFFREY D. ULLMAN) - Bibliografía complementaria Foundations of algorithms using C++ pseudocode (Richard E. Neapolitan, Kumarss Naimipour) - Bibliografía complementaria Introduction to algorithms (Thomas Cormen, Charles Leiserson, Ronald Rivest & Cliford Stein)) - Bibliografía complementaria Introduction to the design & analysis of algorithms (Levitin, Anany) - Bibliografía complementaria The algorithm design manual (Skiena, Steven S. ) - Bibliografía complementaria The Design and analysis of computer algorithms (Alfred V. Aho, John E. Hopcrogt, Jeggrey D. Ullman) - Bibliografía complementaria

Bibliografía existente en el Sistema de Información de la Biblioteca de la UAL Puede ver la bibliografía existente en la actualidad en el Sistema de Gestión de Biblioteca consultando en la siguiente dirección: http://almirez.ual.es/search/e?SEARCH=ESTRUCTURA DE DATOS Y ALGORITMOS II

DIRECCIONES WEB http://www.cise.ufl.edu/~sahni/dsaaj/ Material libro base por Sartaj Sahni http://www.lcc.uma.es/~av/Libro/indice.html Técnicas de diseño de algoritmos. Manual libre, muy ajustado a la asignatura. http://www.csc.liv.ac.uk/~ped/teachadmin/algor/intro.html Resúmenes del curso de técnicas de diseño de algoritmos del profesor Paul E. Dunne (Univ. Liverpool) https://itunes.apple.com/itunes-u/introduction-to-algorithms/id341597754?mt=10 Clases de asignatura equivalente grabadas en el MIT (Massachusetts Institute of Technology). Gratis. http://www.or.deis.unibo.it/knapsack.html Knapsack Problems. Libro disponible en Internet (libre) por Martello y Toth.

Este documento ha sido firmado con el certificado de Sello de Entidad de la UNIVERSIDAD DE ALMERÍA. Puede verificar la autenticidad, validez e integridad de este documento en la dirección: https://verificarfirma.ual.es/verificarfirma/?CSV:=GJ/uct1vFIreGQiTs2xmAQ== VERIFICADOR: https://verificarfirma.ual.es/verificarfirma/

CSV: GJ/uct1vFIreGQiTs2xmAQ==