Макинтош и образование:Информатика и ИТ:Пособие:Алгоритм и программа

© М.Е. Крекин, 1999, 2002

Глава 1
Алгоритм и программа

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

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

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

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

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

Какими свойствами должен обладать алгоритм? Перечислим их:

• дискретность² -- алгоритм делится на отдельные элементарные шаги;
• определенность -- каждая команда однозначно определяет действие исполнителя;
• конечность(результативность) -- алгоритм должен завершаться за конечное число шагов.

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

С определенностью непосредственно связана существенная особенность, о которой нельзя забывать: исполнитель выполняет алгоритм формально³, абсолютно не задумываясь над смыслом производимых действий. Поэтому не стоит обижаться на компьютер, "не догадавшийся", что вы подразумевали, -- он честно делает то, что вы написали.

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

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

Но процессор не понимает команд языков высокого уровня, поэтому их предварительно нужно "перевести". Для этого служат особые программы -- трансляторы⁵.

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

Контрольные вопросы

1. Что такое алгоритм? Какими свойствами он обладает? Приведи примеры алгоритмов.
2. Что значит "алгоритм исполняется формально"?
3. Что такое программа? Язык программирования?
4. Для чего служат трансляторы?

Примечания

1. Algorithmi (лат.) -- искаженное имя математика IX века аль-Хорезми, предложившего способ выполнения арифметических вычислений с многозначными числами.
   Заметим, что подход к определению алгоритма как последовательности операций -- не единственно возможный. Кроме такого -- процедурного (императивного), возможен и функциональный подход, когда алгоритм рассматривается как система функций.
2. Discrete (англ.) -- состоящий из отдельных частей
3. Formalis (лат.) -- строго по установленным правилам
4. Programma (греч.) -- распоряжение
5. Translator (англ.) -- переводчик
6. Язык Лого (Logo, от греч. Logos -- слово, мысль) разработан в 1972 г. Сеймуром Пейпертом (Массачусетский Технологический институт, США). "Прародителем" его был наиболее известный из языков функционального программирования -- Лисп, однако, в процессе развития Лого приобрел ряд особенностей, позволяющих использовать при работе с ним как функциональный, так и процедурный подходы.