Universidad Central del Ecuador

Algoritmos

Título: MONTÍCULOS Y
PROGRAMACIÓN DINÁMICA

INTEGRANTES:
 SUNTAXI CRISTIAN
 VAQUILEMA LUIS
 VELA SAUL
 Algoritmos
MONTÍCULOS
Es un tipo especial de Árbol con información de un conjunto ordenado que se implementan

sobre vectores. Su característica principal es que cada nodo tiene un valor mayor o igual que el

de todos sus nodos hijos.

El orden de los nodos hermanos en un montículo no está especificado en la propiedad de

montículo, de manera que los subárboles de un nodo son intercambiables. (Demonics, Tic

en la UNED (2016))

El montículo nos permite:

 Ordenar elementos de un vector de forma fácil y óptima, pudiendo implementar

un comparador a medida.
Universidad Central del Ecuador
 Búsquedas el máximo, mínimos, o cualquier otro factor a tener en cuenta en la

selección de búsqueda de elementos.

 En problemas específicos de grafos como el recubrimiento mínimo de Prim o el

camino más corto de Dijkstra. (Nullxor, (2016))

Operaciones Básicas de los Montículos:

 Add(item) Inserta un ítem en el montículo y lo reordena.

 GetTop() – Regresa el ítem del tope (El mayor o menor).

 RemoveTop() – Elimina un ítem del tope (El mayor o menor según sea el caso) y

lo retorna.

2
 Algoritmos
 Heapify(array, from)  - Mantiene la propiedad del montículo (Mayor o menor

item en el tope).

 Left(rootIndex) – Calcula el índice del hijo izquierdo a partir del índice del

padre 

 (rootIndex * 2) + 1

 Right(rootIndex) – Calcula el índice del hijo derecho a partir del índice del padre

 (rootIndex * 2) + 2

 Root(rootIndex) – Calcula el índice del padre a partir del hijo (izquierdo o

derecho)

 (rootIndex – 1) / 2

Universidad Central del Ecuador

Las ultimas 3 formulas son para arrays con índice base 0. (Nullxor, (2016).)

La estructura de datos para implementar el montículo consta de un registro con tres

elementos:

 Un vector T [1.n].

 Un contador e para el número de elementos del montículo.

 Un valor para el tamaño máximo del montículo.

Documentación en java (Método de ordenamiento)

Método de montículos (Heap Sort)

2
 Algoritmos
El algoritmo de ordenación por montículos o Heap Sort recorre el conjunto de elementos

desde la posición de la mitad hasta la primera organizando el montículo correspondiente a

dicho elemento.  Una vez terminado este proceso, se inicia el proceso de ordenación

intercambiando el primer elemento por el último del arreglo y reorganizando el montículo

a partir de la primera posición.

La complejidad del algoritmo de ordenación por montículos es O (n log n) teniendo en

cuenta que el proceso de organizar el montículo en el peor caso solamente tiene que hacer

intercambios sobre una sola línea de elementos desde la raíz del árbol hasta alguna de las

hojas para un máximo de log n intercambios. (JorgeP, (2010))

El montículo cuenta con las siguientes operaciones básicas:

Universidad Central del Ecuador

 CreaMonticuloVacio: devuelve un montículo vacío.

 MonticuloVacio: devuelve cierto si el montículo está vacío.

 Flotar: reubica el elemento i-esimo del vector en caso de que este sea mayor que

el padre (montículo de máximos).

 Hundir: reubica el elemento i-esimo del vector en caso de que éste sea menor que

alguno de sus hijos. En tal caso, intercambia su valor por el del mayor de sus hijos

(montículo de máximos).

 Insertar: inserta un elemento en el montículo y lo flota hasta restaurar la

propiedad de montículo. (Demonics, Tic en la UNED (2016))

 Primero: devuelve la cima del montículo sin modificarlo.

2
 Algoritmos
 ObtenerCima: devuelve la cima del montículo, la elimina del mismo y

recompone la propiedad de montículo.

Programación Dinámica

“Es una secuencia de decisiones óptima toda subsecuencia ha de ser también óptima”.
(Bellman en 1957)

La programación dinámica, en esta época actual es asociada a un paradigma de

programación informático, puesto que claramente se puede trabajar con ella, pero su

origen es antaño, puesto que la programación dinámica nace con la computación y es una

herramienta matemática que nace de la necesidad de solucionar problemas

Universidad Central del Ecuador
principalmente de optimización que tiene una secuencia o etapas para su resolución y en

cada etapa tiene que ver los resultados de la anterior.

Tomando en cuenta la eficiencia de la programación dinámica, se ve claramente que es

parte de la técnica de diseño de algoritmos “Divide y Vencerás”, a su vez, La

programación dinámica construye los procesos de algoritmos recursivos.

Técnica matemática orientada a la solución de problemas con decisiones secuenciales en

etapas sucesivas donde se debe minimizar el coste total de dichas decisiones. En cada

etapa se valora no sólo el coste actual de tomar una decisión sino los costes futuros que se

originan a partir de ella.

Etapas: k

2
 Algoritmos
Decisiones en cada etapa: uk

Estados (situaciones en que puede encontrarse el sistema en cada etapa): xk

El número de estados puede ser finito o infinito. 1

En efecto, para el primero, su solución puede entenderse como el resultado de una

sucesión de decisiones. Tenemos que decidir los valores de x i, 1 ≤ i ≤ n. Así, primero

podríamos tomar una decisión sobre x 1, luego sobre x 2, etc. Una sucesión optimal de

decisiones, verificando las restricciones del problema, será la que maximice la

correspondiente función objetivo. En el caso del camino mínimo, una forma de encontrar

ese camino mínimo desde un vértice i a otro j en un grafo dirigido G, es decidiendo que

vértice debe ser el segundo, cual el tercero, cual el cuarto, etc. hasta que alcanzáramos el

vértice j. Una sucesión optimal de decisiones proporcionaría entonces el camino de

longitud mínima que buscamos.2

Universidad Central del Ecuador
Principio de optimalidad de la DP o de Bellman

Dado un estado, la política óptima para las siguientes etapas no depende de la política

tomada en las etapas anteriores.

La decisión de óptima inmediata sólo depende del estado en el que se está, no de cómo se

llegó hasta él.

Toda la información sobre el pasado se resume en el estado en que se encuentra.

Una vez conocida la solución óptima global, cualquier solución parcial que involucre sólo

una parte de las etapas es también una solución óptima.

1
Universidad Politécnica de Comillas (Ramos Andrés, 2011)
2
Guerequeta y Vallecilla 1998

2
 Algoritmos
Todo subconjunto de una solución óptima es a su vez una solución óptima para un

problema parcial.3

El nombre Programación Dinámica y la metodología que subyace en él lo ha tomado la

Teoría de Algoritmos de la Teoría de Control, donde la Programación Dinámica es una

técnica para obtener la política optima en problemas de control con n etapas,

caracterizando está en términos de la política óptima para un problema similar, pero con

n-1 etapas. Por este motivo comenzamos nuestra exposición analizando el método de la

Programación Dinámica en su contexto original, para pasar después a su formulación

dentro de la Teoría de Algoritmos.

El Lugar de la Programación Dinámica

El problema más importante en la Teoría de Control es el del control optimal. Un típico

Universidad Central del Ecuador
proceso supone en este contexto cuatro tipos de variables,

1. Variables independientes, que son las variables manipulables para el control del

proceso.

2. Variables dependientes, que sirven para medir y describir el estado del proceso en

cualquier instante de tiempo.

3. Variables producto, que se usan para indicar y medir la calidad de la tarea que realiza

el sistema de control, y

4. Ruidos, que son variables incontrolables que dependen del ambiente en el que el

sistema lleve a cabo su operación.

3
Universidad Politécnica de Comillas (Ramos Andrés, 21011)

2
 Algoritmos
El problema general del control optimal de un proceso consiste en determinar la forma en

que las variables producto pueden mantenerse en valores optimales, independientemente

de las fluctuaciones que los ruidos, o los cambios de parámetros, puedan causar. Las

variables producto se usan para describir el índice de eficacia del control del sistema. Así

el problema del control óptimo supone la optimización (maximización o minimización)

de ese índice de eficacia.

Generalmente, un sistema físico de n-esimo orden puede describirse en cualquier instante

de tiempo t por medio de un conjunto finito de cantidades (x 1 (t), x 2 (t), x n (t)). Estas

cantidades se conocen como las variables de estado del sistema, y constituyen las

componentes del vector de estado del sistema: x(t). La relación entre los cambios del

parámetro tiempo y las variables de estado del sistema, se establece mediante una sencilla

Universidad Central
y útil hipótesis como es que ladel Ecuador
derivada del vector de estado, dx/dt, solo dependa del

estado del sistema en curso y no de su historia anterior. Esta hipótesis básica lleva a una

caracterización matemática del proceso por medio de una ecuación diferencial vectorial,

dx(t)/dt = f[x(t), m(t), t] con la condición inicial x (0) = x 0.

En esa ecuación m(t) nota el vector de control, y f es una función vectorial de las

variables de estado, las señales de control, el tiempo y, posiblemente, las variables

ambientales o ruidos externos. En cada instante, el vector de control m debe satisfacer la

condición, g(m) ≤ 0 que refleja las restricciones que el control del sistema tenga. La

función g es una función conocida de la señal de control. Entonces, el problema del

diseño de un control optimal puede plantearse en los siguientes términos: Dado un

proceso que debemos controlar, determinar la ley de control, o sucesión, tal que el

2
 Algoritmos
conjunto de índices de eficacia, previamente fijado, sea óptimo. A veces, las variables de

estado de un sistema son todas accesibles para medirlas y observarlas. Para los sistemas

lineales que tienen esta característica, aun en presencia de ruido, puede tratarse

directamente de determinar la ley de control optimal como una función de las variables

de estado. Sin embargo, es bastante frecuente que las variables de estado no sean todas

accesibles para medirlas y observarlas. Entonces, la ley de control optimal se determina

como una función de las mejores estimaciones de las variables de estado, que se calculan

a partir de las señales de salida del sistema que se hayan medido. Por tanto, en el caso

más general, tendremos que considerar la resolución de problemas de control optimal y

de estimación optimal.

La Teoría de Control parte de la caracterización de un sistema mediante sus variables de

Universidad Central
estado y del diseño del sistemadel Ecuador
por medio de técnicas basadas en su representación como

espacio de estados. En una formulación general, el diseño del control optimal se ve

generalmente como un problema variacional. Pero hay muchos métodos variacionales

para optimizar un funcional sobre un espacio de funciones. El rango de tales métodos va

desde los métodos clásicos del cálculo de variaciones, a las técnicas numéricas de

aproximaciones sucesivas de modelos experimentales. Entre los métodos más

frecuentemente usados para el diseño de sistemas de control están,

1.- El Cálculo de Variaciones,

2.- El Principio de Máximo de Pontryaguin, y

3.- La Programación Dinámica.

En todos los casos, el propósito es encontrar la ley de control optimal tal que dado el

funcional del índice de eficacia del sistema, lo optimice. Pero es muy significativo que

2
 Algoritmos
los tres métodos tienen en común el uso de principios variacionales: Cada uno de estos

tres métodos está íntimamente ligado a alguna formulación bien conocida de la Mecánica

clásica. Los primeros, con la ecuación de Euler-Lagrange, los segundos con el Principio

de Hamilton y los terceros con la teoría de Hamilton-Jacobi. Particularmente, el Principio

de Máximo de Pontryaguin emplea procedimientos, más o menos directos, del cálculo de

variaciones, mientras que la Programación Dinámica (PD), aun basándose en principios

variacionales, usa relaciones de recurrencia.

La PD la desarrolló Richard E. Bellman y es una técnica simple, pero poderosa, que se ha

demostrado muy útil para la resolución de problemas de decisión multietápicos. La idea

fundamental que subyace en el método de la PD es el principio del invariante encajado,

según el cual un problema difícil de resolver, esta encajado en una clase de problemas

Universidad
más simples Central del
de resolver, lo que Ecuador
permite encontrar una solución al problema original.

Naturalmente, el objetivo de este tema es el estudio del uso de la PD para el diseño de

algoritmos que resuelvan eficientemente problemas por lo que, una vez que la hemos

colocado en un lugar de referencias exacto, a continuación, nos centramos en ella.

Comenzaremos por introducir los procesos de decisión multietápicos estudiándolos desde

el punto de vista del diseño de su control optimal para, después, presentar el Principio de

Optimalidad de Bellman y emplearlo para el diseño de algoritmos que, basados en el,

resuelven algunos problemas notables en las Ciencias de la Computación.

Bibliografía

Guerequeta, R., & Vallecillo, A. (1998). Técnicas de Diseño de Algoritmos. Málaga:

Servicio de Publicaciones de la Universidad de Málaga.

2
 Algoritmos
Ramos, A. (2011). Programación Dinámica (DP). Madrid: Universidad Politécnica de
Comillas.

Verdegay, J. L. (2008). Algoritmos y Programación. Granada: Publicaciones Universidad

de Granada.

Demonics, Tic en la UNED (2016)blogs: Aprende Y Programa Programación y Estructura de Datos

Avanzada.https://aprendeyprogramablog.wordpress.com/2016/10/19/monticulos

Nullxor, (2016). Program,ación y otros trucos de

magia,programagic.http://programagic.blogspot.com/2016/11/heaps-monticulos.html

JorgeP,(2010).Algoritmos y Programacion, Apuntes de Algoritmo y

Programacion.http://jorgep.blogspot.com/2010/09/ordenacion-por-monticulos-heap-sort.html

Universidad Central del Ecuador

Firmas integrantes