Практическая работа №11 по дисциплине: Теория алгоритмов наименование работы: Анализ рекурсивного алгоритма.


Смоленский колледж телекоммуникаций
(филиал) федерального государственного образовательного
бюджетного учреждения высшего профессионального образования
«Санкт-Петербургский государственный университет телекоммуникаций
им. проф. М.А. Бонч-Бруевича»
Практическая работа №11
по дисциплине: Теория алгоритмов
наименование работы: Анализ рекурсивного алгоритма.
для специальностей: 230115, 09.02.03
работа рассчитана на 2 часа
составлена преподавателем: Скряго О.С.
Смоленск, 2014
1. Цель работы: овладеть навыками анализа рекурсивных алгоритмов.
2. Литература:
2.1. Балюкевич, Э.Л. Математическая логика и теория алгоритмов [Электронный ресурс]: учебное пособие/ Э.Л. Балюкевич, Л.Ф.Ковалева.— М.: Евразийский открытый институт, 2009.— 188 c. ISBN:978-5-374-00220-1
2.2. Верещагин, Н.К. Лекции по математической логике и теории алгоритмов. Часть 3. Вычислимые функции [Электронный ресурс]/ Н.К. Верещагин., А. Шень.— М.: МЦНМО, 2012.— 160 c. ISBN:978-5-4439-0014-8
2.3. Гаврилов, Г.П. Задачи и упражнения по дискретной математике [Электронный ресурс]: учебное пособие/ Г.П. Гаврилов, А.А Сапоженко.— М.: ФИЗМАТЛИТ, 2009.— 416 c. ISBN:978-5-9221-0477-7
3. Подготовка к работе:
3.1. Повторить тему «Введение в анализ алгоритмов».
3.2. Подготовить бланк отчета (см.п.7).
3.3. Ответить на вопросы допуска:
3.3.1. Что такое алгоритм?
3.3.2. Какие существуют свойства алгоритмов?
3.3.3. Что такое анализ алгоритма?
4. Основное оборудование: ПЭВМ
5. Задание:
Выполните задание согласно варианту.

Таблица 1.
Вариант Задача
1 Создайте программы, реализующие рекурсивный и итеративный алгоритмы вычисления n-го числа Фибоначчи. Сравните время их работы для n = 5, 25, 45, 65, 85, 100. Чтобы избежать переполнения, для n < 100 используйте беззнаковое представления чисел размером в 8 байт( тип unsigned long в языке Си или int64 в языке Паскаль). Результаты сравнения оформите в виде таблицы и в виде графика.
2 Проанализируйте вычислительную сложность алгоритмов умножения чисел. На основе анализа поведите сравнения данных алгоритмов.
3 Разработать два алгоритма возведения числа в целую неотрицательную степень, различающиеся по сложности. Для разработанных алгоритмов определите вычислительную сложность алгоритма.
4 Разработать два алгоритма возведения числа в целую неотрицательную степень, различающиеся по сложности. Для разработанных алгоритмов проведите сравнительный анализ.
5 Проанализируйте пространственную сложность алгоритмов умножения чисел. На основе анализа поведите сравнения данных алгоритмов.
6 Создайте программы, реализующие рекурсивный и итеративный алгоритмы вычисления n-го числа Фибоначчи. Сравните время их работы для n = 5, 25, 45, 65, 85, 100. Чтобы избежать переполнения, для n < 100 используйте беззнаковое представления чисел размером в 8 байт( тип unsigned long в языке Си или int64 в языке Паскаль). Результаты сравнения оформите в виде таблицы и в виде графика.
7 Разработать два алгоритма возведения числа в целую неотрицательную степень, различающиеся по сложности. Для разработанных алгоритмов определите вычислительную сложность алгоритма.
8 Проанализируйте вычислительную сложность алгоритмов умножения чисел. На основе анализа поведите сравнения данных алгоритмов.
9 Разработать два алгоритма возведения числа в целую неотрицательную степень, различающиеся по сложности. Для разработанных алгоритмов определите вычислительную сложность алгоритма.
10 Разработать два алгоритма возведения числа в целую неотрицательную степень, различающиеся по сложности. Для разработанных алгоритмов проведите сравнительный анализ.

6. ПОРЯДОК ВЫПОЛНЕНИЯ РАБОТЫ.
6.1. Ознакомиться с заданием.
6.2. Определить номер варианта (в соответствии с номером в журнале).
6.3. Выполнить задание 5 письменно.
6.4. Сообщить преподавателю о выполненных заданиях.
6.5. Повторить правила техники безопасности:
Правила техники безопасности в компьютерном классе.
Перед началом работы необходимо убедиться в отсутствии видимых повреждений аппаратуры.
Работа с компьютером производится строго по указаниям преподавателя.
Запрещается:
Разъединять или соединять разъемы аппаратуры;
Прикасаться к экрану монитора;
Включать и выключать аппаратуру без указания преподавателя;
Класть какие-либо предметы на монитор, системный блок или клавиатуру;
Работать во влажной одежде, а также влажными или грязными руками;
Пытаться самостоятельно исправлять возникшую в аппаратуре неисправность.
Включите компьютер.
Включите в сеть стабилизатор напряжения (если он имеется).
Включите принтер (если он имеется).
Включите монитор.
Включите системный блок (большая кнопка на передней панели).
Выключение компьютера.
Завершите выполнение всех программ.
Выполните команду: Пуск Завершение работы Выключить компьютер (Alt+F4→ Завершение работы).
Выключите системный блок.
6.6. Приступить к выполнению тестирование программ.
6.7.Оформить отчет.
7. Содержание отчета:
7.1. Название и цель работы.
7.2 Ответы на вопросы допуска.
7.2. Указать номер варианта, привести условия задач своего варианта.
7.3. Представить выполненные задания согласно варианта, текст программы с комментариями.
7.4. Ответы на контрольные вопросы.
8. Контрольные вопросы:
8.1. Приведите пример рекурсивного алгоритма?
8.2. Как провести анализ рекурсивного алгоритма?
8.3. Приведите примеры классов сложности алгоритмов?
8.4. Какие асимптотические оценки алгоритма вы знаете?
8.5.Приведите примеры алгоритма порядково - зависимого по трудоемкости?
Составил преподаватель __________________________Скряго О.С.
9. Приложение:
При использовании алгоритмов для решения практических задач мы сталкиваемся с проблемой рационального выбора алгоритма решения задачи. Решение проблемы выбора связано с построением системы сравнительных оценок, которая в свою очередь существенно опирается на формальную модель алгоритма.
Будем рассматривать в дальнейшем, придерживаясь определений Поста, применимые к общей проблеме, правильные и финитные алгоритмы, т.е. алгоритмы, дающие 1-решение общей проблемы. В качестве формальной системы будем рассматривать абстрактную машину, включающую процессор с фон- Неймановской архитектурой, поддерживающий адресную память и набор «элементарных» операций соотнесенных с языком высокого уровня.
В целях дальнейшего анализа примем следующие допущения:
каждая команда выполняется не более чем за фиксированное время;
исходные данные алгоритма представляются машинными словами по битов каждое.
Конкретная проблема задается N словами памяти, таким образом, на входе алгоритма – N = N* бит информации. Отметим, что в ряде случаев, особенно при рассмотрении матричных задач N является мерой длины входа алгоритма, отражающей линейную размерность.
Программа, реализующая алгоритм для решения общей проблемы состоит из М машинных инструкций по м битов – М = М* м бит информации.
Кроме того, алгоритм может требовать следующих дополнительных ресурсов абстрактной машины:
Sd – память для хранения промежуточных результатов;
Sr – память для организации вычислительного процесса (память, необходимая для реализации рекурсивных вызовов и возвратов).
При решении конкретной проблемы, заданной N словами памяти алгоритм выполняет не более, чем конечное количество «элементарных» операций абстрактной машины в силу условия рассмотрения только финитных алгоритмов. В связи с этим введем следующее определение:
Под трудоёмкостью алгоритма для данного конкретного входа – Fa(N), будем понимать количество «элементарных» операций совершаемых алгоритмом для решения конкретной проблемы в данной формальной системе.
Комплексный анализ алгоритма может быть выполнен на основе комплексной оценки ресурсов формальной системы, требуемых алгоритмом для решения конкретных проблем. Очевидно, что для различных областей применения веса ресурсов будут различны, что приводит к следующей комплексной оценке алгоритма:
c1 * Fa(N) + c2 * + c3 * Sd + c4 * Sr, где ci – веса ресурсов.
При более детальном анализе трудоемкости алгоритма оказывается, что не всегда количество элементарных операций, выполняемых алгоритмом на одном входе длины N, совпадает с количеством операций на другом входе такой же длины. Это приводит к необходимости введения специальных обозначений, отражающих поведение функции трудоемкости данного алгоритма на входных данных фиксированной длины.
Пусть DА – множество конкретных проблем данной задачи, заданное в формальной системе. Пусть D DА – задание конкретной проблемы и |D| = N.
В общем случае существует собственное подмножество множества DА, включающее все конкретные проблемы, имеющие мощность N:
обозначим это подмножество через DN: DN = {D DN,: |D| = N};
обозначим мощность множества DN через MDN → MDN = |DN |.
Тогда содержательно данный алгоритм, решая различные задачи размерности N, будет выполнять в каком-то случае наибольшее количество операций, а в каком-то случае наименьшее количество операций. Ведем следующие обозначения:
1. Fa(N) – худший случай – наибольшее количество операций, совершаемых алгоритмом А для решения конкретных проблем размерностью N:
DDN
Fa(N) = max {Fa (D)} – худший случай на DN
2. Fa(N) – лучший случай – наименьшее количество операций, совершаемых алгоритмом А для решения конкретных проблем размерностью N:
DDN
Fa(N) = min {Fa (D)} – лучший случай на DN
3. Fa(N) – средний случай – среднее количество операций, совершаемых алгоритмом А для решения конкретных проблем размерностью N:
DDN
Fa(N) = (1 / MDN)* {Fa (D)} – средний случай на DN
В зависимости от влияния исходных данных на функцию трудоемкости алгоритма может быть предложена следующая классификация, имеющая практическое значение для анализа алгоритмов:
Количественно-зависимые по трудоемкости алгоритмы
Это алгоритмы, функция трудоемкости которых зависит только от размерности конкретного входа, и не зависит от конкретных значений:
Fa (D) = Fa (|D|) = Fa (N)
Примерами алгоритмов с количественно-зависимой функцией трудоемкости могут служить алгоритмы для стандартных операций с массивами и матрицами – умножение матриц, умножение матрицы на вектор и т.д.
Параметрически-зависимые по трудоемкости алгоритмы
Это алгоритмы, трудоемкость которых определяется не размерностью входа (как правило, для этой группы размерность входа обычно фиксирована), а конкретными значениями обрабатываемых слов памяти:
Fa (D) = Fa (d1,…,dn) = Fa (P1,…,Pm), m n
Примерами алгоритмов с параметрически-зависимой трудоемкостью являются алгоритмы вычисления стандартных функций с заданной точностью путем вычисления соответствующих степенных рядов. Очевидно, что такие алгоритмы, имея на входе два числовых значения – аргумент функции и точность выполняют существенно зависящее от значений количество операций.
а) Вычисление xk последовательным умножением Fa(x, k) = Fa (k).
б) Вычисление ex=(xn/n!), с точностью до Fa = Fa (x, )
Количественно-параметрические по трудоемкости алгоритмы
Однако в большинстве практических случаев функция трудоемкости зависит как от количества данных на входе, так и от значений входных данных, в этом случае:
Fa (D) = Fa (||D||, P1,…,Pm) = Fa (N, P1,…,Pm)
В качестве примера можно привести алгоритмы численных методов, в которых параметрически-зависимый внешний цикл по точности включает в себя количественно-зависимый фрагмент по размерности.
Порядково-зависимые по трудоемкости алгоритмы
Среди разнообразия параметрически-зависимых алгоритмов выделим еще оду группу, для которой количество операций зависит от порядка расположения исходных объектов.
Пусть множество D состоит из элементов (d1,…,dn), и ||D||=N,
Определим Dp = {(d1,…,dn)}-множество всех упорядоченных N-ок из d1,…,dn, отметим, что |Dp|=n!.
Если Fa (iDp) Fa (jDp), гдеiDp, jDp Dp, то алгоритм будем называть порядково-зависимым по трудоемкости.
Примерами таких алгоритмов могут служить ряд алгоритмов сортировки, алгоритмы поиска минимума и максимума в массиве. Рассмотрим более подробно алгоритм поиска максимума в массиве S, содержащим n элементов:
MaxS (S,n; Max)
Max S1
For i2 to n
if Max < Si
then Max Si (количество выполненных операций присваивания зависит от порядка следования элементов массива)
При анализе поведения функции трудоемкости алгоритма часто используют принятые в математике асимптотические обозначения, позволяющие показать скорость роста функции, маскируя при этом конкретные коэффициенты.
Такая оценка функции трудоемкости алгоритма называется сложностью алгоритма и позволяет определить предпочтения в использовании того или иного алгоритма для больших значений размерности исходных данных.
В асимптотическом анализе приняты следующие обозначения [6]:
Пусть f(n) и g(n) – положительные функции положительного аргумента, n ≥ 1 (количество объектов на входе и количество операций – положительные числа), тогда:
n0
f,gnc2g(n)
f(n)
c1g(n)
f(n) = (g(n)), если существуют
положительные с1, с2, n0, такие, что:
с1 * g(n) f(n) c2 * g(n), при n > n0
Обычно говорят, что при этом функция g(n) является асимптотически точной оценкой функции f(n), т.к. по определению функция f(n) не отличается от функции g(n) с точностью до постоянного множителя.
Отметим, что из f(n) = (g(n)) следует, что g(n) = (f(n)).
Примеры:
1) f(n)=4n2+nlnN+174 – f(n)= (n2);
2) f(n)=(1) – запись означает, что f(n) или равна константе, не равной нулю, или f(n) ограничена константой на : f(n) = 7+1/n = (1).
В отличие от оценки , оценка О требует только, что бы функция f(n) не превышала g(n) начиная с n > n0, с точностью до постоянного множителя:
cg(n)
f(n)

c > 0, n0 > 0 :
0 f(n) c * g(n), n n0
Вообще, запись O(g(n)) обозначает класс функций, таких, что все они растут не быстрее, чем функция g(n) с точностью до постоянного множителя, поэтому иногда говорят, что g(n) мажорирует функцию f(n).
Например, для всех функций:
f(n)=1/n, f(n)= 12, f(n)=3*n+17, f(n)=n*Ln(n), f(n)=6*n2 +24*n+77
будет справедлива оценка О(n2 )Указывая оценку О есть смысл указывать наиболее «близкую» мажорирующую функцию, поскольку например для f(n)= n2 справедлива оценка О(2n), однако она не имеет практического смысла.
В отличие от оценки О, оценка является оценкой снизу – т.е. определяет класс функций, которые растут не медленнее, чем g(n) с точностью до постоянного множителя:
F(n)
cg(n)

c > 0, n0 >0 :
0 c * g(n) f(n)
Например, запись (n*Ln(n)) обозначает класс функций, которые растут не медленнее, чем g(n) = n*Ln(n), в этот класс попадают все полиномы со степенью большей единицы, равно как и все степенные функции с основанием большим единицы.
Асимптотическое обозначение О восходит к учебнику Бахмана по теории простых чисел (Bachman, 1892), обозначения , введены Д. Кнутом- (Donald Knuth) [6].
Отметим, что не всегда для пары функций справедливо одно из асимптотических соотношений, например для f(n)=n1+sin(n) и g(n)=n не выполняется ни одно из асимптотических соотношений.
В асимптотическом анализе алгоритмов разработаны специальные методы получения асимптотических оценок, особенно для класса рекурсивных алгоритмов. Очевидно, что оценка является более прдпочтительной, чем оценка О. Знание асимптотики поведения функции трудоемкости алгоритма - его сложности, дает возможность делать прогнозы по выбору более рационального с точки зрения трудоемкости алгоритма для больших размерностей исходных данных.

Приложенные файлы

  • docx 26
    Скряго
    Размер файла: 43 kB Загрузок: 0

Добавить комментарий