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