Universidad de Jaén

• Algoritmos sobre grafos
• Algoritmos de búsqueda y algoritmos de ordenación

• Actualmente no existe en los planes de estudio ningún prerrequisito, ya que la Universidad de Jaén no aplica esta política

• La asignatura de Teoría de Algoritmos se imparte en el primer cuatrimestre del tercer curso de la I.T.I.G. Es una asignatura fundamental para cualquier estudiante de informática. Con ella el alumno obtiene una capacitación, tanto a nivel profesional como académico, para aborda problemas reales, siendo capaz de diseñar algoritmos eficientes desde un punto de vista computacional que resuelvan dichos problemas
• Esto se consigue de dos maneras: en primer lugar el alumno desarrolla unos amplios conocimientos de las distintas técnicas de diseño de algoritmos junto con métodos para el análisis de los mismos. En segundo lugar, plasma estos conocimientos mediante de la implementación de diferentes problemas haciendo uso de un lenguaje de programación, el cual ya ha aprendido en otras asignaturas que se han cursado anteriormente o se están

•  Es recomendable para su correcto y completo seguimiento que el alumno haya cursado previamente las siguientes asignaturas:
• • Metodología y Tecnología de la Programación I
  • Metodología y Tecnología de la Programación II
  • Estructura de Datos y de la Información I
• El alumno debe estudiar la asignatura consultando la bibliografía sugerida por el profesor y asistir con regularidad a las tutorías y seminarios impartidos
• Debido al carácter práctico de la asignatura, se recomienda que los alumnos realicen la mayor parte de los ejercicios propuestos en clase y en las relaciones de problemas

Se propone un doble objetivo para esta asignatura:

• En primer lugar, que el alumno conozca, tras cursar esta asignatura, las principales técnicas de diseño de algoritmos, siendo capaz no sólo de aplicarlas para la resolución  de problemas concretos, sino de razonar sobre su aplicabilidad y adecuación
• En segundo lugar, el alumno ha de alcanzar los conocimientos adecuados en el estudio de complejidad algorítmica que le permitan, con un nivel suficiente de formalización, analizar los algoritmos construidos, razonar sobre su eficiencia, y poder compararlos

Tema 1: Introducción. Análisis de eficiencia de algoritmos

Tema 2: Algoritmos Divide y Vencerás 

Tema 3: Algoritmos Voraces (Greedy)

Tema 4: Algoritmos basados en Programación Dinámica

Tema 5: Algoritmos para la Exploración de Grafos

Tema 6: Algoritmos Probabilísticos

• Exámenes teórico y práctico

     Habrá un examen final teórico que supondrá el 80% de la nota final de la asignatura. Estará compuesto por tres tipos de preguntas:

• Tipo test, con opciones múltiples
• Preguntas de razonamiento corto
• Problemas

     El otro 20% de la calificación final corresponderá a la obtenida en un examen de prácticas que se realizará a continuación del de teoría en un laboratorio de informática. Se planteará un determinado problema y el alumno deberá resolverlo utilizando el lenguaje de programación que desee.

Tema I: Introducción. Análisis de Eficiencia

·       Introducción. Problemas y Casos

·       Notación asintótica

·       Análisis de los casos peor y promedio

·       Operaciones elementales

·       Eficiencia de Algoritmos Iterativos

·       Eficiencia de Algoritmos Recursivos:

•      Obtención de la función de tiempos de un algoritmo recursivo
•      Resolución de recurrencias

  Tema II: Divide y Vencerás

·       Introducción

·       Calculo del umbral

·       Búsqueda Binaria

·       Algoritmos de Ordenación : Mergesort y Quicksort

·       Aritmética de Enteros Grandes

o      Multiplicación y Exponenciación discreta

·       Problemas con Matrices

o      Multiplicación (Algoritmo de Strassen) y Traspuesta de una matriz

·       Problemas con Vectores

o      Búsqueda del mayor y el menor elemento de un vector

Tema I II : Algoritmos Voraces

·       Introducción. Elementos del enfoque voraz

·       El problema de la selección de actividades

·       El problema del cambio de monedas

·       Problemas con Grafos

o      Árbol Generador Minimal (Algoritmos de Kruskal y de Prim)

o      Camino mínimo (Algoritmo de Dijkstra)

·       Heurísticas Voraces

o      El problema de la mochila

o      El problema del viajante de comercio

o      El problema del coloreado de un grafo

Tema IV : Algoritmos Basados en Programación Dinámica

·       Introducción

·       La Memorización. Un ejemplo sencillo

·       Elementos de la Programación Dinámica:

o      El principio de optimalidad de Bellman

o      Definición recursiva de la solución óptima

o      Enfoque ascendente

o      Construcción de la solución óptima

·       El Problema de la Mochila

·       Problemas con Grafos

o      Camino de coste mínimo en un grafo multietapa

o      El problema de los caminos mínimos (Algoritmo de Floyd)

o      El problema del viajante de comercio 

Tema V: Algoritmos para la Exploración de Grafos

·       Introducción. Árboles de exploración

·       La Técnica de la Vuelta Atrás (Backtracking)

o      El problema de las ocho reinas

o      El problema de la mochila

o      Otros problemas: Laberinto, Salto del caballo y Sudoku

·       La Técnica de la Ramificación y Poda (Branch & Bound)

o      El problema de la asignación de tareas

o      El problema del viajante de comercio

Tema VI: Algoritmos Probabilísticos

·       Introducción

·       Generadores de Números Aleatorios

·       Algoritmos Numéricos

o      Cálculo del número Ï€

o      Integración numérica

·       Algoritmos MonteCarlo

o      Test de primalidad MonteCarlo

o      Elemento mayoritario de un array

o      Comparación de series de multiplicación de matrices

·       Algoritmos Las Vegas

o         El problema de las ocho reinas

• Tutorías
• Realización de exámenes