что такое дискретность алгоритма
Алгоритм. Свойства алгоритма
Существует множество определений понятия «алгоритм»:
Из определений вытекают свойства алгоритма [5]:
Теперь покажем, что конкретный алгоритм обладает этими свойствами. В качестве примера, возьмем алгоритм, изображенный на рис. 1 в виде блок-схемы [6].
Рис 1 Блок-схема алгоритма проверки правильности расстановки скобок
Приведенный алгоритм проверяет правильность расстановки скобок, если скобки расставлены правильно – то каждой закрывающей скобке предшествует соответствующая открывающая, а каждой открывающей соответствует закрывающая.
Суть алгоритма заключается в подсчете глубины вложенности скобок друг в друга. Если в какой-то момент глубина получает значение меньше нуля – то скобки расставлены неправильно. Если просмотрены все символы строки, но счетчик не равен нулю – то в строке есть не закрытые скобки (расставлены неправильно). В противном случае скобки расставлены правильно.
Можно сказать, что алгоритм обладает свойством дискретности, так как весь алгоритм разбит на отдельные части (на блок-схеме это хорошо видно).
Доказать детерминированность алгоритма, достаточно сложно, например, когда алгоритм содержит части, которые выполняются параллельно, но не будем сейчас на этом останавливаться. Скажем, что в данном случае программа является детерминированной, т.к. не содержит фрагментов, зависящих от времени выполнения, т.е. сколько бы мы не тестировали алгоритм на одной и той же строке результат не изменится.
Чтобы показать результативность алгоритма, в данном случае достаточно заметить, что любой путь из начальной вершины в конечную содержит блок вывода результата. Перед блоком «конец» алгоритм содержит лишь 2 альтернативные ветви, каждая из которых выводит некоторый результат.
Алгоритм обладает свойством массовости, т.к. исходными данными для него может быть любая конечная последовательность символов. Алгоритм не обладал бы этим свойством, если бы работал лишь ограниченном наборе исходных данных, например на строках «()» и «())», но на остальных наборах не работал или работал не правильно.
Проверить свойство правильности алгоритма достаточно просто, для этого можно взять несколько примеров исходных данных, для которых результат очевиден и протестировать алгоритм на них, но доказать правильность алгоритма достаточно сложно. Доказательство правильности называется верификацией и явно выходит за рамки этой статьи.
В этой статье мы разобрались с тем, что такое алгоритм и какими основными свойствами он должен обладать. К теме алгоритмов я обязательно вернусь в будущих статьях.
Информатика. 11 класс
Конспект урока
Информатика, 11 класс. Урок № 1.
Тема — Понятие алгоритма. Свойства алгоритма. Способы записи алгоритма. Понятие сложности алгоритма
Перечень вопросов, рассматриваемых в теме: алгоритм, свойства алгоритма: дискретность, детерминированность, понятность, результативность, конечность, массовость, исполнитель алгоритма, сложность алгоритма
Глоссарий по теме: алгоритм, исполнитель алгоритма, дискретность, детерминированность, понятность, конечность, массовость, сложность алгоритма.
Основная литература по теме урока:
Л. Л. Босова, А. Ю. Босова. Информатика. Базовый уровень: учебник для 11 класса
— М.: БИНОМ. Лаборатория знаний, 2017
Дополнительная литература по теме урока:
К. Ю. Поляков, Е. А. Еремин. Информатика углубленный уровень: учебник для 10 класса: часть 2 — М.: БИНОМ. Лаборатория знаний, 2013
И. Г. Семакин, Т. Ю. Шеина, Л. В. Шестакова Информатика и ИКТ. Профильный уровень: учебник для 10 класса — М.: БИНОМ. Лаборатория знаний, 2010
Теоретический материал для самостоятельного изучения
На протяжении всей жизни, в учебе, на работе или в быту человек сталкивается с необходимостью решения огромного количества задач.
Для решения любой задачи надо знать, что дано и что следует получить. Для получения результатов необходимо знать способ решения задачи, т. е. располагать алгоритмом.
Алгоритм — это точная конечная система предписаний, определяющая содержание и порядок действий исполнителя над некоторыми объектами для получения искомого результата.
Исполнитель алгоритма — это субъект или устройство, способные правильно интерпретировать описание алгоритма и выполнить содержащийся в нем перечень действий.
Исполнители бывают неформальными и формальными.
В информатике рассматривают только формальных исполнителей, которые не понимают и не могут понять смысл даваемых команд. К этому типу относятся все технические устройства, в том числе и компьютер.
Дискретность — алгоритм состоит из отдельных команд, каждая из которых выполняется за конечное число шагов.
Детерминированность (или определенность) — при каждом запуске алгоритма с одними и теми же исходными данными должен быть получен один и тот же результат.
Понятность — алгоритм содержит только те команды, которые входят в систему команд исполнителя, для которого он предназначен.
Конечность (или результативность) — для корректного набора данных алгоритм должен завершиться через конечное время с вполне определенным результатом. При этом результатом может быть и сообщение о том, что задача не имеет решений.
Массовость — алгоритм предназначен для решения не одной частной задачи, а для некоторого класса задач.
Способы записи алгоритмов
Алгоритмы можно записывать разными способами:
— на естественном языке;
— графически в виде блок-схем;
— в виде программы на каком-либо языке программирования.
Если задача имеет алгоритмическое решение вообще, то можно придумать множество алгоритмов ее решения. Критерием выбора наилучшего алгоритма является сложность алгоритма — количество элементарных действий, которые выполняет исполнитель при решении задачи, пользуясь данным алгоритмом.
Сложность алгоритма принято обозначать O(n) (читается «О большое от эн»).
Сложность алгоритма выражают в виде функции от объема входных данных.
Лучшим считается алгоритм, имеющий наименьшую сложность.
Информатика. 11 класс
Конспект урока
Информатика, 11 класс. Урок № 1.
Тема — Понятие алгоритма. Свойства алгоритма. Способы записи алгоритма. Понятие сложности алгоритма
Перечень вопросов, рассматриваемых в теме: алгоритм, свойства алгоритма: дискретность, детерминированность, понятность, результативность, конечность, массовость, исполнитель алгоритма, сложность алгоритма
Глоссарий по теме: алгоритм, исполнитель алгоритма, дискретность, детерминированность, понятность, конечность, массовость, сложность алгоритма.
Основная литература по теме урока:
Л. Л. Босова, А. Ю. Босова. Информатика. Базовый уровень: учебник для 11 класса
— М.: БИНОМ. Лаборатория знаний, 2017
Дополнительная литература по теме урока:
К. Ю. Поляков, Е. А. Еремин. Информатика углубленный уровень: учебник для 10 класса: часть 2 — М.: БИНОМ. Лаборатория знаний, 2013
И. Г. Семакин, Т. Ю. Шеина, Л. В. Шестакова Информатика и ИКТ. Профильный уровень: учебник для 10 класса — М.: БИНОМ. Лаборатория знаний, 2010
Теоретический материал для самостоятельного изучения
На протяжении всей жизни, в учебе, на работе или в быту человек сталкивается с необходимостью решения огромного количества задач.
Для решения любой задачи надо знать, что дано и что следует получить. Для получения результатов необходимо знать способ решения задачи, т. е. располагать алгоритмом.
Алгоритм — это точная конечная система предписаний, определяющая содержание и порядок действий исполнителя над некоторыми объектами для получения искомого результата.
Исполнитель алгоритма — это субъект или устройство, способные правильно интерпретировать описание алгоритма и выполнить содержащийся в нем перечень действий.
Исполнители бывают неформальными и формальными.
В информатике рассматривают только формальных исполнителей, которые не понимают и не могут понять смысл даваемых команд. К этому типу относятся все технические устройства, в том числе и компьютер.
Дискретность — алгоритм состоит из отдельных команд, каждая из которых выполняется за конечное число шагов.
Детерминированность (или определенность) — при каждом запуске алгоритма с одними и теми же исходными данными должен быть получен один и тот же результат.
Понятность — алгоритм содержит только те команды, которые входят в систему команд исполнителя, для которого он предназначен.
Конечность (или результативность) — для корректного набора данных алгоритм должен завершиться через конечное время с вполне определенным результатом. При этом результатом может быть и сообщение о том, что задача не имеет решений.
Массовость — алгоритм предназначен для решения не одной частной задачи, а для некоторого класса задач.
Способы записи алгоритмов
Алгоритмы можно записывать разными способами:
— на естественном языке;
— графически в виде блок-схем;
— в виде программы на каком-либо языке программирования.
Если задача имеет алгоритмическое решение вообще, то можно придумать множество алгоритмов ее решения. Критерием выбора наилучшего алгоритма является сложность алгоритма — количество элементарных действий, которые выполняет исполнитель при решении задачи, пользуясь данным алгоритмом.
Сложность алгоритма принято обозначать O(n) (читается «О большое от эн»).
Сложность алгоритма выражают в виде функции от объема входных данных.
Лучшим считается алгоритм, имеющий наименьшую сложность.
Свойства алгоритмов
Статья расскажет о происхождении термина «Алгоритм» и о том, какими свойствами он обладает.
Алгоритмом называют определенную конечную последовательность действий (набор инструкций), выполнение которых приводит к достижению конкретной цели (решению поставленной задачи). В литературе по информатике, как и на просторах глобальной сети, можно найти множество общей теоретической информации относительно понятия и решения алгоритма. Достаточно запомнить основную мысль: достижение алгоритмического результата обеспечивается выполнением определенной последовательности действий (чаще всего, действий арифметических или логических).
История возникновения термина
Сегодня это понятие является фундаментальным и в математике, и в информатике. Однако сам термин возник задолго до появления компьютеров и прочих электронных средств вычислительной техники. Впервые об алгоритме заговорили в средние века — именно тогда европейские ученые ознакомились с методами вычисления арифметических действий, производимых в десятичной системе счисления азиатским математиком по имени Мухаммед ибн Муса аль-Хорезми (от имени этого математика и сформировался термин Algorithm). Сочинение аль-Хорезми перевели, а в последующие столетия появилось много трудов, посвященных вопросу обучения искусству счёта посредством цифр. Можно вспомнить описание алгоритма в европейской науке в те годы:
Также значение слова «алгоритм» сегодня нередко связывают со значениями таких слов, как «рецепт», «метод», «процесс», «инструкция».
Исполнитель и программа
Судя по историческим справкам, изначально речь шла о способе выполнения арифметических действий над десятичными числами. Прошли годы. Понятие стали применять при обозначении любой последовательности действий, которая приводит к получению требуемого результата. Причем алгоритмы существуют не сами по себе — они предназначаются для конкретного исполнителя. Кто может выступать таким исполнителем: — человек; — роботизированное/автоматизированное устройство, механизм; — компьютер; — язык программирования и т. д.
Отличительная черта исполнителя — способность выполнять команды, которые включены в алгоритм. Это становится возможным, благодаря описанию последнего на формальном языке, который исключает неоднозначность толкования. Множество команд задано изначально строго и является конечным. Действия, которые должен выполнить исполнитель, называют элементарными действиями, а сама запись алгоритмической последовательности на формальном языке — это программа. Разработка алгоритма в целях решения задачи — это алгоритмизация.
Главные характеристики
Выделяют следующие свойства алгоритма: массовость, дискретность, результативность, определенность, понятность, формальность, завершаемость. Будет не лишним рассмотреть их более подробно, дав каждому свойству алгоритма пояснение: 1. Массовость (универсальность). Благодаря этому свойству, алгоритм можно успешно применять к различным наборам исходных данных. Пусть существует запись некой абстрактной последовательности, выраженная формулой. Подставляя в эту формулу значения (каждый раз новые), пользователь будет получать верные решения в соответствии с определенным алгоритмом действий. 2. Дискретность (разрывность). Это свойство характеризует структуру. Каждая алгоритмическая последовательность действий делится на этапы (шаги), а процесс решения задачи — это последовательное исполнение простых шагов. Также дискретность обозначает, что для выполнения каждого этапа потребуется конечный временной отрезок (исходные данные преобразуются во времени в результат дискретно). 3. Определенность (точность, детерминированность) — это свойство указывает алгоритму, что каждый его шаг должен быть строго определенным, то есть различные толкования должны быть исключены. Строго определяется и порядок выполнения шагов. В результате каждый шаг определяется состоянием системы однозначно, когда четко понятно, какая команда станет выполняться на следующем шаге. Как итог — при любом исполнителе для одних и тех же исходных данных при выполнении одной и той же цепочки команд будет выдаваться одинаковый результат. Да, существуют вероятностные алгоритмы — в них на последующий шаг влияют как текущее состояние системы, так и генерируемое случайное число. Но при включении способа генерации рандомных чисел в перечень «исходных данных», вероятностный алгоритм превращается в подвид обычного. 4. Понятность. Должны быть включены лишь те команды, которые доступны и понятны исполнителю, то есть входят в систему его команд. 5. Формальность. Любой исполнитель действует формально и лишь выполняет инструкции, не вникая в смысл. Он не отвлекается от поставленной задачи и не рассуждает, зачем и почему они нужны. Рассуждениями занимается разработчик алгоритма, задача же исполнителя — просто исполнить предложенные команды и получить результат. «Приказы не обсуждают, а выполняют». 6. Завершаемость (конечность). Если исходные данные заданы корректно, алгоритм завершит свое действие и выдаст результат за конечное число шагов. 7. Результативность. Согласно этому свойству, любой алгоритм должен завершаться конкретными результатами.
Основные виды алгоритмов
В информатике и программировании выделяют много видов алгоритмов. Основные из них: — линейные (команды выполняются последовательно, одна за одной); — разветвляющиеся (есть условие, при проверке которого возможно разветвление на несколько параллельных ветвей); — циклические (предусматривается многократное повторение одних и тех же действий).
Что такое дискретность алгоритма
Дадим краткую характеристику каждого свойства.
Элементарность шагов означает, что объем работы, выполняемой на любом шаге, мажорируется некоторой константой, зависящей от характеристик исполнителя алгоритмов, но не зависящей от входных данных и промежуточных значений, получаемых алгоритмом. Для численных алгоритмов такими элементарными шагами могут быть, например, сложение, вычитание, умножение, деление, сравнение двух 32-разрядных чисел, пересылка одного числа из некоторого места памяти в другое. К элементарным шагам не относится сравнение двух файлов, так как время сравнения зависит от длины файлов, а длина потенциально неограниченна.
Определенность (детерминированность) алгоритма означает, что для каждого шага могут быть по набору исходных для этого шага данных однозначно вычислены результаты выполнения шага, и эти результаты не зависят ни от каких случайных факторов. Соответственно этому и алгоритм в целом по окончании работы исполнителя выдает вполне определенный результат.
Конечность (финитность) алгоритма означает, что для получения результата нужно выполнить конечное число шагов, т. е. исполнитель в некоторый момент времени останавливается. Требуемое число шагов зависит от входных данных алгоритма и не мажорируется константой.
Массовость означает, что входные данные для алгоритма могут выбираться из некоторого множества значений. Если же входные данные уникальны, то алгоритм в силу свойства определенности (детерминированности) будет давать всегда один и тот же результат и само построение алгоритма теряет смысл.
Таким образом, понятия алгоритма и данных двойственны, их определения рекурсивны: в формулировке понятия алгоритма использовались понятия данных, а они, в свою очередь, определяются с использованием понятия алгоритма, и т. д. Это определяет равную важность двух понятий в компьютерных науках, что отражается и в современных языках программирования.
Алгоритм является предписанием, а наличие предписания предполагает, что результат будет получен неким исполнителем, действующим по этому предписанию. Исполнитель (компьютер или программист, вручную отлаживающий свою программу) получает предписание и исходные данные. После этого он начинает действовать как автомат, т.е. выполнять в реальном времени описанные в алгоритме шаги. В результате выполнения каждого шага могут образовываться промежуточные результаты, которые исполнитель должен где-то фиксировать так, чтобы они могли быть использованы в качестве исходных данных для следующего шага. Исполнитель совершит конечное число шагов (даже если отдельные описания шагов использовались неоднократно) и после этого остановится, зафиксировав окончательный результат подобно промежуточным результатам.
Если есть текст некоторого предписания, то нужно убедиться в том, что это предписание является алгоритмом. Для этого необходимо проверить, выполняются ли перечисленные выше свойства.
Рассмотрим такую проверку на примере следующего текста (отыскание максимального и минимального элементов массива):
Проверим выполнение основных свойств.
До значения k = 4372 шаги строго чередуются, затем начинается отрезок нерегулярного изменения, на котором имеется 20 четных и 8 нечетных чисел, и заканчивается процесс «хвостом» из степеней двойки.
В целом вопрос о конечности этого алгоритма должен решаться методами теории чисел. Несмотря на ряд усилий, предпринимавшихся математиками, решение пока не найдено. Более подробный анализ задачи можно найти в книге Ю. Нивергельт, Дж. Фаррар, Э. Рейнгольд «Машинный подход к решению математических задач» (М.: Мир, 1977. С. 298).