Основные свойства алгоритмов

⇐ ПредыдущаяСтр 5 из 19Следующая ⇒

Понятие алгоритма принадлежит к числу понятий столь фундаментальных, что не может быть выражено через другие, а должно рассматриваться как неопределяемое. Алгоритм это точное предписание, которое задает вычислительный процесс, начинающийся с произвольных исходных данных и направленный на получение полностью определяемого этими исходными данными результата.

Основные свойства алгоритмов:

1. Дискретность. Процесс решения протекает в виде последовательности отдельных действий, следующих друг за другом.

2. Детерминированность (определенность). В каждый момент времени, следующий шаг работы однозначно определяется состоянием системы. Таким образом, алгоритм выдаёт один и тот же результат (ответ) для одних и тех же исходных данных.

3. Определенность. Каждое действие определено и после выполнения каждого действия однозначно определяется, какое действие будет выполнено следующим.

4. Конечность. Алгоритм заканчивает работу после конечного числа шагов.

5. Результативность. В момент прекращения работы алгоритма известно, что является результатом.

6. Массовость. Алгоритм описывает некоторое множество процессов, применимых при различных входных данных.

7. Алгоритм считается правильным, если при любых допустимых данных он заканчивает работу и выдает результат, удовлетворяющий требованиям задачи.

8. Алгоритм однозначен, если при применении к одним и тем же входным данным он дает один и тот же результат.

Элементы теории сложности

Первые фундаментальные работы по теории алгоритмов были опубликованы независимо в 1936 году Аланом Тьюрингом, Алоизом Черчем и Эмилем Постом.

Английский математик А.М.Тьюринг описал машину, названную его именем. Он показал, что если проблемы не могут быть решены на его машине, то они не могут быть решены ни на какой другой ЭВМ, т.е. это проблемы для которых алгоритмы не могут быть составлены даже в принципе.

Один из основных результатов Тьюринга – разделение всех представляемых в математике проблем на два класса:

1. проблемы, для которых алгоритмы никогда не могут быть написаны, т.е., в формальном смысле, постоянно не решаемые;

2. проблемы, которые могут быть решены с помощью алгоритмов.

Класс решаемых проблем может быть разделен на два подкласса:

1. подкласс, содержащий только полиномиальные алгоритмы;

2. подкласс, содержащий только экспоненциальные алгоритмы.

Эффективностью алгоритма называют максимальное число элементарных операций, выполняемых при его работе. Ее записывают в виде O(f(n)). По определению O(f(n)) – это множество всех функций g(n), для которых существует положительная постоянная с и такой номер n₀, что |g(n)| ≤ c| f(n)| для всех n > n₀.

Распространенным критерием оценки алгоритмов является время работы и порядок роста продолжительности работы в зависимости от объема входных данных.

Для каждой конкретной задачи составляют некоторое число, которое называют ее размером. Например, размером задачи вычисления произведения матриц может быть наибольший размер матриц-множителей, для задач на графах размером может быть количество вершин или ребер графа.

В рамках классической теории алгоритмические задачи различаются по классам сложности (P-сложные, NP-сложные, экспоненциально сложные и др.).

Классы сложности - множества вычислительных задач, примерно одинаковых по сложности вычисления. Более узко, классы сложности — это множества предикатов (функций, получающих на вход слово и возвращающих ответ 0 или 1), использующих для вычисления примерно одинаковые количества ресурсов. Каждый класс сложности (в узком смысле) определяется как множество предикатов, обладающих некоторыми свойствами.

Классом сложности X называется множество предикатов P(x), вычислимых на машинах Тьюринга и использующих для вычисления O(f(n)) ресурса, где n — длина слова x.

В качестве ресурсов обычно берутся время вычисления (количество рабочих тактов машины Тьюринга) или рабочая зона (количество использованных ячеек на ленте во время работы).

Класс P – задачи, которые могут быть решены за время, полиномиально зависящее от объёма исходных данных, с помощью детерминированной вычислительной машины (например, машины Тьюринга),

Класс NP — задачи, которые могут быть решены за полиномиально выраженное время с помощью недетерминированной вычислительной машины, то есть машины, следующее состояние которой не всегда однозначно определяется предыдущими. К классу NP относятся задачи, решение которых с помощью дополнительной информации полиномиальной длины, мы можем проверить за полиномиальное время. В частности, к классу NP относятся все задачи, решение которых можно проверить за полиномиальное время. Класс P содержится в классе NP.

Работу такой машины можно представить как разветвляющийся на каждой неоднозначности процесс: задача считается решенной, если хотя бы одна ветвь процесса пришла к ответу.

Поскольку класс P содержится в классе NP, принадлежность той или иной задачи к классу NP зачастую отражает наше текущее представление о способах решения данной задачи и носит неокончательный характер. В общем случае нет оснований полагать, что для той или иной NP-задачи не может быть найдено P-решение. Вопрос о возможной эквивалентности классов P и NP (то есть о возможности нахождения P-решения для любой NP-задачи) считается многими одним из основных вопросов современной теории сложности алгоритмов. Ответа на этот вопрос нет. Сама постановка вопроса об эквивалентности классов P и NP возможна благодаря введению понятия NP-полных задач. NP-полные задачи составляют подмножество NP-задач и отличаются тем свойством, что все NP-задачи могут быть тем или иным способом сведены к ним. Из этого следует, что если для NP-полной задачи будет найдено P-решение, то P-решение будет найдено для всех задач класса NP. Примером NP-полной задачи является задача о конъюнктивной форме.

Рассмотрим наиболее часто встречающиеся классы сложности в зависимости от числа входных данных n (в порядке нарастания сложности, т.е. увеличения времени работы алгоритма, при стремлении n к бесконечности):

О(1) - количество шагов алгоритма не зависит от количества входных данных. Обычно это алгоритмы, использующие определённую часть данных входного потока и игнорирующие все остальные данные. Например, чистка 1 квадратного метра ковра вне зависимости от его размеров.

Ряд алгоритмов имеют порядок, включающий log₂n, и называются логарифмическими (logarithmic). Эта сложность возникает, когда алгоритм неоднократно подразделяет данные на подсписки, длиной 1/2, 1/4, 1/8, и так далее от оригинального размера списка. Логарифмические порядки возникают при работе с бинарными деревьями. Бинарный поиск имеет сложность среднего и наихудшего случаев O(log₂n).

Сложность О(nlog₂n) имеют алгоритмы быстрой сортировки, сортировки слиянием и " кучной" сортировки, алгоритм Краскала - построение минимального связывающего дерева, n - число ребер графа.

Алгоритм со сложностью О(n) - алгоритм линейной сложности. Например, просмотр обложки каждой поступающей книги - то есть для каждого входного объекта выполняется только одно действие;

Алгоритмы, имеющие порядок О(n²), являются квадратичными (quadratic). К ним относятся наиболее простые алгоритмы сортировки; алгоритм Дейкстры - нахождение кратчайших путей в графе, алгоритм Прима - построение минимального связывающего дерева, n - число вершин графа. Квадратичные алгоритмы используются на практике только для относительно небольших значений n. Всякий раз, когда n удваивается, время выполнения такого алгоритма увеличивается на множитель четыре.

Алгоритм показывает кубическое (cubic) время, если его порядок равен О(n³), и такие алгоритмы очень медленные. Всякий раз, когда n удваивается, время выполнения алгоритма увеличивается в восемь раз. Алгоритм Флойда–Уоршелла (динамический алгоритм для нахождения кратчайших расстояний между всеми вершинами взвешенного ориентированного графа).

Алгоритм со сложностью О(2ⁿ) имеет экспоненциальную сложность (exponential complexity). Такие алгоритмы выполняются настолько медленно, что они используются только при малых значениях n. Этот тип сложности часто ассоциируется с проблемами, требующими неоднократного поиска дерева решений.

Алгоритмы со сложностью О(n! ) - факториальные алгоритмы, в основном, используются в комбинаторике для определения числа сочетаний, перестановок.

В таблице 4.1 приводятся линейный, квадратичный, кубический, экспоненциальный и логарифмический порядки величины для выбранных значений n. Из таблицы очевидно, что следует избегать использования кубических и экспоненциальных алгоритмов, если только значение n не мало.

Таблица 4.1. Сравнение сложности различных алгоритмов

n	lоg₂n	n lоg₂n	n²	n³	2ⁿ





					3.4 × 10³⁸
					1.8 × 10³⁰⁸
				2.8 × 10¹⁴	Избегайте!

Важность проведения резкой границы между полиномиальными и экспоненциальными алгоритмами вытекает из сопоставления числовых примеров роста допустимого размера задачи с увеличением быстродействия В используемых ЭВМ.

В табл. 4.2 указаны размеры задач, решаемых за одно и то же время Т наЭВМ с быстродействием В₁ при различных зависимостях сложности О(n).

Таблица 4.2. Размеры решаемых задач алгоритмов разных класов сложности

О(n)	В₁	В₂ = 100 В₁	В₃ = l000 В₁
n	n₁	100n₁	1000n₁
n²	n₂	10n₂	31, 6n₂
n^з	n_з	4, 64n_з	10n₃
2ⁿ	n₄	6, 64 + n₄	9, 97 + n₄

Эти примеры показывают, что, выбирая ЭВМ в К разболее быстродействующую, получаем увеличение размера решаемых задач при линейных алгоритмах в К раз, при квадратичных - в К¹^/² рази т. д.

Иначе обстоит дело с неэффективными алгоритмами. Так, в случае сложности 2ⁿ для одного и того же процессорного времени размер задачи увеличивается только на lgK / lg2 единиц. Следовательно, переходя от ЭВМ с В₁ = 1 Гфлопс к суперЭВМ с В₃ = 1 Тфлопс, можно увеличить размер решаемой задачи только на 10, что совершенно недостаточно для практических задач. Действительно, в таких задачах, как, например, синтез тестов для БИС число входных двоичных переменных может составлять более 100 и поэтому полный перебор всех возможных проверяющих кодов потребует выполнения более 2¹⁰⁰ вариантов моделирования схемы.

Алгоритмы компоновки

Процесс преобразования функционального описания в конструктивное называется компоновкой. Иначе, компоновка это распределение элементов низшего уровня иерархии по узлам высшего уровня.

Различают две постановки задачи компоновки:

· покрытие – преобразование исходной схемы в схему соединения элемнтов, номенклатура которых задана;

· разрезание – разбиение исходной схемы на части.

Известные алгоритмы компоновки можно условно разбить на 5 групп:

1. алгоритмы, использующие методы целочисленного программирования;

2. алгоритмы, основанные на методе ветвей и границ;

3. последовательные алгоритмы;

4. итерационные алгоритмы;

5. смешанные алгоритмы.

Алгоритмы первой и второй групп, хотя и позволяют получить точное решение задачи, однако для устройств реальной сложности фактически не реализуемы на ЭВМ.

В алгоритмах разбиения, опирающихся на идеи математического программирования, в основном используются методы ветвей и границ и решение задачи о назначении.

Алгоритмы разбиения, использующие методы ветвей и границ, состоят из следующих этапов.

Сначала определяется нижняя оценка разбиения графа на заданное число частей. Затем производится построение дерева решений и осуществляется поиск оптимального результата.

Задачу разбиения графа схемы на части можно свести к задаче о назначении следующим образом.

Сначала отыскивают назначение кандидатов (вершин графа) на все части, дающие минимальные суммарные затраты, причем, каждая вершина графа может быть назначена только в одну часть и в каждой части должны содержаться различные вершины графа.

Наибольшее распространение получили приближенные алгоритмы компоновки (последовательные, итерационные, смешанные).

При использовании последовательных алгоритмов сначала по определенному правилу выбирают вершину графа, затем осуществляют последовательный выбор вершин (из числа нераспределенных) и присоединение их к формируемому куску графа. После образования первого куска переходят ко второму и т. д. до получения желаемого разрезания исходного графа.

В итерационных алгоритмах начальное разрезание графа на куски выполняют произвольным образом; оптимизация компоновки достигается парными или групповыми перестановками вершин графа из различных кусков. Процесс перераспределения вершин заканчивают при получении локального экстремума целевой функции, удовлетворяющего требованиям разработчика.

В смешанных алгоритмах компоновки для получения начального варианта “разрезания” используется алгоритм последовательного формирования кусков; дальнейшая оптимизация решения осуществляется перераспределением вершин между отдельными кусками графа.

Алгоритм покрытия

Важной задачей в общей проблеме конструирования является покрытие, т.е. преобразование функциональных схем в принципиальные.

Под покрытием схемы понимается представление функциональной схемы конструктивными элементами, на которых она будет реализована, и связями между ними.

Конечной целью покрытия является выбор оптимальной элементно-технической базы проектируемого устройства.

В курсовой работе по дисциплине «Дискретная математика» задача покрытия решалась при преобразовании схемы из булева базиса в универсальные базисы с ограничением на число входов.

В основу построения большинства алгоритмов покрытия положена идея выделения из функциональной схемы подсхем, перебора их и проверки на совпадение логических функций элементов подсхем и функции модулей исходного набора. Подсхема закрепляется за модулем, в состав которого входит наибольшее количество ее логических функций.

Предполагается, что элементы заданного набора могут реализовать все функции схемы.

Исходная схема представляет множество M={m₁, m_2,..., m_k} связанных между собой функциональных элементов, таких как логические элементы И, ИЛИ, НЕ, триггер, усилитель, генератор, формирователь и т. д., каждый из которых реализует некоторую функцию ψ _i, а их множество определяет совокупность всех функций Y ={ ψ ₁, ψ ₂, ..., ψ _k}, выполняемых в схеме. Схема представляется графом G(M, U), множество вершин которого отображает элементы, а множество ребер — связи между ними. Задан ограниченный набор (библиотека) типов модулей N={n₁, n_2,..., n_p}, где p — число типов конструктивных модулей в используемой библиотеке, каждый из которых реализует одну или несколько функций (имеет определенный, заранее известный состав функциональных элементов). Каждый конструктивный модуль n_j можно представить в виде подграфа H_j, в котором вершины отображают функциональные элементы, входящие в модуль.

Требуется разбить исходную схему на подсхемы (подграфы) при выполнении следующих условий:

· каждая подсхема по своему функциональному составу должна соответствовать некоторому модулю n_j из заданного набора N;

· любые две подсхемы разбиения не пересекаются, т. е. не имеют общих элементов.

Для оценки качества покрытия используются следующие показатели:

· число типов модулей, использующихся для покрытия;

· полнота использования функциональных возможностей каждого модуля;

· число всех модулей.

Эвристический алгоритм покрытия включает операции вложения подграфов H_j в граф схемы G. Поочередно для каждого H_j - ищутся в графе G изоморфные подграфы G_j. Найденные подграфы G_j удаляются из графа G. Если после этого часть графа осталась непокрытой, то для каждого H_j - вновь ищутся подграфы G_j в G, такие, что G_jÌ H_j. Процесс продолжается, до тех пор, пока вся схема не окажется покрытой модулями заданного набора.

Качество покрытия зависит от порядка, в котором просматриваются подграфы H_j. Поэтому предусматривается получение нескольких вариантов покрытия по рассмотренному последовательному алгоритму с выбором наилучшего, в соответствии с одним из критериев компоновки.

Алгоритмы покрытия упрощаются при использовании набора модулей, состоящих из несвязанных между собой функциональных элементов.

Начальное покрытие может быть улучшено парными перестановками однотипных функциональных элементов различных модулей. Замена элементов производится, если при перестановке увеличивается число внутренних связей модулей и уменьшается число внешних связей.

⇐ Предыдущая 1 2 3 456 7 8 9 10 Следующая ⇒