Algoritmos y Estructuras de Datos

El objetivo de formación de esta materia es desarrollar las destrezas necesarias para que el alumnado sepa analizar la complejidad computacional de un determinado algoritmo, así como desarrollar las capacidades necesarias para escoger la combinación de estructuras de datos y estrategia de resolución más apropiada para resolver de modo eficiente (en términos de recursos espaciales y temporales) un determinado problema. Además, esta materia completa la formación del alumnado en estructuras de datos al presentar las estructuras de datos no lineales y su utilización para representar y resolver problemas de entidad.

Tema 1. Resolución de problemas: algoritmos+estructuras de datos

Tema 2. Estructuras de datos no lineales: Árboles
* Conceptos básicos y propiedades
* Árboles de búsqueda
* Árboles de búsqueda equilibrados
* Aplicaciones

Tema 3. Estructuras de datos no lineales: Grafos
* Conceptos básicos y propiedades
* Algoritmos fundamentales con grafos
* Aplicaciones

Tema 4. Tablas hash

Tema 5. Estrategias algorítmicas
* Divide y vencerás
* Algoritmos voraces
* Programación dinámica
* Vuelta atrás
* Ramificación y poda

Bibliografía Básica:
HEILEMAN, G.L. Estructuras de Datos, Algoritmos y Programación Orientada a Objetos. Madrid: McGraw-Hill, 2001. ISBN 84-481-1173-7.
JOYANES AGUILAR, L., ZAHONERO MARTÍNEZ, I. Algoritmos y Estructuras de Datos: Una perspectiva en C. Madrid: McGraw-Hill, 2010. ISBN 9788448140779.
JOYANES AGUILAR, L. et al. Estructura de Datos. Libro de Problemas. Madrid: McGraw-Hill, 1999. ISBN 84-481-2298-4.
Bibliografía Complementaria:
BOWMAN, C.F. Algoritmos y Estructuras de Datos. Aproximación en C. Oxford University Press, 2001. ISBN: 978-9706134592.
CAIRÓ, O., GUARDATI BUERMO, S. Estructuras de Datos. México: McGraw-Hill, 2006. ISBN 970-10-3534-8.
MARTÍ OLIET, Narciso, ORTEGA MALLÉN, Yolanda, VERDEJO LÓPEZ, José A.: Estructuras de Datos y Métodos Algorítmicos. Ejercicios resueltos. 2ª edición: 213 ejercicios resueltos. Ibergarceta Publicaciones S.L., 2013. ISBN 978-8415452652.

La materia contribuye a alcanzar las siguientes competencias, recogidas en la memoria del título de Grado en Ingeniería Informática de la USC para el Módulo de Programación:
- Desarrollar programas con un buen estilo de programación, con la documentación necesaria y los comentarios adecuados.
- Saber calcular la complejidad computacional de un algoritmo y evaluar la implementación más adecuada de un algoritmo determinado de acuerdo con los recursos disponibles (memoria y tiempo de ejecución).
- Utilizar herramientas de edición, compilación, y ejecución para desarrollar programas. Capacidad para aplicar estrategias de depuración, prueba y corrección de programas.
- Escoger la estructura de datos más correcta y eficiente para resolver un problema.
- Manejar diferentes niveles de abstracción para estructurar el software a desarrollar.
- Diseñar algoritmos de una cierta complejidad e implementarlos aplicando los principios de la programación estructurada y modular.
- Compresión de conceptos relacionados con el desarrollo de algoritmos.
- Manejo de gestores de errores, gestión de excepciones y tolerancia a fallos.
- Uso de repositorios de software.
- Motivación y capacidad de autoaprendizaje.
- Autoestima y espíritu de superación.

Además, se contribuye al desarrollo de las competencias generales y específicas recogidas en las correspondientes tablas en la mencionada memoria del título:
* Competencias generales:
CG1: Capacidad para desarrollar proyectos en el ámbito de la ingeniería en informática que tengan por objeto, de acuerdo con los conocimientos adquiridos, la concepción, el desarrollo o la explotación de sistemas, servicios y aplicaciones informáticas.
CG3: Capacidad para diseñar, desarrollar, evaluar y asegurar la usabilidad de los sistemas, servicios y aplicaciones informáticas, así como de la información que gestionan.
CG8: 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.
CG9: 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 Ingeniería Técnica en Informática.
* Competencias transversales:
TR1 (Instrumentales): Capacidad de análisis y síntesis. Capacidad de organización y planificación. Comunicación oral y escrita. Capacidad de gestión de la información. Resolución de problemas. Toma de decisiones.
TR2 (Personales): Trabajo en equipo. Habilidades en las relaciones interpersonales. Razonamiento crítico.
TR3 (Sistémicas): Aprendizaje autónomo. Adaptación a nuevas situaciones. Creatividad. Iniciativa. Motivación por la calidad.
* Formación Básica
FB3: Capacidad para comprender y dominar los conceptos básicos de algorítmica y complejidad computacional, y su aplicación para la resolución de problemas propios de la ingeniería.
FB4: Conocimientos básicos del uso y programación de los ordenadores.
FB5: Conocimiento de los fundamentos de la programación de los sistemas informáticos, y su aplicación para la resolución de problemas propios de la ingeniería.
* Comunes a la rama de la Informática
RI6: 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.
RI7: 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.

La metodología seguida usa como plataforma básica el Campus Virtual de la USC. En la aula virtual de la materia el alumnado dispondrá de toda la información (material de teoría, presentaciones de clase, guiones de prácticas, bibliotecas de TADs, etc.).
Se impartirán 20 horas de clases magistrales en sesiones de 1 hora, y habrá una sesión semanal de dos horas y media de trabajo práctico (resolución de problemas, programación).
El alumnado podrá en todo momento seguir su progresión, al tener disponibles continuamente las notas de los ejercicios y proyectos que hayan de entregar para seguir el modelo de evaluación continua.
Las competencias de tipo FB3, FB4, FB5, RI6, RI7, CG1, CG3, CG8 y CG9, así como las indicadas del módulo de programación tienen _ contenidos asociados en la parte teórico-práctica de la asignatura y se evalúan de forma explícita en las pruebas que se realizan durante todo el curso .
Las competencias de tipo TR1 se trabajan fundamentalmente en el aspecto de la capacidad de organización y planificación, toma de decisiones y resolución de problemas, en las entregas que tienen que realizar en las clases en las clases prácticas.
De las competencias del tipo TR2 se trabajan principalmente el pensamiento crítico, evaluando las diferentes posibilidades de resolver los problemas, tanto en teoría como en la práctica.
Del grupo de competencias TR3 se trabajan principalmente la creatividad, la adaptación a nuevas situaciones, y la motivación por la calidad, especialmente en las clases prácticas, donde se proponen problemas para desarrollar estas habilidades, con situaciones cambiantes, y se evalúan en la calificación del problema a entregar.

La evaluación consta de dos partes individuales separadas, teoría y práctica, siendo necesario superar ambas partes independientemente. Además, es necesario aprobar todos los módulos de prácticas y todos los tests y pruebas de teoría de forma independiente.

La parte práctica de la materia se evaluará mediante un proceso de EVALUACIÓN CONTINUA:
-30% de la nota global: entrega de proyectos prácticos durante el cuatrimestre, con plazos y normas de entrega/corrección prefijadas por el profesorado.
Se utiliza para evaluar las competencias CG1, CG3, CG8, CG9, TR1, TR3, FB4, FB5, RI6 y RI7, además de las indicadas del módulo de programación, mediante la entrega periódica de las prácticas propuestas durante el semestre.

La parte teórica (70% de la nota global) se evaluará en dos partes:
-10% de la nota: Realización de tests a lo largo del cuatrimestre.
-60% de la nota: Examen global al final del cuatrimestre
Se utiliza para evaluar las competencias CG8, CG9, TR2, FB3, FB4, FB5, RI6 y RI7, además de las especificadas del módulo de programación, utilizando diferentes preguntas en el examen de teoría y la evaluación de los ejercicios que se entregan durante el cuatrimestre.

La entrega de algún trabajo (proyecto o ejercicio) con posterioridad al 1 de noviembre llevará asociada la consideración de PRESENTADA/O en la calificación de la materia, independientemente de la asistencia o no al examen final.

RECUPERACIÓN o 2ª OPORTUNIDAD (JULIO):
Podrán realizar este examen el alumnado que no superara alguna de las partes en la evaluación continua, o las personas que opten directamente por esta opción.
- Teoría (70% de la nota final): repetición de tests no superados y examen final escrito.
- Práctica (30% de la nota final): realización de prácticas no superadas mediante propuesta de ejercicios de programación a entregar antes del examen final.

En aplicación de la normativa de autoría de trabajos prácticos aprobada por la Xunta de la ETSE (01/03/2012), la copia total o parcial de algún ejercicio de prácticas o teoría supondrá el suspenso en las dos oportunidades del curso, con la calificación de 0,0 en ambos casos.

Para el alumnado repetidor: Se conservan únicamente los resultados de la evaluación teórica o práctica que se haya superado (nota superior a 6) en el curso inmediatamente anterior. En otro caso, habrá de repetirse la materia completa.

Una vez que la materia pierde el derecho a docencia la evaluación se realizará mediante un examen escrito (50% de la nota final) y la entrega de varios proyectos de programación (50% de la nota final), de la misma forma que en la oportunidad de recuperación.

En caso de realización fraudulenta de ejercicios o pruebas, será de aplicación lo recogido en la Normativa de evaluación del rendimiento académico de los estudantes y de revisión de calificaciones.

En aplicación de la Normativa de la ETSE sobre plagio (aprobada por la Junta de ETSE el 19/12/2019), la copia total o parcial de algún ejercicio de prácticas o teoría supondrá el suspenso en las dos oportunidades del curso, con la calificación de 0,0 en ambos casos.

Esta materia tiene 6 créditos ECTS, correspondiendo una carga de trabajo personal para los alumnos de 90 horas. Este tiempo puede desglosarse en los siguientes apartados:
TRABAJO PRESENCIAL EN EL AULA:
* Clases magistrales: 20 horas
* Aprendizaje basado en problemas y/o casos en grupos reducidos: 15 horas
* Sesiones prácticas en grupos reducidos: 15 horas
* Actividades de evaluación: 5 horas
Total horas trabajo presencial en el aula: 55 horas
TRABAJO PERSONAL DEL ALUMNADO:
* Estudio autónomo: 35 horas
* Escritura de ejercicios, trabajos, etc.: 15 horas
* Programación/experimentación en ordenador: 30 horas
* Evaluación de trabajos, proyectos, exámenes: 15 horas
Total horas trabajo personal: 95 horas

Se suponen unos conocimientos suficientes de lenguaje de programación C y de los fundamentos de grafos, que se ven, respectivamente, en las materias de Programación I y II, y en Matemática Discreta de primer curso.
Se recomienda seguir el modelo de evaluación continua, lo que significa llevar la materia al día. De esta forma se seguirán con mayor facilidad las clases teóricas y las clases prácticas, lo que hace la materia más llevadera.
También se recomienda encarecidamente el uso de las horas de tutorías para aclarar cualquier duda que se pueda presentar en el desarrollo de la materia.

Se utilizará el campus virtual de la USC para toda la docencia, publicación de material, guiones de prácticas y entrega de trabajos.
El sistema operativo a utilizar en las prácticas es indiferente: Windows o Linux
Se utilizará básicamente el IDE Netbeans o CLion con el compilador de C de cygwin instalado para Windows o el gcc para Linux.
La materia se impartirá principalmente en castellano.