§ 1. Алгоритм и его свойства
Содержание
Алгоритм - это точно заданная система понятных исполнителю команд, выполнение которых позволяет решить задачу за конечное число шагов для любого допустимого набора исходных данных. Алгоритм обладает шестью основными свойствами: дискретностью, детерминированностью, понятностью, результативностью, конечностью и массовостью. Его можно записать в разных формах, а правильность работы проверить с помощью математического доказательства или специально подобранных тестов.
Что нужно понять
- Понятие алгоритма пришло в информатику из математики. Его название связано с именем математика IX века Мухаммеда ибн Мусы аль-Хорезми, описавшего правила основных арифметических действий.
- Алгоритм состоит из отдельных действий, которые исполнитель выполняет по установленным правилам. Каждое действие задаётся командой.
- Дискретность означает разделение алгоритма на отдельные шаги. Следующий шаг выполняется после завершения предыдущего.
- Детерминированность, или определённость, означает, что при одинаковых исходных данных и одинаковых командах алгоритм всегда даёт одинаковые промежуточные и конечные результаты.
- Понятность требует, чтобы команды были чёткими, полными и однозначными для исполнителя. Исполнитель не должен самостоятельно решать, как понимать указания.
- Результативность означает получение ответа на поставленную задачу. Допустимым ответом может быть установление того, что задача не имеет решения.
- Конечность означает, что выполнение алгоритма должно завершиться после конечного числа шагов. Это свойство тесно связано с результативностью.
- Массовость означает применимость алгоритма ко всему предусмотренному классу задач, а не только к одному набору исходных данных.
- Область применимости алгоритма определяет множество допустимых исходных данных, для которых предназначен алгоритм.
- Решето Эратосфена служит примером алгоритма нахождения простых чисел, не превышающих заданного числа N, путём последовательного исключения определённых чисел.
- Алгоритм можно представить текстовым описанием, блок-схемой и другими способами. Базовые алгоритмические конструкции: следование, ветвление и цикл.
- Правильность алгоритма проверяют математическим доказательством или специально подобранными тестами. Теория алгоритмов также рассматривает способы анализа эффективности алгоритмов.
Видео
7:12
Скачать к теме
Главное по теме
Алгоритм позволяет получать результат по заранее определённым правилам. Чтобы последовательность действий считалась алгоритмом, она должна обладать всеми шестью основными свойствами. Для построения алгоритмов используют следование, ветвление и цикл.
Ключевые понятия
Как это работает
Что нужно запомнить
- Алгоритм должен содержать точные и понятные исполнителю предписания.
- Шесть основных свойств алгоритма: дискретность, детерминированность, понятность, результативность, конечность и массовость.
- Дискретность связана с разделением действий на шаги, а детерминированность - с однозначностью получаемых результатов при одинаковых исходных данных.
- Понятность предполагает отсутствие неоднозначных команд и необходимости самостоятельного выбора действий исполнителем.
- Результативность требует получения определённого ответа. Отсутствие решения задачи тоже может быть результатом, если это предусмотрено алгоритмом.
- Конечность требует завершения работы за конечное число шагов.
- Массовость позволяет применять алгоритм к целому классу задач в пределах его области применимости.
- Следование, ветвление и цикл - базовые алгоритмические конструкции, которые используются независимо от формы записи алгоритма.
- Правильность алгоритма можно проверять математическим доказательством и специально подобранными тестами.
- Машина Тьюринга, машина Поста и нормальный алгоритм Маркова относятся к формальным моделям, предложенным в рамках развития теории алгоритмов.
Проверь себя
Что называют алгоритмом?
Какое свойство алгоритма означает получение одинаковых результатов при одинаковых исходных данных?
Какое свойство алгоритма нарушается, если команда требует самостоятельного выбора исполнителя?
Какие три базовые алгоритмические конструкции рассматриваются в теме?
Какие способы проверки правильности алгоритма указаны в учебном материале?