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.
co.combinatorics
big-picture
robinhoode
fuente
fuente
Respuestas:
Aquí hay dos cursos relacionados:
Consulte también las notas de Ryan O'Donnell para su libro:
y los enlaces en la esquina superior derecha.
fuente
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!
fuente
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
fuente
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 i ∩ S 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,…,Sn V={1,…,n} G=(V,E) {i,j}∈E Si∩Sj≠∅ r |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 i ∩ S j ( S i , S j ) k ( S i , S j ) k ⋅ ( n(x,(Si,Sj)) x∈V x∈Si∩Sj (Si,Sj) k (Si,Sj) x ( d(x)k⋅(n2)=k⋅|E| x (Si,Sj)(d(x)2) (Si,Sj)
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.
fuente
¿ Qué tal la computación eficiente con Dedekind Reals por Andrej Bauer y Paul Taylor?
fuente
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:
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 1v e 161⋅e3v2
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 - 1k−1 k k−1
fuente
Si recuerdo correctamente, el teorema de Noga Alon sobre la división de collares usa la versión continua del problema.
Ver: http://www.cs.tau.ac.il/~nogaa/PDFS/nocon.pdf
También hay una mención de eso en la página wiki aquí: http://en.wikipedia.org/wiki/Hobby%E2%80%93Rice_theorem
fuente
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.
fuente
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)
fuente
Un límite inferior exponencial para el tamaño de los circuitos reales monótonos (1997) por Haken, Cook
fuente
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".
fuente