Шютценберже, Марсель-Поль

Материал из Циклопедии
Перейти к навигации Перейти к поиску

Марсель-Поль Шютценберже

фр. Marcel-Paul Schützenberger
Файл:Schützenberger.jpeg
Марсель-Поль Шютценберже в 1972 году.


Дата рождения
24 октября 1920 года
Место рождения
Париж
Дата смерти
29 июля 1996 года
Место смерти
Париж
Гражданство
Франция


Род деятельности
математик





Награды и премии

Член Академии наук

Марсель-Поль Шютценберже (фр. Marcel-Paul Schützenberger; [Нет даты!]) — французский учёный, математик и врач. Известен работами в области теоретической информатики и комбинаторики, основатель комбинаторики слов и пионер теории кодов переменной длины.

Биография[править]

Во время Второй мировой войны Марсель-Поль Шютценберже участвовал в движении Сопротивления. В конце войны он был близким сотрудником Шарля Тийона и членом его министерского кабинета. В 1948 году он женился на Анн Анселен Шютценберже; через несколько лет они развелись.

Марсель-Поль Шютценберже получил степень доктора медицины в 1949 году. С 1948 по 1953 год он был научным сотрудником Национального института гигиены, а с 1948 по 1954 год — ассистентом-консультантом в Центре генетики больницы Сен-Луи. В этот период он разрабатывал и применял статистические методы для анализа различных медицинских проблем. Он участвовал в написании двух книг из серии «Монографии Национального института гигиены» под руководством Пьера Флорана Денуа. В период с 1951 по 1954 год он работал консультантом-биостатистиком во Всемирной организации здравоохранения (ВОЗ). С 1950 по 1955 год он преподавал математическую статистику и прикладную математику в биологии в Пуатье, Париже и Нанси. В 1953 году ВОЗ направила его в Индонезию с миссией по борьбе с фрамбезией, хроническим инфекционным заболеванием тропических стран. Там он встретил свою вторую жену Хариати Суросоэгондо.

В 1953 году он защитил диссертацию по математике на тему «Вклад в статистические приложения теории информации». С 1953 года Шютценберже в течение трёх лет работал исследователем в Национальном центре научных исследований (CNRS). Он работал в области теории полугрупп, начал исследования в теории кодов и публиковал работы по теории автоматов.

В 1956 году он был приглашён в Исследовательскую лабораторию электроники Массачусетского технологического института (MIT), где Клод Шеннон находился в качестве приглашённого профессора. Он совершил множество других поездок в США: в MIT летом 1959, 1961 и 1970 годов, в Университет Северной Каролины в Чапел-Хилле в 1960—1961 годах, в Гарвардский университет в 1961—1962 годах. Весной 1963 года он находился в Пенсильванском университете, а весной 1967 года — в Калифорнийском университете в Беркли. Летом 1962 года он был консультантом в Исследовательском центре IBM, а летом 1966 года — в RAND Corporation.

В 1957 году Шютценберже был назначен профессором Университета Пуатье, где преподавал статистику с 1957 по 1963 год. В этот период он разрабатывал теорию кодов и алгебраическую теорию формальных языков, основанную на формальных рядах от некоммутирующих переменных. В 1961—1962 учебном году он преподавал на медицинском факультете Гарварда. В 1963—1964 учебном году он вернулся в CNRS в качестве директора по исследованиям в Институт Блеза Паскаля. В 1964 году он был назначен профессором Парижского факультета наук, а после создания парижских университетов — в Университет Париж VII в 1970 году. Шютценберже был консультантом научного руководства ВОЗ с 1969 по 1980 год. С 1968 по 1972 год он был научным директором IRIA (прежнее название INRIA).

В 1979 году Шютценберже был избран членом-корреспондентом Академии наук Франции. В 1988 году он стал её действительным членом.

Будучи другом Бориса Виана, он послужил прототипом доктора Шютца, героя романа «И всех уродов убьют»[1]. Близкий к Раймону Кено, он был почётным гостем УЛИПО в 1963 году[2].

В 1980-х и 1990-х годах Шютценберже стал антидарвинистом, ставя под сомнение ряд фундаментальных принципов эволюционизма. Журнал La Recherche опубликовал интервью с Шютценберже[3], которое вызвало ожесточённую полемику: многочисленные письма читателей, статьи в Charlie Hebdo и Le Monde, ответы биологов[4].

Научные труды[править]

Вместе с Ноамом Хомским он является пионером теории языков[5]. Его работы были посвящены теории полугрупп, алгебраической теории кодов переменной длины, теории конечных автоматов, формальным рядам от некоммутирующих переменных и рациональным трансдукциям. Он является одним из основателей комбинаторики слов. Он является одним из создателей комбинаторики плаксического моноида, её использования в таблицах Юнга и её приложений в изучении симметрической группы.

Теория полугрупп[править]

В алгебре, в теории полугрупп, группа Шютценберже — это группа, связанная с классом отношения Грина H. Группы Шютценберже, связанные с различными H-классами, различны, но группы H-классов одного и того же D-класса изоморфны. Кроме того, если H-класс является группой, группа Шютценберже этого H-класса изоморфна самому H-классу. Фактически, с H-классом связаны две группы Шютценберже, и они антиизоморфны.

Группы Шютценберже были открыты Шютценберже в 1957 году. Терминология появилась в книге Альфреда Х. Клиффорда и Гордона Б. Престона.

Теория формальных языков[править]

Теорема Хомского — Шютценберже утверждает, что для любого контекстно-свободного языка Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle L} существует язык Дика Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle D} , регулярный язык Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle K} и алфавитный морфизм Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \varphi} (то есть такой, что образ буквы является буквой или пустым словом) такие, что

Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle L=\varphi(D\cap K)}

Эта теорема означает, что языки Дика являются наиболее «типичными» контекстно-свободными языками. Шютценберже также ввёл в другой статье автоматы с магазинной памятью.

Формальные ряды от некоммутирующих переменных[править]

Формальный ряд над алфавитом Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle A} с коэффициентами в полукольце Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle K}  — это отображение Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle S} свободного моноида Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle A^*} в Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle K} . Значение Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle S} для слова Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle w} обозначается Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle (S,w)} , а сам ряд записывается как

Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle S= \sum_{w\in A^*}(S,w)\,w} .

В серии статей, опубликованных в 1960-х годах, Шютценберже разработал теорию некоммутативных рациональных и алгебраических рядов, которая расширяет и углубляет теорию формальных языков. Введение линейной алгебры позволяет, с одной стороны, количественно оценить неоднозначность в контекстно-свободных языках, а с другой — получить алгебраические доказательства. Теория рациональных рядов от одной переменной замечательным образом обобщается на рациональные ряды от нескольких переменных. Ряд Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle S} является рациональным, если он получен из многочленов конечным числом операций сложения, умножения и звезды Клини (при условии, что постоянный член ряда равен нулю):

Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle S^*= \sum_{n\ge0}S^n} .

Линейное представление порядка Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle N}  — это тройка Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \rho=(\lambda,\mu,\gamma)} , где Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \lambda\in K^{1\times N}} , Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \mu:A^*\to K^{N\times N}}  — морфизм, а Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \gamma\in K^{N\times 1}} . Представление распознаёт ряд Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle S} , если Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle (S,w)=\lambda\mu(w)\gamma} для любого слова Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle w} . Линейное представление является расширением обычных конечных автоматов, иногда называемым взвешенным автоматом. Ряд Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle S} является распознаваемым, если существует линейное представление, которое его распознаёт.

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

Среди наиболее известных результатов Шютценберже:

  • Теорема Клини — Шютценберже: Для любого полукольца Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle K} и любого конечного алфавита Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle A} классы рациональных рядов и распознаваемых рядов над Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle A} с коэффициентами в Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle K} совпадают;
  • Теорема Юнгена — Шютценберже: Для любого коммутативного полукольца Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle K} и любого конечного алфавита Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle A} произведение Адамара алгебраического ряда и рационального ряда также является алгебраическим рядом.

Регулярные языки без звезды[править]

Регулярный язык является языком без звезды (star-free language), если он может быть получен из букв алфавита и пустого множества с помощью конечного числа булевых операций и конкатенаций, но без операции звезды Клини. Например, язык слов над алфавитом Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \{a,\,b\}} , не содержащих двух подряд идущих букв Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle a} , является языком без звезды. Действительно, это множество определяется как Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle (\emptyset^c aa \emptyset^c)^c} , где Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle X^c} обозначает дополнение подмножества Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle X} в Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \{a,\,b\}^*} .

Шютценберже охарактеризовал языки без звезды как языки, синтаксический моноид которых конечен и апериодичен[6]. Этот результат является отправной точкой теории многообразий формальных языков.

Языки без звезды имеют и другие характеризации. Это языки, определимые в монадической логике первого порядка с операцией порядка, обозначаемой FO[<].

Это также языки, распознаваемые автоматами без счётчиков, и языки, определимые в линейной темпоральной логике[7].

Комбинаторика симметрической группы[править]

Соответствие Робинсона — Шенстеда устанавливает биекцию между симметрической группой и парами (P,Q) таблиц Юнга. Шютценберже описал многие свойства конструкции Шенстеда. Шютценберже также ввёл алгоритм, известный как пятнашки Шютценберже, который даёт способ построения таблицы P, связанной с перестановкой.

Награды[править]

  • Член Академии наук Франции.
  • Член Американской академии искусств и наук.
  • Премия Пеано 2001 года (посмертно) за книгу «Треугольник мыслей», написанную совместно с Аленом Конном и Андре Лихнеровичем[8], присуждённая Associazione Subalpina Mathesis.

Семья[править]

Марсель-Поль Шютценберже, известный как Марко, был сыном психиатра Пьера Шютценберже и внуком инженера Леона Шютценберже.

Его прадед, химик Поль Шютценберже, основал Высшую школу промышленной физики и химии города Парижа (ESPCI) в 1882 году.

Брат Марко — композитор Жан-Поль Шютценберже.

У Марко была дочь Элен Шютценберже от первой жены, психолога Анн Анселен Шютценберже, и сын Махар Шютценберже от второй жены, Хариати Суросоэгондо.

Махар, родившийся 22 января 1957 года в Кембридже (Массачусетс), погиб 29 марта 1980 года в автокатастрофе под Парижем. Была учреждена премия для поощрения работ индонезийских исследователей, готовящих докторскую диссертацию во Франции. Индонезийская семья Махара создала в его честь ассоциацию «Yayasan Mahargijono Schützenberger Indonesia», занимающуюся начальным образованием[9].

Библиография[править]

  • Théorie géométrique des polynômes eulériens. avec Dominique Foata, Berlin, Heidelberg, New York, Springer, 1970.
  • Triangle de pensées, avec Alain Connes et André Lichnerowicz, Paris, O. Jacob ; Saint-Gély du Fesc : Espace 34, 2000. ISBN 9782738107626
  • Les failles du darwinisme, La Recherche, № 283, janvier 1996
  • Œuvres complètes, éditées par Jean Berstel, Alain Lascoux et Dominique Perrin, Institut Gaspard-Monge, Université Paris-Est, 2009.

Примечания[править]

  1. ↑ La " période Saint-Germain-des-Prés " de M.-P. Schützenberger est évoquée par Paul Braffort, dans Le grand Docteur Marco.
  2. ↑ Oulipo Invités d'honneur de l'Oulipo. Oulipo. Проверено 24 июня 2026..
  3. ↑ M.-P. Schützenberger : Les failles du Darwinisme // La Recherche. — № 283..
  4. ↑ Les failles du Darwinisme // La Recherche. — № 285..
  5. ↑ Noam Chomsky et Marcel-Paul Schützenberger, " The Algebraic Theory of Context-Free Languages " dans P. Braffort et D. Hirschberg (éds), Computer Programming and Formal Systems, North Holland, 1963, p. 118—161.
  6. ↑ On finite monoids having only trivial subgroups // Information and Computation. — 1965. — том 8. — № 2. — С. 190–194..
  7. ↑ Tense Logic and the Theory of Linear Order. — University of California at Los Angeles (UCLA), 1968..
  8. ↑ Liste des Prix Peano de 2000 à 2015. Associazione Subalpina Mathesis. Проверено 24 июня 2026..
  9. ↑ Yayasan Mahargijono Schützenberger. Проверено 24 июня 2026..

Литература[править]

  • Jean Berstel et Christophe Reutenauer, Noncommutative Rational Series with Applications, Cambridge University Press, 2011.
  • M. Droste, W. Kuich et H. Vogler (eds.), Handbook of Weighted Automata, Springer-Verlag, 2009.
  • Jacques Sakarovitch, Elements of Automata Theory, Cambridge University Press, 2009.

Ссылки[править]

Рувики

Одним из источников, использованных при создании данной статьи, является статья из википроекта «Рувики» («ruwiki.ru») под названием «Шютценберже, Марсель-Поль», расположенная по адресу:

—https://ru.ruwiki.ru/wiki/Шютценберже,_Марсель-Поль

Материал указанной статьи полностью или частично использован в Циклопедии по лицензии CC-BY-SA 4.0 и более поздних версий.

Всем участникам Рувики предлагается прочитать материал «Почему Циклопедия?».

Источник — http://cyclowiki.org/w/index.php?title=Шютценберже,_Марсель-Поль&oldid=2681662