Понятие алгоритма и меры его сложности. Временная и емкостная сложность алгоритмов

Заключение

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

Разработанные в 1930-х годах разнообразные формальные модели алгоритмов (Пост, Тьюринг, Черч), равно как и предложенные в 1950-х годах модели Колмогорова и Маркова, оказались эквивалентными в том смысле, что любой класс проблем, разрешимых в одной модели, разрешимы и в другой.
В настоящее время полученные на основе теории алгоритмов практические рекомендации получают всё большее распространение в области проектирования и разработки программных систем.
Одна из задач, которая обычно ставится при разработке алгоритмов и программ - минимизация требуемых программой ресурсов. Особенно это касается системного программного обеспечения: программ операционной системы, трансляторов, систем управления базами данных и знаний и т. д., т.е. программ, имеющих большое количество пользователей и испытывающих как товар, большую конкуренцию на рынке программных средств.
Теория сложности алгоритмов предлагает достаточные эффективные методы решения поставленной проблемы. Точное решение возможно в подавляющем большинстве практически важных ситуаций.
Однако по-прежнему открыты вопросы, связанные со сводимостью алгоритмов друг к другу и остается нерешенной известная проблема P=NP.
алгоритм сложность оптимизация

Список использованной литературы

1. Ахо А., Хопкрофт Дж., Ульман Дж. Структуры данных и алгоритмы: Пер. с англ.: - М.: Издательский дом «Вильямс», 2001 г. -384 с., ил.

2. Вирт Н. Алгоритмы и структуры данных: Пер. с англ. - 2-ое изд., испр. - СПб.: Невский диалект, 2001 г. - 352 с., ил.
. Карпов Ю.Г. Теория автоматов - СПб.: Питер, 2002 г. - 224с., ил.
. Кнут Д. Искусство программирования. Тома 1, 2, 3. 3-е изд. Пер. с англ. : Уч. пос. - М.: Изд. дом "Вильямс", 2001 г.
. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. - М.: МЦНМО, 2001 г. - 960 с., 263 ил.
. Макконнел Дж. Анализ алгоритмов. Вводный курс. - М.: Техносфера, 2002 г. -304 с.
. Новиков Ф. А. Дискретная математика для программистов. - СПб.: Питер, 2001 г. - 304 с., ил.
. Романовский И.В. Дискретный анализ. Учебное пособие для студентов, специализирующихся по прикладной математике. - Издание 2-ое, исправленное. - СПб.; Невский диалект, 2000 г. - 240 с., ил.
. Успенский В.А. Машина Поста. - М.: Наука, 1999 г. - 96 с.