Предисловие переводчика
Скачать 243.75 Kb.
|
| Neil Immerman Вычислимость и сложность 1 Выполнил: асп. каф. математической логики МГУ Т.А. Стариковская Руководитель семинаров по философии: доц., к. филос. н., С.Л. Катречко Предисловие переводчикаЧто такое алгоритм? Без сомнения, любой человек, даже незнакомый с математикой, ответит, что алгоритм – это некоторая последовательность действий. Однако определить это понятие формально, в математических терминах, не так просто. В начале 20-ого века, в связи с развитием вычислительной техники, этот вопрос стал особенно острым. Несомненно, развитию этого направления в математике мы во многом обязаны Гильберту. Гильберт сформулировал одну из наиболее известных задач в математике, а именно, любая ли математическая задача может быть вычислена с помощью какого-либо вычислительного устройства, или, другими словами, для любой ли математической задачи существует алгоритм, решающий ее. Эта задача вызвала немалый ажиотаж в математике. Прежде всего, следовало дать формальное определение алгоритма. Сразу несколько ученых почти в одно и то же время разработали свои определения. Алонзо Чёрч ввёл λ-исчисление, Курт Гёдель определил рекурсивные функции, Стивен Клине определил формальные системы, Марков – то, что в последствии стало известным как алгоритмы Маркова, Эмиль Пост и Алан Тьюринг определили абстрактные машины, в настоящее время известные как машины Поста и машины Тьюринга. Удивительно, что эти определения, несмотря на внешние различия, эквивалентны, то есть, определяют один и тот же класс вычислимых функций. В связи с этим, Чёрч предположил, что интуитивное понятие “вычислимости” совпадает с тем, которое было введено при помощи точных определений. Это предположение, называемое теперь “Тезисом Чёрча-Тьюринга”, безоговорочно принимается математиками. Наиболее простой и известной системой являются машины Тьюринга. Интересно, что для построения своего определения Тьюринг использовал модель мышления человека. Автору перевода статьи было бы чрезвычайно интересно узнать, совпадает ли мнение Алана Тьюринга с мнением современных биологов о механизмах мышления человека, но, тем не менее, такой поход позволил Тьюрингу разработать очень успешную математическую теорию. Тьюринг полагал, что мозг человека в фиксированный момент времени может находиться в одном из конечного числа состояний, и в каждый момент он может производить действие только с одним числом. Эти два замечания явно прослеживаются в определении машин Тьюринга. С помощью машин Тьюринга удалось доказать, что не всякая математическая задача вычислима. Очевидно, число машин Тьюринга счетно и каждой машине можно присвоить некоторый номер. Кроме того, каждой машине Тьюринга можно взаимно однозначно сопоставить ее код – код ее полного набора инструкций. Следует заметить, что любая машина Тьюринга на некотором входе может останавливаться после конечного числа шагов или работать бесконечно долго. Оказывается, что не существует алгоритма, который бы по номеру машины Тьюринга определял, останавливается ли она на собственном коде. К 1960 году компьютеры были распространены в промышленности и университетах. Постепенно были изобретены алгоритмы для множества задач. Стало ясно, что важно не только существует ли алгоритм для данной задачи, но и то, на сколько он эффективен. Основными параметрами, определяющими сложность алгоритма, стали время и память, затрачиваемые алгоритмом. Время, требующееся алгоритму, зависит от входа и машины, на котором он выполняется. Хорошей мерой сложности алгоритма является асимптотическая функция времени в худшем случае (как функция от длины входа, n). Алан Кобхэм и Джек Эдмондс определили класс сложности P как все задачи, решаемые за полиномиальное время, и это отличное математическое определение задач, решаемых на практике P = ∪i=1,2,… TIME[ni ]. Кроме этого класса, были определены множество других классов сложности, в частности, класс NP. Одна из известнейших нерешенных проблем математики состоит в том, равен ли класс NP классу P. Известно, что класс NP включает в себя класс P. Более того, для всех трудных задач, принадлежащих NP/P, найти полиномиальный алгоритм кажется невозможным. Но и доказать, что такого алгоритма не существует, пока тоже не удается. Несмотря на всю известность такой постановки этой задачи, многим математикам она кажется спорной. Дело в том, что решение этой задачи может повлиять на современное состояние науки совершенно по-разному в зависимости от того, какие нижняя (в случае P≠NP) или верхняя (в случае P=NP) оценки на время работы алгоритма будут доказаны. |
Добавить документ в свой блог или на сайт
Похожие:
 | Предисловие Предисловие переводчика Утверждение тем рефератов по истории отрасли науки для сдачи кандидатского экзамена по дисциплине «История и философия науки» | | Книга Пяти Колец предисловие переводчика япония при жизни Мусаси Традиционная власть императора была свергнута в XII веке, и, хотя каждый наследный император |
 | Абу ма'шар краткое введение в науку о приговорах звезд предисловие переводчика Федеральное агентство по образованию российской федерации фгоу впо «южный федеральный университет педагогический иститут» | | Предисловие переводчика Человечеству сил, преследующих собственные цели, одной из тактических задач которых является порабощение людей во всемирном масштабе... |
| Предисловие переводчика Так что не удивляйтесь когда к вам подсядет долговязый парень, или заглянет через плечо мужчина средних лет с бородкой. Читать кого-то... | | Предисловие переводчика Так что не удивляйтесь когда к вам подсядет долговязый парень, или заглянет через плечо мужчина средних лет с бородкой. Читать кого-то... |
| Программа по формированию навыков безопасного поведения на дорогах... ... | | Ложные друзья переводчика Динамическая эквивалентность как способ преодоления различий в национальных картинах мира |
| Перевод И. И. Городинского От переводчика Курсовая работа по дисциплине «Бухгалтерский учет» выполняется студентами в соответствии с учебным планом на завершающем этапе обучения... | | Электронный русско-англо-китайский переводчик rec-4510v подробная... Вид переводчика в открытом положении и коментарии к функциям клавиш |
| Календарно-тематическое планирование Информатика и икт 10 класс ... | | Урок французского и русского языков на тему: «Путешествие в страну Лингвинию» Цель урока: познакомить учащихся с такими понятиями как «языковые параллели» и «ложные друзья переводчика» |
| Ресурсы интернета для переводчика Все ссылки (и некоторые названия ресурсов) являются интерактивными – при нажатии и удержании клавиши и щелчке по левой клавише мыши... | | Программа по формированию навыков безопасного поведения на дорогах... Выставка книг 95 лет со дня рождения русского поэта и переводчика Бориса Владимировича Заходера (1918-2000) |
| Программа подготовки переводчика в сфере профессиональной коммуникации ... | | Темы для работы в группе ас выздоровление продолжается… Предисловие 2 |
