Cтраница 3
Продолжение серии, начатой издательством Мир в 1965 г. В выпуске содержатся обзорные статьи и оригинальные работы известных зарубежных ученых по наиболее актуальным проблемам теоретической кибернетики. Штрассена ( ФРГ) и др. по теории сложности, цикл статей по проблеме изоморфизма графов, алгоритмической теории чисел и экспертным системам. [31]
Каноническая нумерация химического графа может быть осуществлена с помощью нескольких известных методов и обычно представляет собой первый шаг при разработке буквенно-цифровых обозначений или кодов для обработки или поиска информации о химических структурах. Желательно иметь однозначный код для любой данной структуры, и это требование связано с проблемами изоморфизма графа, для которых было предложено много решений. Однозначная нумерация графа дает решение проблемы однозначного кодирования. Следуя работам некоторых предшествующих исследователей, нами недавно предложен метод однозначной нумерации полиядерных кластерных соединений. Метод берет начало с алгоритма канонической нумерации химического графа, и затем эта нумерация превращается в компактную линейную форму полностью помеченной матрицы смежности. Для нумерации графа алгоритм использует понятие расширенной связности и методы теории возмущений. Явное упорядочивание окончательного кода полностью определяет структуру. Процедура легко осуществляется без использования вычислительных средств и устанавливает изоморфизм, если две структуры имеют идентичные нумерации. Процедура канонической нумерации распространена на некоторые графы, с трудом поддающиеся другим методам канонической нумерации. [32]
Как было замечено в главе 5, каждая конечно представленная группа реализуется в виде фундаментальной группы 4-мно-гообразия. Этот факт вместе с неразрешимостью проблемы изоморфизма был использован А. А. Марковым [15] для доказательства алгоритмической неразрешимости проблемы изоморфизма для 4-многообразий. Работа Маркова была последовательно обобщена Буном, Хакеном и Поенарю [37] на диффео-морфную, а также комбинаторную эквивалентность. В отличие от того, что возникает при работе с группами, в данном случае некоторое внимание должно быть обращено на описание многообразия, к которому применяются критерии проблемы разрешения. [33]
Интерес к проблеме метрического изоморфизма возник после работ Неймана [23] и Неймана и Халмоша [21], где было показано, что в классе эргоди-ческих динамических систем с чисто точечным спектром полная система метрических инвариантов исчерпывается спектром. Гельфанд заметил, что результат фон Неймана может быть получен как простое следствие тривиальности второй группы когомологий спектра, который всегда является счетной абе-левой группой, с коэффициентами в S1, Казалось, что для систем с непрерывным спектром надо понять, в каком смысле спектр образует группу, ввести для нее группы когомологий с коэффициентами в группе унитарных операторов, после чего проблема изоморфизма сведется к вычислению соответствующей второй группы когомологий. [34]
Наименьшая двоичная запись SBN, введенная Рандичем [34], является результатом преобразования матрицы A ( G) в двоичную запись. Строки и столбцы A ( G) переставляются до достижения наименьшего возможного двоичного числа, при котором строки читаются последовательно. Этот индекс был предложен с целью решения проблемы изоморфизма графов, но он слишком громоздок, чтобы использоваться на практике в качестве топологического индекса. [35]
При условии корректности основного предположения классической теории сложности ( Р ф NP), существует класс проблем ( класс NPI) промежуточного уровня трудности; эти проблемы не так трудны, как полные NP-проблемы, однако они все еще не могут быть решены машиной Тьюринга за полиномиально ограниченное время. Проблема факторизации расценена как вероятный кандидат для членства в этом классе ( Garey & Johnson, 1979), так что естественно задаться вопросом, могут ли быть изобретены эффективные квантовые алгоритмы для других проблем, которые, как предполагается, соответствуют NPI-классу. Важно исследовать, могут ли быть изобретены хорошие квантовые алгоритмы для проблемы изоморфизма графов и аналогичных проблем. Я чувствую, что все еще недостает глубокого понимания, как работают квантовые алгоритмы. Несомненно, возможности квантовых компьютеров основаны на скрещениях, квантовом параллелизме и обширности гильбертова пространства, но я думаю, что этот вопрос будет полностью разрешен по мере понимания истинной сущности материи. Один из вопросов можно сформулировать так: как постоянная Планка Н участвует в квантовых вычислениях, и какова природа классического предела Н - О. [36]
При условии корректности основного предположения классической теории сложности ( Р ф NP), существует класс проблем ( класс NPI) промежуточного уровня трудности; эти проблемы не так трудны, как полные NP-проблемы, однако они все еще не могут быть решены машиной Тьюринга за полиномиально ограниченное время. Проблема факторизации расценена как вероятный кандидат для членства в этом классе ( Garey & Johnson, 1979), так что естественно задаться вопросом, могут ли быть изобретены эффективные квантовые алгоритмы для других проблем, которые, как предполагается, соответствуют NPI-классу. Важно исследовать, могут ли быть изобретены хорошие квантовые алгоритмы для проблемы изоморфизма графов и аналогичных проблем. Я чувствую, что все еще недостает глубокого понимания, как работают квантовые алгоритмы. Несомненно, возможности квантовых компьютеров основаны на скрещениях, квантовом параллелизме и обширности гильбертова пространства, но я думаю, что этот вопрос будет полностью разрешен по мере понимания истинной сущности материи. Один из вопросов можно сформулировать так: как постоянная Планка Н участвует в квантовых вычислениях, и какова природа классического предела Н - О. [37]
Многие практические задачи приводят к необходимости распознавания изоморфизма и изоморфного вложения сложных структур, которые могут быть заданы в форме матриц или графов. С содержательной точки зрения изоморфизм структур означает тождественность их функционирования, что приводит в некоторых случаях к возможности замены одной структуры другой, ей изоморфной. Однако для распознавания изоморфизма применяется алгоритм полного перебора, что делает проблему изоморфизма практически нерешимой уже при сравнительно небольшом числе элементов данной структуры. [38]
Доказательство последней теоремы включает в себя конструкцию, которая близка к построениям из доказательства теоремы 4.38, но здесь доказательство проще, и оно может служить пояснением теоремы об изоморфизме в части необходимости. В заключение этого раздела приводится пример очень простого скользящего блокового кода. То, что понятия, связанные со скользящими блоковыми кодами, возникли из работ по проблеме изоморфизма, наглядно продемонстрировало глубокую связь между теорией кодирования и теорией аппроксимации случайных процессов. [39]
Восстановление связано с рассмотрением классов изоморфизма. Занимаясь задачами восстановления, мы неизбежно приходим к проблеме изоморфизма, состоящей в выяснении того, изоморфны или нет два заданных графа. Автор не очень сведущ в алгоритмической тематике, но он знает, что хорошего алгоритма для проблемы изоморфизма пока неизвестно, и предполагает, что такого алгоритма вообще не существует. [40]
В Симферополе Менделеев пробыл недолго. К его огромной радости ему была предоставлена лаборатория, в которой он с увлечением работал над проблемой изоморфизма. [41]
Предположим теперь, что ( Q, У, Р - 1) и ( Q, ff, P, Т) - две изоморфные динамические системы, a S - такой метрический изомор. Тогда S - изометрический изоморфизм и S о Т Т о S, так что операторы Т и Т унитарно эквивалентны. Если бы из унитарной эквивалентности Т и Т следовал изоморфизм преобразований Т и Т, то для решения проблемы изоморфизма в эргодической теории было бы вполне достаточно использовать спектральную теорию. [42]
Вторым применением теории графов для описания химических графов является получение численных данных о химической структуре, которые могут быть использованы для корреляции с биологическими, физическими или химическими свойствами. В книге Кай-ера и Холла [26], в статьях Уилкинса и др. [27, 28] суммированы результаты ряда систематических исследований такого типа, которые можно с успехом применять для корреляции свойств. В некоторых недавних работах [29-33] было высказано предположение, что теоретико-графовые индексы могут также оказаться пригодными для решения проблем изоморфизма графов и различения изомеров. [43]
Моделирование заключается в построении системы знаков ( символов, формул, матриц, слов, фафиков), которые воспроизводят исследуемый объект и с помощью которых можно выявить его свойства, недоступные при изучении любым другим способом. Таким образом, моделирование позволяет получить новую информацию о свойствах исследуемого объекта на основе особого рода обработки и представления существующей и доступной информации. Главной проблемой при этом остается проблема обеспечения соответствия структуры и свойств модели структуре и свойствам реального экономического процесса, явления или объекта, т.е. проблема изоморфизма. Если модель изоморфна и имитирует наиболее существенные характеристики объекта и при этом для своего построения использует доступный инструментарий, то можно значительно сократить затраты ресурсов, в том числе времени, на изучение характеристик экономического объекта. [44]
Обращение теоремы о кодировании для канала с шумом дает оценку снизу искажения, возникающего при передаче информации по каналу со скоростью, превышающей его пропускную способность. Для того чтобы свести к минимуму последствия этого искажения, необходимо использовать устройство, которое бы от: бирало предназначенные для передачи сообщения в соответствии со степенью их важности для адресата. Вслед за обсуждением теоремы о кодировании для канала с шумом мы кратко коснемся одного способа кодирования для источника, возникшего под влиянием работ Д. С. Орнс-тейна по проблеме изоморфизма ( см. гл. Поскольку свойства скорости как функции искажения, включая теорему Шеннона о кодировании для источника, подробно рассмотрены у Маке лис а [86] и не содержат новых применений энтропии, мы не будем затрагивать их здесь. О кодировании для источника речь будет идти только при рассказе о скользящих блоковых кодах в разд. [45]