Оценка - алгоритм
Cтраница 2
Положение главной ( нулевой) системы координат не имеет принципиального значения, однако и алгоритмы, и процесс проектирования значительно упрощаются, если координатные плоскости совпадают со сборочными, конструкторскими или технологическими базами базового элемента [90] и если положительное направление оси ОХ совпадает с направлением вектора сборки базового элемента. Однако эти требования не являются категорическими, они еще четко не систематизированы, в настоящее время происходит накопление опыта на основе оценки уже выполненных алгоритмов и их опытно-промышленной проверки. [16]
Сегодня большие усилия направлены на разработку численных алгоритмов и их исследование и, в частности, на то, чтобы; понять способ оценки алгоритма, И здесь классическим традициям принадлежит основная роль. Поэтому в качестве главного критерия обычно принимают сходимость алгоритма. Расходящийся алгоритм - это плохой алгоритм; чем быстрее сходится алгоритм, тем лучше - подобные истины почти прописные А. [17]
Формализованные алгоритмы данного типа хорошо подходят для решения математических задач, где нужно доказать истинность каких-либо положений или возможность каких-нибудь действий, при этом скорость алгоритма не имеет значения. При решении реальных задач, где необходимо выполнить некоторые инструкции, например сортировку на компьютере записей о миллионе покупателей, эффективность алгоритма становится критерием оценки алгоритма. [18]
Этот раздел основан на работе ( Crowder, Dembo and Mulvey, 1979), в которой дан обзор свыше 50 статей, посвященных оценкам алгоритмов и программ для определенных классов задач. Ни в одной из этих статей не были применены по-настоящему последовательные эксперименты; во многих отношениях большинство из них были признаны неудовлетворительными. Наиболее распространенный недостаток состоит в том, что выводы приводятся без адекватного описания экспериментов или полученных данных. Авторы цитируют одну статью, содержащую следующее утверждение: Поскольку эти методы запрограммированы для различных машин на различных языках различными программистами, то не имеет большого смысла давать детальную оценку результатов, особенно потому, что так много задач оказались вырожденными. [19]
С одной стороны, разрабатываются приближенные алгоритмы представления булевых функций термами, с другой, - методы оценок таких представлений. Нужно отметить, что при решении задачи эффективных нижних оценок сложности возникают трудности принципиального характера. Поэтому оценка алгоритмов минимизации булевых функций в настоящее время производится применением к известным тестовым примерам и общими статистическими данными работы алгоритма. [20]
Чтобы избежать возможных недоразумений, следует прояснить, что полученный протокол обращений к страницам относится только к одной хорошо спланированной программе и, кроме того, к определенным входным данным. Таким образом, алгоритм замещения страниц, выведенный из него, будет характерен только для этой программы с именно этими входными данными. Хотя такой метод полезен для оценки алгоритмов замещения страниц, он не используется в практических системах. Ниже мы изучим алгоритмы, которые являются применимыми в реальных системах. [21]
Чтобы избежать возможных недоразумений, следует прояснить, что полученный протокол обращений к страницам относится только к одной хорошо спланированной программе и, кроме того, к определенным входным данным. Таким образом, алгоритм замещения страниц, выведенный из него, будет характерен только для этой программы с именно этими входными данными. Хотя такой метод полезен для оценки алгоритмов замещения страниц, он не используется в практических системах. Ниже мы изучим алгоритмы, которые являются применимыми в реальных системах. [22]
Полученные данные используются при формировании структур анализируемых алгоритмов. Эти структуры описываются на входном языке моделирующей программы МОДА. При работе с моделирующей программой пользователь имеет возможность планировать эксперимент по получению точностных оценок алгоритмов. Для этого необходимо выбрать наиболее важные для каждой задачи параметры и указать допустимые границы изменения этих параметров. Кроме того, в зависимости от желания разработчика, процедура имитационного моделирования может проводиться как с реальными реализациями случайных процессов, полученными с объекта, так и с реализациями, полученными путем моделирования. [23]
Имеется целый ряд других уже изученных направлений, связанных с параллельной обработкой. Розенкранц и др. [142] и Стирнз и др. [159] моделировали общесистемное планирование, при котором элементы не блокируются транзакциями, но центральный модуль управления блокировками регистрирует блокировки и принимает решение о предоставлении запросам прав на чтение или запись элемента. В работах Берн-штейна и др. [22, 24], Эпштейна и др. [63], Томаса [167, 168] и Гарсия-Молина [71] произведена оценка алгоритмов для поддержания в существенной степени распределенных копий базы данных. В этой ситуации возникают проблемы, когда различные транзакции в разных участках выполняются параллельно, а затем транслируют сделанные ими изменения в другие участки. [24]
 |
Тестирование генетических операторов. [25] |
Данный модуль построен на основе ПГА и используется для сравнения выходных характеристик одного и того же ГА для одинаковых графов при различных генетических операторах. При этом результатами являются: время работы алгоритма, стабильность алгоритма, лучшее решение, достигнутое в процессе работы, оценка алгоритма по сходимости. [26]
 |
Сортировка простыми вставками. [27] |
Ниже рассмотрим случай, когда существует возможность изменить положение записи в файле вместе с ключом записи. В этом случае необходимо учитывать возможность при заданных размерах файла, подлежащего сортировке, его обработки только с использованием оперативной памяти. Очевидно, что сортировка в оперативной памяти и сортировка во внешней памяти существенно отличаются по эффективности; будут отличаться также алгоритмы и критерии оценки алгоритмов. [28]
Однако при использовании методов перемешивания возникает следующая проблема. Цепочка символов, образующая ключ записи, обычно позволяет строить гораздо больше записей с различными ключами, чем их может быть на самом деле. Поэтому отображение множества ключей в множество адресов необязательно взаимно-однозначно, а это означает, что имеются классы эквивалентности ключевых слов, известные как классы коллизий. Поскольку заранее неизвестно, какое из возможных ключевых слов будет использовано, а какое - нет, невозможно оптимизировать алгоритм перемешивания, чтобы сделать минимальной частоту возникновения коллизий и размеры классов коллизий. Считается, что, чем равномернее распределены полученные адреса, тем лучше алгоритм перемешивания. Следовательно, в этом случае оценка алгоритма перемешивания может быть выполнена только эмпирическим путем обычно на основе тщательно проведенного моделирования. Некоторые из этих часто используемых методов кратко рассмотрены ниже. [29]
Первый том носит название Основные алгоритмы. Именно в последние несколько десятилетий создано и изучено огромное количество конкретных алгоритмов. Кроме того имеется большая семья алгоритмов, применяемых для решения нечисловых задач и в частности задач, возникающих в связи с организацией работы самих ЭВМ. Это действительно основные алгоритмы, которые составляют колоссальное научное богатство, так сказать, материальную силу, прикладной математики. Каждый такой алгоритм является орудием, которое можно многократно использовать, и поэтому существенны вопросы о выработке критериев оценки алгоритмов и способов их анализа. [30]
Страницы: 1 2