Departamento de Informática y Automática

Inicio >> Docencia >> Titulación >> Asignaturas/Cursos >> Presentación

Estructura de Datos y Algoritmos II (101116)

Presentación

Grupos

Recursos

Bibliografía

Exámenes

Avisos

Sentido de la materia en el plan de estudios

Bloque formativo al que pertenece la materia

Materia Programación, que consta de las siguientes asignaturas:

Programación I

Programación II

Programación III

Estructuras de Datos y Algoritmos I

Estructuras de Datos y Algoritmos II

Informática Teórica

Programación Avanzada

Procesadores de Lenguaje (optativa)

Animación Digital (optativa)

Desarrollo de Aplicaciones Avanzadas (optativa)

Papel de la asignatura dentro del Bloque formativo y del Plan de Estudios

Esta asignatura es obligatoria de segundo semestre de segundo curso. Es continuación natural de la asignatura Estructuras de Datos y Algoritmos I, y la complementa profundizando en el uso de TAD más complejos, como árboles y grafos. Además concluye con un tema de técnicas de diseño de algoritmos avanzados en los que se utiliza de forma intensiva los TAD estudiados en los primeros temas.

Perfil profesional

Se trata de una asignatura de carácter básico, sirve como fundamento para el desarrollo de otras de la titulación, y constituye una parte fundamental para cualquier perfil profesional de un ingeniero en informática.

Recomendaciones previas

Se recomienda no cursar Estructuras de Datos y Algoritmos II sin aprobar previamente y Estructuras de Datos y Algoritmos I.

Objetivos de la asignatura

Generales

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.

Capacidad para definir, evaluar y seleccionar plataformas hardware y software para el desarrollo y la ejecución de sistemas, servicios y aplicaciones informáticas.

Capacidad para resolver problemas con iniciativa, toma de decisiones, autonomía y creatividad.

Específicos

Determinar la complejidad en tiempo y espacio de diferentes algoritmos y equilibrar los requisitos contrapuestos de eficiencia y costes en la implementación

Analizar, especificar e implementar estructuras de datos, tanto lineales como no lineales, desde la perspectiva de los TAD para la resolución de problemas utilizando la más apropiada, en función de los recursos necesarios.

Diseñar e implementar soluciones algorítmicas utilizando esquemas avanzados.

Contenidos

Tema 1. Árboles Generales y Binarios

1 Definiciones y conceptos básicos

2 Nivel de representación o implementación

Representación de árboles binarios

Representación de árboles generales

3 Recorridos en Árboles Binarios

En profundidad

En amplitud

Tema 2. Árboles Binarios de Búsqueda

1 Nivel abstracto o de definición

2 Nivel de representación

Búsqueda

Inserción

Eliminación

Análisis del caso medio

3 Árboles Balanceados

Inserción y equilibrio del árbol

Rotaciones

Eliminación y equilibrio del árbol

Tema 3.Montículos Binarios. Colas de Prioridad

1 Introducción

2 Nivel abstracto o de definición

Propiedad de Orden

Propiedad de Estructura

3 Nivel de representación

Inserción

Eliminación

Elemento Mínimo

Otras operaciones

4 Ordenación por Montículos

Tema 4. Conjuntos Disjuntos. Estructura de Partición

1 Relación de Equivalencia

2 Nivel abstracto o de definición

3 Nivel de Representación

Representación mediante matrices

Representación mediante listas enlazadas

Representación mediante árboles

4 Compresión de caminos

Tema 5.Grafos

1 Nivel abstracto o de definición

2 Nivel de Representación

3 Recorridos en grafos

4 Ordenación topológica

5 Algoritmos de Caminos de Coste Mínimo

Grafos no ponderados

Grafos Ponderados. Algoritmo Dijkstra

6 Árbol de expansión de coste mínimo

Algoritmo Prim

Algoritmo de Kruskal

Tema 6. Memoria Secundaria

1 Organización de archivos

2 Clasificación externa

3 Organización de índices

Competencias a adquirir

Básicas

CG3 - Capacidad para comprender y dominar los conceptos básicos de matemática discreta, lógica, algorítmica y complejidad computacional, y su aplicación para la resolución de problemas propios de la ingeniería.

CG5 - Conocimiento de la estructura, organización, funcionamiento e interconexión de los sistemas informáticos, los fundamentos de su programación, y su aplicación para la resolución de problemas propios de la ingeniería.

Comunes

CE6 - 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.

CE7 - Conocimiento, diseño y utilización de forma eficiente los tipos y estructuras de datos más adecuados a la resolución de un problema.

CE8 - 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.

Específicas

CECO3 - Capacidad para evaluar la complejidad computacional de un problema, conocer estrategias algorítmicas que puedan conducir a su resolución y recomendar, desarrollar e implementar aquella que garantice el mejor rendimiento de acuerdo con los requisitos establecidos.

CECO5 - Capacidad para adquirir, obtener, formalizar y representar el conocimiento humano en una forma computable para la resolución de problemas mediante un sistema informático en cualquier ámbito de aplicación, particularmente los relacionados con aspectos de computación, percepción y actuación en ambientes o entornos inteligentes.

Transversales

CT1 - Conocimientos generales básicos

CT3 - Capacidad de análisis y síntesis

CT9 - Resolución de problemas

CT12 - Trabajo en equipo

CT16 - Capacidad de aplicar los conocimientos en la practica

CT21 - Habilidad para trabajar de forma autónoma y cumplir plazos

Metodologías

Las actividades formativas que se proponen para esta materia son las siguientes:

Actividades presenciales:

Lección magistral: exposición de teoría y resolución de problemas

Realización de prácticas guiadas en laboratorio

Seminarios tutelados para grupos pequeños con exposición de trabajos

Sesiones de tutorías, seguimiento y evaluación, individuales o en grupo

Exposición de trabajos y pruebas de evaluación

Actividades no presenciales:

Estudio autónomo por parte del estudiante

Revisión bibliográfica y búsqueda de información

Realización de trabajos, prácticas libres, informes de prácticas…

Previsión de Técnicas (Estrategias) Docentes

Nombre	Horas presenciales	Horas no presenciales dirigidas por el profesor	Horas de trabajo autónomo del estudiante	Horas totales
Clases magistrales	28	0	32	60
Seminarios	0	0	0	0
Prácticas en aula	0	0	0	0
Prácticas en el laboratorio	0	0	0	0
Prácticas en aula de informática	28	0	28	56
Prácticas de campo	0	0	0	0
Prácticas de visualización	0	0	0	0
Trabajo personal de contenidos presenciales y recursos on line	0	0	0	0
Exposiciones y debates	0	0	0	0
Tutorías	2	0	0	2
Actividades de seguimiento on line	0	0	0	0
Preparación de trabajos	0	0	15	15
Otras actividades	0	0	0	0
Exámenes	2	0	15	17
Prácticas: Realización del TFM	0	0	0	0
Documentación TFM	0	0	0	0
TOTAL	60	0	90	150

Evaluación

Consideraciones Generales

La evaluación de la asignatura se realizará en base a dos tipos de actividades. Por un lado la realización de un conjunto de pruebas, pequeños controles y entregas de prácticas, que constituye la evaluación continua. Y por otro lado, la realización de un examen con cuestiones teóricas y prácticas que permita evaluar el conjunto de conocimientos y competencias adquiridas.

Criterios de evaluación

Para la evaluación de la asignatura se aplicará la siguiente ponderación en la valoración de las actividades de evaluación:

Actividades de evaluación continua: 30%

Realización de exámenes de teoría o problemas: 70%

La nota final de las asignaturas se obtendrá de forma ponderada a través de las notas finales conseguidas en los apartados anteriores.

En el examen final se exigirá alcanzar una calificación mínima del 40% sobre el peso total de esa prueba para poder superar la asignatura.

Instrumentos de evaluación

Controles cortos: cuando se haya impartido una cantidad razonable de materia se realizará una breve prueba escrita, en horario de clase, en la que se pedirá la resolución de algún ejercicio así como alguna pregunta de carácter teórico. Se pretende evaluar el esfuerzo diario del estudiante en la comprensión y asimilación de los contenidos básicos.

Entregas de prácticas: Consiste en la implementación de uno o varios ejercicios prácticos en aula de informática. Se pretende hacer un seguimiento del trabajo realizado por el estudiante en las sesiones prácticas y horas de trabajo autónomo asociadas a dichas sesiones. El estudiante podrá ser convocado para explicar los métodos utilizados y su resolución. En su caso, esta defensa del trabajo presentado formará parte de la calificación del trabajo.

Examen final: se compondrá de una serie de cuestiones teóricas y prácticas. Será necesario superar el 40% de la valoración del examen para poder aprobar la asignatura.

Recomendaciones

Recomendaciones para la evaluación

La asistencia a clase y el trabajo autónomo del estudiante son fundamentales para poder superar satisfactoriamente las actividades de evaluación continua, y poder enfrentarse con éxito al examen final.

Recomendaciones para la recuperación

Se realizará un examen de recuperación (2ª convocatoria), para aquellos casos en los que, tras el primer examen final (1ª convocatoria), no se ha logrado la superación de la asignatura.

Los criterios de evaluación en la 2ª convocatoria son los mismos que en la primera (30% evaluación continua+70% examen final), por lo que el examen de recuperación solo permite recuperar en el 70% correspondiente al examen final. Las actividades de evaluación continua no son recuperables.

En ningún caso se mantendrán notas parciales para cursos posteriores.

Datos de interés

Documentación

Todas las presentaciones, guiones de prácticas y demás documentos relacionados con la asignatura se encuentran en la plataforma Studium.

Recursos de interés

En http://raed.usal.es se puede descargar la aplicación RAED Representación de Algoritmos de estructuras de datos. Se trata de una herramienta didáctica desarrollada como proyecto fin de carrera que permite, a través de ejemplos y sus representaciones gráficas, el estudio y la comprensión de la mayoría de los algoritmos que se presentan en la asignatura.