Очень важные замечания

Задача и ее решение.

Решение задач предполагает два этапа: 1) постановка задачи, 2) решение задачи.

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

В математике известны два типа задач:

1) задачи на порождение (вычисление, нахождение, построение);

2) задачи на распознавание (доказательство).

Обычно задачи на порождение начинаются словами: «Найти (вычислить, построить)…», а задачи на распознавание: «Доказать, что объект принадлежит, имеет свойство…». Необходимо заметить, что еще на этапе становления математики, как формальной науки, эти два типа задач были четко выделены. Например, в «Началах» Евклида задача порождения называлась «проблема», а задача распознавания – «теорема».

Решение задачи того и другого типа – построение соответствующей системы функций на модели. В случае задачи порождения, функция порождает элементы отношений в ММ. В случае задачи распознавания, функция является предикатом, доказывающим «истинность/ложность» принадлежности заданного объекта заданному отношению в ММ.

Например, проблема «Построить равнобедренный треугольник», требует формулировки:

1) свойств равнобедренного треугольника (геометрических отношений;

2) процедуры в виде применения последовательности правил (алгоритма) построения чертежа геометрического объекта при помощи процессоров (циркуля и линейки).

Известные свойства класса равнобедренных треугольников, выделяющих их из множества всех треугольников, суть математическая модель ММ = {Т, ТР Ì Т}, где Т – множество всех треугольников, а ТР – множество равнобедренных треугольников Порождающая функция имеет входными данными (аргументами) точки и прямые, заданные на плоскости, а выходными данными – треугольники. Правила «вычисления» функции формируются в виде «команд» процессору, состоящего только из циркуля и линейки.

1. Реальные (практические) задачи представляют собой комбинацию порождающих и распознающих процедур.

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

3. Множества и отношения, составляющие ММ, могут кодироваться весьма экзотическим способом. В дальнейшем, ММ совместно со способом кодирования будем называть структурой данных. Понятно, что для одной и той же ММ могут быть выбраны различные способы кодирования (различные структуры данных) и поэтому различные алгоритмы (функции решающие задачу), и, соответственно, различные программы, реализующие алгоритм. Впервые четко такой подход к решению задач сформулировал Вирт в известной книге «Структуры данных + алгоритм = программа».

В принципе иногда можно опустить этап формального определения структур данных и формализовать (кодировать) саму функцию, определяющую алгоритм. Известно стандартное кодирование функций, вычислимых алгоритмом, которое предложено Гёделем. Способ кодирования основан на приведении последовательности формул, описывающих решение задачи, к функциям, определенным на множестве натуральных чисел. Процедура кодирования называется гёделизацией. Вообще говоря, языки процедурного программирования (Fortran, Algol, Pascal, C и т.д.) по сути дела задают способ кодирования системы функций, решающих задачу.

В дальнейшем всегда, рассматривая цепочку:

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