Zastosowania topologii w informatyce

61

Chciałbym napisać ankietę na temat zastosowań topologii w informatyce. Planuję opisać historię pomysłów topologicznych w dziedzinie informatyki, a także zwrócić uwagę na kilka aktualnych osiągnięć. Byłoby niezwykle pomocne, gdyby ktokolwiek mógł udzielić informacji na temat któregokolwiek z poniższych pytań.

  1. Czy są jakieś prace lub notatki opisujące chronologię wykorzystania topologii w informatyce?

  2. Jakie są najważniejsze zastosowania wyników w Topologii do informatyki?

  3. Jakie są najciekawsze obszary bieżącej pracy, które wykorzystują topologię, aby uzyskać wgląd w obliczenia?

Dzięki!

Ben
źródło
8
Kilka odpowiedzi na to drugie pytanie ma znaczenie tutaj: cstheory.stackexchange.com/questions/1920/…
Joshua
1
co z pracą nad algorytmami do obliczania obiektów topologicznych lub wykorzystaniem konstrukcji topologicznych do modelowania danych? to się liczy ?
Suresh Venkat
7
To będzie DŁUGA ankieta.
Jeffε
2
Czy ci się udało Doceniamy link do Twojej ankiety!
Tarc
To jest post o uroczym
Holden Lee

Odpowiedzi:

33

Osobiście uważam, że najciekawszym zastosowaniem topologii była praca wykonana przez Herlihy i Shavit. Wykorzystali topologię algebraiczną do scharakteryzowania asynchronicznego obliczenia rozproszonego i dali nowe dowody ważnych znanych wyników oraz znokautowali szereg długotrwałych otwartych problemów. Wygrali Godel 2004 nagrodę za tę pracę.

„Topologiczna struktura obliczeń asynchronicznych” Maurice Herlihy i Nir Shavit, Journal of the ACM, t. 46 (1999), 858–923,

Mark Reitblatt
źródło
5
"najbardziej interesujące" ? teraz są słowa walczące! :)
Suresh Venkat
28

Topologia jest tak dojrzałą dyscypliną z różnorodnymi subpólami, w tym geometryczną, algebraiczną, metryczną, zestawem punktów i (samorzutną) bezcelową topologią. Informatyka jest również dość szeroka i ma wiele podobszarów matematycznych, więc oczekiwałbym wielu zastosowań pomysłów topologicznych w CS. Marshall Stone powiedział „zawsze topologizuj”, a informatycy z wymaganym doświadczeniem często to robią. Dość bla. Kilka przykładów.

Te przykłady to nie tylko trudne problemy CS rozwiązane przez topologię. Czasami pojęcie topologiczne bardzo dobrze przenosi się na ustawienie CS lub daje podstawę dla podobszaru CS.

  1. Twierdzenie o zwartości logiki zdań jest konsekwencją twierdzenia Tychonoffa. Zwartość w logice pierwszego rzędu jest zwykle udowodniona inaczej. Zwartość jest ważnym narzędziem w klasycznej teorii modeli.

  2. Twierdzenie Stone'a o algebrach boolowskich dotyczy modeli logiki zdań, algebry boolowskiej i niektórych przestrzeni topologicznych. Wyniki dualności typu kamiennego uzyskano dla struktur stosowanych w logice algebraicznej i semantyce języka programowania.

  3. Nick Pippenger zastosował twierdzenie Stone'a do algebry boolowskiej zwykłych języków i wykorzystał topologię do udowodnienia kilku faktów na temat zwykłych języków. Zobacz komentarz Jean-Erica Pin'a, aby zapoznać się z najnowszymi pracami nad topologią w teorii języków.

  4. W metodach formalnych istnieją pojęcia własności bezpieczeństwa i żywotności. Każda właściwość czasu liniowego może być wyrażona jako przecięcie właściwości bezpieczeństwa i żywotności. Dowód wykorzystuje elementarną topologię.

  5. Martín Escardó opracował algorytmy i napisał programy do wyszukiwania nieskończonych zbiorów. Uważam, że zwartość jest kluczowym składnikiem tej pracy.

  6. Praca polskich topologów (takich jak Kuratowski) dała nam operatory zamknięcia. Operatory zamykania na siatkach są kluczową częścią teorii abstrakcyjnej interpretacji, która leży u podstaw statycznej analizy programu.

  7. Operatory zamknięcia i inne pomysły topologiczne są podstawą morfologii matematycznej.

  8. Pojęcie operatorów wewnętrznych również z polskiej szkoły jest ważne w aksjatyzacji logiki modalnej.

  9. Wiele informatyki opiera się na strukturach graficznych. Niektóre aplikacje wymagają bogatszych pojęć związanych z połączeniami i przepływami niż te zapewniane przez grafy, a topologia jest naturalnym następnym krokiem. To jest moja interpretacja wyższych wymiarów automatów van Glabbeeka w teorii współbieżności i zastosowanie topologii geometrycznej przez Erica Goubaulta do semantyki programów współbieżnych.

  10. Być może największą popularnością cieszy się aplikacja wykorzystująca topologię (początkowo algebraiczną, choć istnieją również inne kombinatoryczne prezentacje) w celu scharakteryzowania niektórych scenariuszy tolerancji błędów w obliczeniach rozproszonych. Oprócz wspomnianego wyżej Herlihy i Shavita, Borowsky i Gafni, a także Saks i Zaharouglou dali dowód za pierwszy taki przełom. Ramy obliczeń asynchronicznych dały więcej takich wyników.

  11. Twierdzenie Brouwera o punkcie stałym dało początek kilku problemom, które badamy. Ostatnio w badaniach nad algorytmiczną teorią gier, klasą złożoności PPAD i klasą złożoności FixP problemów z punktami stałymi.

  12. Twierdzenie Borsuka-Ulama ma kilka zastosowań w grafach i osadzeniach metrycznych. Są one opisane w książce Jiří Matouška.

To skromne wybory na to, co tam jest. Powodzenia!

Vijay D.
źródło
Co za świetna lista!
Dave Clarke
24

D[DD]λ-rachunek różniczkowy. Semantyka zasadniczo opiera się na pojęciu aproksymacji podanym przez porządkowanie oraz rozwiązaniu równań o najmniej ustalonym punkcie, a rozwiązania na ogół są gwarantowane.

Z semantyki denotacyjnej wynikają związki z abstrakcyjną interpretacją oraz analizą i weryfikacją programu.

Obecne badania obejmują zapewnienie semantyki denotacyjnej dla współbieżności i języków kwantowych.

Abramsky i Jung przedstawiają miłą analizę głównych pomysłów: teorii domen .

Dave Clarke
źródło
18

Ograniczenia dotyczące liczby połączonych komponentów, a bardziej ogólnie liczb Bettiego, odmian algebraicznych i układów hiperpłaszczyznowych (oraz ich uzupełnień) zastosowano w kilku dolnych granicach obliczeń algebraicznych i drzew decyzyjnych. Aby zobaczyć tylko kilka dużych referencji, zobacz:

Michael Ben-Or, Dolne granice dla drzew obliczeniowych algebraicznych, STOC 1983, s. 80–86.

Andrew Chi-Chih Yao, Złożoność drzewa decyzyjnego i liczby Betti, J. Comput. System Sci. 55 (1997), no. 1, część 1, 36–43 (STOC 1994).

Anders Bjorner i Laszlo Lovasz, Liniowe drzewa decyzyjne, aranżacje podprzestrzeni i funkcje Mobiusa, J. Amer. Matematyka Soc. 7 (1994), no. 3, 677–706.


W innym, ale nieco pokrewnym stylu, Smale zastosował topologię w dość interesujący sposób (w szczególności kohomologię grupy warkoczy), aby obniżyć granicę złożoności znalezienia korzenia w modelu Blum-Shub-Smale:

Smale, S. O topologii algorytmów, IJ Complexity, 3 (2): 81-89, 1987.

Joshua Grochow
źródło
Te odniesienia wydają się stosunkowo stare. Czy była kontynuowana linia badań, czy były to dość jednorazowe wyniki?
Mark Reitblatt,
Cóż, nie nazwałbym ich jednorazowymi, ponieważ przy użyciu tych technik uzyskano wiele wyników. Myślę, że bardziej nowoczesne wyniki (powiedzmy z ostatniej dekady) albo stosują zupełnie inne techniki, albo wykorzystują więcej aspektu geometrii półalgebraicznej niż aspektu topologicznego.
Joshua Grochow
(Nie wiem o pytaniu Marka o wynik Smale.)
Joshua Grochow
18

2ω

Jest to związane z odpowiedzią Dave'a i teorią domen. Podstawowym argumentem jest tutaj to, że obliczalność jest z natury oparta na lokalnych operacjach i skończonych obserwacjach . Obliczenia można traktować jako dopracowane pojęcie topologii. Najbardziej wyraźnym przykładem jest to, że:

Wszystkie funkcje obliczeniowe (oracle Turing) są ciągłe. Z drugiej strony, każda funkcja ciągła jest wyrocznią Turinga obliczalną z odpowiednią wyrocznią.

Więcej można znaleźć w książce Klausa Weihraucha „Analiza obliczeniowa”. Możesz także zajrzeć do ładnej książki Stevena Vickersa zatytułowanej „Topologia przez logikę”.

Kaveh
źródło
15

Dwa inne artykuły, które mogą być istotne dla Twojej ankiety ...

M. Gehrke, S. Grigorieff, J.-E. Pin, Topologiczne podejście do rozpoznawania, ICALP 2010, część II, Uwagi do wykładu z informatyki 6199, Springer Verlag, (2010), 151-162.

M. Gehrke, S. Grigorieff, J.-E. Pin, Dwoistość i teoria równania języków regularnych, Nagroda za najlepszą pracę papierową ICALP 2008, Ścieżka B, ICALP 2008, Część II, Uwagi do wykładu z informatyki 5126, Springer Verlag, (2008), 246-257.

Jean-Eric Pin
źródło
3
Witamy! Bardzo podobał mi się artykuł z ankiety „Metody profinite w teorii automatów”.
Neel Krishnaswami,
14

Nie zapomnij przypuszczenia Knesera i dowodu Kahna / Saksa / Sturtevanta dla przypuszczenia Aandery-Rosenberga-Karpa.

Suresh Venkat
źródło
14

Nie widziałem wspomnianej pracy Roberta Ghrista , wcześniej w Illinois, ale teraz w U Penn, stosującej topologię do takich rzeczy, jak sieci czujników i robotyka. Oto miły wywiad.

Również bardzo związany z pracą Gunnara Carlssona i in. Nad zastosowaniem topologii do analizy danych .

Być może nie STS / FOCS TCS, ale zdecydowanie informatyka.

Mugizi Rwebangira
źródło
13

Teorie rozumienia współbieżności i modelowania obliczeń współbieżnych najlepiej zrozumieć topologicznie. Oprócz słynnej pracy Herlihy i Shavita na temat topologicznej struktury obliczeń asynchronicznych wspomnianej we wcześniejszej odpowiedzi - Eric goubault wykonał prace nad modelowaniem współbieżności z geometrią, a praca Pratta nad zastosowaniem przestrzeni Chu do współbieżności w grupie konkurentów Stanforda jest również interesująca chociaż nie znam ich pracy.

kryptos
źródło
12

Wszystkie prace rozpoczęte przez Kitaeva nad topologicznym podejściem do odpornego na uszkodzenia komputera kwantowego. Zobacz oryginalny artykuł Kitaeva lub, na przykład, notatki z wykładu Johna Preskilla .

Alessandro Cosentino
źródło
12

Nikt jeszcze nie wspomniał o ukierunkowanej topologii algebraicznej , która w rzeczywistości została opracowana w celu zapewnienia odpowiedniego algebraicznego zestawu narzędzi topologicznych do badania współbieżności.

Istnieje również kilka nisko wymiarowych podejść topologicznych do tematów teorii obliczeń, wszystkie dość nowe:

  • Różne podejścia do odpornego na błędy dowolnego obliczenia kwantowego opartego na teorii warkoczy. Zobacz np. TUTAJ i TUTAJ . Również do sieci adiabatycznych obliczeń kwantowych TUTAJ .
  • Schematyczne formalizmy oparte na topologii dla rachunku lambda (np. TUTAJ , strony 46-48 i TUTAJ ) oraz dla rachunku pi Milnera ( TUTAJ ).
  • Wykorzystanie konkatenacji kolorowych splotów do modelowania rekurencji i łańcuchów Markowa. Zobacz np. TUTAJ i TUTAJ . W rzeczywistości udowodniono (niepublikowane), że w ten sposób można modelować dowolne obliczenia maszyny Turinga i dowolną rekurencyjną sieć neuronową pierwszego rzędu.
  • Istnieje formalizm teoretyczny wyższej kategorii dla obliczeń kwantowych, w którym diagramy topologiczne reprezentują obliczenia, a diagramy równoważne topologicznie reprezentują różne procedury o identycznej treści obliczeniowej. Zobacz TUTAJ .
Daniel Moskovich
źródło
11

Niektóre aplikacje do osadzania danych.

Sprawdź tę książkę Matousek: http://kam.mff.cuni.cz/~matousek/akt.html

Sprawdź także następujące dokumenty:

  • Osadzanie Bi-Lipschitza w mało wymiarowych przestrzeniach euklidesowych, J. Matousek (1990) (używa twierdzenia van Kampena, aby udowodnić dolną granicę)
  • Niedopuszczalność osadzeń metrycznych w Rd, J. Matousek i A. Sidiropoulos
Zouzias
źródło
10

przeczytaj tę książkę:

Zobacz zarchiwizowaną stronę internetową

rhl
źródło
Nie wiem, czy topologia obliczeń jest tym, czego naprawdę szuka. Czy istnieją aplikacje poza topologią obliczeniową?
Mark Reitblatt,
8
Ummm. Tak. Książka Afry wyraźnie omawia rekonstrukcję powierzchni i usuwanie szumów topologicznych (które mają zastosowania w grafice komputerowej), ale są też zastosowania topologii obliczeniowej w analizie danych wielowymiarowych, różnorodnym uczeniu się, wizji komputerowej, przetwarzaniu obrazu, redukcji wymiarów, wyszukiwaniu informacji, ruchu planowanie itp. itd. itd.
Jeffε
8

Sprawdź tę książkę, Złożoność obliczeniowa: perspektywa ilościowa, bada rozmiar niektórych klas złożoności przy użyciu narzędzi topologicznych ograniczonych do zasobów.

PNPPNPNPPNPNPP

Mohammad Al-Turkistany
źródło
4
W rzeczywistości dużo pracy włożono w pomiar p-miar i kategorii p (do tego właśnie odnosi się turkistany). Jack Lutz przedstawił ten pomysł i możesz znaleźć mnóstwo artykułów, patrząc na niego, podążając za linkami do współautorów i przesyłając dalej referencje.
Joshua Grochow