Есть ли какие-либо применения методов в реальном анализе к теоретической информатике?

Я искал далеко и широко для таких приложений и в основном оказался коротким. Я могу найти множество применений топологии и подобных структур на счетных (или неисчисляемых) наборах, но редко я нахожу неисчислимые наборы в качестве объекта изучения компьютерными учеными, что приводит к необходимости использования методов анализа.

Вот два связанных курса:

• Аналитические методы в комбинаторике и КС Эхуда Фридгута из Университета Торонто (2009),
• Аналитические методы в комбинаторике и информатике Ирит Динур и Эхуд Фридгут в Еврейском университете (2006).

Также проверьте записи Райана О'Доннелла для его книги:

• Анализ булевых функций Райан О'Доннелл.

и ссылки в правом верхнем углу.

См. Книгу « Конкретная математика - основа компьютерных наук » Грэма, Кнута и Паташника. В главе 9 они объясняют формулу суммирования Эйлера-Маклаурина . Это метод, который позволяет аппроксимировать конечную сумму с помощью интегралов. В той же главе, стр. 466, они используют эту технику для аппроксимации номера гармоники (который часто встречается в некоторых областях TCS). Это случилось со мной один раз, когда я должен был использовать его, и в итоге решил интеграл, используя методы асимптотической аппроксимации для дифференциальных уравнений!

Существует теория пределов последовательностей плотных графов, разработанная в работах Ловаша и Б. Сегеды. Это имеет значение для определенных проблем тестирования свойств на графиках. См. Http://www.cs.elte.hu/~lovasz/hom-stoc.pdf . По сути, идея заключается в том, что они определяют подходящую метрику для графов и понятие о том, что они ограничивают последовательности графов, а затем показывают, что свойство графа тестируемо, если функция, которая отображает граф на расстояние редактирования до свойства, является непрерывной в метрическое пространство на графах, которые были определены.

И тогда, конечно , Flajolet и Седжвик магнум опус полностью посвящен использование аналитических методов для асимптотического анализа комбинаторных структур, в том числе анализа алгоритмов. В основном это генерация функциональных трюков, основанных на комплексном анализе.

Как отметил Шир, неравенство Дженсена проявляется постоянно. Особенно в доказательстве границ в комбинаторных задачах. Например, рассмотрим следующую проблему:

Для данного семейства подмножеств V = { 1 , … , n } его граф пересечений G = ( V , E ) определяется { i , j } ∈ E тогда и только тогда, когда S i ∩ S j ≠ ∅ . Предполагается, что средний размер набора равен r, а средний размер парных пересечений не более k. Покажи то$S_1, \ldots, S_n$$V = \{1, \ldots, n\}$$G = (V, E)$$\{i, j\} \in E$$S_i \cap S_j \neq \emptyset$$r$ .$|E| \geq \frac{n}{k} \cdot \binom{r}{2}$

Доказательство:

Подсчитаем пары такие, что x ∈ V и x ∈ S i ∩ S j . Давайте сначала исправим ( S i , S j ) , мы увидим, что существует не более k таких выборов. Принимая все значения ( S i , S j ) , мы получаем верхнюю границу k ⋅ ($(x, (S_i, S_j))$$x \in V$$x \in S_i \cap S_j$$(S_i, S_j)$$k$$(S_i, S_j)$, Теперь мы исправим х. Легко видеть, что у каждогоxесть ( d(x$k \cdot \binom{n}{2} = k \cdot |E|$$x$ способы выбора(Si,Sj). По неравенству Дженсена имеем:$\binom{d(x)}{2}$$(S_i, S_j)$

,$n \cdot \binom{r}{2} = n \cdot \binom{\frac{1}{n}\sum_x d(x)}{2} \leq \sum_x \binom{d(x)}{2} \leq k \cdot |E|$

Мы наконец объединяем термины, чтобы иметь ,$\frac{n}{k} \cdot \binom{r}{2} \leq |E|$

Хотя это немного более "математично", чем CS, оно показывает, как можно использовать инструмент для выпуклых функций - особенно в комбинаторной оптимизации.

Как насчет эффективных вычислений с Dedekind Reals Андрея Бауэра и Пола Тейлора.

Очень распространенная и часто полезная техника при подходе к проблеме в дискретной математике - это встраивание ее в непрерывную область, поскольку это позволяет использовать более богатый выбор математических инструментов. Итак, исправляя мой ответ: кроме полей, в которых естественный анализ будет появляться естественным образом (графика, обработка сигналов и другие поля, имитирующие или взаимодействующие с физическим миром), он появляется практически везде, а в местах, где его не было, - мой думаю, так и будет в будущем.

Несколько быстрых примеров:

1. Коды исправления ошибок: коды Рида-Соломона используют полиномы. Некоторые ограничения на коды включают просмотр функции индикатора кода как функции от дискретного куба до действительного значения, таким образом применяя преобразование Фурье и другие методы.
2. Вероятностный метод - теоремы измерения концентрации (аналитический инструмент) используются для отображения различных свойств случайных графов (например, хроматического числа). Смотрите книгу Алона и Спенсера.

3. Теорема о пересечении (это больше относится к комбинаторике, но в любом случае) - граф с вершинами и e ребрами имеет по крайней мере $v$$e$ пересечения. Доказательство включает в себя случайный граф и оптимизацию параметров с помощью деривации.$\frac {1}{61} \cdot \frac {e^3} {v^2}$

4. $k-1$$k$$k-1$

Если я правильно помню, теорема Ноги Алона о расщеплении ожерелий использует непрерывную версию задачи.

См .: http://www.cs.tau.ac.il/~nogaa/PDFS/nocon.pdf.

На странице вики также есть упоминание об этом: http://en.wikipedia.org/wiki/Hobby%E2%80%93Rice_theorem

Поле Ресурс-ограниченной меры применяет меру Лебега к классам сложности. Идея состоит в том, чтобы получить разделение между классами сложности, говоря об относительных «размерах» этих наборов.

Есть прекрасная статья: « Квантовая односторонняя связь экспоненциально сильнее классической», написанная Боазом Клартагом и Одедом Регевом, в которой используется довольно большое количество методов из реального анализа, которые редко встречаются в TCS, включая преобразование Радона, сферические гармоники и гиперконтрактанты. неравенства на (недискретной) единичной сфере

Экспоненциальная нижняя граница для размера монотонных реальных цепей (1997) Хакен, Кук

Я всегда находил связи между обычными / контекстно-свободными языками и теорией функций ((формальными) степенными рядами) весьма захватывающими: именно поэтому французы называют эти языковые классы «рациональными» и «алгебраическими». Это также указывает на связь с фрактальной геометрией. Подобным образом, например, конечные автоматы могут определять языки по бесконечным словам, которые имеют хорошие топологические свойства при оснащении стандартной метрической топологией.

Другой связью может быть недавно разработанная теория «множеств свертки», которая позволяет ускорить несколько алгоритмов, аналогичных тем, которые известны из преобразований Фурье. Я предполагаю, что это по крайней мере "вдохновляющие сходства".