Г Р А Ф И Т — б а з и с

Приложение 4.
Элементы когнитивного обеспечения

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

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

К сему прилагается | Элементы организации познавательной работы | Опора

Далее будут показаны конкретные случаи визуализации знаний, представляющие как теоретический, так и практический интерес.

Содержание

Примеры визуализации алгоритмов обработки данных

Вывод формул и доказательство их справедливости

Задача 1

Составление алгоритмов с одним циклом

Задача 2

Задача 3

Задача 4

Задача 5

Составление алгоритмов произвольного вида

Задача 6

Примеры алгоритмизации процессов переработки данных

Далее описаны составленные Ляховичем примеры применения методики алгоритмизации к конкретным задачам.

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

Вывод формул и доказательство их справедливости

Задача 1

Дано: последовательность элементов а1, а2, а3, ...,аn ,

где n чётное.

Надо: определить сумму элементов последовательности с нечётными номерами S и визуализировать соответствующий алгоритм.

Решение (только для вывода рабочих формул).

Понятно, что объект исходных данных в задаче один - массив элементов последовательности аi. К промежуточным величинам относится i, n; к результатным – S.

Описание процесса решения задачи по этапам:

1) S1=a1+a3;

2) S2=S1+a5;

3) S3=S2+a7.

Из сопоставления формул трёх этапов несложно подметить, что будет справедливо инвариантное выражение

i) Si=Si-1+a2i+1 (3)

Это выражение и будет основной рабочей формулой.

Последний этап описывается как:

Sr=Sr-1+an-1

Приводя операцию первого этапа к инвариантному виду, имеем:

S1=S0+a3

Отсюда следует, что S0=a1, т.е. найдено начальное значение S.

Кроме S в формуле (3) используется i - номер этапа. Начальное значение i=1 определяется из (3), закон изменения

i:=i+1 (4)

Выражение (4) - это формула изменения аргумента. Других переменных в задаче нет.

Разумеется, в рабочей формуле индекс для S не пишется, т.к. это скаляр, изменяемый по присваиванию.

Из того, что индекс величины a в (3) не может превышать n-1, вытекает условие ПЦ:

2i+1≤n-1, или i≤(n-2)/2.

Докажем справедливость выражения (3).

При i=1 выражение верно, что очевидно.

Пусть (3) верно при некотором i=k; покажем, что оно верно и для следующего числа k+1:

Sk=Sk-1+a2k-1=a1+a3+...+a2k+1,

Sk+1=a1+a3+...+a2k+1+a2k+2+1=Sk+a2k+2+1,

т.е.

Sk+1=Sk+a2(k+1)+1

Мы получили (3), где вместо i стоит k+1; следовательно, на основании аксиомы математической индукции заключаем, что (3) верно для любого натурального числа i.

Определены все объекты циклического алгоритма. Заполнив ими блоки типовой схемы, получаем решение поставленной задачи. Блок-схема визуала приведена далее (см. графчасть):

Визуализация содержания алгоритма решения задачи 1

Отметим, что если n нечётное, то задача решается с использованием полученного для задачи 1 результата в два этапа:

1) дополнение массива а до чётного числа элементов (нулевым элементом);

2) определение S по построенному выше алгоритму.

Т.о., такая задача уже относится к произвольному виду.

В начало страницы

Составление алгоритмов с одним циклом

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

Величины и выражения будем записывать, как принято в программировании, а именно:

Для некоторых величин верхняя граница диапазона значений м.б. неизвестна заранее; в этом случае обозначаем её знаком '?'. Эта ситуация не влияет на детерминированность алгоритма; при исполнении конечное число его шагов обеспечивается точным заданием условия ПЦ (ОПЦ) от определённых текущих значений величин.

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

Имена величин (кроме служебных) можно сделать информативными, давая их по общеязыковым правилам; здесь мы сохраним именование Ляховича.

В начало страницы

Задача 2

Дано: функция (многочлен) Z=3X5-X4+6X3-2X2-7X+3

Надо: вычислить Z при одном значении X.

Решение.

1. Принимаем формулировку условия задачи.

2. Описываем объекты данных.

2.1. К исходным данным относятся:

2.2. К результатам относятся:

3. Метод решения очевиден и состоит в вычислении выражения для Z. Этот процесс можно разбить на этапы, на каждом из которых определяется Z с учетом члена очередной степени.

5. Выводим рабочие формулы.

5.1. Порядок решения задачи.

этап 1: b1:=A[4]*X+A[5].

этап 2: r2:=X*X; b2:=A[3]*r2+b1.

этап 3: r3:=r2*X; b3:=A[2]*r3+b2.

Здесь вводятся промежуточные величины:

5.2. Обобщение решения.

этап i: ri:=ri-1*X; bi:=A[5-i]*ri+bi-1

5.3. Формулировка последнего этапа.

этап k: rk:=rk-1*X; bk=Z:=A[0]*rk+bk-1

5.4. Для единообразия 1-ю операцию этапа 2 запишем так:

r2:=r1*X, откуда r1=X.

Этап 1 дополним операцией над ri и приведем к обобщённому виду:

r1:=r0*X; b1:=A[4]*r1+b0,

откуда следуют начальные значения: r0=1 (с учетом предыдущего); b0=A[5].

6. Окончательно формируем содержание глиф для циклического алгоритма.

6.1. Выделяем переменные и выражения (рекуррентные) для них:

r:=r*X |r=1...?

b:=A[5-i]+b |b=1...?

i:=i+1 |i=1...5

Индексы при переменных r, b опускаем.

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

Вертикальной чертой здесь и далее отделяем указание диапазона изменения переменной (обозначение Ляховича).

При вычислении b вводим промежуточную величину d и разбиваем выражение на два:

d:=A[5-i]*r ; b:=d+b.

Приём вычисления через промежуточные величины в данном случае упрощает выражения (что необязательно, если только язык Х не ограничивает число операций в одном выражении); далее он будет применяться и с другими целями.

6.2. Из сравнения индексов при А на i-том и k-том этапах вытекает условие ПЦ: i<5.

7. Изображаем типовую схему базис-блока и заполняем её глифы. Результат показан на рисунке (см. графическую часть).

Визуализация содержания алгоритма решения задачи 2

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

В начало страницы

Задача 3

Дано: матрица A(nXn).

Надо: найти наибольший элемент побочной диагонали.

Решение.

1. Принимаем формулировку условия задачи.

2. Описываем объекты данных.

2.1. К исходным данным относятся:

2.2. К результатам относятся:

3. Метод решения: сравниваем первые два элемента диагонали и находим наибольший. Результат сравниваем с третьим элементом диагонали и находим наибольший и т.д.

5. Выводим рабочие формулы.

5.1. Порядок решения задачи.

этап 1: проверить условие A[1,n]>A[2,(n-1)]; если оно выполняется, то наибольшее на данном этапе значение b1:=A[1,n], иначе b1:=A[2,(n-1)].

этап 2: проверить b1>A[3,(n-2)]; если выполняется, то b2:=b1, иначе b2:=A[3,(n-2)].

этап 3: проверить b2>A[4,(n-3)]; если выполняется, то b3:=b2, иначе b3:=A[4,(n-3)].

5.2. Обобщение решения.

этап i bi-1>A[(i+1),(n-i)] ?: да — bi:=bi-1. нет — bi:=A[(i+1),(n-i)].

Здесь мы одновременно перешли к формулировке текста условия в виде вопроса с «да-нетным» ответом, как принято в техноязыке; оператор проверки условия записан как '?:' - так принято в некоторых текстовых ЯВУ. Случаи разных результатов проверки оформлены как ответы на вопрос. После ответа перечисляются операторы, выполняемые в этом случае. Нетрудно видеть, что ответы соответствуют ключевым словам типа ТО и ИНАЧЕ ЯВУ-текста. Завершение ветви условной конструкции мы обозначаем точкой.

То же как логическая структура:

Ось 1

Ось 2

Ось 3

(*предыдущий этап*)

bi-1>A[(i+1),(n-i)] ?:



(*следующий этап*)



?: = да

bi:=bi-1.



?: = нет

bi:=A[(i+1),(n-i)].

Здесь принята двумерная ЛСП; завершение всей конструкции представляется продолжением записи по Оси1.

Некоторые сочетания мы представим на примерах записи условий в следующих задачах.

5.3. Формулировка последнего этапа.

Ось 1

Ось 2

Ось 3

(*этап r:*)

br-1>A[n,1] ?:



(*завершение*)



?: = да

br:=br-1.



?: = нет

br:=A[n,1].

Здесь мы внесли название этапа в комментарий. Также ширина граф ЛСП-таблицы установлена по наибольшей длине строки содержимого.

5.4. Для единообразия операции этапа 1 запишем так:

Ось 1

Ось 2

Ось 3

(*этап 1:*)

b0>A[2,(n-1)] ?:



(*этап i*)



?: = да

b1:=b0.



?: = нет

b1:=A[2,(n-1)].

откуда начальное значение: b0=A[1,n].

Заметим, что определить начальное значение, по-видимому, «несравненно проще», говоря словами Ляховича, когда текстовая запись условных выражений для этапов структурирована «неизбыточными» средствами, хотя бы так, как здесь. Тогда как запись в виде граф-схемы добавляет графику вершин и связей, которая человеку, привыкшему к тексту, может и затруднить восприятие необходимых закономерностей для вывода. То же м.б. справедливо и для ЯВУ-текста с его ключевыми словами для обозначения маршрутов и их частей.

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

6. Окончательно формируем содержание глифов для циклического алгоритма.

6.1. Выделяем переменные и выражения (рекуррентные) для них:

Ось 1

Ось 2

Ось 3

(*этап i: |b=A[1,n]...?*)

b>A[(i+1),(n-i)]?:




(*завершение*)



?: = да

b:=b. (*т.е. ничего делать не нужно*)



?: = нет

b:=A[(i+1),(n-i)].

Как видим, графы таблицы м.б. и неодинаковой ширины, а строки могут и переноситься.

Заметим, что выражения для индексов у Ляховича «математизированные», что требует понимания перехода к инфор-модели. Для упрощения используем то, что индексное выражение можно записать информатически как цикл с параметром:

ДЛЯ b ОТ A[1,n] ДО ? ШАГ НА [1,-1]

Тогда по индексному выражению для i вида:

i:=i+1 |i=1...n-1

можно записать цикл в виде варианта «полуторамерной» ЛСП:

Ось 1

Ось 2

(*этап i:*)

ДЛЯ i ОТ 1 ДО n-1 ?:


?: = да


СЛЕД i (*возврат к началу*)

?: = нет

ВСЁ ДЛЯ i. (*завершение*)



(*выполнить тело цикла ДЛЯ*).


ШАГ НА 1.


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

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

6.2. Из сравнения индексов при а на i-том и k-том этапах вытекает условие ПЦ:

i+1<n, или i<n-1.

7. Изображаем типовую схему базис-блока и заполняем её глифы. Результат показан на рисунке (см. графическую часть):

Визуализация содержания алгоритма решения задачи 3

В начало страницы

Задача 4

Дано: функция Y=aX (X<0)

Надо: вычислить приближённое значение функции с помощью разложения её в ряд:

Y=1+X*lna/1+X2*ln2a/2+...

Допустимая погрешность - ε.

Решение.

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

2. Описываем объекты данных.

2.1. К исходным данным относятся:

2.2. К результатам относятся:

3. Метод: последовательное вычисление каждого члена ряда, начиная с первого, и сложение его с предшествующей суммой.

Введём обозначение (промежуточную величину): c=ln(a);

Как и в предыдущей задаче, промежуточная величина упростит запись выражений; кроме того, тем самым мы косвенно «вводим в обращение» исходную величину а. Однако важнее, что здесь этим приёмом мы избегаем многократного логарифмирования в ходе исполнения алгоритма.

5. Выводим рабочие формулы.

5.1. Порядок решения задачи.

этап 1: b1:=c*X; Y1:=b1+1.

этап 2: r2:=1*2; b2:=b1*c*X/r1; Y2:=b2+Y1.

этап 3: r3:=r2*3; b3:=b2*c*X/r3; Y3:=b3+Y2.

Здесь промежуточная величина r - это произведение знаменателя текущего члена ряда на знаменатели предыдущих; такое определение позволяет построить рабочую формулу для b.

5.2. Обобщение решения.

этап i: ri:=ri-1*i; bi:=bi-1*c*X/ri; Yi:=bi+Yi-1.

5.3. Из п.1 известно условие ОПЦ будущего алгоритма: |b<ε|, поэтому формулировка операций последнего этапа не требуется.

5.4. Для единообразия операции этапов 1 и 2 запишем так:

r2:=2*r1; r1:=1*r0; b1:=b0*c*X/r1; Y1:=b1+Y0.

Отсюда следует, что начальные значения r, b, Y равны 1.

6. Окончательно формируем содержание глифов для циклического алгоритма.

6.1. Выделяем переменные и выражения (рекуррентные) для них:

i:=i+1 |i=1...?

Y:=Y+b/r |Y=1...?

r:=r*i |r=1...?

b:=b*c*X/r |b=1...ε

7. Изображаем типовую схему базис-блока и заполняем её глифы. Результат показан на рисунке (см. графическую часть).

Визуализация содержания алгоритма решения задачи 4

В начало страницы

Задача 5

Дано: массив А(1:n).

Надо: выбрать из массива все положительные элементы.

Решение.

1. Принимаем формулировку с уточнением: результат оформим также в виде массива (исходя из правила выделения и типизации данных).

2. Описываем объекты данных.

2.1. К исходным данным относятся:

2.2. К результатам относятся:

Размер массива В максимален, т.к. число положительных элементов массива А заранее неизвестно.

3. Метод: сравниваем с нулём каждый элемент массива А по порядку, начиная с 1-го; если его значение больше нуля, то переносим его в массив В.

5. Выводим рабочие формулы.

5.1. Порядок решения задачи «в лоб» можно описать так.

этап 1: проверить A[1]>0; если выполняется, то B[1]:=A[1], иначе переход к следующему этапу.

этап 2: проверить A[2]>0; если выполняется, то B[2]:=A[2], иначе переход к следующему этапу.

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

Правильным будет считать, что индекс очередного элемента массива В не совпадает с номером текущего этапа; в общем случае на i-том этапе он может принимать значение от единицы до i.

Исходя из вышесказанного, индекс для В обозначаем как переменную величину f.

Теперь следует вернуться к п. 2.2 и определить получение новой переменной. Очевидно, все её значения описываются рекуррентным выражением (итерационной формулой):

f:=f+1. (З5.1)

Очевидно также, что вычисление нового значения f по (З5.1) следует выполнять при каждом выявлении в массиве А очередного положительного элемента.

Значение f по завершении алгоритма будет указывать число положительных элементов в А (и одновременно номер последнего элемента В, содержащего результат).

5.1. Порядок решения задачи (корректный).

этап 1: A[1]>0? : да – f:=f+1, B[f]:=A[1]; нет – переходим к следующему этапу.

этап 2: A[2]>0? : да – f:=f+1, B[f]:=A[2]; нет – переходим к следующему этапу.

5.2. Обобщение решения.

этап i: A[i]>0? : да – f:=f+1, B[f]:=A[i]; нет – переходим к следующему этапу.

5.3. Операции последнего этапа соответствуют обобщённым.

5.4. Операции первого этапа уже приведены к общему виду добавлением формулы (З5.1); из неё определяется начальное значение f=0.

6. Окончательно формируем содержание глиф для циклического алгоритма.

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

i:=i+1 |i=1...n. (З5.2)

6.2. Из (З5.2) вытекает условие ОПЦ: i<n.

7. Изображаем типовую схему базис-блока и заполняем её глифы. Результат показан на рисунке (см. графическую часть):

Визуализация содержания алгоритма решения задачи 5

Как и в задаче 3, имеем сложную (ветвящуюся) структуру рабочего блока циклического визуала.

В данной задаче встретился частный случай для п. 5.

В начало страницы

Составление алгоритмов произвольного вида

Задача 6

Дано: матрица A(n,n).

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

Решение.

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

2. Описываем объекты данных.

2.1. К исходным данным относятся:

2.2. К результатам относятся:

3. Метод: последовательно преобразуем строки матрицы, начиная с первой.

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

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

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

1) Обработка строк с 1-й по (n-1)-ю.

2) Обработка n-ной строки.

Отсюда вытекает, что задача сложная, поэтому продолжаем выполнение данной методики.

5. Выделяем наиболее крупную многократно выполняемую операцию.

5.1. Расписываем начальные этапы.

этап 1: B[1]:=A[1,n]; сдвинуть в 1-й строке элементы A[1,1]...A[1,(n-1)] на места элементов A[1,2]...A[1,n]; A[1,1]:=0.

этап 2: B[2]:=A[2,n]; сдвинуть во 2-й строке элементы A[2,2]...A[2,(n-1)] на места элементов A[2,3]...A[2,n]; A[2,2]:=0.

5.2. Составляем обобщённое описание.

этап i: B[i]:=A[i,n]; сдвинуть в i-той строке элементы A[i,i]...A[i,(n-1)] на места элементов A[i,(i+1)]...A[i,n]; A[i,i]:=0.

5.3. Операции последнего этапа соответствуют обобщённым; на этом этапе обрабатывается (n-1)-я строка матрицы А.

5.4. На каждом этапе также определяется новый индекс из итерационной формулы:

i:=i+1 |i=1...n-1. (З6.1)

6. Составляем укрупнённую схему алгоритма решения всей задачи.

6.1. Выражения для исходных данных и результатов, множества которых заданы указанием граничных значений индексов, уже составлены в п. 5.

6.2. Из (З6.1) вытекает условие ОПЦ: i<n-1.

Укрупнённая схема показана на рисунке (см. графическую часть):

Визуализация содержания алгоритма решения подзадачи 1 задачи 6

7. Дальнейшей детализации подлежит операция сдвига элементов i-той строки. Рассматриваем её как подзадачу второго уровня детализации, обозначив буквенным индексом «А».

Дано: матрица A(n,n).

Надо: сдвинуть элементы A[i,i]...A[i,(n-1)] на места элементов A[i,(i+1)]...A[i,n].

Решение. (к номерам пунктов методики будем добавлять приставку-индекс подзадачи)

А2. Описываем объекты данных.

А2.1. К исходным данным относятся:

А2.2. К результатам относятся:

А3. Метод: последовательно переносим вправо каждый элемент, начиная с последнего.

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

Порядок решения задачи (для краткости без выделения пунктов):

этап 1: A[i,n]:=A[i,(n-1)].

этап 2: A[i,(n-1)]:=A[i,(n-2)].

этап j (т.к. имя i уже занято): A[i,(n-j+1)]:=A[i,(n-j)].

этап r (последний): A[i,(i+1)]:=A[i,i].

Все этапы изначально записаны в единообразном виде; нужно лишь вывести выражение для индекса j:

j:=j+1 |j=1...n-i.

Теперь имеем все рабочие формулы.

А6. Окончательно формируем содержание глиф для циклического алгоритма.

А6.1. Переменные и выражения для них уже имеются.

С целью упрощения выражений для индексов матрицы введем еще одну промежуточную величину k:=n-j. Тогда обобщённая операция i-того этапа запишется в виде:

A[i,(k+1)]:=A[i,k].

А6.2. Сравнивая выражения для 2-го индекса результата операции на j-том и r-том этапах, получаем условие ОПЦ:

n-j+1=i+1 или j=n-i.

А7. Изображаем типовую схему базис-блока и заполняем её глифы. Результат показан на рисунке (см. графическую часть):

Визуализация содержания алгоритма решения подзадачи 1А задачи 6

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

Составляем подробную схему всей задачи, подставляя подробную схему подзадачи "А" вместо укрупнённого блока; результат показан на рисунке (см. графическую часть):

Визуализация содержания алгоритма решения задачи 6

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

В начало страницы | Оглавление | Версия для печати

Copyright © Жаринов В.Н.

1 Ошибка происходит потому, что «лобовой» алгоритм игнорирует неявное требование к результату: элементы массива В должны следовать непрерывно по порядку начиная с 1-го, как и в массиве А; тем самым результат отделяется от неиспользуемой части массива В; отсюда видно, как важно учитывать все условия задачи.

Hosted by uCoz