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

33

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

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

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

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

spaceman_spiff
источник
1
Является ли изучение полей частью алгебры? На математике есть те, кто так не думает.
alancalvitti
1
Он предлагается во многих институтах здесь как курс алгебры второго уровня, и во многих известных книгах по алгебре, таких как абстрактная алгебра dummit и foote, содержится значительный материал по теории Филда ...
spaceman_spiff

Ответы:

27

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

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

Коди
источник
24

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

Джошуа Грохов
источник
15

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

Мартин Бергер
источник
11

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

Сашо Николов
источник
7

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

Карлос Эдуардо Канчино Чакон
источник
6

Задумывались ли вы о взгляде на компьютерную алгебру? Аксиома - это система компьютерной алгебры, в которой система типов смоделирована после теории категорий (или универсальной алгебры, в зависимости от вашего взгляда). Есть еще две производные от 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, не беспокоясь о теории категорий, в качестве типичного конечного пользователя, то система символьных вычислений - это как раз то, что нужно для изучения отдельных алгебр.

Ник Доай
источник
5

LИкс*

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

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

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

StefanH
источник
Также было бы интересно взглянуть на древовидные языки, а не на языковые. Давно нерешенная проблема состоит в том, чтобы охарактеризовать выразительную силу логики первого порядка на деревьях с точки зрения некоторого алгебраического объекта, связанного с ним (упомянутого в "Некоторые открытые проблемы в автоматах и ​​логике" в ACM SIGLOG News). Для дальнейшего чтения я рекомендую статьи Миколая Боянчика и Говарда Штраубинга.
Бартош Беднарчик
4

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

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

Чад Brewbaker
источник
12
Не уверен, что за обычаи здесь, но в Stack Overflow этот ответ, вероятно, будет удален как ответ только для ссылок очень скоро. Не могли бы вы предоставить краткую информацию о том, как ссылка отвечает на вопрос, а не только о том, что она отвечает Ссылки имеют тенденцию ломаться со временем, и без ссылки ваш ответ будет почти бесполезным.
Палек,
1
Не беспокойся Я написал себе напоминание, чтобы обновить его с его окончательным проектом.
Чад Brewbaker
4
@ChadBrewbaker Но, тем не менее, ваш ответ по сути всего две ссылки. Даже если вы пообещаете поддерживать эти ссылки в актуальном состоянии (что является благородной целью и высоко ценится, но, несомненно, обречено на провал), это плохой ответ.
Дэвид Ричерби
3

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

mathDR
источник
2

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

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

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

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

Манолито Перес
источник
0

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

Мартин Питерс
источник