Чем отличается инструкция от алгоритма действий - Kompot.top

Если вы видите это сообщение, значит, произошла проблема с загрузкой файлов в стилей (CSS) нашего сайта. Попробуйте сбросить кэш браузера (Ctrl+F5).
Если это не поможет, а вы находитесь в регионе, где возможны ограничения интернет-трафика с российских серверов — воспользуйтесь VPN.

Какая разница между понятиями «алгоритм» и «инструкция»? В каких случаях их надо употреблять?

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

В деловой сфере также существует понятие «должностная инструкция» — перечень служебных обязанностей работника.

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

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

Термин «алгоритм», скорее, уместен в точных науках — в математике, информатике, программировании.

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

автор вопроса выбрал этот ответ лучшим

Безразличный
[292K]

8 лет назад

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

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

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

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

Хотя и в программировании существуют инструкции выполнения тех или иных функций, команд и других действий.

Степан БВ
[41.2K]

2 года назад

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

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

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

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

inspaer
[28K]

5 лет назад

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

654476959581
[7.5K]

7 лет назад

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

znatok54
[15.2K]

7 лет назад

Алгоритм — объективен, а инструкция субъективна, поскольку её сочиняет субъект в интересах достижения конкретной цели деятельностью других субъектов.

Davlat9777
[55]

5 лет назад

Инструкция — это указания или описание действий к чему-либо, а алгоритм это строгая ПОСЛЕДОВАТЕЛЬНОСТЬ этих действий. Применимы везде.

Знаете ответ?

Источник

Основные понятия, рассматриваемые на уроке:

· алгоритм;

· свойства алгоритма;

· способы записи алгоритмов.

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

Пример 1. Задача «Найти среднее арифметическое двух чисел» решается в три шага:

задумать два числа;
сложить два задуманных числа;
полученную сумму разделить на 2.

Пример 2. Задача «Внести деньги на счёт телефона» подразделяется на следующие шаги:

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

Нахождение среднего арифметического, внесение денег на телефонный счёт — на первый взгляд совершенно разные процессы. Но у них есть общая черта: каждый из этих процессов описывается последовательностями кратких указаний, точное следование которым позволяет получить требуемый результат. Последовательности указаний, приведённые в примерах 1-2, являются алгоритмами решения соответствующих задач. Исполнитель этих алгоритмов — человек.

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

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

Каждый алгоритм предназначен для определённого исполнителя.

Исполнитель — это некоторый объект (человек, животное, техническое

устройство), способный выполнять определённый набор команд.

Различают формальных и неформальных исполнителей. Формальный исполнитель одну и ту же команду всегда выполняет одинаково. Неформальный исполнитель может выполнять команду по-разному.

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

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

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

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

исполнителя, который будет его выполнять.

Режимы работы исполнителя.

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

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

Источник

План урока:

Алгоритмы, которыми мы пользуемся

Исполнители, система команд исполнителя (СКИ)

Свойства алгоритмов

Классификация алгоритмов

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

Пример алгоритма на Turbo Pascal

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

Один человек сразу включает чайник, потом начинает искать чашки, заварку, сахар.

Второй действует согласно плану:

Проверить наличие заварки и сахара.
Если их нет, купить.
Если все есть, найти чашку, проверить ее чистоту.
Поставить чайник греться.
Ополоснуть чашку кипятком.
Насыпать заварку, залить кипятком.
Добавить сахар.

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

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

Алгоритмы, которыми мы пользуемся

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

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

Давайте вспомним, какими детальными инструкциями мы пользуемся:

пошаговые кулинарные рецепты;
мастер-классы по рукоделию;
инструкции к оборудованию;
план действия при ЧП.

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

Пример в виде красочной инструкции и сухой пошаговой рекомендации:

Работа за компьюетром Инструкция по настройке

А в информатике без них не обойтись – именно на алгоритмах основано программирование.

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

Если действия однотипные, например, «набрать ковш воды и вылить» или «взять яблоко и проверить, есть ли червоточина», то его записывают 1 раз и повторяют конечное число раз.

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

Исполнители, система команд исполнителя (СКИ)

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

Исполнитель – субъект/объект, который может выполнить команды данного алгоритма.

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

Компьютер (ПК) – автоматизированный исполнитель команд. Алгоритмы программ для ПК пишут на языках программирования (С++, Basic, Pascal, Delphi, Ассемблер, Фортран).

Для каждого типа и уровня исполнителей существует своя система команд исполнителя (СКИ).

Свойства алгоритмов

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

Детерминированность – все описания должны быть однозначными, понятными.

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

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

Дискретность – строгие команды, идущие в определенной последовательности.

Точность – команды должны быть конкретными, понятными, однозначными.

Пример непонятного и неточного задания мы помним из сказки: “Пойди туда, не знаю куда. Принеси то, не знаю что”.

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

Пример бесконечного алгоритма

Мытье рук:

включить воду;
намочить руки и мыло;
выключить воду;
намылить руки;
включить воду.

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

Классификация алгоритмов

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

Виды алгоритмов:

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

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

Источник

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

Запишем схему линейного алгоритма (покупки чая):

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

Для многих задач важно выполнение определенного условия.

Пример алгоритма ветвления – если нужного сорта нет, то процесс покупки чая усложняется:

Взять пакет и кошелек с деньгами.
Зайти в любой продуктовый маркет.
Посмотреть, есть ли чай «Элитный».
Если да, то узнать цену, отдать деньги.
Покупку положить в пакет, пойти домой.
Если нет, найти сорт «Белый, китайский», узнать цену, отдать деньги.
Упаковку положить в пакет, вернуться домой.
Если нет ни «Элитного», ни «Белого, китайского», то пойти в другой магазин и повторить все с пункта №3.

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

Данный пример включает в себя ветвление «если» и повторение команд:

Взять пакет и кошелек с деньгами.
Зайти в любой продуктовый маркет.
Взять коробку с чаем в руки, посмотреть, это сорт «Элитный».
Если да, то узнать цену, заплатить.
Забрать покупку, вернуться домой.
Если нет, взять следующую упаковку и повторить пункты 3-6.
Если весь чай перебран, но «Элитного» нет, то пойти в другой магазин и повторить все с пункта №3.

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

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

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

Легче воспринимается такой план, если его дополнять картинками.

Источник

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

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

Блок-схема – графическая форма представления алгоритмов при помощи геометрических объектов и стрелок.

Блок схема линейного алгоритма вычисления площади прямоугольника:

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

Пример алгоритма на Turbo Pascal

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

Для примера попробуем программирование линейных алгоритмов при помощи языка Turbo Pascal.

Запустить среду программирования следующими шагами:

Меню Пуск → Все программы → Turbo Pascal

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

Оболочка разработана под DOS, что объясняет необычную реализацию интерфейса.

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

На латинской раскладке набираем в синем окне такие команды:

program Test;

begin

write(‘Доброе утро!’);

end.

Учитываем важные моменты при использовании языка Турбо Паскаль:

все пишется латинскими буквами;
регистр неважен;
каждая строка – команда, в конце строки ставится Enter и «;»;
после «end» должна быть «.».

Как видим, в программе есть свои слова-команды, как в письменных алгоритмах. Слово program – как заголовок, название объекта, а тest – непосредственно название программы.

Началом является команда begin, end – окончанием, а между ними стоят операторы или команды-действия («write» – напиши на экране). А текст, который нужно выводить на экране берется в скобки и ’….’.

Чтобы запустить программу, следует нажать Ctrl+F9 или набор команд Run Run.

Если нет ошибок в командах, появится такой результат:

Чтобы выйти обратно, можно нажать любую кнопку клавиатуры.

При каждом запуске будет новая запись, на той же строке. Если заменить write на writeln, то текст будет выводиться в новой строчке:

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

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

Источник

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

Определение

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

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

Сравнение

В чем разница между алгоритмом и программой ясно уже из терминологии. Казалось бы, в обоих случаях мы видим упорядоченные действия, приводящие к конечному результату. Как понятно из определений, программа может состоять из нескольких алгоритмов, однако иерархия “общее — частное” здесь не прослеживается. Алгоритм — это вообще любая инструкция, в которой четко перечислены действия. Например, для сборки шкафа. Программой она, конечно, являться не будет. Алгоритм может существовать в любой форме: его можно запомнить, записать в блокнот, зарисовать в виде схемы, продиктовать, так как в основе его — логическая составляющая, а не формальная. Программа же — понятие формальное. Она представляет собой именно запись набора алгоритмов, причем запись на одном из языков программирования, понятных вычислительной машине. Это может быть не только наш привычный компьютер, но и блок управления любого прибора. Таким образом, алгоритм можно определить как метод или схему воплощения идеи, программу — как ее реализацию конкретными средствами.

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

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

Выводы сайт

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

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

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

Объекты, над
которыми исполнитель
может совершать
действия, образуют
так называемую
среду исполнителя.

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

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

Такими свойствами
являются:

Дискретность
(прерывность,
раздельность)

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

Определенность

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

Результативность
(конечность)

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

Массовость

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

На основании
этих свойств
иногда дается
определение
алгоритма,
например: “Алгоритм
– это последовательность
математических,
логических
или вместе
взятых операций,
отличающихся
детерменированностью,
массовостью,
направленностью
и приводящая
к решению всех
задач данного
класса за конечное
число шагов.”
Такая трактовка
понятия “алгоритм”
является неполной
и неточной.
Во-первых, неверно
связывать
алгоритм с
решением какой-либо
задачи. Алгоритм
вообще может
не решать никакой
задачи. Во-вторых,
понятие “массовость”
относится не
к алгоритмам
как к таковым,
а к математическим
методам в целом.
Решение поставленных
практикой задач
математическими
методами основано
на абстрагировании
– мы выделяем
ряд существенных
признаков,
характерных
для некоторого
круга явлений,
и строим на
основании этих
признаков
математическую
модель, отбрасывая
несущественные
признаки каждого
конкретного
явления. В этом
смысле любая
математическая
модель обладает
свойством
массовости.
Если в рамках
построенной
модели мы решаем
задачу и решение
представляем
в виде алгоритма,
то решение
будет “массовым”
благодаря
природе математических
методов, а не
благодаря
“массовости”
алгоритма.

Разъясняя
понятие алгоритма,
часто приводят
примеры “бытовых
алгоритмов”:
вскипятить
воду, открыть
дверь ключом,
перейти улицу
и т. д.. : рецепты
приготовления
какого-либо
лекарства или
кулинарные
рецепты являются
алгоритмами.
Но для того,
чтобы приготовить
лекарство по
рецепту, необходимо
знать фармакологию,
а для приготовления
блюда по кулинарному
рецепту нужно
уметь варить.
Между тем исполнение
алгоритма –
это бездумное,
автоматическое
выполнение
предписаний,
которое в принципе
не требует
никаких знаний.
Если бы кулинарные
рецепты представляли
собой алгоритмы,
то у нас просто
не было бы такой
специальности
– повар.

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

Само выражение
“свойства
алгоритма”
некорректно.
Свойствами
обладают объективно
существующие
реальности.
Можно говорить,
например, о
свойствах
какого-либо
вещества. Алгоритм
– искусственная
конструкция,
которую мы
сооружаем для
достижения
своих целей.
Чтобы алгоритм
выполнил свое
предназначение,
его необходимо
строить по
определенным
правилам. Поэтому
нужно говорить
не о свойствах
алгоритма, а
о правилах
построения
алгоритма, или
о требованиях,
предъявляемых
к алгоритму.

Первое правило

– при построении
алгоритма
прежде всего
необходимо
задать мно-жество
объектов, с
которыми будет
работать алгоритм.
Формализованное
(закодирован-ное) представление
этих объектов
носит название
данных. Алгоритм
приступает
к работе с некоторым
набором данных,
которые называются
входными, и в
результате
своей рабо-ты
выдает данные,
которые называются
выходными.
Таким образом,
алгоритм пре-образует
входные данные
в выходные.

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

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

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

Третье правило

– дискретность.
Алгоритм строится
из отдельных
шагов (действий,
операций, команд).
Множество
шагов, из которых
составлен
алгоритм, конечно.

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

Пятое правило

– сходимость
(результативность). Алгоритм должен
завершать
работу после
конечного числа
шагов. При этом
необходимо
указать, что
считать результатом
работы алгоритма.

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

Любая работа
на компьютере
– это есть обработка
информации.
Работу компьютера
можно схематически
изобразить
следующим
образом:

“Информация”
слева и “информация”
справа – это
разные информации.
Компьютер
воспринимает
информацию
извне и в качестве
результата
своей работы
выдает новую
информацию.
Информация,
с которой работает
компьютер,
носит название
“данные”.

Компьютер
преобразует
информацию
по определенным
правилам. Эти
правила (операции,
команды) заранее
занесены в
память компьютера.
В совокупности
эти правила
преобразования
информации
называются
алгоритмом.
Данные, которые
поступают в
компьютер,
называются
входными данными.
Результат
работы компьютера
– выходные
данные. Таким
образом, алгоритм
преобразует
входные данные
в выходные:

Теперь можно
поставить
вопрос: а может
ли человек
обрабатывать
информацию? Конечно, может.
В качестве
примера можно
привести обычный
школьный урок:
учитель задает
вопрос (входные
данные), ученик
отвечает (выходные
данные). Самый
простой пример:
учитель дает
задание – умножить
6 на 3 и результат
написать на
доске. Здесь
числа 6 и 3 – входные
данные, операция
умножения –
алгоритм, результат
умножения –
выходные данные:

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

Рассмотрим
следующую
задачу.

Длина класса
7 метров, ширина
– 5 метров, высота
– 3 метра. В классе
25 учеников. Сколько
кв. м площади
и сколько куб.
м воздуха приходится
на одного ученика?

Решение
задачи:

1. Вычислить
площадь класса:

2. Вычислить
объем класса:

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

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

105: 25 = 4,2
Ответ:
на одного ученика
приходится
1,4 кв. метров
площади и 4,2 куб.
метров воздуха.

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

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

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

1. Вычислить
площадь класса
и записать в
переменную
S.

2. Вычислить
объем класса
и записать в
переменную
V.

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

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

5. Вывести на
экран значения
переменных
S1 и V1.

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

Трактовка
работы алгоритма
как преобразования
входных данных
в выходные
естественным
образом подводит
нас к рассмотрению
понятия “постановка
задачи”. Для
того, чтобы
составить
алгоритм решения
задачи, необходимо
из условия
выделить те
величины, которые
будут входными
данными и четко
сформулировать,
какие именно
величины требуется
найти. Другими
словами, условие
задачи требуется
сформулировать
в виде “Дано… Требуется”
– это и есть
постановка
задачи.

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

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

Механические
алгоритмы
,
или иначе
детерминированные,
жесткие (например
алгоритм работы
машины, двигателя
и т.п.);

Гибкие
алгоритмы
,
например
стохастические,
т.е. вероятностные
и эвристические.

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

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

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

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

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

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

Цикл программы

– последовательность
команд (серия,
тело цикла),
которая может
выполняться
многократно
(для новых исходных
данных) до
удовлетворения
некоторого
условия.

На рисунке
продемонстрированы
в условных
обозначениях
схемы основных
конструкций
алгоритмов:

а). линейного
алгоритма;

б,в,г). разветвляющихся
алгоритмов
(б-ответвление,
в-раздвоение,
г-переключение);

д,е,ж). циклических
алгоритмов
(д,ж-проверка
в начале цикла,
е-проверка в
конце цикла).

Вспомогательный
(подчиненный)
алгоритм

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

На всех этапах
подготовки
к алгоритмизации
задачи широко
используется
структурное
представление
алгоритма.

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

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

Можно встретить
даже такое
утверждение:
“Внешне алгоритм
представляет
собой схему
– набор прямоугольников
и других символов,
внутри которых
записывается,
что вычисляется,
что вводится
в машину и что
выдается на
печать и другие
средства отображения
информации
“. Здесь форма
представления
алгоритма
смешивается
с самим алгоритмом.

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

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

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

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

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

Вот в этом
– “ объяснение
и понимание”
– и кроется
различие между
понятиями
“алгоритм”
и “способ”,
“метод”, “правило”.
Правила выполнения
арифметических
операций – это
именно правила
(или способы), а не алгоритмы.
Конечно, эти
правила можно
изложить в виде
алгоритмов,
но толку от
этого не будет.
Для того, чтобы
человек смог
считать по
правилам арифметики,
его нужно научить.
А если есть
процесс обучения,
значит, мы имеем
дело не с алгоритмом,
а с методом.

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

Очень ярко
эта особенность
человеческой
психологии
– неалгоритмичность
мышления –
проявилась
в методичесом
пособии А. Г.
Гейна и В. Ф.
Шолоховича.
В пособии излагаются
решения задач
из известного
учебника. Решения
задач должны
быть представлены
в виде алгоритмов.
Однако авторы
пособия понимают,
что если просто
написать алгоритм
решения задачи,
то разобраться
в самом решении
будет трудно.
Поэтому они
сначала приводят
“нечеткое
изложение
алгоритма”
(т. е. объясняют
решение задачи), а затем пишут
сам алгоритм.

Л И Т Е Р А Т
У Р А

1. Нестеренко
А. В. ЭВМ и профессия
программиста.

М., Просвещение,
1990.

2. Брудно А.
Л., Каплан Л. И.
Московские
олимпиады по
программированию.

М., Наука, 1990.

3. Кузнецов
О. П., Адельсон-Вельский
Г. М. Дискретная
математика
для инженера.

М., Энергоатомиздат,
1988.

4. Гейн А.Г. и
др.. Основы
информатики
и вычислительной
техники.

М., Просвещение,
1994.

5. Информатика.
Еженедельное
приложение
к газете “Первое
сентября”.
1998, № 1.

6. Радченко
Н. П. Ответы на
вопросы выпускных
экзаменов. –
Инфоматика
и

образование,
1997, №4.

7. Касаткин
В.Н. Информация,
алгоритмы, ЭВМ.
М., Просвещение,
1991.

8. Каныгин Ю.
М., Зотов Б. И. Что
такое информатика?

М., Детская
литература,
1989.

9. Гейн А. Г.,
Шолохович В.Ф.
Преподавание
курса “Основы
информатики
и вычислительной
техники” в
средней школе.
Руководство
для учителя.

Екатеринбург,
1992.

10. Извозчиков
В.А. Информатика
в понятиях и
терминах.

11. Газета
«Информатика»,
№35, 1997г.

12. Л.З. Шауцуков
Основы информатики
в вопросах и
ответах.

Автор: Богашова Татьяна, Донец Сергей (КПИ,ФАКС) г.Киев, 1999г.
Оценка:отл.
Сдавался: ПТУ №34
E-Mail:[email protected]

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

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

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

Известно, что термин “алгоритм”
используется и в более широком смысле
для представления человеческой
деятельности в виде строгой
последовательности
отдельных элементарных действий или
процедур , а
технологический процесс можно определить
как “последовательность направленных
на создание заданного объекта действий
(технологических операций), каждое из
которых основано на каких-либо естественных
процессах (физических, химических,
биологических и др.) и человеческой
деятельности” . Тщательный анализ
этих и многих других определений
показывает, что исследуемые понятия взначительной степени
совпадают, а имеющиеся различия в
определенном смысле несущественны.
Иными словами, технологический процесс
и алгоритм — это понятия-близнецы или
во всяком случае “близкие родственники”.
Чтобы сделать эту мысль более убедительной,
попытаемся отойти от традиционной точки
зрения и предложим новые определения.

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

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

Что такое технологический язык?

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

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

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

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

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

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

Приветствую, друзья! Мы продолжаем знакомить вас с миром криптографии и криптовалют. Сегодня хотелось бы рассказать о протоколах безопасности Proof of Work
и Proof of Stake
. В чем их отличие и как переход от одного к другому может сказаться на мире майнинга. Как всегда простыми и интересными словами. Поехали!

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

Proof of Work

Теперь, давайте рассмотрим алгоритм подтверждения транзакций и создания новых блоков, под названием – Proof of Work. Представьте, что все транзакции, это кусочки криптографического пазла () , которые собираются вместе и создают блок. Решение этого пазла (блока) называется майнингом.

Как зарабатывает майнер?

Чтобы подписать блок с неподтвержденными транзакциями, майнерам необходимо вычислить ХЭШ. Вычислив его, майнер создает новый блок и получает вознаграждение в размере 12,5 BTC. Вознаграждение за подписание нового блока, уменьшается каждые 4 года. В начале создания сети Биткойн, оно было 50 BTC.

Как система определяет майнера подписавшего новый блок?

Каждый майнер, желающий создать блок, трудится над очень сложной вычислительной задачей. Сложность которой подбирается сетью так, чтобы в среднем решение находилось 1 раз в 10 минут. Если число майнеров увеличивается, задача усложняется. Следовательно, шансы каждого участника решить задачу за 10 минут, уменьшаются. Чем больше у майнера вычислительной мощности, тем выше его шансы на успех. Майнер, который первым решает задачу и вычисляет ХЭШ, подписывает новый блок и получает награду.

Итак, что мы имеем?

Алгоритм Proof of Work обеспечивает высококачественную защиту. Еще не было ни одного случая взлома сети Биткойн. Однако, данный алгоритм имеет огромный минус, выполняемая работа требует очень больших затрат электроэнергии. Гонка за новыми блоками превратила индустрию майнинга в ненасытного энергетического монстра. И именно для решения этой проблемы и был разработан алгоритм Proof of Stake.

Proof of Stake

Proof of Stake переводится как доказательство доли владения. В этом алгоритме нет майнеров. Люди, подтверждающие транзакции и создающие новые блоки, называются – Валидаторы.

Рассмотрим условный пример

Предположим, есть блок который нужно подписать, и есть 4 валидатора. Каждый валидатор вносит свои средства в блокчейн, чтобы получить возможность подписать блок.

Первый валидатор имеет больше всего монет, и вносит 40%. Второй валидатор вносит 25%, третий 20%, и, наконец, последний вносит 15%. С алгоритмом Proof of Work шансы на подписание блока зависят от вычислительной мощности которая у вас есть. Но в Proof of Stake алгоритм работает иначе. Чем больше у вас монет, тем больше у вас шансов подписать новый блок.

После рандомных подсчетов, система выбирает одного из валидаторов и он подписывает блок. Но за это действие валидатор не получает новых монет, он получает все комиссии за транзакции которые были записаны в этом блоке.

Преимущества Proof of Stake

Алгоритм Proof of Stake имеет ряд очевидных преимуществ.

1.
Нет расхода электроэнергии. При использовании Proof of Stake ресурсы не используются в пустую. Компьютер, хоть и должен быть включен, однако он не проводит сложных вычислений и соответственно не потребляет много электричества.

2.
Отсутствует необходимость наращивать вычислительные мощности.

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

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

Теперь вы знаете как работают алгоритмы Proof of Work и Proof of Stake. Подписывайтесь на наши социальные сети (ссылки в футере сайта), чтобы не пропустить информацию о новых статьях и проектах.

Зарабатывайте и прокачивайте свои мозги вместе с Business Biceps.

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

В этой статье мы разберем основные понятия алгоритма.

История появления алгоритмов

Алгоритм — понятие, появившиеся в XII веке. Само слово «алгоритм» происходит от латинской интерпретации имени известного математика среднего востока Мухаммеда аль Хорезми, который написал книгу «Об индийском счете». В этой книге описано, как правильно записывать натуральные числа, используя арабские цифры, и приведено описание алгоритма действий столбиком над такими числами.

В XII веке книга «Об индийском счете» была переведена на латинский язык, тогда-то и появилось данное определение.

Взаимодействие алгоритма с человеком и машиной

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

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

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

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

Что такое алгоритм?

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

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

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

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

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

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

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

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

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

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

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

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

Существуют разные типы алгоритмов, но есть три основных.

Цикличный алгоритм

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

Итерация цикла — это выполнение всех пунктов, входящих в тело цикла.
Части цикла, которые постоянно выполняются определенное количество раз, называются циклом с фиксированным числом итераций.

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

Самый простой вид цикла — это фиксированный.

Существует два вида цикличных алгоритмов:

Цикл с предусловием. В этом случае тело цикла проверяет свое условие до того, как он будет выполнен.

Цикл с постусловием. В проверка условия происходит после окончания выполнения цикла.

Линейные типы алгоритмов

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

Разветвляющийся алгоритм

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

Пример. Вопрос: «Идет дождь?» Варианты ответов: «Да» или «Нет». Если «да» — откройте зонт, если «нет» — положите зонт в сумку.

Вспомогательный алгоритм

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

Термины, встречающиеся в алгоритмах

Условие
находится между словами «если» и «тогда».

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

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

Алгоритмический процесс
— решение задачи по алгоритму с применением определенных данных.

Структура алгоритма

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

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

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

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

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

Также блок-схемы изображаются в соответствии с ГОСТ-19701-90 и ГОСТ-19.003-80.
Графические фигуры, применяемые в алгоритме, делятся на:

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

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

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

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

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

Как правильно построить алгоритм?

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

Общая методика по записи включает в себя следующие пункты:

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

У каждого алгоритма должны быть четко обозначены начало и конец.

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

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

Имя схемы.
Данные.
Начало.
Команды.
Конец.

Правильное построение схемы существенно облегчит вычисление алгоритмов.

Геометрические фигуры, отвечающие за разные действия в алгоритме

Горизонтально расположенный овал — начало и конец (знак завершения).

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

Горизонтально расположенный параллелограмм — ввод или вывод (знак данных).

Горизонтально расположенный ромб — проверка условия (знак решения).

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

Модели алгоритмов представлены ниже на рисунке.

Формульно-словестный вариант построения алгоритма.

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

Понятие алгоритма в информатике

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

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

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

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

Вывод

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

Источник

Исходная версия статьи (Ворожцов А. В., «Что такое алгоритм?») была опубликована в журнале «Потенциал»

Геометрия развивает геометрическое мышление, математика — абстрактное математическое, логика — логическое, физика — физическое… А какое мышление развивает информатика? Информатика есть наука, служащая информационным технологиям. Но фундаментальными достижениями этой науки оказались не сами технологии, а общие методы построения систем и решения сложных задач. Базисом этих методов являются алгоритмы и системный подход к решению задач. Поэтому информатика развивает алгоритмическое мышление и учит системному подходу к решению задач.

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

Понятие алгоритма — одно из основных в программировании и информатике^[1]. Это последовательность команд, предназначенная исполнителю, в результате выполнения которой он должен решить поставленную задачу. Алгоритм должен описываться на формальном языке, исключающем неоднозначность толкования. Исполнитель может быть человеком или машиной. Исполнитель должен уметь выполнять все команды, составляющие алгоритм. Множество возможных команд конечно и изначально строго задано. Действия, выполняемые по этим командам, называются элементарными.

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

Приведём для примера простой алгоритм действия пешехода, который
позволит ему безопасно перейти улицу:

Подойти к дороге.
Дождаться зелёного сигнала светофора.
Перейти дорогу.
Если впереди есть ещё одна дорога, то перейти к шагу 1.

Алгоритмы обладают свойством детерминированности (определённости): каждый шаг и переход от шага к шагу должны быть точно определены так, чтобы его мог выполнить любой другой человек или механическое устройство.

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

Конечность: Алгоритм всегда должен заканчиваться за конечное число шагов, но это число не ограничено сверху.

Массовость: Алгоритм применяется к некоторому классу входных данных (чисел, пар чисел, набору букв и тому подобному). Не имеет смысла строить алгоритм нахождения наибольшего общего делителя только для одной пары чисел 10 и 15.

Поясним эти свойства на простом примере. Рассмотрим следующую формулу вычисления числа :
.

Является ли эта формула алгоритмом вычисления числа ? Ответ на этот вопрос — «нет», так как здесь нет ни свойства массовости (нет входных данных), ни свойства конечности (сумма бесконечного количества чисел)^[2].

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

Понятие элементарных объектов и элементарных действий

править

Алгоритмы по определению должны сводиться к последовательности элементарных действий над элементарными объектами. Какие действия и объекты элементарны, а какие — нет, зависит от исполнителя (вычислительной машины). Набор элементарных действий и элементарных объектов для каждого исполнителя чётко зафиксирован. Элементарные действия оперируют с небольшим числом элементарных объектов. Все остальные объекты и действия являются совокупностью элементарных. В современных компьютерах рациональные числа и иррациональные числа не являются элементарными объектами^[3]. Элементарным объектом в современных компьютерах является бит — это ячейка памяти, в которую может быть записано число 0 или 1. С помощью набора бит можно записывать целые и действительные числа. В частности, существует простой способ представить целые числа от до в виде последовательности 8 бит:

0	→ 00000000
1	→ 00000001
2	→ 00000010
3	→ 00000011
4	→ 00000100
5	→ 00000101
…	→ …
250	→ 11111010
251	→ 11111011
252	→ 11111100
253	→ 11111101
254	→ 11111110
255	→ 11111111

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

3 →	11 →
5 →	101 →
7 →	111 →
31 →	11111 →
32 →	100000 →

Задача 1

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

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

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

Итак, для компьютеров лишь некоторые действительные числа являются элементарными объектами^[4]Множество этих чисел конечно. Какие именно действительные числа элементарны, зависит от используемого машинного представления. Многие современные процессоры поддерживают несколько типов машинного представления действительных чисел. Целые числа практически везде представляются одинаковым образом. В процессорах с 32-битной архитектурой большая часть команд связана с числами, записанными в 32 битах. При представлении неотрицательных чисел в 32 бита помещается просто двоичная запись. Множество представимых таким образом чисел — это все неотрицательные числа меньше . Этому машинному представлению в языке Си соответствует тип данных unsigned int. Если мы попытаемся сложить с помощью команды процессора два числа типа unsigned int, сумма которых больше либо равна , то возникнет переполнение — старший 33-й бит результата будет утерян.

При представлении отрицательных чисел в виде 32 бит один бит необходимо выделить под знак — «плюс» или «минус». Неотрицательные числа, меньшие , записываются обычным образом в виде двоичной записи. Старший бит у них равен нулю. Отрицательное число , модуль которого меньше либо равен , записывается в 32 битах как двоичная запись числа . Старший бит для отрицательных чисел равен 1. Этому машинному представлению соответствует тип int. Представимые таким образом числа — это числа на отрезке .

Подведём итоги:

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

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

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

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

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

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

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

Идея решения → Алгоритм → Программа

Стрелка означает переход к следующему этапу решения задачи с повышением уровня подробности описания метода решения.

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

Если , то НОД (наибольший общий делитель) и заканчиваем вычисления.
Если , то из вычитаем ( ). Переходим к 1.
Если же , то из вычитаем ( ). Переходим к 1.

Запишем этот алгоритм с помощью псевдокода.

Псевдокод 1. Алгоритм Евклида

 1 Function НОД(a, b)
 2   While  
 3     If  
 4        
 5     Else
 6        
 7     End If
 8   End While
 9   Return a
10 End Function

Конструкция While(A) B End While псевдокода означает «повторять последовательность операций B, записанных в теле оператора While, пока выполнено условие A». Тело оператора While — это все инструкции между While(A) и End While. Если условие A не выполнено в самом начале, то тело оператора While не выполняется ни разу. Один шаг выполнения тела цикла называется итерацией цикла.

Конструкция If(A) B Else C End If» псевдокода означает «если верно A, то выполнить инструкции B, иначе выполнить инструкции C».

Инструкция return a означает «вернуть как результат вычислений объект a».

Покажем, что наш алгоритм нахождения НОДа чисел и .

Действительно, НОД НОД при , поэтому, несмотря на то, что на каждом шаге меняется одно из чисел, значение НОД остаётся неизменным. Максимальное из чисел и с каждым шагом уменьшается, и в какой-то момент они становятся равны друг другу и равны искомому значениюЗадача 2

Докажите, что НОД НОД для любых неотрицательных целых и , таких что .

Задача 3

Усовершенствуйте вышеприведённый алгоритм, используя то, что НОД НОД при положительных и (выражение означает остаток при делении на ).

Алгоритм вычисления чисел Фибоначчи

править

В математике для описания функций часто используются рекуррентные соотношения, в которых значение функции определяется через её значение при других (обычно меньших) аргументах. Наиболее известным примером является последовательность Фибоначчи 1, 1, 2, 3, 5, 8, 13, …, определяемая следующими соотношениями:

Используя это рекуррентное соотношение, можно построить рекурсивный алгоритм вычисления чисел Фибоначчи:

Псевдокод 2. Числа Фибоначчи

1 Function Fibo(n)
2   If n = 1 Or n = 2
3     Return 1
4   End If
5   Return Fibo(n - 1) + Fibo(n - 2)
6 End Function

При анализе рекурсивной функции обычно возникает два вопроса: почему функция работает правильно и почему она завершает работу? Ответ на первый вопрос обычно прост, — если рекуррентные отношения правильны и интерпретатор (компилятор) сработал правильно, то единственное значение, которое может вернуть программа, — правильное. Но есть ещё другая альтернатива — программа может не закончить свою работу^[5].

Наибольший интерес в этом алгоритме представляет строчка 5:

Return Fibo(n - 1) + Fibo(n - 2)

Она означает следующее: «Запустить процесс вычисления Fibo(n - 1), затем запустить процесс вычисления Fibo(n - 2), результаты вычислений сложить и вернуть в качестве результата». Можно считать что в этой строчке исполнитель нашего алгоритма просит другого исполнителя вычислить Fibo(n - 1), а сам ждёт, когда тот закончит вычисления. Узнаёт у него результат, просит вычислить Fibo(n - 2) и снова ждёт результата. Два полученных результата складывает, возвращает значение суммы как результат и заканчивает работу. Интерес заключается в том, что этот дополнительный исполнитель действует по такому же алгоритму — если его аргумент больше 1, он также вызывает очередного исполнителя для вычисления нужных ему значений. Получается серия вызовов, которые выстраиваются в дерево рекурсивных вызовов.

Рис. 1. Дерево рекурсивных вызовов для .

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

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

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

Задача 4

Сколько раз вызывались вычисления и при вычислении ? Нарисуйте дерево рекурсивных вызовов для и определите, сколько раз будут вызваны и . Найдите общую формулу для числа вызовов и при вычислении .

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

Для вычисления Fibo(n) нам потребуется вызвать Fibo(n - 1) и Fibo(n - 2), поэтому . Используя это соотношение и то, что , можно по индукции доказать, что . Но числа Фибоначчи возрастают достаточно быстро ( ). Поэтому даже на мощном компьютере с помощью этого алгоритма нам не удастся вычислить больше, чем первые несколько десятков членов последовательности Фибоначчи. Вы, наверное, уже догадываетесь, в чём здесь проблема. В нашей программе очень много избыточных вызовов — в дереве рекурсивных вызовов много повторений. Например Fibo(n - 2) будет вызвана два раза: сначала из Fibo(n), а потом из Fibo(n - 1), и оба раза будут проводится одни и те же вычисления. Простой «человеческий» алгоритм вычисления чисел Фибоначчи работает существенно быстрее: нужно помнить последние два числа Фибоначчи, вычислять следующее число и повторять этот шаг нужное число раз. Приведём его описание на псевдокоде (см. псевдокод 3).

Алгоритм 3 для вычисления выполнит итераций цикла While. Видно, что время работы алгоритма растёт линейно с (увеличение в раз приведёт к тому, что время работы алгоритма тоже увеличится примерно в раз).

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

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

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

Псевдокод 3. Числа Фибоначчи: нерекурсивный алгоритм

 1 Function FiboNR(n)
 2   If   Then
 3     Return 1
 4   Else
 5               \\ Предпоследнее вычисленное число Фибоначчи
 6               \\ Последнее вычисленное число Фибоначчи
 7     For  
 8            \\ Вычисляем следующее число Фибоначчи
 9               \\ Старое последнее число стало предпоследним
10               \\ Новое вычисленное число стало последним
11     End For
12     Return c
13   End If
14 End Function

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

Рассмотрим ещё один классический пример на рекурсивные алгоритмы — игру «Ханойские башни», придуманную ещё в 1883 году Эдуардом Люка. Есть три стержня и 64 кольца́, нанизанных на них. В начале все ко́льца находятся на первом стержне, причём все ко́льца разного диаметра, и меньшие ко́льца лежат на бо́льших. За ход разрешается взять верхнее кольцо с любого стержня и положить на другой стержень сверху, при этом запрещается класть большее кольцо на меньшее. Цель игры состоит в том, чтобы переместить всю пирамиду с первого стержня на второй.

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

Псевдокод 4. Ханойские башни

1 Function Move(n, x, y)
2   If n = 1 Then
3     передвинуть кольцо с стержня x на стержень y
4   End If
5   Move(n - 1, x        , 6 - x - y)
6   Move(1    , x        , y        )
7   Move(n - 1, 6 - x - y, y        )
8 End Function

Итак, мы опять получили рекурсивный алгоритм: для того, чтобы решить задачу для пирамиды из колец, достаточно решить её для пирамиды из колец. Посчитаем теперь количество действий, необходимое для проведения всей операции. Пусть — необходимое число действий, для переноса пирамиды из колец. Для одного кольца ответ равен единице: , для ответ будет . Решая это рекуррентное соотношение, получаем: . А значит, Таким образом, время, необходимое для перемещения пирамидки из 64 колец, очень велико.

Алгоритм 4, записанный на псевдокоде, реализует рекурсивную идею перемещения колец в игре «Ханойские башни». Функция MOVE(n, x, y) перемещает n колец со стержня с номером x на стержень с номером y.

Задачу «Xанойские башни» можно значительно усложнить.

Задача

Дано четыре стержня. На одном из них 64 кольца́, размеры которых увеличиваются от верхнего к нижнему. Следуя правилам задачи «Ханойские башни» необходимо переместить их на второй стержень. Напишите программу, которая находит минимальное необходимое число операций перекладывания одного кольца́.

Примеры простых алгоритмических задач

править

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

Задача 5

Сколько раз в рекурсивном алгоритме вычисления Fibo(10) будет вызвана процедура вычисления Fibo(1)?

Задача 6

Сколько раз в рекурсивном алгоритме вычисления Fibo(n) будет вызвана процедура вычисления Fibo(m)?

Задача 7

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

Задача 8

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

Задача 9

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

Задача 10

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

Задача 11

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

Задача 12

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

Задача 13

Квадратный бумажный лист сложили пополам по вертикали (так, что изгиб шёл посредине, сверху вниз) (1-я операция), потом по горизонтали (2-я операция), затем снова по вертикали (3-я операция) и так далее, сделав всего операций. Затем сделали разрез по горизонтали. Напишите рекурсивный алгоритм, вычисляющий
число получившихся бумажек.

Задача 14

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

Задача 15

Рассмотрим следующее рекуррентное соотношение для функции :

Нарисуйте дерево рекурсивных вызовов для (подсказка: это дерево не ветвится и выглядит как цепочка вызовов).

Задача 16

Чем отличается алгоритм от функции?

Чем отличается программа от алгоритма?

В чём разница между идеей решения и алгоритмом решения задачи?

^ Определение взято из книги Борисенко В. В., Основы программирования, Интернет ун-т информ. технологий. — М.: Интернет ун-т информ. технологий, 2005.
^ Следует отметить, что в различных системах символьных вычислений число представляется как число с бесконечной точностью как алгоритм, который по мере надобности вычисляет нужное число первых цифр десятичного представления числа . Такой алгоритм можно построить и на основе приведённой формулы, но этот алгоритм нельзя идентифицировать с самой формулой.
^ Для человека числа также не являются элементарными — обычно он думает о них как о наборе цифр в десятичной записи и для их сложения и умножения использует алгоритмы сложения и умножения чисел «столбиком», в которых эти операции сводятся к последовательности элементарных действий с цифрами.
^ Несмотря на то, что натуральное число не является элементарным объектом, мы в некоторых алгоритмах позволим себе работать с натуральными числами как с элементарными объектами. При этом мы будем подразумевать, что алгоритм работает лишь для небольших натуральных чисел или что за арифметическими операциями стоят соответствующие алгоритмы сложения, вычитания и умножения столбиком или алгоритм деления уголком сколь угодно больших чисел.
^ Эта неприятная альтернатива оказывается является неотъемлемой частью вычислений. Оказывается в принципе нельзя из множества всех программ каким-либо алгоритмическим образом выделить никогда не зависающие программы. Об этом вы можете подробно узнать на курсе по вычислимые функции (см. теоремы Тарского и Геделя).

В Википедии:

Алгоритм
Математическая индукция

В Викиучебнике:

Слово «алгоритм»: происхождение и развитие
Знакомство с методом математической индукции

Томас Х. Кормен. Алгоритмы: вводный курс Томаса Х. Кормена = Algorithms Unlocked. — М.: «Вильямс», 2014. — 208 с. — ISBN 978-5-8459-1868-0.
Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн. Алгоритмы: построение и анализ, 3-е издание = Introduction to Algorithms, Third Edition. — М.: «Вильямс», 2014. — 1328 с. — ISBN 978-5-8459-1794-2.

Larry LIU Xinyu. AlgoXY — открытая книга об элементарных алгоритмах и структурах данных. = AAlgoXY is an open book about elementary algorithms and data structures.. — github.com: -, 2017. — >600 с. — ISBN -.

Дискретная математика, алгоритмы и структуры данных^[1]

↑ Дискретная математика, алгоритмы и структуры данных — Викиконспекты. neerc.ifmo.ru. Дата обращения: 11 февраля 2017.

Источник