Лекция: Модель – алгоритм - программа» - методологический принцип решения задач на компьютере.
Мы уже привыкли к тому, что все большее число задач, возникающих в нашей жизни, мы решаем, используя компьютер. Во-первых, это задачи, требующие громоздких вычислений. Во-вторых, это задачи, которые имеют несколько решений, среди которых необходимо выбрать одно решение, в некотором смысле лучшее. Кроме того, компьютер часто используется для хранения больших объемов информации, которая по мере необходимости извлекается из памяти компьютера по частям или целиком в виде, удобном для пользователя.
Но при решении всех этих задач компьютеру обязательно нужно сформулировать задачу во вполне определенном виде, а также указать последовательность действий, которые приведут к ее решению, причем эта последовательность действий также должна быть записана на специальном языке. Иначе говоря, для решения задачи на компьютере ее нужно специальным образом подготовить.
Методологический принцип решения задач на компьютере можно сформулировать как триаду «модель – алгоритм – программа». Любая практическая задача, как правило, формулируется вначале на естественном языке. Затем человек, пытающийся решить эту задачу, ищет закономерности, позволяющие получить результат, имея заданный набор исходных данных. Как правило, эти закономерности записываются в виде математических соотношений. Совокупность математических соотношений, описывающих данную задачу, называют ее математической моделью.
Поясним сказанное выше примером. Пусть необходимо решить такую задачу. В классе 32 мальчика и 24 девочки, а всего учащихся в классе 100. В какой системе счисления ведется счет и сколько мальчиков и девочек в классе в системе счисления с основанием 10?
1 этап – построение математической модели задачи. Обозначим через х основание неизвестной системы счисления. Тогда 3х+2 – число мальчиков в классе, 2х+4 – число девочек в классе, 1х2+0х+0 – число учеников в классе. В итоге получаем 3х+2+2х+4=х2или х2-5х-6=0. Итак, моделью нашей задачи является квадратное уравнение х2 – 5х – 6=0.
2 этап – построение алгоритма решения задачи. Алгоритмом решения данной задачи будет являться алгоритм решения квадратного уравнения по известной формуле, которая и будет определять алгоритм решения задачи, если только зафиксировать порядок действий.
Выполнив эту программу для исходных данных р=-5, q=-6, получим результат х1=6, х2=-1. Поскольку в нашем случае основание системы счисления не может быть отрицательным числом, то получили, что основанием системы счисления должно быть число 6. Значит в классе 3*6+2=20 девочек и 2*6+4=16 мальчиков, а всего в классе 62=36 учеников, что верно так как 20+16=36.
Разработка алгоритма по его математической модели.
Когда модель построена и есть уверенность в ее соответствии условию решаемой задачи, необходимо разработать алгоритм решения, пользуясь полученной моделью. Часто одной и той же модели могут соответствовать несколько различных алгоритмов. Например, пусть моделью некоторой задачи является система линейных алгебраических уравнений. Но решить эту систему можно различными методами. Тогда можно сказать, что каждый метод решения системы линейных уравнений определяет свой конкретный алгоритм, хотя модель одна и та же.
Следующий шаг – это преобразование алгоритма в программудля компьютера, т.е. необходимо представить алгоритм в виде последовательности операторов некоторого языка программирования. После этого исходная задача готова для решения на компьютере, необходимо лишь задать начальные данные.
Вернемся к примеру предыдущего пункта и выполним 3 этап – представление алгоритма в виде программы. Запишем алгоритм в виде программы на языке Паскаль.
Алгоритмически неразрешимые задачи.
Неправильно было бы думать, что для любой задачи существует алгоритм ее решения. Известна задача древнегреческой математики – задача о трисекции угла, т.е. о делении угла на три равные части с помощью циркуля и линейки. Неразрешимость этой задачи была доказана в 19 веке алгебраическими методами. В этом примере речь идет о задаче, для которой не существует алгоритма решения в рамках фиксированного набора допустимых действий, в данном случае – построения с помощью циркуля и неразмеченной линейки. Однако отсюда не следует, что эту задачу нельзя решить, применяя какие-либо другие средства. Те же древние греки находили для этого хитроумные способы.
Есть также множество проблем, о которых мы и сейчас не можем сказать, разрешимы они или нет, и если разрешимы, то каким образом. Так известна гипотеза о том, что любое четное число представимо в виде суммы двух простых чисел. Но утверждение это пока не доказано, и не ясно, удастся ли его когда-либо доказать или опровергнуть.
Из сказанного выше вытекает, что для некоторых задач существует несколько алгоритмов их решения, для некоторых задач таких алгоритмов вообще не существует, и, наконец, есть задачи, для которых мы не знаем, существуют или нет алгоритмы их решения.