Asignatura:          Ampliación de Programación

Titulación/es:           Ingeniería Informática.

         Ingeniería Técnica en Informática de Sistemas.

                           Ingeniería Técnica en Informática de Gestión.

Créditos:                     9

Carácter:                     Obligatoria

Curso:                         2º

Temporalidad:            Cuatrimestral (Segundo Cuatrimestre)

Departamento:         Informática

Profesores:          Javier de la Mata Mora.

Félix Óscar García Rubio.

Miguel Ángel Redondo Duque.

Julián Ruiz Fernández (coordinador)

Manuel Ángel Serrano Martín.

        

 

Prerrequisitos:         Metodología y Tecnología de la Programación (1º)

                           Lógica (1º)

                           Álgebra y Matemáticas Discretas (1º)

                           Cálculo (1º)

 

Correquisitos:         Estructuras de Datos y de la Información (2º)

                           Estadística (2º)

 

Objetivos:

 

Mostrar al alumno las distintas técnicas para la construcción correcta y eficiente de programas, y familiarizarlo con distintas técnicas fundamentales en Programación. Para lo cual se estructura la asignatura en las tres partes que más abajo se detallan.

En la Primera Parte, Eficiencia de los Programas, nos ocupamos de los recursos computacionales que necesita un algoritmo dado. En la Segunda Parte, con Esquemas Algorítmicos Fundamentales, vemos los esquemas a los que se adaptan gran parte de los problemas que se plantean en programación. Finalmente, en la Tercera Parte, Construcción y Verificación de Programas, estudiamos la verificación y derivación formal de programas, tanto recursivos como iterativos, haciéndo hincapié en su corrección y eficiencia.

Docencia:

 

4 horas semanales de teoría y problemas.

2 horas semanales de prácticas de laboratorio.

 

Evaluación:

 

Se realizará un examen final de la asignatura que constará de una parte relativa a las prácticas de laboratorio y otra de teoría y problemas, debiendo aprobar ambas por separado para superar la asignatura.

I.         Eficiencia de los Programas

1.         Análisis de Algoritmos.        

1.1.         Introducción.        

1.2.         Eficiencia de algoritmos.        

1.3.         Complejidad en tiempo y en espacio.        

1.4.         Complejidad en los casos mejor, medio y peor.        

1.5.         Tamaño de un problema. Funciones y órdenes de complejidad. Problemas Tratables e Intratables.        

1.6.         Medidas Asintóticas.        

1.7.         Análisis de algoritmos.        

1.7.1.     Análisis de las Estructuras de Control

1.7.2.     Resolución de Recurrencias.

1.7.3. Ejemplos.

II.         Esquemas Algorítmicos Fundamentales        

2.         Algoritmos "Divide y vencerás".        

2.1.         Descripción del método general.        

2.2.         Ejemplos.        

2.3.         Quicksort (ordenación por bipartición).        

2.4.         Mergesort (ordenación por mezcla).        

2.5.         Selección de los K elementos menores de un vector.        

3.         Algoritmos Voraces.        

3.1.         Descripción del método general.        

3.2.         Ejemplos.        

3.3.         El problema de la mochila (versión general).        

3.4.         Programas almacenados en una cinta.        

3.5.         Camino mínimo en un grafo desde un nodo fijo.        

3.6.         El árbol generador mínimo: Algoritmos de Kruskal y de Prim.        

3.7.         Algoritmo de Huffman para el árbol de expansión mínimo.        

3.8.         Estrategias heurísticas voraces: Ejemplos.        

4.         Programación Dinámica.        

4.1.         El Principio de Optimalidad de Bellman.        

4.2.         Descripción del método general. Planteamientos hacia adelante y hacia atrás.

4.3.         Ejemplos.        

4.4.         Camino mínimo en un grafo multietápico.        

4.5.         Distancia mínima entre todos los pares de vértices de un grafo.        

4.6.         Problema de la mochila (versión 0/1).        

4.7.         Problema del viajante.

4.8.         Problema de inversiones.

4.9.         Funciones con Memoria.

5.         Backtracking (Vuelta atrás).        

5.1.         El método general.        

5.2.         Representación del árbol de resolución de un problema. Nodos solución y nodos problema.        

5.3.         Implementaciones recursiva e iterativa.        

5.4.         Ejemplos.        

5.5.         Problema de las n reinas.        

5.6.         Subconjuntos con suma igual a un valor dado.        

5.7.         Problema de los cuatro colores.        

5.8.         Backtracking en problemas de optimización.        

5.9.         Problema de la mochila (versión 0/1).        

5.10.         Subconjunto de menor cardinal con suma igual a un valor dado.        

5.11.         El problema de la devolución del cambio.        

6.         Ramifica y Poda.        

6.1.         El método general.        

6.2.         Exploración de un árbol mediante expansión de sus nodos.        

6.3.         Cotas heurísticas: inferior y superior.        

6.4.         Arboles de juegos: Algoritmo minimax.        

7.         Algoritmos Probabilistas.        

7.1.         Consideraciones Generales.        

7.2.         Clasificación de los Algoritmos Probabilistas.        

7.3.         Algoritmos Probabilistas Numéricos.        

7.4.         Algoritmos Probabilistas de Monte Carlo.        

7.5.         Algoritmos Probabilistas de Las Vegas.

III.         construcción y verificación de programas

8.          Especificación de Problemas

8.1.         Introducción.

8.2.         Lógica de Predicados.

8.3.         Especificación de Predicados.

9.          Diseño Recursivo

9.1.         Conceptos Básicos.

9.2.         Principio de Inducción.

9.3.         Diseño y Verificación de Programas Recursivos.

9.4.         Técnicas de Inmersión.

9.5.         Técnica de Plegado y Desplegado.

9.6.         Transformación de Recursivo a Iterativo.

10.          Diseño Iterativo

10.1.         Semántica de un Lenguaje Imperativo.

10.2.         Verificación a posteriori.

10.3.         Derivación Formal de Programas Iterativos.

10.4.         Recursión en Programas Imperativos.

Bibliografía básica.

BRASSARD, G., BRATLEY, P. Fundamentos de Algorítmica. Prentice Hall, 1997. ISBN 84-89660-00-X

HOROWITZ, E., SAHNI, S., RAJASEKARAN, S. Computer Algorithms/C++. Computer Science Press, 1997. ISBN 0-7167-8315-0

PEÑA, R. Diseño de Programas. Formalismo y Abstracción. Prentice Hall, 1997. ISBN 84-8322-003-2

BALCÁZAR, J.L. Programación Metódica. McGraw Hill, 1993.  ISBN 84-481-1957-6

Bibliografía Complementaria.

BRASSARD, G., BRATLEY, P. Algorítmica: Concepción y Análisis. Masson, 1990. ISBN 84-311-0531-3

GUEREQUETA GARCÍA, R., VALLECILLO MORENO, A. Técnicas de Diseño de Algoritmos. Universidad de Málaga,1997. ISBN 84-7496-784-8

KNUTH, D.E. El Arte de Programar Ordenadores. Volumen I: Al­go­ritmos Fundamentales. Reverté, 1986. ISBN 84-291-2662-7.

KNUTH, D.E. El Arte de Programar Ordenadores. Volumen III: Cla­sificación y Búsqueda. Reverté, 1987. ISBN 84-291-2664-3

KNUTH, D.E. The Art of Computer Programming. 3ª Ed. Addison Wesley, cop. 1997-1998. Reimpresión de 2000. ISBN 0-201-89683-4 (v.1)  ISBN 0-201-89684-2 (v.2)

SKIENA, S. The Algorithm Design Manual. Springer Verlag, 1997. ISBN 0-387-94860-0