Работа зачтена.Хорошее выполнение.Очень порадовало выполнение.Рекомендую.
Информация о работе
Подробнее о работе
1. Проблема алгоритмической разрешимости в математике. 2. Основатели теории алгоритмов – Клини, Черч, Пост, Тьюринг.
- 9 страниц
- 2016 год
- 422 просмотра
- 2 покупки
Гарантия сервиса Автор24
Уникальность не ниже 50%
Фрагменты работ
1. История возникновения понятия «алгоритм»
Алгоритм – это предписание исполнителю выполнить последовательность команд, приводящую от исходных данных к искомому результату.
Алгоритм – это конечная последовательность указаний, адресованных исполнителю, четко и однозначно задающая процесс решения задач какого-либо типа во всех деталях и позволяющая получить за конечное число шагов результат, однозначно определяемый исходными данными.
Некоторые из математических алгоритмов известны уже несколько тысячелетий. Считается, что самым древним нетривиальным алгоритмом является способ нахождения наибольшего общего делителя двух целых чисел. Он был открыт около 2300 лет тому назад и известен как алгоритм Евклида, поскольку содержится в первых предложениях седьмой книги «Начал» этого древнего математика. (Правда есть предположение, что алгоритм Евклида лишь интерпретация алгоритма, предложенного Эвдоксом за 75 лет до этого.)
Содержание
1. История возникновения понятия «алгоритм» 3
2. Проблема алгоритмической разрешимости 4
3. Формулировки проблемы разрешения 5
4. Примеры и решение проблемы разрешимости 6
Литература 9
Неразрешимость проблемы разложения числа на простые множители достаточно простым алгоритмом стала основой современной теории надёжных индивидуальных шифров. Одним из методов решения неразрешимых проблем является переход к вероятностным алгоритмам разрешения и к квантовым вычислениям. Показано, что для многих переборных задач есть быстрые алгоритмы, решающие их со сколь угодно близкой к единице заранее заданной вероятностью.
В последние десятилетия в связи с приложениями к проблемам, имеющим практическое значение, к проблеме разрешения относят и вопросы оптимизации найденных алгоритмов, то есть требуется не только предоставить разрешающий алгоритм, но и обосновать, что этот алгоритм имеет наименьшую возможную сложность вычисления в том или ином смысле (по затратам времени, памяти, и так далее). С точки зрения этой подпроблемы проблема разрешения многие теории (или множества конструктивных объектов), для которых проблемы разрешения были положительно решены, оказались практически неразрешимыми или, по крайней мере, найденные алгоритмы не годятся для практического применения.
Литература
1. Ершов Ю. Л. Проблемы разрешимости и конструктивные модели. — М.: Наука, 1980.
2. Катленд Н. Вычислимость. Введение в теорию рекурсивных функций. — М.: Наука, 1983.
3. Мальцев А. И. . Алгоритмы и рекурсивные функции. — М.: Наука, 1986.
4. Справочная книга по математической логике. Ч. III. Теория рекурсии. — М.: Наука. 1982.
5. Чёрч А. Введение в математическую логику. — М.: Наука, 1960.
6. Н. Н. Непейвода. А. А. Ивин. А. С. Карпенко. Проблема разрешимости. Гуманитарная энциклопедия [Электронный ресурс] // Центр гуманитарных технологий. — 21.08.2014 (последняя редакция: 10.06.2015). URL: http://gtmarket.ru/concepts/6927
Форма заказа новой работы
Не подошла эта работа?
Закажи новую работу, сделанную по твоим требованиям
