Необходимость формального определения алгоритма. Лекция 5а

1.

2.

1.3.Теория алгоритмов
Раздел
Лекции
ПЗ
СРС
Всего
часов
1.3.Теория
алгоритмов
8
14
9
31

3.

Литература
• Теория алгоритмов. Учебное пособие для
студентов ВУЗов/ В.Н. Крупский, В.Е. Плиско.М: Издательский центр “АКАДЕМИЯ”, 2009.208 c. (Университетский учебник. Серия
прикладная информатика и математика)
3

4.

Лекция 5а
Необходимость формального
определения алгоритма
Цель лекции:
Рассмотреть систематизированные основы знаний
по основам математической теории алгоритмов
4

5.

Учебные вопросы:
1. Основные понятия и проблемы
теории алгоритмов
5

6.

1. Основные понятия и проблемы теории
алгоритмов
Понятия алгоритма в интуитивном смысле было достаточно
и в своей основе оно не менялось до 30 годов XX века , так
как для определения является ли объект алгоритмом или
нет, достаточно знать свойства алгоритма:
A. Aлгоритм– это процесс последовательного построения
величин, идущий в дискретном времени таким образом, что
в начальный момент задается исходная система величин, а
в каждый следующий момент система величин получается
по определенному закону (программе из системы величин,
имевшихся в предыдущий момент времени (дискретность
алгоритма));
6

7.

Б) Система величин, получаемых в какой-то (не начальный)
момент времени, однозначно определяется системой
величин, полученных в предшествующие моменты времени
(детерминированность);
В) Закон получения последующей величины из
предшествующей должен быть простым и локальным
(элементарность шагов алгоритма);
Г) если способ получения последующей величины из какойнибудь заданной величины не дает результата, то должно
быть указано, что надо считать результатом алгоритма
(направленность алгоритма);
Д) начальная система величин может выбираться из
некоторого потенциально бесконечного множества
(массовость алгоритма)
7

8.

Причины необходимости формального определения
алгоритма:
- усложнение объектов, которыми оперировали
алгоритмы (векторами, матрицами, множествами,
функциями),
- определение элементарности шагов алгоритма
(например, можно ли считать элементарным шагом
взятие интеграла или транспонирование матрицы?),
-что понимать конечностью и однозначностью
алгоритма,
-все ли задачи имеют алгоритмическое
решение?
8

9.

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

10.

В середине 30-х годов XX века была решена задача
точного определения алгоритмов математиками:
Дави́д Ги́льберт (23 января 1862 — 14
февраля 1943) — выдающийся немецкий
математик-универсал, внёс значительный
вклад в развитие многих математических
разделов.
В 1900 году на Втором Международном
математическом конгрессе Гильберт
формулирует знаменитый список 23
нерешённых проблем математики,
послуживший направляющим указателем
приложения усилий математиков на
протяжении всего XX века.
10

11.

14 июня 1903 — 11 августа 1995
Алонзо Черч родился 14 июня 1903 года в
Вашингтоне, США.
Получил степень бакалавра в Принстонском
университете в 1924 году, и защитил
кандидатскую в 1927 году под руководством
Освальда Веблена.
В 1926 году Черч становится профессором
математики в Принстоне.
Слава пришла к Черчу после разработки
теории лямбда-исчислений.
11

12.

А́лан Матисон Тью́ринг (23 июня
1912 — 7 июня 1954) — английский
математик, логик, криптограф,
оказавший существенное влияние на
развитие информатики.
Предложенная им в 1936 году
абстрактная вычислительная
«Машина Тьюринга» позволила
формализовать понятие
алгоритма и до сих пор
используется во множестве
теоретических и практических
исследований.
12

13.

Пост, Эмиль Леон (англ. Post Emil
Leon, 11 февраля 1897, Августов
(Российская империя, ныне Польша)
— 21 апреля 1954, Нью-Йорк) —
американский математик и логик;
один из основателей многозначной
логики (1921);
основные труды по математической
логике: алгебра Поста, классы
Поста функций алгебры логики;
предложил абстрактную
вычислительную машину —
машину Поста.
13

14.

Сти́вен Ко́ул Кли́ни (правильнее — Кле́йни,
(5 января 1909, Хартфорд, Коннектикут, США
— 25 января 1994, Мэдисон, Висконсин,
США) — американский математик.
Его работы совместно с работами Алонзо
Чёрча, Курта Гёделя и Алана Тьюринга дали
начало разделу математической логики —
теории вычислимости.
Кроме того, известен изобретением
регулярных выражений. Его именем названы
Алгебра Клини, Звёздочка Клини, теорема
Клини о рекурсии, теорема Клини о
неподвижной точке.
Работал также в области интуиционистсткой
математики Брауэра.
Внёс важный вклад в теорию конечных
автоматов
14

15.

Андрей Андреевич Марков
[р. 9 (22) сент. 1903] — сов. математик, чл.корр. АН СССР (с 1953). Сын А. А. Маркова
(старшего). С 1935 — проф. Ленинградского
университета.
Автор исследований в области топологии,
топологич. алгебры (им построена теория
свободных топологич. групп), теории
алгоритмов, теории динамических систем и
др.
Доказал методами математической логики
невозможность алгоритмического решения
некоторых задач теории ассоциативных
систем и задач, относящихся к
целочисленным матрицам.
15

16.

Основной идеей всех решений было построение
алгоритмической модели, которая содержала бы
конечный набор конкретных шагов, способ
определения следующего шага, способ записи
шагов и т.д.
Поиск велся в 3-х направлениях, которые и
определили три типа алгоритмических моделей:
Первое направление основано на
арифметизации алгоритма, так как любые данные
можно закодировать целыми числами, то шаги
здесь – известные арифметические операции, а их
последовательность задается формулой.
16

17.

Сама формула строиться при помощи двух
приемов:
- суперпозиции;
- рекурсии.
Суперпозиция – подстановка одной формулы в
другую, то есть вводится набор элементарных
операций и с помощью подстановок строятся более
сложные выражения.
Например, (a b)+(c/d) – есть суперпозиция операций:
x+y, x y, x/y.
Рекурсия задает функции через самих себя. Например,
n!=F(n)=
1, n 0
.
n F (n 1), n 0
17

18.

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

19.

Второе направление основано на мысли, что
алгоритм – это то, что может быть выполнено
машиной. Э. Пост и А. Тьюринг, практически
одновременно (1936-37 г.г.) предложили
конструкции двух абстрактных машин, предложив
считать их алгоритмическими моделями.
Машина состоит из памяти (ленты разбиты на
ячейки), и считывающей головки, которая
осматривает ячейки памяти и в зависимости от
их содержимого и состояния машин, стирает
увиденное или записывает новый элемент, или
оставляет старое значение.
19

20.

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

21.

Все задачи математической теории алгоритмов
принято делить на два класса:
- Связанные с вычислением функции;
- Связанные с распознаванием
принадлежности объекта множеству.
Хотя второй случай можно свести к первому,
деление на два класса позволяет ввести два
важных понятия:
Вычислимая функция;
Разрешимое множество.
21

22.

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

23.

В 1936 году Чёрчем был сформулирован тезис о том,
что любую вычислимую функцию можно
представить как рекурсивную.
Так как в отличии от понятия вычислимой функции
понятие рекурсивной функции является строгим,
обычная математическая техника позволяет иногда
непосредственно доказать, что решающая задачу
функция не может быть рекурсивной, а значит задача
алгоритмически неразрешима.
Точное описание класса частично рекурсивных
функций вместе с тезисом Чёрча дает одно из
возможных решений задачи об уточнении понятия
алгоритма.
23

24.

В 1937 году Тьюринг сформулировал тезис о том, что для
всякой вычислимой функции существует машина
Тьюринга, его вычисляющая.
Доказать эти тезисы нельзя, так как понятие вычислимой
функции не формализовано, но косвенным свидетельством
их истинности являются строго математические теоремы
вида:
«Любую рекурсивную функцию можно вычислить на
некоторой машине Тьюринга»;
«Для любой задачи, решаемой на машине Тьюринга,
существует нормальный алгоритм Маркова» и т.п.
24

25.

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

26.

Более общей является теорема Райса
Теорема Райса:
Никакое свойство вычислимой функции
не является разрешимым.
То есть, какое бы свойство функции мы не взяли
(периодичность, ограниченность, монотонность),
нельзя алгоритмически (по алгоритму
вычисления функции) определить обладает ли
она заданным свойством.
Общая неразрешимость задана неоднозначно
(означает, что неразрешимы частные случаи) 26

27.

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

28.

1. Допустимость нестрогой формализации
представления
алгоритмов
при
применении
исполнителей,
способных
выполнять сложные команды.
Определение
термина
«исполнитель
алгоритма» достаточно очевидно:
Исполнитель алгоритма – это субъект или
устройство,
способные
правильно
интерпретировать описание алгоритма и
выполнить содержащийся в нем перечень
действий.
28

29.

Указания по выполнению действий для каждого
исполнителя формулируются посредством
некоторого языка, включающего набор
служебных слов, обозначающих действия
(команды), а также синтаксические правила их
объединения.
Совокупность допустимых команд образует
систему команд исполнителя (СКИ), которая
при реализации ее исполнителем преобразуется
в элементарные операции ( действия).
29

30.

Таким образом, при записи алгоритмов
возможны ситуации, когда язык представления
алгоритма является формальным, но в нем
используются сложные команды, которые
самим исполнителем переводятся на уровень
истинно элементарных действий.
Оператор ЯП
ТРАНСЛЯТОР
Микрокоманды
30

31.

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

32.

3. Расширение применимости понятия
алгоритма на последовательность любых
дискретных действий.
По определению алгоритм должен быть
обязательно связан с обработкой дискретной
информации.
Однако этот же термин используется и для
обозначения действий по управлению
исполнителем, напрямую не производящим
преобразование информации.
Учебные исполнители «Чертежник», «Паркетчик», «Черепашка», СКИ
которых включает перемещение по экрану и выполнение некоторых
операций («начертить линию», «положить плитку» и т.п.)
32