Shared on 10th May 2014

On lines of level of continuous functions having partial derivatives, (with A. Kronrod), DAN SSSR, 49, no. 4, (1945).

Generalization of a theorem of Bernstein, DAN SSSR, 49, no. 6, (1945).

On the maximum principle for solutions of systems of elliptic equations, DAN SSSR, 49, no. 8, (1945).

On the direct proof of analycity of monogenic functions, DAN SSSR, 50, (1945).

Spectral analysis of rings of bounded operators of Hilbert space, Dissertation, (1949).

Spectral analysis of rings of bounded operators of Hilbert space, DAN SSSR, 67, no. 6, (1949).

Selected Problems and Theorems of Elementary Mathematics, (with D. Shkliarsky, N. Chentsov, A. Yaglom, and I. Yaglom), Gostekhizdat, Moscow, (1950). (1st edition)

Calculations of critical size of reactors, (with A. Kronrod), in: "Theory of Nuclear Reactors on Thermal Neutrons", by A. Galanin, Atomic Energy, Moscow, (1957).

Banach mean on groups, (with Yu. Shreider), Uspekhi matem. nauk, 12, no. 2, (1957).

Alpha-Decay of non-spherical nuclei, (with L. Goldin et al.), Zhurn. teoret. i eksp. fiziki, 35, no. 1(7), (1958).

An algorithm for information organization, (with E. Landis), DAN SSSR, 146, no. 2, (1962).

A chess playing program, ( with V. Arlazarov and A. Uskov), Proc. of Int. Symp. by Upper Mantle, (1963).

On choice of extrema of many variables functions, (with F. Filler), ibid., (1963).

Real part of the p-p forward scattering amplitude of high energies, (with I. Levintov), Physics Letters,, 13, no. 2, (1964).

On a system of instructions for 3-address computer, (with A. Kronrod et al.), DAN SSSR, 154, no. 3, (1964).

A library of standard programs B-61, (with A. Kronrod et al.), preprint, (1965).

A program for calculation of networks, (with F. Filler), Zhurnal Vychisl. matem. i matem. fiziki, 5, no. 1, (1965).

On an algorithm of the quick choice of pseudo maxima of functions given on an integer-valued lattice, (with P. Kunin and A. Leman),DAN SSSR, 168, no. 3, (1966).

On a class of teaching algorithms of pattern recognition,  (with P. Kunin and A. Leman), DAN SSSR, 173, no. 2, (1967).

Systems of information for description of partial ordered sets, in: "Cybernetics for service of communism", Nauka, Moscow, (1967).

On Chess program of IT&EF, (with V. Arlazarov et al. ), preprint, (1967).

A program for calculation of networks, (with F. Filler), in: "Collection of algorithms and programs", Statistika, Moscow, (1967).

Chess as "a drosofile" for heuristic programming, (with V. Arlazarov and M. Donskoy), Priroda, no. 2, (1968).

Computer-Chess USSR-USA, (in German), Wissenschaft und Technik, no. 19, (1968).

Determination of minimum duration of a project if limitation of an unperservable resource is given, (with S. Kalinovskaya), Trudy 1-y zimney shkoly po matem. programmirovaniyu, (1969).

On choice of extrema of many variables functions, (with F. Filler), ibid,, (1969).

On programming of Chess, (with V. Arlazarov et al.), ibid., (1969).

An information-logical model of a building firm, (with E. Dymshits et al.), Trudy 2-y zimney shkoly po matem. programmirovaniyu, (1969).

Networks with variable durations of works, (with S. Kalinovskaya), ibid., (1969).

Systems of mappings, (with S. Kalinovskaya), ibid., (1969).

Realization of a way for the exactness Estimation of parameters of a many variables function received in the result of Experiments working up, (with N. Beketova), preprint (1969).

Example of a graph without a transitive automorphism group, (with I. Faradgev, A. Leman, and B. Weisfeiler), DAN SSSR, 185, no. 5 (1969) and Soviet Math. Dokl., vol. 10, no.2, (1970).

On programming computers to play Chess, (with V. Arlazarov et al.), Uspekhi matem. nauk, 25, no. 2 (152), (1970).

Minimum quantity of operations for estimation of positions, (with S. Kalinovskaya), Trudy 3-y zimney shkoly po matem. programmirovaniyu, (1970).

The problem of technologies, (with S. Kalinovskaya), ibid., (1970).

On structure of economical Information Systems, (with S. Kalinovskaya), ibid., (1970).

Heuristic Programming, (with V. Arlazarov, M. Bongard, and S. Lavrov), Trudy 2-y soviet konf. po programmirovaniyu, (1970).

On programming computers to play Chess, (with V. Arlazarov), ibid., (1970).

Research of mechanism of dehydration of isopenthane by iodine in presence of oxygen, (with S. Adelson), DAN SSSR, 192, no. 3, (1970).

On structure of economic Information Systems, (with S. Kalinovskaya), Matem. programmirovaniye i raschet stroitelnykh konstruktsiy, 83, (1971).

Generalized networks for building, (with S. Kalinovskaya and V. Voropayev), Na stroykakh Rossii, no. 4, (1971).

Ways of calculating of generalized networks, ( with S. Kalinovskaya and V. Voropayev), Na stroykakh Rossii, no. 5, (1971).

Ways of calculation of the inverse matrix to a matrix of partial derivatives, (with N. Beketova and I. Chernyshova), Factory laboratory, no. 1, (1971).

Realization of a method of the mistakes estimating, (with N. Beketova), in: "Some Problems of General and Applied Physics", Nauka, Kazakh. SSR, (1972).

Who will go to Rio, (with J. Bernstein and M. Gerver), Kvant, no. 8, (1972).

Optimal Control of parameters of building for explosion-dangerous factories, (with I. Razdolsky and M. Strizhevsky), Trudy 4-y zimney shkoly po matem. programmirovaniyu, (1972).

Generalized networks, (with S. Kalinovskaya and V. Voropayev), ibid., (1972).

Problems of Software for automatic control in hydro-technical building, (with S. Kalinovskaya and V. Voropayev), in: "Mathematical Methods in Economics", Zinatne, Riga, no. 9, (1972).

Structure and contents of Software for automatic Control, (with S. Kalinovskaya and V. Voropayev), Trudy akademii selskokhoz. nauk Latv. SSR, (1972).

Some questions of network scheduling, in: "Collection of Researches in Discrete Mathematics", Nauka, Moscow, (1973). Исследования по дискретной математике : [сб. науч. тр. / отв. ред. А. А. Фридман]. - М. : Наука, 1973.

On estimation of the quantity of operations for determination of a partial order, (with J. Bernstein and M. Gerver), ibid., (1973).

On 4-chromatic cubic graphs, (with V. Titov), Voprosy kibernetiki, Trudy seminara po diskretnoy matematike, Nauka, Moscow, (1973).

Methods for strengthening of chess programs, (with V. Arlazarov), Problemy kibernetiki, 29, (1974).

More commentary on the Chichelly Heuristics, (with V. Arlazarov and M. Donskoy), Sigart, 45 no. 6, (1974).

Ways of modeling of planning works, (with R. Rappoport et al.), Ekonomika i matem. metody, 11, no. 2, (1975).

Flow Algorithms, (with E. Dinitz and A. Karzanov), Nauka, Moscow, (1975).

Some Methods of controlling the Tree Search in Chess Programs, (with V. Arlazarov and M. Donskoy), Artificial Intelligence, no. 6, (1975).

Chess Programming, (with V. Arlazarov and M. Donskoy), Proc. of 4-th Artificial Intelligence Conf., (1975).

On the Structure of an important Class of exhaustive Problems and on the ways of Search Reduction for them, (with V. Arlazarov and M. Donskoy), ibid., (1975). Advances in Computer Chess v. 1, 1977

Block-module Programming, (with E. Dinitz, N. Yemelyanov, and M. Furman), in: "Multiprocessing Computer Systems", Nauka, Moscow, (1975).

Possibilities of the equipment application for Improving of effectiveness of Programming, (with A. Volkov et al.), ibid., (1975).

On construction and identification of graphs, (with B. Weisfeiler et al.), Lecture Notes in Mathematics, 558, Springer-Verlag, (1976). Подтверждение?

On the structure of an important class of exhaustive problems and on the ways of search reduction for them, (with V. Arlazarov and M. Donskoy), Advances in Computer Chess, 1, (1977).

Methods of adaptive Search, (with V. Arlazarov and M. Donskoy), Rep. of Int. Conf. in Artificial Intelligence in Repino, (1977).

On the method of purposeful game for Search Reduction in Chess programs, (with A. Futer), ibid., (1977).

Programming of Chess, (with V. Arlazarov and M. Donskoy), Vestnik Akademii nauk SSSR, no. 4, (1978).

Algorithms of adaptive search, (with V. Arlazarov and M. Donskoy), Machine Intelligence, 9, (1978).

Programming for Games, ( with V. Arlazarov and M. Donskoy), Nauka, Moscow, (1979).

Principles of Creation of Chess Programs, (with V. Arlazarov and M. Donskoy), Priroda, no. 7, (1979).

On probabilistic approach to modeling two-player games with complete Information, (with V. Arlazarov), Semiotika i informatika, no. 12, (1979).

On applying of probabilistic Approach for Improving of quality of Program for two-player Games with complete Information, ( with V. Akimov, V. Arlazarov, and N. Kosacheva), ibid., (1979).

On probabilistic approach to substantiate Shannon's model, (with V. Akimov and V. Arlazarov), Avtomatika i telemekhanika, no. 9, (1980).

Discrete Mathematics for Engineers, (with O. Kuznetsov), Energoizdat (1-st ed.), (1980).

What can we go with Problems of exhaustive Search, (with A. Slisenko), Lecture Notes in Computer Science, Proc. Urgench Uzbek SSR Algorithms in Modern Math. Conf., Springer-Verlag, (1981).

Machine plays Chess, (with V. Arlazarov, A. Bitman, and M. Donskoy), Nauka, Moscow, (1983).

Discrete Mathematics for Engineers, (with O. Kuznetsov), Gordon and Breach Science Publishers, New York, London, et al., (1985).

Г. М. Адельсон-Вельский, В. П. Акимов, “К обоснованию игровой модели Шеннона”, Автомат. и телемех., 1987, № 1, 171–173

Discrete Mathematics for Engineers, (with O. Kuznetsov), Energoizdat, (2-nd ed.), Moscow, (1988).

Algorithms for Games, (with V. Arlazarov and M. Donskoy), Springer-Verlag, (1988).

On forming of algorithms for machine to play Chess, ( with A. Bitman), Izvestia Akademii nauk SSSR, Tekhnicheskaya kibernetika, no. 2, (1988).

Non-Shannonian algorithms of search, (with V. Akimov), Izvestia Akademii nauk SSSR, Tekhnicheskaya kibernetika, no. 3, (1988).

Analysis of data models within the frames of uniform formalization, (with V. Arlazarov), Sbornik trudov VNIISI, 22, (1988).

Machine plays Chess (in Latvian), (with V. Arlazarov, A. Bitman, and M. Donskoy), Zinatne, Riga, (1991).

Interdisciplinary efforts in application tasks solution, Systemnyye issledovaniya, Metodol. problemy, Yezhegodnik 1989-1990, Nauka, Moscow, (1991).

On a game of players with memory, (with V. Levit), preprint, (1994).

On Design of Software Systems capable of Self-Improvement during the Expert-Machine Dialogue. Proceedings of the Int. Workshop "Intelligent Scheduling of Robots and Flexible Manufacturing Systems" (Holon, Israel,July 2, 1995), CTEH Press, (1995).

On difficulties of Programming for parallel computers. Proceedings of the Int. Workshop "Intelligent Scheduling of Robots and Flexible Manufacturing Systems" (Holon, Israel, June 5, 1996), CTEH Press, (1997).

On the ways to form heuristic Algorithms and Programs. Proceedings of the Int. Workshop "Intelligent Scheduling of Robots and Flexible Manufacturing Systems" (Holon, Israel, June 5, 1996), CTEH Press, (1997).

Some remarks about machine Learning. preprint, (1998).

On the earliest times of the events determined by and-or graphs. preprint, (1999).

On the and-or graphs with non-negative lengths of the arcs (the paper was sent in the Journal of Operation Research), (2000).

On Fast Path-Fiding Algorithms in AND-OR Graphs (with Alexander Glebukh and Eugene Levner) Mathematical Problems in Engineering, 2002, Vol. 8(4-5), pp. 283-293

Некролог Ефима Диница

Shared on 10th May 2014

English original:

Георгий Максимович (Гера, Жора) Адельсон-Вельский умер вчера, в возрасте 92 лет.

Гера - легендарный основатель двух знаменитых советских научных школ в области Computer Science: одна занималась алгоритмами и структурами данных, другая - программированием шахмат. Обе возникли еще до появления самого термина Computer Science.

Его АВЛ-деревья (совместно с Е.М.Ландисом) были одним из первых, основополагающих примеров динамической структуры данных. В целом, его подход к эффективным алгоритмам базировался на амортизационном анализе времени выполнения. Этот способ анализа был воспринят на Западе существенно позднее. На его идеях учились авторы таких замечательных работ, как “алгоритм четырех русских”, алгоритм сортировки без использования дополнительной памяти, алгоритмы решения задач о потоках в сетях, работ по изоморфизму графов (теоретических и алгоритмических), биоинформатике, и других. Его подход настолько обгонял принятый  тогда на Западе, что некоторые его алгоритмы, как и алгоритмы его последователей в Советском Союзе, слабо понимались в то время на Западе.

Гера, вместе с А.Л.Брудно, инициировал развитие теории программирования игр в СССР, одновременно с появлением аналогичных работ на Западе. Советский проект по программированию шахмат (который он возглавлял совместно с В.Л.Арлазаровым и М.В.Донским) увенчался созданием программы “Каисса” - чемпиона мира среди шахматных программ.

Его учениками (формально или неформально) были: В.Арлазаров, Е.Диниц, М.Донской, И.Фараджев, А.Карзанов, М.Кронрод, А.Леман, П.Певзнер, Б.Вейсфеллер, и многие другие.

Г.М.Адельсон-Вельский останется в истории Computer Science как один из ее отцов-основателей

Ефим Диниц, ученик Геры с 1968 года
Отделение Computer Science университета Бен-Гуриона

Научная автобиография

Shared on 10th May 2014

Первая научная работа была сделана мной в 1944 г., когда я был студентом 4-го курса. Я обобщил одну теорему С.Н. Бернштейна о порядке роста значений функции двух переменных, чей график в трехмерном пространстве значений аргументов и функций имеет отрицательную кривизну, заменив это требование другим, не предполагающим существования производных у рассматриваемых функций: отсутствием ограниченных связных частей во множестве точек любой плоскости этого трехмерного пространства, полученного в результате исключения точек ее пересечения с графиком рассматриваемой функции. Работа получила 3-ю премию на конкурсе студенческих научных работ. Этот подход и его результат были использованы в следующем году в совместном с A.С. Кронродом решении проблемы, поставленной Лузиным: доказать, что моногенная в некоторой области функция аналитична в этой области, пользуясь только ее качественными свойствами, а не интегралом Коши. За эту работу мы получили премию Московского Математического Общества.

Я защитил кандидатскую диссертацию в 1948 г. "Спектральный анализ кольца ограниченных линейных операторов Гильбертова пространства", где было построено интегральное разложение такого кольца (если в него вместе с каждым оператором входит результат его инволюции) на почти неприводимые представления и дан пример, когда такого разложения на неприводимые представления не существует.

Через 11 лет после окончания аспирантуры я занялся решением прикладных задач физики, химии и математической экономики. Из 24 опубликованных работ на эти темы (1957-1975 гг.) можно отметить следующие.

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

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

В статье "Некоторые вопросы сетевого планирования" была исследована модель, когда продолжительность работы зависит от времени ее начала.

Я не упоминаю многих задач, решенных с моим участием, так как не считаю, что при их решении были использованы принципиально новые методы. В то же время были выполнены многие работы, связанные проблемами и потребностями программирования. В первую очередь следует отметить разработанную совместно с В. Л. Арлазаровым и почти не опубликованную систему стандартов для создания программ (кое-что есть в статье "Блочно-модульное программирование", опубликованной в сборнике "Многопроцессорные компьютерные системы"). Эти работы были начаты A.С. Кронродом и A.Л. Брудно, но строгое соблюдение глубоко разработанной системы стандартов — это наш вклад. Применение стандартов дает возможность создавать эффективные программы и, особенно, системы программ: так стандартные программы, созданные нами для машины М20 требуют меньше памяти и работают быстрее, чем программы альтернативной системы.

Раньше, чем на Западе, мы разработали метод организации программ, которые могут использовать себя, как подпрограмму и как подпрограммы своих подпрограмм. Вместо системы списков, использующей язык LISP, мы разработали удобные стандарты программирования списков (это же сделал Д. Кнут, но после нас).

Наконец, следует отметить конструкцию текущей справочной, разработанную E.M. Ландисом и мною, для которой количество элементарных действий, как для включения нового элемента информации, так и для исключения старого пропорционально логарифму объема справочной.

Ряд работ, посвященных выяснению, изоморфны ли 2 данных графа, выполнены совместно с коллективом сотрудников лаборатории A. С. Кронрода. Их результаты собраны в книге "On construction and identification of graphs" (главный автор Б. Вейсфейлер).

Новый подход к исследованию задач о потоках был использован в книге "Потоковые алгоритмы", написанной моими учениками E. A. Диницем и A. В. Карзановым совместно со мною.

Проблемами искусственного интеллекта я начал заниматься в 1957 г. Эти проблемы стали главными для меня. Я был участником создания некоторых программ для решения этих проблем (игра в подкидного дурака в 1957 г., шахматные программы 1961-1970 гг., программы для медицинской дифференциальной диагностики в 1966-67 гг.). Этим вопросам посвящены 2 статьи (совместно с П.Е. Куниным и A.А. Леманом) и 25 работ, выполненных в сотрудничестве с В.Л. Арлазаровым, A.Р. Битманом и M.В. Донским (соавтор одной из работ — А.Л. Футер). Среди них 2 книги: "Программирование игр" и "Машина играет в шахматы". Первая переведена на английский язык. Кроме нее, переведена книга "Дискретная математика для инженеров" (авторы О.П. Кузнецов и я). Следует отметить еще статью "Межпрофессиональное взаимодействие при решении прикладных задач" (1991), где я изложил свой опыт. Однако меня больше интересуют проблемы взаимодействия человека с машиной. Здесь я не могу положиться на свой опыт, так как я долго был программистом и не смог найти контакта с психологами, чтобы исследовать взаимодействие обыкновенного человека с машиной.

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