Cтраница 3
В математической логике имеется ограничение на правило выдачи результата: оно обязано задаваться алгоритмом; обращение к таблице ( бесконечной) недопустимо. Время работы такого алгоритма и определяет сложность решения задачи. Таким образом, в математической логике мы считаем задачу идентифицированной ( своим кодом), но ограничиваем средства, которые можно применять для преобразования заданного кода задачи в код ее решения. В теории информационной сложности, напротив, применяемые средства никак не ограничены, но зато информацию о решаемой задаче разрешается получать в рамках строго регламентированного диалога. [31]
Первые попытки учесть сложность при проектировании систем автоматического регулирования сделаны в работе Солодовникова В. В. 1 при разработке частотного метода синтеза корректирующих устройств. При этом за меру сложности был принят порядок числителя и знаменателя передаточной функции синтезируемой САР. В конце 50 - х годов было дано мате матическое определение понятия сложности, относящееся к конеч ным автоматам, состоящим из элементов, реализующих функции алгебры логики. При этом под сложностью понималось число эле ментов блоков, из которых состоит система, В работах А. Н. Колмо горова было дано определение понятия информационной сложности конечного объекта, которое позволило установить формальную связь между понятиями сложности, информации и случайности. [32]