Optimización del orden de evaluación de programas recursivos

A través de los años los científicos de la computación han identificado diversas técnicas (estrategias) generales que a menudo producen algoritmos eficientes para la resolución de muchas clases de problemas. Este trabajo presenta un análisis de la estrategia dynamic programming (programación dinámic...

Descripción completa

Guardado en:

Detalles Bibliográficos
Autores principales:	Luna, Carlos Daniel, Baum, Gabriel Alfredo
Formato:	Objeto de conferencia
Lenguaje:	Español
Publicado:	1998
Materias:	Ciencias Informáticas Informática Estrategias de Diseño de Algoritmos: Programación Dinámica Algorithms Optimization Divide and Conquer Especificación y Transformación de Programas Optimización de Programas Recursivos Análisis de Algoritmos
Acceso en línea:	http://sedici.unlp.edu.ar/handle/10915/24893
Aporte de:	SEDICI (UNLP) de Universidad Nacional de La Plata

id	I19-R120-10915-24893
record_format	dspace
institution	Universidad Nacional de La Plata
institution_str	I-19
repository_str	R-120
collection	SEDICI (UNLP)
language	Español
topic	Ciencias Informáticas Informática Estrategias de Diseño de Algoritmos: Programación Dinámica Algorithms Optimization Divide and Conquer Especificación y Transformación de Programas Optimización de Programas Recursivos Análisis de Algoritmos
spellingShingle	Ciencias Informáticas Informática Estrategias de Diseño de Algoritmos: Programación Dinámica Algorithms Optimization Divide and Conquer Especificación y Transformación de Programas Optimización de Programas Recursivos Análisis de Algoritmos Luna, Carlos Daniel Baum, Gabriel Alfredo Optimización del orden de evaluación de programas recursivos
topic_facet	Ciencias Informáticas Informática Estrategias de Diseño de Algoritmos: Programación Dinámica Algorithms Optimization Divide and Conquer Especificación y Transformación de Programas Optimización de Programas Recursivos Análisis de Algoritmos
description	A través de los años los científicos de la computación han identificado diversas técnicas (estrategias) generales que a menudo producen algoritmos eficientes para la resolución de muchas clases de problemas. Este trabajo presenta un análisis de la estrategia dynamic programming (programación dinámica), a partir de su formalización mediante una regla en el cálculo transformacional desarrollado en el proyecto CIP [Bauer, 85] [Bauer, 87]. La técnica especificada es utilizada en la optimización de programas recursivos ineficientes, derivados, en general, por razonamientos divide and conquer. A partir del análisis de la resolución de problemas sobre dominios de distinta complejidad, siguiendo un proceso sistemático y formal, se plantea una generalización de la estrategia programación dinámica formalizada que hace explícitas las condiciones del orden involucrado sobre el dominio de un problema. Asimismo, se formula una regla que combina la técnica de operacionalización divide and conquer recursivo [Grinspan, 95a] con la de optimización programación dinámica. Programación dinámica evita calcular subproblemas más de una vez, invirtiendo el orden computacional y eliminando recursiones no lineales. No obstante puede conducir a que se resuelvan subproblemas innecesarios en el cómputo de ciertos problemas. Esto provoca que tanto la complejidad en tiempo como en espacio de almacenamiento resulten mayores a las deseadas. Existe una técnica conocida como memorización [Turner, 81] (tabulación exacta [Bird, 80]) que evita, por un lado, recomputar valores y por el otro, computar valores innecesarios. Sin embargo memorización no elimina recursiones no lineales, complicándose luego este proceso en el contexto de una metodología de desarrollo de software transformacional. Este trabajo plantea una regla que combina las ventajas de ambas técnicas, a través de un refinamiento de programación dinámica, en función al orden involucrado sobre el dominio del problema. Técnicas y conceptos inherentes a la rama de análisis de algoritmos sirven de herramientas en la formalización y deducción de las condiciones necesarias para la utilización de las reglas propuestas. Asimismo, en la evaluación de los resultados obtenidos como consecuencia de un proceso de optimización. Dos casos de estudio siguen el desarrollo del artículo: “cálculo de números combinatorios” y “multiplicación eficiente de n matrices”. Éstos destacan la relevancia de cada una de estrategias –puras, generalizadas o combinadas– que se formalizan.
format	Objeto de conferencia Objeto de conferencia
author	Luna, Carlos Daniel Baum, Gabriel Alfredo
author_facet	Luna, Carlos Daniel Baum, Gabriel Alfredo
author_sort	Luna, Carlos Daniel
title	Optimización del orden de evaluación de programas recursivos
title_short	Optimización del orden de evaluación de programas recursivos
title_full	Optimización del orden de evaluación de programas recursivos
title_fullStr	Optimización del orden de evaluación de programas recursivos
title_full_unstemmed	Optimización del orden de evaluación de programas recursivos
title_sort	optimización del orden de evaluación de programas recursivos
publishDate	1998
url	http://sedici.unlp.edu.ar/handle/10915/24893
work_keys_str_mv	AT lunacarlosdaniel optimizaciondelordendeevaluaciondeprogramasrecursivos AT baumgabrielalfredo optimizaciondelordendeevaluaciondeprogramasrecursivos
bdutipo_str	Repositorios
_version_	1764820466523963395

Optimización del orden de evaluación de programas recursivos

Ejemplares similares