Эдвард Шейнерман - Путеводитель для влюбленных в математику

Закон умножения степеней 10 m × 10 ⁿ = 10 m + ⁿ можно переформулировать для логарифмов. Посмотрим, как такое сделать. Допустим, a = 10 m и b = 10 ⁿ .

Чему равен десятичный логарифм a ? Это степень, в которую нужно возвести 10, чтобы получить a . Иными словами, lg( a ) = m . Аналогично lg( b ) = n .

Чему равен логарифм произведения ab ? Мы знаем, что a = 10 m и b = 10 ⁿ . Таким образом, ab = 10 m + ⁿ . В какую степень нужно возвести 10, чтобы получить ab ? Ответ: m + n . На языке математических символов это выглядит так: lg( ab ) = m + n .

Подытожим:

lg( a ) = m,

lg( b ) = n,

lg( ab ) = m + n .

Отсюда мы выводим закон сложения для логарифмов:

lg( ab ) = lg( a ) + lg( b ). (**)

Похоже, мы уже встречали эту формулу…

Давайте подытожим то, что мы узнали из предыдущих разделов. Мы определили функцию f ( m ) как долю тех величин среди большого количества измерений, мантисса которых меньше m . Эта функция удовлетворяет трем условиям:

f (1) = 0,

f (10) = 1,

f ( ab ) = f ( a ) + f ( b ).

Потом мы обсудили логарифмы и выяснили следующее:

lg(1) = 0,

lg(10) = 1,

lg( ab ) = lg( a ) + lg( b ).

Другими словами, значения f при 0 и 10 совпадает со значением десятичного логарифма от тех же величин. Кроме того, f и логарифм подчиняются одному и тому же правилу в соответствии с формулами (*) и (**). На основе этих фактов (и чисто технической оговорки, что функция f непрерывна) математики могут доказать, что f представляет собой логарифмическую функцию.

Теперь мы наконец готовы указать точную частотность первых значащих цифр при большом количестве измерений.

Какая доля измерений имеет первую значащую цифру 1? Сформулируем вопрос иначе: какая доля этих величин имеет мантиссу меньше 2? Ответ равен f (2) = lg(2) ≈ 0,3010 = 30,1 %.

Какая доля величин начинается с 9? Ответ равен f (10) – f (9), так как мы должны вычесть из общего количества величин те, первая значащая цифра которых меньше 9.

Это дает f (10) – f (9) = lg(10) – lg(9) ≈ 1 – 0,9542 = 0,0458 = 4,58 %.

Когда-то я задавал вопрос о значении f (1,7). Теперь можно уверенно ответить:

f (1,7) = lg(1,7) ≈ 0,23 = 23 %.

Шеф-повара с фантазией редко руководствуются точными рецептами. Скорее, они следуют за вдохновением. А повара-новички покорно выполняют все указания поваренных книг.

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

В этом плане компьютеры похожи на новичков. Скажем, если нужно сложить несколько чисел, они скрупулезно выполняют операцию за операцией, руководствуясь инструкциями программистов. Эти инструкции называют алгоритмами [125] Слово алгоритм происходит от имени персидского математика Аль-Хорезми (IX в. н. э.). . Компьютерные алгоритмы окружают нас повсюду: они высчитывают проценты для банков, определяют разрывы страниц в текстовых документах, превращают цифровые данные на DVD-диске в кино, предсказывают погоду, рыщут по интернету в поисках рецепта, включающего заданные ингредиенты, и дают советы, сверяясь со спутниками GPS, когда мы ищем дом с хитрым адресом.

Первый математический алгоритм, который изучает большинство людей, – как складывать числа. Когда нужно просуммировать в столбик 25 и 18, мы знаем: вначале нужно к 5 прибавить 8 (и запомнить результат: 13), записать 3 в колонке единиц, а 1 держать в уме. Затем сложить 2 и 1, увеличить результат на 1 и записать 4 в колонке десятков. Получится 43.

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

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

Итак, перед нами встает проблема: имеется стопка тетрадей, перемешанных в хаотичном порядке, необходимо разложить их по алфавиту. Как это сделать наилучшим образом?

Начнем с простой, но неэффективной идеи. Допустим, у меня учится 100 студентов. Я беру из стопки первую тетрадку и смотрю, должна ли она идти первой по алфавиту. Каким образом? Я сравниваю имена на всех тетрадках с именем на этой тетрадке. Если не повезло и тетрадка по алфавиту не первая, я кладу ее в самый низ стопки и начинаю сначала. Я стану действовать так, пока не обнаружу первую по алфавиту тетрадку. Тогда я переложу ее в новую стопку, где тетрадки будут лежать упорядоченным образом.

Дальше я вернусь к неупорядоченной стопке – сейчас там 99 тетрадей – и, как и раньше, начну искать первую по алфавиту тетрадку. Я возьму тетрадку сверху, сравню со всеми остальными и положу в самый низ стопки, если она не подойдет. Когда я найду искомую тетрадку, я положу ее во вторую стопку снизу.

Теперь у меня есть «всего-навсего» 98 тетрадей, и я повторяю все по новой: ищу первую по алфавиту тетрадь и кладу ее в низ второй стопки.

Сколько времени это займет?

Основная операция заключается в том, чтобы сравнить два имени и решить, какое следует первым по алфавиту [126] Даже эту операцию можно разбить на еще более элементарные. Например, нужно решить, чью тетрадь положить первой – Алисы или Алекса. Я сравниваю первые буквы. Они совпадают. Тогда я сравниваю вторые буквы – они снова совпадают. Третья буква в имени Алисы – «и», третья буква в имени Алекса – «е». Следовательно, тетрадка Алекса должна идти первой. . Мы будем оценивать эффективность алгоритма по количеству сравнений, которые необходимо провести. У меня 100 учащихся; как долго мне придется сопоставлять имена и решать, какое идет первым?

В неупорядоченной стопке из 100 тетрадей я сравниваю первую с 99 остальными. Необходимо проделать эту операцию со всеми 100 тетрадями (не исключено, что искомая лежит в самом конце). Поиск первой по алфавиту потребует максимум 100 × 99 = 9900 сопоставлений.