Проверка условия i > 50. Если условие истинно, то перейти к пункту 8 настоящего алгоритма, если условие ложно, то перейти к пункту 4.

8. Конец работы алгоритма.

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

Решение: Подробное описание всех блоков структурной схемы алгоритма не приводится, поскольку блоки структурной схемы будут аналогичны операторам граф - схемы алгоритма из примера 10.2. Приведем содержание основных 1-го и 3 -го блоков.

Блок 1 - Ввод размера интервала n и начального значения шага i = 0;

Блок 3 - Выбор начального числа из интервала a;

Ответ. Структурная схема алгоритма показана на рис. 10.17.

 

                                                                              

Рис. 10.17. Пример структурной схемы алгоритма

10.5. “Жадные” алгоритмы

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

Рассмотрим стандартную задачу (Кормен, Лейзерсон, Ривест) о выборе заявок. Пусть даны n заявок на проведение занятий в одной и той же аудитории. Два разных занятия не могут проводиться в одно время. В каждой заявке указаны начало и конец занятия (s_i и f_i для i -той заявки). Разные заявки могут пересекаться, и тогда можно реализовать только одну из них. Каждая заявка отождествляется с промежутком [ s_i, f_i ], так что конец одного занятия может совпадать с началом другого, и это не считается пересечением. Целевая функция задачи заключается в наборе максимального количества совместных друг с другом заявок при временных ограничениях и граничных условиях. Жадный алгоритм работает следующим образом. Предполагаем, что заявки упорядочены в порядке возрастания времени окончания, т.е., f ₁ ≤ f ₂ ≤ … £ f_n. Заявки с одинаковым временем конца располагаем в произвольном порядке. Тогда запишем псевдокод алгоритма, приведенный в учебнике (Кормен, Лейзерсон, Ривест):

ВЫБОР ЗАЯВОК (s, f - массивы)

1 n ← length [ s ]

2 А ← {1}

3 j ← 1

4 for i ← 2 to n

5 do if s_i ≥ f_j

6 then A ← A È { i }

7 j ← i

8 return A

Множество А состоит из номеров выбранных заявок, j – номер последней из них; при этом f_j = m ах{ f_k: k Î A }, поскольку заявки отсортированы по возрастанию времени окончания. Вначале А содержит заявку номер 1, и j = 1 (строки 2 - 3). Далее (цикл в строках 4 - 7) ищется заявка, начинающаяся не раньше окончания заявки номер j. Если таковая найдена, она включается в множество А и переменной j присваивается ее номер (строки 6 - 7). Описанный алгоритм выбора заявок требует всего лишь O (n) шагов (не считая предварительной сортировки). Как и подобает жадному алгоритму, на каждом шаге он делает выбор так, чтобы остающееся свободным время было максимально.

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

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

10.6. Нечеткие (расплывчатые) алгоритмы

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

Инструкции в расплывчатых алгоритмах делят на три группы.

1-я группа — назначающие инструкции. Например, х = “большой” или х = “вкусный”.

2-я группа — расплывчатые высказывания. Например, если х — “очень дорогой”, то перейти к y, или если х “не помещается в комнате”, то “увеличить размер комнаты”.

3-я группа — безусловные активные предложения. Например, “немного увеличить” х, или “сильно увеличить” х, или перейти к другому значению параметра x.

Отметим, что все инструкции могут быть нечеткими или четкими.

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

Расплывчатой переменной считают кортеж П = < a, X, >, где a — наименование расплывчатой переменной; X = {x₁, х ₂,..., х _n } — область ее определения; A = {  (x_i) | x_i } x_i Î X — расплывчатое множество в X, определяющее ограничения на возможные значения П. Лингвистической переменной называют кортеж Л = < b, Т, X >, где b — наименование Л; Т — множество ее значений, представляющих наименования П, областью определения которых является X.

Например, пусть оценивается качество технологического процесса выхода годных с помощью понятий “плохой”, “средний”, “хороший”. Максимальный выход годных 80%. Тогда Л = <качество, Т, [0; 80]>, где Т = {“плохой”, “средний”, “хороший”}. Значения Л описываются расплывчатыми переменными. Например, значение “плохой” описывается расплывчатой переменной < плохой, [0; 80],  >, где  может иметь вид  = {< 1 / 0 >,
< 0,8 / 5 >,< 0,6 / 7 >,< 0,2 / 20 >}. Значение “хороший” можно, например, описать так: < хороший, [0; 80], >, где  = {< 1 / 80 >, < 0,8 / 75 >, <0,6 / 70 >,< 0,2 / 40 >}.

Функцию принадлежности при наличии k экспертов упрощенно определяют так. Пусть k ₁ экспертов на вопрос о принадлежности х Î Х к  отвечают положительно, а k ₂ = k — k ₁ экспертов на этот же вопрос отвечают отрицательно. Тогда устанавливают следующее значение функции принадлежности:  (x_i) = k ₁ / { k ₁ + k ₂). Для точных оценок приводят парные сравнения функций принадлежности и др. Лингвистические переменные используют для построения расплывчатых моделей и алгоритмов.

Например, приведем нечеткий алгоритм. Пусть у — быстродействие системы, состоящей из двух ЭВМ, а х — быстродействие одной ЭВМ в системе.

Тогда запишем следующий нечеткий алгоритм построения системы с заданным быстродействием:

1°. Если х “мало” и х “незначительно увеличить”, то у “незначительно увеличится”.

2°. Если х “мало” и х “значительно увеличить”, то у “увеличится значительно”.

3°. Если х “велико” и х “увеличить значительно”, то у “увеличится очень значительно”.

Заметим, что значения расплывчатых условных предложений в этом алгоритме можно определить, если даны значения первичных терминов «большой», «маленький» и расплывчатых терминов «незначительно», «значительно», «очень значительно». Значения указанных терминов субъективны и зависят от носителя нечеткого множества. Например, если четкое множество X = {1, 2, 3, …, 10}, то при x = 9 мы имеем, скорее всего, термин «большой». Если четкое множество X = {1, 2, 3, …, 1000}, то при x = 9 мы имеем, скорее всего, термин «маленький».

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

Рис. 10.18. Структурная схема нечеткого алгоритма «Трассировка»

Эту структурную схему (рис. 10.18) можно представить в виде следующих нечетких инструкций:

1°. Сделать шаг трассировки. Если не трассируется “большое” число связей, то перейти к 1°.

2°. Если не трассируется “небольшое” число связей, то сделать “малый” шаг и перейти к 2°.

3°. Если не трассируется “очень маленькое” число связей, то сделать “очень маленький шаг” и перейти к 3°.

4°. Конец работы алгоритма.

Рассмотрим пример размещения БИС на подложке. Структурная схема одного из возможных алгоритмов такого типа показана на рис. 10.19. В терминах нечетких высказываний структурная схема алгоритма может быть переведена в расплывчатые инструкции.

Рис. 10.19. Структурная схема расплывчатого алгоритма размещения

Следует отметить, что конструктор хорошо оперирует расплывчатыми понятиями «большое», «маленькое», «очень маленькое» и эффективно реализует данный алгоритм в интерактивном режиме связи с ЭВМ. При определении степени принадлежности можно формализовать алгоритм и реализовать его на ЭВМ. Отметим, что операция «сделать шаг» в алгоритме (рис. 10.18) может быть сложным алгоритмом перетрассировки всего кристалла или небольшой его области, или простого удаления нескольких трасс и т.п. Реальные варианты нечетких алгоритмов представляют сложную структуру и необходимо разбиение его на части меньшей размерности. Важным в разработке и применении таких алгоритмов является то, что они могут служить эффективным средством распространения и изучения опыта пользователя.

КОНТРОЛЬНЫЕ ВОПРОСЫ

1. Назовите основные виды универсальных алгоритмических моделей.

2. Что представляет собой первая алгоритмическая модель?

3. В чем заключается преобразование слов в произвольных абстрактных алфавитах?

4. Что такое алфавитный оператор?

5. Дайте различные определения алгоритма на основе первой алгоритмической модели.

6. Какие алгоритмы являются равными, а какие – эквивалентными?

7. Определите вторую алгоритмическую модель.

8. Каким образом строятся рекурсивные алгоритмы?

9. Что такое алгоритмы, сопутствующие рекурсивным функциям?

10. Что такое рекурсивные и частично рекурсивные функции?

11. Определите операторы суперпозиции, подстановки и рекурсии.

12. Сформулируйте тезис Черча.

13. В чем заключается метод «разделяй и властвуй»?

14. Постройте третью алгоритмическую модель

15. Опишите принцип работы машины Тьюринга.

16. Приведите правила построения алгоритмов Ван-Хао.

17. Приведите основные правила построения логических схем алгоритмов (ЛСА).

18. В чем заключаются правила построения алгоритмов Маркова?

19. Определите основную идею графических схем алгоритмов (ГСА).

20. Приведите основные правила построения структурных схем алгоритмов.

21. В чем основная идея словесного описания алгоритма?

22. Что представляют собой «жадные» алгоритмы?

23. Для каких задач целесообразно применять «жадные» алгоритмы?

24. Дайте определение нечеткого (расплывчатого) алгоритма.

25. Что такое расплывчатая и лингвистическая переменные?

ЗАДАНИЯ ДЛЯ САМОСТОЯТЕЛЬНОЙ РАБОТЫ

1. Постройте пример первой алгоритмической модели.

2. Постройте пример второй алгоритмической модели.

3. Постройте пример третьей алгоритмической модели.

4. Запишите словесный алгоритм упорядочивания массива из n чисел в порядке возрастания.

5. Запишите словесный алгоритм для вычисления среднего арифметического и наибольшего значений элементов массива целых чисел размерностью до 70.

6. Запишите алгоритм Ван-Хао для вычисления среднего арифметического значения элементов массива чисел размерностью до 20.

7. Составить словесный алгоритм определения элементов множества Z, если Z = X \ Y, где X, Y - множества (| X | = N, | Y | = M).

8. Составить ЛСА поисканаибольшегоэлемента массива A_ij, где i = 1, 2,...,10; j = 1, 2,..., 20.

9. Составить ГСА вычисления по формуле K!

10. Составить ГСА нахождения одинаковых чисел в одномерном массиве длины n.

11. Запишите ГСА вычисления по формуле: .

12. Составить структурную схему алгоритма вычисления по формуле: .

13. Составить ЛСА вычисления по формуле: .

14. Составить структурную схему алгоритма вычисления по формуле: , где .

15. Составить ЛСА алгоритма вычисления по формуле: .

16. Составьте логическую схему алгоритма сортировки для массива А = (3, 41, 52, 26, 38, 57, 9, 49).

17. Приведите пример использования «жадного» алгоритма для решения задачи нахождения наибольшего числа в массиве А = (13, 41, 89, 26, 38, 57, 9, 49).

18. Составьте нечеткий алгоритм перехода перекрестка с односторонним движением.

19. Составьте нечеткий алгоритм перехода перекрестка с двусторонним движением.

 

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

Глава 11. Сложность алгоритмов

Не рассуждайте о том, почему происходит какое-то явление – описывайте его количественно.

Галилей

Временная сложность алгоритма, полиномиальные и экспоненциальные алгоритмы, анализ алгоритмов

ЦЕЛИ

Освоив эту главу, учащиеся должны уметь и знать:

· определять временную сложность алгоритмов;

· определять полиномиальные и экспоненциальные алгоритмы;

·  анализировать алгоритмы.

11.1. Анализ алгоритмов

Важнейшая практическая задача теории и практики проектирования устройств различного типа - это анализ алгоритма. Кроме того, анализ алгоритмов - одна из важнейших задач дискретной математики. С анализом алгоритма связано время работы алгоритма. Оно также связано с ограничениями на характеристики работы ЭВМ и со сложностью решаемой задачи. Для выбора лучшего алгоритма необходимо получение оценок или границ для объема памяти и времени работы ЭВМ, которое потребуется алгоритму для обработки конкретных данных. Для этого необходимо сформулировать количественный критерий для сравнения двух алгоритмов, решающих одну и ту же задачу. В этой связи желательно определить, в каком случае решение задачи считается оптимальным.

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

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

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

В настоящее время алгоритмы сравниваются по скорости роста числа операций. Это связано с тем, что при небольшом размере (n < 50) входных данных одному алгоритму потребуется меньше операций, чем другому. При росте объема входных данных (n > 50) для указанных алгоритмов ситуация может поменяться на противоположную. На основе анализа алгоритмов оценивается, насколько быстро решается задача на массиве входных данных размера n. Следовательно, анализ алгоритма позволяет пользователю выбирать эффективный с его точки зрения алгоритм.

При анализе алгоритмов решения сложных задач (n > 1000) для упрощения различные входные множества разбиваются на классы в зависимости от поведения алгоритма на каждом множестве. Такое разбиение позволяет уменьшить число рассматриваемых возможностей. Например, число различных расстановок множества из 20 неповторяющихся чисел есть 20! = 2432902008176640000.

Применим к данному множеству из 20 чисел алгоритм поиска наименьшего элемента. Как уже было сказано, имеется 2432902008176640000 вариантов расстановки чисел в начальном множестве. Их все можно поместить в один класс. Количество вариантов, когда наименьшее число стоит на втором месте, в 20 раз меньше, а именно 19! = 121645100408832000. Их можно отнести к другому классу. Таким образом, можно разбить все входные множества на N разных классов. Для описанного алгоритма разбиение основывается на местоположении элемента, имеющего наименьшее значение. В результате получается 20 классов. После выделения классов можно проанализировать поведение алгоритма на одном множестве из каждого класса. Это разбиение выполняется на основе принципа «разделяй и властвуй», приведенного выше. Если разбиение выбрано правильно с точки зрения пользователя, то на всех множествах входных данных одного класса алгоритм производит одинаковое количество операций, а на множествах из другого класса это количество операций будет другим.

В алгоритмах обычно выделяют операции двух типов:

- сравнение;

- арифметические операции:

· аддитивные операторы;

· мультипликативные операторы.

Существует тезис Тьюринга: любой алгоритм может быть реализован на машине Тьюринга. Математически доказано, что если задача не может быть решена на машине Тьюринга, то она не может быть решена ни на какой другой автоматической вычислительной машине.

Один из основных результатов Тьюринга — разделение всех задач, решаемых с помощью алгоритмов, на два типа (класса).

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

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

2 класс. Это класс решаемых задач, т.е. задач, для которых могут быть написаны и реализованы алгоритмы. К ним относятся задачи, решаемые на основе:

· полиномиальных алгоритмов;

· экспоненциальных алгоритмов.

Экспоненциальными алгоритмами называются алгоритмы, у которых время решения экспоненциально растет по мере увеличения размера входных данных. К ним относятся алгоритмы типа 2 ⁿ, n!, n!! и т.п. Здесь n — количество входов алгоритма.

К экспоненциальным алгоритмам относятся алгоритмы полного перебора при нахождении оптимального решения.

Пример 1. Найти все одинаковые числа в массиве натуральных чисел размера n ´ n.

Пример 2. Задача о коммивояжере. Пусть некоему коммивожеру необходимо посетить n городов и вернуться в исходную точку, причем каждый город он может посетить только один раз. Найти такой маршрут коммиявожера, чтобы пройденный им путь был минимальным.

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

Полиномиальные алгоритмы - это такие алгоритмы, при реализации которых на ЭВМ, время решения изменяется в зависимости от размера входных данных (например, числа вершин или ребер графа). Эта зависимость представляется в виде полиномов, где число входов n принимает значения n, n ², n ³,... Если число входов равно n, то имеем дело с «линейным» алгоритмом. Линейный алгоритм - это алгоритм, у которого зависимость времени решения от числа входных данных носит линейный характер. Другими словами, полиномиальные алгоритмы – это алгоритмы, у которых время решения находится в полиномиальной зависимости от изменения размера входных данных.

Пример 3. Пусть время решения произвольного алгоритма находится в следующей зависимости от размера входных данных: t = an + b, где n это числа из множества A = {1, 5, 10, 15, 20, 25, 30}; a, b – постоянные величины (a = 20, b = 10). График временной сложности алгоритма показан на рис. 11.1 (Функция 1).

Пример 4. Пусть время решения произвольного алгоритма находится в следующей зависимости от размера входных данных: t = an ² - bn + c, где n - числа из множества A (пример 3); a, b, c – постоянные величины (a = 1, b = 7, c = 10). График временной сложности алгоритма представлен на рис. 11.1 (Функция 2).

Рис. 11.1. Сравнение временной сложности функций

График функции 1 отражает линейную зависимость времени работы алгоритма от числа входных данных, а график функции 2 - квадратичную.

Анализируя графики, видно, что существует некоторая область для входных данных небольшого размера, где временная сложность «квадратичных» алгоритмов лучше, чем линейных. Так, например, на рис. 11.1 видно, что в области, где n меняется от 1 до приблизительно 27, квадратичный алгоритм работает быстрее линейного. Затем (n > 27) линейный алгоритм работает значительно быстрее.

Аппроксимированные графики временной сложности полиномиальных алгоритмов различных классов показаны на рис. 11.2.

Рис. 11.2. Графики временной сложности различных классов алгоритмов

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

Рис. 11.3. Классификация алгоритмов

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

Задачей на допустимость называется задача определения хотя бы одного возможного решения.

Задачей на оптимальность считается задача определения допустимого решения, дающего экстремум функции.

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

Согласно классическому учебнику Кормена, Лейзерсона и Ривеста «Алгоритмы: построение и анализ» запись f (n) = Q (g (n)) включает в себя две оценки временной сложности алгоритма: верхнюю и нижнюю. Их разделяют на f (n) = O (g (n)) и f (n) = W (g (n)).

Говорят, что f (n) = O (g (n)), если найдется такая константа c > 0 и такое число входных данных n₀, что 0 £ f (n) £ cg (n) для всех n ³ n ₀.

Говорят, что f (n) = W (g (n)), если найдется такая константа c > 0 и такое число n ₀, что 0 £ cg (n) £ f (n) для всех n ³ n ₀.

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

Асимптотически обозначают, например, 8 n ⁴ +5 n ³ +13 n ² + 9 n + 4» 8 n ⁴ + Q (n ³) + Q (n ²) + Q (n)» Q (n ⁴). То есть какой бы ни была функция k (n) = Q (n ³), Q (n ²), Q (n) в левой части, сумма 8 n ⁴ + Q (n ³) +Q (n ²) +Q (n), есть Q (n ⁴). Тогда время работы полиномиальных алгоритмов такого типа составляет не более Q (n^k), для некоторой константы, не зависящей от длины входа.

В теории встречаются задачи, для которых существует решающий их алгоритм, но любой такой алгоритм работает «долго» — время его работы не есть O (n^k) ни для одного фиксированного числа k. Согласно работе Кормена, Лейзерсона и Ривеста «Алгоритмы: построение и анализ» полиномиальные алгоритмы представляют собой некую границу между «практическими» алгоритмами и алгоритмами, представляющими лишь теоретический интерес.

Отдельный класс составляют задачи, называемые «NP -полными». Для них не найдены полиномиальные алгоритмы, однако и не доказано, что таких алгоритмов не существует. Изучение NP -полных задач связано с нерешенными проблемой Р = NP или Р ≠ NP. Сокращение NP происходит от английских слов Nondeterministic Polynomial time, что переводится как недетерминированное полиномиальное время.

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

В теории алгоритмов при исследовании NP -полноты рассматриваются в основном задачи разрешения, то есть задачи, в которых требуется дать ответ «да» или «нет» на некоторый вопрос. Формально задачу разрешения можно рассматривать как функцию, отображающую множество условий I в множество решений S = {0, 1 }, где (1 = «да», 0 = «нет»). В этой связи для определения NP -полноты многие задачи преобразуют к указанному виду.

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

Поэтому данные задачи выделяют в особый класс оптимизационных комбинаторных задач на графах. В задачах такого класса общее число вариантов решения равно числу перестановок из n вершин графов, то есть C_n = n!, а с учетом ограничений на формирование подмножеств (частей графа в задаче разбиения) – числу сочетаний из n вершин по m частей, то есть  = n! / m!(n – m)!

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

Говорят, что алгоритм решает задачу за время O (T (n ²)), если на входном данном, например битовой строке i длины n, алгоритм работает за время O (T (n ²)).

Говорят, что функция f:{0, 1} ® {0, 1} вычислима за полиномиальное время, если существует полиномиальный алгоритм, который для любого элемента y Î {0, 1} выдает результат f (y).

Интуитивно класс Р можно представлять себе как класс задач, которые можно “быстро” решить, а класс NP — как класс задач, которые нельзя решить за полиномиальное время. Известно, что ни для одной NP -полной задачи не найден полиномиальный разрешающий алгоритм.

Конечно, нет уверенности, что однажды не будет найден полиномиальный алгоритм для решения NP -полной задачи, это и будет доказательством, что Р = NP.

11.2. Сложность алгоритмов

Изменение алгоритма во времени или время, затраченное алгоритмом как функция размерности задачи, называется временной сложностью алгоритма (ВСА).

ВСА — это количество единиц времени, требуемое для обработки входных данных задачи.

Обозначается ВСАO [ f_A (n)]. Функция f_A (n) дает верхнюю границу для максимального числа операций, которые должен выполнить алгоритм для решения любой задачи размерности n.

Основные операции — это сдвиг, сравнение, сложение и тому подобное.

Существует теорема, что для достаточно больших n линейные алгоритмы всегда эффективнее квадратичных, кубичных и т.д. алгоритмов.

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

Все алгоритмы, у которых ВСАO (n), O (n ²), O (n ³), считаются эффективными и применяются при решении практических задач.

Все алгоритмы, у которых ВСАO (n ⁵) и выше, считаются не эффективными для использования на практике.

Кроме ВСА, важной характеристикой является сложность алгоритма (СА). Сложность алгоритма характеризуется числом выполняемых операций N и общим объемом используемой информации.

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

С числом операций алгоритма связано время его выполнения на конкретной ЭВМ. Объем информации связан с объемом памяти ЭВМ, необходимой для реализации этого алгоритма. Значит, время реализации алгоритма есть функция T = f (N, V).

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

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

N = { Q ₁, Q ₂,..., Q_r },

где Q_i — количество операций в исследуемом классе задач,

N = , P_i = Q_i / N — относительная частота операций.

Умножая время выполнения каждой операции на количество этих операций и суммируя результаты по всем операциям, получим время реализации алгоритма:

T = .

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

B_i = t_i / t _э,

где t_i — время реализации i -й операции; t _э — время реализации эталонной операции сложения.

Тогда количество условных элементарных операций составит

N = ,

а общее время их реализации — T _э = N _э t _э.

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

И = Ип + Ии + Ив + Ипр,

где И — общий объем информации; Ип — объем программной информации; Ии — объем исходной информации; Ив — объем выходной информации; Ипр — объем промежуточной информации.

Тогда обобщенный коэффициент сложности Ксл = N э/И, т.е. он характеризуется числом эталонных операций, выполняемых при обработке единицы информации.

В современных ЭВМ распределением памяти занимается операционная система, и пользователь зачастую не знает, какую память он использует.

В современных ЭВМ объем внешней памяти значительно опережает объем оперативной памяти:

V _в.п. >> V _о.п.,

поэтому T = f (N, V _в.п.).

Основной путь повышения скорости реализации алгоритма — это параллельное выполнение большого числа операций.

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

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

Временем работы алгоритма называется число элементарных шагов, которые он выполняет. Каждая строка псевдокода требует фиксированного числа операций (если только это не словесное описание каких-то сложных действий — типа «отсортировать все точки по координате x»). Также необходимо различать вызов процедуры (исполняемый за фиксированное число операций) и её выполнение, которое может быть долгим.

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

· Зная время работы в худшем случае, можно гарантировать, что выполнение алгоритма для всех входов данной размерности займет не более определенного промежутка времени вне зависимости от конкретного входа;

· На практике ситуации, когда время работы алгоритма близко к максимуму, встречаются довольно часто.

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

Время работы в среднем может быть довольно близко к времени работы в худшем случае.

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

Предположим, что алгоритм разбивает задачу размера n на а подзадач, каждая из которых имеет в b раз меньший размер. Считаем, что разбиение требует времени D (n), а соединение полученных решений — времени С (n). Тогда получаем соотношение для времени работы Т (n) на задачах размера n (в худшем случае): Т(n) = aT (n / b) + D (n) + C (n). Это соотношение справедливо для достаточно больших n, когда задачу имеет смысл разбивать на подзадачи. Для малых n, когда такое разбиение невозможно или не нужно, применяется какой-либо прямой метод решения задачи. Так как n ограничено, время работы тоже не превосходит некоторой константы.

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

Основной метод повышения скорости работы алгоритма - это параллельные вычисления. В соответствии с гипотезой Минского параллельные машины, выполняющие последовательную программу над n множествами данных, повышают производительность, по крайней мере, на множитель O (log n).

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

КОНТРОЛЬНЫЕ ВОПРОСЫ

1. Дайте определение понятия алгоритма.

2. Назовите основные свойства алгоритма.

3. Перечислите виды алгоритмов.

4. Приведите классификацию алгоритмов.

5. Назовите основные виды универсальных алгоритмических моделей.

6. Что представляет собой первая алгоритмическая модель?

7. Каким образом строятся рекурсивные алгоритмы?

8. Опишите принцип работы машины Тьюринга.

9. Приведите основные правила построения ЛСА.

10. Приведите основные правила построения ГСА.

11. Приведите основные правила построения структурных схем алгоритмов.

12. Что представляют собой «жадные» алгоритмы?

13. Для каких задач наиболее целесообразно применять «жадные» алгоритмы?

14. Как определяется временная сложность алгоритма?

15. Перечислите параметры, характеризующие эффективность алгоритма.

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

17. Определите алгоритмы подклассов P, NP, NPC.

18. Поясните принципы анализа алгоритмов.

19. Каким образом определяется время работы алгоритмов?

20. Перечислите методы математического программирования.

21. Приведите примеры и дайте определение задач на допустимость и оптимальность.

ЗАДАНИЯ ДЛЯ САМОСТОЯТЕЛЬНОЙ РАБОТЫ

1. Дана последовательность чисел x ₁, x ₂,..., х _n. Покажите, что за время O (n log n) можно определить, есть ли в этой последовательности три одинаковых числа.

2. Как записать выражение n ³ /1000 - 100 n ² - 100 n + 3 с помощью O(n) - обозначений?

3. Дан массив S из n действительных чисел, а также число x. Как за время O (n log n) определить, можно ли представить x в виде суммы трех элементов массива S?

4. При каком наименьшем значении n алгоритм, требующий 1000 n ² операций, эффективнее алгоритма, требующего 3 ⁿ операций?

5. Пусть имеется алгоритм, решающий задачу размера n за время f (n) микросекунд. Каков максимальный размер задачи, которую он может решить за время t? Заполнить таблицу.

 

	1 сек	1 минута	1 час	1 день	1 месяц	1 год	1 век
log n
n
n log n
n2
n3
n4
2n
3n
n!

6. Следуя примеру, покажите работу сортировки слиянием для массива А = (3, 41, 52, 26, 38, 57, 9, 49).

7. Напишите текст процедуры СЛИЯНИЕ(A, p, q, r).

8. Сортировку вставками можно оформить как рекурсивную процедуру: желая отсортировать A [1,..., n ], мы рекурсивно сортируем А [1, …, n - 1], а затем ставим А [ n ] на нужное место в отсортированном массиве A [1, …, n - 1]. Напишите рекуррентное соотношение для времени работы такой процедуры.

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

 

 

Тестовые задания к модулю 2