Algoritmos e Estruturas de Datos

O obxectivo de formación desta materia é desenvolver as destrezas necesarias para que o alumnado saiba analizar a complexidade computacional dun determinado algoritmo, así como desenvolver as capacidades necesarias para escoller a combinación de estruturas de datos e estratexia de resolución máis apropiada para resolver de modo eficiente (en termos de recursos espaciais e temporais) un determinado problema. Ademais, esta materia completa a formación do alumnado en estruturas de datos ao presentar as estruturas de datos non lineais e a súa utilización para representar e resolver problemas de entidade.

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

Tema 2. Estruturas de datos non lineais: Árbores
* Conceptos básicos e propiedades
* Árbores de busca
* Árbores de busca equilibrados
* Aplicacións

Tema 3. Estruturas de datos non lineais: Grafos
* Conceptos básicos e propiedades
* Algoritmos fundamentais con grafos
* Aplicacións

Tema 4. Táboas hash

Tema 5. Estratexias algorítmicas
* Divide e vencerás
* Algoritmos voraces
* Programación dinámica
* Volta atrás
* Ramificación e 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.

A materia contribúe a alcanzar as seguintes competencias, recollidas na memoria do título de Grao en Enxeñaría Informática da USC para o Módulo de Programación:
- Desenvolver programas cun bo estilo de programación, coa documentación necesaria e os comentarios adecuados.
- Saber calcular a complexidade computacional dun algoritmo e avaliar a implementación máis adecuada dun algoritmo determinado de acordo cos recursos dispoñibles (memoria e tempo de execución).
- Utilizar ferramentas de edición, compilación, e execución para desenvolver programas.
- Capacidade para aplicar estratexias de depuración, proba e corrección de programas.
- Escoller a estrutura de datos máis correcta e eficiente para resolver un problema.
- Manexar diferentes niveis de abstracción para estruturar o software a desenvolver.
- Deseñar algoritmos dunha certa complexidade e implementalos aplicando os principios da programación estruturada e modular.
- Comprensión de conceptos relacionados co desenvolvemento de algoritmos.
- Manexo de xestores de erros, xestión de excepcións e tolerancia a fallos.
- Uso de repositorios de software.
- Motivación e capacidade de autoaprendizaxe.
- Autoestima e espírito de superación.

Ademais, contribúese ao desenvolvemento das competencias xerais e específicas recollidas nas correspondentes táboas na mencionada memoria do título:
* Competencias xerais:
CG1: Capacidade para desenvolver proxectos no ámbito da enxeñaría en informática que teñan por obxecto, de acordo cos coñecementos adquiridos, a concepción, o desenvolvemento ou a explotación de sistemas, servizos e aplicacións informáticas.
CG3: Capacidade para deseñar, desenvolver, avaliar e asegurar a usabilidade dos sistemas, servizos e aplicacións informáticas, así como da información que xestionan.
CG8: Coñecemento das materias básicas e tecnoloxías, que capaciten para a aprendizaxe e desenvolvemento de novos métodos e tecnoloxías, así como as que lles doten dunha gran versatilidade para adaptarse a novas situacións.
CG9: Capacidade para resolver problemas con iniciativa, toma de decisións, autonomía e creatividade. Capacidade para saber comunicar e transmitir os coñecementos, habilidades e destrezas da profesión de Enxeñaría Técnica en Informática.
* Competencias transversais:
TR1 (Instrumentais): Capacidade de análise e síntese. Capacidade de organización e planificación. Comunicación oral e escrita. Capacidade de xestión da información. Resolución de problemas. Toma de decisións.
TR2 (Persoais): Traballo en equipo. Habilidades nas relacións interpersoais. Razoamento crítico.
TR3 (Sistémicas): Aprendizaxe autónoma. Adaptación a novas situacións. Creatividade. Iniciativa. Motivación pola calidade.
* Formación Básica
FB3: Capacidade para comprender e dominar os conceptos básicos de algorítmica e complexidade computacional, e a súa aplicación para a resolución de problemas propios da enxeñaría.
FB4: Coñecementos básicos do uso e programación dos computadores.
FB5: Coñecemento dos fundamentos da programación dos sistemas informáticos, e a súa aplicación para a resolución de problemas propios da enxeñaría.
* Comúns á rama da Informática
RI6: Coñecemento e aplicación dos procedementos algorítmicos básicos das tecnoloxías informáticas para deseñar solucións a problemas, analizando a idoneidade e complexidade dos algoritmos propostos.
RI7: Coñecemento, deseño e utilización de forma eficiente dos tipos e estruturas de datos máis adecuados á resolución dun problema.

A metodoloxía seguida usa como plataforma básica o Campus Virtual da USC. Na aula virtual da materia o alumnado disporá de toda a información (material de teoría, presentacións de clase, guións de prácticas, bibliotecas de TADs, etc.).
Impartiranse 20 horas de clases maxistrais en sesións de 1 hora, e haberá unha sesión semanal de dúas horas e media de traballo práctico (resolución de problemas, programación).
O alumnado poderá en todo momento seguir a súa progresión, ao ter dispoñibles continuamente as notas dos exercicios e proxectos que teñan que entregar para seguir o modelo de avaliación continua.
As competencias FB3, FB4, FB5, RI6, RI7, CG1, CG3, CG8 e CG9, así como as indicadas do módulo de programación teñen contidos asociados na parte teórica e práctica da materia e avalíanse de xeito explícito nas probas realizadas ao longo do curso.
As competencias de tipo TR1 trabállanse fundamentalmente no aspecto de capacidade de organización e planificación, toma de decisións e resolución de problemas, nas entregas que teñen que realizar nas clases prácticas.
Das competencias do tipo TR2 trabállase fundamentalmente a de razoamento crítico, avaliando as distintas posibilidades de resolución de problemas tanto na parte teórica como na práctica.
Do grupo de competencias TR3 trabállanse principalmente a creatividade, adaptación a novas situacións, e motivación pola calidade, especialmente nas clases prácticas, onde se propoñen problemas para desenvolver estas competencias, con cambios de situacións, e se avalían na cualificación do problema a entregar.

A avaliación consta de dúas partes individuais separadas, teoría e práctica, sendo necesario superar ambas as partes independentemente. Ademais, é necesario aprobar tódolos módulos de prácticas e tódolos tests e probas de teoría de forma independente.

A parte práctica da materia avaliarase mediante un proceso de AVALIACIÓN CONTINUA:
-30% da nota global: entrega de proxectos prácticos durante o cuadrimestre, con prazos e normas de entrega/corrección prefixadas polo profesorado.
Utilízase para avaliar as competencias CG1, CG3, CG8, CG9, TR1, TR3, FB4, FB5, RI6 e RI7, ademais das especificadas do módulo de Programación, mediante a entrega periódica das prácticas realizadas durante o cuadrimestre.

A parte teórica (70% da nota global) avaliarase en dúas partes:
-10% da nota: Realización de tests ao longo do cuadrimestre.
-60% da nota: Exame global ao final do cuadrimestre
Utilízase para avaliar as competencias CG8, CG9, TR2, FB3, FB4, FB5, RI6 e RI7, ademais das especificadas do módulo de Programación, mediante distintas preguntas no exame teórico e a avaliación dos exercicios realizados e entregados durante o semestre.

A entrega dalgún traballo (proxecto ou exercicio) con posterioridade ao 1 de novembro levará asociada a consideración de PRESENTADA/O na cualificación da materia, independentemente da asistencia ou non ao exame final.

RECUPERACIÓN OU 2ª OPORTUNIDADE (XULLO):
Poderá realizar este exame o alumnado que non superase algunha das partes na avaliación continua, ou as persoas que opten directamente por esta opción.
- Teoría (70% da nota final): repetición de tests non superados e exame final escrito.
- Práctica (30% da nota final): realización de prácticas non superadas mediante proposta de exercicios de programación a entregar a data anterior ao exame final.

Para o alumnado repetidor: Mantéñense unicamente os resultados da avaliación teórica ou práctica que se teña superado (nota superior a 6) no curso inmediatamente anterior. Noutro caso, terá que repetirse a materia completa.

No caso de realización fraudulenta de exercicios ou probas, será de aplicación o recollido na Normativa de avaliación do rendemento académico dos estudantes e de revisión de cualificacións.
En aplicación da Normativa da ETSE sobre plaxio (aprobada pola Xunta da ETSE o 19/12/2019), a copia total ou parcial dalgún exercicio de prácticas ou teoría suporá o suspenso nas dúas oportunidades do curso, coa cualificación de 0,0 en ambos casos.

Esta materia ten 6 créditos ECTS, correspondendo unha carga de traballo total de 150 horas. Este tempo pode desagregarse nos seguintes apartados:
TRABALLO PRESENCIAL NA AULA:
*Clases maxistrais: 20 horas
*Sesións prácticas en grupos reducidos: 30 horas
*Actividades de avaliación: 5 horas
Total horas traballo presencial na aula: 55 horas
TRABALLO PERSOAL DO ALUMNADO:
* Estudo autónomo: 30 horas
* Escritura de exercicios, traballos, etc.: 15 horas
* Programación/experimentación en computador: 35 horas
* Avaliación de traballos, proxectos, exames: 15 horas
Total horas traballo persoal: 95 horas

Supóñense uns coñecementos suficientes de linguaxe de programación C e dos fundamentos de grafos, que ven, respectivamente, nas materias de Programación I e II, e en Matemática Discreta de primeiro curso.
Recoméndase seguir o modelo de avaliación continua, o que significa levar a materia ao día. Desta forma seguiranse con maior facilidade as clases teóricas e as clases prácticas, o que fai a materia máis levadía.
Tamén se recomenda encarecidamente o uso das horas de titorías para aclarar calquera dúbida que se poida presentar no desenvolvemento da materia.

Utilizarase o campus virtual da USC para toda a docencia, publicación de material, guións de prácticas e entrega de traballos.
O sistema operativo a utilizar nas prácticas é indiferente: Windows ou Linux
Utilizaranse basicamente o IDE Netbeans ou CLion co compilador de C de cygwin instalado para Windows ou o gcc para Linux.
A materia impartirase principalmente en castelán.