Поиски первопричины

Изучение какой-либо сложной системы всегда начинается с анализа причинно-следственных связей между ее отдельными элементами. Прямые взаимосвязи, когда элемент i является непосредственной причиной элемента j, как правило, лежат на поверхности и хорошо прослеживаются. Но наибольший интерес всегда представляют глубинные первопричины, скрытые за очевидностью фактов. Недавно просматривая один очень старый сборник алгоритмов , я наткнулся на процедуру, которая показалась мне интересной. Процедура носит название ancestor, что означает "прародитель". В качестве исходных данных алгоритм использует логическую матрицу m размера n на n, в которой элемент m(i, j) = true тогда, когда элемент i является непосредственной причиной элемента j. После обработки процедурой ancestor элемент m(i, j) = true, если элемент i является косвенной причиной элемента j. То есть, если существует непрерывная причинно-следственная цепь m(i, k), m(k, l), ..., m(p, j), соединяющая два этих элемента косвенно, через другие элементы. В переводе с Алгола на Visual Basic процедура выглядит следующим образом:

Sub ancestor()
 For i = 1 To n
  For j = 1 To n
   If m(j, i) Then
    For k = 1 To n
     If m(i, k) Then m(j, k) = True
    Next k
   End If
  Next j
 Next i
End Sub

Проиллюстрируем ее работу на историческом примере, в наибольшей степени подходящем ее названию и назначению. А именно: проанализируем при помощи процедуры ancestor, или прародитель, причинно-следственные династические связи Дома Романовых. В соответствии с материалами сайта www.intercult.ru/culture/romanovs/index.html к Дому Романовых относится 20 царственных персон. Их перечень приведен ниже:

Михаил Федорович
Алексей Михайлович
Федор Алексеевич
Иоанн V Алексеевич
Софья Алексеевна
Петр I Алексеевич
Екатерина I Алексеевна
Петр II Алексеевич
Анна Иоанновна
Анна Леопольдовна
Иоанн VI Антонович
Елизавета Петровна
Петр III Федорович
Екатерина II Алексеевна
Павел I Петрович
Александр I Павлович
Николай I Павлович
Александр II Николаевич
Александр III Александрович
Николай II Александрович

Царственные особы расположены в списке в хронологическом порядке своего пребывания у власти. Для работы процедуры это не имеет существенного значения. Они вполне могли быть расположены и в произвольном порядке. Теперь заполним исходную причинно-следственную матрицу размером 20 на 20 элементов. Будем вписывать единицу (true) в соответствующую позицию, если i-тый монарх является непосредственным родителем j-того монарха. То есть, например, m(2, 6) = true, так как Петр I (№6 в нашем списке) является сыном самодержца Алексея Михайловича (№2 в списке). При подготовке исходного примера я сделал несколько, на мой взгляд, допустимых исключений и обозначил Петра I как непосредственного родителя Петра II (m(6, 8) = true) и Петра III (m(6, 13) = true), хотя в действительности они были лишь его внуками. Без этого кровная династическая преемственность выглядела бы не столь наглядно. В результате получилась матрица, приведенная на рисунке сверху.

Если бы элементы списка не были расположены в хронологическом порядке, то по виду матрицы установить основателя династии было бы затруднительно. Теперь подвергнем нашу матрицу обработке процедурой ancestor. Результат ее работы приведен на том же рисунке ниже. На ней со всей очевидностью прослеживается, что прародителем династии является Михаил Федорович Романов, так как в первом столбце расположено максимальное количество единичек. Существенное генетическое влияние на династическое дерево оказал и царь Алексей Михайлович. Прямая генетическая преемственность чуть было не прервалась Екатериной I, но была восстановлена внуком Петра I, Петром III. Одним словом, полезная процедура. Попробуйте подобрать другие примеры для ее применения. Мне представляется, что их можно придумать множество, и процесс этот достаточно занимателен. Если же вы преподаете информатику, то описанный пример может послужить основой для очередного урока или лабораторной работы.

А. КОЛЕСНИКОВ,
andr61@mail.ru