Главная страница
Навигация по странице:

  • Миков, А.И., Лапина О.Н.

  • 1. Сложность алгоритмов с одним исполнителем 1.1. Понятие сложности алгоритма

  • 1.2. Функция сложности циклических алгоритмов

  • циклы

  • Циклы

  • Максимальная сложность

  • 1.3. Функция сложности рекурсивных алгоритмов

  • Уч.Пособие2013-4. Учебное пособие Краснодар 2013 удк 681 07 ббк 32. 973. 26018 75 м 594 Рецензенты


    Скачать 0.64 Mb.
    НазваниеУчебное пособие Краснодар 2013 удк 681 07 ббк 32. 973. 26018 75 м 594 Рецензенты
    АнкорУч.Пособие2013-4.doc
    Дата05.04.2017
    Размер0.64 Mb.
    Формат файлаdoc
    Имя файлаУч.Пособие2013-4.doc
    ТипУчебное пособие
    #194
    страница1 из 7

    Подборка по базе: Учебно-методическое пособие по изучению дисциплины и выполнению , РАБ. ТЕТР. 5 2013а ГЕОЭКОЛ. ЯШИН И.М.(+) (2).doc, Учеб. пособие УиЭ ПЗРК. ч. 1.doc, Учеб. пособие УиЭ ПЗРК. ч. 1.doc, Учеб. пособие ОПЗРК.doc, Учеб. пособие ОПЗРК.doc, Pashchenko O.I. Informatsionnie tehnologii v obrazovanii - Uch-m, Всекубанский классный час для 3 класса по теме Краснодарскому кр, Всекубанский классный час для 3 класса по теме Краснодарскому кр, лазаренко Л.В. Суздальцева Л.С. ПОСОБИЕ для студентов всех факу.
      1   2   3   4   5   6   7


    Министерство образования и науки Российской Федерации

    КУБАНСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ
    Кафедра вычислительных технологий

    А.И. МИКОВ, О.Н. ЛАПИНА

    ВЫЧИСЛИМОСТЬ

    И СЛОЖНОСТЬ АЛГОРИТМОВ

    Учебное пособие

    Краснодар

    2013

    УДК 681.3.07

    ББК 32.973.26-018.2.75

    М 594

    Рецензенты:

    Доктор физико-математических наук, профессор

    С.В. Русаков

    Доктор физико-математических наук, профессор

    Е.А. Семенчин

    Миков, А.И., Лапина О.Н.

    М 594 Вычислимость и сложность алгоритмов: учеб. пособие / А.И. Миков, О.Н. Лапина. Краснодар: Кубан. гос. ун-т, 2013. 79 с. 200 экз.

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

    Адресуется студентам, обучающимся по направлениям магистратуры и бакалавриата 010300 – Фундаментальные информатика и информационные технологии, 010400 – Прикладная математика и информатика и 010500 – Математическое обеспечение и администрирование информационных систем.

    УДК 681.3.07

    ББК 32.973.26-018.2.75
     Кубанский государственный университет, 2013

     Миков А.И., Лапина О.Н., 2013


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

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

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

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

    1. Сложность алгоритмов с одним исполнителем
    1.1. Понятие сложности алгоритма

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

    Постоянная задача для программистов – сделать программу, работающую хотя бы немного быстрее и попытаться заставить ее работать в условиях ограниченной памяти. Для ряда областей ресурсы настолько критичны, что может возникнуть проблема целесообразности всего проекта из-за неэффективной работы программы. К таким областям относятся системы реального времени (real-time systems).

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

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

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

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

    Поэтому сложность алгоритма α рассматривается как функция от некоторого числового параметра V, характеризующего исходные данные. Обозначим: Tα(V) – временная сложность алгоритма α; Sα(V) – емкостная сложность.

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

    Рассмотрим примеры:

    1. Задача вычисления факториала числа х (x> 0).

    Программа итеративного решения задачи имеет следующий вид:

    function Factorial (x: integer): integer;

    var m, i: integer;

    begin m := 1;

    for i := 2 to x do

    m := m*i;

    Factorial := m;

    end.

    Количество операций здесь подсчитать легко: один раз выполняется оператор присваивания: m:= 1; тело цикла (умножение и присваивание) выполняется (х – 1) раз; один раз выполняется присваивание Factorial := m. Если сложность каждой элементарной операции считать равной единице, то временная сложность приведенного алгоритма будет равна: 1 + 2(х – 1) + 1 = 2х. Из этого анализа ясно, что за параметр V удобно принять x.

    1. Задача отыскания скалярного произведения двух векторов A=(a1, a2, …, ak) и B=(b1, b2, …, bk). Вектор входных данных X=(A,B). Стандартный алгоритм выполняет циклическое сложение попарных произведений компонент векторов. Количество операций будет пропорционально k, т.е. можно взять V = k – сложность алгоритма зависит от количества компонент и не зависит от самих компонент векторов.

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

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

    Задача минимизации временной сложности может быть поставлена так: среди всех алгоритмов, решающих задачу P, отыскать такой алгоритм α, для которого функция Tα(X) будет принимать минимальные значения на выбранном подмножестве S значений исходных данных . Задача минимизации емкостной сложности возникает реже, в силу архитектурных особенностей современных ЭВМ. Программе может быть доступна практически неограниченная область памяти – виртуальная память. Недостаточное количество основной памяти приводит лишь к некоторому замедлению работы из-за обменов с дисков. Поэтому в дальнейшем будем рассматривать в основном временную сложность алгоритмов.

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

    Другой вопрос связан с классификацией алгоритмов. Как быстро растет функция сложности алгоритма Tα(X), с ростом значений аргумента? Существуют алгоритмы с линейной зависимостью временной сложности; полиномиальной зависимостью. А существуют алгоритмы, сложность которых увеличивается быстрее любого полинома. Поэтому множество исследований посвящено вопросу: «возможен ли для данной задачи полиномиальный алгоритм либо нет?».

    1.2. Функция сложности циклических алгоритмов

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

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

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

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

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

    Проведем анализ алгоритма, содержащего вложенные циклы for. Процедура MULTIPLY перемножает две квадратные матрицы и , получая матрицу .
    procedure MULTIPLY (n: integer; a, b: matrix; var c: matrix);

    var i, j, k: integer;

    begin

    for i :=1 to n do

    for j :=1 to n do

    begin c[i, j] := 0;

    for k :=1 to n do

    c[i, j] := c[i, j] + a[i,k]*b[k,j];

    end;

    end.

    Тип данных matrix определен вне процедуры как двумерный массив. Простой анализ текст показывает, что за параметр сложности данных V можно взять размер матриц n. Процедура представляет собой цикл по переменной i, тогда ее сложность

    Tα(X) = n* (сложность тела цикла 1).

    В свою очередь

    (сложность тела цикла 1) = (сложность тела цикла 2).

    Тело цикла 2 состоит из одного оператора присваивания и цикла 3. Таким образом

    Tα(X) = n* (n*(1+n* (сложность тела цикла 3))).

    Тело внутреннего цикла включает умножение, сложение и присваивание (3 операции) окончательно получаем

    .

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

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

    Рассмотрим пример процедуры.
    for i := 1 to x do

    for j :=i to x do

    begin

    тело цикла;

    end.

    Входная переменная здесь принимает любое целое значение из промежутка .

    Тело цикла выполняется раз.

    Верхняя граница сложности равна

    .

    Среднее значение сложности, если все значения х равновероятны

    .
    Циклы while и repeat, анализировать сложнее, так как условия повторения цикла вычисляются в теле самого цикла.

    Рассмотрим в качестве примера вычисление вещественного значения корня методом Ньютона.

    Задача сводится к отысканию корня уравнения . Корень отыскивается с помощью итерационного процесса



    Выбираем некоторое начальное значение z0. Окончание процесса происходит, когда корень найден с заданной точностью eps.

    function P_root (p: integer; x, z0, eps : real) : real;

    var i: integer;

    y, zn, z: real;

    begin

    z:= z0;
    repeat

    zn:=z; y:=zn;

    for i:=2 to p-1 do y:=y*zn;

    z:=(p - 1)*zn/p + x/(p*y);

    until abs(z - zn) < eps;

    P_root :=z;

    end.

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

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

    Рассмотрим алгоритм поиска заданного элемента в векторе А:

    function Locate (data: integer): integer;

    var i: integer;

    fl: boolean;

    begin

    fl := false; i := 1;

    while (not fl) and (i <= N) do

    begin

    if A[i] = data then fl := true

    else i := i +1;

    end;

    if ( not fl) then i := 0;

    Locate := i;

    end.

    Если искомый элемент находится в конце списка, то программе придется выполнить N шагов – это наихудший случай. Наилучший случай будет, когда искомый элемент находится в списке на первой позиции. Тогда алгоритму придется сделать только один шаг. Оба эти случаи маловероятны.

    Если же элементы списка беспорядочно смешаны, то искомый элемент может находиться в любом месте списка. Чтобы найти требуемый элемент, в среднем потребуется сделать N/2 сравнений.

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

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

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

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

    1.3. Функция сложности рекурсивных алгоритмов

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

    Рассмотрим сначала случай прямой рекурсии с единственным рекурсивным вызовом в теле процедуры. Примером такого алгоритма является алгоритм Евклида вычисления наибольшего общего делителя.

    Процедура вычисления НОД (GCD) для двух целых чисел m и n.
      1   2   3   4   5   6   7


    написать администратору сайта