тема "Понятие сложности алгоритма" курс "Теория алгоритмов"
план-конспект урока по теме

Тивиков

При использовании алгоритмов для решения практических задач мы сталкиваемся с проблемой рационального выбора алгоритма решения задачи. Решение проблемы выбора связано с построением системы сравнительных оценок, которая в свою очередь существенно опирается на формальную модель алгоритма

Скачать:

ВложениеРазмер
Microsoft Office document icon ponyatie_slozhnosti_algoritmov.doc35.5 КБ

Предварительный просмотр:

Сравнительные оценки алгоритмов

При использовании алгоритмов для решения практических задач мы сталкиваемся с проблемой рационального выбора алгоритма решения задачи. Решение проблемы выбора связано с построением системы сравнительных оценок, которая в свою очередь существенно опирается на формальную модель алгоритма.

Будем рассматривать в дальнейшем, придерживаясь определений Поста, применимые к общей проблеме, правильные и финитные алгоритмы, т.е. алгоритмы, дающие 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:

Fa(N) = max {Fa (D)} – худший случай на DN

2. Fa(N) – лучший случай – наименьшее количество операций, совершаемых алгоритмом А для решения конкретных проблем размерностью N:

Fa(N) = min {Fa (D)} – лучший случай на DN

3. Fa(N) – средний случай – среднее количество операций, совершаемых алгоритмом А для решения конкретных проблем размерностью N:

Fa(N) = (1 / MDN)* {Fa (D)} – средний случай на DN


По теме: методические разработки, презентации и конспекты

Программа элективного курса «Сочинение-рассуждение как жанр и вид задания повышенной сложности на ЕГЭ по русскому языку»

Рекомендации написания сочинения- рассуждения в 11 классе, пошаговое объяснение....

Методическое пособие по выполнению практической работы по теме "Расчёт технологичности деталей средней сложности"

Методическое пособие разработано для студентов 3 курса специальности Технология машиностроения для изучения междисциплинарного курса "Технологические процессы изготовления деталей машин" по теме "Расч...

Программа элективного курса «Сочинение-рассуждение как жанр и вид задания повышенной сложности на ЕГЭ по русскому языку»

Программа элективного курса «Сочинение-рассуждение как жанр и вид задания повышенной сложности на ЕГЭ по русскому языку»   Программа включает: - пояснительную записку;- содержание прогр...

Презентация по теме: "Алгоритмы. Свойства алгоритмов."

Презентация по теме: "Алгоритмы. Свойства алгоритмов."...

Понятие алгоритма. Свойства алгоритма. Способы записи алгоритма. Понятие сложности алгоритма

Конспект темы по информатике для 1 курсов. Понятие алгоритма. Свойства алгоритма. Способы записи алгоритма. Понятие сложности алгоритмаСамостоятельная работа после изучения темы...