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