Формализация задачи

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

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

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

Итак, процесс зачисления происходит описанным ниже образом:

1. в приемную комиссию поступают сведения об абитуриенте, включающие данные о его оценках из аттестата о среднем образовании;

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

1. когда все вступительные экзамены сданы, список абитуриентов упорядочивается по мере убывания общей суммы оценок по сданным экзаменам с учетом среднего балла по аттестату;

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

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

Формализация выполнена. Ее результат – описание решения в виде последовательности шагов, входные и выходные данные.

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

семестр, х	1	2	3	4
число отчисленных, y	20	5	2	1

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

Эта задача относится к классу задач экстраполяции функций: определить значение функции y в точке x (x ∉ x₀, x_n), если известны (n+1) значений функции y в точках x₀, x₁ x₂, …, x_n.

Решим задачу двумя способами.

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

 

Как видно из рисунка, сформированная функциональная зависимость имеет вид:

y(x) = 20,777 x^-2,1513,

где y – число отчисленных студентов;

x – номер семестра.

Тогда для определения числа оставшихся студентов к пятому курсу (дипломному проектированию) может быть построена модель:

st = N – y (10),

где st – число оставшихся к дипломному проектированию студентов.

Формальная постановка задачи выполнена.

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

В соответствии с принятыми выше обозначениями имеем:

где y_i – число отчисленных студентов в i-м семестре;

p_i(10) – коэффициент Лагранжа, который рассчитывается по формуле:

и имеет значения из множества {p₁(10), p₂(10), p₃(10), p₄(10)}.

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

Программирование задачи

Технология программирования задач различается для операторных и функциональных языков программирования. Ограничимся рассмотрением вопроса для операторных языков. Тогда этот этап разбивается на два последовательных шага – разработку алгоритма и отладку программы.

Разработка алгоритма

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

Алгоритм обладает следующими свойствами (они следуют из определения):

1. определенность (детерминированность) – каждая команда (или предписание) понятна исполнителю (человеку или компьютеру) и исключает неоднозначность исполнения;

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

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

1. дискретность – пошаговый характер процесса получения результата, состоящий в последовательном выполнении конечного числа заданных алгоритмом действий.

Различают следующие простейшие виды алгоритмов:

1. линейный, когда предписания алгоритма выполняются в той последовательности, в которой они представлены в алгоритме;

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

1. циклический, когда предписания алгоритма выполняются многократно. В зависимости от характера повторений различают циклические алгоритмы с заданным и незаданным числом повторений (в этом случае такие алгоритмы называют итерационными).

Существуют следующие способы описания алгоритма: словесный, структурно-стилизованный, язык графических символов, операторный язык

Словесный способ

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

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