Перейти к содержимому
10 класс
НОВОЕ
Новости
Новости сайта
Тарифы
Информатика 10 класс · § §1

§ 1. Алгоритм и его свойства

Содержание
Главное за минуту

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

Что нужно понять

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

Видео

Превью видео по теме «§ 1. Алгоритм и его свойства» - Информатика, 10 класс 7:12
Видео доступно после бесплатной регистрации.

Скачать к теме

Материалы по теме доступны после бесплатной регистрации.

Главное по теме

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

Ключевые понятия

Алгоритм Точно определённая система понятных исполнителю предписаний, выполнение которых позволяет получить решение задачи для любого допустимого набора исходных данных за конечное число шагов.
Команда Указание исполнителю, предписывающее выполнить отдельное действие алгоритма.
Простая команда Команда, принадлежащая системе команд исполнителя. Другие команды могут быть определены через простые.
Дискретность Свойство алгоритма, согласно которому процесс его выполнения разделяется на отдельные последовательные шаги. Каждый следующий шаг выполняется после завершения предыдущего.
Детерминированность Свойство алгоритма, при котором одинаковые исходные данные всегда приводят к одним и тем же промежуточным и конечным результатам. Результат определяется входными данными и командами алгоритма.
Понятность Свойство алгоритма, требующее чёткой, полной и однозначной записи команд, которые исполнитель способен выполнить без самостоятельного выбора их смысла.
Результативность Свойство алгоритма, согласно которому точное выполнение его команд должно приводить к определённому ответу на поставленную задачу, в том числе к установлению отсутствия решения.
Конечность Свойство алгоритма, требующее завершения его выполнения за конечное число шагов с получением результата.
Массовость Свойство алгоритма, позволяющее использовать его для решения любой задачи из определённого класса при допустимых исходных данных.
Область применимости алгоритма Множество исходных данных, для которых предназначен данный алгоритм.
Решето Эратосфена Алгоритм нахождения простых чисел, не превышающих заданного числа N, основанный на последовательном вычёркивании чисел по определённым правилам.

Как это работает

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

Что нужно запомнить

  • Алгоритм должен содержать точные и понятные исполнителю предписания.
  • Шесть основных свойств алгоритма: дискретность, детерминированность, понятность, результативность, конечность и массовость.
  • Дискретность связана с разделением действий на шаги, а детерминированность - с однозначностью получаемых результатов при одинаковых исходных данных.
  • Понятность предполагает отсутствие неоднозначных команд и необходимости самостоятельного выбора действий исполнителем.
  • Результативность требует получения определённого ответа. Отсутствие решения задачи тоже может быть результатом, если это предусмотрено алгоритмом.
  • Конечность требует завершения работы за конечное число шагов.
  • Массовость позволяет применять алгоритм к целому классу задач в пределах его области применимости.
  • Следование, ветвление и цикл - базовые алгоритмические конструкции, которые используются независимо от формы записи алгоритма.
  • Правильность алгоритма можно проверять математическим доказательством и специально подобранными тестами.
  • Машина Тьюринга, машина Поста и нормальный алгоритм Маркова относятся к формальным моделям, предложенным в рамках развития теории алгоритмов.

Проверь себя

Вопрос 1 из 5

Что называют алгоритмом?

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

Какое свойство алгоритма означает получение одинаковых результатов при одинаковых исходных данных?

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

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

Команды алгоритма должны быть чёткими и однозначными. Если исполнитель самостоятельно определяет смысл указания, нарушается понятность.
Вопрос 4 из 5

Какие три базовые алгоритмические конструкции рассматриваются в теме?

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

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

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