Estructura de datos y algoritmos Código:  M0.506    :  5
Consulta de los datos generales   Descripción   La asignatura en el conjunto del plan de estudios   Campos profesionales en el que se proyecta   Conocimientos previos   Información previa a la matrícula   Objetivos y competencias   Contenidos   Consulta de los materiales de los que dispone la asignatura   Materiales y herramientas de apoyo   Informaciones sobre la evaluación a la UOC   Consulta del modelo de evaluación  
ATENCIÓN: Este es el plan docente de la asignatura para el primer semestre del curso 2020-2021. Os servirá para planificar la matrícula (consultad si la asignatura se ofrece este semestre en el espacio del Campus Más UOC / La Universidad / Planes de estudios). Una vez empiece la docencia, tenéis que consultarlo en el aula. (El plan docente puede estar sujeto a cambios).

A la hora de diseñar un programa suele ser muy importante su eficiencia, es decir, que consuma la menor cantidad de recursos para llevar a cabo su cometido. Así pues nos interesa minimizar el tiempo de cálculo, el espacio de memoria para almacenar los datos, el número de mensajes que deben enviarse a través de la red, la cantidad de energía que consumida, etc.

Dos herramientas fundamentales para conseguir esta eficiencia son las estructuras de datos y los esquemas algorítmicos:

  • Las estructuras de datos se centran en cómo gestionar la información: son estrategias para organizar los datos de forma que se reduzca el tiempo de acceso y manipulación, así como el espacio de almacenamiento necesario.
  • Los esquemas algorítmos se centran en el proceso de cálculo: son patrones generales que describen los pasos necesarios para alcanzar una solución y que deben particularizarse para el problema concreto a resolver.

Esta asignatura presenta los conceptos sobre estructuras de datos y algorítmica necesarios para realizar actividades de investigación. En particular, la asignatura revisa conceptos fundamentales de complejidad algorítmica (coste espacial y temporal, cálculo del coste de un algoritmo, órdenes de magnitud usuales) así como conceptos básicos de estructuras de datos (tipos abstractos de datos, gestión de apuntadores y memoria, etc). A partir de esta base, la asignatura profundiza en estructuras de datos frecuentas (pilas, colas, listas, árboles, heaps, tablas de hash) y presenta una introducción a algoritmos sobre grafos (recorridos, caminos mínimos, árboles generadores, etc.).

Amunt

Estructuras de datos y algoritmos es una asignatura optativa del Máster Interuniversitario en Ingeniería Computacional y Matemática.

Los conocimientos adquiridos en esta asignatura serán de utilidad en el desarrollo de prácticas en otras asignaturas del Máster. En particular, se recomienda cursar esta asignatura antes de cursar Optimización combinatoria.

Amunt

Los conceptos adquiridos en esta asignatura son fundamentales para desarrollar software que utilice de forma eficiente los recursos de cálculo disponibles. Por este motivo, esta asignatura es relevante para cualquier trabajo relacionado con el diseño e implementación de software, especialmente en el campo del I+D o de la matemática aplicada.

Amunt

Esta asignatura requiere conocimientos básicos de algorítmica: conocer las primitivas básicas de programación (bucles, condicionales, etc.) y comprender algoritmos descritos en pseudocódigo. También se requiere un conocimiento previo del lenguaje de programación orientado a objectos Java suficiente para escribir, ejecutar y testear programas.

Por otro lado, los materiales centrales de la asignatura están en inglés. Por este motivo, se recomienda tener un buen nivel de comprensión lectora de inglés técnico.

Amunt

Antes de cursar esta asignatura, es necesario disponer de conocimientos previos de algorítmica y programación en Java y tener un buen nivel de inglés técnico a nivel de lectura.

Amunt

La competencias generales del Máster que se ponen de manifiesto en esta asignatura son:

  • Comprender y poder aplicar conocimientos avanzados de computación y métodos numéricos o computacionales a problemas de ingeniería.
  • Aplicar los métodos matemáticos y computacionales a la resolución de problemas tecnológicos y de ingeniería de empresa, particularmente en tareas de investigación, desarrollo e innovación.
  • Diseñar, implementar y validar algoritmos utilizando las estructuras más convenientes.

Las competencias específicas de esta asignatura son:

  • Conocer el concepto de tipo abstracto de datos y saber definir un tipo abstracto de datos para un problema concreto.
  • Conocer los tipos abstractos de datos secuenciales (pilas, colas, listas) y sus operaciones, y saber utilizarlos para resolver problemas.
  • Conocer el concepto de complejidad asintótica, saber calcularla para un algoritmo dado y ser capaz de utilizarla para comparar dos algoritmos diferentes desde el punto de vista de su eficiencia.
  • Conocer diferentes algoritmos de ordenación, sus ventajas e inconvenientes y saber elegir el más apropiado en un contexto concreto.
  • Conocer diferentes estrategias de búsqueda de información (hashing, árboles de búsqueda), sus ventajas e inconvenientes y saber elegir la más apropiada en un contexto concreto.
  • Conocer los principales algoritmos sobre grafos, su complejidad y ser capaz de utilizarlos para resolver problemas concretos.
  • Ser capaz de elegir la estructura de datos más apropiada para un problema según criterios de eficiencia y justificar argumentadamente la decisión.

Amunt

La asignatura se estructura en cuatro bloques temáticos:

Bloque temático

Contenidos

1. Estructuras de datos secuenciales

Tipos abstractos de datos

Pilas, colas, listas

2. Ordenación (Sorting)

Complejidad asintótica

Algoritmos de ordenación

Colas con prioridad

3. Búsqueda (Searching)

Árboles

Árboles de búsqueda

Tablas de hash

4. Algoritmos sobre grafos

Grafos dirigidos y no dirigidos

Recorridos: DFS, BFS

Búsqueda de componentes conexas y ciclos

Caminos mínimos

Árboles generadores



Amunt

MATLAB_ENG PDF
MATLAB PDF
Diseño de estructuras de datos PDF

Amunt

El material central de la asignatura es un libro de referencia en este ámbito: "Algorithms, 4th Edition", de Robert Sedgewick y Kevin Wayne. Tanto por extensión como por profundidad, los contenidos del libro van más allá de lo que se estudiará en la asignatura y os será útil como referencia durante vuestra carrera profesional.

Para guiar el estudio del libro y focalizar los contenidos relevantes del libro dentro de la asignatura, en el aula de la asignatura podréis encontrar guías de estudio semanales de los contenidos a estudiar cada semana con consejos sobre cómo revisar el material del libro.

A modo de material complementario, en el aula de la asignatura podréis encontrar módulos didácticos UOC titulados "Diseño de estructuras de datos". Estos materiales os pueden servir como apoyo para resolver dudas que podáis tener revisando el libro de la asignatura. Sin embargo, estos materiales se centran mucho en cómo están implementadas las estructuras de datos, mientras que en esta asignatura nos centraremos más en saber cómo utilizarlas y los criterios para elegir la más apropiada.

Amunt

La Normativa académica de la UOC dispone que el proceso de evaluación se fundamenta en el trabajo personal del estudiante y presupone la autenticidad de la autoría y la originalidad de los ejercicios realizados.

La falta de originalidad en la autoría o el mal uso de las condiciones en las que se hace la evaluación de la asignatura es una infracción que puede tener consecuencias académicas graves.

El estudiante será calificado con un suspenso (D/0) si se detecta falta de originalidad en la autoría de alguna actividad evaluable (práctica, prueba de evaluación continua (PEC) o final (PEF), o la que se defina en el plan docente), ya sea porque ha utilizado material o dispositivos no autorizados, ya sea porque ha copiado de forma textual de internet, o ha copiado de apuntes, de materiales, manuales o artículos (sin la citación correspondiente) o de otro estudiante, o por cualquier otra conducta irregular.

La calificación de suspenso (D/0) en la evaluación continua (EC) puede conllevar la obligación de hacer el examen presencial para superar la asignatura (si hay examen y si superarlo es suficiente para superar la asignatura según indique este plan docente).

Cuando esta mala conducta se produzca durante la realización de las pruebas de evaluación finales presenciales, el estudiante puede ser expulsado del aula, y el examinador hará constar todos los elementos y la información relativos al caso.

Además, esta conducta puede dar lugar a la incoación de un procedimiento disciplinario y la aplicación, si procede, de la sanción que corresponda.

La UOC habilitará los mecanismos que considere oportunos para velar por la calidad de sus titulaciones y garantizar la excelencia y la calidad de su modelo educativo.

Amunt

Esta asignatura sólo puede superarse a partir de la evaluación continua (EC). La nota final de evaluación continua se convierte en la nota final de la asignatura. La fórmula de acreditación de la asignatura es la siguiente: EC.

 

Amunt