Czy są jakieś zastosowania technik analizy rzeczywistej w informatyce teoretycznej?

Rozglądałem się daleko za takimi aplikacjami i najczęściej okazało się, że są krótkie. Potrafię znaleźć wiele zastosowań topologii i podobnych struktur na zestawach policzalnych (lub niepoliczalnych), ale rzadko znajduję zbiory niepoliczalne jako przedmiot badań przez informatyków, a zatem prowadzi to do potrzeby technik analizy.

Oto dwa powiązane kursy:

• Metody analityczne w kombinatoryce i CS autorstwa Ehuda Friedguta z University of Toronto (2009),
• Metody analityczne w kombinatoryce i informatyce Irit Dinur i Ehud Friedgut z Uniwersytetu Hebrajskiego (2006).

Sprawdź także notatki Ryana O'Donnella dotyczące jego książki:

• Analiza funkcji boolowskich autorstwa Ryana O'Donnella.

oraz linki w prawym górnym rogu.

Zobacz książkę Concrete Mathematics - A Foundation for Computer Science autorstwa Grahama, Knutha i Patashnika. W rozdziale 9 wyjaśniają formułę sumowania Eulera-Maclaurina . Jest to technika, która pozwala przybliżać skończoną sumę za pomocą całek. W tym samym rozdziale, str. 466, używają tej techniki do przybliżania liczby harmonicznych (która pojawia się często w kilku obszarach TCS). Zdarzyło mi się to raz, gdy musiałem go użyć, i ostatecznie rozwiązałem całkę za pomocą asymptotycznych technik aproksymacyjnych dla równań różniczkowych!

Istnieje teoria granic gęstych sekwencji grafowych opracowana w pracach Lovasz i B. Szegedy. Ma to wpływ na niektóre problemy z testowaniem właściwości na wykresach. Zobacz http://www.cs.elte.hu/~lovasz/hom-stoc.pdf . Zasadniczo chodzi o to, że definiują odpowiednią metrykę na wykresach i pojęcie ograniczania sekwencji wykresu, a następnie pokazują, że właściwość wykresu jest testowalna, jeśli funkcja mapująca wykres na odległość edycji do właściwości jest ciągła w przestrzeń metryczna na zdefiniowanych wykresach.

Jest też oczywiście opus magnum Flajoleta i Sedgewicka, poświęcony całkowicie wykorzystaniu metod analitycznych do asymptotycznej analizy struktur kombinatorycznych, w tym analizy algorytmów. Generuje to głównie sztuczki funkcyjne oparte na złożonej analizie

Jak wspomniał Shir przez cały czas pojawia się nierówność Jensena. Zwłaszcza w sprawdzaniu granic problemów kombinatorycznych. Weźmy na przykład następujący problem:

Biorąc pod uwagę rodzinę podzbiorów V = { 1 , … , n } , jej wykres przecięcia G = ( V , E ) jest zdefiniowany przez { i , j } ∈ E wtedy i tylko wtedy, gdy S i ∩ S j ≠ ∅ . Załóżmy, że przeciętny ustawiony rozmiar wynosi r, a przeciętny rozmiar przecięć parami wynosi co najwyżej k. Pokazują, że$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}$

Dowód:

Policzmy pary takie, że x ∈ V i x ∈ S i ∩ S j . Najpierw poprawmy ( S i , S j ) , widzimy, że istnieje co najwyżej k takich wyborów. Biorąc również wszystkie wartości ( S i , S j ) , mamy górną granicę 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)$. Naprawiamy teraz x. Łatwo zauważyć, że każdyxma ( d(x$k \cdot \binom{n}{2} = k \cdot |E|$$x$ sposoby wyboru(Si,Sj). Przez nierówność Jensena mamy:$\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|$

W końcu łączymy warunki, aby mieć .$\frac{n}{k} \cdot \binom{r}{2} \leq |E|$

Chociaż jest to nieco bardziej „math” niż CS, służy on do pokazania, w jaki sposób można użyć narzędzia do funkcji wypukłych - szczególnie w optymalizacji kombinatorycznej.

co powiesz na Efficient Computation with Dedekind Reals autorstwa Andreja Bauera i Paula Taylora.

Bardzo powszechną i często przydatną techniką, gdy podchodzisz do problemu w dyskretnej matematyce, jest osadzanie go w ciągłej dziedzinie, ponieważ pozwala to na szerszy wybór narzędzi matematycznych. Tak więc, poprawiając moją odpowiedź: poza polami, w których prawdziwa analiza pojawi się naturalnie (grafika, przetwarzanie sygnałów i inne pola naśladujące lub wchodzące w interakcje ze światem fizycznym), pojawia się w zasadzie wszędzie, aw miejscach, w których nie miała - mój zgadnij, czy tak będzie w przyszłości.

Kilka szybkich przykładów:

1. Błąd poprawiania kodów: Kody Reeda Solomona używają wielomianów. Niektóre ograniczenia kodów obejmują oglądanie funkcji wskaźnika kodu jako funkcji od odrębnej kostki do liczb rzeczywistych, w ten sposób stosując transformatę Fouriera i inne techniki.
2. Metoda probabilistyczna - pomiary twierdzeń o koncentracji (narzędzie analityczne) służą do wykazania różnych właściwości losowych wykresów (np. Liczby chromatycznej). Zobacz książkę Alona i Spencera.

3. $v$$e$$\frac {1}{61} \cdot \frac {e^3} {v^2}$

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

Jeśli dobrze pamiętam, twierdzenie Nogi Alona o rozszczepianiu naszyjników wykorzystuje ciągłą wersję problemu.

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

Wspomina się o tym również na stronie wiki tutaj: http://en.wikipedia.org/wiki/Hobby%E2%80%93Rice_theorem

Pole miary ograniczonej do zasobów stosuje miarę Lebesgue'a do klas złożoności. Chodzi o to, aby uzyskać separacje między klasami złożoności, mówiąc o względnych „rozmiarach” tych zbiorów.

Jest piękny artykuł, Kwantowa komunikacja jednokierunkowa jest wykładniczo silniejsza niż komunikacja klasyczna autorstwa Boaza Klartaga i Oded Regev, która wykorzystuje dość dużą liczbę technik z prawdziwej analizy, które są rzadkie w TCS, w tym transformację Radona, harmoniczne sferyczne i hiperkonkurencję nierówności w (niedyskretnej) sferze jednostkowej

Wykładnicza dolna granica wielkości rzeczywistych obwodów monotonicznych (1997), autor: Haken, Cook

Zawsze uważałem związki między językami zwykłymi / bezkontekstowymi a teorią funkcji ((formalną) serią potęg)) za dość ekscytujące: dlatego Francuzi nazywają te klasy językowe „racjonalnymi” i „algebraicznymi”. Wskazuje to również połączenia z geometrią fraktalną. W podobny sposób, np. Automaty skończone mogą definiować języki na nieskończonych słowach, które mają ładne właściwości topologiczne, gdy są wyposażone w standardową topologię metryczną.

Innym połączeniem może być niedawno opracowana teoria „ustawiania zwojów”, która pozwala przyspieszyć kilka algorytmów podobnych do znanych z transformat Fouriera. Zakładam, że są to przynajmniej „inspirujące podobieństwa”.