114

Правила построения алгоритмов

Правила построения алгоритмов

Первое правило — при построении алгоритма прежде всего необходимо задать множество объектов, с которыми будет работать алгоритм. Формализованное (закодированное) представление этих объектов носит название данных. Алгоритм приступает к работе с некоторым набором начальных данных, которые называются входными, и в результате работы выдает данные, называемые выходными. Таким образом, алгоритм преобразует входные данные в выходные.

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

Практическая работа с алгоритмами (программирование) начинается с реализации первых двух правил. В языках программирования распределение памяти осуществляется декларативными операторами (операторами описания переменных).

Третье правило — дискретность. Алгоритм строится из отдельных шагов (действий, операций, команд). Множество шагов, из которых составлен алгоритм, конечно.

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

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

62

Виды алгоритма

Виды алгоритма

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

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

+гибкие алгоритмы:

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

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

+линейные алгоритмы — наборы команд (указаний), выполняемых последовательно во времени друг за другом;

+разветвляющиеся алгоритмы — алгоритмы, содержащие хотя бы одно условие, в результате провер-

63

Виды алгоритма

ки которого ЭВМ обеспечивает переход на один из двух возможных шагов; циклические алгоритмы — алгоритмы, предусмат-

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

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

64

Способы записей алгоритмов

Окончание таблицы

3. Описание на каком-либо языке программирования

(программа).

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

Программа — это форма представления алгоритма для исполнения его машиной.

66

Объектно-ориентированное программирование

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

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

Указание — второй основной способ идентификации — связано с использованием особых объектов, в представлении которых хранится как бы «стрелка», указывающая на идентифицируемый объект. Такой особый объект называется указателем или ссылкой. Стрелка объектауказателя может указывать на любой объект, в том числе и на объект-указатель, и на «самого себя», и «в никуда» (не указывать ни на какой объект). Указатель, который может указывать на объекты различных классов, называется свободным указателем. Указатель, который может указывать только на объекты определенного класса, называется ограниченным указателем.

Термин «интерпретация» определяет «приписывание»

объекту определенных семантических, смысловых свойств. Например, символ «I», интерпретируемый как «римская цифра 1», будет ассоциироваться с объектом определенной системы счисления, характеризуемой особыми свойствами этой системы.

Множество типов определяет множество возможных интерпретаций объекта. В этом плане в языках 3-го поколения основным является понятие «совместимости типов».

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

68

Объектно-ориентированное программирование

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

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

Создание объекта следует интерпретировать как выделение памяти под его элемент хранения. Такая интерпретация подразумевает разделение всего рабочего пространства памяти ЭВМ на две категории, два класса — статическую память и динамическую. Первый класс памяти,

69