nextupprevious

Next:1.1.3 Как можно определять функции?
Up:1.1 Алгоритмы и функции
Previous:1.1.1 Что такое алгоритм?

1.1.2 Что такое компьютер?

Главная цель нашего изучения алгоритмов в настоящей книге -- научиться формулировать их так, чтобы они могли исполняться на устройствах, работающих автономно, независимо от человека. Такие устройства, широко распространенные сегодня, называются компьютерами или электронными вычислительными машинами (ЭВМ), а алгоритмы, предназначенные для исполнения на ЭВМ, называются программами. Какой-нибудь десяток лет назад всякий учебник по программированию начинался довольно подробным описанием того, как устроена ЭВМ, что она может делать. Понятия программы и алгоритма вводились затем на основе этих сведений, т.е. выводились из функций, реализуемых ЭВМ. Сегодня более предпочтительным представляется другой путь. Понятие алгоритма вводится как исходное, базовое понятие, а конструкция устройств, реализующих различные алгоритмы, определяется как понятие производное, в значительной мере учитывающее специфику тех средств, с помощью которых формулируются те или иные алгоритмы. В этой связи принятым стало говорить об ЭВМ различной архитектуры.

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

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

ЭВМ -- это автомат, способный реализовать процесс вычислений по заданной программе и состоящий из памяти, одного или нескольких процессоров, устройств ввода и вывода. Программа, представляющая собой последовательность команд, понятных ЭВМ, и ее исходные данные вводятся в память машины с помощью устройств ввода, в качестве которых могут использоваться клавиатура, мышь, сканер или устройства чтения с дискет или лазерных дисков. Введенные команды и данные программы хранятся в памяти ЭВМ в закодированном виде. К основным характеристикам памяти относятся ее емкость (количество адресуемых элементов памяти) и скорость, с которой происходит запись в память или считывание из нее. Любое обращение к памяти должно сопровождаться указанием порядкового номера соответствующего элемента памяти, называемого его адресом. Адрес изменяется от 0 до m-1, где m -- емкость памяти.

Целый ряд соображений оправдывает преимущественное применение при кодировании алфавита из двух символов (двоичного алфавита), условно называемых 0 и 1. Использование в современных ЭВМ двоичного алфавита и двоичной системы счисления (вместо всем хорошо знакомой десятичной) выражается, в частности, в том, что байт, состоящий из 8 двоичных запоминающих устройств, называемых битами, обычно представляет собой минимальный адресуемый элемент памяти ЭВМ и может принимать $2^8=256$ различных состояний. Биты в байте нумеруются от 0 до 7 справа налево. Важно отметить, что состояние байта может быть изменено только при записи информации в него.

Для представления чисел, однако, размер байта не является достаточным. Поэтому обычно байты объединяются в пары: нулевой с первым, второй с третьим, четвертый с пятым т.д. Такая пара байтов с соседними адресами, из которых меньший адрес четный, называется словом. Так как слово состоит из двух байтов (16 битов), то оно может принимать $256^2=2^{16}=65 536$ различных состояний. Биты в слове нумеруются с нуля и справа налево.

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

Если для представления каких-то объектов размер слов не является достаточным, то используются группы байтов большего размера. Например, вещественные числа кодируются в двух соседних словах -- так называемые двойные слова. Двойное слово образовано из четырех байтов с соседними адресами, из которых меньший адрес кратен четырем. Оно может принимать $2^{32}=65536^2$ различных состояний.

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

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

Не требуется, чтобы выполнение программы всегда после конечного числа шагов нормально завершалось достижением одного из конечных состояний. Для некоторых входных данных программа может задавать потенциально бесконечный процесс вычисления (сколько бы такой процесс ни продолжался, ЭВМ никогда не приходит ни в одно из конечных состояний). Кроме того, в ЭВМ предусмотрены специальные ситуации (состояния ошибки), возникновение любой из которых аварийно завершает ход вычисления по программе. Например, состояние ошибки возникает в том случае, когда у выполняемой команды обрабатываемые ею аргументы не удовлетворяют нужным условиям (деление на нуль и т.п.). Говорят, что программа применима к некоторому набору входных данных, если процесс обработки его нормально завершается после конечного числа шагов, и неприменима к нему, если процесс вычисления аварийно завершается или является потенциально бесконечным. Поэтому в общем случае функция, реализуемая программой, является частичной по отношению к множеству всех наборов входных данных. Область определения этой функции состоит из всех тех входных наборов, к которым программа применима.

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

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

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

Второй прием -- это разработка специальных языков программирования "высокого уровня", таких как Zonnon, Паскаль, Фортран и многие сотни других языков. Эти языки приближены к решаемой задаче настолько, насколько это возможно, и позволяют представить алгоритм в такой более удобной для человека текстовой форме, для которой существует возможность автоматического перевода в логически эквивалентную машинную программу. Операция перевода (трансляция) выполняется специальной системной программой, называемой транслятором. Язык программирования высокого уровня -- это средство, позволяющее программировать на некоторую физически не существующую (виртуальную) вычислительную машину $A$, которая не связана имеющимися техническими ограничениями и ориентируется на человека, а транслятор -- это программа для реально существующей машины $B$, которая позволяет машине $B$ выступать в роли виртуальной машины $A$. При этом обработка программы $P$ обычно происходит в два этапа, которые во времени следуют один за другим: этап трансляции -- построения машинной (рабочей) программы и этап выполнения построенной машинной программы, при котором осуществляются обработка входных данных программы $P$ и печать полученных результатов.
 

Next:1.1.3 Как можно определять
Up:1.1 Алгоритмы и функции
Previous:1.1.1 Что такое алгоритм?


© В.Н. Касьянов, Е.В.Касьянова, 2004