¿Existen aplicaciones de técnicas en análisis real a la informática teórica?

18

He buscado por todas partes tales aplicaciones y la mayoría de las veces me he quedado corto. Puedo encontrar muchas aplicaciones de topología y estructuras similares en conjuntos contables (o incontables), pero rara vez encuentro conjuntos incontables como objeto de estudio por parte de científicos informáticos y, por lo tanto, conducen a la necesidad de técnicas de análisis.

robinhoode
fuente
Según lo que dicen mis amigos, se necesita un análisis real en la teoría de la información. Sin embargo, si omites lo básico, no parece ser popular en tcs (al menos para mí).
singhsumit
¡La teoría de la información es suficiente para mí! Si puede obtener un ejemplo específico, marcaré su respuesta como la respuesta ..
robinhoode
1
También hay procesamiento de señales, gráficos y lo que tienes. ¿Qué tipo de técnicas estás buscando?
Shir
44
Un ejemplo (no estoy seguro si eso es lo que está buscando) de la teoría de la información: , que es la información mutua de dos variables aleatorias no es negativa. Esto se deduce directamente de la concavidad de la función de y la desigualdad de Jensen. (ver Elementos de la teoría de la información, por Cover y Thomas, página 28)X , Y l o gI(X;Y)0X,Ylog
Shir
¿También le interesan las aplicaciones de análisis complejo?
Raphael

Respuestas:

11

Vea el libro Matemáticas concretas: una base para la informática de Graham, Knuth y Patashnik. En el Capítulo 9 explican la fórmula de suma de Euler-Maclaurin . Esta es una técnica que le permite aproximar una suma finita mediante el uso de integrales. En el mismo capítulo, página 466, usan esta técnica para aproximar el número de armónicos (que aparece mucho en varias áreas de TCS). Me ocurrió una vez que tuve que usarlo, ¡y terminé resolviendo una integral usando técnicas de aproximación asintótica para ecuaciones diferenciales!

Marcos Villagra
fuente
Buenos enlaces, pero ¿no es este un análisis más numérico?
Huck Bennett
Esto es completamente analítico.
Marcos Villagra
9

Existe la teoría de los límites de las secuencias gráficas densas, desarrollada en el trabajo de Lovasz y B. Szegedy. Tiene implicaciones para ciertos problemas de prueba de propiedad en gráficos. Ver http://www.cs.elte.hu/~lovasz/hom-stoc.pdf . Básicamente, la idea es que definen una métrica adecuada en gráficos y una noción de tomar límites de secuencias de gráficos, y luego muestran que una propiedad de gráfico es comprobable si la función que asigna un gráfico a la distancia de edición a la propiedad es continua en el espacio métrico en los gráficos que se definió.

Y luego está, por supuesto, la obra maestra de Flajolet y Sedgewick dedicada exclusivamente al uso de métodos analíticos para el análisis asintótico de estructuras combinatorias, incluido el análisis de algoritmos. Esto genera principalmente trucos de función basados ​​en análisis complejos

Sasho Nikolov
fuente
2
Vale la pena mencionar que la teoría de los límites de los gráficos y, en términos más generales, el análisis de los gráficos es un tema muy candente, véase, por ejemplo, math.ias.edu/cga
Marcin Kotowski
Buen puntero @MarcinKotowski. es agradable tener a laci lovasz en el área :)
Sasho Nikolov
8

Como Shir mencionó, la desigualdad de Jensen aparece todo el tiempo. Especialmente en probar límites en problemas combinatorios. Por ejemplo, considere el siguiente problema:

Dada una familia de de subconjuntos de V = { 1 , ... , n } , su gráfico de intersección G = ( V , E ) está definido por { i , j } E si y solo si S iS j . Supongamos que el tamaño promedio establecido es r y que el tamaño promedio de las intersecciones por pares es como máximo k. Muestra esaS1,,SnV={1,,n}G=(V,E){i,j}ESiSjr|E|nk(r2) .

Prueba:

los pares modo que y . Primero , vemos que hay a lo sumo tales opciones. Tomando todos los valores de también, tenemos un límite superior de. Ahora arreglamos x. Es fácil ver que cada tiene formas de elegir . Por la desigualdad de Jensen tenemos:x V x S iS j ( S i , S j ) k ( S i , S j ) k ( n(x,(Si,Sj))xVxSiSj(Si,Sj)k(Si,Sj)x ( d(x)k(n2)=k|E|x (Si,Sj)(d(x)2)(Si,Sj)

n(r2)=n(1nxd(x)2)x(d(x)2)k|E|.

Finalmente combinamos términos para tener.nk(r2)|E|

Si bien esto es un poco más "matemático" que CS, sirve para mostrar cómo se puede utilizar una herramienta para funciones convexas, especialmente en la optimización combinatoria.

Nicholas Mancuso
fuente
tenga en cuenta que la desigualdad de jensens parece estar muy relacionada con erd "os sunflower lemma [la versión discreta vista en los límites inferiores del circuito] aunque no creo haber visto que se haya probado en ninguna parte.
vzn
7

¿ Qué tal la computación eficiente con Dedekind Reals por Andrej Bauer y Paul Taylor?

vzn
fuente
2
Realmente me gusta leer sobre el trabajo en esto: el cálculo exacto de números reales ofrece una perspectiva interesante sobre lo que son innumerables conjuntos, así como algunos algoritmos alucinantes.
Neel Krishnaswami
... por Andrej Bauer y Paul Taylor , por favor.
Andrej Bauer
2
Oh, oye, puedo editar la publicación. Fijo.
Andrej Bauer
estar corregido utilizó el autor que figura en el papel. tal vez deberías ponerlo como el coautor del periódico
vzn
1
Depende de si la teoría en la que intentas demostrarlo es clásica o constructiva. Constructivamente, solo usa el argumento de diagonalización estándar para mostrar que son incontables. Dado que los números reales deben realizarse mediante procesos computables, a partir de un POV clásico, la prueba constructiva nos dice que el problema de detención es indecidible. ¡Esto es parte de lo que quise decir cuando dije que ofrece perspectivas interesantes sobre lo que son incontables conjuntos ...!
Neel Krishnaswami
3

Una técnica muy común y a menudo útil al abordar un problema en matemática discreta es incorporarlo en un dominio continuo, ya que esto permite una mayor variedad de herramientas matemáticas para emplear. Entonces, corrigiendo mi respuesta: además de los campos en los que el análisis real aparecerá naturalmente (gráficos, procesamiento de señales y otros campos que imitan o interactúan con el mundo físico), aparece básicamente en todas partes, y en lugares donde no lo había hecho - mi Supongo que será en el futuro.

Algunos ejemplos rápidos:

  1. Error al corregir los códigos: los códigos Reed Solomon usan polinomios. Algunos límites en los códigos implican ver la función del indicador del código como una función desde el cubo discreto hasta los reales, aplicando así la transformación de Fourier y otras técnicas.
  2. El método probabilístico: los teoremas de concentración de medida (una herramienta analítica) se utilizan para mostrar varias propiedades de gráficos aleatorios (por ejemplo, número cromático). Ver el libro de Alon y Spencer.
  3. El teorema de la intersección (esto está más relacionado con la combinatoria, pero de todos modos): un gráfico con vértices y bordes tiene al menos intersecciones. La prueba consiste en tomar un gráfico aleatorio y optimizar los parámetros mediante derivación.e 1ve161e3v2

  4. El intercambio secreto de Shamir utiliza el hecho de que un polinomio grado distinto de cero se define únicamente por puntos (se basa en el hecho de que puntos proporcionan información prácticamente nula).k k - 1k1kk1

Shir
fuente
Ejemplos concretos, por favor?
Marcin Kotowski
Agregué 4 ejemplos, aunque creo que hay muchos de ellos, realmente podemos ir todo el día.
Shir
2

El campo de la medida limitada por recursos aplica la medida de Lebesgue a las clases de complejidad. La idea es obtener separaciones entre clases de complejidad hablando de los "tamaños" relativos de estos conjuntos.

mikero
fuente
2

Hay un hermoso artículo, la comunicación cuántica unidireccional es exponencialmente más fuerte que la comunicación clásica de Boaz Klartag y Oded Regev, que utiliza una gran cantidad de técnicas de análisis real que son poco comunes en TCS, incluida la transformación de radón, armónicos esféricos e hipercontractivo desigualdades en la esfera de unidad (no discreta)

usuario887
fuente
1

Siempre encontré las conexiones entre los lenguajes regulares / libres de contexto y la teoría de funciones (series de poder (formales)) bastante emocionantes: es por eso que los franceses llaman a estas clases de lenguaje "racionales" y "algebraicas". Esto también indica conexiones con la geometría fractal. En una línea similar, por ejemplo, los autómatas finitos pueden definir idiomas en palabras infinitas que tienen buenas propiedades topológicas cuando están equipados con la topología métrica estándar.

Otra conexión podría ser la teoría desarrollada recientemente de "convoluciones de conjunto" que permite acelerar varios algoritmos similares a lo que se conoce de las transformadas de Fourier. Supongo que estas son al menos "similitudes inspiradoras".

Henning Fernau
fuente