Breve descripción de la asignatura:
Esta asignatura es la continuación de Fundamentos de programación I. Se centra en establecer las estructuras dinámicas de datos necesarias para almacenar la información que luego será tratada por los diferentes algoritmos.
Objetivos de la asignatura:
- Conocer e identificar las principales estructuras de datos, tanto lineales como no lineales, incluidas aquellas que se establecen en memoria secundaria.
- Realizar programas avanzados con tipos abstractos de datos.
- Calcular la complejidad algorítmica de un determinado código.
Temario:
Tema 1. Ficheros.
- Librería estándar de C.
- Operaciones básicas con ficheros: Apertura, lectura, escritura, renombrado, borrado y cierre.
- Ficheros de texto.
- Ficheros binarios. Posicionamiento.
Tema 2. Punteros.
- Definición.
- Declaración de punteros.
- Operadores.
- El operador referencia: &
- El operador indirección: *
- Asignación de punteros.
- Punteros como argumentos.
- Proteger argumentos.
- Devolver punteros.
Tema 3. Punteros y arrays.
- Aritmética de punteros.
- Uso de punteros para el procesamiento de arrays.
- Uso del nombre de array como puntero.
- Arrays como argumentos.
- Punteros y arrays multidimensionales.
Tema 4. Programación modular y documentación de código fuente
- Programación modular en C
- Archivos de cabecera
- Archivos de implementación
- Variables globales
- Documentación de código en C
- Introducción a Doxygen
- Añadir comentarios al código
- Generación automática de documentación
Tema 5. Listas.
- Listas versión estática
- Lista versión cursor.
- Listas dinámicas
- Lista simple con cabecera
- Lista simple sin cabecera
- Lista circular
- Lista doblemente enlazada
- Lista circular doblemente enlazada
Tema 6. Pilas.
- Versión estática.
- Versión dinámica.
Tema 7. Colas.
- Versión estática.
- Versión dinámica.
Tema 8. Árboles.
- Estructuras dinámica.
- Recorrido.
- Previo.
- Simétrico
- Posterior.
- Operaciones básicas:
- Insertar
- Pertenece
- Encontrar
- Padre de
- Borrar
Tema 9. Grafos.
- Versión estática.
- Versión dinámica.
- Algoritmos sobre grafos:
- Dijkstra.
- Floyd.
- Warshall.
Tema 10. Complejidad.
- Conceptos básicos.
- Notaciones asintóticas.
- Ecuaciones de recurrencia.
Breve descripción de la asignatura:
La asignatura de Algoritmia se basa fundamentalmente en explicar los conocimientos teóricos necesarios para cualquier tipo de programación informática. Con estos conocimientos, el alumno tendrá las herramientas necesarias para encontrar soluciones a diferentes tipos de problemas mediante programación software. En particular, se estudiarán algoritmos de recorrido de estructura de datos lineales y no lineales, algoritmos de clasificación y búsqueda, y técnicas de backtracking y hashing.
Objetivos de la asignatura:
- Que el alumno comprenda el esquema de funcionamiento de los algoritmos más importantes de clasificación, búsqueda, backtracking y hashing.
- Que el alumno sea capaz de aplicar soluciones óptimas para la resolución de problemas utilizando algoritmos adecuados
- Que el alumno sepa desarrollar aplicaciones informáticas aplicando el algoritmo correcto para un problema, es decir, que sea capaz de seleccionar un algoritmo de búsqueda, clasificación, backtracking o hashing, dependiendo del problema a resolver
- Que el alumno sea capaz de detectar las importantes diferencias que se pueden obtener, en términos de rendimiento temporal, entre algoritmos aparentemente equivalentes en cuanto a su resultado.
Temario:
Tema 1. Algoritmos de búsqueda.
- Búsqueda lineal
- Búsqueda binaria
- Búsqueda en árboles binarios balanceados (AVL)
- Búsqueda de patrones (Fuerza bruta, KMP, BM)
Tema 2. Algoritmos de clasificación y ordenación.
- Algoritmo de la burbuja
- Algoritmo de inserción
- Algoritmo de selección
- Algoritmo Shell Short
- Algoritmo Bucket Sort
- Algoritmo Quick Sort
- Algoritmo de mezcla directa
- Algoritmo de mezcla natural
Tema 3. Backtracking: Algoritmos de vuelta atrás.
- Concepto de backtracking
- Programación con backtracking
- Ejemplos de algoritmos de backtracking
- Optimización: Branch and bound
Tema 4. Métodos de almacenamiento y búsqueda mediante cálculo de dirección basado en clave (hashing).
- Introducción
- Colisiones y alternativas para su solución
- Borrado de elementos en tablas hash
- Reordenamiento en tablas hash
- Eficiencia de algoritmos hash
Breve descripción de la asignatura:
En esta asignatura se introduce al alumno en programación paralela. Veremos los distintos modelos tradicionales de programación paralela, así como los últimos desarrollos de arquitecturas masivamente paralelas. Concretamente nos centraremos en las unidades de procesamiento gráfico de Nvidia, y en su modelo de programación CUDA.
Objetivos de la asignatura:
- Comprender los conceptos de la programación paralela. El nuevo paradigma de programación, los beneficios y las contrariedades que puede acarrear.
- Comprender los conceptos de sincronización y exclusión mutua.
- Entender y enumerar las características de arquitecturas con memoria compartida y distribuida.
- Conocer algunos problemas paradigmáticos de la programación Concurrente y ser capaces de resolverlos.
- Saber traducir entre semáforos y monitores y a la inversa.
- Explicar adecuadamente las diferencias entre los sistemas basados en paso de mensajes y los basados en variables compartidas.
- Enumerar las características propias de los sistemas basados en paso de mensajes síncronos y los asíncronos.
- Conocer las condiciones para que se produzca un interbloqueo, así́ como las técnicas de manejo de los mismos.
Temario:
Tema 1. Introducción. Conceptos básicos de paralelismo.
- Noción de computación paralela.
- Necesidad de la computación paralela.
- Limitaciones físicas de la computación secuencial.
- Problemas con complejidad elevada.
- Limitaciones físicas de la computación paralela.
- Aspectos de la programación paralela.
- Niveles de paralelismo.
- Arquitectura básica de computadores.
- Consideraciones del lenguaje C.
Tema 2. Modelos de los computadores paralelos.
- Introducción.
- Paralelismo en los computadores monoprocesador.
- Formas básicas de paralelismo.
- Procesadores vectoriales.
- Procesadores escalares.
- Técnicas multhreading.
- Procesadores VLIW (Very Long Instruction Word)
- Paralelismo en los computadores multiprocesadores.
- Clasificación de los computadores paralelos.
- Organización de los computadores paralelos.
- Multiprocesadores con memoria compartida.
- Multicomputadores.
- Redes de interconexión.
- Ventajas e inconvenientes de los multicomputadores frente a los multiprocesadores.
- Redes de computadores.
- Procesadores multinúcleo.
- Modelos de computadores paralelos.
- El modelo de memoria compartida.
- Sistemas de memoria distribuida: el modelo de paso de mensajes
- Sistemas heterogéneos masivamente paralelos.
Tema 3. Modelos de programación paralela tradicionales.
- Visión general.
- Programación mediante paso de mensajes: MPI.
- Conceptos básicos de MPI.
- Operaciones de comunicación colectiva.
- Programación en memoria compartida: OpenMP.
- Conceptos básicos de OpenMP.
- Definición de regiones paralelas.
- Ejecución de bucles en paralelo.
- Ejecución de secciones de código en paralelo
- Combinación de directivas.
- Sincronización.
Tema 4. Modelos de programación paralela emergentes.
- Visión General
- Programación en sistemas heterogéneos masivamente paralelos: CUDA
- Consideración de rendimiento en CUDA
- Estrategias algorítmicas de Optimización en CUDA
- Problemas de localidad de datos.
- Tratamiento de datos dinámicos y dispersos
- Eficiencia en aplicaciones con una ingente cantidad de datos
- Reducir el interfaz de salida
- Depuración y evaluación de códigos CUDA
- Ejecución Multi-GPU
- Introducción al estándar OpenCL.
