Контроллеры портов ввода-вывода

Контроллер порта ввода-вывода (КПВВ) обеспечивает интерфейс между периферийным устройством, подключенным к порту КПВВ, и системной шиной.

Порты ввода-вывода делятся на два типа в зависимости от количества бит, проходящих за один такт передачи:

- параллельные, в которых за один такт проходит несколько бит (например, 8 или 16 бит);

- последовательные, в которых за один такт проходит один бит.

Наиболее распространенные порты ввода-вывода.

RS-232 (COM) – интерфейс обмена данными по последовательному коммуникационному порту (СОМ-порту). С помощью данного интерфейса осуществляется работа и подключение таких устройств, как внешний модем, мышь и т. д.

IEEE 1284 (Instute of Electrical and Electronic Engineers 1284; LPT) – стандарт, описывающий спецификации параллельных скоростных интерфейсов SPP (Standard Parallel Port – стандартный параллельный порт), EPP (Enhanced Parallel Port – улучшенный параллельный порт), ECP (Еxtended Capabilities Port – порт с расширенными возможностями). Параллельный порт IEEE 1284 (LPT-порт) используется для принтеров, внешних запоминающих устройств, сканеров.

USB (Universal Serial Bus – универсальная последовательная шина) – универсальный последовательный интерфейс, пришедший на смену устаревшим портам RS-232 и IEEE 1284. Поддерживает технологию Plug and Play с возможностью «горячей» замены, то есть замены устройств без необходимости выключения или перезагрузки компьютера. Для адекватной работы интерфейса необходима операционная система, которая корректно с ним работает. Поддержка USB введена в Microsoft Windows 2000. К портам USB можно подключить до 127 устройств. Каждое устройство, подключенное непосредственно к порту, может работать в качестве разветвителя, то есть можно подключать к нему другие устройства. Скорость передачи через порт – 480 Мбит/с. Кроме данных, через порт подается электропитание. В настоящее время большинство ПУ подключаются через порт USB.

PS/2 (Personal System – персональная система) – последовательный порт, разработанный фирмой IBM в середине 1980-х для своей серии персональных компьютеров IBM PS/2. В отличие от порта RS-232 порт PS/2 имеет более компактный разъем. Через порт подается также электропитание. В настоящее время используется вместе с портом USB.

IEEE 1394 (FireWire, iLink) – последовательный интерфейс, использующийся для подключения цифровых видеоустройств (видеокамер). Через порт возможна передача видеоизображения со скоростью 100-400 Мбит/с. Поддерживает технологию Plug and Play.

PCMCIA (Personal Computer Memory Card International Association; PC Card) – порт, используемый в переносных компьютерах для подключения новых устройств к нему без вскрытия корпуса компьютера. Порт имеет разрядность данных/адреса – 16/26 бит, поддерживает автоконфигурирование, возможно подключение и отключение устройств в процессе работы компьютера. Существует много ПУ, разработанных для переносных компьютеров и использующих порт PCMCIA.

Периферийные устройства

Клавиатура

Клавиатура – это стандартное клавишное устройство ввода, предназначенное для ввода алфавитно-цифровых данных и команд управления. Клавиатуры имеют по 101-104 клавиши, размещенные по стандарту QWERTY (в верхнем левом углу алфавитной части клавиатуры находятся клавиши Q, W, E, R, T, Y).

Набор клавиш клавиатуры разбит на несколько функциональных групп:

- алфавитно-цифровые клавиши (буквы и цифры) предназначены для ввода знаковой информации и команд, которые набираются посимвольно;

- функциональные клавиши (F1-F12); функции клавиш зависят от конкретной, работающей в данный момент времени программы;

- клавиши управления курсором подают команды на передвижение курсора по экрану монитора относительно текущего изображения (стрелки, а также клавиши PAGE UP, PAGE DOWN, HOME, END); курсор – экранный элемент, указывающий на место ввода знаковой информации;

- служебные клавиши используются для разных вспомогательных целей, таких как, изменение регистра, режимов вставки, образование сочетаний «горячих» клавиш и т. д. (SHIFT, CAPS LOCK, ENTER, CTRL, ALT, ESC, DEL, INSERT, TAB, BACKSPACE);

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

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

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

Манипулятор типа «мышь»

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

Принцип работы «мыши» заключается в отслеживании перемещения корпуса «мыши» по поверхности и синхронизации перемещения по экрану монитора курсора.

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

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

Основной характеристикой «мыши» является разрешающая способность – насколько точно можно отследить самое мельчайшее перемещение «мыши». Измеряется в точках (dot) на дюйм (dpi – dots per inch).

Клавиатура и «мышь» подсоединяются к портам PS/2 или USB.

Принтеры

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

Разрешающая способность или разрешение печати измеряется числом элементарных точек (dot), которые размещаются РЅР° РѕРґРЅРѕРј РґСЋР№РјРµ (dpi). Например, разрешение 1440 dpi означает, что РЅР° длине РѕРґРЅРѕРіРѕ РґСЋР№РјР° бумаги размещается 1440 точек. Запись 720 ´ 360 dpi означает разрешение печати РїРѕ горизонтали Рё вертикали соответственно. Чем больше разрешение, тем точнее воспроизводятся детали изображения, РЅРѕ РїСЂРё этом возрастает время печати.

Единицей измерения скорости печати информации служит число печатаемых страниц формата A4 (210 ´ 297 РјРј) РІ минуту (ppm – pages per minute).

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

Максимальный поддерживаемый формат бумаги для большинства принтеров A4 или A3 (297 ´ 420 РјРј).

Принтеры подключаются к ЭВМ через порты LPT или USB.

Рассмотрим три наиболее распространенных типа принтеров: 1) матричные; 2) струйные; 3) лазерные.

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

Достоинства матричных принтеров:

- низкая стоимость принтера и расходных материалов для него (красящей ленты);

- низкая себестоимость копии;

- возможность одновременной печати нескольких копий с помощью копирки.

Недостатки матричных принтеров:

- невысокие качество и скорость печати;

- шум при печати.

Струйные принтеры в печатающем узле вместо иголок имеют тонкие трубочки – сопла, через которые на бумагу выбрасываются мельчайшие капельки красителя (чернил) («пузырьковая» технология). Матрица печатающей головки обычно содержит от 12 до 64 сопел (дюз). Технически процесс распыления выглядит следующим образом. В стенку сопла встроен электрический нагревательный элемент, температура которого при подаче электрического импульса резко возрастает за 5-10 мкс. Все чернила, находящиеся в контакте с нагревательным элементом, мгновенно испаряются, что вызывает резкое повышение давления, под действием которого чернила выстреливаются из сопла на бумагу. Объем выстреливаемой капли не превышает 1,5 пиколитра (1 пиколитр = 10^-10 литра). После «выстрела» чернильные пары конденсируются, в сопле образуется зона пониженного давления и в него всасывается новая порция чернил. Чернила каждого цвета находятся в своем картридже. Для создания цветного изображения используется обычно принятая в полиграфии цветовая схема CMYK, включающая четыре базовых цвета: Cyan – циан (оттенок голубого), Magenta – пурпурный, Yellow – желтый, blacK – черный. Сложные цвета образуются смешением цветов CMYK. В последнее время к базовой схеме добавляют 2-4 цвета для повышения правильности цветопередачи.

Основные достоинства струйных принтеров:

- высокое качество печати для принтеров СЃ большим количеством сопел СЃ разрешением РґРѕ 720 ´ 1440 dpi; возможна печать фотографий;

- высокая скорость печати – до 10 страниц в минуту;

- бесшумность работы.

Основные недостатки струйных принтеров:

- использование хорошей бумаги, чтобы не растекались чернила;

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

- высокая стоимость расходных материалов, в частности, картриджей с чернилами.

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

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

Достоинства лазерных принтеров:

- высокая скорость печати – от 10 до 40 и выше страниц в минуту;

- скорость печати не зависит от разрешения;

- высокое качество печати до 2880 dpi;

- нетребовательность к качеству бумаги;

- низкая себестоимость копии (на втором месте после матричных принтеров);

- бесшумность.

Недостатки лазерных принтеров:

- высокая цена принтеров, особенно цветных;

- невысокое качество цветных изображений, напечатанных на цветных лазерных принтерах;

- высокое потребление электроэнергии.

Сканеры

Сканер – это устройство для ввода в ЭВМ информации с бумаги, слайдов или фотопленки.

Различают планшетные и ручные сканеры.

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

Применяются два типа сенсоров – CCD (Charge-Coupled Device) и CIS (Contact Image Sensor).

В ССD-сканерах используется система зеркал, установленная в специальной каретке. Зеркала передают отраженный от оригинала свет на параллельные линейки светочувствительных элементов (CCD-матрица). Каждая линейка принимает информацию о своем цвете – красном (Red), зеленом (Green) и синем (Blue).

В CIS-сканерах светочувствительный элемент находится в непосредственной близости от сканируемого документа, и система зеркал не применяется. Поэтому CIS-сканеры компактнее CCD-сканеров, однако глубина резкости и качество изображения уступает последним.

В сканирующем сенсоре уровни освещенности преобразуются в уровни напряжения и формируется аналоговый сигнал. Затем, после коррекции и обработки, аналоговый сигнал преобразуется в цифровой аналого-цифровым преобразователем (АЦП). Цифровой сигнал поступает в ЭВМ, где данные, соответствующие изображению оригинала обрабатываются и преобразовываются под управлением драйвера сканера.

Скорость сканирования страницы формата A4 составляет 5-15 секунд.

В отличие от планшетного, пользователь сам двигает сканирующую головку ручного сканера по оригиналу. Ручные сканеры применяются в магазинах для считывания скан-кодов товаров.

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

Сетевой адаптер

Для доступа ЭВМ к локальной сети используется специальная плата – сетевой адаптер, которая выступает в качестве физического соединения ЭВМ и канала связи. Сетевой адаптер выполняет следующие функции:

- подготовку данных, поступающих от ЭВМ, к передаче по каналу связи;

- передачу данных по каналу связи;

- прием данных из канала связи и перевод их в форму, понятную ЭВМ.

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

Модем

Модем – это устройство, предназначенное для подсоединения ЭВМ к обычной телефонной линии. Название происходит от сокращения двух слов – МОдуляция и ДЕМодуляция.

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

Модуляция колебаний – это изменение амплитуды, частоты или фазы колебаний по определённому закону. Различают амплитудную модуляцию (рис. 8.4, в), частотную модуляцию (рис. 8.4, г) и фазовую модуляцию (рис. 8.4, д).

Рис. 8.4. Виды модуляции

Модемы передают данные по обычным телефонным каналам со скоростью от 300 до 56 000 бит в секунду. Кроме того, современные модемы осуществляют сжатие данных перед отправлением, что сокращает время передачи данных.

По конструктивному исполнению модемы бывают трех видов:

1) встроенные модемы интегрированы в материнскую плату;

2) внутренние модемы вставляются в системный блок ЭВМ в один из слотов расширения материнской платы;

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

По аппаратной реализации модемы бывают двух типов.

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

2. Аппаратные (hardware) модемы реализуют все процедуры передачи и приема средствами самого модема. Поэтому такие модемы несколько дороже, но более эффективны при работе со старыми телефонными линиями.

Факс-модемы позволяют отправлять и принимать факсимильные сообщения (факсы) и поддерживают возможность телефонного разговора через факс-модем.

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

ADSL-модемы позволяют передавать данные, используя телефонные линии. При этом остается возможность говорить параллельно по телефону. ADSL-модемы позволяют осуществлять передачу данных на скорости до 1 Мбит/с, а прием данных – до 7 Мбит/с.

Каждый сотовый телефон (за исключением некоторых дешевых моделей) содержит модем для передачи данных в сетях сотовой связи. Также такие модемы выпускаются отдельными устройствами, подключаемые к порту USB.

Таким образом, основными характеристиками модемов являются:

1) скорость передачи;

2) конструктивное исполнение: внутренний, внешний, встроенный;

3) способ подключения к ЭВМ в случае внутреннего и внешнего конструктивного исполнения: слот PCI, порт PCMCIA, порт USB;

4) сеть или технология, по которой модем осуществляет передачу.

Глава 9. ОСНОВЫ АЛГОРИТМИЗАЦИИ

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

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

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

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

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

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

2. Исполнитель может выполнить алгоритм, если он ему понятен, то есть записан на понятном ему языке и содержит предписания, которые исполнитель может выполнить. Набор действий, которые могут быть выполнены исполнителем, называется системой команд исполнителя. Алгоритм не должен содержать описания действий, не входящих в систему команд исполнителя, то есть своей структурой команд и формой записи алгоритм должен быть ориентирован на конкретного исполнителя.

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

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

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

В математике известны вычислительные процедуры алгоритмического характера, не обладающие свойством конечности. Например, процедура вычисления числа p. Однако, если мы введем условие завершения вида «закончить после получения n десятичных знаков числа p», то получим алгоритм вычисления n десятичных знаков числа p. На этом принципе построены многие вычислительные алгоритмы.

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

Алгоритмическая система

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

1) множеством входных объектов или исходных данных, подлежащих обработке алгоритмами данной системы;

2) множеством выходных объектов или результатов выполнения алгоритмов данной системы;

3) системой команд исполнителя, то есть набором тех действий, которые может выполнять исполнитель, и которые мы можем описывать в алгоритмах, что собственно является ориентацией алгоритмической системы на конкретного исполнителя;

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

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

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

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

Алгоритмизация

Алгоритмизация – процесс разработки и описания алгоритма решения какой-либо задачи.

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

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

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

1) разложении всего вычислительного процесса на отдельные шаги – возможные составные части алгоритма, что определяется внутренней логикой самого процесса и системой команд исполнителя;

2) установлении взаимосвязей между отдельными шагами алгоритма и порядка их следования, приводящего от известных исходных данных к искомому результату;

3) полном и точном описании содержания каждого шага алгоритма на языке выбранной алгоритмической системы;

4) проверке составленного алгоритма на предмет, действительно ли он реализует выбранный метод и приводит к искомому результату.

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

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

1) множество допустимых исходных данных одного из них является множеством допустимых исходных данных и другого; из применимости одного алгоритма к каким-либо исходным данным следует применимость и другого алгоритма к этим данным;

2) применение этих алгоритмов к одним и тем же исходным данным дает одинаковые результаты.

Приведем пример двух эквивалентных алгоритмов. Пусть нам надо подсчитать общую сумму чисел, приведенных в табл. 9.1.

Таблица 9.1. Целые числа

Эквивалентными будут алгоритмы подсчета общей суммы «по строкам»: 5 + 1 + 3 + 8 + 10 + 9 + 6 + 1 + 5 + 10 + 1 + 1 = 60 - и «по столбцам»: 5 + 10 + 5 + 1 + 9 + 10 + 3 + 6 + 1 + 8 + 1 + 1 = 60. Заметим, что для данной таблицы считать проще по столбцам.

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

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

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

К настоящему времени в информатике сложились вполне определенные традиции в представлении алгоритмов.

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

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

Сѓ := Рђ

(читается: «у присвоить значение А»), где у – переменная; А – некоторое выражение/формула. Следует сначала выполнить все действия, предусмотренные формулой А, а затем полученный результат сохранить в качестве значения переменной у. Выражение А в частном случае может быть переменной или числом. Например,

x := sin a – присвоить переменной х значение синуса;

y := x – присвоить переменной у значение переменной x;

z := 5.7 – считать значением переменной z число 5,7;

k := k + 1 – значение переменной k увеличить на единицу.

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

Пример 9.1. Составим алгоритм вычисления коэффициентов приведенного квадратного уравнения x² + px + q = 0, РєРѕСЂРЅРё которого x₁, x₂ известны. Коэффициенты такого уравнения определяются РїРѕ формулам:

p = –(x₁+x₂),

q = x₁x₂.

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

Начало.

1. Ввести x₁, x₂.

2. p = –(x₁+x₂).

3. q = x₁x₂.

4. Вывести p, q.

Конец. □

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

Пример 9.2. Составим алгоритм определения максимального числа из трех чисел: z = max (a, b, c).

Решение задачи на ЭВМ можно получить, действуя следующим образом. Сначала найдем наибольшее из двух чисел, например, сравнив между собой a и b. Предположим, что исполнитель может выполнить операцию сравнения «больше». Найденное наибольшее число сохраним, как значение переменной z. Далее сравним значение переменной z с оставшимся числом c. Если с больше z, то присвоим z новое значение – значение с, в противном случае, значение z останется прежним. В результате переменная z будет равна наибольшему из a, b, c и будет являться искомым результатом.

Изложенные рассуждения можно представить в виде следующей словесной записи алгоритма:

Начало.

1. Ввести a, b, c.

2. Если a > b, то z := a,

иначе z := b.

3. Если c > z, то z := c.

4. Вывести z

Конец.

РҐРѕРґ выполнения алгоритма зависит РѕС‚ результатов проверки условий Р° > b Рё c > z. Если для введенных значений a, b действительно a > b, то выполняется операция z := a; если нет, то выполняется z := b. Таким образом, РІ зависимости РѕС‚ результата проверки условия a > b требуется выполнить различные действия. Р’ алгоритме РЅР° этом шаге предусмотрены РѕР±Р° возможных направления дальнейших вычислений. РџСЂРё проверке условия c > z операция z := c может выполняться, если действительно c > z, или РЅРµ выполняться, РІ противном случае. □

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

Пример 9.3. Составим алгоритм определения остатка РѕС‚ деления РґРІСѓС… целых неотрицательных чисел Рђ Рё Р’, РіРґРµ Р’ ¹ 0. Рассматривая деление как многократное вычитание делителя Р’ РёР· делимого Рђ, получим алгоритм, состоящий РёР· следующих шагов:

Начало.

1. Ввести A, B.

2. Если A < B, то перейти к шагу 5,

иначе перейти к шагу 3.

3. A := A – B.

4. Перейти к шагу 2.

5. РћРЎРў := A.

6. Вывести ОСТ.

Конец.

Шаги 2, 3, 4 записаны в алгоритме один раз, а могут выполняться многократно. Многократно повторяемые участки вычислений образуют так называемый цикл. Вычислительный процесс, содержащий многократные вычисления по одним и тем же математическим зависимостям, но для различных значений входящих в них переменных, называется циклическим. Переменные, изменяющиеся в цикле, называются переменными цикла, а действия, повторяемые в цикле, – телом цикла. Количество повторений цикла определяется значениями переменных, входящих в условие его окончания.

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