Doble Titulación en Ingeniería Telemática e Ingeniería Informática

Doble Grado en Ingeniería Telemática e Ingeniería Informática

Fórmate para ser un ingeniero experto en Redes y Tecnologías de Internet y adquiere a la vez las certificaciones oficiales de CCNA y CCNP

Programación avanzada y estructura de datos

Descripción
La asignatura tiene como objetivo ofrecer una visión avanzada de la programación de algoritmos, así como de las estructuras de datos más usadas. El estudio de la eficiencia de los algoritmos y diversas técnicas y estructuras se trabajan en profundidad con el objetivo de resolver problemas de forma eficiente y elegante. Es importante dominar el análisis descendiente, la modularidad, la gestión de la memoria, las estructuras de datos lineales, el pseudocódigo, el lenguaje C, etcétera, trabajados en la asignatura de “Metodología y tecnología de la programación”. Adquiriendo los conocimientos de la asignatura, el alumno desarrolla habilidades para proponer y discutir la adecuación de soluciones a problemas complejos.
Tipo asignatura
Tercer - Obligatoria
Semestre
Anual
Curso
2
Créditos
8.00

Profesores Titulares

Profesor/a
Conocimientos previos

Dominio de las técnicas de programación trabajadas en Metodología y Tecnología de la Programación (análisis descendente, modularidad, paso de parámetros y estructuras de datos básicos).
Conocer bien el lenguaje que se utilizará para realizar los ejercicios (Pseudocódigo / C / Java).
Capacidad para seguir y proponer razonamientos matemáticos.

Objetivos

Resultados de aprendizaje
- Uso de un entorno real de programación
- Trabajo en equipo en el análisis, diseño e implementación de software
- Definición de la estructura modular y de datos para llevar a término las aplicaciones informáticas

Al finalizar el curso, el alumno debe ser capaz de:
- Evaluar la eficiencia de un algoritmo a través del cálculo del coste.
- Diseñar un algoritmo recursivo.
- Transformar un algoritmo recursivo en iterativo.
- Justificar la necesidad de la especificación formal de los algoritmos.
- Explicar los principales mecanismos de derivación formal y demostración formal de algoritmos recursivos simples y de llevarlo a la práctica en problemas.
- Hacer la especificación de una función en términos de pre y post-condiciones.
- Implementar un algoritmo sin ambigüedades a partir de la especificación del mismo.
- Escoger los métodos de resolución de problemas combinatorios más adecuados en cada situación.
- Implementar los métodos de Backtracking, Branch & Bound y Greedy adaptados a cada problema en concreto y buscando la máxima eficiencia y eficacia.
- Especificar formalmente cualquier Tipo Abstracto de Datos usando especificación algebraica.
- Implementar un Tipo Abstracto de Datos a partir de su especificación algebraica.
- Diseñar e implementar la estructura de datos más adecuada para una determinada aplicación, dados unos requisitos de eficiencia temporal y espacial.
- Implementar los árboles binarios, n-arios, AVL, 2-3, B y heaps. Implementar también los diversos recorridos posibles.
- Implementar las tablas vistas en la asignatura.
- Implementar las variantes de los diferentes grafos. Implementar la búsqueda del camino mínimo.

Contenidos

La asignatura divide los contenidos en dos partes claramente diferenciadas:

• Durante el primer semestre se trabaja la especificación, el análisis, el diseño y la verificación formal de algoritmos. El diseño comprende un enfoque para la resolución de problemas mediante técnicas recursivas simples y múltiples. Se incluye también en esta parte el estudio y la aplicación de técnicas orientadas a la resolución de problemas que presentan un espacio combinatorio de soluciones.

• El segundo semestre se centra en el estudio de estructuras de datos avanzadas lineales y no lineales y sus aplicaciones prácticas.

Las técnicas que se estudian incluyen conocimientos teóricos y prácticos, habilidades, experiencias y sentido crítico, todas ellas fundamentadas en teorías y técnicas sólidas, comprobadas y bien establecidas.

Metodología

Durante la asignatura, se usarán las siguientes metodologías, por semestre:

• Primer Semestre:
o Clases magistrales, para aquellos contenidos que lo requieran.
o Problemas y ejercicios a clase, para consolidar conocimientos.
o Ejercicios de EC en clase y prácticas evaluables.
o Self-paced learning, para contenidos que no se evaluarán directamente.
o Flipped-classroom, para motivar el autoaprendizaje y dar soporte al alumno.

• Segundo Semestre:
o Project-Based Learning, donde los alumnos aprenderán a diseñar e implementar estructuras de datos.
o Clases magistrales intercaladas para introducir conceptos necesarios, complementados durante el PBL.
o Self-paced learning, para contenidos que no se puedan aplicar al proyecto.

Evaluación

La asignatura es anual, por lo que la nota final se calcula a partir de las notas de los dos semestres, siempre que ambas sean superiores o iguales a 5. Si no se aprueban los dos semestres, la asignatura queda suspendida con un 4.

Nota_Final = 0.5 · Nota_S1 + 0.5 · Nota_S2

Primer semestre:

La nota del primer semestre se calcula a partir de la ponderación de las notas de conocimientos y prácticas:

Nota_S1 = 0.5 · Nota_Conocimientos_S1 + 0.5 · Nota_Prácticas_S1

Es necesario haber aprobado ambas partes (con un 5 o más) para aprobar el semestre. En caso contrario, la nota semestral será de 4.

Conocimientos

Para calcular esta nota se pondera la nota del examen final del primer semestre con la nota de evaluación continua, únicamente en caso de beneficiar al alumno y siempre que la nota del examen sea superior o igual a 3,5.

Nota_Conocimientos_B1 = max( 0.6 · Nota_EC_S1 + 0.4 · Nota_Examen_S1,Nota_Examen_S1 )

En este primer semestre, el punto de control contará como ejercicio de evaluación continua, teniendo un peso del 30% de la nota correspondiente. El resto vendrá de ejercicios realizados en clase.

En caso de suspender la parte de conocimientos del primer semestre, se realizará un examen de recuperación durante el mes de Julio, donde la nota de evaluación continua no beneficiará al alumno, quien tendrá que sacar un 5 o más para aprobar.

Prácticas

La nota de prácticas del primer semestre se calcula ponderando las notas de las dos prácticas que se realizan en parejas, teniendo que aprobar ambas por separado, con una nota igual o superior a 5. En caso contrario, la nota de prácticas será de 4.

Nota_Prácticas_S1 = 0.4 · Nota_Práctica_1 + 0.6 · Nota_Práctica_2

Convalidar el examen semestral

En caso de que un alumno cumpla los requerimientos especificados a continuación, puede convalidar el examen final del primer semestre, obteniendo como nota de conocimientos su nota de evaluación continua. Concretamente, el alumno debe:

Realizar todas las ECs, incluyendo el punto de control, obteniendo una media ponderada superior o igual a 7.
Presentar las dos prácticas del primer semestre.
Asistir de forma continuada a clase y mostrar interés.

El alumno es libre de renunciar a la convalidación, optando a realizar el examen del primer semestre, ya sea en convocatoria ordinaria o extraordinaria.

Los mecanismos concretos de convalidación, así como la forma de pedirla, se comunicarán con tiempo cuando se acerque el final del primer semestre.

Segundo semestre:

El segundo semestre se basa casi totalmente en la metodología Project-Based Learning (PBL), por lo que la nota final será la del proyecto, que tiene que ser superior o igual al 5 para aprobar:

Nota_S2 = Nota_Proyecto_S2

El punto de control del segundo semestre consistirá en un ejercicio opcional que solo podrá bonificar la nota del alumno.

Según el criterio del profesorado, se podrán realizar entrevistas del proyecto a aquellos grupos o alumnos que se considere necesario, para asegurar que se han adquirido los conocimientos vistos durante el semestre. En caso de suspender el proyecto, se podrá recuperar en convocatoria extraordinaria, como se indica en el siguiente apartado.

Criterios evaluación
Bibliografía básica

Brass, P. (2008). Advanced Data Structures. Cambridge University Press.
Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2014). Introduction to algorithms (3rd Edition). MIT Press.
Sedgewick, R., Wayne, K. (2011). Algorithms (4th Edition). Addison-Wesley Professional.
Skiena, S. S. (2012). The algorithm design manual (2nd Edition). Springer.

Material complementario