Билет №13. 1. Понятие алгоритма. Свойства алгоритма

1. Понятие алгоритма. Свойства алгоритма. Воз­можность автоматизации деятельности человека. При­меры.

2. Операции с файлами (переименование, копирова­ние, удаление, поиск) в среде операционной системы.

1. Понятие алгоритма. Свойства алгоритма. Воз­можность автоматизации деятельности человека. При­меры.

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

Термин имеет интересное историческое происхожде­ние. В IX веке великий узбекский математик Аль Хорезми разработал правила арифметических действий над десятичными числами. Совокупность этих правил в Ев­ропе стали называть " алгоризм". Впоследствии слово трансформировалось до известного нам сейчас вида и, кроме того, расширило свое значение: алгоритмом ста­ли называть любую последовательность действий (не только арифметических), которая приводит к решению той или иной задачи. Можно сказать, что понятие выш­ло за рамки математики и стало применяться в самых различных областях.

Человек, едва родившись, уже сталкивается с алго­ритмами типа " в бутылочку с кефиром влить пастери­зованный охлажденный отвар из риса...". Большин­ство женщин и некоторые мужчины пользуются по­варенной книгой — сборником всевозможных описа­ний последовательности действий, направленных на получение вкусных блюд. Еще более четкие указания по изготовлению продукции содержит обыкновенный аптечный рецепт — в этом случае от точности выпол­нения алгоритма может порой зависеть жизнь паци­ента. Определенным алгоритмом действий " руковод­ствуется" стиральная машина или микроволновая печь. Любому шахматисту известен способ, как поставить мат одинокому королю противника с помощью ладьи и своего короля. Школьный курс математики также предлагает большое разнообразие алгоритмов: умно­жение " столбиком" и деление " уголком", приведение к общему знаменателю...

А теперь пример из художественной литературы. Вот как описывает известная писательница Андрэ Нортон в своей книге " Саргассы в космосе" алгоритм движения по гигантскому лабиринту. Главный герой Дейн, тайком наблюдая за главарем галактических гангстеров Ричем, быстро узнает этот алгоритм.

" Он дал Ричу отойти, а затем двинулся сле­дом. Рич шагал уверенно, сразу было видно, что он отлично знает дорогу. Еще до того, как вдали в сером сумраке засветился луч фона­рика Муры, Дейн уже знал формулу пути к выходу из лабиринта. Два поворота направо, один налево, еще три направо и пропустить один проход. И снова: два поворота направо, один налево и так далее до самого выхода. Рич на глазах у Дейна проделал этот цикл четыре раза подряд..."

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

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

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

Исходные данные		Алгоритм		Искомый результат

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

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