Цейтин, Григорий Самуилович
Григорий Самуилович Цейтин (15 ноября 1936, Ленинград, РСФСР, СССР — 27 августа 2022) — советский и американский учёный в области математики и информатики. Занимался проблемами конструктивной математики, логики высказываний, теории групп и математической лингвистики.
Общие сведения
| Григорий Самуилович Цейтин | |
|---|---|
| Дата рождения | 15 ноября 1936 |
| Место рождения | |
| Дата смерти | 27 августа 2022 (85 лет) |
| Место смерти | Кэмпбелл, Санта-Клара (Калифорния), США |
| Страна | |
| Место работы | |
| Образование | |
| Учёная степень | доктор физико-математических наук |
| Научный руководитель | Андрей Андреевич Марков[2] |
| Сайт | math.spbu.ru/user/tseyti… |
Биография
В 1956 году окончил математико-механический факультет ЛГУ (ныне СПбГУ) и в дальнейшем работал в НИИ математики и механики (НИИММ) ЛГУ. В конце 1950-х годов он возглавил исследовательскую группу по машинной обработке текстов, которая в 1963 году легла в основу лаборатории математической лингвистики[3]. С 1960 года кандидат физико-математических наук ЛГУ, тема диссертации «Алгорифмические операторы в конструктивных метрических пространствах»[4][5]. Доктор физико-математических наук (1968). С 1970 по 2000 год — заведующий лабораторией математической лингвистики (ныне Лаборатория интеллектуальных систем) в НИИММ ЛГУ[6].
Также Цейтин был одним из создателей и основных преподавателей Юношеской математической школы при математико-механическом факультете ЛГУ.
В 1999 году Цейтин переехал в США, где начал работать в компании «Rational Software» в Калифорнии. В 2000—2009 годах работал в IBM, в 2009—2013 годах — научным сотрудником в Стэнфордском университете[7].
В 2006 году Цейтин был признан почётным членом (англ. Distinguished Member) Ассоциации вычислительной техники.
Цейтин — эсперантист. В 2017—2020 годах он являлся секретарём Региональной Организации Эсперанто в Сан-Франциско (англ. San Francisco Esperanto Regional Organization, SFERO).
Научные достижения
В 1956 году Цейтин привёл пример полугруппы, для которой нет алгоритма, распознающего равенство слов — такие полугруппы были названы полугруппами Цейтина[8].
В 1968 году Цейтин разработал алгоритм приведения формул логики высказываний к КНФ, названный преобразованием Цейтина[9]. Это преобразование имеет фундаментальное значение для современных SAT-решателей, так как позволяет эффективно переводить формулы в КНФ с линейным ростом размера, предотвращая экспоненциальный взрыв[10].
Также Цейтин разработал специальный класс невыполнимых пропозициональных формул («формулы Цейтина») и с их помощью доказал экспоненциальные нижние оценки для метода резолюций[11].
Цейтин был одним из основателей и неформальным лидером ленинградской школы программирования, внёс свой вклад в разработку языка программирования Алгол 68 и являлся фактическим научным руководителем проекта по созданию транслятора с этого языка для ЕС ЭВМ[7][12][13].
Основные публикации
- Кандидатская диссертация «Алгорифмические операторы в конструктивных полных сепарабельных метрических пространствах» (1960)[14]
- Докторская диссертация «Исследования по конструктивному анализу: конструктивные вещественные числа и точечно-определённые функции» (1968)
- Статья «О сложности вывода в исчислении высказываний» (Записки научных семинаров ЛОМИ, 1968) и её перевод на английский язык «On the complexity of derivations in propositional calculus» (1970)[15][16].
Примечания
Ссылки
Дополнительно по теме
 |
|---|
