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

Приложение 4.
Элементы организации познавательной работы

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

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

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

Здесь даны материалы, раскрывающие процесс формализации, как правило, в виде примерных методик проведения работы в целом или её отдельных составляющих.

Содержание

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

Обозначения и определения

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

Общие положения

Содержание методики

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

Общие положения

Содержание методики

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

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

Обозначения и определения

1. Назначение методики – визуализация процесса получения результата задачи.

В основе лежит методика составления алгоритмов по В. Ляховичу.

2. Объект методики (исходное описание) – неалгоритмическое словесно-формульное.

3. Язык записи – блок-схем, частично упорядоченных Ляховичем, со следующими требованиями к подъязыкам.

3.1. В маршрутном подъязыке возможны следующие типы структур алгоритмов (маршрут-схемы) по уровню обобщения.

Блок подробной схемы – глиф «Действие», «Вопрос» либо макроглиф «Переключатель».

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

3.2. В командном подъязыке (текстовой части глифоов) приняты следующие соглашения.

3.2.1. Язык текста укрупнённых схем м.б. любым, в т.ч. естественным.

3.2.2. Текст подробных схем удовлетворяет следующим формальным требованиям.

3.2.2.1. В глифах «Действие» допускается использовать выражения вида:

Х := А, (1)

где Х (А) – любая переменная (арифметическое выражение).

Yi := f(Yi-1), (2)

где Y – одна и та же величина, принимающая ряд значений i=1...n, в частности текущее (i) и предшествующее (i-1).

Выражение (1) выполняется так же, как оператор присваивания в ЯП. Выражение (2) называется рекуррентным.

3.2.2.2. В глифах «Вопрос» или «Вариант» допускается использовать только логические выражения, в частности отношения, например X<Y+2.

3.3. Объекты (данные) задачи декларируются как величины следующих типов:

Имя (метка) величины образуется по общеязыковым правилам (см. п/р 1.1 Приложения 1).

4. Результат методики – содержимое (тело) визуала обработки данных в форме базис-блока одного из следующих видов.

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

5. Базовая метаструктура визуализации определяется в зависимости от формы визуала.

5.1. Циклический алгоритм визуализирует т.н. типовая схема (укрупнённая), в графит-методе имеющая вид базис-блока на базе гибридного цикла (см. графическую часть):

Базис-блок (типовая схема) тела циклического алгоритма

Для визуализации циклического алгоритма необходимо располагать т.н. рабочими формулами, т.е. такими, многократное вычисление по которым дает искомый результат. Обычно рабочая формула – это рекуррентное выражение вида (2); для его вычисления необходимо располагать также начальным значением Y1.

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

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

6. Основная идея методики в терминах ТФЗ-ДРАКОН – эскизная визуализация алгоритма получения результата задачи как укрупнённой маршрут-схемы, где укрупнённый блок обобщённо описывает свою часть, а текст глифов записывается на неформальном языке. Далее от укрупнённой схемы переходят к подробной путем детализации укрупнённых блоков (итеративной для произвольных алгоритмов) и одновременно от командного языка укрупнённых схем – к командному языку подробных схем как совокупности выражений (1) и (2) над величинами.

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

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

7. Для понимания дальнейшего существенны также следующие допущения Ляховича.

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

7.2. Должен быть известен математический метод решения алгоритмизуемой задачи. Если это не так, метод д.б. найден не позднее шага 3 методики, возможно, эмпирически .

7.3. Детализация понимается более узко, чем в ТФЗ-ДРАКОН, а именно только как раскрытие содержания блоков укрупнённой схемы уже заданной структуры до блоков (подсхем) подробной схемы. Поэтому если при визуализации произвольного алгоритма заданная структура укрупнённой схемы оказалась неоптимальной, методика применяется повторно сначала с выбором новой структуры.

7.4. Методика составлялась до появления техноязыка, и диоформой всего визуала в ней неявно считается примитив (т.е. полученный базис-блок подставляется в заготовку-примитив для завершения визуализации). Структура укрупнённой схемы никак не ограничивается, и в общем случае при её визуализации возможны пересечения линий; в этом случае возможно:

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

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

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

Общие положения

1. Для однозначного задания циклического алгоритма необходимо указать три объекта:

2. Визуализация алгоритма в общем происходит следующим образом.

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

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

Условие ОПЦ (ПЦ) выводится затем из сравнения выражений для некоторой величины на i-том и последнем этапах.

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

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

Содержание методики

1. Формулируется условие задачи.

2. Определяются состав и структура объектов данных, т.е. совокупность скалярных величин и массивов, которыми исходные данные будут представлены в задаче.

2.1. Выделяются исходные данные:

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

В сложных задачах м.б. необходимо объединить ряд скаляров и/или массивов в составную величину. При этом структура данных может оказаться проще. Для объединения используется тип запись (в некоторых языках называется «структура»).

2.2. Выделяем результаты, для чего:

3. Выбираем метод решения задачи и разбиваем процесс её решения на этапы с равным числом аналогичных операций.

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

5. Выводятся рабочие формулы, для чего:

5.1. Записываются операции 1-го, 2-го, 3-го этапов решения задачи, используя выражения вида (1) и (2). Результат выполнения одной и той же операции на разных этапах обозначается одним именем с индексом, равным номеру этапа;

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

5.3. Записываются операции последнего этапа, если они известны;

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

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

Если при выполнении п. 5 обнаруживается, что переменная зависит от своего предшествующего значения (на предыдущем этапе решения задачи), то:

Далее действуем в соответствии с методикой.

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

6. Формируем содержание глиф типовой схемы алгоритма:

6.1. Для каждой переменной, включённой в формулы i-того этапа, выписываем начальное и конечное значения и закон изменения. Для каждого массива вводим служебную переменную, содержащую значения его индексов.

6.2. Выявляем условие окончания (повторения) цикла. Оно может:

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

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

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

Общие положения

1. Методика используется для алгоритмизации сложных задач.

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

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

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

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

4. Понятия «наиболее крупная операция» и «наиболее крупный этап» нестроги и применяются к конкретной задаче эвристически, на основе здравого смысла и опыта работы по данной методике.

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

Содержание методики

1. Чётко формулируется условие задачи.

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

3. Формулируется метод решения задачи в наиболее общем виде (без лишних подробностей).

4. Выделяются наиболее крупные этапы решения задачи, которые выполняются однократно и охватывают в совокупности процесс решения всей задачи. При отсутствии таких этапов следует переход к п. 5.

4.1. Если такие этапы есть (в сложной задаче их не менее двух), то:

5. Выделяется наиболее крупная операция, которая выполняется многократно для решения всей задачи.

6. Составляется укрупнённая схема алгоритма с одним циклом по ранее определённой методике. При этом, описывая процесс решения задачи в терминах операции п.5, на каждом из этапов (1, 2, 3,..., i) указываем множества исходных данных и результатов заданием, в общем случае, их граничных значений (или граничных значений индексов).

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

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

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

1 Это означает, что циклический алгоритм для всей задачи построить невозможно и следует строить алгоритм другого вида либо представить алгоритм как совокупность подалгоритмов циклического и/или прочих видов.

Hosted by uCoz