Георгий Адельсон-Вельский

Георгий Михайлович Адельсон-Вельский (8 января 1922, Самара — 26 апреля 2014, Бат-Ям, Израиль) — советский и израильский математик, кибернетик и шахматист. Известен как один из создателей АВЛ-дерева — первой в истории информатики самобалансирующейся структуры данных. Также внёс значительный вклад в развитие компьютерных шахмат, в частности, как разработчик одной из первых шахматных программ для ЭВМ.

Биография

Ранние годы и образование

Георгий Адельсон-Вельский родился 8 января 1922 года в Самаре. Его отец, Михаил Михайлович Адельсон-Вельский, был инженером-строителем, мать, Елена Исааковна, — домохозяйкой. В 1930-х годах семья переехала в Москву. В 1940 году Георгий поступил на механико-математический факультет Московского государственного университета имени М. В. Ломоносова (МГУ).

Участие в Великой Отечественной войне

С началом Великой Отечественной войны в 1941 году Адельсон-Вельский прервал учёбу и добровольцем ушёл на фронт. Служил в артиллерийской разведке, участвовал в боях на Западном, 3-м Белорусском и 1-м Прибалтийском фронтах. Был награждён орденом Красной Звезды, орденом Отечественной войны II степени и медалями. Демобилизовавшись в 1945 году, вернулся в МГУ и в 1948 году окончил университет с отличием.

Научная и педагогическая деятельность

После окончания МГУ Адельсон-Вельский работал в Институте точной механики и вычислительной техники АН СССР (ИТМиВТ), где занимался вопросами теории алгоритмов и программирования. В 1950-х годах он участвовал в разработке одной из первых советских ЭВМ — М-20. В 1962 году защитил кандидатскую диссертацию на тему «Алгоритмы и структуры данных для быстрого поиска».

С 1963 по 1990 год преподавал на кафедре математической логики и теории алгоритмов механико-математического факультета МГУ. В 1970-х годах совместно с коллегами разработал шахматную программу «Каисса», которая в 1974 году стала чемпионом мира среди компьютерных шахматных программ.

Эмиграция и последние годы

В 1990 году Адельсон-Вельский репатриировался в Израиль, где поселился в городе Бат-Ям. Продолжал научную работу, сотрудничал с Тель-Авивским университетом и компанией IBM. Скончался 26 апреля 2014 года на 93-м году жизни.

Научные достижения

АВЛ-дерево

Главным научным результатом Адельсон-Вельского является создание в 1962 году совместно с Евгением Михайловичем Ландисом АВЛ-дерева (аббревиатура от фамилий авторов: Адельсон-Вельский и Ландис). Это бинарное дерево поиска, в котором для каждого узла высота левого и правого поддеревьев различается не более чем на единицу. Такая балансировка гарантирует, что операции поиска, вставки и удаления выполняются за логарифмическое время O(log n), где n — количество узлов.

АВЛ-дерево стало первой в истории информатики самобалансирующейся структурой данных и до сих пор широко используется в базах данных, файловых системах и компиляторах. Работа Адельсон-Вельского и Ландиса «Алгоритм организации информации» была опубликована в журнале «Доклады Академии наук СССР» в 1962 году и стала классикой компьютерной науки.

Шахматная программа «Каисса»

В 1960-х годах Адельсон-Вельский заинтересовался компьютерными шахматами. В 1965 году он совместно с коллегами из ИТМиВТ начал разработку шахматной программы для ЭВМ М-20. Программа, названная «Каисса» (в честь богини шахмат из поэмы Уильяма Джонса), была одной из первых в мире, способных играть на уровне мастера.

В 1974 году «Каисса» приняла участие в первом чемпионате мира по шахматам среди компьютерных программ, проходившем в Стокгольме в рамках конгресса Международной федерации по обработке информации (IFIP). Программа одержала победу, обыграв всех соперников, включая американскую программу «Chess 4.0» и британскую «Master». Этот успех принёс Адельсон-Вельскому и его команде мировую известность.

Другие работы

Помимо АВЛ-дерева и «Каиссы», Адельсон-Вельский внёс вклад в следующие области:

• Теория алгоритмов: разработал методы анализа сложности алгоритмов сортировки и поиска.
• Искусственный интеллект: занимался проблемами автоматического доказательства теорем и эвристического поиска.
• Математическая логика: изучал вопросы разрешимости логических теорий.

Шахматная карьера

Параллельно с научной работой Адельсон-Вельский был сильным шахматистом-практиком. В 1950-х годах он участвовал в чемпионатах Москвы, выполнил норму кандидата в мастера спорта. В 1960-х годах входил в состав сборной Москвы по шахматам. Его лучший рейтинг по версии Международной шахматной федерации (ФИДЕ) составлял около 2300 пунктов.

Память и признание

• В 1975 году за создание «Каиссы» Адельсон-Вельский был удостоен премии Совета Министров СССР.
• АВЛ-дерево включено в стандартные учебники по алгоритмам и структурам данных во всём мире.
• В 2015 году в честь Георгия Адельсон-Вельского и Евгения Ландиса была названа премия AVL Award, вручаемая за выдающиеся достижения в области структур данных.
• В 2022 году, к 100-летию со дня рождения, в МГУ прошла международная конференция, посвящённая его научному наследию.

Источники

• Адельсон-Вельский Г. М., Ландис Е. М. «Алгоритм организации информации». Доклады АН СССР, 1962, том 146, № 2, с. 263–266.
• Кнут Д. Э. «Искусство программирования», том 3: «Сортировка и поиск». — М.: Вильямс, 2007.
• Ботвинник М. М. «О кибернетической цели игры». — М.: Советское радио, 1975.
• Некролог в журнале «Компьютерные инструменты в образовании», 2014, № 3.
• Статья «Каисса: первая советская шахматная программа» в сборнике «История вычислительной техники в лицах». — Киев: Феникс, 1998.