Оцените презентацию от 1 до 5 баллов!
Тип файла:
ppt / pptx (powerpoint)
Всего слайдов:
16 слайдов
Для класса:
1,2,3,4,5,6,7,8,9,10,11
Размер файла:
133.00 kB
Просмотров:
71
Скачиваний:
0
Автор:
неизвестен
Слайды и текст к этой презентации:
№1 слайд![Алгоритмически неразрешимые](/documents_6/9a503ce3e7d1ac3a6f32bc8cecff4419/img0.jpg)
Содержание слайда: Алгоритмически неразрешимые проблемы
№2 слайд![В теории алгоритмов известны](/documents_6/9a503ce3e7d1ac3a6f32bc8cecff4419/img1.jpg)
Содержание слайда: В теории алгоритмов известны задачи, о которых доказано, что для их решения не существует алгоритма.
Такие задачи называются алгоритмически неразрешимыми.
№3 слайд![ТЕОРЕМА проблема останова Не](/documents_6/9a503ce3e7d1ac3a6f32bc8cecff4419/img2.jpg)
Содержание слайда: ТЕОРЕМА (проблема “останова”):
Не существует алгоритма (машины Тьюринга), позволяющего по описанию произвольного алгоритма и его исходных данных (и алгоритм и данные заданы символами на ленте машины Тьюринга) определить, останавливается ли этот алгоритм на этих данных или работает бесконечно.
Иными словами: проблема «останова», т.е. определения по записи произвольного алгоритма , а также по записи произвольного "входа", остановится ли вычислительное устройство, действующее в соответствие с данным алгоритмом и обрабатывающее данный "вход", или же оно будет работать бесконечно долго, является алгоритмически неразрешимой.
№4 слайд![ПОНЯТИЕ САМОПРИМЕНИМОСТИ](/documents_6/9a503ce3e7d1ac3a6f32bc8cecff4419/img3.jpg)
Содержание слайда: ПОНЯТИЕ САМОПРИМЕНИМОСТИ АЛГОРИТМА :
Алгоритм называется самоприменимым, если он эффективно перерабатывает текст, соответствующий его собственной записи, в некоторый результат за конечное число шагов.
В противном случае - если алгоритм не останавливается и продолжает работать бесконечно долго, он называется несамоприменимым.
№5 слайд![ТЕОРЕМА проблема](/documents_6/9a503ce3e7d1ac3a6f32bc8cecff4419/img4.jpg)
Содержание слайда: ТЕОРЕМА (проблема распознавания самоприменимости):
Проблема распознавания самоприменимости
алгоритмически неразрешима.
Проблема распознавания самоприменимости является частным случаем проблемы останова.
Алгоритмическая неразрешимость более общей проблемы будет очевидна.
ДОКАЗАТЕЛЬСТВО:
От противного
Пусть такая машина существует.
Назовем ее А.
Тогда А
- любой самоприменимый шифр перерабатывает в ‘1’
(значит машина самоприменима)
- любой несамоприменимый в ‘0’
(машина несамоприменима)
№6 слайд![Если существует такая машина](/documents_6/9a503ce3e7d1ac3a6f32bc8cecff4419/img5.jpg)
Содержание слайда: Если существует такая машина А,
то существует и такая машина В, что:
- несамоприменимые машины перерабатывает в ‘1’
- самоприменимые не перерабатывает (работает бесконечно)
Рассмотрим два случая:
В самоприменима
В несамоприменима
№7 слайд![. Если В самоприменима, то](/documents_6/9a503ce3e7d1ac3a6f32bc8cecff4419/img6.jpg)
Содержание слайда: 1. Если В самоприменима, то она, будучи применена к своему шрифту В*, будет работает бесконечно.
Но это означает, что данный алгоритм несамоприменим.
Противоречие.
2. Если В несамоприменима, то она, будучи применена к своему шифру В*, остановится с 1.
Применимость В к В* означает, что В самоприменима.
Противоречие.
Следовательно, таких машин А и В не существует.
Теорема доказана.
№8 слайд![ПРИМЕРЫ НЕРАЗРЕШИМЫХ ПРОБЛЕМ](/documents_6/9a503ce3e7d1ac3a6f32bc8cecff4419/img7.jpg)
Содержание слайда: ПРИМЕРЫ НЕРАЗРЕШИМЫХ ПРОБЛЕМ:
Десятая проблема Гильберта
Пусть задан многочлен n-ой степени с целыми коэффициентами – P, существует ли алгоритм, который определяет, имеет ли уравнение P=0 решение в целых числах?
Ю.В. Матиясевич показал, что такого алгоритма не существует, т.е. отсутствует общий метод определения целых корней уравнения P=0 по его целочисленным коэффициентам.
№9 слайд![Проблема тотальности Проблема](/documents_6/9a503ce3e7d1ac3a6f32bc8cecff4419/img8.jpg)
Содержание слайда: Проблема тотальности
Проблема тотальности
По произвольному заданному алгоритму определить, будет ли он останавливаться на всех возможных наборах исходных данных.
Другая формулировка этой задачи – определить, является ли алгоритм Р всюду определённым или частично определенным?
№10 слайд![Проблема останова и](/documents_6/9a503ce3e7d1ac3a6f32bc8cecff4419/img9.jpg)
Содержание слайда: Проблема “останова” и сводящиеся к ней задачи
Проблема “останова” и сводящиеся к ней задачи
ТЕОРЕМА:
Задача о печатании данного знака машины на чистой ленте точно один раз алгоритмически неразрешима.
ДОКАЗАТЕЛЬСТВО:
Пусть дана машина Т, которая работает на чистой ленте.
1. Преобразуем машину Т в машину D
1.1 если в алфавите машины Т нет “0”, то D совпадает с Т
1.2 если “0” есть, то заменяем в алфавите D “0” новым знаком, который не содержался в ее алфавите.
2. Построим машину Е такую, которая работает также, как и машина Т, но после остановки машины Т она ставит “0” и тоже останавливается.
3. Вывод: “0” печатается один раз, если машина Тьюринга останавливается на чистой ленте.
Задача о печатании “0” равносильна задаче об остановке машины на чистой ленте.
№11 слайд![ТЕОРЕМА ТЕОРЕМА Задача о](/documents_6/9a503ce3e7d1ac3a6f32bc8cecff4419/img10.jpg)
Содержание слайда: ТЕОРЕМА:
ТЕОРЕМА:
Задача о печатании данного знака машины на чистой ленте бесконечное количество раз алгоритмически неразрешима
Доказательство:
Возьмем знак «0». Пусть машина Тьюринга Т работает на чистой ленте.
1.Преобразим ее в новую машину Тьюринга D.
1.1 Если Т не содержит в своем алфавите «0», то D совпадает с T.
1.2 Если T имеет этот знак в своем алфавите, то в алфавите машины D «0» будет заменен любым знаком, ранее не входящим в алфавит машины.
№12 слайд![D остановится тогда, когда](/documents_6/9a503ce3e7d1ac3a6f32bc8cecff4419/img11.jpg)
Содержание слайда: D остановится тогда, когда остановится Т.
2. Построим машину Е, которая работает как D вплоть до ее остановки. После чего Е переходит в состояние А и печатает «0» бесконечно много раз (A 0RA).
3. Получим, что символ «0» печатается бесконечно много раз в том и только в том случае, если машина Т останавливается на чистой ленте. Значит задача о печатании бесконечно большого числа нулей равносильна задаче об остановке машины на чистой ленте.
Поскольку задача останова алгоритмически неразрешима, то и задача о печатании символа бесконечно много раз тоже
неразрешима.
№13 слайд![ТЕОРЕМА ТЕОРЕМА Проблема](/documents_6/9a503ce3e7d1ac3a6f32bc8cecff4419/img12.jpg)
Содержание слайда: ТЕОРЕМА:
ТЕОРЕМА:
Проблема распознавания эквивалентности машин Тьюринга является алгоритмически неразрешимой.
По двум произвольным машинам Тьюринга определить, будут ли они выдавать одинаковые выходные результаты на всех исходных данных.
№14 слайд![Примеры задач, для которых не](/documents_6/9a503ce3e7d1ac3a6f32bc8cecff4419/img13.jpg)
Содержание слайда: Примеры задач, для которых не найден алгоритм решения
1. Вычисление совершенных чисел
Совершенные числа – это числа, которые равны сумме своих делителей, например: 28 = 1+2+4+7+14.
Определим функцию S(n) = n-ое по счёту совершенное число и поставим задачу вычисления S(n) по произвольно заданному n. Не найден общий метод вычисления совершенных чисел, мы даже не знаем, множество совершенных чисел конечно или счетно.
№15 слайд![. Распределение девяток в](/documents_6/9a503ce3e7d1ac3a6f32bc8cecff4419/img14.jpg)
Содержание слайда: 2. Распределение девяток в записи числа π(пи)
2. Распределение девяток в записи числа π(пи)
Определим функцию f(n) = i,
где n – количество девяток подряд в десятичной записи числа π ,
а i – номер самой левой девятки из n девяток подряд:
π =3,141592… f(1) = 5.
Задача состоит в вычислении функции f(n) для произвольно заданного n.
Поскольку число π является иррациональным и трансцендентным, то мы не знаем никакой информации о распределении девяток (равно как и любых других цифр) в десятичной записи числа π . Вычисление f(n) связано с вычислением последующих цифр в разложении π , до тех пор, пока мы не обнаружим n девяток подряд, однако у нас нет общего метода вычисления f(n), поэтому для некоторых n вычисления могут продолжаться бесконечно – мы даже не знаем в принципе (по природе числа π ) существует ли решение для всех n.
№16 слайд![Вопросы для самопроверки](/documents_6/9a503ce3e7d1ac3a6f32bc8cecff4419/img15.jpg)
Содержание слайда: Вопросы для самопроверки:
Вопросы для самопроверки:
1. Какие задачи называются алгоритмически неразрешимыми?
2. Сформулируйте проблему тотальности.
3. Какой алгоритм называется самоприменимым/несамоприменимым?
4. В чем заключается проблема останова?
5. Какой способ доказательства неразрешимости задачи является самым распространенным?
6. Является ли задача, для которой не найден алгоритм решения неразрешимой?
7. Сформулируйте проблему распознавания эквивалентности.