Algebra zorientowana na informatykę teoretyczną

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?

Były ostatnie zmiany w zależnej teorii typów , które dotyczą systemów typu do homotopii typów .

Jest to obecnie stosunkowo niewielka dziedzina, ale w tej chwili wykonuje się wiele ekscytujących prac i potencjalnie dużo nisko wiszących owoców, szczególnie w zakresie przenoszenia wyników z topologii algebraicznej i algebry homologicznej oraz formalizowania pojęcia wyższych typów indukcyjnych .

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ą.

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.

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.

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 .

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.

Oto wiele interesujących odpowiedzi, ale nikt nie wspomniał o tym w każdym języku $L \subseteq X^{\ast}$ 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.

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.

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).

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).

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.

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.