Свойство алгоритма детерминированность означает что

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

Существует множество определений понятия «алгоритм»:

Из определений вытекают свойства алгоритма [5]:

Теперь покажем, что конкретный алгоритм обладает этими свойствами. В качестве примера, возьмем алгоритм, изображенный на рис. 1 в виде блок-схемы [6].

Рис 1 Блок-схема алгоритма проверки правильности расстановки скобок

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

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

Можно сказать, что алгоритм обладает свойством дискретности, так как весь алгоритм разбит на отдельные части (на блок-схеме это хорошо видно).

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

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

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

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

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

Источник

Студентик.РФ

Алгоритмы

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

Алгоритм обладает следующими основными свойствами:

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

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

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

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

Источник

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

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

Содержание

Недетерминированный алгоритм

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

Использование

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

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

Примеры

Список покупок

Представим список покупок: список товаров для покупки.

Это можно осмыслить двумя способами:

Сортировка слиянием

Допустим мы имеем набор сущностей (скажем, 300 студенческих экзаменов), которые необходимо отсортировать (скажем, по номерам студентов).

Один из алгоритмов для этого (называется Сортировка слиянием):

Тест простоты

Задача: дано натуральное число больше единицы, определить является ли это число простым.

Недетерминированный алгоритм следующий:

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

Этот алгоритм недетерминированный, он не всегда выдаёт верное решение, но только при определённой комбинации выборов. Это пример поискового типа недетерминированного алгоритма.

См. также

Полезное

Смотреть что такое «Детерминированный алгоритм» в других словарях:

Алгоритм Шенкса — (англ. Baby step giant step; также называемый алгоритм больших и малых шагов) в теории групп, детерминированный алгоритм дискретного логарифмирования в кольце вычетов по модулю простого числа. Для модулей специального вида данный… … Википедия

Алгоритм Полига — Хеллмана — Алгоритм Полига Хеллмана (также называемый алгоритм Силвера Полига Хеллмана) детерминированный алгоритм дискретного логирифмирования в кольце вычетов по модулю простого числа. Для модулей специального вида данный алгоритм… … Википедия

Алгоритм Полига-Хеллмана — (также называемый алгоритм Силвера Полига Хеллмана) детерминированный алгоритм дискретного логирифмирования в кольце вычетов по модулю простого числа. Для модулей специального вида данный алгоритм является полиномиальным. Содержание 1 История… … Википедия

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

алгоритм — а, м. algorithme m. 1230 algorisme. Лексис.1. В математике общепонятное предписание, определяющее детерминированный вычислительный процесс, ведущий от исходных данных к искомому результату. БАС 2. Алгебра логика математики; алгоритм ее… … Исторический словарь галлицизмов русского языка

Алгоритм — У этого термина существуют и другие значения, см. Алгоритм (значения). Для улучшения этой статьи желательно?: Переработать оформление в соответствии с правил … Википедия

древовидный алгоритм — 05.02.59 древовидный алгоритм [ tree algorithm]: Детерминированный алгоритм, используемый устройством считывания/опроса, при котором после обнаружения коллизии сигналов радиочастотных меток осуществляется поиск по доступному пространству… … Словарь-справочник терминов нормативно-технической документации

Вероятностный алгоритм — В теории алгоритмов классом сложности BPP (от англ. bounded error, probabilistic, polynomial) называется класс предикатов, быстро (за полиномиальное время) вычислимых и дающих ответ с высокой вероятностью (причём, жертвуя временем, можно добиться … Википедия

Список алгоритмов — Эта страница информационный список. Основная статья: Алгоритм Ниже приводится список алгоритмов, группированный по категориям. Более детальные сведения приводятся в списке структур данных и … Википедия

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

Источник

Информатика. 11 класс

Тезаурус

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

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

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

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

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

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

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

Сложность алгоритма — количество элементарных шагов в вычислительном процессе этого алгоритма.

Список литературы

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

— Л. Л. Босова, А. Ю. Босова. Информатика. Базовый уровень: учебник для 11 класса — М.: БИНОМ. Лаборатория знаний, 2017

Дополнительная литература по теме урока:

— К. Ю. Поляков, Е. А. Еремин. Информатика углубленный уровень: учебник для 10 класса: часть 2 — М.: БИНОМ. Лаборатория знаний, 2013

— И. Г. Семакин, Т. Ю. Шеина, Л. В. Шестакова. Информатика и ИКТ. Профильный уровень: учебник для 10 класса — М.: БИНОМ. Лаборатория знаний, 2010

Источник

Презентация к уроку

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

Задачи урока:

Дидактические: Обеспечить условия:

Воспитательные: Обеспечить условия:

Развивающие: Обеспечить условия:

Демонстрационный материал к уроку:

Ход урока

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

Появление алгоритмов связывают с зарождением математики.

Более 1000 лет назад (825 г.)ученый из города Хорезма Абдулла (или Абу Ждафар) Мухаммед бен Мусса аль-Хорезми создал книгу по математике, в тором описал способы выполнения арифметических действий над многозначными числами.

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

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

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

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

Пример: Алгоритм «Зарядка»

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

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

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

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

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

Линейный алгоритм – это такой, в котором все операции выполняются

последовательно одна за другой.

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

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

Полная форма

Неполная форма

Пример: Если на улице дождь, то останемся дома, а если нет то идем гулять.

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

Цикл с известным числом повторений

Цикл с известным числом повторений часто называют «циклом ДЛЯ»

Пример: Алгоритм «Упражнение для глаз»

Цикл с постусловием

Цикл с неизвестным числом повторений, в тором выход из цикла осуществляется при выполнении условия, принято называть «циклом с постусловием» или «циклом ПРИ»

Цикл с предусловием

Цикл с известным числом повторений, в котором цикл продолжается, пока выполняется условие, принято называть «циклом с предусловием» или «циклом ПОКА»

Источник