Д. Кнут - Искусство программирования том 4 выпуск 4 - 2007 (1119377), страница 21
Текст из файла (страница 21)
Если бы он имел немного больше способностей к математике по сравнению с тем, чем был наделен на самом деле, германская математика процветала бы именно в Лейпциге, а не в Берлине и Геттингене. Однако первая же математическая работа Гинденбурга, ВеэсЬге1Ьппя ешег яапя пепеп Агг, пасЬ ешет Ьейаппгеп Сеяегяе гог18нЬепйе ЯаЫеп дпгсЬ АЬяаЫеп обжег АЬшеамп Ье9иет ипд з!сЬег гп лаев (1е1рз18, 1776), достаточно ярко показала, чего следует ожидатгн его "йапя пепе" (совершенно новая) идея заключалась в придании комбинаторного смысла цифрам десятичной записи чисел. Невероятно, но Гинденбург завершил свою монографию большими таблицами — таблицей чисел от 0000 до 9999, после которой следовали таблицы четных и нечетных чисел в отдельности (!). Гинденбург публиковал письма людей, хваливших его работу, и приглашал нх писать статьи в его журналы.
В 1796 году он редактировал Яапип)ппя сошЫпаГопясЬвпа)ут1ясЬег АЬЬапд1ипбеп, где в подзаголовке было указано, что теорема о полиномах де Муавра "является наиболее важной во всем математическом анализе". Около десятка людей объединили свои усилия и образовали то, что впоследствии сделано для гяггцьк! пГапаса.ого 7.2.1 ГЕНЕРАЦИЯ ОСНОВНЫХ КОМВИНАТОРНЫХ ОБ'ЬЕКТОВ 91 стало известно как "школа комбинаторики Гинденбурга", и опубликовали тысячи страниц, заполненных эзотерическим символизмам, поражавшим воображение множества людей, не имеющих отношения к математике.
С точки зрения информатики работа этой школы не может считаться совершенно тривиальной. Например, лучший студент Гинденбурга, Г.А. Роте (Н.А. Но1Ье), заметил, что имеется простой способ перейти от последовательности кода Морзе к следующей за ней в лексикографическом порядке или к предшествующей. Другой ученик, И.К. Буркхардт (З.С. ВигЬЬагог)„заметил, что последовательности кодов Морзе длиной и могут быть легко сгенерированы, если сначала рассмотреть коды без тире, затем с одним тире, далее с двумя и т.д. Их целью была не табуляция стихотворных форм с п тактами, как это делалось в Индии, а перечисление членов континуантов К(хм хю..., х„), формула 4.5.3-(4).
[См. АгсЬп йг геше ипд апйе. яапдге Магйешагй, 1 (1794), 154-194.) Кроме того, на с. 53 упоминавшегося выше Баппп1ппя Г.С. Клюгель (О.Б. К1цйе1) привел способ перечисления всех перестановок, который впоследствии получил название алгоритма Орд-Смита (Огп-Бш11Ь); см, формулы (23)-(26) в разделе 7.2.1.2. Гинденбург верил, что его методы заслуживают достойного места в учебных курсах алгебры, геометрии и вычислений. Однако и он, и его ученики ограничивались в своих работах составлением списков комбннаторных объектов. Закопавшись в своих формулах и формализме, им редко удавалось открыть что-то действительно интересное с точки зрения математики. Эжен Нетто (Епбеп Непо) замечательно охарактеризовал нх работу в СеэсИсЬге г(ег МагЬешапй М.
Кантора (М. Сап1ог), 4 (1908), 201-219: "Какое-то время они контролировали германский рынок, но большинство из того, что они откопали, тут же засьпило песком забвения". Грустным итогом их исследований стало то, что в результате комбинаторика в целом стала восприниматься как лженаука. Геста Миттаг-Леффлер (Созга МййабЬе(()ег), собравший великолепную библиотеку математической литературы примерно через 100 лет после смерти Гинденбурга, решил поместить все такие работы на отдельной полке, помеченной "Декаденс". Эта категория осталась в шведском институте Миттаг-Леффлера и сегодня, несмотря на то что этот институт привлекает со всего мира математиков, работающих в области комбинаторики, труды которых можно назвать как угодно, но никак не упадничеством. Во всем есть хорошая сторона, н мы можем отметить, как минимум, одну хорошую книгу, появившуюся в результате всей этой деятельности.
Это Ие сошЬшасог!ясЬе Апа)уя1я (Ч1еппа, 1826) Андреаса фон Эттингсхаузена (Апдгеав топ ЕП(п8- яЬапяеп), заслуживающая внимания как первая книга, в которой методы генерации комбинаторных объектов рассматриваются ясно и последовательно. Эттингсхаузен рассмотрел общие принципы лексикографической генерации в 3 8 и применил их для построения метода перечисления всех перестановок (1 11), сочетаний (3 30) и разбиений (3 41-44). А где же деревьи7 Итак, мы уже видели, что на протяжении истории человечества неоднократно создавались списки кортежей, перестановок, сочетаний и разбиений.
Таким образом, мы рассмотрели эволюцию тем в разделах 7.2.1.1-7,2.1.5, но наш рассказ будет неполон, если мы не проследим происхождение генерации деревьев— тему раздела 7.2.1.6. сделано для жиалп(анашка.ого 92 КОМБИНАТОРНЫЙ ПОИСК Однако исторические сведения по этой теме до прихода компьютеров практически отсутствуют, если не считать нескольких статей, опубликованных в Х1Х веке Артуром Кейли (Агйпг Сау1еу). Основная работа Кейли по деревьям была опубликована в 1875 году н перепечатана в его Со!!ее!ей Майетансл! Рарегя (Уо1. 4, 427-460); она содержала большую иллюстрацию со всеми свободными деревьями не более чем с девятью непомеченными вершинами. Ранее в этой статье он также привел девять ориеищироевнимх деревьев с пятью вершинами. Методы, использовавшиеся Кейли для получения этих списков, были весьма сложными, совершенно отличавшимися от алгоритма 7.2.1.60 и упр. 7.2.1.6-90.
Все свободные деревья не более чем с десятью вершинами были перечислены много лет спустя Ф. Харари (Р. Нагагу) и Д. Прннсем (О. Рг1пз) [Асга Магй., 101 (1958), 158-162), которые дошли до и = 12 для случаев свободных деревьев, не имеющих узлов степени 2 и не обладающих симметрией. Деревья, наиболее любимые кибернетиками, — бинарные деревья, или эквивалентные упорядоченные леса, или вложенные скобки — как ни странно, в литературе отсутствуют.
В разделе 2.3.4.5 мы видели, что многие математики на протяжении 1700-1800-х годов изучали количество бинарных деревьев; мы также знаем, что числа Катэлана С„подсчитывают десятки различных комбинаторных объектов. Однако до 1950 года, похоже, никто не публиковал список из С4 = 14 объектов порядка 4 любоаэ вида, и еще меньше авторов публиковали список из Сз = 42 объектов порядка 5.
(За косвенным исключением — 42 диаграммы генджи-ко нз (25), не имеющие пересекающихся линий, оказываются эквивалентны 5-узловым бинарным деревьям и лесам. Однако этот факт не изучался до ХХ века.) Имеется несколько отдельных примеров, когда в былые дни авторы составляли списки из Сз — — 5 объектов, связанных с числами Каталаиа. Здесь также первым был Кейли; он привел бинарные деревья с тремя внутренними узлами и четырьмя листьями [РМ!оэорй!са! Малая!пе, 18 (1859), 374-378).
ЬйЬЬЬ (33) (В той же статье проиллюстрированы другие разновидности деревьев, эквивалентные так называемым слабым упорядочениям (иеай огбегшйз).) В 1901 голу Нетто перечислил пять способов расстановки скобок в выражении 'а + Ь + с + 8': (а + Ь) + (с+ И), [(а + Ь) + с) + г(, [а + (Ь + с)[+ 4, а+ [(Ь + с) + ф, а+ [Ь + (с+ 4)) (34) [йеЬгЬпсЬ г)ег СотМпагог!)г„з 122.[ Пять перестановок множества (+1, +1, +1, — 1, -1,— 1), частичные суммы которых неотрицательны, перечислены П. Эрдешем (Р.
Егббэ) н Ирвингом Каплански (1гу1пй Кар1апэ1су) [Всг!рга Май., 12 (1946), 73 — 75]: 1+ 1+ 1 — 1 — 1 — 1,1+ 1 — 1+ 1 — 1 — 1,1+ 1 — 1 — 1+ 1 — 1, 1 — 1+1+1 — 1 — 1,1 — 1+1 — 1+1 — 1. (35) Несмотря на то что в приведенных примерах используется только пять объектов, мы видим, что упорядочение в (ЗЗ) и (34) выполнено "как получится", и только упорядочение (35), соответствующее алгоритму 7.2.1.6Р, систематическое и лексикографическое. сделано для вълк! пГапаса.огя 7.2.1 ГЕНЕРАЦИЯ ОСНОВНЫХ КОМБИНАТОРНЫХ ОБ'ЬЕКТОВ 93 Мы также должны вкратце отметить работу Вальтера фон Дика (Ъа(сЬег гоп Вусй), поскольку многие современные статьи используют термин "Слова Дика" ("1)усй сгогс)з"), говоря о строках вложенных скобок. Днк был педагогом, известным, помимо прочего, как сооснователь Немецкого музея в Мюнхене (ПеисзсЬез Мизешп).
Он также написал две пионерские статьи по теории свободных групп [Ма|5. Аппа!еп, 20 (1882), 1-44; 22 (1883), 70-108). Так называемые слова Дика имеют очень слабое отношение к его реальным исследованиям. Он изучал слова на алфавите (хп х|,..., хы х,, ), которые приводятся к пустой строке после многократного удаления пар соседних букв вида хсх, ' нли х,. |х;; связь со скобками и деревьями возникает, только если ограничиться первым случаем, х|х, Итак, мы можем заключить, что, несмотря на огромный рост интереса к бинарным деревьям и их "родственникам" после 1950 года, такие деревья — единственный предмет нашего рассмотрения, исторические корни которого крайне неглубоки. После 1950. Разумеется, выход на сцену электронных вычислительных машин резко все изменил.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
