Что будет в результате выполнения алгоритма

2. Определение результата выполнения алгоритма по его блок-схеме, записи на естественном языке или записи на языке программирования.

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

Предлагается задача: в приведенном алгоритме при к = 4 каким будет выведенное значение Р?

Это задание можно сформулировать как тестовое, где нужно выбрать правильный ответ из нескольких пред­ложенных и обосновать его.

В нашем случае варианты ответов (правильный выде­лен жирным шрифтом).

1) 1; 3) 12; 5) 1944.

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

В нашем примере задача формулируется так: найти произведение первых k натуральных чисел, крат­ных 3; Р = 1944.

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

Язык Бейсик

input «Введите натуральное число: «, k

print «Результат: «, р

Конец Билет №5

1. Операционная система компьютера (назначение, состав, способ организации диалога с пользователем). Загрузка компьютера.

2. Создание, преобразование, сохранение, распе­чатка рисунка в среде графического редактора.

1. Операционная система компьютера (назначение, состав, способ организации диалога с пользователем). Загрузка компьютера.

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

Примечание. Ресурсами компьютера являются процессор­ное время, память всех видов, устройства ввода/вывода, прог­раммы и данные.

Роль операционной системы можно наглядно пред­ставить себе с помощью следующего рисунка. В центре его изображен собственно компьютер, т.е. все то обору­дование, которое стоит на вашем столе и которое мож­но непосредственно «потрогать руками» (в информати­ке эта часть часто называется hardware). Внешней обо­лочкой является разнообразное программное обеспече­ние (software), позволяющее многочисленным пользо­вателям решать свои прикладные задачи из всех облас­тей человеческой деятельности. ОС организует их со­вместную работу и служит своеобразным программным расширением управляющего устройства компьютера. Вы можете спросить: а так ли нужен еще один дополни­тельный слой? Очень нужен, учитывая тот факт, что не­возможно заложить в центральный блок информацию обо всех устройствах, которые к нему могут быть под­соединены. И, кроме того, новое устройство может быть изобретено уже после изготовления компьютера! Отсю­да очевидно, что загружаемая (а следовательно, изменя­емая) программная часть, обеспечивающая работу ком­пьютерное аппаратуры, совершенно необходима.

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

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

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

• Организация согласованного выполнения всех про­цессов в компьютере. Планирование работ, распределе­ние ресурсов.

• Организация обмена с внешними устройствами. Хра­нение информации и обеспечение доступа к ней, предо­ставление справок.

• Запуск и контроль прохождения задач пользователя.

• Реакция на ошибки и аварийные ситуации. Конт­роль за нормальным функционированием оборудования.

• Обеспечение возможности доступа к стандартным системным средствам (программам, драйверам, инфор­мации о конфигурации и т.п.).

• Обеспечение общения с пользователем.

• Сохранение конфиденциальности информации в многопользовательских системах.

Первые операционные системы (СР/М, МS-DOS,Unix ) вели диалог с пользователем на экране текстового дисплея. Это был в полном смысле слова диалог, в ходе которого человек и компьютер по очереди обменива­лись сообщениями: человек вводил очередную команду, а компьютер, проверив ее, либо выполнял, либо отвер­гал по причине ошибки. Такие системы в литературе принято называть ОС с интерфейсом командной строки.

Пользователь последовательно набрал две команды вывода каталога дисков, причем первую компьютер вы­полнил нормально, и на экране появился требуемый спи­сок файлов, а вторую «отказался» делать, поскольку опе­ратор ошибочно указал имя несуществующего диска. Очевидно, что подобный способ общения не очень удо­бен для человека, поскольку требует постоянно держать в голове жесткий синтаксис всех допустимых команд и очень внимательно их вводить. Поэтому почти сразу же стали появляться сервисные системные программы, тем или иным способом облегчающие работу с ОС. Наиболее яр­ким примером таких программ-оболочек может служить широко известный Norton Commander, который был настолько распространен, что многие пользователи ис­кренне считали его частью операционной системы.

Развитие графических возможностей дисплеев привело к коренному изменению принципов взаимодействия че­ловека и компьютера. Командная строка была безвоз­вратно вытеснена графическим интерфейсом, когда объекты манипуляций в ОС изображаются в виде не­больших рисунков, а необходимые действия тем или иным образом выбираются из предлагаемого машиной списка — так называемого меню. При подобном методе диалога набор текста полностью отсутствует и вполне достаточно всего нескольких клавиш. Существенным до­полнением к графическому способу ведения диалога яви­лось появление нового устройства ввода информации в компьютер — манипулятора «мышь», без которого сей­час просто невозможно представить современный ком­пьютер. Примерами операционной системы с графиче­ским интерфейсом служат довольно похожие ОС для компьютеров «Масintosh» (не имеет специального на­звания и обозначается просто System с номером версии) и «IВМ РС» — 0S/2 и Windows. Последняя система в нашей стране распространена необычайно широко.

Перейдем теперь к описанию состава операционных систем. Он, конечно, может быть довольно разным для различных систем. Так, для «классических» ОС с ко­мандной строкой довольно четко выделяются три ос­новные части:

• машинно-зависимая часть для работы с конкретны­ми видами оборудования;

• базовая часть (ядро), не зависящая от конкретных деталей устройств: она работает с абстрактными логи­ческими устройствами и при необходимости вызывает функции из предыдущей части; отвечает за наиболее общие принципы устройства ОС;

• программа ведения диалога с пользователем (ее ча­сто называют командным процессором).

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

Состав операционных систем с графическим интер­фейсом типа Windows заметно шире, но в целом имеет похожее строение.

В момент включения компьютера в ОЗУ нет осмыслен­ной информации. Поэтому особый интерес представляет вопрос о том, как операционная система загружается. Процесс этот в заметно упрощенном виде выглядит так. При включении компьютера (или при нажатии кнопки сброса) счетчик процессора аппарате устанавливается на начальный адрес ПЗУ, и стартует выполнение программы начальной загрузки. Прежде всею ищется и тестируется установленное оборудование. Современные компьютеры в основном используют внешние устройства «plug and р1ау» (переводится — «включил и работай»), поэтому они спо­собны сообщить процессору свои основные характеристи­ки и условия работы. Опрос внешних устройств и провер­ка их работоспособности занимают достаточно длительное время, несмотря на высокое быстродействие компьютера. В случае если все оборудование функционирует нормаль­но, происходит переход к следующему этапу — поиску начального загрузчика операционной системы. Он может находиться на жестком диске, на дискете, на СD-RОМ и даже быть получен с помощью сетевой платы. Поэтому компьютер опрашивает перечисленные устройства по оче­реди, в определенном порядке, до тех пор, пока не обнаружит требуемую информацию (в скобках заметим, что порядок поиска при наличии достаточных навыков и зна­ний может быть легко изменен). Итак, загрузчик, пред­ставляющий собой не что иное, как программу дальней­шей загрузки, обнаружен и прочитан в память. Дальней­шие действия машины уже определяются тем, что введено извне. Поскольку начальный загрузчик очень мал, то он умеет очень немного — найти и прочесть первый файл ОС с фиксированным именем и передать ему управление. И только после этого будет загружена в ОЗУ остальная часть операционной системы и машина сможет, наконец, нор­мально общаться с пользователем.

Примечание. Несколько слов для тех, кого удивила слож­ность описанного процесса. Почему загрузка ОС такая много­ступенчатая • и почему, например, нельзя просто записать начальный загрузчик в то же самое ПЗУ? Технически это не представляет никакого труда, но все дело в том, что тогда мы сможем пользоваться только одной(!) операционной систе­мой, а именно той, загрузчик для которой жестко «зашили» в ПЗУ.

И в заключение еще одно дополнительное замеча­ние. Может быть, не стоит требовать этот материал с учеников, но рассказать об этом, по-моему, стоит. Все­гда ли существовала ОС и может ли компьютер рабо­тать без нее? Как ни странно, ответ на оба вопроса отрицательный. Операционная система существовала не всегда, а возникла на стыке второго и третьего по­колений.

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

Составление блок схем и решение задач

Определить результат выполнения алгоритма при определённых значениях исходных данных

Устанавливая рекомендуемое программное обеспечение вы соглашаетесь
с лицензионным соглашением Яндекс.Браузера и настольного ПО Яндекса .

Задачи на составление блок-схем алгоритмов

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

Дана блок-схема алгоритма

Определить результат выполнения алгоритма при определённых значениях исходных данных

Например, при x=16 и y=2

Дана блок-схема алгоритма

Определить результат выполнения алгоритма при определённых значениях исходных данных

Например, при x=-6 или x=0 или x=7

Дана блок-схема алгоритма

Определить результат выполнения алгоритма при определённых значениях исходных данных

Например, при n=15 или n=0 или n=-7

Дана блок-схема алгоритма

Определить результат выполнения алгоритма при определённых значениях исходных данных

Например, при A=7; B=8; C=9 или A=6; B=6; C=-10 или A=6; B=10; C=-10

Дана блок-схема алгоритма

Определить результат выполнения алгоритма при определённых значениях исходных данных

Например, при n=4 или n=1

Устанавливая рекомендуемое программное обеспечение вы соглашаетесь
с лицензионным соглашением Яндекс.Браузера и настольного ПО Яндекса .

• Сердинова Елена ВикторовнаНаписать 29270 30.12.2015

Номер материала: ДВ-298078

Устанавливая рекомендуемое программное обеспечение вы соглашаетесь
с лицензионным соглашением Яндекс.Браузера и настольного ПО Яндекса .

30.12.2015 394

29.12.2015 3550

29.12.2015 4901

29.12.2015 2121

29.12.2015 5373

29.12.2015 1378

29.12.2015 1004

Не нашли то что искали?

Вам будут интересны эти курсы:

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

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

Цель: выработать умение решать задачи на составление алгоритмов на языке блок – схем.

+ Презентация и самостоятельная работа

Скачать:

Вложение	Размер
_.doc	146 КБ
_.ppt	793 КБ
_2.doc	37.5 КБ

Предварительный просмотр:

Тема: Решение задач на составление разветвляющихся алгоритмов.

Цели: выработать умение решать задачи на составление алгоритмов на языке

Оборудование: карточки с заданиями, мультимедийная презентация.

1. Актуализация знаний.

Диктант. Учащиеся выполняют диктант, Решение задач (одновременно с

записывая ответы на листочках. диктантом). 2 ученика у доски.

1. Как обозначается блок означающий вычислительное действие (операцию присваивания)?

2. Как обозначается блок означающий ввод исходных данных, вывод результатов?

3. Разветвляющийся алгоритм – это алгоритм …

Ответ. … в котором в зависимости от истинности условия выполняется та или иная серия команд.

4. Как изображается в блок – схеме ветвление в полной форме?

5.Как оформляется в блок – схеме ветвление в неполной форме?

Теперь поменяйтесь листочками, проверьте, правильно ли ответили на вопрос ваш сосед и поставьте ему оценку (её определяет количество правильных ответов). (Ответы на слайдах).

Карточка №1. Функция y = f(х) задана графиком

Составьте блок-схему решения алгоритма.

Карточка №2. Составить блок – схему алгоритма вычисления значения

у = х + в, при 10 ≤ х ≤ 23;

х + а , при х > 23.

2. Решение задач.

Определить результат выполнения алгоритма по его блок – схеме при заданных значениях а и в (а = 2, в = 3). Значения занести в таблицу.

(На примере задания карточки №2).

10 23 ? нет у = 10 + 3 = 13

25 23 ? да у = 25 + 2 2

Составить блок – схему алгоритма решения задачи. Переменной к присвоить номер четверти плоскости в которой находится точка с координатами х и у (х ≠ 0, у ≠ 0).

Практикум. Игра «Ежиные тропы».

1. Составьте по шаблону блок – схему решения задачи (шаблоны раздать

2. Найдите и исправьте ошибки в приведённой блок – схеме. Определите

значения х и у в результате выполнения алгоритма по его блок – схеме при

заданных значениях а, в. Значения переменных, изменяющиеся в процессе

исполнения, занесите в таблицу.

1. Составьте по шаблону блок – схему решения задачи (шаблоны раздать

Заданы три числа – а, в, с. Известно, что два из них равны между собой, а третье отлично от них. Найдите, какое из чисел отлично от двух других.

Осуществить самопроверку (ответы на слайдах).

Ответы: I вариант

Приведите приведённую блок – схему в формульное описание (сведите все

действия в одну формулу, если это возможно).

5. Итог урока. Кроссворд.

Ответы. По горизонтали: 1. Программа. 4. Результат. 7. Ветвление. 8. Схема.

По вертикали: 2. Алгоритм. 3. Аргумент. 5. Условие. 6. Бейсик.

6. Сообщение оценок.

7. Домашнее задание. Составить блок-схему алгоритма решения

вывод «Выражение не имеет смысла»

Предварительный просмотр:

Подписи к слайдам:

Предварительный просмотр:

1. Составьте по шаблону блок – схему решения задачи у = .

1. Найдите и исправьте ошибки в приведённой блок – схеме. Определите значения х и у в результате выполнения алгоритма по его блок – схеме при заданных значениях а, в. Значения переменных, изменяющиеся в процессе исполнения, занесите в таблицу.

1. Составьте по шаблону блок – схему решения задачи.

Заданы три числа – а, в, с. Известно, что два из них равны между собой, а третье отлично

от них. Найдите, какое из чисел отлично от двух других.

2. Найдите и исправьте ошибки в приведённой блок – схеме. Определите значения х и у в

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

Значения переменных, изменяющиеся в процессе исполнения, занесите в таблицу.

По теме: методические разработки, презентации и конспекты

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

Цель урока: совершенствовать навыки составления пропорций по условию задачи, сформировать умение применять пропорции при решении задач, использовать условие и решение задачи для сохранения и укреплени.

Предлагаю план — конспект открытого урока, а также презентацию к нему. Презентация содержит иллюстративный материал к уроку математики в 5 классе по теме: "Решение задач путем составления уравнений". .

Алгоритм решения задач на составление уравнений в 5 классе.

Конспект и презентация к уроку в 9 классе по теме "Алгоритм решения квадратного уравнения".

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

Name already in use

OAP / articles / t1l1.md

• Go to file T
• Go to line L
• Copy path
• Copy permalink

0 contributors

Users who have contributed to this file

• Open with Desktop
• View raw
• Copy raw contents Copy raw contents

Copy raw contents

Copy raw contents

Основные понятия алгоритмизации

Работа по решению любой задачи с использованием компьютера делится на следующие этапы:

1. Постановка задачи.
2. Формализация задачи.
3. Построение алгоритма.
4. Составление программы на языке программирования.
5. Отладка и тестирование программы.
6. Использование программы.

Часто эту последовательность называют технологической цепочкой решения задачи. Непосредственно к программированию в этом списке относятся пункты 3, 4, 5.

На этапе постановки задачи должно быть четко сформулировано, что дано и что требуется найти. Здесь очень важно определить полный набор исходных данных, необходимых для получения решения.

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

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

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

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

• уметь строить алгоритмы;
• знать языки программирования;
• уметь работать в соответствующей системе программирования.

Одним из фундаментальных понятий в информатике является понятие алгоритма. Происхождение самого термина «алгоритм» связано с математикой. Это слово происходит от Algorithmi — латинского написания имени Мухаммеда альХорезми (787 — 850), выдающегося математика средневекового Востока. В XII в. был выполнен латинский перевод его математического трактата, из которого европейцы узнали о десятичной позиционной системе счисления и правилах арифметики многозначных чисел. Именно эти правила в то время называли алгоритмами. Сложение, вычитание, умножение столбиком, деление уголком многозначных чисел — вот первые алгоритмы в математике.

В наше время понятие алгоритма трактуется шире. Алгоритм — это последовательность команд управления каким-либо исполнителем.

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

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

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

Компьютер работает с величинами — различными информационными объектами: числами, символами, кодами и т.п. Поэтому алгоритмы, предназначенные для управления компьютером, принято называть алгоритмами работы с величинами.

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

Например, при решении квадратного уравнения ах 2 + Ьх + с = 0 исходными данными являются коэффициенты а, Ь, с; результатами — корни уравнения х1, х2; промежуточным данным — дискриминант уравнения D = b 2 — 4ас.

Для успешного освоения программирования необходимо усвоить следующее правило: всякая величина занимает свое определенное место в памяти ЭВМ (иногда говорят — ячейку памяти). Хотя термин «ячейка» с точки зрения архитектуры современных ЭВМ несколько устарел, однако в учебных целях его удобно использовать.

У всякой величины имеются три основных свойства: имя, значение и тип (на самом деле многие современные языки, такие как PHP или JS, обходятся без явного указания типа, интерпретируя тип переменной в зависимости от контекста операции). На уровне команд процессора величина идентифицируется при помощи адреса ячейки памяти, в которой она хранится. В алгоритмах и языках программирования величины делятся на константы и переменные. Константа — неизменная величина, и в алгоритме она представляется собственным значением, например: 15, 34.7, k, true и т.д. Переменные величины могут изменять свои значения в ходе выполнения программы и представляются символическими именами — идентификаторами, например: X, S2, cod15. Любая константа, как и переменная, занимает ячейку памяти, а значение этих величин определяется двоичным кодом в этой ячейке.

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

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

Типы констант определяются по контексту (т.е. по форме записи в тексте), а типы переменных устанавливаются в описаниях переменных (не во всех языках; Python, например, не имеет явного определения типа, тип переменной определяетя при первом присваивании).

Есть еще один вариант классификации данных — классификация по структуре. Данные делятся на простые и структурированные. Для простых величин (их еще называют скалярными) справедливо утверждение: одна величина — одно значение, для структурированных: одна величина — множество значений. К структурированным величинам относятся массивы, строки, множества и т.д.

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

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

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

Определенность (детерминнированность) — предполагает получение однозначного результата вычислительного процecca при заданных исходных данных. Благодаря этому свойству процесс выполнения алгоритма носит механический характер.

Результативность (конечность) — алгоритм должен приводить к решению задачи за конечное число шагов.

Формы записи алгоритмов

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

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

Пример: написать алгоритм «Одеться по погоде». Если на улице температура ниже 0, то необходимо надеть шубу, иначе – куртку.

Словесный способ записи алгоритма

Словесный способ записи алгоритмов представляет собой описание последовательных этапов обработки данных. Алгоритм задается в произвольном изложении на естественном языке.

Словесный способ не имеет широкого распространения, так как такие описания:

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

Графический способ записи алгоритмов

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

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

Название символа	Обозначение и пример заполнения	Пояснение
Процесс	Вычислительное действие или последовательность действий
Решение	Проверка условий
Модификация	Начало цикла
Предопределенный процесс	Вычисления по подпрограмме, стандартной подпрограмме
Ввод-вывод	Ввод-вывод в общем виде
Пуск-останов	Начало, конец алгоритма, вход и выход в подпрограмму
Документ	Вывод результатов на печать

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

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

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

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

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

Блок Пуск-останов используется для обозначения начала, конца, прерывания процесса обработки данных или выполнения программы.

Блок Документ предназначен для ввода-вывода данных, носителем которых служит бумага.

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

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

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

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

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

Программный способ записи алгоритмов

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

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

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

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

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

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

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

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

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

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

Общие принципы построения алгоритмов

При разработке алгоритма используют следующие основные принципы.

Принцип поэтапной детализации алгоритма (другое название — «проектирование сверху-вниз»). Этот принцип предполагает первоначальную разработку алгоритма в виде укрупненных блоков (разбиение задачи на подзадачи) и их постепенную детализацию.

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

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

Определение сложности работы алгоритмов

Существует несколько способов измерения сложности алгоритма. Программисты обычно сосредотачивают внимание на скорости алгоритма, но не менее важны и другие показатели – требования к объёму памяти, свободному месте на диске. Использование быстрого алгоритма не приведёт к ожидаемым результатам, если для его работы понадобится больше памяти, чем есть у компьютера.

Память или время

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

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

Из этой зависимости проистекает идея объёмно-временной сложности. При таком подходе алгоритм оценивается, как с точки зрении скорости выполнения, так и с точки зрения потреблённой памяти.

Мы будем уделять основное внимание временной сложности, но, тем не менее, обязательно будем оговаривать и объём потребляемой памяти.

При сравнении различных алгоритмов важно знать, как их сложность зависит от объёма входных данных. Допустим, при сортировке одним методом обработка тысячи чисел занимает 1 с., а обработка миллиона чисел – 10 с., при использовании другого алгоритма может потребоваться 2 с. и 5 с. соответственно. В таких условиях нельзя однозначно сказать, какой алгоритм лучше.

В общем случае сложность алгоритма можно оценить по порядку величины. Алгоритм имеет сложность O(f(n)) , если при увеличении размерности входных данных N, время выполнения алгоритма возрастает с той же скоростью, что и функция f(N) . Рассмотрим код, который для матрицы A[NxN] находит максимальный элемент в каждой строке.

В этом алгоритме переменная i меняется от 1 до N. При каждом изменении i, переменная j тоже меняется от 1 до N. Во время каждой из N итераций внешнего цикла, внутренний цикл тоже выполняется N раз. Общее количество итераций внутреннего цикла равно N*N. Это определяет сложность алгоритма O(N 2 ).

Оценивая порядок сложности алгоритма, необходимо использовать только ту часть, которая возрастает быстрее всего. Предположим, что рабочий цикл описывается выражением N 3 +N. В таком случае его сложность будет равна O(N 3 ). Рассмотрение быстро растущей части функции позволяет оценить поведение алгоритма при увеличении N. Например, при N=100, то разница между N 3 +N=1000100 и N=1000000 равна всего лишь 100, что составляет 0,01%.

При вычислении O можно не учитывать постоянные множители в выражениях. Алгоритм с рабочим шагом 3N 3 рассматривается, как O(N 3 ). Это делает зависимость отношения O(N) от изменения размера задачи более очевидной.

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

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

В качестве примера рассмотрим две процедуры: Slow со сложностью O(N 3 ) и Fast со сложностью O(N 2 ).

Если во внутренних циклах процедуры Fast происходит вызов процедуры Slow, то сложности процедур перемножаются. В данном случае сложность алгоритма составляет O(N 2 )*O(N 3 )=O(N 5 ).

Если же основная программа вызывает процедуры по очереди, то их сложности складываются:

Следующий фрагмент имеет именно такую сложность:

Сложность рекурсивных алгоритмов

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

Рассмотрим рекурсивную реализацию вычисления факториала:

Эта процедура выполняется N раз, таким образом, вычислительная сложность этого алгоритма равна O(N).

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

Рассмотрим такую процедуру:

Поскольку процедура вызывается дважды, можно было бы предположить, что её рабочий цикл будет равен O(2N)=O(N). Но на самом деле ситуация гораздо сложнее. Если внимательно исследовать этот алгоритм, то станет очевидно, что его сложность равна O(2 (N+1) -1)=O(2 N ).

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

Объёмная сложность рекурсивных алгоритмов

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

Средний и наихудший случай

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

Если искомый элемент находится в конце списка, то программе придётся выполнить N шагов. В таком случае сложность алгоритма составит O(N). В этом наихудшем случае время работы алгоритма будем максимальным.

С другой стороны, искомый элемент может находится в списке на первой позиции. Алгоритму придётся сделать всего один шаг. Такой случай называется наилучшим и его сложность можно оценить, как O(1).

Оба эти случая маловероятны. Нас больше всего интересует ожидаемый вариант. Если элемента списка изначально беспорядочно смешаны, то искомый элемент может оказаться в любом месте списка. В среднем потребуется сделать N/2 сравнений, чтобы найти требуемый элемент. Значит сложность этого алгоритма в среднем составляет O(N/2)=O(N).

В данном случае средняя и ожидаемая сложность совпадают, но для многих алгоритмов наихудший случай сильно отличается от ожидаемого. Например, алгоритм быстрой сортировки в наихудшем случае имеет сложность порядка O(N 2 ), в то время как ожидаемое поведение описывается оценкой O(N*log(N)), что много быстрее.

Общие функции оценки сложности

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

1. C – константа (время выполнения алгоритма не зависит от входных параметров, линейные алгоритмы)
2. log(log(N))
3. log(N) — (поиск в сортированном массиве)
4. N C , 0<C<1
5. N — линейная сложность (поиск в не сортированном массиве)
6. N*log(N)
7. N C , C>1
8. C N , C>1
9. N!

Если мы хотим оценить сложность алгоритма, уравнение сложности которого содержит несколько этих функций, то уравнение можно сократить до функции, расположенной ниже в таблице. Например, O(log(N)+N!)=O(N!).

Если алгоритм вызывается редко и для небольших объёмов данных, то приемлемой можно считать сложность O(N 2 ), если же алгоритм работает в реальном времени, то не всегда достаточно производительности O(N).

Обычно алгоритмы со сложностью N*log(N) работают с хорошей скоростью. Алгоритмы со сложностью N C можно использовать только при небольших значениях C. Вычислительная сложность алгоритмов, порядок которых определяется функциями C N и N! очень велика, поэтому такие алгоритмы могут использоваться только для обработки небольшого объёма данных.

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

Что такое алгоритм?! Часть первая

Терзаем вместе основной кирпичик программиста — Алгоритм.

Проблема

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

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

Почему конкретный прием был успешен в задаче-образце? Будет ли он успешен в твоём проекте? Какие признаки проекта дают понять, что использование приёма уместно?

В личном опыте существования в профессии не раз отмечено, что каждый Junior борется с одинаковыми ветряными мельницами и постигает методы создания программ основываясь только на своих ошибках. Но ведь такие ошибки совершили уже очень многие. Почему до сих пор не создана система правил программирования, которая поможет обойти новоиспеченному кораблю-программисту подводные прибрежные камни? Ну, например, объяснение вреда использования метода «Copy-Paste» для развития кода. Если такие правила получится объяснить малым набором причин, их сформировавшим, то это объяснение обеспечит их запоминание и последующее использование в практике, тем самым поможет уклониться от бесчисленных грабель, разложенных тут и там.

Для компактного и полезного набора объяснений нужно:

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

Если обобщить, то нужны алгоритмы для написания и развития алгоритмов.

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

Задача

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

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

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

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

Сразу возникает масса вопросов к этому определению:

• Что такое правило?
• Как, кому и для кого это правило можно задать?
• Что есть объединение совокупностью?
• Каким образом правила соотносятся с задачей?
• Что формирует класс задачи?
• Определяется ли способ формирования совокупности правилами и задачами?
• .

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

• Какова структура набора?
• Какие есть варианты действий и исполнителей?
• Существуют ли минимально возможное действие, минимальный набор необходимых действий?
• Каким образом действия встроены в исполнителя?
• Какие есть способы создания копии исполнителя (например, если исполнитель — человек)?
• Как действия зависят друг от друга в упорядоченном выполнении?
• Что есть задача кроме того, что она выполняется последовательностью действий?
• Как задача соотносится с исполнителем и с действиями?
• Возможно ли использовать решение задачи в качестве действия?
• Какие возможны варианты указания порядка действий?
• Если воспроизведение патефоном записи звуков леса является алгоритмом, то какова структура этой задачи?
• Если репликация ДНК является алгоритмом, то каков её исполнитель?
• Если исполнителем является Машина Тьюринга, то как с её использованием решить механическую задачу, например, воспроизведение звука?

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

Определение алгоритма

Рассмотрим определение алгоритма, говорящее, что он — приводящая к решению задачи последовательность действий. Как программисту мне приходится писать много кода. Этот код состоит из частей. Такими частями являются и функции, и классы, и модули. Когда я пишу текст функции — я занимаюсь написанием алгоритма.

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

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

Если «действие = алгоритм», то определение можно попробовать переписать рекурсивно «алгоритм — это приводящая к решению задачи последовательность использования существующих алгоритмов». Рекурсивные определение не самое простое, что можно записать в словаре обычного человека. Но для программиста и математика эта форма знакома. Мы умеем с ней работать, и это даёт нам преимущество в рассмотрении разных задач, разбиваемых на подобные себе подзадачи. Так давайте воспользуемся этим преимуществом.

Чтобы разрешить рекурсию нам необходимо найти:

• терминальное условие выхода из рекурсии — минимальное неделимое «действие» (атомарный алгоритм), которое можно использовать в разработке алгоритма;
• способ перехода от текущего уровня рекурсии (набора «действий») к следующему уровню (алгоритму).

Действие

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

Этой причиной является возможность повторного использования «действия» с получением тождественного результата. Только тогда разработанный с использованием этого «действия» алгоритм решения некоторой задачи будет одинаково решать эту задачу снова и снова. Мы нащупали важные законы нашего мира, в котором:

• существуют «действия», главным свойством которых является одинаковость результатов их исполнения в разные моменты времени и в разных местах,
• существует возможность создать такую схему использования нескольких «действий», которая сформирует из них новое «действие», которое мы назвали алгоритмом.

Какие признаки «действия» кроме повторимости делают возможным его использование в создании алгоритма? Что является терминальным неделимым «действием»? Чтобы ответить на этот вопрос стоит рассмотреть разные примеры «действий» из нашего опыта. Программисты встречали их много раз. Это и сложение, и умножение, и установка цвета пикселя на экране. Но мы знакомы с ними и вне программирования. Вся наука основывается на повторяемых явлениях.

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

Рассмотрим, что происходит при выполнении «действия». Например, во время падения яблока с ветки яблони на землю. В этом процессе происходит несколько изменений. Если вспомнить школьную физику и рассмотреть ситуацию в системе отсчета, привязанной к Земле, то сила гравитации вызывает изменение скорости яблока, разгоняя его. При этом в процессе отмечается еще одно важное изменение — уменьшается расстояние между яблоком и Землей.

В рамках примера процесса «Земля-Яблоко» можно отметить у «действия» следующие признаки:

• наличие процесса изменения (расстояния и параметров движения объектов);
• наличие объектов, взаимодействие которых вызывает такие изменения;
• наличие локальности процесса, то есть существование значения расстояния между объектами, с превышением которого их взаимодействие перестает вызывать процесс изменения, что делает невозможным использование «действия» (Земля и гипотетическое яблоко, находящееся вне солнечной системы).

Рассмотрим с этими признаками разные области и процессы, выделяя в них примеры «действий» и контролируя особенности указанных признаков в описании структуры «действия».

Физические процессы

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

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

Химические процессы

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

Математические процессы

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

В ситуации с математиком можно выделить много объектов, но с точки зрения «действия» («сложение математиком двух целых чисел»), объекта всего три: это объект «математик», объект «первое число» и объект «второе число». В отличие от всех рассмотренных ранее объектов числа являются обозначениями, то есть виртуальными объектами. И их преобразование в алгоритме более сложно устроено нежели изменение расстояния и параметров движения объектов, как это было для «химических» действий. Подробности такого преобразования — это тема отдельной увлекательной статьи. А в рамках текущей рассмотрим древнего математика, который складывает числа, используя кучки камешков (рим. ‘calculi’), и более «современного» математика, использующего абак. Абстракции таких способов вычисления суммы не так далеко отошли от физических и химических процессов, поэтому структура процессов их «действий» полностью описывается изменениями расстояний и связей.

Интересно, что на примере древнего математика становится понятен смысл слова «сложить», которое отсылает нас к действию «класть» и к фразе «положить вместе».

Сложение и древний математик

Для математика, оперирующего камешками, сумма это «действие» со следующими характеристиками.

• это сам «математик» (он взаимодействует со слагаемыми);
• лежащая отдельно кучка №1, содержащая и связывающая вместе камешки (подобно химическим связям), и обозначающая первое слагаемое;
• лежащая отдельно кучка камешков №2, обозначающая второе слагаемое.

• «математик» подходит к кучкам (физически изменяет расстояние между кучками и собой) и начинает с ними взаимодействие;
• «математик» объединяет две кучки (физически изменяет расстояние между двумя кучками или переносит все камешки одной кучки в другую, возможно, используя «действие» «Перенос по-одному» камешку)

• сформированная кучка камешков, обозначающая результат (сумму);
• «математик», отошедший от кучки результата и переставший на неё воздействовать.

Сложение и математик-абакист

У математика с абаком ситуация сложнее. Кучки разделены по значению на разрядные борозды.

Можно рассмотреть самый простой абак с двумя разрядами-бороздами. Пусть он будет десятичный. Тогда один камешек на борозде десятков соответствует десяти камешкам на борозде единиц. И 10 — это максимальное количество камешков на борозде единиц. По сравнению с действием первого математика меняется представление слагаемых. И в арсенале математика уже необходимы нескольких готовых «действий».

• «Перенос по-одному» из борозды в борозду одинакового уровня (действие, позаимствованное у первого математика);
• «Перенос в десятки», которое необходимо выполнять, если борозда единиц полностью заполняется, тогда из неё убираются все камешки кроме одного, который переносится в борозду десятков.

• это сам «математик» (он взаимодействует со слагаемыми);
• группа камешков №1, лежащих и удерживаемых двумя бороздами (единиц и десятков), и обозначающих первое слагаемое;
• группа камешков №2, лежащих и удерживаемых двумя бороздами (единиц и десятков), и обозначающих второе слагаемое;

• «математик» подходит к группам борозд (физически изменяет расстояние между ними и собой) и начинает с ними взаимодействие;
• «математик» объединяет камешки из двух борозд единиц (физически изменяет расстояние между камешками, разрушает связи со старой бороздой и создает связи с новой) с использованием действий «Перенос по-одному» и «Перенос в десятки»;
• «математик» объединяет камешки из двух борозд десятков с использованием действия «Перенос по-одному»

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

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

Сложение и машина Тьюринга

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

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

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

Выводы

Соберём всё, что мы отметили рассматривая разные примеры «действия»:

• «действие» можно использовать для создания алгоритма;
• «действие» может быть элементарным;
• «действие» может быть реализовано алгоритмом;
• в «действии» обязательно участвует некоторый объект или группа объектов;
• для группы объектов «действие» происходит только тогда, когда эти объекты «достаточно близко»;
• в действии изменяются связи и параметры объектов (включая параметры их движения);
• «действие» всегда и обязательно должно быть повторимо.

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

Следующая статья серии (Часть 2) будет посвящена рассмотрению способов, с использованием которых «действия» могут быть сгруппированы в алгоритм. Этих способов достаточно много и есть предпосылки, что их описание не получится уместить в одну статью. Напишем — увидим.

Спасибо Вам за внимание.

Отзывы

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

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