Алгоритмы, программы, языки - общие понятия

С функциональной точки зрения, компьютер — это цифровое устройство, предназначенное для хранения, автоматизированной обработки, воспроизведения, приёма и передачи информации.

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

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

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

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

Алгоритм — это детализированное пошаговое предписание, дающее общий метод решения определённого (обычно, бесконечного) класса однотипных задач.

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

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

Таким образом, любая запись алгоритма явно или неявно ориентирована на определённый тип исполнителя, “интеллекта и умений" которого достаточно для однозначной трактовки и исполнения этого алгоритма.

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

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

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

Язык, на котором записывается алгоритм, называется алгоритмическим языком (АЯ).

В роли алгоритмических языков могут выступать как естественные (русский, французский, итальянский и др.), так и искусственные, т.е.  специально созданные для записи алгоритмов языки (такие, например, как Pascal, С++, язык блок-схем).

В первом случае, алгоритмы, почти всегда, ориентированы на исполнение человеком (такова, например, инструкция для сборки мебели), а во втором – чаще всего могут интерпретироваться исполнителем - автоматом.

Если роль исполнителя берёт на себя автоматическое устройство, то соответствующий алгоритм называется программой, а сам исполнитель — процессором. Алгоритмический язык при этом становится языком записи программ и называется, поэтому,  языком программирования (ЯП).

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

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

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

Алгоритм НОД (M,N):

Шаг_1. Взять два исходных  числа,  обозначить их  M и N;  перейти к шагу 2 .

Шаг_2. Сравнить обрабатываемые числа: если M=N, то взять в качестве результата M  и остановиться,  иначе, перейти к шагу 3.

Шаг_3. Если M>N, то  переобозначить  через M разность чисел M-N, иначе  переобозначить через N разность N-M;   перейти к шагу 2.

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

Момент времени

Номер шага

Значение  M

Значение  N

Действия исполнителя

1

1

24

18

Взяли 24 и 18, обозначили их M и  N

2

2

24

18

Сравнили: 24 > 18; перешли к шагу_3

3

3

6

18

24 >18; переобозначили через M разность 24 -18

4

2

6

18

Сравнили: 6 < 18; перешли к шагу_3

5

3

6

12

6 <18; переобозначили через N разность 18 - 6

6

2

6

12

Сравнили: 6 < 12; перешли к шагу_3

7

3

6

6

6 <12; переобозначили через N разность 12 - 6

8

2

6

6

Сравнили: 6 = 6;  результат M = 6;  остановились

Окончательно получили M=6.  Значит,  НОД(24, 18) = 6.

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

 

 Основные свойства алгоритмов

  1.  Дискретность. Алгоритм строится как упорядоченная последовательность явно различимых (дискретных)  шагов, которые вычислитель выполняет в  дискретные (т.е. также явно различимые: 1-й, 2-й  и т.д.) моменты времени. Так, рассматриваемый нами алгоритм представляет собой инструкцию, состоящую всего из трёх шагов, в то время, как на соответствующий алгоритмический процесс для заданной пары  чисел (24 и 18) тратится, в общей сложности, 8 явно различимых моментов (дискретов) времени. Некоторые шаги, при этом,  выполняются многократно.
  2. Результативность. Алгоритм  должен быть составлен так,  что соответствующий ему алгоритмический процесс, если его начать с допустимых исходных данных,  в какой-то момент обязательно завершится. То, что алгоритмический процесс выполнения алгоритма Евклида при любом выборе исходной пары натуральных чисел  всегда завершается – доказуемый математический факт (попробуйте убедиться  в этом самостоятельно!).
  3. Определённость. Алгоритм должен представлять собой совершенно точное, на любом этапе вычислений однозначно и явно определяющее действия предполагаемого исполнителя предписание. Отметим, что содержащая некоторую неопределённость фраза типа “взять в качестве результата M или  N  и  остановиться ”, хотя с точки зрения здравого смысла и кажется верной, формально и по существу, противоречила бы данному свойству (действительно, так что же конкретно, M или N, считать результатом?). Поэтому в приведённом выше примере алгоритма, для завершения алгоритмического процесса использована несколько иная и уже вполне определённая  редакция этой фразы.
  4. Массовость. Алгоритм направлен на решение не одной частной задачи, а целого класса (обычно, бесконечного)  однотипных задач. В нашем примере, каждая задача состоит в нахождении наибольшего общего делителя для любой конкретной пары натуральных чисел. В том, что таких пар бесконечное множество и для каждой пары алгоритм даёт ожидаемый результат, как раз и проявляется свойство массовости алгоритма Евклида.
  5. Конечность. Алгоритм, как текст, как описание некоторого стандартного для решаемого класса задач способа действий исполнителя,  всегда должен представлять собой конечную инструкцию, т.е. занимать ограниченное пространство на соответствующем носителе информации (на листе бумаги, на магнитном диске и т.п.). Последнее свойство не следует путать со свойством результативности, которое требует конечности алгоритмического процесса, т.е. по существу, представляет собой ограничение во времени, а не в пространстве.

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

4.69231
Your rating: Нет Average: 4.7 (26 votes)