Алгоритмов и формальных языков

Понятие алгоритма. Свойства алгоритмов. Формы представления алгоритмов.

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

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

Понятие о формальных языках и порождающих грамматиках. Формальная грамматика как средство описания алгоритмических (формальных) языков.

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

Алгоритмическая полнота ЭВМ.

Алгоритмическая неразрешимость некоторых массовых проблем.

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

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

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

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

Формальность. Алгоритм не должен допускать неоднозначности толкования действий для исполнителя.

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

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

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

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

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