Epónimos relacionados con las matemáticas

La aproximación de Padé es la "mejor" aproximación de una función por una función racional de un orden dado. En virtud de esta técnica, la serie de potencias de la aproximación concuerda con la serie de potencias de la función que se aproxima. La técnica fue desarrollada por Henri Padé.

La aproximación de Padé, da una mejor aproximación de la función que truncar su serie de Taylor, y funciona incluso donde la serie de Taylor no es convergente. Por esta razón las aproximaciones de Padé se usan ampliamente en los cálculos de ordenadores. Han sido también aplicados a las aproximaciones diofantinas, aunque para resultados nítidos, típicamente son reemplazados por métodos en cierto sentido inspirados en la teoría de Padé.

Definición

Dada una función f y dos enteros m ≥ 0 y n ≥ 0, la aproximación de Padé de orden (m, n) es la función racional

${\displaystyle R(x)={\frac {p_{0}+p_{1}x+p_{2}x^{2}+\cdots +p_{m}x^{m}}{1+q_{1}x+q_{2}x^{2}+\cdots +q_{n}x^{n}}}}$

que concuerda con ${\displaystyle f(x)}$ en el máximo orden posible, lo que equivale a

${\displaystyle {\begin{array}{rcl}f(0)&=&R(0)\\f'(0)&=&R'(0)\\f''(0)&=&R''(0)\\&\vdots &\\f^{(m+n)}(0)&=&R^{(m+n)}(0)\end{array}}}$.

Equivalentemente, si ${\displaystyle R(x)}$ se expande en una serie de McLaurin (Serie de Taylor en 0), sus primeros m + n términos cancelarían los primeros m + n términos de ${\displaystyle f(x)}$, y como tal

${\displaystyle f(x)-R(x)=c_{m+n+1}x^{m+n+1}+c_{m+n+2}x^{m+n+2}+\cdots }$

La Aproximación de Padé es única para determinadas m y n, es decir, los coeficientes ${\displaystyle p_{0},p_{1},\dots ,p_{m},}$ ${\displaystyle q_{1},\dots ,q_{n}}$, pueden ser determinados únicos. es por razones de esta singularidad que el término de orden cero del denominador de ${\displaystyle R(x)}$ fue elegido para ser 1, de otra manera, el numerador y denominador de ${\displaystyle R(x)}$ habría sido único sólo multiplicando por una constante.

La Aproximación de Padé definida arriba es denotada también por

${\displaystyle [m/n]_{f}(x).\,}$

Para una ${\displaystyle x}$ dada, la Aproximación de Padé puede ser calculada por el Algoritmo Épsilon y también por otras secuencias de transformaciones de sus sumas parciales

${\displaystyle s_{n}(x)=c_{0}+c_{1}x+c_{2}x^{2}+\cdots +c_{n}x^{n}}$

de la Serie de Taylor de ${\displaystyle f}$, es decir, tenemos

${\displaystyle c_{k}={\frac {f^{(k)}(0)}{k!}}.}$

Cabe denotar que ${\displaystyle f}$ también puede ser una serie formal de potencias y, por lo tanto, la Aproximación e Padé puede ser aplicada también a la sumatoria de series divergentes.

Función zeta de Riemman - Padé

Para estudiar la sumatoria de una Serie divergente, por ejemplo

${\displaystyle \sum _{z=1}^{\infty }f(z),}$

puede ser útil introducir la función simple racional de Padé

${\displaystyle \zeta _{R}(s)=\sum _{z=1}^{\infty }{\frac {R(z)}{z^{s}}},}$

donde

${\displaystyle R(x)=[m/n]_{f}(x),\,}$

es sólo la aproximación de orden (m, n) de la función f(x). El valor de regularización zeta en s = 0 se toma como la suma de las series divergentes. La ecuación funcional para la función zeta de Padé es

${\displaystyle \sum _{j=0}^{n}p_{j}\zeta _{R}(s-j)=\sum _{j=0}^{m}q_{j}\zeta _{0}(s-j),}$

donde ${\displaystyle p_{j}}$ y ${\displaystyle q_{j}}$ son los coeficientes en la aproximación de Padén. El subíndice "0" significa que el Padé es del orden de [0 / 0] y por lo tanto, tenemos la función zeta de Riemann.

Una aproximación de Padé aproxima a una función en una variable. Un aproximación en dos variables se llama una aproximación de Chisholm, en múltiples variables aproximación de Canterbury (después de Graves-Morris en la Universidad de Kent).

árbol Cartesiano es un árbol binario que se deriva de una secuencia de números; se define únicamente a partir de que cumple con una ordenación a modo de montículo y de que un recorrido entre-orden del árbol retorna la secuencia original de números. Introducido por Vuillemin (1980) en el contexto de las estructuras de datos de búsqueda en rangos geométricos, los árboles Cartesianos también han sido utilizados en la definición del treap y árboles aleatorios binarios de búsqueda para problemas de búsqueda binaria. El árbol Cartesiano de una secuencia puede ser construido en tiempo lineal usando un algoritmo de pila para encontrar todos los menores valores más cercanos en una secuencia.

Una secuencia de números y el árbol cartesiano derivado de ellos.

Definición

Para una secuencia de números distintos, el árbol Cartesiano se puede definir únicamente a partir de las siguientes propiedades:

1. Para una secuencia, el árbol Cartesiano contiene un nodo para cada número de la secuencia. Cada nodo está asociado con un único número de la secuencia.
2. Un recorrido entre-orden del árbol resulta en la secuencia original. Esto significa que el subárbol izquierdo consiste de valores antecesores de la raíz en la secuencia, mientras que el subárbol derecho consiste de valores sucesores de la raíz en la secuencia. Estas restricciones se aplican para el resto de los nodos del árbol.
3. El árbol cumple con la propiedad del montículo: el padre de cualquier nodo, excepto la raíz, contiene un valor menor que el valor del nodo.¹

Basado en la propiedad del montículo, la raíz del árbol tiene que ser el menor número de la secuencia. A partir de esto, el árbol también se puede definir de forma recursiva: la raíz es el menor valor de la secuencia, y los subárboles izquierdo y derecho son árboles Cartesianos para las subsecuencias a la izquierda y a la derecha del valor de la raíz en la secuencia.

Si una secuencia contiene números repetidos, el árbol Cartesiano se puede definir determinando una regla de desempate (por ejemplo, determinando que el primer número repetido sea tratado como menor que su homólogo en la secuencia) antes de aplicar las propiedades anteriores.

Búsqueda en rango y menores ancestros comunes

Los árboles cartesianos se pueden usar como parte de una estructura de datos eficiente para consultas de rango mínimo, un problema de búsqueda en rango relacionado con consultas que buscan el menor valor de una subsecuencia contigua de la secuencia original.² En un árbol cartesiano, dicho menor valor se puede encontrar en el menor ancestro común de los valores más a la izquierda y más a la derecha en la subsecuencia. Por ejemplo, en la subsecuencia (12, 10, 20, 15) de la secuencia mostrada en la primera figura, el menor valor es (10) forma el menor ancestro común de los valores más a la izquierda y más a la derecha (12 y 15). Debido a que los menores ancestros comunes se pueden encontrar en un tiempo constante para cada consulta, usar una estructura de datos que utiliza un espacio lineal para almacenamiento y que se construye en tiempo lineal,³ implica obtener dichos tiempos para el problema de minimización en rangos.

Bender y Farach-Colton (2000) invirtieron esta relación entre las dos estructuras de datos demostrando que los menores ancestros comunes en un árbol de entrada se podían encontrar eficientemente aplicando una técnica de minimización en rangos que no se basa en árboles. Su estructura de datos usa una técnica del circuito euleriano para transformar el árbol de entrada en una secuencia. La secuencia resultante de esta transformación tiene una forma especial (números adyacentes, representantes de las alturas de nodos adyacentes en el árbol, difieren en ±1) de la cual ellos se aprovechan en su estructura de datos; para resolver problemas de minimización en rango en secuencias que tienen esta forma especial, ellos utilizan un árbol Cartesiano para transformar el problema de minimización en rango en un problema de menor ancestro común y entonces aplican la técnica del circuito euleriano para transformar el problema nuevamente a un problema de minimización de rango con esta forma especial.

El mismo problema de minimización también se puede interpretar de forma alternativa, en términos de búsqueda bidimensional en rango. Una colección finita de puntos en el plano Cartesiano se puede utilizar para formar un árbol Cartesiano, ordenando los puntos por su coordenada x y utilizando la coordenada y (en ese orden) para construir la secuencia de la cual se construye el árbol. Si S es el subconjunto de los puntos de entrada contenidos en una región definida por las desigualdades L ≤ x ≤ R, p es el punto más a la izquierda en S (cuya coordenada x es la menor) y q el punto más a la derecha en S (cuya coordenada x es la mayor) entonces el menor ancestro común de p y q en el árbol Cartesiano es el punto más inferior en la región. Una consulta de rango delimitada por tres lados, en la cual el objetivo es listar todos los puntos contenidos en una región delimitada por tres desigualdades L ≤ x ≤ R and y ≤ T, se puede responder encontrando el punto más inferior b, comparando su coordenada y con T, y (si el punto se encuentra dentro de la región delimitada por los tres lados) continuando recursivamente en las regiones que se encuentran entre p y b y entre b y q. De esta forma, después de que los puntos más a la izquierda y más a la derecha en la región han sido encontrados, todos los puntos en la región delimitada por los tres lados se pueden listar en un tiempo constante para cada punto⁴

Esta misma construcción, de menores ancestros comunes en un árbol Cartesiano, hace posible construir una estructura de datos con espacio lineal que permite que las distancias entre pares de puntos en cualquier espacio ultra métrico sean consultadas en un tiempo constante para cada consulta. La distancia dentro de una ultra métrica es lo mismo que el peso de un camino minimax en el árbol abarcador de costo mínimo de la métrica.⁵ A partir del árbol abarcador de costo mínimo, se puede construir un árbol Cartesiano, del cual el nodo raíz representa la arista más de mayor costo del árbol abarcador de costo mínimo. Quitar esta arista particiona el árbol abarcador de costo mínimo en dos subárboles y los árboles Cartesianos construidos recursivamente para los dos subárboles forman los hijos del nodo raíz del árbol Cartesiano. Las hojas del árbol Cartesiano representan puntos en el espacio métrico, y el menor ancestro común de dos hojas es la arista más de mayor costo entre esos dos puntos en el árbol abarcador de costo mínimo, que tiene un costo igual a la distancia entre esos dos puntos. Una vez que el árbol abarcador de costo mínimo ha sido encontrado y los costos de sus aristas ordenados, el árbol Cartesiano puede ser construido en tiempo lineal.⁶

Treaps

Debido a que un árbol Cartesiano es un árbol binario, resulta natural utilizarlo como un árbol binario de búsqueda para una secuencia ordenada de valores. No obstante, definir un árbol Cartesiano basado en los mismos valores que forman las llaves de un árbol binario de búsqueda puede no funcionar bien: el árbol Cartesiano de una secuencia ordenada no es más que una rama, comenzando en el punto más a la izquierda y una búsqueda binaria en dicho árbol se degenera a una búsqueda secuencial en la rama. Sin embargo, es posible construir árboles de búsqueda más balanceados generando valores de prioridad para cada llave que son distintos de la llave, ordenando la entrada por el valor de las llaves y usando la secuencia correspondiente de prioridades para generar el árbol Cartesiano. Esto construcción puede ser vista de forma equivalente en el esquema geométrico descrito anteriormente, tomando las coordenadas x de un conjunto de puntos son las llaves de búsqueda y las coordenadas y son las prioridades.

Esta idea fue aplicada por Seidel y Aragon (1996), quienes sugirieron el uso de números aleatorios como prioridades. La estructura de datos resultante de esta selección aleatorio es denominada treap , debido a la combinación de las características del árbol binario de búsqueda (en inglés binary search tree) y el montículo binario (en inglés binary heap). Una inserción en un treap se realiza insertando la nueva llave como una hoja de un árbol existente, eligiendo una prioridad para dicha hoja y realizando operaciones de rotación en el camino desde la hoja hasta la raíz para reparar cualquier violación de la propiedad del montículo causadas por la inserción del nuevo nodo; la eliminación se realiza de forma similar, con una número constante de cambios en el árbol seguidos por una secuencia de rotaciones sobre un único camino en el árbol.

Si las prioridades de cada llave se eligen de forma aleatoria e independiente cuando la llave se inserta en el árbol, entonces el árbol Cartesiano resultante tendrá las mismas propiedades que un árbol aleatorio binario de búsqueda, que no es más que un árbol binario computado mediante la inserción de llaves en una permutación escogida aleatoriamente. Dicho árbol comienza con un árbol vacío, y con cada inserción se deja la estructura del árbol anterior intacta y se inserta el nuevo nodo como una hoja del árbol. Los árboles aleatorios binarios de búsqueda han sido estudiados por mucho tiempo, y se conoce que presentan un buen comportamiento como árboles de búsqueda (tiene profundidad logarítmica con una alta probabilidad); el mismo buen comportamiento se lleva a los treaps. También es posible, como sugieren Aragon y Seidel, re-priorizar nodos accedidos frecuentemente, causando que se muevan hacia la raíz y acelerando futuros accesos con las mismas llaves.

Construcción eficiente

Un árbol Cartesiano puede ser construido en tiempo lineal a partir de la secuencia de entrada. Un método es procesar los valores de izquierda a derecha, manteniendo el árbol Cartesiano de los nodos procesados hasta el momento en una estructura que permite los recorridos hacia abajo y hacia arriba del árbol. Para procesar cada valor nuevo x, se comienza en el nodo que representa el valor anterior a x en la secuencia y se continua en el camino desde este nodo hasta la raíz hasta encontrar un valor y que sea menor que x. Este nodo y es el padre de x, y el antiguo hijo derecho de y pasa a ser el nuevo hijo izquierdo de x. El tiempo total para este procedimiento es lineal, ya que el tiempo que se emplea buscando por el padre y de cada nodo x se puede sobrecargar contra el número de nodos que se eliminan del camino en la extrema derecha del árbol.⁴

Una construcción alternativa de tiempo lineal se basa en el problema de los todos los valores cercanos más pequeños. En la secuencia de entrada, se puede definir el vecino izquierdo de un valor x como el valor que ocurre anterior a x, que es menor que x y cuya posición es la más cercana a x que cualquier otro valor menor que x. El vecino derecho se define de forma simétrica. La secuencia de los vecinos izquierdos de x se puede encontrar mediante un algoritmo que mantiene una pila que contiene una subsecuencia de la entrada. Para cada valor nuevo x de la secuencia, la pila se va reduciendo mediante la operación de desapilar (pop en inglés) hasta que la pila esté vacía o el elemento en la cima de la pila sea menor que x, y luego se apila dicho elemento. El vecino izquierdo de x es el elemento que estaba en el la cima de la pila en el momento en que se insertó x. El vecino derecho se puede encontrar aplicando el mismo algoritmo de pila a la secuencia inversa. El padre de x en el árbol Cartesiano es el vecino izquierdo o el vecino derecho de x. Los vecinos izquierdo y derecho de x también pueden ser encontrados eficientemente mediante algoritmos paralelos, por lo que esta formulación puede ser utilizada para desarrollar algoritmos paralelos eficientes para la construcción de árboles Cart⁷

Aplicación en la ordenación.

Levcopoulos y Petersson (1989) describen un algoritmo de ordenación basado en árboles Cartesianos. Ellos describen el algoritmo como basado en un árbol cuyo máximo está en la raíz, pero puede ser modificado para soportar árboles Cartesianos con la convención de que el menor valor está en la raíz. Por consistencia, el algoritmo descrito a continuación incluye dicha modificación.

El algoritmo Levcopoulos–Petersson puede ser visto como una versión del ordenamiento por selección o el ordenamiento por montículos que mantiene una cola con prioridad de los candidatos a mínimo, y que en cada paso encuentra y elimina el mínimo de dicha cola, llevándolo al final de la secuencia de salida. En su algoritmo, la cola con prioridad consiste solo de elementos cuyos padres en el árbol Cartesiano han sido encontrados y eliminados. El algoritmo consiste de los siguientes pasos:

1. Construir el árbol Cartesiano a partir de la secuencia de entrada.
2. Inicializar la cola con prioridad, que contiene inicialmente la raíz del árbol.
3. Mientras que la cola no esté vacía:
   • Encontrar y eliminar el mínimo valor x de la cola.
   • Agregar x a la secuencia de salida.
   • Agregar los hijos de x en el árbol cartesiano a la cola con prioridad.

Como Levcopoulos and Petersson demuestran, para secuencias de entradas que estén casi ordenadas, el tamaño de la cola con prioridad se mantendrá pequeño, permitiendo a este método aprovechar el hecho de que la secuencia de entrada está casi ordenada y ejecutarse de manera más rápida. En específico, el peor tiempo de ejecución para este algoritmo es O(n log k), donde k es el promedio, para todos los valores x de la secuencia, del número de pares consecutivos de valores de la secuencia que encierran a x. Ellos también demuestran una cota inferior enunciando que, para cualquier n y k = ω(1), cualquier algoritmo de ordenación basado en comparaciones debe utilizar Ω(n log k) comparaciones para algunas entradas.

Historia

Los árboles Cartesianos fueron introducidos y nombrados por Vuillemin (1980). El nombre se deriva del sistema de coordenadas Cartesianas para el plano: en la versión de Vuillemin (1980) de esta estructura, un árbol Cartesiano para un conjunto de puntos contiene la ordenación de los puntos por sus coordenadas x en el recorrido en orden simétrico y contiene la propiedad del montículo de acuerdo a las coordenadas y de los puntos. Gabow, Bentley y Tarjan (1984) y los autores subsecuentes seguidos en la definición mostrada aquí, en la cual el árbol Cartesiano se define a partir de una secuencia. Este cambio generaliza el enfoque geométrico de Vuillemin para permitir otras secuencias además de las coordenadas x ordenadas, y permite también al árbol Cartesiano ser aplicado a problemas no geométricos.

El árbol de Steiner, nombrado en honor a Jakob Steiner, es un problema de optimización combinatoria consistente en buscar la interconexión más corta para un conjunto de elementos dado. Es superficialmente similar al problema del árbol recubridor mínimo: dado un conjunto V de puntos (vértices), interconectalos por la red gráfica de menor longitud, donde la longitud es la suma de las medidas de todos los lados.

La diferencia entre el problema del árbol de Steiner y el del árbol recubridor es que, en el primero se pueden añadir vértices intermedios y lados extras al grafo con el fin de reducir la longitud del árbol recubridor. Los vértices introducidos para decrecer la longitud total de las conexiones son conocidos como puntos de Steiner. Ha sido demostrado que la conexión resultante es un árbol, llamado árbol de Steiner. Pueden existir varios árboles de Steiner para un conjunto dado de vértices iniciales.

El árbol de Steiner tiene aplicaciones en el diseño de circuitos eléctricos y redes de telecomunicaciones. La mayoría de las versiones del problema de Steiner son NP-completo. De hecho uno de estos pertenece a la lista de 21 problemas NP-completos de Karp. Algunos casos restringidos pueden ser resueltos por tiempo polinómico, sin embargo en la práctica se usa la heurística en su lugar.

Definición

Dado un grafo ${\displaystyle G=(V,E)}$, un subconjunto de vértices ${\displaystyle S\subset V}$, una función de pesos ${\displaystyle f:E\rightarrow \mathbb {Z} }$; minimizar el costo del árbol que conecta todos los elementos de ${\displaystyle S}$.

Árbol de Steiner para tres puntos A, B y C. Nótese que no hay conexiones directas entre ellos. El punto de Steiner S está puesto en el punto de Fermat del triángulo ABC.