Ссылка на http://www.mathnet.ru
Георгий Максимович Адельсон-Вельский
Для многих из нас он был другом, учителем, старшим товарищем, коллегой. Талантливейший математик, ученый с разносторонними знаниями и интересами, человек с редчайшей скоростью и реактивностью мышления, он готов был включиться в любую проблему.
Георгий Максимович Адельсон-Вельский родился в Самаре 8 января 1922 г. В 1940 г. он поступил на механико-математический факультет МГУ.
В 1944 г., будучи студентом 4-го курса, Георгий Максимович обобщил теорему С.Н. Бернштейна о гладкой функции двух переменных, график которой имеет отрицательную кривизну. Г. М. ввел следующее определение: непрерывная функция двух переменных имеет обобщенную неположительную кривизну, если от ее графика никакой плоскостью нельзя срезать “шапочку”, т. е. если для всякой плоскости в R3 все компоненты связности, на которые плоскость разрезает график функции, неограничены.
Теорема [1]. Если функция f : R2 → R имеет обобщенную неположительную кри- визну, то либо она на бесконечности растет не медленнее, чем линейная функция, либо ее график является цилиндрической поверхностью,т.е. f(x,y)=g(ax+by).
Продолжая эти исследования, Г. М. Адельсон-Вельский совместно с A. C. Кронродом написал цикл работ [2]–[4] о геометрических свойствах функции двух перемен- ных, имеющих ограниченную гладкость. В [4] решена следующая проблема, настойчиво выдвигаемая Ж. Адамаром и Н.Н. Лузиным: доказать теорему Коши–Гурса (об аналитичности функции комплексного переменного, у которой в каждой точке есть производная), пользуясь лишь качественными свойствами функции (а не интегралом Коши). Эта работа удостоена премии Московского математического обще- ства за 1946 г. Согласно Л.А. Люстернику 1., именно из идеи этого цикла выросла геометрическая теория функций двух и многих переменных (работы А. С. Кронрода, А. Г. Витушкина и А. Н. Колмогорова). Крупнейшим достижением этого направления явилось решение А. Н. Колмогоровым и В. И. Арнольдом 13-й проблемы Гильберта.
Вопрос о непрерывном разложении гильбертова пространства на подпространства, инвариантные относительно всех операторов из некоторой алгебры R, был популярен в 1940–1950-х годах и – для сепарабельного случая – завершился двумя монографиями Ж. Диксмье. Основной вклад внесли Ф. Мюррей, Дж. фон Нейман, Э. Глисон, И. Сигал в Америке, П. Картье, Р. Годман (R. Godement), А. Вейль во Франции и (независимо, поскольку обмен информацией был сильно затруднен) И. М. Гельфанд, М. А. Наймарк и Г. М. Адельсон-Вельский в России.
В 1949 г. Георгий Максимович защищает кандидатскую диссертацию “Спектральный анализ кольца ограниченных линейных операторов гильбертова пространства”. Научным руководителем был И.М. Гельфанд, оппонентами – А.Н. Колмогоров и М.А. Наймарк. В этой работе было построено разложение нормированного кольца с инволюцией в прямой интеграл (обобщение прямой суммы) неприводимых колец ограниченных линейных операторов. Предположений о сепарабельности не делалось. М. А. Наймарк выделял три части работы:
1) конструкция разложения на независимые кольца;
2) контрпример, показывающий, что полученные компоненты не обязаны быть неприводимыми; 2.
3) конструкция, “подправляющая” представление до неприводимого.
Краткое изложение первой части опубликовано в [6]. Подробное изложение так и не было подготовлено для публикации и существует лишь в малодоступном тексте диссертации [5].
Банахово среднее на группе G – это правоинвариантный неотрицательный ли- нейный функционал L на пространстве ограниченных вещественных функций на G такой, что L(1) = 1. Пусть для всякого конечного множества E ⊂ G число всевозмож- ных произведений не более чем n (возможно, повторяющихся) элементов из E при n → ∞ растет медленнее, чем экспоненциально. В [7] доказано, что если это условие выполнено, то на G есть банахово среднее. Это условие выполнено для коммутатив- ных групп, но не выполнено для SO(3). На SO(3) банахова среднего нет: это вытекает из знаменитого примера Хаусдорфа (препятствующего существованию на единичной сфере нетривиальной SO(3)-инвaриaнтнoй конечноаддитивной меры, в которой изме- римы все подмножества). В [7] также дан (трудно проверяемый) критерий существования на группе G банахова среднего, мотивированный примером Хаусдорфа.
В 1955 г. Георгий Максимович поступил в Теплотехническую лабораторию Академии наук (ныне Институт теоретической и экспериментальной физики – ИТЭФ). Как математик и как математик-вычислитель он продуктивно работал вместе с физиками над задачей построения эффективного и надежного ядерного реактора, над анализом треков частиц в пузырьковой камере ускорителя, изучал модели ядерной физики и т. п. [8]–[10]. Эти годы стали поворотными в его жизни – он увлекся обширными возможностями и непривычными для чистого математика проблемами эффективного использования вычислительных машин.
Г. М. Адельсон-Вельский стоял у истоков, по крайней мере, двух научных направлений, играющих важнейшую роль в современной информатике. Первое – алгоритмы с полиномиальными оценками времени исполнения (далее – полиномиальные алгоритмы). Примерно до 1970 г. таких алгоритмов насчитывалось всего несколько десятков. К настоящему времени теоретиками разработаны многие тысячи таких алгоритмов. Именно они составляют основу практического применения информатики. Г. М. Адельсона-Вельского можно считать одним из отцов-основателей этой области.
В этом направлении им и его учениками выполнен ряд блестящих работ. Прежде всего надо отметить придуманные им вместе с Е.М. Ландисом сбалансированные деревья [11], известные теперь как АВЛ (Адельсон-Вельский и Ландис). Предназначенные первоначально для быстрого поиска повторяющихся позиций в играх, АВЛ-деревья стали прецедентным в мировой информатике примером нетривиальной эффективной структуры данных, изменяющейся при изменении самих данных. Они открыли путь целой череде методов организации динамических структур данных, таких как “расширяющееся” дерево, дерево отрезков, дерево Фенвика и т.п. – сейчас в информатике используются многие десятки, если не сотни динамических структур.
Задача быстрого поиска хорошо иллюстрируется в терминах поиска слова в обычном словаре, содержащем n слов. Для того чтобы найти заданное слово в таком словаре, требуется не более C log n операций (C зависит от модели вычислений и от максимально возможной длины слова). Возникает новая задача: как обеспечить быстрый поиск в словаре, состав которого постоянно меняется?
В ставшей классической для Computer Science работе Г. М. Адельсона-Вельского и Е. М. Ландиса [11] эта задача была решена. Оказывается, постоянно пополняемый словарь нужно упорядочивать не линейно (лексикографически), как это делается обычно, а представлять его в виде бинарного дерева с естественным упорядочением: правая ветвь уходит вверх, левая вниз. Дерево должно быть сбалансированным: т.е. глубина левой и правой ветвей в любой вершине должна отличаться не больше чем на единицу. Нахождение любого слова в таком дереве с n вершинами требует также C log n операций. Но, что важнее всего, как удаление, так и добавление слова в такое дерево требуют столько же операций. При этом, когда новое слово становится на свое место в естественно упорядоченном дереве (на это требуется C log n операций), дерево может стать разбалансированным: глубина правой ветви, исходящей из некоторой “разбалансированной” вершины, может отличаться от глубины левой ветви больше чем на единицу. Алгоритм АВЛ позволяет в этом случае перестроить дерево в окрестности “разбалансированной” вершины за конечное (не зависящее от n) число операций так, что оно снова станет сбалансированным.
Таким образом, в сбалансированном словаре возможен быстрый поиск слова и быстрое добавление или удаление слова; при этом словарь остается сбалансированным.
Примерно с 1970 г. началось бурное развитие полиномиальных алгоритмов вообще. Здесь роль Г. М. Адельсона-Вельского бесценна: он создал московскую школу полиномиальных алгоритмов, подарившую мировой науке немало важных достижений (см. ниже). Эта школа была одной из первых, если не первой такой школой в мире. Она была основана на широком знании и глубоком понимании мировой полиномиальной алгоритмики того времени, преподанных Георгием Максимовичем его ученикам. В особенности он делал упор на использование динамических структур данных для убыстрения счета. В течение многих лет начиная с 1969 г. Г. М. Адельсон-Вельский вел семинар по алгоритмам. Вначале – студенческий на мехмате МГУ, затем – исследовательский в ИПУ АН СССР. Фактически этот семинар был центром полиномиальной алгоритмики в Москве.
Школа Г. М. Адельсона-Вельского отличалась новаторским методом подсчета времени исполнения алгоритмов и операций структур данных. Общепринятый тогда способ оценки времени счета алгоритма был основан на оценке максимального времени счета одной итерации, умноженной на максимальное количество итераций. В сложных случаях этот метод дает завышенные оценки, препятствуя анализу и, тем самым, созданию новых, более быстрых алгоритмов. Георгий Максимович создал гораздо более мощный распределительный метод оценки времени счета. Стоимость (время исполнения) каждой содержательной операции или ее части распределяется – “записывается на счет” – одному из связанных с ней элементов одного из базисных множеств. Общее время рассчитывается как сумма по всем элементам всех базисных множеств. При этом базисными множествами могут быть множество итераций, множество вершин или ребер анализируемого графа и т. п.
В качестве примера динамической структуры данных, время работы которой оце- нивается с помощью распределительного метода, можно указать послойную справочную кратчайших путей Е.А. Диница для нахождения максимального потока в сети [12]. Она создается как вариант стандартного поиска в ширину (BFS), не отбрасывающий дублирующих потенциально нужных ребер. Послойная справочная находит пути, увеличивающие поток, на порядок быстрее других методов. Несмотря на то что исправление справочной на одной отдельно взятой итерации может быть очень дорогим, ее общее время исправления за все время ее существования не превосходит времени ее построения.
В настоящее время распределительный метод анализа общепринят в полиномиальной алгоритмике, но, к сожалению, в качестве фольклора, без упоминания первооткрывателя. Г. М. Адельсон-Вельский был первым, поэтому в 1960-х и в начале 1970-х этот метод был почти исключительным искусством московской школы алгоритмов. В середине 1970-х в отдельных работах на Западе был использован частично похожий метод анализа эффективности структур данных (см., например, [13]); этот метод был впервые последовательно изложен только в 1985 г. в статье [14] под названием амортизационного анализа.
Ученики Георгия Максимовича, получив от него мощные средства анализа алгоритмов, опубликовали такие значимые в информатике результаты, как “алгоритм четырех русских” [15], алгоритм сортировки без рабочей памяти [16], один из первых полиномиальных алгоритмов решения транспортной задачи [17], алгоритм [12] с оценкой [18], эквивалентный алгоритму Хопкрофта–Карпа для нахождения системы представителей множеств, новаторские алгоритмы для анализа изоморфизма графов [19] (о связанной с этим теории см. сборник под редакцией Б.Ю. Вейсфейлера [20]) и другие. Имена их авторов – формальных и неформальных учеников Георгия Максимовича – сейчас широко известны в мире: В. Л. Арлазаров, Б. Ю. Вейсфейлер, Е. А. Диниц, М. В. Донской, А. В. Карзанов, М. А. Кронрод, А. А. Леман, П. А. Певзнер (биоинформатик), И. А. Фараджев, Б. В. Черкасский и другие. Результаты учеников Георгия Максимовича по потоковым алгоритмам были изложены в книге [21] и по сей день входят во все учебники алгоритмики.
Подтверждением оригинальности методов, созданных Г. М. Адельсоном-Вельским и опережавших свое время, служит тот факт, что некоторые результаты, полученные в московской школе алгоритмики, были далеко не сразу поняты на Западе. Примерами могут служить как АВЛ-деревья, так и потоковый алгоритм Диница (историю непонимания последнего см. в [22]).
Другим важным и очень результативным направлением его деятельности был “искусственный интеллект” или, как тогда говорили, “эвристическое программирование”. Это, прежде всего, многолетняя работа над шахматной программой, которая в течение полутора десятилетий была лучшей в мире. В 1974 г. программа “Каисса” стала победителем первого чемпионата мира в Стокгольме. На ней отрабатывались многие общие методы работы с информацией, такие как рекурсивный перебор, отсечение на основе формальных (например, метод граней и оценок) и неформальных (например, форсированные варианты) соображений, организация справочных (поисковые деревья, хэш-таблицы и т. п.).
Было проведено исследование следующего фундаментального вопроса теории игр с полной информацией. Еще Цермело показал, что если представлять такую игру в виде дерева, на листьях которого написаны оценки (результат игры), то существуют алгоритм (минимаксная процедура), определяющий оценку начальной позиции – корня дерева, и оптимальная для каждого из противников стратегия, ведущая к этой оценке. Отсюда, в частности, следует, что в любой шахматной позиции исход партии при оптимальной игре противников предопределен.
Однако в реальности ни одна программа не доводит расчет до финальной позиции, а ограничивается обходом некоторого поддерева игры на определенную глубину. Конечные позиции этого поддерева оцениваются эвристически. Кажется очевидным, что - при “разумной” оценке – чем глубже рассматриваемое дерево, тем лучше будет играть программа. Оказывается, это не всегда верно.
В работе [23] Г.М. Адельсон-Вельский, В.П. Акимов и В.Л. Арлазаров доказали, что существуют определенные границы на “разумность” эвристической оценки, понимаемую как вероятность ее близости к правильной, при которой углубление перебора имеет смысл. Иными словами, если эта вероятность достаточно велика, то при углублении перебора она будет увеличиваться, в противном случае – уменьшаться. Интересно, что вычисляемая для простейших случаев граница “разумности” оценки далека от интуитивной.
Еще одним важным результатом разработки шахматной программы была теория и практическая реализация “геометрической декомпозиции” перебора или, как сказали бы теперь, “извлечения знаний” из перебора. Одной из главных проблем, препятствующих углублению перебора, является наличие большого числа повторяющихся поддеревьев, обход которых занимает львиную долю общего времени выбора хода.
Г. М. Адельсон-Вельский и М. Донской (см., например, [24]) показали, как связать с каждым поддеревом A позиции Pi систему полей доски Q(Pi) со следующим свойством: если позиция Pj является корнем другого поддерева, но множество полей, затронутых изменениями позиции Pj по сравнению с Pi, имеет пустое пересечение с Q(Pi), то поддерево A будет в точности повторено в позиции Pj и принесет ту же оценку, что и в Pi. Знания, полученные в переборе из позиции Pi, могут, таким образом, быть использованы в других позициях.
Докторская диссертация “Метод структурных графов для задач дискретной оптимизации” была защищена в 1974 г. в Институте проблем управления (Москва). В нее вошли результаты, полученные во время работы над шахматной программой, а также некоторые результаты по потоковым алгоритмам и сетевому планированию.
Г. М. Адельсон-Вельский внес важный вклад и в математическое образование школьников. Он был соавтором первого издания “Избранных задач и теорем элементарной математики”, сборника задач олимпиадного уровня, много лет использовавшегося в работе математических кружков [25]. Середина 1960-х годов стала счастливым временем для школьного математического образования в СССР. У математиков появилась возможность учить детей не только в кружках, но и прямо на школьных уроках. Помимо четырех интернатов при университетах, “математическими и про- граммистскими” стали и некоторые “обычные” городские школы. Вместе с А. С. Кронродом и Н. Н. Константиновым Георгий Максимович преподавал в одной из первых математических школ в России – московской школе No 7. Свою цель он однажды сформулировал так: “Я хочу помочь детям стать свободными людьми”. Стиль обучения был “задачный”, наследующий традицию математических кружков, содержание – основы математического анализа (или ТФДП, сказывалось влияние Кронрода – уче- ника Н.Н. Лузина). На практике Г.М. Адельсон-Вельский реализовал свой подход в 1964–1966 гг. вместе со своими младшими коллегами А. Леманом, Л. Лимановым, М. Якобсоном и блистательным школьным учителем математики И. И. Юдиной. Один из выпускников математического класса свидетельствует: “Г. М. учил нас стремиться к истине ради истины, хотя сам бы так не сказал: высокопарность была ему совершенно чужда”. Традиция, созданная тогда при участии Г. М. Адельсона-Вельского и продолжаемая, прежде всего, учениками учеников Н. Н. Константинова, является важнейшей для роли математики в российской школе по сей день.
Георгий Максимович был убежден, что коммерция убивает программирование: “Грандиозная наука – математика – построена без коммерции. А когда на первый план выходят права собственности, дух коллективного творчества отступает, и вели- кий творец – коллектив ученых – теряет силу”.
Книга “Дискретная математика для инженера”, написанная Георгием Максимовичем совместно с О. П. Кузнецовым (1-е издание – 1980 г.) сыграла важную роль в становлении современного математического фундамента компьютерных наук в технических вузах. Тогда это была единственная книга на русском языке, где систематически излагались все основные разделы дискретной математики, вплоть до основных понятий теории вычислительной сложности, в то время мало известной широкому кругу преподавателей технических вузов. Неудивительно, что, несмотря на тираж 25 000 экз., она уже через 3–4 года стала библиографической редкостью. Английский перевод первого издания вышел в 1985 г. В 1988 г. вышло 2-е, дополненное издание. В частности, в этом издании было дано первое в учебной литературе изложение полиномиального алгоритма Хачияна для решения задачи линейного программирования.
Последняя работа была написана в 2002 г. [26]. В это время Георгий Максимович был профессором Бар-Иланского университета в Израиле, куда он переехал в 1992 г. После тяжелой продолжительной болезни, 26 апреля 2014 г., Георгий Максимович Адельсон-Вельский скончался в Тель-Авиве, на 93-м году жизни.
Он навсегда останется в нашей памяти примером искрометного таланта, скромности, трудолюбия и бескомпромиссной честности.
В.Л. Арлазаров, Е.А. Диниц, Ю.С. Ильяшенко, А.В. Карзанов, С.М. Карпенко, А.А. Кириллов, Н.Н. Константинов, М.А. Кронрод, О.П. Кузнецов, Л.Б. Окунь, П.А. Певзнер, А.Л. Семенов, И.А. Фараджев, Б.В. Черкасский, А.Г. Хованский
Список литературы
[1] G. Adelson-Welsky, “G ́en ́eralisation d’un th ́eor`eme geom ́etrique de M. Serge Bern- stein”, Докл. АН СССР, 49 (1945), 391–392.
[2] G.M. Adelson-Welsky, A.S. Kronrode, “Sur les lignes de niveau des fonctions continues poss ́edant des d ́eriv ́ees partielles”, Докл. АН СССР, 49:4 (1945), 235–237.
[3] G.M. Adelson-Welsky, A.S. Kronrode, “Sur le principe du maximum pour les solutions d’un syst`eme d’ ́equations a` d ́eriv ́ees partielles du type elliptique”, Докл.
АН СССР, 49 (1945), 539–541.
[4] Г.М.Адельсон -Вельский,А.С.Кронрод,“Прямое доказательство аналитичности моногенной функции”, Докл. АН СССР, 50 (1945), 7–9.
[5] Г.М. Адельсон-Вельский, Спектральный анализ кольца граничных линейных операторов, Дисс. . . . канд. физ.-матем. наук, МГУ, М., 1948.
[6] Г.М. Адельсон-Вельский, “Спектральный анализ кольца ограниченных линейных операторов гильбертова пространства”, Докл. АН СССР, 67 (1949), 957–959.
[7] Г.М. Адельсон-Вельский, Ю.А. Шрейдер, “Банахово среднее на группах”, УМН,
12:6(78) (1957), 131–136.
[8] А.С. Кронрод, Г.М. Адельсон-Вельский, Численные расчеты критических размеров реактора, в кн: А.Д. Галанин, Теория ядерных реакторов на тепловых нейтронах, Атомиздат, М., 1957, 169–183.
[9] Л. Л. Гольдин, Г. М. Адельсон-Вельский, А. П. Бирзгал, А. Д. Пилия, К. А. Тер-Мартиросян, “α-распад несферических ядер”, ЖЭТФ, 35:1 (1958), 184–202;
англ. пер.: L. L. Gol’din, G. M. Adel’son-Vel’skij, A. P. Birzgal, A. D. Piliya, K.A. Ter-Martirosyan, “Alpha decay of nonspherical nuclei”, Soviet Phys. JETP, 8 (1959), 127–139.
[10] I. I. Levintov, G. M. Adelson-Velsky, “Real part of the p–p forward scattering amplitude of high energies”, Phys. Lett., 13:2 (1964), 185–187.
[11] Г.М. Адельсон-Вельский, Е.М. Ландис, “Один алгоритм организации информации”, Докл. АН СССР, 146:2 (1962), 263–266.
[12] Е.А. Диниц, “Алгоритм решения задачи о максимальном потоке в сети со степенной оценкой”,Докл.АНСССР,194:4(1970),754–757; англ.пер.:E.A.Dinic, “Algorithm for solution of a problem of maximum flow in a network with power estimation”, Soviet Math. Dokl., 11 (1970), 1277–1280.
[13] R.E. Tarjan, “Efficiency of a good but not linear set union algorithm”, J. Assoc. Comput. Mach., 22:2 (1975), 215–225.
[14] R.E. Tarjan, “Amortized computational complexity”, SIAM J. Algebraic Discrete Methods, 6:2 (1985), 306–318.
[15] В.Л.Арлазаров,Е.А.Диниц, М.А.Кронрод, И.А.Фараджев,“Об экономном построении транзитивного замыкания ориентированного графа”, Докл. АН СССР,
194:3 (1970), 487–488; англ. пер.: V. L. Arlazarov, E. A. Dinic, M. A. Kronrod, I. A. Faradˇzev, “The economical construction of the transitive closure of an oriented graph”, Soviet Math. Dokl., 11 (1970), 1209–1210.
[16] М.А. Кронрод, “Оптимальный алгоритм упорядочения без рабочей памяти”, Докл. АН СССР, 186 (1969), 1256–1258; англ. пер.: M.A. Kronrod, “Optimal ordering algorithm without operational field”, Soviet Math. Dokl., 10 (1969), 744–746.
[17] Е.А.Диниц,“Алгоритм поразрядного сокращения невязок и транспортные задачи”, Исследования по дискретной математике, ред. А.А. Фридман, Наука, М., 1973, 46–57.
[18] А.В. Карзанов, “Точная оценка алгоритма нахождения максимального потока, примененного к задаче о ‘представителях’ ”, Вопросы кибернетики. Tруды семинара по комбинаторной математике (1971), Изд-во Научного совета АН СССР по кибернетике, М., 1973, 66–70.
[19] Г.М. Адельсон-Вельский, Б.Ю. Вейсфейлер, А.А. Леман, И.А. Фараджев, “Об одном примере графа, не имеющего транзитивной группы автоморфизмов”, Докл. АН СССР, 185 (1969), 975–976; англ. пер.: G.M. Adel’son-Vel’skii, B. Ju. Veisfeiler, A. A. Leman, I. A. Faradˇzev, “An example of a graph which has no transitive group of automorphisms”, Soviet Math. Dokl., 10 (1969), 440–441.
[20] On construction and identification of graphs, with contributions of A. Lehman, G.M. Adelson-Velsky, V. Arlazarov, I. Faragev, A. Uskov, I. Zuev, M. Rosenfeld, B. Weisfeiler, Lecture Notes in Math., 558, ed. B. Weisfeiler, Springer-Verlag, Berlin–New York, 1976, xiv+237 pp.
[21] Г.М. Адельсон-Вельский, E.A. Диниц, А.В. Карзанов, Потоковые алгоритмы, Наука, М., 1975, 119 с.
[22] Y. Dinitz, “Dinitz’ algorithm: the original version and Even’s version”, Theoretical computer science, essays in memory of Shimon Even, Lecture Notes in Comput. Sci., 3895, eds. O. Goldreich, A. L. Rosenberg, A. L. Selman, Springer, Berlin, 2006, 218–240.
[23] Г.М.Адельсон-Вельский, В.П.Акимов, В.Л.Арлазаров, “Овероятностном подходе к обоснованию игровой модели Шеннона”, Автомат. и телемех., 1980, No 9, 138–144; англ. пер.: G. M. Adel’son-Vel’skii, V. P. Akimov, V. L. Arlazarov, “On a probabilistic approach to verification of the Shannon game model”, Autom. Remote Control, 41:9 (1981), 1299–1304.
[24] Г.М. Адельсон-Вельский, В.П. Арлазаров, М.В. Донской, Программирование игр, Наука, М., 1978, 225 с.; англ. пер.: G.M. Adelson-Velsky, V.L. Arlazarov, M. V. Donskoy, Algorithms for games, Springer-Verlag, New York, 1988, x+197 pp.
[25] Д.О.Шклярский, Г.М.Адельсон-Вельский, Н.Н.Ченцов, А.М.Яглом, И.М.Яглом, Избранные задачи и теоремы элементарной математики, Библиотека ма- тематического кружка, 1, Гостехиздат, М., 1950, 296 с.
[26] G. Adelson-Velsky, A. Gelbukh, E. Levner, “On fast pathfiding algorithms in AND-OR graphs”, Math. Probl. Eng., 8:4-5 (2002), 283–293.
___________________________________________________
1. Л.А. Люстерник, Отзыв о работах Г.М. Адельсона-Вельского.
2. Это возможно только в случае несепарабельного кольца (см. [5; с. 58]).