Содержание предисловие 2 веб-страницы 3 введение 6 1архитектура ЭВМ 17




НазваниеСодержание предисловие 2 веб-страницы 3 введение 6 1архитектура ЭВМ 17
страница72/78
Дата конвертации11.12.2012
Размер5.58 Mb.
ТипРеферат
1   ...   68   69   70   71   72   73   74   75   ...   78

ТЕОРИЯ ВЫЧИСЛЕНИЙ


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

Функции и их вычисление


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

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

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

Рассмотрим, например, систему, в которой входы и выходы функции могут быть заранее определены и занесены в таблицу. Каждый раз, когда нам требуется выход функции, мы просто ищем в таблице нужный вход и соответствующий ему выход. Так, вычисление функции можно свести к процессу поиска в таблице. Подобные системы удобны, но их возможности ограничены, поскольку огромное количество функций не представимы в табличной форме. Пример этого приведен на рис. 11.1, где мы попытались показать функцию преобразования ярдов в метры. Так как список возможных пар входов и выходов не ограничен, таблица никогда не будет завершена.



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

V=P(1 + r)"

мы можем описать величину V, представляющую собой увеличившееся в соответствии с годовой ставкой процента г за и лет значение исходных инвестиций Р. Но выразительные возможности алгебраических формул также ограничены. Существуют функции, отношения между входами и выходами которых слишком сложны для того, чтобы их можно было описать алгебраическими действиями. Например, тригонометрические функции, такие как синус и косинус. Если вам требуется вычислить синус 38 градусов, вы можете нарисовать соответствующий треугольник, измерить его стороны и сосчитать нужное соотношение — такой процесс невозможно выразить в терминах алгебраических действий со значением 38. Ваш карманный калькулятор также не умеет вычислять синус 38 градусов. В действительности он применяет сложные математические методы для получения очень хорошего приближения синуса 38 градусов, которое и выдает вам в качестве ответа.

Теория рекурсивных функций


Похоже, ничто не может так раздразнить человеческую натуру, как утверждение, что что-то сделать невозможно. Как только исследователи обнаружили нерешаемые задачи (в смысле отсутствия для них алгоритмического решения), другие ученые сразу же приступили к изучению этих задач, чтобы понять, в чем состоит сложность. Сегодня это поле исследований является основной частью дисциплины, известной как теория рекурсивных функций, и многое уже известно об этих сверхсложных проблемах. Действительно, как только математики разработали системы счисления, для которых «количественные» уровни — далекое прошлое, ученые, занимающиеся теорией рекурсивных функций, открыли множество уровней сложности этих проблем, которые выходят далеко за пределы возможностей алгоритмов.

Таким образом, мы видим, что с усложнением функций нам приходится применять все более мощные методы для их вычисления. Мы задаемся вопросом, всегда ли возможно найти систему для вычисления функций, независимо от их сложности? Ответ — нет. Поразительный вывод математиков состоит в том, что существуют настолько сложные функции, что для них невозможно найти хорошо определенный пошаговый процесс нахождения выходов в зависимости от входных значений. Таким образом, вычисление этих функций лежит далеко за пределами возможностей любой алгоритмической системы. Эти функции называются невычислимыми (noncomputable), тогда как функции, выходы которых можно найти алгоритмически на основе входных значений, называются вычислимыми (computable).

Изучение вычислимых и невычислимых функций — одна из важных областей, лежащих в основе вычислительной техники. Так как машины могут выполнять только задачи, описанные при помощи алгоритмов, изучение вычислимых функций — это изучение пределов способностей машин. Если мы узнаем, какие способности требуются для выполнения абсолютно всех вычислимых функций, и затем создадим машины, обладающие такими способностями, то сможем быть уверены, что эти машины настолько мощны, насколько вообще могут быть мощны созданные людьми машины. Аналогично, если мы обнаружим, что решение задачи требует вычисления невычислимой функции, то сможем сделать вывод, что такая проблема лежит за пределами возможностей машин.
1   ...   68   69   70   71   72   73   74   75   ...   78

Похожие:

Содержание предисловие 2 веб-страницы 3 введение 6 1архитектура ЭВМ 17 iconОсновы работы с Sharepoint в какое место веб-страницы разрешается вставить новую веб-часть (в браузере)?
В какое представление веб-страницы будут вноситься изменения, если выбрать команду Настроить эту страницу?
Содержание предисловие 2 веб-страницы 3 введение 6 1архитектура ЭВМ 17 iconВведение в физику и технологию элементной базы ЭВМ и компьютеров
Введение   8
Содержание предисловие 2 веб-страницы 3 введение 6 1архитектура ЭВМ 17 iconСодержание
Содержание размещают после титульного листа отчёта (как правило, на стр. 2). Слово «Содержание» рас­полагают посередине страницы...
Содержание предисловие 2 веб-страницы 3 введение 6 1архитектура ЭВМ 17 iconСоздание веб-страницы в простом текстовом редакторе
Давайте создадим  веб-страницу. Для этого нужно напечатать ее исходный код в простом текстовом редакторе  блокнот
Содержание предисловие 2 веб-страницы 3 введение 6 1архитектура ЭВМ 17 iconЗагрузка uploading теория
После того как набор html страниц веб-сайта создан. Все они связаны между собой с помощью ссылок. Страницы наполнены контентом. Таким...
Содержание предисловие 2 веб-страницы 3 введение 6 1архитектура ЭВМ 17 iconЛитература 153 Алфавитный указатель 155 Предисловие редактора русского издания Глубокоуважаемые коллеги! Содержа­ние этой книги значительно шире и глуб­же, нежели заявлено в ее названии. Я бы назвала ее «Лечение и реставрация молочных зубов»
Предисловие редактора русского издания 6 Введение 9 Предисловие 11 Благодарности 13
Содержание предисловие 2 веб-страницы 3 введение 6 1архитектура ЭВМ 17 icon        Информатика  Системы счисления и  арифметические основы эвм  
Введение   
Содержание предисловие 2 веб-страницы 3 введение 6 1архитектура ЭВМ 17 iconЯндекс - поисковая машина, способная по вашему запросу найти в русскоязычной части интернета наиболее подходящие веб-страницы, новости, картинки, статьи
Яндекс — поисковая машина, способная по вашему запросу найти в русскоязычной части интернета наиболее подходящие веб-страницы, новости,...
Содержание предисловие 2 веб-страницы 3 введение 6 1архитектура ЭВМ 17 iconВзаимодействие веб-сайтов по культуре с пользователем. 
Предисловие к русскому изданию   4 
Содержание предисловие 2 веб-страницы 3 введение 6 1архитектура ЭВМ 17 iconВзаимодействие веб-сайтов по культуре с пользователем. 
Предисловие к русскому изданию   4 
Разместите кнопку на своём сайте:
kak.znate.ru


База данных защищена авторским правом ©kak.znate.ru 2012
обратиться к администрации
KakZnate
Главная страница