Gibt es Anwendungen von Techniken in der realen Analyse für die theoretische Informatik?

18

Ich habe weit und breit nach solchen Anwendungen gesucht und bin größtenteils zu kurz gekommen. Ich kann viele Anwendungen von Topologie und ähnlichen Strukturen auf abzählbaren (oder unzählbaren) Mengen finden, aber selten finde ich tatsächlich unzählbare Mengen als Untersuchungsgegenstand von Informatikern, was dazu führt, dass Techniken aus der Analyse benötigt werden.

Robinhoode
quelle
Nach Meinung meiner Freunde ist in der Informationstheorie eine echte Analyse erforderlich. Wenn Sie jedoch die Grundlagen weglassen, scheint es in tcs nicht populär zu sein (zumindest für mich).
singhsumit
Informationstheorie ist genug für mich! Wenn Sie ein konkretes Beispiel
herausgreifen können
1
Es gibt auch Signalverarbeitung, Grafik und was haben Sie. Welche Art von Techniken suchen Sie?
Shir
4
Ein Beispiel (nicht sicher, ob Sie danach suchen) aus der Informationstheorie: , dh die gegenseitige Information zweier Zufallsvariablen X , Y ist nicht negativ. Dies folgt unmittelbar aus der Höhlung der l o g Funktion und Jensen-Ungleichung. (Siehe Elemente der Informationstheorie, von Cover und Thomas, Seite 28)I(X;Y)0X,YloG
Shir
Interessieren Sie sich auch für Anwendungen komplexer Analysen?
Raphael

Antworten:

18

Hier sind zwei verwandte Kurse:

Überprüfen Sie auch die Notizen von Ryan O'Donnell für sein Buch:

und die Links in der oberen rechten Ecke.

Kaveh
quelle
1
Diese Vorlesungsunterlagen sind großartig! Guter Post!
Nicholas Mancuso
11

Siehe das Buch Konkrete Mathematik - Eine Stiftung für Informatik von Graham, Knuth und Patashnik. In Kapitel 9 erklären sie die Euler-Maclaurin-Summationsformel . Dies ist eine Technik, mit der Sie eine endliche Summe mithilfe von Integralen approximieren können. Im selben Kapitel, Seite 466, verwenden sie diese Technik, um die harmonische Zahl zu approximieren (die in verschiedenen Bereichen von TCS häufig vorkommt). Es passierte mir einmal, als ich es verwenden musste, und schließlich löste ich ein Integral mit asymptotischen Approximationstechniken für Differentialgleichungen!

Marcos Villagra
quelle
Gute Links, aber ist das nicht eher eine numerische Analyse?
Huck Bennett
Das ist völlig analytisch.
Marcos Villagra
9

Es gibt die in der Arbeit von Lovasz und B. Szegedy entwickelte Theorie der Grenzen dichter Graphsequenzen. Dies hat Auswirkungen auf bestimmte Probleme beim Testen von Eigenschaften in Diagrammen. Sehen http://www.cs.elte.hu/~lovasz/hom-stoc.pdf . Grundsätzlich besteht die Idee darin, dass sie eine geeignete Metrik für Diagramme und den Begriff der Begrenzung von Diagrammsequenzen definieren und dann zeigen, dass eine Diagrammeigenschaft testbar ist, wenn die Funktion, die ein Diagramm dem Bearbeitungsabstand zur Eigenschaft zuordnet, in der stetig ist Metrikraum in Diagrammen, der definiert wurde.

Und dann gibt es natürlich Flajolet und Sedgewick des Hauptwerk gewidmet ganz auf analytische Methoden zur asymptotischen Analyse von kombinatorischen -strukturen einschließlich der Analyse von Algorithmen. Dies erzeugt hauptsächlich Funktionstricks, die auf einer komplexen Analyse beruhen

Sasho Nikolov
quelle
2
Es ist erwähnenswert , dass die Theorie der Graphen Grenzen und, weiter gefasst, die Analyse auf Graphen ein sehr heißes Thema ist, siehe zB math.ias.edu/cga
Marcin Kotowski
netter Zeiger @MarcinKotowski. Es ist schön, Laci Lovasz in der Gegend zu haben :)
Sasho Nikolov
8

Wie Shir sagte, zeigt sich Jensens Ungleichung die ganze Zeit. Besonders beim Nachweis von Grenzen in kombinatorischen Problemen. Betrachten Sie beispielsweise das folgende Problem:

Bei einer Familie von von Teilmengen von V = { 1 , ... , n } , dessen Schnitt Graph G = ( V , E ) definiert ist durch { i , j } E , wenn und nur wenn S iS j & ne; . Angenommen, die durchschnittliche eingestellte Größe ist r und die durchschnittliche Größe der paarweisen Schnittpunkte ist höchstens k. Zeige, dassS1,,SnV={1,,n}G=(V,E){i,j}ESiSjr .|E|nk(r2)

Beweis:

Zählen wir die Paare so, dass x V und x S iS j . Lassen Sie uns zuerst festlegen ( S i , S j ) , dass es höchstens k solcher Möglichkeiten gibt. Nimmt man auch alle Werte von ( S i , S j ) , so ergibt sich eine Obergrenze von k ( n(x,(Si,Sj))xVxSiSj(Si,Sj)k(Si,Sj). Wir beheben jetzt x. Es ist leicht zu sehendass jedesxhat ( d(x)k(n2)=k|E|x Möglichkeiten zur Auswahl(Si,Sj). Durch Jensens Ungleichung haben wir:(d(x)2)(Si,Sj)

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

Wir kombinieren endlich Begriffe, um n zu habennk(r2)|E|.

Dies ist zwar etwas "mathematischer" als CS, zeigt jedoch, wie ein Tool für konvexe Funktionen verwendet werden kann - insbesondere bei der kombinatorischen Optimierung.

Nicholas Mancuso
quelle
Anmerkung Jensens Ungleichheit scheint erd sehr verwandt zu sein "o Sonnenblumen- Lemma [die diskrete Version in der Schaltung untere Grenzen gesehen] , obwohl ich Ive denke nicht , dass überall bewiesen gesehen.
VZN
7

Wie wäre es mit Efficient Computation with Dedekind Reals von Andrej Bauer und Paul Taylor ?

vzn
quelle
2
Ich lese sehr gerne über die Arbeit in diesem Bereich - die exakte Berechnung von reellen Zahlen bietet eine interessante Perspektive auf unzählige Mengen sowie einige atemberaubende Algorithmen.
Neel Krishnaswami
... von Andrej Bauer und Paul Taylor , bitte.
Andrej Bauer
2
Oh hey, ich kann den Beitrag bearbeiten. Fest.
Andrej Bauer
stehen korrigiert. hat den auf Papier angegebenen Autor verwendet. vielleicht solltest du ihn als
mitautor
1
Es hängt davon ab, ob die Theorie, in der Sie sie zu beweisen versuchen, klassisch oder konstruktiv ist. Konstruktiv verwenden Sie einfach das Standardargument für die Diagonalisierung, um zu zeigen, dass sie unzählig sind. Da reelle Zahlen durch berechenbare Prozesse realisiert werden müssen, zeigt uns der konstruktive Beweis anhand eines klassischen POV, dass das Stopp-Problem nicht zu entscheiden ist. Dies ist ein Teil dessen, was ich meinte, als ich sagte, dass es interessante Perspektiven bietet, was unzählige Sets sind ..!
Neel Krishnaswami
3

Eine sehr verbreitete und oft nützliche Technik bei der Lösung eines Problems in der diskreten Mathematik ist die Einbettung in einen kontinuierlichen Bereich, da hierdurch eine größere Auswahl mathematischer Werkzeuge eingesetzt werden kann. Wenn ich meine Antwort korrigiere: Abgesehen von den Feldern, in denen die eigentliche Analyse auf natürliche Weise vorkommt (Grafiken, Signalverarbeitung und andere Felder, die die physische Welt imitieren oder mit ihr interagieren), taucht sie im Grunde überall auf und an Orten, an denen sie nicht vorhanden war Vermutlich wird es in Zukunft so sein.

Einige kurze Beispiele:

  1. Fehlerkorrekturcodes: Reed-Solomon-Codes verwenden Polynome. Bei einigen Codebeschränkungen wird die Indikatorfunktion des Codes als Funktion vom diskreten Würfel bis zum Real betrachtet, wodurch eine Fouriertransformation und andere Techniken angewendet werden.
  2. Die probabilistische Methode - Konzentrationssätze messen (ein analytisches Werkzeug) wird verwendet, um verschiedene Eigenschaften von Zufallsgraphen (z. B. chromatische Zahl) aufzuzeigen. Siehe Alon und Spencers Buch.
  3. ve161e3v2

  4. k1kk1

Shir
quelle
Konkrete Beispiele bitte?
Marcin Kotowski
Ich habe 4 Beispiele hinzugefügt, obwohl ich denke, dass es so viele davon gibt, dass wir wirklich den ganzen Tag durcharbeiten können.
Shir
2

Das Feld Ressourcengebundenes Maß wendet das Lebesgue-Maß auf Komplexitätsklassen an. Die Idee ist, eine Trennung zwischen Komplexitätsklassen zu erzielen, indem über die relativen "Größen" dieser Mengen gesprochen wird.

mikero
quelle
1

Die Zusammenhänge zwischen regulären / kontextfreien Sprachen und Funktionstheorie ((formalen) Potenzreihen) fand ich immer sehr spannend: Deshalb nennen die Franzosen diese Sprachklassen "rational" und "algebraisch". Dies weist auch auf Verbindungen zur fraktalen Geometrie hin. In ähnlicher Weise können beispielsweise endliche Automaten Sprachen für unendliche Wörter definieren, die schöne topologische Eigenschaften aufweisen, wenn sie mit der Standardtopologie für Metriken ausgestattet sind.

Eine weitere Verbindung könnte die kürzlich entwickelte Theorie der "Mengenfaltungen" sein, die es ermöglicht, mehrere Algorithmen zu beschleunigen, die den Fourier-Transformationen ähneln. Ich gehe davon aus, dass dies zumindest "inspirierende Ähnlichkeiten" sind.

Henning Fernau
quelle