Алгебра ориентированная отрасль теоретической информатики

У меня очень сильная база в алгебре, а именно

• коммутативная алгебра,
• гомологическая алгебра,
• теория поля,
• теория категорий,

и я в настоящее время изучаю алгебраическую геометрию.

Я - математик со склонностью переключаться на теоретическую информатику. Помня вышеупомянутые области, какое поле было бы наиболее подходящей областью в теоретической информатике, на которую переключиться? То есть, в какой области можно использовать теорию и математическую зрелость, полученные с помощью этих полей, в своих интересах?

В последнее время появились теории зависимых типов, которые связывают системы типов с гомотопическими типами .

В настоящее время это сравнительно небольшая область, но в настоящее время проводится много увлекательной работы и, возможно, много низко висящих плодов, особенно в области переноса результатов из алгебраической топологии и гомологической алгебры и формализации понятия высших индуктивных типов .

Алгебраическая геометрия широко используется в теории алгебраической сложности и, в частности, в теории геометрической сложности. Теория представлений также имеет решающее значение для последних, но она еще более полезна в сочетании с алгебраической геометрией и гомологической алгеброй.

Ваши знания теории поля были бы полезны в криптографии, в то время как теория категорий широко используется в исследованиях языков программирования и систем ввода, которые тесно связаны с основами математики.

Теория поля и алгебраическая геометрия были бы полезны в темах, связанных с кодами, исправляющими ошибки, как в классических условиях, так и при изучении локально декодируемых кодов и списочного декодирования. Я считаю, что это восходит к работе над кодами Рида-Соломона и Рида-Мюллера, которые затем были обобщены на алгебраические геометрические коды. См., Например, главу этой книги о классическом представлении теории кодирования алгебраических геометрических кодов, этот краткий обзор локально декодируемых кодов и эту знаменитую статью о декодировании списков кода Рида-Соломона и, в более общем смысле, кодов алгебраической геометрии.

Есть некоторые проблемы в теории компьютерного обучения, машинного обучения и компьютерного зрения, которые могут быть решены с помощью коммутативной алгебры и алгебраической геометрии. Например, сходимость алгоритма распространения убеждений, алгоритма передачи сообщений для байесовского вывода, может быть сформулирована в терминах характеристики аффинного многообразия системы полиномиальных уравнений .

Задумывались ли вы о взгляде на компьютерную алгебру? Аксиома - это система компьютерной алгебры, в которой система типов смоделирована после теории категорий (или универсальной алгебры, в зависимости от вашего взгляда). Есть еще две производные от Axiom FriCAS и OpenAxiom .

Если вы интересуетесь теорией категорий, то вам стоит обратить внимание на систему типов.

В Аксиоме каждый «элемент» (например, «1», «5 * x ** 2 + 1») является элементом домена. «Домен» - это объект Axiom, объявленный как член определенной категории (например, Integer, Polynomial (Integer). Категория Axiom - это объект Axiom, объявленный как член различаемого символа «Category» (например, Ring, Polynomial). (R, E, F)).

Существует решетка наследования для множественного наследования среди категорий. например, Категория Monad наследуется от SetCategory, Monoid от Monad, Group от Monoid и т. д., и т. д.

Существует также полиморфизм высшего порядка, немного похожий на Generics в Java.

Несколько действий в Аксиоме можно рассматривать как Функторы, но это было бы довольно много, чтобы рассмотреть их здесь!

Если вы просто хотите использовать Axiom, не беспокоясь о теории категорий, в качестве типичного конечного пользователя, то система символьных вычислений - это как раз то, что нужно для изучения отдельных алгебр.

$L \subseteq X^{\ast}$

Следующие люди использовали этот алгебраический взгляд в случае регулярных языков: Сэмюэль Эйленберг из Теории автоматов, Жан Берстель , Жан-Эрик Пин , Марсель Шютценберг и Теория Крона-Родса .

Также есть нетривиальная алгебра, вовлеченная в работу вокруг гипотезы Черни , большая часть которой является довольно комбинаторной. Но в последнее время я видел, что больше сделано с линейной алгеброй, теорией колец и теорией представлений, посмотрите на работы Бенджамина Стейнберга и Хорхе Алмейды .

Между прочим, вы можете неплохо продвинуться в этих областях с теорией полугрупп, моноидов и групп, но теория категорий и теория гомотопий не так широко используются в этой области. Но, возможно, интересно отметить, что С. Эйленберг был одним из отцов-основателей теории категорий, хотя это было до того, как он начал заниматься теорией автоматов.

Тезис Брента Йорджи , хотя и является всего лишь черновиком, прекрасно объясняет, почему ваши интересы актуальны для TCS.

Вот что говорил Джоял в апреле этого года на соответствующем материале.

Я не знаю, рассматривали ли вы отрасль, но компания Ayasdi проделывает потрясающую работу, применяя множество гомотопических и других прикладных топологических методов в науке о данных. Они смешивают много теории с приложениями. В основном, чтобы увидеть, что они делают, посмотрите на веб-сайт Stanford Comptop. (Большинство людей пришли оттуда).

В дополнение к тому, что сказали все остальные (я думаю, что самое большое применение этих веток действительно в системах типов):

• Теория решеток и частичные порядки в целом применяются довольно мало для анализа поведения распределенных систем и для анализа потоков данных в компиляторах.
• Я также видел связи Галуа, применяемые к машинному обучению (в частности, классификация текста: связь Галуа между подмножествами левой и правой вершин двудольного графа документ / слово позволила значительно ускорить алгоритм).

Связи между алгеброй и теоретической информатикой очень сильны. Ник Доай уже упоминал о компьютерной алгебре, но он явно не включал теорию систем переписывания, которая является неотъемлемой частью компьютерной алгебры, с приложениями для автоматического решения уравнений и автоматического рассуждения. Системы переписывания строк являются важной областью, с приложениями в теории вычислительных групп. Посмотрите книгу «Системы переписывания строк», например, Рональдом Буком и Фридрихом Отто.

Существует также связь между теорией графов и алгеброй, которая включает в себя, например, хорошо развитую спектральную теорию графов и сложных сетей, а также теорию симметрий графов (графы Кэли, вершинно-транзитивные графы и другие типы симметрических графов. , которые интенсивно используются в качестве моделей для сетей связи в параллельных компьютерах). Проверьте книгу «Теория алгебраических графов» Криса Годсила и Гордона Ройла, чтобы ознакомиться с различными темами.

Проверьте ситуацию в компьютерном зрении. Есть много тем, в частности, алгоритмического типа, для которых очень полезны первые три области, которые вы перечислите.