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

  • 01 февр. 2010 г.
  • 3940 Слова
Федеральное агентство по образованию Российской Федерации
Государственное образовательное учреждение
высшего профессионального образования «Борисоглебский государственный педагогический институт»

Кафедра прикладной математики и информатики

СЛОЖНОСТЬ АЛГОРИТМОВКурсовая работа
по информатике
Выполнил: студент IV курса 3 группы физико-математического факультета специальность «Информатика с дополнительной специальностью математика»
Чернецов М.Г.Руководитель: к.п.н.,
доцент кафедры прикладной математики и информатики
Лободина Л.В.

Борисоглебск 2009 г.

Содержание
Введение……………………………………………………………………..- 3 -
Анализ алгоритма
1. Основные требования калгоритмам………………………………………………………………-6-
2. Основы оценок сложности алгоритмов………………………...- 12 -
3. Оценка программ…………………………………………………………….….-17-
4. О-Сложность алгоритмов…………………………………………- 20 -
5. Классы сложности…………………………………………………- 27 -
Заключение………………………………………………………………...- 28 -
Список литературы……………………………………………………….- 29 -

Введение

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

Слово алгоритм содержит в своем составе преобразованноегеографическое название Хорезм. Термин “алгоритм” обязан своим происхождением великому ученому средневекового Востока - Муххамад ибн Муса ал-Хорезми ( Магомет, сын Моисея, из Хорезма ). Он жил приблизительно с 783 по 850 гг., и в 1983 году отмечалось 1200 летие со дня его рождения в городе Ургенче – областном центре современной Хорезмской области Узбекистана. В латинских переводах с арабского арифметическоготрактата ал-Хорезми его имя транскрибировалось как algorismi. Откуда и пошло слово “алгоритм” – сначала для обозначения алгоритмов цифровых вычислений десятичной позиционной арифметики, а затем для обозначения произвольных процессов, в которых искомые величины решаемых задач находятся последовательно из исходных данных по определенным правилам и инструкциям.

Вплоть до 30-х годов нашего столетия понятиеалгоритма оставалось интуитивно понятным, имевшем скорее методологическое, а не математическое значение. Так, к началу ХХ в. много ярких примеров дала алгебра и теория чисел. Среди них упомянем алгоритм Евклида нахождения наибольшего общего делителя двух натуральных чисел или двух целочисленных многочленов, алгоритм Гаусса решения системы линейных уравнений над полем, алгоритм нахождениярациональных корней многочленов одного переменного с рациональными коэффициентами, алгоритм Штурма определения числа действительных корней многочлена с действительными коэффициентами на некотором отрезке действительных чисел, алгоритм разложения многочлена одного переменного над конечным полем на неприводимые множители. Указанные алгоритмические проблемы решены путем указания конкретных разрешающих процедур. Дляполучения результатов такого типа достаточно интуитивного понятия алгоритма. Однако, в начале ХХ в. были сформулированы алгоритмические проблемы, положительное решение которых представлялось маловероятным. Решение таких проблем потребовало привлечения новых логических средств. Ведь одно дело доказать существование...
tracking img