При использовании данной презентации при объяснении новой темы появляется возможность применять методы личностно-ориентированного обучения: проблемный метод, метод эвристической беседы и элементы исследования. Постановка проблемы ставит учащихся в условия, которые побуждают его решать учебную проблему, проводить анализ материала и оперировать им. Такая деятельность позволяет учащимся получить новую информацию, освоит новые способы применения знаний
Алгоритмически
неразрешимые
задачи
и вычислимые
функции
Алгоритмически
неразрешимая задача
это задача, для
которой невозможно
построить алгоритм
решения.
В 1900 г. на Международном
математическом конгрессе в
Париже немецкий математик
Д.Гильберт сформулировал 23
математические проблемы.
Сегодня решение (даже
частичное) какойлибо
проблемы Гильберта
расценивается как высшее
математическое
достижение.
10ая проблема Гильберта
Задано произвольное
алгебраическое уравнение с
целыми коэффициентами
P(x1,x2,…,xn)=0
(Например, ax12+bx22+cx33=0).
Требуется выяснить,
существует ли у данного
уравнения решение в целых
числах.
В 1970 г. математик
Ю.В.Матиясевич (СССР)
доказал
невозможность
построения
алгоритма
решения этой задачи.
Проблема останова
По описанию произвольного
алгоритма и его исходных данных
требуется определить
остановится ли алгоритм на
этих данных или будет работать
бесконечно.
Это классическая алгоритмически
неразрешимая задача – доказано в
теории алгоритмов.
Проблема
распознавания выводимости
любой теоремы из любой
системы аксиом, которую
пытался решить Лейбниц в XVII
в., пытаясь построить алгоритм
решения любых мат. задач.
В 1936 г. амер. математик А.Чёрч
доказал теорему об
алгоритмической неразрешимости
проблемы.
Методы доказательства
алгоритмической неразрешимости
основаны на методе сведения к
этим задачам известных
алгоритмически неразрешимых
задач.
Задачи, для которых доказана
алгоритмическая неразрешимость, не
надо и пытаться решать на ЭВМ –
практическая ценность понятия
«алгоритмической неразрешимости».
Вычислимая функция
(алгоритмически вычислимая)
– функция, вычисляемая
некоторым алгоритмом.
Теория вычислимости –
раздел теории алгоритмов.
Пример
есть отрезок из n девяток
невычислимой функции
1, если в десятичной записи числа π
f(n)=
0 в противном случае
Анализ первых 800 знаков разложения
π показывает, что f(n)=1 для n=0, 1, 2, 6.
Не существует общего метода
(алгоритма), реализующего эту функцию.
В теории алгоритмов было
сформулировано понятие
вычислительной машины и
доказано, что для преобразования
информации не обязательно
строить специализированные
вычислительные устройства: все
можно сделать на одном
универсальном устройстве при
помощи подходящей программы и
соответствующего кодирования.
alg_nerazresh.ppt
