Основы теории алгоритмов

Сентябрь 2, 2022

Главная
Алгебра
Основы теории алгоритмов

Содержание

2. 6.1 Интуитивное понятие об алгоритме Интуитивное понятие алгоритма. Алгоритм – это правило, сформированное на некотором языке
3. Правила описания алгоритмов: Понятность для исполнителя Массовость (т.е. допустимость для него всех предложений языка исходных данных)
4. Алгоритм применим к допустимому исходному данному, если с его помощью, отправляясь от этого исходного данного, можно
5. Поскольку требование завершения алгоритмического процесса за конечное число шагов не учитывает реальных возможностей, связанных с затратами
6. Об источниках алгоритмов: Практика; научная теория; совокупность накопленных алгоритмов; изобретательность разработчика.
7. 6.2 Три типа алгоритмических моделей Различный выбор исходных средств формализации приводит к моделям алгоритмов разного вида.
8. Первый тип Связывает понятие алгоритма с вычислениями и числовыми функциями. Наиболее развитая и изученная модель этого
9. Второй тип Основан на представлении об алгоритме как о некотором детерминированном устройстве, способном выполнять в каждый
10. Третий тип Это преобразование слов в произвольных алфавитах, в которых элементарными операциями являются подстановки, т.е. замена
11. Тезис Чёрга Класс задач, решаемых в любой из этих формальных моделей, и есть класс всех задач,
12. Примеры. Задача о квадратуре круга. Требуется найти алгоритм построения с помощью циркуля и линейки квадрата, равновеликого
13. Примеры. Задача удвоения куба. Найти алгоритм, позволяющий на стороне любого куба с помощью циркуля и линейки
14. Вторая причина разработки теории алгоритмов – необходимость обоснования математики, поскольку появления антиномий привели к тому, что
15. Пример Актуально бесконечное множество. Расходуя ограниченное количество ресурсов на каждом шаге, имеющим фиксированную длительность, построить такое
16. 6.3 Кризис теории множеств антиномии. Выводы из антиномий. До середины XIX века никто не сомневался в
17. На втором Международном Математическом Конгрессе было заявлено, что теперь в математике остались только целые числа и
18. Две теории Кантора из теории множеств Кардинальное число множества М называется его мощностью и обозначается m.
19. Парадокс Кантора. Пусть М множество всех множеств обозначим его кардинальное число буквой m. В силу теоремы
20. Парадокс Рассела (парадокс брадобрея). Один из солдат оказался по профессии парикмахером, узнав об этом командир приказал
21. Открытие антиномий потрясло математику и математиков, как землетрясение. Нужно сказать, что математики поразному отреагировали на это
22. 6.4 Машины Тьюринга как модели алгоритмов В 1937г. английский математик Тьюринг опубликовал работу в которой он
23. Машина состоит из бесконечной в обе стороны ленты, разбитой на ячейки, и рабочей головки. Машина работает
24. Основной частью машины является логический блок, который работает следующим образом. В каждый момент времени рабочая головка
25. Т.о. работа МТ задается системой команд вида: qj*ai-qk*ax*dy Все случаи сочетания qj и ai для разных
26. Если головка в состоянии qj читаем символ ai, то в следующий момент она записывает в эту
28. Примеры построения машин Тьюринга Постороить машину Тьюринга, реализущую. «сложение» чисел. В машине Тюринга все числа представляются
30. Построить машину Тьюринга, которая вычисляет функцию а(Х)=Х+1 число Х запишем в виде строки, состоящей из букв
31. В первом случае говорят, что машина применила к исходному данному, во втором – не применима. Соответствия
32. Тезис Тьюринга: Любая вычислимая функция вычислимая по Тьюрингу, или всякий алгоритм может быть реализован машиной Тьюринга.
33. Проблема остановки: Можно ли построить машину То такую что для любой машины Тк любых исходных данных
35. Скачать презентацию

Слайд 2

6.1 Интуитивное понятие об алгоритме
Интуитивное понятие алгоритма.
Алгоритм – это правило, сформированное

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

Слайд 3

Правила описания алгоритмов:
Понятность для исполнителя
Массовость (т.е. допустимость для него всех предложений

языка исходных данных)
Определенность (все шаги алгоритма детерминированы и четко определены)
Результативность

Слайд 4

Алгоритм применим к допустимому исходному данному, если с его помощью,

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

Слайд 5

Поскольку требование завершения алгоритмического процесса за конечное число шагов не учитывает

реальных возможностей, связанных с затратами времени и ресурсов, то говорят, что при этом алгоритм потенциально выполним.

Слайд 6

Об источниках алгоритмов:
Практика;
научная теория;
совокупность накопленных алгоритмов;
изобретательность разработчика.

Слайд 7

6.2 Три типа алгоритмических моделей
Различный выбор исходных средств формализации приводит

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

Слайд 8

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

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

Слайд 9

Второй тип
Основан на представлении об алгоритме как о некотором детерминированном

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

Слайд 10

Третий тип
Это преобразование слов в произвольных алфавитах, в которых элементарными

операциями являются подстановки, т.е. замена куска слова (подслова) другим словом (Нормальный алгоритм Маркова, каноническая система Поста).

Слайд 11

Тезис Чёрга
Класс задач, решаемых в любой из этих формальных моделей,

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

Слайд 12

Примеры.
Задача о квадратуре круга.
Требуется найти алгоритм построения с помощью циркуля и

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

Слайд 13

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

циркуля и линейки построить сторону куба, объем которого вдвое больше объема заданного куба.

Слайд 14

Вторая причина разработки теории алгоритмов – необходимость обоснования математики, поскольку появления

антиномий привели к тому, что все в математике стало казаться неустойчивым.

Слайд 15

Пример
Актуально бесконечное множество. Расходуя ограниченное количество ресурсов на каждом шаге,

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

Слайд 16

6.3 Кризис теории множеств антиномии. Выводы из антиномий.
До середины XIX

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

Слайд 17

На втором Международном Математическом Конгрессе было заявлено, что теперь в

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

Слайд 18

Две теории Кантора из теории множеств
Кардинальное число множества М

называется его мощностью и обозначается m.
Теорема 1: Для любого кардинально числа m справедливо неравенство m<2m, где 2m – мощность множества всех подмножеств бесконечного множества.
Теорема 2: Мощность m’ подмножества множеств, имеющих мощность m удовлетворяет неравенству m’<= m

Слайд 19

Парадокс Кантора.
Пусть М множество всех множеств обозначим его кардинальное

число буквой m. В силу теоремы 1 кардинальное число множества его подмножества 2m удовлетворяет условию 2m> m с другой стороны множество m есть множество всех множеств его подмножества являются множествами и значит являются элементом М, а их множества являются подмножествами множества М. По теореме 2 должно иметь место неравенство 2m<= m полученные два неравенства противоречат друг другу

Слайд 20

Парадокс Рассела (парадокс брадобрея).
Один из солдат оказался по профессии

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

Слайд 21

Открытие антиномий потрясло математику и математиков, как землетрясение. Нужно сказать,

что математики поразному отреагировали на это заявление: одни стали во всем сомневаться, другие на антиномии не отреагировали.

Слайд 22

6.4 Машины Тьюринга как модели алгоритмов
В 1937г. английский математик

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

Слайд 23

Машина состоит из бесконечной в обе стороны ленты, разбитой на

ячейки, и рабочей головки. Машина работает в дискретные моменты времени t=0,1,2… В каждый момент времени во всякой ячейке ленты записана одна буква из некоторого конечного алфавита А={а0, а1, а2…аn}, называемым внешним алгоритмом машины, а головка находится в одном состояний из конечного множества внутренних состояний Q={q0, q1…qz}. Будем считать,что а0-пустой символ, т.е. в ячейке ничего не написано.

Слайд 24

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

В каждый момент времени рабочая головка обозревает одну ячейку ленты и в зависимости от того, что там написано и от своего внутреннего состояния она заменяет символ в обозреваемой ячейке, переходит в новой состояние и сдвигает на одну ячейку или остается на месте. Введем для обозначения этого движения символы d-1, d0, d+1 соответственно.

Слайд 25

Т.о. работа МТ задается системой команд вида:
qjai-qkax*dy
Все случаи сочетания qj

и ai для разных j и j и все реакции машины на них можно представить в виде функциональной таблицы с двумя входами.

Слайд 26

Если головка в состоянии qj читаем символ ai, то в

следующий момент она записывает в эту ячейку символ ax. Переход в состояние qk и в зависимости от того каково dy гловка сдвигает на одну ячейку влево, вправо или остается на месте.

Слайд 27

Слайд 28

Примеры построения машин Тьюринга
Постороить машину Тьюринга, реализущую. «сложение» чисел.
В машине Тюринга

все числа представляются в единичном коде, состоящем из Х единиц. Поэтому сложить а и в значит переработать слова 1а * 1в в слово 1а+в. Это преобразование выполняет машина c 4-мя состояниями и системой команд вида

Слайд 29

Слайд 30

Построить машину Тьюринга, которая вычисляет функцию а(Х)=Х+1 число Х запишем в

виде строки, состоящей из букв 1 (палочек)

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

Слайд 31

В первом случае говорят, что машина применила к исходному данному, во

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

Слайд 32

Тезис Тьюринга:
Любая вычислимая функция вычислимая по Тьюрингу, или всякий

алгоритм может быть реализован машиной Тьюринга.

Слайд 33

Проблема остановки:
Можно ли построить машину То такую что для любой

машины Тк любых исходных данных а для машины Т.
Ответ на этот вопрос отрица-тельный, т.к. сформулирована и доказана следующая теорема.

Основы теории алгоритмов

Содержание

6.1 Интуитивное понятие об алгоритмеИнтуитивное понятие алгоритма.Алгоритм – это правило, сформированное

Правила описания алгоритмов:Понятность для исполнителяМассовость (т.е. допустимость для него всех предложений

Алгоритм применим к допустимому исходному данному, если с его помощью,

Поскольку требование завершения алгоритмического процесса за конечное число шагов не учитывает

Об источниках алгоритмов:Практика;научная теория;совокупность накопленных алгоритмов;изобретательность разработчика.

6.2 Три типа алгоритмических моделей Различный выбор исходных средств формализации приводит

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

Второй тип Основан на представлении об алгоритме как о некотором детерминированном

Третий тип Это преобразование слов в произвольных алфавитах, в которых элементарными

Тезис Чёрга Класс задач, решаемых в любой из этих формальных моделей,

Примеры.Задача о квадратуре круга.Требуется найти алгоритм построения с помощью циркуля и

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