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
Centro Escola Politécnica Superior de Enxeñaría
Convocatoria: Segundo semestre
Docencia: Sen docencia (Extinguida)
Matrícula: Non matriculable
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 (2 horas presenciais)
* Abstracción
* Tipos Abstractos de Datos
Programación Orientada a obxectos e Análises (8 horas presenciais, 12 non presenciais)
* 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 (6 horas presenciais, 12 non presenciais)
* Pilas
* Colas
* Listas
Deseño Recursivo. Estratexias e técnicas algorítmicas (8 horas presenciais, 12 non presenciais)
* 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 (8 horas presenciais, 12 non presenciais)
* 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 Complexa
Árbores (8 horas presenciais, 12 non presenciais)
* Introdución
* Representacións de árbores
* Percorridas de árbores
* Árbores binarios de procura. Análise
* Árbores binarios de procura equilibrados
Grafos (8 horas presenciais, 12 non presenciais)
* 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
Brad Miller e 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 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.
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 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 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 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
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 avaliación
A memoria do título recolle que, para os sistemas de avaliación da materia, a normativa xeral de avaliación da USC e a
especificacións descritas no apartado 5.1. Do mesmo. En concreto, e para esta materia, os pesos mínimo e máximo de cada un
sección, como se reflicte na seguinte táboa
SISTEMAS DE AVALIACIÓN
Exame: entre 0% e 70%
Traballos/Actividades: entre 0% e 40%
Titorías: entre 0% e 10%
A asistencia ás clases interactivas e expositivas é obrigatoria e terase en conta para a avaliación da materia. A asistencia será obrigatoria
polo menos o 95% das sesións (salvo por motivos moi xustificados, segundo a normativa da USC). As clases prácticas impartiranse ao longo do curso
durante as clases interactivas.
Recoméndase encarecidamente o uso de titorías, tanto presenciais como virtuais, para a resolución de dúbidas ao respecto.
problemas ou calquera contido do asunto.
Para superar a materia, o alumno deberá realizar todas as actividades que se propoñan e superar os exames correspondentes.
Para os casos de realización fraudulenta de exercicios ou probas aplicarase o disposto nas "Normas de avaliación do rendemento".
académico dous estudantes e revisión de titulacións” da USC.
Primeira oportunidade:
Para superar a materia, o alumno deberá ter asistido ás clases, ter entregado e superado as actividades propostas, que se realizarán a través de obradoiros na plataforma virtual da materia (40% da nota final) e aprobar por separado tanto a teoría, que se realizará mediante un exame tipo test coa axuda da plataforma virtual. . , como a parte práctica, que se realizará mediante tarefas na plataforma virtual da materia consistentes na resolución de problemas de programación (60% da nota final). Terase en conta a asistencia ás titorías para a resolución de dúbidas
As preguntas do exame teórico poderán referirse tanto aos contidos reflectidos nas notas da materia como aos contidos prácticos traballados polo alumno nas actividades impartidas. Estas probas poden consistir en preguntas tipo test, preguntas curtas e problemas prácticos.
En todas as probas avaliarase o grao de asimilación das competencias establecidas na programación docente da materia. Non haberá exame parcial. Para aprobar a materia haberá que demostrar un coñecemento superior ao 50% en todo tipo de avaliación.
Segunda oportunidade:
Ademais da avaliación continua, todos os estudantes teñen dereito a asistir ao exame de segunda oportunidade. Mantense a nota, e tamén o seu peso na nota final, obtida en cada unha das partes (asistencia a clase, entrega de actividades e a cualificación da parte teórica, así como da parte práctica) durante o curso. Non obstante, o alumnado poderá presentar previamente o exame de segunda oportunidade, aquelas actividades que non alcanzaran a nota de corte na convocatoria anterior. Para superar a materia, o alumnado deberá demostrar un coñecemento superior ao 50% en todo tipo de avaliación.
Sistema de avaliación
Competencias
Peso mínimo
peso máximo
Actividades propostas CG2, CG3, CG5, CE5 entre 20% e 40%
Proba ou probas de avaliación CG2, CG3, CG5, CE5 entre 50% e 70%
Titorías CG2, CG3, CG5, CE5 entre 0 e 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
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
Por razóns evidentes de convivencia, así como unha adecuada calidade das actividades didácticas que levan a cabo no marco do grao, está terminantemente prohibido o uso do teléfono móbil na aula, responsabilizando ao alumnado das consecuencias legais e académicas que poidan derivarse da utilización de leste.