Анализ постановки задачи и ее предметной области
Основы алгоритмизации
ЭТАПЫ РЕШЕНИЯ ЗАДАЧ НА ЭВМ
Рассмотрим обобщенный процесс решения проблемы на основе
системного подхода как последовательность, состоящую из трех этапов,
приведенных ниже:
А. Анализ постановки задачи и ее предметной области:
1) понимание постановки и требований исходной задачи, определение предметной области, для которой поставлена задача;
2) анализ предметной области; выявление данных, которые фиксируют входную и выходную информацию (определение их структуры и свойств);
3) определение отношений между данными, задание условий и ограничений, накладываемых на эти отношения.
Б. Формальное моделирование решения задачи:
1) формирование основной идеи;
2) выбор и применение формальной системы для описания метода решения задачи;
3) построение алгоритмов, реализующих выбранный метод;
4) выбор оптимального алгоритма для заданных ранее условий и ограничений.
В. Практическое решение задачи:
1) определение технологий, средств и исполнителя решения задачи;
2) реализация оптимального алгоритма средствами и технологиями выбранного исполнителя решения задачи;
3) анализ решения и полученных результатов.
Анализ постановки задачи и ее предметной области
При решении любой задачи важным является первый этап, связанный с анализом и пониманием постановки задачи. На этапе анализа необходимо детализировать постановку задачи. Основные вопросы, на которые требуется ответить, можно сформулировать следующим образом:
Какие данные являются исходными?
Какие данные являются результирующими?
Какие отношения между исходными данными и требуемым результатом?
Являются ли исходные данные достаточными?
К какому виду следует отнести исходные данные?
К какому типу следует отнести исходные и результирующие данные?
На этом этапе уточняется постановка задачи, после чего выявляются
отдельные явления, объекты, процессы, их связи и зависимости, то есть создается структурная модель предметной области.
Модель– это упрощенное представление о реальном объекте, процессе или явлении. На этапе анализа постановки задачи определяются такие понятия,
как исходные и результирующие данные, абстрактно представляющие
информацию о предметной области решаемой задачи в виде значений.
Исходные данные должны быть полными, т. е. содержать данные, необходимые и достаточные для решения задачи. Если данные неполные, необходимо приложить дополнительные усилия для сбора дополнительных сведений; эта ситуация может также возникнуть на последующих этапах при выборе метода решения. Данные могут быть определены на основе свойств данных, которые задают их вид и тип.
Различают исходные данные трех видов: постоянные, условнопостоянные и переменные.
Постоянные исходные данные– это данные, которые сохраняют свои значения в процессе решения задачи (математические константы, координаты неподвижных объектов) и не зависят от внешних факторов.
Условно-постоянные данные– это данные, которые могут иногда изменять свои значения; причем эти изменения не зависят от процесса решения задачи, а определяются внешними факторами (величина подоходного налога, курс валют, количество дней в году).
Переменные данные– это данные, которые изменяют свои значения в процессе решения задачи.
В дальнейшем необходимо как для исходных, так и для результирующих данных выбрать определенный тип данных.
Тип данныхопределяет множество значений и множество допустимых операций к ним.
На этом этапе важно не только классифицировать данные по отношению к
процессу решения, но определить их наименование, тип, структуру и ограничения, накладываемые на значения исходя из постановки задачи.
Желательно также определить допустимые и недопустимые операции по
отношению к различным типам исходных данных.
Данное относят к простому типу, если в любой момент времени оно определяет одно и только одно значение.
На рис. 1 представлена классификация типов данных по структурному признаку.
Например, требуется вычислить площадь поверхности некоторого тела. Очевидно, что для представления информации о вычисляемой площади поверхности некоторого тела достаточно использовать данное простого числового типа. Простые данные определяют такое отношение: одно имя – одно значение.
Структурированные данные отличаются от простых тем, что к ним применимо другое отношение: одно имя – много значений. Если все элементы, входящие в такую структуру, однотипны, то такая структура называется однородной, в противном случае – неоднородной.
Классическим примером однородной структуры является некоторая последовательность однотипных данных, заданная в виде массива значений, таких как, например (2, 51, 3, 7, 88).
Массивхарактеризуется фиксированным количеством входящих в него значений, эти значения упорядочены по номерам следования.
Номер элементав массиве является средством адресации, доступа к конкретному элементу, например в вышеприведенном массиве чисел значение 51 имеет номер два, а значение 7 – номер четыре. Неоднородная структура в отличие от однородной содержит значения различных типов, относящихся к одному понятию или объекту, и, значит, такое структурированное данное несет в себе больше информации. Для представления неоднородных структур используют запись. Запись– это структура, предназначенная для представления данных преимущественно различного типа. Значения, составляющие запись, называются полями записи. По-другому запись можно представить как совокупность полей, каждое из которых имеет свое наименование. Имя поля является средством адресации, доступа к значению этого поля в записи.
Рассмотрим простой пример. Задача заключается в определении в некоторой стране города с максимальным количеством жителей. Данные, которые необходимо проанализировать, это нечисловые данные, содержащие информацию о названии города, и числовые данные, содержащие информацию о численности в этом городе. В качестве структуры, содержащей данные о названии города и количестве в нем жителей, следует выбрать неоднородную структуру – запись, пример которой изображен в таблице 1. Запись содержит два поля: Название
города и Количество жителей. В первой строке табл. 1 указаны названия полей, во второй строке – типы полей, в третьей строке значения полей, образующие запись.
В качестве структуры, содержащей информацию о множестве городов рассматриваемой страны, можно выбрать однородную структуру типа массив, состоящий из нескольких однотипных записей табл. 1. Определение отношений между данными, условиями и ограничениями, накладываемыми на значения данных, зависит от конкретной постановки задачи и требований пользователя.
В результате анализа постановки задачи создается структурная модель, в которой определены данные, их свойства через виды, типы, ограничения и возможные соотношения между ними.
Формальное решение задачи
После проведения анализа постановки задачи, выявления данных, их вида, типа и структуры можно приступить к построению, синтезуформальной модели решения задачи. Это наиболее важный этап в процессе решения задачи. На этом этапе детализируются отношения между исходными и результирующими данными, условиями и ограничениями, накладываемыми на значения данных, зависящими от конкретной постановки задачи и требований пользователя, а также генерируется идея, подход к решению задачи. Для выбора и описания метода решения необходимо выбрать некоторую формальную систему. Обычно, исходя из постановки задачи, можно сразу определить один или несколько видов моделей, подходящих для описания и моделирования решения вашей задачи: аналитические, геометрические, структурные, логические и др.
Наиболее распространенными и хорошо изученными являются математические модели. Например, в качестве математической модели звезды можно использовать систему уравнений, описывающую процессы, происходящие в недрах звезды. Математической моделью другого рода являются математические соотношения, позволяющие рассчитать оптимальный план работы предприятия. К основным достоинствам математических моделей относятся хорошо изученные и широко применяемые математические методы решения большого класса задач, что значительно облегчает формирование основной идеи и выбор методов
решения задачи. В дальнейшем в пособии рассматриваются только математические модели.
Приступая к разработке формальной модели решения задачи, следует попытаться решить задачу для конкретных входных данных, затем обобщить полученное решение на основе его анализа для любых значений входных данных.
К основным вопросам, на которые целесообразно обратить внимание на этапе формального решения задачи, следует отнести:
Что дано? Как можно обозначить исходные данные исходя из их типа, определенного на предыдущем этапе?
Что неизвестно? Как можно обозначить результирующие данные исходя из их типов?
Какие условия, ограничения можно определить для исходных и результирующих данных? Как их записать?
Какие соотношения между исходными данными и результатами можно записать еще? Как их записать?
Какая формальная модель больше всего подходит для решения этой задачи?
Известен ли метод решения для такой или родственной задачи? Если метод известен, как его записать в терминах введенных ранее обозначений исходных, результирующих данных и условий? Требуются ли промежуточные данные?
К какому типу их следует отнести?
Если метод решения задачи неизвестен, решаемую задачу можно разделить на несколько задач, более простых, известных для Вас. Введение искусственных, дополнительных переменных является другим способом поиска метода решения задачи. Попытка переформулировать постановку задачи может оказать действенную помощь в поиске подходящего метода решения задачи, также как и консультации, и обращение к информационным ресурсам. Иногда метод решения задачи является настолько простым и очевидным, что его и не осознают в качестве метода, а иногда метод решения представляет собой сложные
математические выводы и формулы, занимающие несколько страниц.
Пример 1. Постановка задачи. Требуется определить пригодность для проведения учебных занятий данной аудитории.
Решение.
Этап 1. Анализ постановки задачи и ее предметной области.
В результате анализа предметной области, выявляем, что эта предметная область связана с образовательным процессом. Постановка задачи может быть переформулирована следующим образом: определить, подходит ли некоторая
аудитория для проведения занятий группы учеников при некоторой норме площади для каждого ученика. Введем обозначения для входных и выходных данных. Исходные данные: А – ширина аудитории, B – ее длина, К – количество учеников в группе, N – допустимое минимальное количество квадратных метров для одного ученика (норма), M – количество парт в аудитории. В качестве выходных данных будут выступать сообщения: «Аудитория может быть использована для проведения учебных занятий» и «Аудитория не может быть использована для проведения учебных занятий».
Этап 2. Формальное решение.
Определим отношения между входными и выходными данными. Введем
дополнительные понятия: S – площадь аудитории, C – требуемая по нормам площадь для проведения занятий в группе из К учеников, D – требуемое количество парт для обучения группы из К учеников. Опишем соотношения между входными и выходными данными, используя математические зависимости. Математическая модель:
Задача построения алгоритмов, реализующих выбранные методы решения задачи, детализирует и визуализирует процесс ее решения.
Алгоритмизацияпозволяет определить последовательность преобразования исходных данных в результирующие и уже на этом этапе оценить эффективность решения, уточнить методы решения для различных потоков входных данных и выявить некоторые ошибки. Поэтому особенно важно уделить серьезное внимание алгоритмизации решения заданной задачи. Вопросы корректного построения алгоритмов являются наиболее значимыми для большого класса вычислительных задач со сложными структурами данных, со сложной логикой и большим объемом вычислительных операций, решаемых программными средствами ЭВМ. В этом случае алгоритмическое представление, алгоритмическая модель решения задачи, созданная на основе метода решения рассматривается как промежуточное звено между методом решения и его программной реализацией. В принципе, желательно понимать, что между методом решения задачи и реализующим алгоритмом существует отношение «один метод – множество алгоритмов», поэтому необходимо принимать решение
о выборе наиболее адекватного, оптимального алгоритма, удовлетворяющего заданным условиям и ограничениям.
Следует отметить, что алгоритмическое решение существует не для всех классов задач, к таким задачам относятся, например, задачи искусственного интеллекта.