Элементы теоретического программирования Что такое алгоритм? - презентация

1 Элементы теоретического программирования Что такое алгоритм?

2 Класс однотипных задач называют общей задачей При подстановке вместо параметров конкретных значений получаем частную задачу

3 Что такое алгоритм? Общий метод, позволяющий для любой задачи данного класса в конечное число шагов дать ответ «да» или «нет», называют проблемой разрешения для этого класса задач. Общий метод, если он существует, называется разрешающей процедурой, разрешающим алгоритмом или просто алгоритмом.

4 Что такое алгоритм? Вопрос: «Существует ли общий метод, позволяющий для каждой частной задачи данного класса в конечное число шагов дать требуемый ответ», называется проблемой вычисления. Искомый общий метод, если он существует, называется вычислительной процедурой, вычислительным алгоритмом, или просто алгоритмом.

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

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

7 2. Понятное предписание Это не только предписание, выраженное на понятном исполнителю языке. Предусмотренные предписанием действия должны быть выполнимыми определенной категорией исполнителей, которым оно адресовано. Иначе говоря, чтобы эти действия принадлежали системе действий исполнителя.

8 2. Понятное предписание Под системой действий исполнителя понимают совокупность действий, которые он умеет выполнять. Чтобы предписание, задающее алгоритм, было понятным, оно должно быть конечным, т. е. выражено с помощью конечного текста. Бесконечно длинные предписания исключаются ввиду того, что они принципиально не допускают передачи исполнителю.

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

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

11 4. Решить любую задачу Во-вторых, «решить задачу» означает решить ее «за конечное число шагов». Получение результата за конечное число шагов составляет свойство результативности алгоритма.

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

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

14 5. Класс однотипных задач Класс однотипных задач или общая задача обычно формулируется (в математике) с использованием некоторых переменных параметров.

15 6. Конструктивные объекты Исходные объекты, промежуточные и окончательные результаты конструктивные объекты. Эти объекты могут быть построены целиком или допускают кодирование посредством слов в некоторых конечных алфавитах

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

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

18 Способы записи алгоритмов Словесный Блок-схема Алгоритмическая запись