Математическая постановка задачи

 

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

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

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

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

Рис.6.1. Состав задачи для постановки единичного структурно-функционального элемента задачи

В общем виде постановка задачи состоит из четырех принципиально важных компонентов:

1) организационной части ее использования и описания;

2) свода применяемых математических моделей;

3) описания вычислительных алгоритмов;

4) концепции построения информационной модели системы.

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

Математическая модель и разрабатываемые на ее основе алгоритмы должны удовлетворять трем требованиям: определенности (однозначности), инвариантности по отношению к различным альтернативным ситуациям в задаче и результативности (возможности ее решения за конечное число шагов). Результатом алгоритмизации является логически построенная и отлаженная блок-схема.

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

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

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

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

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

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

План постановки задачи

1. Организационно-экономическая сущность задачи:

- наименование задачи;

- место решения;

- цель решения;

- назначение (для каких объектов, подразделений, пользователей предназначена);

- периодичность решения и требования к срокам решения;

- источники и способы получения данных;

- потребители результатной информации и способы ее отправки;

- информационная связь с другими задачами.

2. Описание исходной (входной) информации:

- перечень исходной информации;

- формы представления (документ) по каждой позиции перечня; примеры заполнения документов;

- количество формируемых документов (информации) в единицу времени, количество строк в документе (массиве);

- описание структурных единиц информации (каждого элемента данных, реквизита);

- точное и полное наименование каждого реквизита документа, идентификатор, максимальная разрядность в знаках;

- способы контроля исходных данных;

- контроль разрядности реквизита;

- контроль интервала значений реквизита;

- контроль соответствия списку значений;

- балансовый или расчетный метод контроля количественных значений реквизитов;

- метод контроля с помощью контрольных сумм и любые другие возможные способы контроля.

3. Описание результатной (выходной) информации:

- перечень результатной информации;

- формы представления (печатная сводка, машинный носитель и его макет и т.д.);

- периодичность и сроки представления;

- количество формируемых документов (информации) в единицу времени, количество строк в документе (массиве);

- перечень пользователей результатной информации (подразделение и персонал);

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

- способы контроля результатной информации;

- контроль разрядности;

- контроль интервала значений реквизита;

- контроль соответствия списку значений;

- балансовый или расчетный метод контроля отдельных показателей;

- метод контроля с помощью контрольных сумм и любые другие возможные способы контроля.

4. Описание алгоритма решения задачи (последовательности действий и логики решения задачи):

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

- описание связей между частями, операциями, формулами алгоритма;

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

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

5. Описание используемой условно-постоянной информации:

- перечень условно-постоянной информации (классификаторов, справочников, таблиц, списков с указанием их полных наименований);

- формы представления;

- описание структурных единиц информации (по аналогии с исходными записями);

- способы взаимодействия с переменной информацией.

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

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

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

 

Понятие алгоритма

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

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

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

Алгоритм должен обладать следующими основными свойствами, раскрывающими его определение.

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

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

3. Результативность (или конечность). Это свойство состоит в том, что алгоритм должен приводить к решению задачи за конечное число шагов.

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

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

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

 

Язык схем

 

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

Несмотря на все многообразие решаемых на ЭВМ задач, можно выделить несколько «типичных» действий (этапов), которые в различной последовательности выполняются при решении задач:

1. Присваивание. (Заметим, что присваивание является основной операцией, при помощи которой осуществляется обработка данных.)

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

3. Ввод данных и вывод результата.

4. Начало и конец вычислительного процесса.

Конкретные операции указаны внутри фигур в качестве примеров, Рассмотрим выполнение этих действий, а также функции других элементов схем, приведенных на рис.6.1.

Присваивание. При выполнении операции присваивания переменной присваивается значение (переменная - некоторая величина, которая может изменяться, принимая в процессе этого изменения различные значения). Переменная обозначается при помощи имени. Именами обозначаются также различные функции (например, SIN). Функции имеют, в языках программирования, закрепленные за ними имена. Как Вы уже знаете, имя переменной обозначает символический адрес той ячейки памяти, в которой записано числовое значение соответствующей переменной или функции (после ее

 

вычисления). Следовательно, термины "переменная" или "функция" только условно соответствуют общепринятым математическим понятиям. Числа, используемые, например, в операторах присваивания для задания значений переменных, называются константами. Константы обозначают сами числа, а не фактические адреса ячеек памяти.

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

В операторах присваивания справа от знака “=“ часто используются арифметические выражения.

Арифметическим выражением называется математическая запись, состоящая из констант, переменных, стандартных и нестандартных функций, объединённых знаками арифметических операций:

“+ “ - сложение; “ \ “ - деление нацело;

“ - “ - вычитание; “ ^ “ - возведение в степень;

“ / “- деление; “ * “ - умножение;

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

 

Примеры операторов присваивания

Оператор присваивания	Действие оператора
К=1	В ячейку памяти с символическим адресом К помещается 1. (переменной К присваивается значение 1)
L=K	В ячейку памяти с символическим адресом L пересылается содержимое ячейки с символическим адресом К (переменной L присваивается значение К). При этом К не изменяется.
К=К+1	К содержимому ячейки с символическим адресом К прибавляется 1, результат помещается в ту же ячейку К. При этом старое значение К пропадает (стирается).
Y=SIN(X)	Вычисляется sin угла (выраженного в радианах), величина которого находится в ячейке Х, и результат помещается в ячейку Y.
X=SIN(X)	Правая часть вычисляется аналогично. Значение функции записывается в ту же ячейку, в которой раньше находилось значение угла. Перед присваиванием старое значение пропадает (стирается).

Замечания:

1. Перед выполнением присваивания старое значение стирается.

2. При пересылке значение переменной копируется. Значение копируемой переменной не изменяется.

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

4. Если переменной не присвоено значение, то ее значение не определено.

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

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

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

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

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

Комментарии можно записывать около любого блока.

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

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

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