Содержание
Оглавление
1 Общие положения о вычислительной сложности 3
2. Проблемы сокращения вычислительной сложности в прикладных областях 6
3 Методы сокращения вычислительной сложности 8
4. Примеры способов сокращения вычислительной сложности 11
4.1 Алгоритм бинарного возведения в степень. 11
4.2 Алгоритм поиска в отсортированном массиве 13
4.3 Задача одномерного динамического программирования 16
5 Выводы 20
Список использованных источников 21
Выдержка из текста
Понятие вычислительной сложности в настоящее время очень актуально в связи с тем, что происходит лавинообразное развитие средств вычислительной техники. Компьютеры становятся более мощными, способными одновременно выполнять десятки и сотни операций параллельно. Активно используются мультипроцессорные системы. Компьютеры все больше и больше проникают в повседневную жизнь каждого человека. Мир уже не может обойтись без электронной почты, электронных платежных систем, свободного доступа к глобальной сети и т.д. Растет сложность задач управления во всех видах деятельности человека. Большими темпами растут объемы информации, необходимые для обработки и восприятия и т.д. Все это напрямую связано со сложностью вычислений, поскольку сложность пользовательских задач и сложность вычислений находятся в прямой зависимости.
Для оценки вычислительных алгоримов используют понятие вычислительной сложности. При этом оценивание вычислительной сложности напрямую связывают с количеством времени, потраченным для решения задачи по заданному алгориму. Понятно, что чем больше размер исходных данных, обрабатываемых в процессе вычисления, тем выше временная сложность. Поведение временной сложности в пределе при увеличении размера задачи называется ассимптотической временной сложностью»
Список использованной литературы
Список использованных источников
1. А. Ахо, Дж. Ульман, Дж. Хопкрофт — Построение и анализ вычислительных алгоритмов. Издательство «Мир», 1979. – 536 с.
2. Вычислительная сложность некоторых задач математической логики тема диссертации и автореферата по ВАК 01.01.06, кандидат физико-математических наук Дудаков С.М.
3. Крейнделин В.Б., Шлома А.М. Быстрые алгоритмы обработки радиосигналов и их вычислительная сложность. Учебное пособие. М.:- 2001. – 62 с.
4. Перепелица В.А., Тебуева Ф.Б. Дискретная оптимизация и моделирование в условиях неопределенности данных, Издательство "АкадемияЕстествознания", 2007 год . – 151 С.
5. Лавров С.С. Программирование. Математические основы, средства, теория. Издательство БХВ-Петербург. 2001 – 314 С.
6. Б.Шнайер Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си. Издательство: Триумф. 2002 – 152 с.