Учебное пособие по информатике 2014

4. Выстраивание программы из набора фактов. Эта часть процесса программирования вызывает наибольшие затруднения, ибо здесь начинается то, что извне обычно и воспринимается как «программирование»: написание текста программы. Особенность заключается в том, что обычно фрагменты взаимосвязаны друг с другом прямо по структуре алгоритма или косвенно через данные. Различие подходов состоит в том, в какой последовательности в программу включаются фрагменты (по отношению к гипотетической готовой программе), с какой стороны начать этот процесс и в каком направлении двигаться[19].

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

Восходящее проектирование – проектирование программы

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

впроцессе своего написания не нуждается, как и в «историческом» подходе,

виных средствах описания, кроме самого языка программирования. Недостатки тоже очевидны:

-не факт, что программу удастся «свести» в единое целое, особенно сложную;

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

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

61

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

«Грязное» программирование – заключается в создании макета, воспроизводящего основные свойства проектируемой программы. В дальнейшем все изменения/дополнения сохраняют эти первоначальные соотношения.

5. Последовательное приближение к результату. Сложную программу не всегда удается спроектировать за один этап. Цикл «результат – образная модель – факты – выстраивание программы» может повторяться. При выстраивании программы может оказаться, что ненаписанная часть программы нуждается в дополнительном осмыслении, начиная с образной модели. При этом само направление выстраивания программы, т.е. собственно технология программирования, имеют большое значение: она в большей или меньшей степени гарантируется правильность и неприкосновенность уже написанного.

Кратко рассмотрим упомянутые ранее методики[19].

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

«Историческому» принципу проектирования также наиболее соответствует структурная схема алгоритма. К этому есть несколько причин:

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

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

Структурное программирование – от общего к частному.

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

62

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

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

2.Создается образная модель происходящего процесса, используются графические и какие угодно способы представления, образные «картинки», позволяющие лучше понять выполнение алгоритма в динамике;

3.Выполняется сбор фактов, касающихся любых характеристик алгоритма, и попытка их представления средствами языка. Такими фактами является наличие определенных переменных и их «смысл», а также соответствующих им программных контекстов. Понятно, что не все факты удастся сразу выразить в виде фрагментов программы, но они должны быть сформулированы хотя бы на естественном языке;

4.В образной модели выделяется наиболее существенная часть – «главное звено», для которой подбирается наиболее точная словесная формулировка;

5.Производится определение переменных, необходимых для формального представления данного шага алгоритма и формулируется их «смысл»;

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

7.Для оставшихся неформализованных частей алгоритма (в словесной формулировке) - перечисленная последовательность действий повторяется. Обычно разработка образного представления программы опережает ее «выстраивание», поэтому следующим этапом для неформализованной части алгоритма может быть п.4 (в лучшем случае, при его проработке в образной модели) или п.1-3. В любом случае для вложенных конструкций мы возвращаемся на предыдущие этапы проектирования[19].

Неправильное программирование – грязное.

Под «грязным» программированием обычно понимается написание программы, грубо воспроизводящей требуемое поведение. Такая программа может быть быстро разработана и отлажена, а затем использована для уяснения последующих шагов, либо для наложения «заплаток» с целью получения требуемого результата. Хотя этот подход крайне некрасив с точки зрения технологии проектирования, но он может быть оправдан при следующих условиях:

- «грязная» программа воспроизводит требуемое поведение на самом верхнем уровне;

63

- в дальнейшем в нее могут встраиваться контексты и фрагменты, не меняющие ее поведения, но конкретизирующие ее в нужном направлении.

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

Рисунок 2.3 – «Среда обитания» программы

Почему крайне не рекомендуется использовать при программировании оператор goto (оператор безусловного перехода)? Нисходящее пошаговое проектирование исключает использование оператора goto, более того, запрещает его применение как нарушающего структуру программы. Goto страшен не тем, что «неправильно» связывает разные части алгоритма, а в том, что переводит алгоритм из одних «условий обитания» в другие: в точке перехода они составлены без учета того, что управление будет передано в точку программы «не по правилам».

Тем не менее, есть допустимые случаи использования оператора goto. Чрезвычайными обстоятельствами, вынуждающими прибегнуть к помощи оператора goto, являются глобальные нарушения логики выполнения программы, например грубые неисправимые ошибки во входных данных. В таких случаях делается переход из нескольких вложенных конструкций либо в конец программы, либо к повторению некоторой ее части. В других обстоятельствах его использование свидетельствует скорее о неправильном проектировании структуры программы - наличии неявных условных или циклических конструкций. Приведем пример достаточно разумного использования оператора goto.

64

3.МАТЕМАТИЧЕСКИЕ ОСНОВЫ ИНФОРМАТИКИ

3.1Понятие дискретного автомата

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

Вкибернетику, однако, вошел и прочно в ней укрепился термин «дискретный автомат» или кратко просто «автомат» для обозначения гораздо более абстрактного понятия, а именно - модели, обладающей следующими особенностями:

а) на входы модели в каждый из дискретных моментов времени t1, t2,… поступают m входных величин x1,x2,…xm. каждая из которых может принимать конечное число фиксированных значений из входного алфавита

Х;

б) на выходах модели можно наблюдать n выходных величин y1,…yn каждая из которых может принимать конечное число фиксированных значений из выходного алфавита Y;

в) в каждый момент времени модель может находиться в одном из

состояний z1,z2,…zn;

г) состояние модели в каждый момент времени определяется входной величиной x в этот момент и состоянием z в предыдущий момент времени;

д) модель осуществляет преобразование ситуации на входе

x={x1,x2,…,xm} в ситуацию на выходе y={y1,y2,…,yn} зависимости от ее состояния в предыдущий момент времени.

Рисунок 3.1 – Дискретный автомат

Такая модель (рисунок 3.1) удобна для описания многих кибернетических систем.

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

66

Мы ограничимся рассмотрением лишь простейших из дискретных автоматов, входной и выходной алфавиты которых состоят всего из двух букв: 0 и 1. Это оправдывается тем что, как оказывается в теории автоматов, автоматы с такими "бедными" алфавитами способны решать такие же задачи, как и автоматы с любыми другими алфавитами.

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

Логический автомат

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

Каждый выход из логического автомата может принимать значение 0 или 1 в зависимости от значений входных переменных х. Определим число всех возможных логических функций преобразования хi в yi, если число входных величин равно т, каждая из них может принимать значение 0 или 1. Для этого расположим все входные величины в ряд x1, x2, …, xm и будем рассматривать их как разряды двоичного числа. Ясно, что число r различных сочетаний значений входных величин равно числу различных двоичных чисел, содержащих r разрядов, откуда следует, что r=2m. Но каждой из r ситуаций на входе может соответствовать одно из двух значений выхода 0 или 1. Поэтому общее число N всех различных логических функций для логического автомата с m двоичными входами равно

1.- отрицание, инверсия x (читается «не x»). Функция отрицания означает, что x=0, если x=1; и x=1, если x=0.

2.x1 ˄ x2 (x1 & x2) - логическое умножение или конъюнкция (читается «x1

иx2»). Функция логического умножения означает, что его результат равен единице только тогда, когда x1=1 и x2=1, и равен нулю во всех остальных случаях.

3.x1 ˅ x2 (x1 + x2) - логическое сложение или дизъюнкция (читается «x1

или x2»). Функция логического сложения означает, что его результат равен

67

нулю только тогда, когда x1=0 и x2=0 , и равен единице во всех остальных случаях.

Логические функции могут задаваться таблицами, в которых указывается значение функции у (индекс i будем опускать) для всех сочетаний аргументов х. В таблице 3.1 приведены значения двух элементарных логических функций от двух аргументов: x1 и x2. Эту таблицу нужно читать по строкам: «если х1 = ..., a х2 = ..., то х1 и х2 =..., а х1 или х2 =

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

Таблица 3.1 – Задание логических функций таблицей

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

Логические элементы выполняют преобразования информации, которые описываются логическими функциями (таблица 3.1). Условные графические обозначения (УГО) элементов И, ИЛИ и НЕ на функциональных схемах приведены на рисунке 3.2.

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

– справа. Инверсный выход обозначается кружком (рисунок 3.2в)

68

При передаче одноразрядных данных (рисунок 3.4а) один вход элемента И является информационным, а второй — управляющим. На информационный вход поступают одноразрядные данные D от источника А. Если на управляющем входе сигнал «Передать» равен «0», то на приемник В поступает сигнал «0» независимо от значения данных D. Если сигнал «Передать» равен «1», то сигнал на выходе элемента И совпадает с информационным сигналом и на вход приемника поступают данные D.

При передаче многоразрядных данных (рисунок 3.4б) каждый разряд данных проходит через отдельный элемент И, а сигнал «Передать» подается одновременно на управляющие входы всех ключей.

Рисунок 3.4 – Схемы передачи данных а – одноразрядных, б – многоразрядных

Автомат с конечной памятью. Триггеры

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

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

где yj- выход автомата в j-й такт зависит от состояния автомата в (j-1)-й такт, zj-1 - состояние автомата в (j-1)-й такт.

70