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

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

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

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

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

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

V=P(1 + r)"

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