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

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

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

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

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

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

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

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

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

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

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

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

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

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

Приведенное
определение не является определением
в математическом смысле слова, т.е. это
не формальное определение (формальное
определение алгоритма см. в статье
“Теория
алгоритмов”).

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

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

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

Соседние файлы в папке Билеты

• #
• #
• #
• #
• #
• #
• #
• #
• #
• #
• #

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

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

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

Процесс разработки алгоритма — достаточно сложный и трудоемкий.

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

Цель же, в свою очередь, является достижением желаемого результата.

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

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

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

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

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

Понятие алгоритма в теорию и практику обучения вошло в конце $50$-х годов прошлого столетия в связи с развитием программированного обучения и применением обучающимися машин.

Способы описания алгоритмов

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

• словесный (пошаговое описание);
• табличный и в виде формул;
• графический (в виде схем);
• с использованием псевдокода (алгоритмического языка).

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

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

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

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

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

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

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

1. Наличие ввода исходных данных.
2. Наличие вывода результата выполнения.
3. Однозначность, так как компьютеру понятны лишь однозначные инструкции.
4. Общность, в соответствии с которой алгоритм может использоваться не только для решения одной задачи, но и целого класса задач.
5. Корректность, согласно которой при выполнении алгоритма должно быть всегда правильное решение задачи.
6. Конечность означает, что решение задачи необходимо получить за конечное число шагов.
7. Эффективность означает, что для решения задачи необходимо использовать ограниченные ресурсы компьютера (объем оперативной памяти, процессорное время и т. д.).

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

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

Блок-схемы

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

Кроме того, в алгоритмах используются разветвляющие и циклические блоки.

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

Операторный блок (блок действия) содержит команды обработки данных.

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

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

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

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

• дискретностью;
• определенностью (детерминированностью, точностью);
• массовостью;
• результативностью;
• формальностью.

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

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

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

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

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

• Алгоритмы >>
• Главная страница >>