Créditos ECTS Créditos ECTS: 6
Horas ECTS Criterios/Memorias Traballo do Alumno/a ECTS: 99 Horas de Titorías: 3 Clase Expositiva: 24 Clase Interactiva: 24 Total: 150
Linguas de uso Castelán, Galego
Tipo: Materia Ordinaria Grao RD 1393/2007 - 822/2021
Departamentos: Electrónica e Computación
Áreas: Linguaxes e Sistemas Informáticos
Centro Escola Politécnica Superior de Enxeñaría
Convocatoria: Segundo semestre
Docencia: Sen docencia (Extinguida)
Matrícula: Non matriculable | 1ro curso (Si)
Presentación
A materia describe as estruturas de datos lineares e as técnicas algorítmicas básicas para o deseño de algoritmos e a implementación de programas en casos prácticos sinxelos, desenvolvendo as habilidades necesarias para que o alumno analice a complexidade computacional dun algoritmo dado, así como desenvolver as capacidades necesarias para escoller a combinación de estruturas de datos e a estratexia de resolución máis adecuada para resolver de forma eficiente (en termos de recursos espaciais e temporais) un problema específico. Ademais, esta materia completa a formación do alumno en estruturas de datos presentando estruturas de datos non lineais e o seu uso para representar e resolver problemas importantes.
Dando continuidade á materia Fundamentos da programación, desenvólvense os criterios básicos que deberían guiar o deseño dun programa modular, así como a elaboración e execución dun plan de proba adecuado para verificar o bo funcionamento dun programa. Todos estes aspectos desenvolveranse de forma práctica en proxectos de programación integrada de todos os contidos aprendidos e de todas as competencias adquiridas coa realización das actividades da materia.
Obxectivos da materia
• Estudar detalladamente os requisitos dun problema e identificar os obxectivos e as súas dependencias.
• Desenvolver a capacidade de abstracción e xeneralización para buscar solucións alternativas no deseño dun programa.
• Saber programar baixo o paradigma orientado a obxectos no desenvolvemento de aplicacións, identificando posibles estratexias para resolver problemas con conceptos como herdanza, polimorfismo ou encapsulación.
• Coñecer estruturas de datos para a organización de información que permita obter algoritmos eficaces.
• Adquirir a capacidade de analizar rigurosamente a eficiencia dos algoritmos, distinguindo conceptos de eficiencia no tempo e no espazo.
• Saber comparar, en termos de eficiencia, diferentes solucións algorítmicas co mesmo problema para reducir o custo computacional
• Coñecer as familias máis importantes de problemas algorítmicos e estudar diferentes esquemas ou paradigmas de deseño aplicables para resolvelos.
• Determinar o método de busca máis adecuado segundo as características de cada problema.
• Aplicar estratexias de busca cega e de busca informada para planificar unha secuencia de accións para atopar unha solución que cumpra as restricións do problema.
• Desenvolver capacidade crítica para a verificación do algoritmo con todos os casos posibles de entrada de datos.
Contidos
A memoria do título contempla para esta materia os seguintes contidos:
Tipos abstractos de datos: definición e formalización. Estruturas de datos lineais e complexas. Deseño recursivo. Notacións algorítmicas. Estratexias e técnicas algorítmicas (voraces, divide e vencerás, programación dinámica, volta atrás) Algoritmos básicos de procura, ordenación e mestura. Implementación destas estruturas desde o punto de vista orientado a obxectos.
Estes contidos serán desenvolvidos de acordo co seguinte temario:
Introdución
* Abstracción
* Tipos Abstractos de Datos
Programación Orientada a obxectos e Análises
* Clases e Obxectos: Tipos de datos «a medida».
* Variables e funcións estáticas
* Composición, Herdanza e Polimorfismo
* Algunhas clases de uso común. Exemplos
* Clases en C++
* Análises da complexidade dos Algoritmos
Estruturas de Datos Lineais
* Pilas
* Colas
* Listas
Deseño Recursivo. Estratexias e técnicas algorítmicas
* Recursividade
* Complexidade en algoritmos recursivos
* Visualización da Recursividade
* Estratexias e técnicas algorítmicas (divide e vencerás, voraces, forza bruta, volta atrás, programación dinámica)
Ordenación e Procura
* Algoritmos de Procura: Secuencial, Binaria, por salto, Fibonacci, exponencial, interpolación, Hashing, ?
* Algoritmos de Ordenación: Burbulla, selección, inserción, Shell, mestura, rápida (QuickSort), ?
Estruturas de Datos Complexas
Árbores
* Introdución
* Representacións de árbores
* Percorridas de árbores
* Árbores binarios de procura. Análise
* Árbores binarios de procura equilibrados
Grafos
* O TAD Grafo
* Matrices e listas de adyacencia
* Grafo Escaleira de Palabras
* Procura en Anchura
* O problema do cabalo
* Procura en profundidade
* Ordenamento Topológico
* O problema da ruta máis curta
Bibliografía básica e complementaria
Bibliografía básica:
Brad Miller e David Ranum, Luther College: Resolución de problemas con algoritmos e estruturas de datos usando Python
HEILEMAN, G.L. Estructuras de datos, algoritmos e programación orientada a obxectos. Madrid: McGraw-Hill, 2001. ISBN 84-481-1173-7.
JOYANES AGUILAR, L., ZAHONERO MARTÍNEZ, I. Algoritmos e estruturas de datos: unha perspectiva en C. Madrid: McGraw-Hill, 2010. ISBN 9788448140779.
JOYANES AGUILAR, L. et al. Estrutura de datos Libro de problemas. Madrid: McGraw-Hill, 1999. ISBN 84-481-2298-4.
Brassard, G., Bratley, P. Fundamentos de algoritmos. 1 ª edición, Lugar de publicación: Madrid, Prentice Hall, 2002. ISBN: 84-89660-00-X
Bibliografía complementaria:
BOWMAN, C.F. Algoritmos e estruturas 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 e métodos algorítmicos. Exercicios resoltos. 2ª edición: resoltos 213 exercicios. Ibergarceta Publicaciones S.L., 2013. ISBN 978-8415452652.
COMPETENCIAS
BASICAS
• CB1: Que os estudantes demostraron posuír e comprender coñecementos nunha área de estudo que parte da base da educación secundaria xeral, e normalmente atópase a un nivel que, aínda que está soportado por libros de texto avanzados, tamén inclúe algúns aspectos que implican coñecementos procedentes da vangarda do seu campo de estudo.
• CB2: Que os alumnos saben aplicar os seus coñecementos ao seu traballo ou vocación de xeito profesional e posúan as habilidades que se adoitan demostrar mediante a elaboración e defensa dos argumentos e a resolución de problemas dentro da súa área de estudo.
• CB5: Que os estudantes desenvolvan esas habilidades de aprendizaxe necesarias para realizar estudos posteriores cun alto grao de autonomía.
XERAIS
• CG2: Capacidade para resolver problemas no campo da enxeñaría robótica con creatividade, iniciativa, metodoloxía e razoamento crítico.
• CG3: Capacidade para utilizar ferramentas informáticas para a modelización, simulación e deseño de aplicacións de enxeñería.
• CG5: Ser capaz de obter e analizar información sobre circuítos, elementos de máquina, control automático, sensores e sistemas informáticos, co obxectivo final de conseguir aplicacións robóticas autónomas e flexibles.
ESPECÍFICAS
• CE5: Capacidade para analizar, deseñar, representar e programar algoritmos e xestionar estruturas de datos adecuadas para resolver problemas no campo da robótica.
TRANSVERSAIS
• CT1: Capacidade de análise e síntese.
• CT3: Capacidade de traballo individual, cunha actitude autocrítica.
• CT4: Capacidade para traballar en grupo e xestionar situacións problemáticas colectivamente.
• CT9: Habilidade na xestión das tecnoloxías da información e da comunicación (TIC).
• CT10: Uso de información bibliográfica e de Internet.
• CT12: Capacidade para resolver problemas mediante a aplicación integrada dos seus coñecementos.
Metodoloxía do ensino
A metodoloxía de ensino que se persegue dentro da materia onde se encadra a presente materia é a seguinte:
* Os contidos da materia impartiranse, de forma presencial ou virtual, de maneira indistinta nas clases expositivas e nas clases interactivas. As unidades teóricas e prácticas impartiranse de maneira alternativa ao longo do semestre co obxecto de afianzar os conceptos impartidos nelas.
* A realización de todas as actividades propostas é necesaria, do mesmo xeito que a asistencia a todas as clases (expositivas e interactivas) para superar a materia.
* Os recursos necesarios para a presente materia son os seguintes:
a) Dispor dun computador persoal
b) Copias dos apuntamentos da materia.
c) Acceso dos alumnos á bibliografía na Biblioteca ou por Internet.
d) Acceso á ferramenta Ms Visual Studio
e) OpenOffice ou LibreOffice para a preparación da documentación das prácticas.
f) Acceso o campus virtual da USC
g) Acceso a Ms Teams
Clases Expositivas e interactivas: As clases, tanto presenciais como virtuais, consistirán na explicación dos apartados do programa coa axuda dunha presentación electrónica. Tamén se realizarán exercicios na lousa, facendo que o alumnado participe e desenvolver programas interactuando co profesor para a resolución destes. Todos os contidos dixitais (os códigos dos programas en Python e en C++, as diapositivas da presentación en formato PDF, así como as explicacións destas en formato vídeo por streaming), serán postos a disposición do alumnado tanto no Campus virtual como na contorna colaborativo Ms Teams.
As clases presenciais fundamentalmente terán lugar nunha aula de informática, na que se proporcionará un computador para cada alumno. Cando a docencia impártase por medios virtuais, utilizarase a ferramenta Ms Teams para levar a cabo a mesma. A metodoloxía de aprendizaxe de prácticas consiste fundamentalmente na resolución por parte do alumno das actividades propostas e outros exercicios de programación, individualmente ou por grupos, coa axuda do profesor.
Actividades: Ao longo do semestre, o alumno deberá resolver problemas de programación adecuados aos contidos desenvolvidos até o momento. Ditas actividades correspóndense con enunciados dos problemas resoltos nos exames de convocatorias anteriores e con problemas propostos en recursos detallados na bibliografía.
A resolución e entrega destas actividades considéranse esenciais para alcanzar un resultado satisfactorio na presente materia. Estas actividades serán defendidas polos alumnos en sesións de tutoría a través da plataforma Ms Teams
Actividades experimentais: Ao finalizar o semestre o alumno, individualmente ou por grupos e coa axuda do profesor, deberá entregar unha recompilación de programas en C++ ou en Python para a resolución de problemas de Robótica. Coa devandita recompilación, crearase unha libraría ou un módulo específico de programas para Robótica.
Tutorías: As sesións de tutorías servirán para resolver as dúbidas do alumnado en canto aos contidos da materia, resolución de problemas de teoría e exercicios de prácticas propostos no anexo de actividades. Estas tutorías serán tanto presenciais como virtuais a través de correo electrónico, campus virtual ou plataforma Ms Teams, e son fundamentais para alcanzar unha aprendizaxe efectiva da materia.
Curso Virtual: Esta materia disporá dun curso virtual desenvolvido sobre a plataforma de Campus virtual da USC, usando ademais a ferramenta colaborativa Ms Teams. Nestas facilitaráselle ao alumnado todo o material necesario en formato dixital, ademais de distintas ferramentas de comunicación para o apoio, tanto da docencia virtual como das tutorías, incluíndo 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
PONDERACIÓN MÍNIMA
PONDERACIÓN MÁXIMA
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 las actividades propuestas (30% 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 (10% de la calificación final)
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 40% 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 40% 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%
Os alumnos repetidores de anos anteriores estarán exentos do cumprimento do deber de asistencia ás clases presenciais. Para aprobar a materia é obrigatorio a realización e entrega das actividades propostas nas mesmas datas establecidas para o resto dos alumnos, así como superar a proba de tipo Test e o exame de tipo práctico.
Os alumnos que non asistan a ningunha das actividades de ensino programadas por conciliación laboral ou familiar deberán cumprir coas disposicións da Instrución 1/2017 da Secretaría Xeral. Nestes casos, para aprobar esta materia, é obrigatorio a realización e entrega das actividades propostas, así como superar a proba de tipo Test e o exame de tipo práctico.
Tempo de estudo e traballo persoal
A materia ten unha carga de traballo de 6 ECTS. Estes datos levan a unha carga de traballo para o material situado entre 150 (6x25) horas e 180 (6x30) horas.
Na guía do asunto pódese ver un estudo máis detallado sobre o tempo de estudo e o traballo persoal necesario para superar a materia. A recomendación xeral sería empregar entre 10 e 12 horas (incluidas as 4 de clase) por semana
Traballo na aula
• Clases teóricas (exposicións de grupo grande): 24 horas.
• Prácticas (con pequenos grupos): 24 horas.
• Titorías en grupo (con grupos reducidos): 3 horas.
• Titorías individualizadas: 4 horas.
• Actividades de avaliación: 5 horas.
TOTAL 60 horas
Traballo persoal do alumnado
• Lectura e preparación de temas: 24 horas.
• Realización de exercicios e preparación de traballos: 48 horas.
• Titorías en grupo: 7 horas.
• Titorías individualizadas: 3 horas.
• Preparación de probas de avaliación: 8 horas.
TOTAL 90 horas
Os alumnos que non asistan a ningunha das actividades de ensino programadas por conciliación laboral ou familiar deberán cumprir coas disposicións da Instrución 1/2017 da Secretaría Xeral. Nestes casos, para aprobar esta materia, é obrigatorio a realización e entrega das actividades propostas, así como superar a proba de tipo Test e o exame de tipo práctico.
Dado que se emprega unha metodoloxía sustentada na avaliación continua, é necesario un traballo continuado cos contidos da materia. Isto é especialmente importante coas prácticas, xa que uns contidos vanse asentando sobre os anteriores, o que fai moi conveniente ter asimilados os temas anteriores antes de tentar comprender os novos. É a única forma de poder ir superando as distintas actividades de avaliación que se propoñen.
Para o estudo da materia, recoméndase realizar a totalidade dos exercicios dos boletíns de problemas e das actividades, tanto os que se resolvan nas propias sesións interactivas, como os que queden propostos.
A asignatura impartirase en castelan
Plan de continxencia:
Para o presente curso 20/21 exponse tres escenarios posibles:
Escenario 1: normalidade adaptada
* A docencia expositiva e interactiva será fundamentalmente de carácter presencial. As tutorías poderán realizarse parcialmente de maneira virtual.
* A modalidade preferente para a realización das prácticas será a presencialidad.
* A avaliación será levada a cabo de forma presencial
Escenario 2: distanciamento
* A docencia presencial convivirá coa virtual. As clases expositivas serán virtuais e as interactivas presenciais
* A avaliación será levada a cabo de forma presencial
Escenario 3: peche das instalacións
* A docencia será completamente de carácter virtual, tanto con mecanismos síncronos como asíncronos, usando o Campus virtual e a plataforma Teams
* De non poderse levar a cabo a avaliación presencial, esta será Telemática
Efren Arias Jordan
Coordinador/a- Departamento
- Electrónica e Computación
- Área
- Linguaxes e Sistemas Informáticos
- Correo electrónico
- efren.arias [at] usc.es
- Categoría
- Profesor/a: Titular de Escola Universitaria
| Luns | |||
|---|---|---|---|
| 09:00-11:00 | Grupo /CLE_01 | Castelán | Salón de Actos (Pav.III) |
| Mércores | |||
| 09:00-11:00 | Grupo /CLIL_03 | Castelán | Aula de Informática 5 (Pav III) |
| Xoves | |||
| 11:00-13:00 | Grupo /CLIL_01 | Castelán | Aula de Informática 5 (Pav III) |
| Venres | |||
| 09:00-11:00 | Grupo /CLIL_02 | Castelán | Aula de Informática 5 (Pav III) |
| 21.05.2021 10:00-14:00 | Grupo /CLE_01 | Aula de Informática 1 (Pav.III) |
| 21.05.2021 10:00-14:00 | Grupo /CLE_01 | Aula de Informática 2 (Pav.II-PSI) |
| 21.05.2021 10:00-14:00 | Grupo /CLE_01 | Aula de Informática 4 (Pav.III) |
| 21.05.2021 10:00-14:00 | Grupo /CLE_01 | Aula de Informática 5 (Pav III) |
| 13.07.2021 10:00-14:00 | Grupo /CLE_01 | Aula de Informática 1 (Pav.III) |
| 13.07.2021 10:00-14:00 | Grupo /CLE_01 | Aula de Informática 2 (Pav.II-PSI) |
| 13.07.2021 10:00-14:00 | Grupo /CLE_01 | Aula de Informática 4 (Pav.III) |
| 13.07.2021 10:00-14:00 | Grupo /CLE_01 | Aula de Informática 5 (Pav III) |