книги / Математическая логика и теория алгоритмов. Анализ алгоритмов

функции с учетом различных вариантов подсчета – как «чистого» времени без учета вызова вложенных функций и обращений к операционной системе, так и общего времени), concurrency (сбор информации о многопоточных приложениях), Memory Usage (сбор информацииоб использованиииосвобождениипамяти)ит.д.

Рассмотрим работу профилировщика Visual Studio 2017 на примере простой программы, вычисляющей N-е число Фибоначчи двумя способами: рекурсивно и итерационно.

Текст программы представлен ниже

class Program

{

static int fibRec(int n)

{

if (n <= 2) return 1;

return fibRec(n - 1) + fibRec(n - 2);

}

static int fibIter(int n)

{

int cur, prev; cur = prev = 1;

for (int i = 3; i <=n; i++)

{

int tmp = prev; prev = cur;

cur = tmp + prev;

}

return cur;

}

static void Main(string[] args)

{

Console.WriteLine(fibRec(40));

Console.WriteLine(fibIter(40));

Console.WriteLine(fibRec(44));

Console.WriteLine(fibIter(44));

}

}

171

Для запуска профилировщика выберем команду «Performance Profiler…» в меню «Analyze»:

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

Запустим профилировщик нажатием кнопки «Start». После окончания работы программы мы увидим результаты. В окне отображается совокупное и «чистое» время работы подпрограмм. Можно обратить внимание на то, что 97,56 % всего времени работала собственно функция «fibRec», содержащая рекурсивное вычисление N-го числа Фибоначчи:

172

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

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

173

СПИСОК ЛИТЕРАТУРЫ

1.Аляев Ю.А., Тюрин С.Ф. Дискретная математика и математическая логика. – М.: Финансы и статистика, 2006. – 357 с.

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

3.Канцедал С.А. Дискретная математика: учеб. пособие. – М.: ФОРУМ: ИНФРА–М, 2007. – 224 с. – (Профессиональное образование)

4.Тюрин С.Ф., Ланцов В.М. Дискретная математика & математическая логика. – Пермь: Изд-во Перм. нац. исслед. поли-

техн. ун-та, 2013. – 271 с.

5.Коршунов Ю.М. Математические основы кибернетики: учеб. пособие для вузов. – М.: Энергия, 1972. – 376 с.

6.Коршунов Ю.М. Математические основы кибернетики. – М.:Энергоатомиздат,1987.–496 с.

7.Кузнецов О.П., Адельсон-Вельский Г.М. Дискретная математика для инженера. – М.: Энергоатомиздат, 1988. – 450 с.

8.Кибер форум [Электронный ресурс]. – URL: http://www. cyberforum.ru/cpp-beginners/thread1625750.html (дата обращения: 20.07.2017).

9.Шрайнер П.А Основы программирования на языке Пролог: курс лекций: учеб. пособие. [Электронный ресурс]. – URL: http://www.stepanoff.info/lisp/materials/prolog.pdf (дата обращения: 13.04.2019).

10.Залогова Л.А. Формальное описание механизма логического вывода в Прологе [Электронный ресурс]. – URL: https://doc- player.ru/31284484-Formalnoe-opisanie-mehanizma-logicheskogo-vyvo- da-v-prologe.html (датаобращения:13.04.2019).

11.Тюрин С.Ф. Вычислительная техника и информационные технологии. Руководство к лабораторным работам в системе

Proteus 7.2. – Пермь: Изд-во Перм. гос. техн. ун-та, 2010. – 135 с.

174

12.Дизассемблер [Электронный ресурс]. – URL: http: //www.heaventools.ru/pe-explorer-disassembler.htm (дата обращения: 08.08.2017).

13.Тюрин С.Ф., Гончаровский О.В., Громов О.А. Вычислительная техника и информационные технологии. Аппаратные средства вычислительной техники: конспект лекций. – Пермь: Изд-во Перм. гос. техн. ун-та, 2011. – 324 с.

14.Mbed [Электронный ресурс]. – URL: https: //www.mbed. com/en/ (дата обращения: 07.06.2019).

15.Гончаровский О.В. Прототипирование: метод. пособие. – Пермь:Изд-воПерм.нац.исслед.политехн.ун-та,2019.–120с.

16.Дискретная математика: конечные автоматы, рекурсивные функции: метод. рекомендации / сост. В.В. Морозенко. – Пермь: Изд-во Перм. нац. исслед. политехн. ун-та, 2005. – 72 с.

17.Анализ сложности алгоритмов: метод. пособие / сост. М.В.Кавалеров.–Пермь:Изд-воПерм.гос.техн.ун-та,2008.– 16 с.

18.ГОСТ 28195-89. Оценка качества программных средств. Общиеположения.–М.:Изд-во стандартов,2001.–31 с.

19.ГОСТ 28806-90. Качество программных средств. Терми- ныиопределения.–М.:Изд-востандартов,2001.–8с

20.Алябьева В.Г. Математическая логика. – Пермь, 2017. –

С.19–21, 110.

21.Лавров И.А. Математическая логика: учеб. пособие для вузов / под ред. Л.Л. Максимовой. – М.: Академия, 2006. –

С. 230.

22.Лавров И.А., Максимова Л.Л. Задачи по теории множеств, математической логике и теории алгоритмов. – М.: Физ-

матлит, 2001. – С. 248–249.

23.Судоплатов С.В., Овчинникова Е.В. Математическая логика и теория алгоритмов: учебник. – М.: ИНФРА-М4; Новосибирск: Изд-во НГТУ, 2008. – 224 с.

175