Cтраница 2
Незначительные отличия в алгоритмах заданного множества задач обработки данных затрудняют, а в некоторых случаях исключают возможность выделения формализованным способом общих частей анализируемых задач. Введение различных классов эквивалентности анализируемых задач позволяет осуществлять сравнение алгоритмов их решения на заданном уровне абстракции. Сравнение алгоритмов решения задач и выделение в них совпадающих или эквивалентных частей предлагается осуществлять без учета различия в константах элементов, так как эти отличия учитываются при настройке синтезированных типовых программных модулей на исходные данные каждой задачи. [16]
Следует, однако, иметь в виду, что порядок роста сложности алгоритма является определяющим только при обработке данных большого размера. Для задач с малым размером входных данных ( а именно на таких данных и проверяется правильность студенческих алгоритмов) следует учитывать мультипликативные константы при сравнении алгоритмов. [17]
Незначительные отличия в алгоритмах заданного множества задач обработки данных затрудняют, а в некоторых случаях исключают возможность выделения формализованным способом общих частей анализируемых задач. Введение различных классов эквивалентности анализируемых задач позволяет осуществлять сравнение алгоритмов их решения на заданном уровне абстракции. Сравнение алгоритмов решения задач и выделение в них совпадающих или эквивалентных частей предлагается осуществлять без учета различия в константах элементов, так как эти отличия учитываются при настройке синтезированных типовых программных модулей на исходные данные каждой задачи. [18]
В главе 4 рассматривается применение алгоритма динамического программирования для решения некоторых аддитивных задач. В пособии не ставится цель изложить методологические вопросы, связанные с общими схемами динамического программирования: этому посвящена обширная литература. Применение алгоритмов демонстрируется на задаче о ранце, для этой задачи приведено сравнение алгоритма ветвей и границ и динамического программирования. [19]
При сравнении различных реализаций легко допустить ошибки, особенно, если в игру вступают разные машины, компиляторы или системы, либо гигантские программы с плохо охарактеризованным вводом. Принципиальная опасность при эмпирическом сравнении программ таится в том, что код для одной реализации может быть создан более тщательно, чем для другой. Изобретателю предлагаемого нового алгоритма необходимо обратить внимание на все аспекты его реализации, чтобы не расходовать слишком много усилий на создание классического конкурирующего алгоритма. Чтобы быть уверенным в точности эмпирического сравнения алгоритмов, мы должны быть уверены, что каждой реализации уделялось одинаковое внимание. [20]
При анализе совокупности задач обработки данных для определения степени их общности и специфичности необходимо ввести понятие классов эквивалентности задач, соответствующих различным степеням их близости. Незначительные отличия в алгоритмах заданного множества задач обработки данных затрудняют, а в некоторых случаях - исключают, возможность выделения формализованным способом общих частей анализируемых задач. Введение различных классов эквивалентности анализируемых задач позволяет осуществлять сравнение алгоритмов их решения на заданном уровне абстракции. [21]
Если учесть, что декомтюзициЯ в определенном смысле есть выбор вполне определенных переменных системы, определяющих возможность отдельного расчета каждой из подсистем, то для отыскания оптимального варианта всей системы очевидно необходимо проводить итерации по каждой из выбранных переменных декомпозиции и на каждой такой итерации - проводить расчет каждого из элементов процесса. Тогда необходимо рассматривать уже две проблемы - как провести декомпозицию системы с точки зрения обеспечения возможности раздельного расчета элементов системы и связанную с ней проблему выбора таких переменных, при которых достигается экономия времени решения задачи. Для решения задачи декомпозиции системы предложен ряд алгоритмов, например [23-26], и все предложенные алгоритмы различаются, прежде всего, по количеству времени, необходимому для декомпозиции исходной системы. Поскольку в общем случае количество времени при реализации алгоритма зависит и от быстродействия используемой ЭВМ, сравнение алгоритмов проведено в терминах количества арифметических и логических операций, необходимых для декомпозиции системы. [22]
Обычно существуют три основных возможности: реальные данные, случайные данные и ошибочные данные. Реальные данные позволяют точно измерить параметры используемой программы; случайные данные гарантируют, что наши эксперименты тестируют алгоритм, а не данные; ошибочные данные гарантируют, что наши программы могут воспринимать любой направленный им ввод. Например, при тестировании алгоритмов сортировки мы запускаем их для работы с данными в виде слов в произведении Моби Дик, в виде сгенерированных случайным образом целых чисел и в виде файлов, содержащих одинаковые числа. Проблема определения, какие данные необходимо использовать для сравнения алгоритмов, возникает также и при анализе алгоритмов. [23]