Алгоритм. Свойства алгоритма. Способы описания алгоритма. Примеры.

Алгори́тм, от имени учёного аль-Хорезми — точный набор инструкций, описывающих порядок действий исполнителя для достижения результата решения задачи за конечное время. В старой трактовке вместо слова «порядок» использовалось слово «последовательность», но по мере развития параллельности в работе компьютеров слово «последовательность» стали заменять более общим словом «порядок». Это связано с тем, что работа каких-то инструкций алгоритма может быть зависима от других инструкций или результатов их работы. Таким образом, некоторые инструкции должны выполняться строго после завершения работы инструкции, от которых они зависят. Независимые инструкции или инструкции, ставшие независимыми из-за завершения работы инструкций, от которых они зависят, могут выполняться в произвольном порядке, параллельно или одновременно, если это позволяют используемые процессор и операционная система.

Для углубления понятия алгоритма выделим и рас­кроем его основные свойства, вытекающие из его опре­деления:

1. Дискретность алгоритма. Свойство алгоритма, озна­чающее, что процесс решения задачи, определяемый алгоритмом, разделен на отдельные элементарные действия (шаги) и, соответственно, алгоритм представ­ляет последовательность указаний, команд, определя­ющих порядок выполнения шагов процесса. Дискретность алгоритма – пошаговое выполнение алгоритма.

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

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

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

К основным способам описания алгоритмов можно отнести следующие:

1. Словесно-формульное описание алгоритма, т. е. описание алгоритма с помощью слов и формул. Это на­иболее простой способ. Для его понимания достаточно рассмотреть пример, приведенный ниже. Кстати, кули­нарный рецепт — пример такого описания алгоритма.

Задача 4.1.

Составить алгоритм начисления зарплаты согласно следующему правилу: если стаж работы сотрудника менее 5 лет, то зарпла­та 130 тыс. руб., при стаже работы от 5 до 15 лет — 180 тыс. руб., при стаже свыше 15 лет зарплата по­вышается с каждым годом на 10 тыс. руб.

Сформулируем задачу в математическом виде: вычис­лить

где: ZP — зарплата; ST — стаж работы.

Словесно-формульное описание алгоритма решения задачи 4.1:

1. Ввести ST, перейти к п. 2.

2. Если ST<5, то 2Р:=130, перейти к п. 4, иначе — перейти к п. 3.

3. Если STd15, то ZP:=180, перейти к п. 4, иначе ZP:=180+(ST-15)10, перейти к п. 4.

4. Вывести (отпечатать) значение ZP, перейти к п. 5.

5. Вычисления прекратить.

Алгоритм, очевидно, не нуждается в пояснении, по­скольку форма записи его очень естественна.

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

Операция присваивания изображается прямоугольни­ком

Операции Ввод и Вывод изображаются параллело­граммом

Каждый из трех указанных блоков имеет один вход и один выход.

Операция Условный переход изображается ромбом; блок имеет два выхода — Да и Нет,

Если условие выполняется — выходим из блока по выходу Да, если не выполняется — по выходу Нет.

Начало процесса решения задачи обозначается бло­ком Начало.

Завершение процесса решения задачи обозначается блоком Останов.

3. Описание алгоритма на ал­горитмическом языке (алгоязыке).

5. Аппаратно – зависимые компоненты в ОС.

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

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

- средства поддержки привилегированного режима;

- средства трансляции адресов;

- средства переключения процессов;

- система прерываний;

- системный таймер;

- средства защиты областей памяти.

Средства поддержки привилегированного режима обычно основаны на системном регистре процессора, часто называемом “ словом состояния ” машины или процессора. Этот регистр содержит некоторые признаки, определяющие режимы работы процессора, в том числе и признак текущего режима привилегий. Смена режима привилегий осуществляется за счёт изменения слова состояния машины в результате прерывания или выполнения привилегированной команды. Число уровней привилегий может быть разным у разных типов процессоров, однако, наиболее часто используется либо два уровня (ядро–пользователь), либо четыре (например, ядро–супервизор–выполнение–пользователь у платформы VAX, или 0–1–2–3 у процессоров Intel x86/Pentium). В обязанности средств поддержки привилегированного режима входит проверка допустимости выполнения активной программой инструкций процессора при текущем уровне привилегированности.

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

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

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

Системный таймер, часто реализуемый в виде быстродействующего регистра-счетчика, необходим ОС для выдержки интервалов времени. В регистр таймера программно загружается значение требуемого интервала в условных единицах, из которого затем автоматически с определенной частотой начинает вычитаться по единице. Частота “тиков” таймера, как правило, тесно связана с частотой тактового генератора процессора. Заметим, что не следует путать таймер ни с тактовым генератором, вырабатывающем сигналы по синхронизации всех операций в компьютере, ни с системными часами – работающей на батареях электронной схеме, ведущие независимый отсчет времени и календарной даты. При достижении нулевого значения счетчика таймер инициирует прерывание, которое обрабатывается соответствующей процедурой ОС. Прерывания от системного таймера используются ОС в первую очередь для слежения за тем, как отдельные процессы расходуют время процессора. Например, в системе разделения времени при обработке очередного прерывания от таймера планировщик процессов может принудительно передать управление другому процессу, если данный процесс исчерпал выделенный ему квант времени.

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

6. Архитектура Windows NT/2000.