Czy w teoretycznym CS są jakieś tematy, które bardziej dotyczą czystej matematyki?

Jestem absolwentem informatyki teoretycznej, aw szczególności algorytmów aproksymacyjnych. Teraz uważam, że bardziej interesuje mnie czysta matematyka (mogę to powiedzieć, ponieważ wydaje mi się, że bardziej podobały mi się kursy matematyki niż kursy CS). Chciałbym zapytać, czy istnieją obszary w informatyce teoretycznej, które są prawie czystą matematyką (mówiąc ściślej, dziedziną, która sama w sobie jest zainteresowana czystą matematyką, bez uwzględnienia aplikacji w CS), czy też muszę rozważyć poważną zmianę. Jestem już dwa i pół roku w programie, więc nie jestem pewien, czy zmiana byłaby w tym momencie dobrym pomysłem.

Jedyną rzeczą, jaką mogłem znaleźć, była teoria pomniejszych grafów, pochodząca z przeglądania list akceptacji najlepszych konferencji. Ale to nie liczy się dla mnie jako „obszar”, na którym mogę się skupić.

Oto trzy kolejne pola, które pasują do twoich kryteriów.

• Teoria kategorii . Jest to wyraźnie interesujące dla najbardziej czystych pól matematycznych, ale ma również duży wpływ na teorię (funkcjonalnych, sekwencyjnych) języków programowania.

• Logika , szczególnie teoria dowodowa. Związków z informatyką jest zbyt wiele, by je wymienić, ale logika to nie tylko bogata dziedzina czystej matematyki, ale podstawa matematyki.

• Teoria liczb , „królowa matematyki”, która została uznana za pozbawioną zastosowań ... aż do pojawienia się kryptografii.

Tak: Teoria grafów, geometria obliczeniowa, teoria złożoności, kombinatoryka to rzeczy, które badam w CS. Przestrzenie wektorowe i teoria miar mogą być również przydatne w teoretycznym uczeniu maszynowym.

W teoretycznej CS stosuje się znacznie więcej matematyki, ale nie trafiają one do wiadomości tak często, jak sztuczna inteligencja i uczenie maszynowe, dlatego niewiele o nich słyszysz.

Osobiście przeniosłem się na CS z fizyki i czystej matematyki (tak, jak matematyka abstrakcyjna algebra) i nigdy nie przestaję znaleźć ciekawych problemów.

• Teoria złożoności geometrycznej jest niezwykle „matematyczna”, a wielu wiodących badaczy to więcej matematyków. patrz np. Teoria złożoności geometrycznej: wprowadzenie dla geometrów / Landsberga
• Teoria grup jest łączona z TCS na wiele głębokich sposobów, np. W badaniu słowa problem, izomorfizmy i nierozstrzygalność. patrz np . SŁOWO PROBLEM I PROBLEM ISOMORFIZMU DLA GRUP / Stillwell
• niektóre teorie automatów są bardzo matematyczne, np. połączenie półgrup z przetwornikami stanu skończonego itp. patrz np. Matematyczne podstawy teorii automatów / pin

Interesujące są współczesne badania w teorii automatów (w szerokim znaczeniu). Opiera się na wielu matematyce, ale niekoniecznie na matematyce, której nauczyłbyś się na standardowych kursach matematyki. Bardzo luźnym wyjaśnieniem może być to, że w informatyce podstawowym przedmiotem jest booolean semiring , podczas gdy w matematyce pola skończone, w tym , odgrywają znaczącą rolę.F$\mathbb{B}$$\mathbb{F}_2$

Na przykład wykorzystuje się półgrupy (również grupy odgrywają ważną rolę), a wiele wyników dotyczących półgrup skończonych w ostatnich latach było pierwotnie motywowanych teorią automatów. Stosowane są również półirowania (zamiast pierścieni): na przykład tropikalne półtrwania zostały po raz pierwszy wprowadzone w teorii automatów, zanim zostały zastosowane w geometrii tropikalnej , nowej udanej dziedzinie matematyki. Inne tematy związane z automatami obejmują logikę i teorię modeli skończonych (pomyśl o twierdzeniu o drzewie Rabina), topologię, dualność i (quasi) -jednorodne przestrzenie oraz pewną teorię liczb (zwłaszcza w przypadku pytań dotyczących systemów numeracji i formalnych szeregów mocy), teorii prawdopodobieństwa ( zwłaszcza łańcuchy Markowa) i teorię gier.

Mówiąc nieco więcej o Teorii Złożoności Geometrycznej (GCT): jest to zastosowanie geometrii algebraicznej i teorii reprezentacji do długoterminowego programu do rozwiązywania P w porównaniu z NP. Pytania postawione w GCT są zwykle głębokimi pytaniami matematycznymi, z których niektóre sięgają ponad 100 lat do pionierów geometrii algebraicznej i teorii reprezentacji - najwyraźniej nie mają nic wspólnego z obliczeniami, ale za pomocą GCT widać, że są one ściśle powiązane ze złożonością obliczeniową - i inne, z których rodzą się nowe pytania i idee w czystej matematyce (ponownie, geometria algebraiczna i teoria reprezentacji).

Nie do końca teoretyczny temat CS, ale wykorzystuje wiele wyników teoretycznych CS: możesz być zainteresowany weryfikacją oprogramowania, którego celem jest upewnienie się, że program robi to, co powinien, i nic więcej. Wśród różnych technik w tym temacie niektóre są szczególnie matematyczne. Wiele krytycznych systemów, zwłaszcza awioniki / przestrzennej / nuklearnej, zostało udowodnionych w ten sposób, aby zapewnić, że są wolne od błędów.

W grę wchodzi wiele dziedzin matematyki: logika, teoria dowodów, teoria automatów, teoria mnogości, ...