Информатика

       

Решение сложных задач


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

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

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

При таком подходе доказательство правильности

сложных алго­ритмов и программ подразделяется на доказательство ряда лемм о правильности вспомогательных алгоритмов и подпрограмм и доказательство правильности программ в целом.

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

Первая задача: упорядочение массивов данных. Пример, для чисел 3, 7, 9, 1, 4 упорядоченная последовательность имеет вид: 1, 3, 4, 7, 9.                                                 

Существует несколько способов и методов упорядочения масси­вов и последовательностей. Простейший из них называется методом «пузырька».

Метод «пузырька» состоит в нахождении в массиве наименьшего числа и перестановке его на первое место. Это как бы «пузырек», поднимающийся к началу массива. Затем в остатке массива нахо­дится наименьшее число, которое перемещается на второе место, и так далее - до исчерпания всего массива.

Для рассматриваемых чисел метод «пузырька» дает следующие перестановки:


исходные числа:                    3, 7,   9, 1, 4.
перестановка1:                       1, 7,   9,  3, 4.


перестановка2:                       1, 3,   9,  7, 4.
перестановка3:                       1, 3,   4,  7, 9.     ¬ упорядочено.
Приведем точную математическую постановку задачи.
Постановка задачи
Упорядочение последовательности чисел.
Дано:
x1, х2, ..., хN - исходные числа.
Треб.: x1', x2', ..., хN' - упорядоченные числа.
Где:   х1' £
х2' £
... £ хN'.
При:   N > 0.
Упорядочение чисел по методу «пузырька» в общей форме имеет вид:
Способ «упорядочение чисел»
нач
от k=1 до N-1 цикл
хтп := xk
imn := k
от i=k+1 до N цикл
если xi < хтп то
хтп := xi
imn : = i
кесли
кцикл                                                    
            xmn = Min (хk, ..., хN)
xk' = хтп
ximn ' = xk
кцикл                                                          хk¢ = Min (хk, ..., хN)
кон                                                                  x1 < х2
< ... < хk¢
Приведенный алгоритм можно рассматривать как алгоритм, сло­женный из нескольких фрагментов - вспомогательных алгоритмов, решающих определенные подзадачи.
Первый фрагмент (внутренний цикл) решает подзадачу нахожде­ния минимального значения в подмассиве x[k:N]. Второй фрагмент решает подзадачу перемещения k-го минимального значения на k-e место в массиве.
Лемма 1. Для вспомогательного алгоритма
алг «поиск минимума»
нач
хтп
:= xk
imn := k
от i
= k + 1 до N цикл
если
xi < хтп то
хтп
:= xi
imn := i
кесли
кцикл                                                         { xmn = Min (хk, ..., х1) }
кон
конечным результатом вычислений будет значение
xmn = Min (хk, ..., хN).
Доказательство. Применим индуктивную схему рассуждений. Первое присваивание дает
xmnk =
xk.
Далее на первом шаге цикла при i = k + 1 будет получен минимум первых двух чисел:
                  xk+1 при xk+1 < xmnk,
xmnk+l =


      xmnk при xk+1
³ xmnk.
На втором шаге цикла будет получен минимум первых трех чисел:
xmnk+2
= min (xk+2, min (хk+1, хk)) = Min (хk+2,
хk+1, хk).
Теперь можно утверждать, что на третьем и последующих шагах цикла результатом будет минимальное значение среди чисел xk , ..., xi
хmni = Min (хk, ..., хi).
Данное утверждение доказывается с помощью математической индукции. На первых двух шагах при i = k + 1, k + 2 оно уже уста­новлено. Покажем, что оно будет выполняться на (i + 1)-м шаге. Действительно, на следующем шаге цикла результатом будет:
      xi+1
при хi+1 < xmni = min(xi+1, хmni)
хmni+1
=
                  хmni при хi+1 ³ хmni = min(xi+1, xmni)
= min (xi+1, Min (хk , ..., хi)) =  Min (хk, ..., хi, xi+1).
Что и требовалось показать. Следовательно, в силу принципа мате­матической индукции конечным результатом выполнения рассмат­риваемого цикла будет значение:
xmnN
= Min (xk, ...,
хN)
Что и требовалось доказать.
Лемма 2. Для вспомогательного алгоритма
алг «перестановки»
нач                                                      { xmn = Min (хk, ..., хN) }
xi¢mn= xk
кон
конечным результатом будет значение хk' = Min (хk, ..., хN).
Доказательство. В силу леммы 1 xmn = Min (xk, ..., хN). А так как в этом алгоритме хk' =
xmn, то в итоге получим
хk' = xmn = Min (хk, ..., хN).
Что и требовалось.
Утверждение. Конечным результатом выполнения алгоритма будет упорядоченная последовательность чисел х1', ..., хN', удовлет­воряющая условию х1' £ х2' £ ... £ хN'.
Доказательство проводится по индуктивной схеме рассуждений. Рассмотрим результаты выполнения основного цикла основного алгоритма:
алг «упорядочение чисел»
нач
от k = 1 до N - 1 цикл
xmn
:= хk
...............                                                         { xmn = Min (хk, ..., хi) }
х¢k
= xmnN
хmп¢
= хk 
кцикл                                                         { хk' = Min (хk, ..., хN) }
кон                                                                  { х1' £ х2' £ ... £ хk' }


На первом шаге при k = 1 первый элемент последовательности
х1' = Min (x1, х2, ..., хN),
На втором шаге второй элемент последовательности
x2' = Min (х2, ..., хN).
В силу свойств минимума последовательности чисел будем иметь
х1' = Min(x1, x2, ..., хN) = min (x1, Min (х2, ..., хN) £ (Min (х2, ..., хN) = x2'.
Таким образом, при k = 2 результатом станут значения х1' и x2', такие что
х1' £ x2'
На третьем шаге выполнения основного цикла результатом станет
х3 = Мin(х3, ..., хN).
Опять же в силу свойств минимума последовательности имеем
х2' = Min (х2, х3, ..., хN) = min (x2, Min (x3, ..., хN)) £ Min (x3, ..., хN) = x2'.
Таким образом, после третьего шага при k = 3 первые три значе­ния последовательности х1', x2', x3' будут удовлетворять условию
х1'£ x2'£ x3'
Из приведенных выкладок можно сделать индуктивное предположение, что на каждом очередном k-м шаге выполнения основного цикла первые k членов последовательности х1', x2', .... хk' будут удов­летворять условию
х1'£ x2'£  … £ xk'.
Данное предположение доказывается с помощью математической индукции. На начальных шагах при k == 2 и k = 3 оно уже показано. Покажем, что оно будет выполнено на (k + 1)-м шаге, если это усло­вие выполнено на k-м. шаге.
В силу Леммы 2 на k-м и (k + 1)-м шагах выполнения основного цикла промежуточными результатами будут
хk'   = Min(xk, xk+1, ..., хN),
хk+1' = Min (xk+1, ..., хN).
В силу свойств минимума последовательности чисел имеем
хk' = Min(xk, xk+1, ..., хN) = min (хk, Min (хk+1, ...,хN)) £ Min (xk+1, ..., хN) = хk+1'.
Таким образом, хk £ xk+1 и в силу индуктивного предположения получаем, что
x1' £ х2' £ ... £ хk' £ xk+'1.
Что и требовалось доказать.
Осталось уточнить результаты выполнения последнего шага цикла при k = N - 1. В силу Леммы 2 результатом будет значение
xN-'1 = Min (xN-1, xN) £
хN'.
Таким образом, после N - 1 шагов выполнения основного цикла для последовательности в целом будут выполнены соотношения упорядоченности


x1' £ x2' £ ... £ хN' .
Что и требовалось доказать. Следовательно, рассмотренный алго­ритм упорядочения чисел правильный в целом.
Применим теперь данный способ упорядочения для решения задачи сортировки. Рассмотрим следующую задачу. Пусть дана не­которая партия товаров с заданной отпускной ценой, указана цена товаров и известны остатки от их продажи. Требуется подсчитать выручку от продажи и отсортировать товары по их остатку.
Данные о товарах представлены двумя таблицами:
товар              стоим                      кол-во      

яблоки
500
200
огурцы
400
250
арбузы
200
600

товар              цена           остаток

яблоки
2500
100
огурцы
2000
150
арбузы
1200
200

Приведем точную постановку задачи и сценарий диалога с ком­пьютером для решения поставленной задачи.
Постановка задачи                                                                            Сценарий
Сортировка товаров по остатку.    
Дано:                                                                                                  товары:
D = (d1, d2, .... dN) - данные товара,                                     <товар1> <s1> < m 1>  *
d = (товар, s, m),                                                                                ...... ... ...     
s - стоимость, m - кол-во,                                                                 остатки:
R = (r1, r2, ..., rN) - данные об остатках,                                <товap1> <c1> < р1>   *
г = (товар, с, р),                                                                                 ...... ... ...     
с - цена, р - остаток.
Треб.:
S - сумма выручки,                                                                выручка = <S>
R' = (r1', ..., rN') - упорядоченные данные,                                       сортировка:
Где:                                                                                         <товар1'> <с1'> <р1'>  *


S = (c1-s1)×(m1-p1) +...+ (сN-sN)×(mN-рN),                                              ............     
р1' £
р2' £
... £ рN',      
рk' = рi  для k = 1 ... N и i = 1 ... N.
При:
N > 0.
Для представления исходных данных в программе примем опера­торы data:
tovs: 'товары:                                               osts: 'остатки:
data «яблоки», 500, 200                               data «яблоки», 2500, 100
data «огурцы», 400, 250                              data «огурцы», 2000, 150
data «арбузы», 200, 600                               data «арбузы», 1200, 200
data «персик», 800, 100                               data «персик», 2000, 0
data «», 0, 0                                                    data «», 0, 0
 
Приведем теперь алгоритм и программу решения поставленной задачи в соответствии с выбранным сценарием и рассмотренным выше способом упорядочения массивов методом «пузырька».
При составлении алгоритмов и программы решения этой задачи будем использовать принцип нисходящей разработки «сверху-вниз»: от основного алгоритма и основной части программы к алгоритмам и подпрограммам решения вспомогательных подзадач.
При решении сложных задач существенным становится органи­зация и представление данных: подбор массивов и переменных для размещения и обработки данных в памяти ЭВМ, а при выделении подпрограмм - процедуры доступа к этим данным.
Для размещения исходных данных о товарах в поставленной задаче примем пять массивов: tv(l:N), s(l:N), m(l:N), с (1:N), p(l:N). Общий размер этих массивов ограничим числом N = 200, которое явно выделено в описании массивов с тем, чтобы в дальней­шем его можно было увеличить для большего количества данных без других изменений программы.
алг «выручка и остатки товаров»                       'выручка и остатки товаров
N
= 100                                                                      N = 100
массив tv[1:N],s[1:N],m1l:N]                                   dim tv$(N),s(N),m(N)


массив L[1:N],c[1:N],p[1:N]                                    dim L(N),c(N),p(N)
нач                                                                              сls
вывод («товары:»)                                                   ? «товары:»
данные-товаров                                                       gosub tovar 'товары
вывод («остатки:»)                                                ? «остатки:»
данные-остатков                                                   gosub ostatok 'остатки
вывод («-----»)                                                            ? «-----»
подсчет-выручки                                                     gosub vyruch 'выручка
вывод («выручка», S)                                               ? «выручка=»;S
вывод («сортировка:»)                                            ? «сортировка:»
сортировка-товаров                                               gosub sortdan 'сортировка
кон                                                                              end
По приведенному алгоритму и основной части программы видно, что последовательность ввода-вывода данных о товарах и резуль­татов обработки полностью соответствует выбранному сценарию. Загрузку исходных данных в выбранные массивы в соответствии с принятым представлением выполнят два следующих вспомогательных алгоритма
алг «данные товаров»                                             tovar: 'данные товаров
нач                                                                              '
загрузка-товаров                                                    restore tovs
от k = 1 до N цикл                                                  for k = 1 to N
чmeнue(tv(k),s(k),m(k))                                          read tv$(k),s(k),m(k)
при tv(k) = «» то                                                     if tv$(k) = «» then exit for
вывод (tv(k),s(k),m(k))                                            ? tv$(k);s(k);m(k)


кцикл                                                                        next k
если k< Nmo N := k-1                                              if k < N then N = k-1
кон                                                                              return
Последний условный оператор изменяет верхнюю границу N массивов в том случае, если фактическое число данных меньше числа мест в массивах, размещенных в памяти компьютера.
алг «данные остатков»                                          ostatok: 'данные остатков
нач                                                                              '
загрузка-остатков                                                 restore osts
от k = 1 до N цикл                                                  for k = 1 to N
чmeнue(tv(k),c(k),p(k))                                           read tv$(k),c(k),p(k)
при tv(k) = «» выход                                                if tv$(k) = «» then exit for
вывод (tv(k),c(k),p(k))                                             ? tv$(k);c(k);p(k)
кцикл                                                                        next k
если k < N mo N := k-1                                            if k < N then N = k-1
кон                                                                              return
Подсчет выручки в соответствии с постановкой задачи по данным, введенным в эти массивы, выполнят следующие вспомогательный алгоритм и подпрограмма:
алг «подсчет выручки»                                           vyruch: 'подсчет выручки
нач                                                                              '
S := 0                                                                         S = 0
от k = 1 до N цикл                                                  for k = 1 to N
S := S+(c(k)-s(k)) *(m(k)-p(k))                                S = S+(c(k)-s(k))*(m(k)-p(k))
кцикл                                                                        next k


кон                                                                              return
Лемма 3. Конечным результатом выполнения данного вспомога­тельного алгоритма будет сумма
SN
= (с(1) - s(l))×(m(l) - р(1)) + ... + (c(N) - s(N))×(m(N) - p(N)).
Доказательство проводится с помощью индуктивных рассужде­ний. Первое присваивание S := 0 обеспечивает начальное значение суммы S0 = 0.
О результатах k-го шага выполнения цикла можно сделать индук­тивное утверждение
Sk = Sk-1
+ (c(k)-
s(k))-(m(k) - p(k)) = (с(1) - s(l))×(m(l) - p(l)) + ... + (c(k) - s(k))×(m(k) - p(k)).
Это утверждение доказывается с помощью математической индукции. На его основании можно сделать заключение о том, что конечным результатом выполнения цикла и алгоритма в целом будет сумма
SN
= (с(1) - s(l))×(m(l) - р(1)) + ... + (c(N) - s(N))×(m(N) - p(N)).
Что и требовалось доказать.
Для сортировки данных воспользуемся алгоритмом упорядочения чисел по методу «пузырька», предполагая, что исходная и упорядоченная последовательность чисел r1, r2, ..., rN будут записаны в мас­сиве x[l:N].
Для формирования результирующих упорядоченных данных ис­пользуется массив индексов L(1:N), в котором будут записаны номера элементов исходной последовательности так, что x(k) = p(L(k)) для всех k = 1, ..., N.
алг «сортировка данных»                                      sortdan: 'сортировка данных
массив x[1:N]                                                            dim x(N)
нач                                                                              '
от k = 1 до N цикл                                                  for k = 1 to N
L(k) = k                                                                    L(k) = k
x(k)=p(L(k))                                                             x(k)=p(L(k))
кцикл                                                                        next k
сортировка-массива                                              gosub sortmas 'сортировка


от k = 1 до N цикл                                                  for k = 1 to N
i := L(k)                                                                   i = L(k)
вывод (tv(i),c(i),p(i))                                                ? tv$(i);c(i);p(i)
кцикл                                                                         next k
кон                                                                              return
Модификация алгоритма упорядочения чисел, размещаемых в массиве x[l:N], с учетом перестановок значений в массиве индексов L[1:N] получает следующий вид:
алг «сортировка массива»                                     sortmas: 'сортировка массива
нач                                                                              '
от k = 1 до N-1 цикл                                               for k = 1 to N-1
xmn := x(k)                                                              xmn = x(k)
imn := k                                                                    imn = k
от i = k + 1 до N цикл                                            for i = k + 1 to N
если x(i) < xmn то                                                if x(i) < xmn then
xmn := x(i)                                                              xmn = x(i)
imn := i                                                                   imn = i
кесли                                                                        end if
кцикл                                                                         next i
Imn := L(imn)                                                            Imn = L(imn)
xmn := x(imn)                                                            xmn = x(imn)
L(imn) := L(k)                                                            L(imn) = L(k)
x(imn) := x(k)                                                            x(imn) = x(k)
L(k) :=Imn                                                                L(k) = Imn


x(k) := xmn                                                               x(k) = xmn
кцикл                                                                         next k
кон                                                                              return
Лемма 4. Результатами выполнения алгоритма сортировки массива будут последовательность чисел, упорядоченная по возрастанию
х(1)' £ х(2)' £ ... £ x(N)'
и последовательность индексов в массиве L[1:N], удовлетворяющих условиям
x(k)' = p(L(k)) для всех k = 1, .... N.
Доказательство. Первое утверждение об упорядоченности значе­ний х(1)' £ х(2)' £... £ x(N)' массива x[l:N] по завершении алгоритма следует из доказательства правильности алгоритма упорядочения последовательности чисел. Для доказательства второго утверждения рассмотрим результаты перестановок значений элементов:
Imn := L(imn)                                    Imn = L(imn)
xmn
:= x(imn)                                    xmn = x(imn)
L(imn) := L(k)                                    L(imn)' = L(k)
x(imn) := x(k)                                     x(imn)' = x(k)
L(k) := Imn                                         L(k)' = Imn = L(imn)
x(k) := xmn                                         x(k)' = xmn = x(imn)
Перед началом выполнения алгоритма упорядочения массива в алгоритме сортировки данных массив индексов L[1:N] и упорядочи­ваемый массив x[l:N] получают значения, удовлетворяющие следу­ющим соотношениям:
х(i)' = P(L(i) для всех i = 1, ..., N.
Покажем, что эти соотношения сохраняются после каждого шага цикла. Действительно, на каждом очередном k-м шаге цикла будут получены следующие результаты:
Imn = L(imn)
xmn = x(imn) == p(L(imn))
L(imn)' = L(k)
x(imn)' = x(k) = p(L(k)) = p(L(imn)')
L(k)' = Imn = L(imn)
x(k)' = xmn = x(imn) = p(L(imn)) = p(L(k)')
Следовательно, после каждого шага цикла для переставленных элементов массивов сохраняются соотношения


x(i)' = p(L(i)) для всех i = 1, ..., N.
Что и требовалось доказать.
Утверждение. Конечным результатом выполнения алгоритма и подпрограммы сортировки данных будет список данных, в котором последовательность значений р1', р2', ..., рN' будет упорядочена:
p1' £  р2' £  … £ pN'
Доказательство. В соответствии с доказанной выше леммой 4 зна­чения в массиве x[l:N] после выполнения алгоритма упорядочения чисел будут удовлетворять условиям
х(1)' £  х(2)' £  ... £  x(N)'.
В силу этой же леммы 4 значения индексов в массиве
L[1:N] будут удовлетворять соотношениям x[k]' = p(L(k)) для всех k = 1, ..., N.
Конечным результатом алгоритма сортировки данных является вывод значений из массива p[l:N] в соответствии с массивом индек­сов L[1:N]. Таким образом, очередные значения последовательности p1', p2',... будут равны:
р1' = p(L(l)) = х(1)',
p2'= р(L (2)) = х(2)'и т. д.
В силу упорядоченности значений х(1)', х(2)', ...,
x(N)' получаем, что значения выходной последовательности будут также упорядо­чены:
p1' £  р2' £  … £ pN'
Что и требовалось доказать.
Следовательно, весь комплекс алгоритмов и подпрограмм пол­ностью соответствует поставленной задаче и гарантирует получение правильных результатов, при любых допустимых исходных данных.
Проверка на ЭВМ программы сортировки товаров, составленной таким систематическим образом, при указанных исходных данных дает следующие результаты:
товары:
яблоки, 500, 200
огурцы, 400, 250
арбузы, 200, 600
персики, 800, 100
остатки:
яблоки, 2500, 100
огурцы, 2000, 150
арбузы, 1200, 200
персики, 2000, 0
выручка = 880000
сортировка:
персики, 2000, 0
яблоки, 2500, 100
огурцы, 2000, 150
арбузы, 1200, 200
Таким образом, выполнение программы подтверждает правиль­ность составленного комплекса алгоритмов. Полное и исчерпыва­ющее обоснование их правильности приведено выше.
 
 
В о п р о с ы
 
1. Что такое сложные алгоритмы и программы?


2. Что такое упорядоченная последовательность?
3. Что такое упорядочение методом «пузырька»?
4. Как доказывается правильность сложных программ?
5. Что такое разработка программ «сверху-вниз»?
З а д а ч и
 
1. Составьте алгоритм и программу обработки данных о товарах и постройте обоснование их правильности для следующих задач:
а) подсчет планируемых доходов от продажи товаров;
б) подсчет начальной суммы вложений реализации товаров;
в) подсчет планируемой прибыли от продажи товаров;
г) подсчет текущей задолженности.
2. Составьте алгоритм и программу сортировки данных о товарах и постройте обоснование их правильности для следующих задач:
а) сортировка данных по начальному количеству;
б) сортировка данных по остаточному количеству;
в) сортировка данных по начальной стоимости;
г) сортировка данных по продажной цене.
3. Составьте алгоритм и программу сортировки данных о товарах по следующим признакам и приведите обоснование их правильности:
а) по доле планируемых доходов от реализации товаров;
б) по доле прибыли от реализации товаров;
в) по доле убыточности реализации товаров.

Содержание раздела