Теория алгоритмов. Основные понятия и определения

1.

Федеральное государственное бюджетное образовательное учреждение
высшего профессионального образования
«Ижевский государственный технический университет
имени М. Т. Калашникова»
Кафедра «АСОИУ»
Курс «Математическая логика и теория алгоритмов»
Тема «Теория алгоритмов. Основные понятия и
определения»
Автор Исенбаева Е.Н., старший преподаватель
Ижевск
2013

2. ОСНОВНЫЕ ТРЕБОВАНИЯ К АЛГОРИТМАМ

Алгоритм- эффективная
процедура, однозначно
приводящая к результату.
Курс «Математическая логика и теория алгоритмов»
Тема «Теория алгоритмов»
2

3. ОСНОВНЫЕ ТРЕБОВАНИЯ К АЛГОРИТМАМ

1.Каждый алгоритм имеет
данные- входные,
промежуточные и выходные.
Курс «Математическая логика и теория алгоритмов»
Тема «Теория алгоритмов»
3

4. ОСНОВНЫЕ ТРЕБОВАНИЯ К АЛГОРИТМАМ

Данные- объекты, с которыми
алгоритм сможет работать.
Объекты: числа, векторы, матрицы
смежности графа, формулы.
«Необъекты»: «хорошая книга»,
рисунок графа.
Курс «Математическая логика и теория алгоритмов»
Тема «Теория алгоритмов»
4

5. ОСНОВНЫЕ ТРЕБОВАНИЯ К АЛГОРИТМАМ

При построении данных
используются:
• алфавит- набор элементарных
объектов(цифры, буквы и т.д.);
• правила- средства построения
объектов из элементарных
Курс «Математическая логика и теория алгоритмов»
Тема «Теория алгоритмов»
5

6. ОСНОВНЫЕ ТРЕБОВАНИЯ К АЛГОРИТМАМ

Данные для своего размещения требуют
памяти.
Память обычно однородная и дискретная- состоит
из одинаковых ячеек.
Каждая ячейка может содержать один символ
алфавита данных.
2.
Единицы измерения
согласованы.
объема данных и памяти
Память может быть бесконечной.
Курс «Математическая логика и теория алгоритмов»
Тема «Теория алгоритмов»
6

7. ОСНОВНЫЕ ТРЕБОВАНИЯ К АЛГОРИТМАМ

3. Алгоритм состоит из отдельных
элементарных шагов, или
действий
Множество различных шагов
алгоритма- конечно.
Курс «Математическая логика и теория алгоритмов»
Тема «Теория алгоритмов»
7

8. ОСНОВНЫЕ ТРЕБОВАНИЯ К АЛГОРИТМАМ

4.
Последовательность
шагов
алгоритма детерминирована – т.е.
после
каждого
шага
либо
указывается, какой шаг делать
дальше, либо дается команда
остановки, после чего работа
алгоритма считается
законченной.
Курс «Математическая логика и теория алгоритмов»
Тема «Теория алгоритмов»
8

9. ОСНОВНЫЕ ТРЕБОВАНИЯ К АЛГОРИТМАМ

5. Результативность - остановка
после конечного числа шагов
(зависящего
от
данных)
с
указанием того, что считать
результатом.
Курс «Математическая логика и теория алгоритмов»
Тема «Теория алгоритмов»
9

10. ОСНОВНЫЕ ТРЕБОВАНИЯ К АЛГОРИТМАМ

6. Следует различать:
а) описание алгоритма
б) механизм реализации
алгоритма
в) процесс реализации
алгоритма
Курс «Математическая логика и теория алгоритмов»
Тема «Теория алгоритмов»
10

11. ОСНОВНЫЕ ТРЕБОВАНИЯ К АЛГОРИТМАМ

Описание алгоритма и механизм
его реализации конечны.
Требования к конечности
процесса реализации совпадают
с требованиями
результативности.
Курс «Математическая логика и теория алгоритмов»
Тема «Теория алгоритмов»
11

12. ПРИМЕР 1

Дана последовательность P из n
положительных чисел (n – конечное,
но произвольное число).
Требуется упорядочить их, т.е.
построить последовательность R, в
которой эти же числа расположены в
порядке возрастания.
Курс «Математическая логика и теория алгоритмов»
Тема «Теория алгоритмов»
12

13. ПРИМЕР 1

Разобьем способ решения на шаги и укажем
переходы между шагами.
Шаг 1. Ищем в P наименьшее число.
Шаг 2. Найденное число приписываем справа к
R и вычеркиваем его из P.
Шаг 3. Если в P нет чисел, то переходим к шагу 4.
Иначе, к шагу 1.
Шаг 4. Конец. Результатом считать последовательность
R, построенную к данному моменту.
Курс «Математическая логика и теория алгоритмов»
Тема «Теория алгоритмов»
13

14. ОСНОВНЫЕ ТРЕБОВАНИЯ К АЛГОРИТМАМ

Это описание- еще не алгоритм.
Необходимо
уточнить:
алфавит,
форму представления данных, память,
размещение в ней элементов Р и R,
элементарные шаги.
Выбор механизма реализации будет
влиять и на сам характер уточнения.
Курс «Математическая логика и теория алгоритмов»
Тема «Теория алгоритмов»
14

15. БЛОК - СХЕМЫ АЛГОРИТМОВ

Связи
между
шагами
можно
изобразить в виде графа. Для примера
1 граф изображен на рис. 1.
Рис. 1
Курс «Математическая логика и теория алгоритмов»
Тема «Теория алгоритмов»
15

16. БЛОК - СХЕМЫ АЛГОРИТМОВ

Блок- схема алгоритма- граф,
в
котором
вершинам
соответствуют шаги, а ребрампереходы между шагами.
Курс «Математическая логика и теория алгоритмов»
Тема «Теория алгоритмов»
16

17. БЛОК - СХЕМЫ АЛГОРИТМОВ

Виды вершин:
- вершины, из которых выходит одно
ребро( операторы);
-вершины, из которых выходит два ребра(
логические условия или предикаты);
- вершина начала( нет входных ребер,
одно выходное ребро);
- вершина конца( одно входное ребро, нет
выходных ребер).
Курс «Математическая логика и теория алгоритмов»
Тема «Теория алгоритмов»
17

18. БЛОК - СХЕМЫ АЛГОРИТМОВ

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

19. БЛОК - СХЕМЫ АЛГОРИТМОВ

Композиция алгоритма- соединение
алгоритмов.
Рис. 2
Курс «Математическая логика и теория алгоритмов»
Тема «Теория алгоритмов»
19

20. БЛОК - СХЕМЫ АЛГОРИТМОВ

Описание – это граф; процесс
реализации – это путь в графе.
Различные пути в одном и том же
графе возникают при различных
данных, которые создают разные
логические
условия
в
точках
разветвления.
Курс «Математическая логика и теория алгоритмов»
Тема «Теория алгоритмов»
20

21. ТИПЫ УНИВЕРСАЛЬНЫХ АЛГОРИТМИЧЕСКИХ МОДЕЛЕЙ

Алгоритмическая
модельформализация понятия «алгоритм».
Алгоритмические модели должны
быть
универсальными
(должны
допускать
описание
любых
алгоритмов).
Курс «Математическая логика и теория алгоритмов»
Тема «Теория алгоритмов»
21

22. ТИПЫ УНИВЕРСАЛЬНЫХ АЛГОРИТМИЧЕСКИХ МОДЕЛЕЙ

Первый тип связывает понятие алгоритма с
наиболее
традиционными
понятиями
математики – вычислениями и числовыми
функциями.
Наиболее развитая и изученная модель этого
типа – рекурсивные функции – является
исторически первой формализацией понятия
алгоритма.
Курс «Математическая логика и теория алгоритмов»
Тема «Теория алгоритмов»
22

23. ТИПЫ УНИВЕРСАЛЬНЫХ АЛГОРИТМИЧЕСКИХ МОДЕЛЕЙ

Второй тип - машина Тьюринга основан
на
представлении
об
алгоритме,
как
о
некотором
детерминированном
устройстве,
способном выполнять в каждый
отдельный момент лишь весьма
примитивные операции.
Курс «Математическая логика и теория алгоритмов»
Тема «Теория алгоритмов»
23

24. ТИПЫ УНИВЕРСАЛЬНЫХ АЛГОРИТМИЧЕСКИХ МОДЕЛЕЙ

Третий тип алгоритмических моделей –
нормальные алгоритмы Маркова,
канонические системы Поста - это
преобразование слов в произвольных
алфавитах, в которых элементарными
операциями являются подстановки замена части слова (подслова) другим
словом.
Курс «Математическая логика и теория алгоритмов»
Тема «Теория алгоритмов»
24

25.

СПАСИБО ЗА ВНИМАНИЕ
© ФГБОУ ВПО ИжГТУ имени М.Т. Калашникова, 2013
© Исенбаева Елена Насимьяновна, 2013