Créditos ECTS Créditos ECTS: 6
Horas ECTS Criterios/Memorias Trabajo del Alumno/a ECTS: 99 Horas de Tutorías: 3 Clase Expositiva: 24 Clase Interactiva: 24 Total: 150
Lenguas de uso Castellano, Gallego
Tipo: Materia Ordinaria Grado RD 1393/2007 - 822/2021
Centro Escuela Politécnica Superior de Ingeniería
Convocatoria: Segundo semestre
Docencia: Sin docencia (Extinguida)
Matrícula: No matriculable
Presentación
En la materia se describen las estructuras de datos lineales y las técnicas algorítmicas básicas para el diseño de algoritmos y la implementación de programas en casos prácticos simples, desarrollando las destrezas necesarias para que el estudiante 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 estudiante en estructuras de datos al presentar las estructuras de datos no lineales y su utilización para representar y resolver problemas de entidad.
Asimismo, se forma al alumno en los conceptos de la Programación Orientada a Objetos, haciendo especial énfasis en sus aspectos más prácticos. Esto supone que a la finalización del curso el alumno estará plenamente capacitado para desarrollar un programa siguiendo el paradigma orientado a objetos como alternativa a la programación procedimental.
Dando continuidad a la materia Fundamentos de Programación, se desarrollan los criterios básicos que deben guiar el diseño de un programa modular, así como la elaboración y ejecución de un plan de pruebas apropiado para verificar el correcto funcionamiento de un programa. Todos estos aspectos se desarrollarán de forma práctica en proyectos de programación integradores de todos los contenidos aprendidos y todas las competencias adquiridas con la realización de las actividades de la materia.
Objetivos de la asignatura
* Estudiar detalladamente los requerimientos de un problema e identificar los objetivos y sus dependencias. Desarrollar la capacidad de abstracción y de generalización para buscar soluciones alternativas en el diseño de un programa.
* Saber programar bajo el paradigma orientado a objetos en el desarrollo de aplicaciones, identificando posibles estrategias de solución a problemas con conceptos como la herencia, el polimorfismo o el encapsulamiento.
* Conocer estructuras de datos para la organización de la información que permita la obtención de algoritmos eficientes.
* Adquirir la capacidad para analizar con rigor la eficiencia de los algoritmos distinguiendo los conceptos de eficiencia en tiempo y en espacio, con el fin de reducir el coste computacional.
* Conocer las familias más importantes de problemas algorítmicos y estudiar diferentes esquemas o paradigmas de diseño aplicables para resolverlos.
* Proporcionar una amplia información, tanto teórica como práctica, de diferentes técnicas para diseñar algoritmos.
* Presentar y analizar las técnicas algorítmicas básicas que permitan abordar el desarrollo de programas correctos y eficientes para resolver problemas no triviales.
* Determinar el método de búsqueda y el método de ordenación más adecuado según las características de cada problema.
Contenidos
La memoria del título contempla para esta materia los siguientes contenidos:
Tipos abstractos de datos: definición y formalización. Estructuras de datos lineales y complejas. Diseño recursivo. Notaciones algorítmicas. Estrategias y técnicas algorítmicas (voraces, divide y vencerás, programación dinámica, vuelta atrás) Algoritmos básicos de búsqueda, ordenación y mezcla. Implementación de estas estructuras desde el punto de vista orientado a objetos.
Estos contenidos serán desarrollados de acuerdo con el siguiente temario:
Introducción (2 horas presenciales)
* Abstracción
* Tipos Abstractos de Datos
Programación Orientada a objetos y Análisis (8 horas presenciales, 12 no presenciales)
* Clases y Objetos: Tipos de datos «a medida».
* Variables y funciones estáticas
* Composición, Herencia y Polimorfismo
* Algunas clases de uso común. Ejemplos
* Clases en C++
* Análisis de la complejidad de los Algoritmos
Estructuras de Datos Lineales (6 horas presenciales, 12 no presenciales)
* Pilas
* Colas
* Listas
Diseño Recursivo. Estrategias y técnicas algorítmicas (8 horas presenciales, 12 no presenciales)
* Recursividad
* Complejidad en algoritmos recursivos
* Visualización de la Recursividad
* Estrategias y técnicas algorítmicas (divide y vencerás, voraces, fuerza bruta, vuelta atrás, programación dinámica)
Ordenación y Búsqueda (8 horas presenciales, 12 no presenciales)
* Algoritmos de Búsqueda: Secuencial, Binaria, por salto, Fibonacci, exponencial, interpolación, Hashing, …
* Algoritmos de Ordenación: Burbuja, selección, inserción, Shell, mezcla, rápida (QuickSort), …
Estructuras de Datos Complejas
Árboles (8 horas presenciales, 12 no presenciales)
* Introducción
* Representaciones de árboles
* Recorridos de árboles
* Árboles binarios de búsqueda. Análisis
* Árboles binarios de búsqueda equilibrados
Grafos (8 horas presenciales, 12 no presenciales)
* El TAD Grafo
* Matrices y listas de adyacencia
* Grafo Escalera de Palabras
* Búsqueda en Anchura
* El problema del caballo
* Búsqueda en profundidad
* Ordenamiento Topológico
* El problema de la ruta más corta
Bibliografía básica y complementaria
Bibliografía Básica:
* Brad Miller and David Ranum, Luther College: Problem Solving with Algorithms and Data Structures using Python
* Brad Miller and David Ranum, Luther College, and Jan Pearce, Berea College: Problem Solving with Algorithms and Data Structures using C++
* 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.
* Brassard, G., Bratley, P. Fundamentos de algoritmia. 1ª edición, Lugar de publicación: Madrid, Prentice Hall, 2002. ISBN: 84-89660-00-X
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.
* Kent D. Lee • Steve Hubbard : Data Structures and Algorithms with Python
* 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.
COMPETENCIAS
BÁSICAS
CB1: Que los estudiantes hayan demostrado poseer y comprender conocimientos en un área de estudio que parte de la base de la educación secundaria general, y se suele encontrar a un nivel que, si bien se apoya en los libros de texto avanzados, incluye también algunos aspectos que implican conocimientos procedentes de la vanguardia de su campo de estudio.
CB2: Que los estudiantes sepan aplicar sus conocimientos a su trabajo o vocación de una forma profesional y posean las competencias que suelen demostrarse por medio de la elaboración y defensa de argumentos y la resolución de problemas dentro de su área de estudio.
CB5: Que los estudiantes hayan desarrollado aquellas habilidades de aprendizaje necesarias para emprender estudios posteriores con un alto grado de autonomía.
GENERALES
CG2: Capacidad de resolución de problemas en el campo de la ingeniería robótica con creatividad, iniciativa, metodología y razonamiento crítico.
CG3: Capacidad de utilizar herramientas informáticas para el modelado, la simulación y el diseño de aplicaciones de ingeniería.
CG5: Ser capaz de obtener y analizar información sobre circuitos, elementos de máquinas, control automático, sensores y sistemas informáticos, con el fin último de lograr aplicaciones robóticas autónomas y flexibles.
ESPECÍFICAS
CE5: Capacidad de analizar, diseñar, representar y programar algoritmos, y manejo de las estructuras de datos adecuadas para la resolución de problemas en el ámbito de la robótica.
TRANSVERSALES
CT1: Capacidad de análisis y síntesis.
CT3: Capacidad de trabajo individual, con actitud autocrítica.
CT4: Capacidad para trabajar en grupo y abarcar situaciones problemáticas de forma colectiva.
CT9: Habilidad en el manejo de tecnologías de la información y de la comunicación (TIC).
CT10: Utilización de información bibliográfica y de Internet.
CT12: Capacidad para resolver problemas mediante la aplicación integrada de sus conocimientos.
Metodología de la enseñanza
La metodología de enseñanza que se persigue dentro de la materia donde se encuadra la presente asignatura es la siguiente:
* Los contenidos de la materia se impartirán de manera indistinta en las clases expositivas y en las clases interactivas. Las unidades teóricas y prácticas se impartirán de manera alternativa a lo largo del semestre con el objeto de afianzar los conceptos impartidos en ellas.
* La realización de todas las actividades propuestas es necesaria, al igual que la asistencia a todas las clases (expositivas e interactivas) para superar la materia.
* Los recursos necesarios para la presente materia son los siguientes:
a) Disponer de un ordenador personal
b) Copias de los apuntes de la materia.
c) Acceso de los alumnos a la bibliografía en la Biblioteca o por Internet.
d) Acceso a la herramienta Ms Visual Studio
e) OpenOffice o LibreOffice para la preparación de la documentación de las prácticas.
f) Acceso el campus virtual de la USC
g) Acceso a Ms Teams
Clases Expositivas e interactivas: Las clases consistirán en la explicación de los apartados del programa con la ayuda de una presentación electrónica. También se realizarán ejercicios en la pizarra, haciendo que el alumnado participe y desarrolle programas interactuando con el profesor para la resolución de estos. Todos los contenidos digitales (los códigos de los programas en Python y en C++, las diapositivas de la presentación en formato PDF, así como las explicaciones de estas en formato video por streaming), serán puestos a disposición del alumnado tanto en el Campus virtual como en el entorno colaborativo Ms Teams.
Las clases presenciales fundamentalmente tendrán lugar en un aula de informática, en la que se proporcionará un ordenador para cada alumno. Cuando la docencia se imparta por medios virtuales, se utilizará la herramienta Ms Teams para llevar a cabo la misma. La metodología de aprendizaje de prácticas consiste fundamentalmente en la resolución por parte del alumno de las actividades propuestas y otros ejercicios de programación, individualmente o por grupos, con la ayuda del profesor.
Actividades: A lo largo del semestre, el alumno deberá resolver problemas de programación adecuados a los contenidos desarrollados hasta el momento. Dichas actividades se corresponden con enunciados de los problemas resueltos en los exámenes de convocatorias anteriores y con problemas propuestos en recursos detallados en la bibliografía.
La resolución y entrega de estas actividades se consideran esenciales para alcanzar un resultado satisfactorio en la presente materia. Estas actividades serán defendidas por los alumnos en sesiones de tutoría a través de la plataforma Ms Teams
Tutorías: Las sesiones de tutorías servirán para resolver las dudas del alumnado en cuanto a los contenidos de la materia, resolución de problemas de teoría y ejercicios de prácticas propuestos en el anexo de actividades. Estas tutorías serán tanto presenciales como virtuales a través de correo electrónico, campus virtual o plataforma Ms Teams, y son fundamentales para alcanzar un aprendizaje efectivo de la materia.
Curso Virtual: Esta materia dispondrá de un curso virtual desenvuelto sobre la plataforma de Campus virtual de la USC, usando además la herramienta colaborativa Ms Teams. En estas se le facilitará al alumnado todo el material necesario en formato digital, además de distintas herramientas de comunicación para el apoyo, tanto de la docencia virtual como de las tutorías, incluyendo videoconferencia, chat, correo electrónico, foros…
Sistema de evaluación
La memoria de título plantea que, para los sistemas de evaluación de la asignatura, se seguirá la normativa general de evaluación de la USC y las especificaciones descritas en el apartado 5.1. de la misma. En concreto, y para esta asignatura, se fijan las ponderaciones mínima y máxima de cada apartado, tal y como se refleja en la siguiente tabla
SISTEMAS DE EVALUACIÓN
Examen: entre 0% y 70%
Trabajos/Actividades: entre 0% y 40%
Tutoría: entre 0% y 10%
La asistencia a las clases interactivas y expositivas es obligatoria y se tendrá en cuenta para la evaluación de la materia. Será obligatorio la asistencia al menos al 95% de las sesiones (salvo causas muy justificadas, según normativa de la USC). Las clases prácticas se realizarán a lo largo del curso durante las sesiones de clases interactivas.
Se recomienda encarecidamente utilizar las tutorías, tanto presenciales como virtuales, para la resolución de las dudas al respecto de estos problemas o de cualquier contenido de la materia.
Para superar la materia, el alumno tendrá que realizar todas las actividades que se propongan y superar los exámenes correspondientes.
Para los casos de realización fraudulenta de ejercicios o pruebas será de aplicación lo recogido en la “Normativa de avaliación do rendemento académico dos estudantes e de revisión de cualificacións” de la USC.
Primera oportunidad:
Para superar la materia, el alumno deberá haber asistido a las clases, haber entregado y superado las actividades propuestas, que se realizarán mediante talleres en la plataforma virtual de la asignatura (40% de la calificación final) y aprobar por separado tanto la teoría, que se realizará mediante un examen tipo test con la ayuda de la plataforma virtual, como la parte práctica, que se realizará mediante tareas en la plataforma virtual de la asignatura consistente en la resolución de problemas de programación ( 60% de la calificación final). Se tendrá en cuenta la asistencia a las tutorías para la resolución de dudas
Las preguntas del examen teórico podrán referirse tanto a los contenidos reflejados en los apuntes de la asignatura como a los contenidos prácticos trabajados por el alumno en las actividades entregadas. Estas pruebas podrán constar de preguntas tipo test, preguntas cortas y problemas de casos prácticos.
En todas las pruebas se evaluará el grado de asimilación de las competencias establecidas en el programa docente de la materia. No se realizará ningún examen parcial. Para superar la materia se tendrá que demostrar un conocimiento superior al 50% en todos los tipos de evaluación.
Segunda oportunidad:
Al margen de la evaluación continua, todos los alumnos tienen derecho a asistir al examen de la segunda oportunidad. Se mantiene la nota, y también su peso en la nota final, conseguida en cada una de las partes (asistencia a clase, entrega de actividades y las notas de la parte teórica, como de la parte práctica) durante el curso. Sin embargo, los alumnos podrán entregar en fecha previa el examen de la segunda oportunidad, aquellas actividades que no hubiesen alcanzado la nota de corte en la convocatoria anterior. Para superar la materia se tendrá demostrar un conocimiento superior al 50% en todos los tipos de evaluación
Sistema de evaluación
Competencias
Ponderación mínima
Ponderación máxima
Actividades Propuestas
CG2, CG3, CG5, CE5
entre 20% y 40%
Prueba o pruebas evaluación
CG2, CG3, CG5, CE5
entre 50% y 70%
Tutorías
CG2, CG3, CG5, CE5
entre 0% y 10%
Los alumnos repetidores de años anteriores estarán exentos del cumplimiento del deber de asistencia a las clases presenciales. Para aprobar la materia es obligatorio la realización y entrega de las actividades propuestas en las mismas fechas establecidas para el resto de los alumnos, así como superar la prueba de tipo Test y el examen de tipo práctico.
Los alumnos que no asistan a ninguna de las actividades de enseñanza programadas por conciliación laboral o familiar deberán cumplir con las disposiciones de la Instrucción 1/2017 de la Secretaría General. En estos casos, para aprobar esta materia, es obligatorio la realización y entrega de las actividades propuestas, así como superar la prueba de tipo Test y el examen de tipo práctico.
Tempo de estudio y trabajo personal
La materia tiene fijada una carga de trabajo de 6 ECTS. Este dato conduce a una carga de trabajo para la materia situada entre las 150 (6x25) horas y las 180 (6x30) horas.
En la guía de la materia se puede ver un estudio más detallado sobre el tiempo de estudio y trabajo personal necesario para superar la materia. La recomendación general sería emplear entre 5,5 y 6,5 horas (incluidas las 4 de clase) por semana
Trabajo presencial en el aula
* Clases teóricas (expositivas de grupo grande): 24 horas.
* Prácticas (con grupos reducidos): 24 horas.
* Tutorías de grupo (con grupos reducidos): 3 horas.
* Tutorías individualizadas: 4 horas.
* Actividades de evaluación: 5 horas.
TOTAL 60 horas
Trabajo personal del alumnado
* Lectura y preparación de temas: 24 horas.
* Realización de ejercicios y Elaboración de trabajos: 48 horas.
* Tutoría en grupo: 7 horas.
* Tutoría individualizada: 3 horas.
* Preparación de pruebas de evaluación: 8 horas.
TOTAL 90 horas
Dado que se emplea una metodología sustentada en la evaluación continua, es necesario un trabajo continuado con los contenidos de la materia. Esto es especialmente importante con las prácticas, ya que unos contenidos se van asentando sobre los anteriores, lo que hace muy conveniente tener asimilados los temas anteriores antes de intentar comprender los nuevos. Es la única forma de poder ir superando las distintas actividades de evaluación que se proponen.
Para el estudio de la materia, se recomienda realizar la totalidad de los ejercicios de los boletines de problemas y de las actividades, tanto los que se resuelvan en las propias sesiones interactivas, como los que queden propuestos.
La asignatura se impartirá en Castellano
Por razones evidentes de convivencia, así como una adecuada calidad de las actividades didácticas que se llevan a cabo en el marco del grado, está terminantemente prohibido el uso del teléfono móvil en el aula, responsabilizando al alumnado de las consecuencias legales y académicas que puedan derivarse de la utilización de este.