Algebra zorientowana na informatykę teoretyczną

33

Mam bardzo silną bazę w algebrze, a mianowicie

  • algebra przemienna,
  • algebra homologiczna,
  • teoria pola,
  • teoria kategorii,

i obecnie uczę się geometrii algebraicznej.

Jestem matematyką z tendencją do przejścia na informatykę teoretyczną. Mając na uwadze powyższe pola, które pole byłoby najbardziej odpowiednie w informatyce teoretycznej, na które należy się przełączyć? To znaczy, w jakim polu można wykorzystać teorię i matematyczną dojrzałość uzyskaną dzięki zastosowaniu powyższych pól?

spaceman_spiff
źródło
1
Czy badanie pól jest uważane za część algebry? Na stronie matematyki istnieje kilka osób, które nie myślą.
alancalvitti
1
Jest oferowany w wielu instytutach jako kurs algebry drugiego poziomu, a wiele znanych książek o algebrze, takich jak dummit i abstrakcyjna algebra Foote'a, zawiera znaczący materiał na temat teorii filed ...
spaceman_spiff

Odpowiedzi:

24

Geometria algebraiczna jest szeroko stosowana w teorii złożoności algebraicznej, a zwłaszcza w teorii złożoności geometrycznej. Teoria reprezentacji jest również kluczowa dla tych ostatnich, ale jest jeszcze bardziej użyteczna w połączeniu z geometrią algebraiczną i algebrą homologiczną.

Joshua Grochow
źródło
15

Twoja wiedza na temat teorii pola byłaby przydatna w kryptografii, podczas gdy teoria kategorii jest szeroko wykorzystywana w badaniach nad językami programowania i systemami pisania, które są ściśle związane z podstawami matematyki.

Martin Berger
źródło
11

Teoria pola i geometria algrebraiczna byłyby przydatne w tematach związanych z kodami korygującymi błędy, zarówno w ustawieniach klasycznych, jak i w badaniu kodów dekodowanych lokalnie i dekodowania list. Sądzę, że wróciło to do pracy nad kodami Reeda-Solomona i Reeda-Mullera, które następnie uogólniono na algebraiczne kody geometryczne. Zobacz na przykład ten rozdział książki na temat klasycznej teorii algebraicznych kodów geometrycznych, tę krótką ankietę na temat kodów dekodowanych lokalnie oraz ten słynny artykuł o dekodowaniu listowym Reeda-Solomona i, bardziej ogólnie, kodów geometrii algebraicznej.

Sasho Nikolov
źródło
7

Istnieją pewne problemy w teorii uczenia obliczeniowego, uczenia maszynowego i wizji komputerowej, które można rozwiązać za pomocą algebry przemiennej i geometrii algebraicznej. Na przykład, zbieżność algorytmu Belief Propagation, algorytmu przekazywania wiadomości dla wnioskowania Bayesa, można sformułować pod kątem charakteryzowania różnorodności afinicznej układu równań wielomianowych .

Carlos Eduardo Cancino Chacón
źródło
6

Czy myślałeś o spojrzeniu na algebrę komputerową? Axiom to komputerowy system algebry, w którym system typów jest modelowany na podstawie teorii kategorii (lub algebry uniwersalnej, w zależności od widoku). Istnieją dwie dalsze pochodne Axiom FriCAS i OpenAxiom .

Jeśli interesuje Cię teoria kategorii, to system typów może być jedną rzeczą, na którą warto spojrzeć.

W Axiomie każdy „element” (np. „1”, „5 * x ** 2 + 1”) jest elementem Domeny. „Domena” to obiekt Axiom zadeklarowany jako członek określonej kategorii (np. Liczba całkowita, wielomian (liczba całkowita). Kategoria Axiom to obiekt Axiom zadeklarowany jako członek wyróżnionego symbolu „kategoria” (np. Pierścień, wielomian (OBRÓT SILNIKA)).

W przypadku kategorii wielokrotnych istnieje sieć dziedziczenia. np. Kategoria Monada dziedziczy z SetCategory, Monoid z Monady, Grupa z Monoidu itp. itp.

Istnieje również polimorfizm wyższego rzędu, trochę podobny do Generics w Javie.

Kilka działań w Axiomie może być postrzeganych jako Functors, ale tutaj byłoby dużo do zrobienia!

Jeśli chcesz korzystać z Axiom, nie martwiąc się o teorię kategorii, jako typowy użytkownik końcowy, to system obliczeń symbolicznych jest właśnie odpowiednim oprogramowaniem do wyszukiwania poszczególnych algebry.

Nic Doye
źródło
5

Oto wiele interesujących odpowiedzi, ale nikt nie wspomniał o tym w każdym języku L.X jest naturalnie związany ze strukturą monoidu poprzez relację zgodności Nerode-Myhill.

Poniższe osoby wykorzystały ten algebraiczny pogląd w przypadku zwykłych języków: Samuel Eilenberg na temat teorii automatów, Jean Berstel , Jean-Eric pin , Marcel Schützenberg i teoria Krohna-Rhodesa .

W pracach wokół hipotezy Cerny'ego zaangażowana jest także nietrywialna algebra , z której większość ma charakter kombinatoryczny. Ale ostatnio widziałem, jak więcej się robi z algebrą liniową, teorią pierścieni i teorią reprezentacji, patrzcie na pracę Benjamina Steinberga i Jorge Almeidy .

Nawiasem mówiąc, możesz dobrze sobie radzić w tych obszarach z teorią półgrup, monoidów i grupami, ale teoria kategorii i teoria homotopii nie są tak często używane w tym obszarze. Ale może warto zauważyć, że S. Eilenberg był jednym z ojców założycieli teorii kategorii, pomimo tego, że był zaangażowany w teorię automatów.

StefanH
źródło
Interesujące może być również spojrzenie na języki drzewa, a nie na języki słów. Długotrwały otwarty problem polega na scharakteryzowaniu ekspresyjnej mocy logiki pierwszego rzędu na drzewach pod względem powiązanego z nią obiektu algebraicznego (wspomnianego w „Niektórych otwartych problemach w automatach i logice” w ACM SIGLOG News). Do dalszej lektury polecę artykuły Mikołaja Bojańczyka i Howarda Straubinga.
Bartosz Bednarczyk
4

Teza Brenta Yorgeya , choć wciąż jest tylko szkicem , robi niesamowitą robotę, wyjaśniając, dlaczego twoje zainteresowania są istotne dla TCS.

Oto przemówienie Joyal z kwietnia ubiegłego roku na temat pokrewnych materiałów.

Chad Brewbaker
źródło
12
Nie jestem pewien, jakie są urzędy celne, ale w przypadku przepełnienia stosu ta odpowiedź prawdopodobnie zostanie wkrótce usunięta jako odpowiedź tylko do łącza. Czy podasz podsumowanie, w jaki sposób link odpowiada na pytanie, a nie tylko, że tak? Linki z czasem się psują i bez linku odpowiedź byłaby prawie bezużyteczna.
Palec
1
Nie martw się Napisałem sobie przypomnienie, aby zaktualizować go o jego ostateczny projekt.
Chad Brewbaker
4
@ChadBrewbaker Ale twoja odpowiedź to w zasadzie tylko dwa linki. Nawet jeśli obiecujesz utrzymać te linki na bieżąco (co jest szlachetnym celem i bardzo doceniane, ale na pewno skazane na porażkę), to słaba odpowiedź.
David Richerby
3

Nie wiem, czy zastanawiałeś się nad branżą, ale firma Ayasdi wykonuje niesamowitą pracę, stosując wiele homotopii i innych stosowanych metod topologicznych w dziedzinie analizy danych. Łączą wiele teorii z aplikacjami. Zasadniczo, aby zobaczyć, co zamierzają, zajrzyj na stronę Stanford Comptop. (Większość ludzi stamtąd przybyła).

matematyka
źródło
2

Oprócz tego, co wszyscy inni mówili (myślę, że największe zastosowanie tych gałęzi jest rzeczywiście w systemach typu):

  • Teoria krat i generalnie częściowe porządki są dość często stosowane do analizy zachowania systemów rozproszonych oraz do analizy przepływu danych w kompilatorach.
  • Widziałem także połączenia Galois stosowane w uczeniu maszynowym (w szczególności klasyfikację tekstu: połączenie Galois między podzbiorami lewego i prawego wierzchołka dwustronnego wykresu dokument / słowo pozwoliło znacznie przyspieszyć algorytm).
jkff
źródło
1

Powiązania między algebrą a informatyką teoretyczną są bardzo silne. Nic Doye wspomniał już o Algebrze Komputerowej, ale nie zawarł wyraźnie teorii o przepisywaniu systemów, która jest istotną częścią Algebry Komputerowej, z zastosowaniami w automatycznym rozwiązywaniu równań i automatycznym rozumowaniu. Systemy przepisywania ciągów to ważny podobszar, mający zastosowanie w obliczeniowej teorii grup. Sprawdź na przykład książkę „String Recriting Systems” autorstwa Ronalda Booka i Friedricha Otto.

Istnieje również związek między teorią grafów i algebrą, która obejmuje na przykład dobrze rozwiniętą teorię spektralną grafów i sieci złożonych, a także teorię symetrii grafów (wykresy Cayleya, grafy przechodzące wierzchołki i inne typy grafów symetrycznych , które są szeroko stosowane jako modele sieci połączeń w komputerach równoległych). Sprawdź książkę „Algebraic Graph Theory” autorstwa Chrisa Godsila i Gordona Royle'a, aby uzyskać przegląd różnych tematów.

Manolito Pérez
źródło
0

Sprawdź sytuację w wizji komputerowej. Jest w szczególności wiele tematów typu algorytmicznego, dla których pierwsze trzy wymienione obszary są bardzo przydatne.

Martin Peters
źródło