Различные подходы к разработке алгоритмов.

Существует несколько подходов к проекти­рованию внутренней структуры и логики обработки данных (алгоритмов). Проектирование алгоритмов и программ — наиболее ответственный этап жизненного цикла программных продуктов, определяющий, насколько создаваемая программа соответствует спецификациям и требованиям со стороны конечных пользователей.

Проектирование алгоритмов и программ может основываться на различных подходах, среди которых наиболее распространены:

• структурное проектирование программных продуктов;

• информационное моделирование предметной области и связанных с ней приложений;

• объектно-ориентированное проектирование программных продуктов.

Типичными методами структурного проектирования являются:

• нисходящее проектирование, кодирование и тестирование программ;

• модульное программирование;

• структурное проектирование (программирование) и др.

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

Первоначально строятся информационные модели различных уровней представления:

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

• даталогические модели, ориентированные на среду хранения и обработки данных.

Даталогические модели имеют логический и физический уровни представления. Физи­ческий уровень соответствует организации хранения данных в памяти компьютера.

Логичес­кий уровень данных применительно к СУБД реализован в виде:

• концептуальной модели базы данных — интегрированные структуры данных под уп­равлением СУБД;

• внешних моделей данных — подмножество структур данных для реализации прило­жений.

Объектно-ориентированный подход к проектированию программных продуктов осно­ван на:

• выделении классов объектов;

• установлении характерных свойств объектов и методов их обработки;

• создании иерархии классов, наследовании свойств объектов и методов их обработки.

Объектный подход при разработке алгоритмов и программ предполагает:

• объектно-ориентированный анализ предметной области;

• объектно-ориентированное проектирование.

Объектно-ориентированный анализ — анализ предметной области и вы­деление объектов, определение свойств и методов обработки объектов, ус­тановление их взаимосвязей.

Объектно-ориентированное проектирование соединяет процесс объект­ной декомпозиции и представления с использованием моделей данных про­ектируемой системы на логическом и физическом уровнях, в статике и динамике.

Для проектирования программных продуктов разработаны объектно-ориентированные технологии, которые включают в себя специализированные языки программирования и ин­струментальные средства разработки пользовательского интерфейса

Известно несколько подходов к формализации понятия «алгоритм»:

• теория конечных и бесконечных автоматов;

• теория вычислимых (рекурсивных) функций;

• лямбда-исчисление Черча.

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

(Пример – машина Тьюринга, машина Поста)

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

Рассматриваются принципы оценки сложности алгоритмов в зависимости от размера задачи.

Временной сложностью алгоритма T(x) называется число его шагов, необходимых для решения данной задачи размера x в худшем случае (сложность в худшем). Пространственная сложность S(x) - это число единиц памяти, необходимых для решения задачи размера n в худшем случае.  Введем понятие верхнего и нижнего порядка функции относительно другой функции. Рассмотрим арифметические функции. Идет счет на шаги вычислительного процесса и единицы времени и пространства.  Определение Назовем арифметическую функцию f(x) функцией одного верхнего порядка с функцией g(x) и пишем f(x) = O(g(x)), если существует такое натуральное число c > 0, что, в конце концов (т. е. начиная с некоторого N) функция ||f(x)|| c |g(x)|. Функция сложности заведомо неотрицательная. Значит f(x)  cg(x). Пример: ln n = O(n); при n > 0 ln n < n. Можно записать 2n + 3 = O(n²). Решим уравнение, т. е. неравенство 2n + 3  n² . Решим подбором: 

n	2n+3	n2
0	3	0
1	5	1
2	7	4
3	9	9

Таким образом, n² обгонит любую линейную функцию.  Определение Назовем арифметическую функцию f(x) функцией одного нижнего порядка с функцией g(x) и пишем f(x) = (g(x)), если существует такое c > 0, что |f(x)|  c|g(x)|, f(x)  cg(x). Например: e^x = (x + 2). e^x - рано или поздно станет больше любого полинома. При малых размерах экспоненциальный алгоритм лучше полиномиального алгоритма; f(x) = o(g(x)).  Определение: f(x) одного порядка с функцией g(x), если она одного верхнего и одного нижнего порядка с функцией g(x), если она одного верхнего и одного нижнего порядка: = f(x) = o(g(x)) & f(x) = (g(x)). ^ Пример: x 10x + 2. Определение. Функция одного верхнего порядка с полиномиальными функциями называется полиномиальной функцией. Это не только все полиномы, но и некоторые трансцендентные функции. Все остальные функции есть экспоненциальные в широком смысле этого слова. Но в строгом смысле слова экспоненциальными называются функции одного нижнего порядка с экспонентой. Тогда функции между экспоненциальными и полиномиальными называются субэкспоненциальными функциями. Обычно их не рассматривают! Экспоненциальные функции выделяются по скорости еще на несколько классов. Полиномиальные и экспоненциальные алгоритмы. В конечном счете, функции пространственной и временной сложности должны определятся для конкретных машин (в операциях). Но теория сложности алгоритмов определяет общие типы алгоритмов по сложности: 1) полиномиальные алгоритмы; 2) экспоненциальные алгоритмы. Алгоритм, обе функции сложности которого полиномиальные, называется полиномиальным алгоритмом. Такой алгоритм считается хорошим, быстрым (практика). Алгоритм, у которого хотя бы одна из двух функций сложности экспоненциальная называется экспоненциальным алгоритмом. Такой алгоритм считается плохим, медленным. (При больших размерах задач, т. к. при малых может оказаться наоборот!).  Трудноразрешимые задачи. Задача, решаемая полиномиальным алгоритмом, называется легкоразрешимой задачей. Задача, которую нельзя решить полиномиальным алгоритмом называется трудноразрешимой. В число трудных задач входят алгоритмически неразрешимые задачи. Неразрешимость есть крайний случай экспоненциальности.  Для наглядности рассмотрим таблицу возможностей алгоритмов. Объем вычислений.

тип алгоритма Размер задачи	Полиномиальный	Экспоненциальный
малый	малый	малый
большой	большой	сверхбольшой
сверхбольшой	сверхбольшой	сверхбольшой