Виды алгоритмов как логико-математических средств, характеристика свойств. Корректный вывод алгоритма при решении вычислительной задачи. Механизм реализации алгоритма, его описание. Решение задачи Майхилла при помощи автоматной модели поведения стрелка.
Краткое сожержание материала:

Размещено на

Курсовая работа

по дисциплине: "Теория вычислительных процессов"

на тему:

"Виды и свойства алгоритмов. Решение задачи Майхилла (о стрелках)"

Содержание

• Введение
• 1. Теоретический вопрос "Виды и свойства алгоритмов"
• 1.1 Виды алгоритмов
• 1.2 Свойства алгоритмов
• 2. Решение задачи Майхилла (о стрелках)
• 2.1 Постановка задачи
• 2.2 Решение задачи
• Заключение
• Список использованных источников

Введение

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

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

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

Алгоритм может быть задан на естественном языке, в виде компьютерной программы или даже воплощен в аппаратном обеспечении. Единственное требование - его спецификация должна предоставлять точное описание вычислительной процедуры, которую требуется выполнить. [1, С.46-47]

1. Теоретический вопрос "Виды и свойства алгоритмов"

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

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

Первый тип связывает понятие алгоритма с наиболее традиционными понятиями математики - вычислениями и числовыми функциями. Наиболее развитая и изученная модель этого типа - рекурсивные функции - является исторически первой формализацией понятия алгоритма.

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

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

Впрочем, модели второго и третьего типа довольно близки (их взаимная сводимость доказывается просто). [2, С.154-155]

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

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

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

· гибкий алгоритм, т.е. вероятностный и эвристический;

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

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

· линейный алгоритм - набор команд (указаний), выполняемых последовательно во времени друг за другом;

· разветвляющийся алгоритм - алгоритм, содержащий хотя бы одно условие, в результате проверки которого ЭВМ обеспечивает переход на один из двух возможных шагов;

· циклический алгоритм - алгоритм, предусматривающий многократное повторение одного и того же действия (одних и тех же операций) над новыми исходными данными. К циклическим алгоритмам сводится большинство методов вычислений, перебора вариантов. [3]

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

Для алгоритмов характерны общие черты и особенности.

1. Дискретность

Применение каждого алгоритма осуществляется путем выполнения дискретной цепочки (последовательности) неких элементарных действий. Эти действия называют шагами, а процесс их выполнения называют алгоритмическим процессом [4, С.314].

2. Детерминированность (определенность)

Каждый шаг алгоритма должен быть точно определен. Действия, которые нужно выполнить, должны быть строго и недвусмысленно определены для каждого конкретного случая. Предписания алгоритма единственным и вполне определенным путем всякий раз приводят к искомому результату. Для описания алгоритмов были разработаны формально определенные языки программирования, или машинные языки, в которых каждый оператор имеет строго определенное значение [5, С.23-24].

3. Результативность

Данное свойство требует от алгоритма остановки после конечного числа шагов (зависящего от данных) с указанием того, что считать результатом. В частности, всякий, кто предъявляет алгоритм решения некоторой задачи, например вычисления функции f (x), должен показать, что алгоритм останавливается после конечного числа шагов (говорят, сходится) для любого x из области задания f. Проверить результативность (сходимость) непросто. Сходимость обычно не удается установить простым просмотром описания алгоритма; общего же метода проверки сходимости, пригодного для любого алгоритма А и любых данных х, не существует [2, С.149].

4. Массовость

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

5. Допустимость начальных данных

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

Среди допустимых начальных данных для алгоритма могут быть такие, к которым он применим, т.е. отправляясь oт которых можно получить искомый результат, а могут быть и такие, к которым данный алгоритм неприменим, т.е. отправляясь от которых искомого результата получить нельзя. Неприменимость алгоритма к допустимым начальным данным может заключаться либо в том, что алгоритмический процесс никогда не оканчивается, либо в том, что его выполнение во время одного из шагов наталкивается на препятствие, заходит в тупик. [4, С.314-315]

Также следует различать: