5. Алгоритм и примеры задач, решаемых с помощью алгоритмов

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

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

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

Вход: последовательность из N чисел ( ).

Выход: перестановка входной последовательности для получения из ее элементов новой последовательности ( ) такой, что для ее членов выполняется соотношение .

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

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

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

Практическое применение алгоритмов чрезвычайно широко. Приведем два примера.

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

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

2. Адресация и распределение памяти

1. Адресные пространства и модели оперативной памяти

Синтаксическая конструкция, с помощью которой обеспечивается доступ к определенному объекту (переменной, полю записи, массиву или его элементу, файлу), называется неявным адресом (implied address). Примеры неявных адресов дают следующие конструкции: Point^.Name, arrA[4], intValue, D:\DelProj\Table.xls. Используя неявный адрес, программист или пользователь предполагает, что адресуемый объект хранится в некотором участке памяти. Доступ к этому участку со стороны программы осуществляется по логическому адресу (logical address), который идентифицирует объект в виртуальной памяти. Логический адрес преобразуются в реальный физический адрес (physical address) ячейки оперативной памяти или порта.

Под адресным пространством компьютера понимается множество адресов памяти. Адресное пространство, понимаемое как множество адресов, доступных программе, еще называют виртуальным адресным пространством, а элемент этого пространства – виртуальным адресом. Определение «виртуальный», относящееся к техническим средствам или данным, указывает на то, что некоторый элемент представляется прикладному программисту существующим, тогда как фактически в представляемом виде он отсутствует. Например, при запуске приложения современная 32-разрядная операционная система, работая в так называемом защищенном режиме, представляет ему для кода и данных блок памяти размером 4 Гбайт. Понятно, что далеко не каждый пользователь может выделить 4 Гбайт ОЗУ под одно приложение. Фактически предоставляется пространство логических адресов, по которым, теоретически может храниться до 4 Гбайт информации. Это и есть виртуальное пространство. Компьютер незаметно для программиста компенсирует недостаток физической памяти, используя специальный страничный механизм, организующий обмен блоков данных или программ между оперативной и внешней памятью.

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

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

Микропроцессор аппаратно поддерживает две модели оперативной памяти:

• сегментированная модель, в которой программе выделяются непрерывные области памяти, называемые сегментами, а сама программа может обращаться только к информации, которая находится в этих сегментах;

• страничная модель, которую можно рассматривать как надстройку над сегментированной моделью. Основное применение этой модели связано с организацией виртуальной памяти, что позволяет операционной системе использовать для работы программ пространство памяти большее, чем объем физической памяти. Для микропроцессоров Pentium размер доступной виртуальной памяти может достигать 4 Тбайт (терабайт – 2⁴⁰ байт).

Особенности использования и реализации этих моделей зависят от режима работы микропроцессора:

• режим реальных адресов, или просто реальный режим,

• защищенный режим.