Основы алгоритмизации вычислительных процессов: основные понятия теории алгоритмов, свойства и виды алгоритмов

Теория алгоритмов- это раздел математики, который
изучает общие свойства алгоритмов.

Понятие «алгоритм» сформировалось
в математике в 20-х гг. XX
века. Началом систематической теории алгоритмов стала работа А. А. Черча 1936
г.

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

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

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

Основой теоретических
исследований послужили 3 основных арифметических модели:

1. Арифметизация алгоритмов

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

2. Абстрактная машина Тьюрена.

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

3. Нормативные алгоритмы Маркова.

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

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

Задача называется алгоритмически
неразрешимой, если не существует абстрактной машины Тьюринга, нормального
алгоритма Маркова, рекурсивной функции.

Определение алгоритма:

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

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

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

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

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

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

2. определенность алгоритма-
каждая команда алгоритма должна быть понятна исполнителю и не должна оставлять
места для неоднозначного толкования данного действия.

3. результативность- алгоритм
должен приводить к решению поставленной задачи за конечное число шагов.

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

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

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

1. механические алгоритмы
(детерминированные) задают определенные действия в единственной и достоверной
последовательности (однозначные решения).

2. гибкие алгоритмы:А) вероятностные
(стохастические);

Б)
эвристические;

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

4. разветвляющиеся – содержат
хотя бы одно условие и предполагают выбор.

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

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

- доцент
- кандидат юридических наук
- профессор кафедры

Оцените автора
Добавить комментарий