Языки программирования

ВИДЫ И СВОЙСТВА АЛГОРИТМА.

ТЕМА 5. АЛГОРИТМ.

5.1. Алгоритм: определение, виды и свойства

.

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

Почти во всех сферах жизни нам приходится иметь дело с инструкциями, в соответствии с которыми можно и нужно что-то сделать. Еще в IX веке появилось понятие «алгоритм», которое стало одним из основных понятий математики (от имени среднеазиатского математика Аль-Хорезми). Сейчас, в общем смысле алгоритм – это понятное и точное предписание исполнителю совершить определенную последовательность действий для достижения указанной цели или решения поставленной задачи.

Алгоритм является одним из основных понятий современной математики.

Ещё в начале своего развития математика встречалась с такими вычислениями, которые выполнялись чисто механическими способами. Эти виды вычислений получили название а л г о р и т м о в по имени математика Алго Резми (Аль Хорезми), основоположника четырёх математических действий: «+», «-», «*», «/».

Долгое время математики довольствовались следующим определением:

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

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

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

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

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

Применительно к ЭВМ:

Алгоритм – это точное, сформулированное на определенном языке, конечное описание того или иного общего метода, основанного на применении исполнимых элементарных тактов обработки.

Известны основные особенности алгоритма:

1. массовость - один и тот же алгоритм может применяться для решения целого класса однотипных задач, различающихся исходными данными;

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

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

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

Применимо к ЭВМ различают следующие виды алгоритмов:

последовательные – элементарные такты обработки выполняются один за другим;

параллельные – элементарные такты выполняются одновременно;

коллатеральные – разрешено как последовательное, так и параллельное выполнение операций;

терминистические (завершающиеся) – имеющие конечное число элементарных тактов обработки. От алгоритма требуется, чтобы он обязательно заканчивался. Если нет свободы в выборе очередного шага обработки – говорят о детерминистическом алгоритме.

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

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

Способы записи алгоритмов:

1. на языке алгоритма;

2. графический: блок-схема, сети и диаграммы, например сети Петри;

3. на языке программирования.

Дата добавления: 2014-01-06