Эффективность алгоритмов

Для обоснованного использования времени и памяти вычислительной машины необходим теоретический и эмпирический анализ эффективности.

На практике приходится довольствоваться приближенным решением задачи и мириться с элементами неопределенности в решении. Как правило, точно решаются только задачи с конечным числом входных и выходных данных, допускающих конечное представление. Можно выделить две причины, по которым ограничиваются приближенным решением: либо задачу невозможно решить точно, либо точное решение не нужно. Невозможность получить точное решение может объясняться тем, что:

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

- информация приближенная, которая может появиться в результате многих причин, в том числе ошибок ЭВМ, ошибок при передаче данных, ограниченной точности представления и обработки чисел, ограничений на точность измерений;

- ограничен класс допустимых алгоритмов.

Большинство реальных задач приходится решать, располагая лишь неполной или приближенной информацией. Численные процедуры используют арифметику конечной точности и основываются на теории аппроксимации. В принципе желательно описывать численные алгоритмы с той же строгостью, что и алгебраические. Понятие вычисления может относиться не только к числам. Первые символьные манипуляции были связаны с использованием шифров и тайнописи. Начиная с 1963 г распространяются программные системы для формульных преобразований. Другим примером символьных вычислений являются: работа с текстами, игры в шашки, шахматы, го. К этой же группе программ относятся программы для получения математических доказательств.

Алгебраические алгоритмы реализуются в программных системах, допускающих ввод и вывод информации в символьных обозначениях. Она отличаются простыми формальными описаниями, существованием доказательств правильности и асимптотических границ времени выполнения. Кроме того алгебраические объекты можно точно представить в памяти ЭВМ, поэтому алгебраические преобразования могут быть выполнены без потери точности и значимости. Точность при использовании алгебраического алгоритма часто оплачивается большим временем выполнения и необходимым объемом памяти, чем для его численного аналога.

Существует ряд важных причин для анализа алгоритмов. Одной из них является необходимость получения оценок (или границ) для объема памяти или времени работы, которое потребуется алгоритму для успешной обработки конкретных данных. Машинное время и память относительно дефецитные и дорогие ресурсы. Другая – желание иметь некий количественный критерий для сравнений двух алгоритмов, претендующих на решение одной и той же задачи. Еще одна причина - желание иметь механизм для выявления наиболее эффективных алгоритмов. Иногда невозможно составить четкое мнение об относительной эффективности двух алгоритмов. Один может в среднем лучше работать, к примеру, на случайных входных данных, другой лучше работает на каких-то специальных данных. Важно также установить абсолютный критерий. Когда считать решение задачи оптимальным, т.е. когда наш алгоритм настолько хорош, что его невозможно (независимо от наших умственных способностей) значительно улучшить.

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

Ограничение финитности для практических целей является не-достаточно жестким: используемый алгоритм должен иметь не просто конечное, а предельно конечное, разумное число шагов. В реальных вычислениях главный вопрос относительно некоторой функции состоит не в том "вычислима ли данная функция", а скорее в том "вычислима ли она практически". Т.е. существует ли программа, вычисляющая функцию за время, которым мы располагаем? Можно измерять время, требуемое для вычисления каждого значения функции по конкретной программе, в предположении, что каждый шаг совершается за единицу времени. И мерой вычислительной сложности брать время вычисления.

Недостаточно доказать правильность алгоритма. Все мы можем сделать ошибки при доказательстве и при переводе правильного алгоритма в программу. Каждый может забыть некоторый частный случай задачи. Мельчайшие особенности операционной системы могут вызвать для некоторых входных данных такое действие части вашего алгоритма, о котором вы и не подозревали. Программа должна быть проверена для широкого спектра допустимых входных данных. Этот процесс может быть утомительным и сложным. Аналитический и экспериментальный анализ дополняют друг друга. Аналитический анализ может быть неточным, если сделаны слишком сильные упрощающие допущения. В этом случае могут быть получены только грубые оценки. Экспериментальные результаты, особенно когда используются случайно сгенерированные данные, могут оказаться слишком односторонними. Чтобы получить достоверные результаты, следует проводить как аналитическое, так и экспериментальное исследование там, где это возможно.

Дата добавления: 2014-01-06