1.Способы решения задач
 

Существуют четыре основных способа решения задач:

1)   применение формулы;
2)   использование рекурсий;
3)   использование алгоритма;
4)   метод перебора, метод проб и ошибок и др.

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

Пример 4.1.
Пусть требуется вычислить сумму n чисел натурального ряда: ∑i=1+2+...+n

Эту задачу можно решить первыми тремя способами. Известно, что эта сумма определяется по формуле S(n)=∑i =n(n+1)/2
При ее использовании сложность решения не зависит от n и равна 0(1).

Решение этой же задачи можно определить рекурсивно. S(n) = S(n - 1) + n, S(1) = 1 или по итеративному алгоритму с использованием цикла. Тогда сложность алгоритма равна О(n).

Аналогично можно вычислить и значения:
∑i²=n(n+1)(2n+1)/6; ∑i³= (1+2+...+n)² =(n(n+1)/2)²

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

Существует множество задач, которые принято называть задачами выбора.
Пример 1. Пусть известны попарные расстояния между n городами. Требуется найти кратчайший путь между некоторой парой городов.
Пример 2.Имеется n различных деталей и n станков. На каждом станке можно обрабатывать любую деталь, но время обработки одной и той же детали на различных станках может быть различным. Пусть заданы времена обработки каждой детали на каждом станке. Как разместить n деталей по n станкам так, чтобы суммарное время работы было минимальным?
Пример 3. Имеется n предметов, вес каждого из них известен. Можно ли разделить их на две равные по весу части?

Эти задачи — задачи выбора имеют следующие общие свойства:

1) конечность множества вариантов выбора (путей между городами, размещение деталей, распределение предметов между частями);
2) каждому варианту соответствует количественная характеристика (длина пути, суммарное время обработки деталей, вес предметов в каждой части);
3) требуется выбрать вариант, числовая характеристика которого удовлетворяет заданному условию, или определить существование такого варианта. Иногда нужен только один вариант или вариант с экстремальной характеристикой (оптимальный вариант), иногда — все варианты, а иногда — не сам вариант, а только его числовая характеристика.

Казалось бы, решить такие задачи просто — поочередно пересмотреть все варианты и выбрать требуемый, т.е. использовать алгоритм прямого перебора (переборный алгоритм). Однако такой подход приемлем только тогда, когда число вариантов небольшое. Применение ЭВМ позволяет методом перебора решать задачи выбора с большим числом вариантов, однако и при этом возможное число интересных для практики задач невелико. В то же время число таких задач увеличивается.

Для решения некоторых задач выбора разработаны точные алгоритмы, приводящие к получению результатов за приемлемое время. Во многих случаях, когда такие алгоритмы невозможно получить или они являются недопустимо сложными, применяют различные методы целенаправленного перебора вариантов, сокращающих их число. Это «жадные» (градиентные) алгоритмы, метод ветвей и границ, алгоритмы с возвратом, динамическое программирование и др. Для реше-ния задач поиска оптимального варианта часто используются эвристические алгоритмы.

Эвристический алгоритм обладает двумя свойствами:

1) он находит хорошие, хотя и не обязательно оптимальные решения;
2) его можно быстрее и проще реализовать, чем любой точный алгоритм, дающий оптимальное решение.