Страница 5 из 5
Боби предложил другой способ улучшить алгоритм АВС. До того, как оказаться на больничной койке, он был главным редактором французского женского журнала Elle и имел хорошее представление о языке. Например, ему было известно, что E – самая распространенная буква (в английском и французском). Поэтому Боби попросил, чтобы буквы зачитывали в порядке их популярности – то есть частотности. В английском этот порядок таков: E, Т, А, О… Во французском, на котором говорил Боби, это Е, S, А, R… Боби, соответственно, использовал французский порядок. Таким образом, помощница быстрее доходила до распространенных букв.
Похожий трюк использовался веками, чтобы расшифровать секретные коды. Он называется частотный анализ. Алгоритм для использования частотности букв был изобретен арабскими учеными около 1000 лет назад. Марию Стюарт обезглавили, потому что сэр Фрэнсис Уолсингем, начальник разведки королевы Елизаветы I, лучше нее владел вычислительным мышлением. Но это уже другая история. Идея Боби использовать частотный анализ – это пример и сопоставления с образцом, и обобщения. Задачи трансформируются, и решения для них используются повторно. Осознав, что расшифровывание кодов и угадывание букв – процессы схожие, мы видим, что частотный анализ, изобретенный для одного, пригоден для другого.
Насколько это быстро?
Давайте вернемся к алгоритму Боби, который мы определенно усовершенствовали. Новый способ должен быть лучше изначальной идеи – моргать разное количество раз для разных букв. Однако напрашивается вопрос: как быстро это будет – сколько времени уйдет, чтобы написать книгу? Удалось ли найти наилучший способ или можно предложить более быстрый алгоритм, который облегчит написание книги?
Нам необходимо определить эффективность алгоритма. Проведем эксперимент и применим научное мышление. Например, следующим образом: несколько раз определим время, которое уходит на передачу какого-то отрывка с каждым алгоритмом и с разными участниками, и выясним, в каком случае все было в среднем быстрее. Однако на это уйдет очень много времени и сил. Есть способ и лучше.
Можно прибегнуть к аналитическому мышлению. В этом случае необходимо сделать простые вычисления. Например, давайте учитывать не время, а сделанную работу. Если подсчитать, сколько букв алфавита произносит помощница, то мы всегда определим потраченное время. Просто надо знать, сколько времени уходит на произнесение одной буквы, и умножить это время на количество букв. Мы только что произвели действие, которое называется абстрагированием. Это еще один элемент вычислительного мышления, который применяется, чтобы упростить задачи и облегчить написание программ. Абстрагирование – просто длинное слово, которое подразумевает, что некоторые подробности скрывают или игнорируют. Мы проигнорировали такую деталь, как точное время, потраченное на всю книгу, и вместо этого подсчитали произнесенные буквы. «Число произнесенных букв» – это абстракция реально потраченного времени. Такой принцип очень часто используется в вычислительных процессах, чтобы упростить их работу.
Как же нам выяснить, сколько букв надо произнести? Для этого нужно задать несколько вопросов. Самый простой звучит так: сколько это будет в лучшем случае? Каково минимальное количество букв, которое должна произнести помощница, чтобы получилась книга? Рассмотрим и худший случай. Если не повезет, то насколько? Наконец, рассмотрим средний вариант и таким образом получим реалистичную оценку необходимой работы. Давайте чисто теоретически представим, что нам нужны только буквы алфавита, без цифр и знаков пунктуации. И проанализируем наш простой алгоритм, в соответствии с которым помощница говорит: «A, B, C…»
В лучшем случае вся книга будет состоять только из «А»: «АААА…» (возможно, выражая боль автора). Чтобы общаться при помощи одной буквы «А», достаточно сказать «А» один раз (ответить на один вопрос), и ответ будет получен. Здесь мы снова используем абстракцию – сначала анализируем, что будет, если посчитать только одну букву, и игнорируем всю книгу – по крайней мере для начала. Умножьте наш ответ для одной буквы на количество букв в книге и получите упомянутый лучший случай.
В худшем случае (для латинского алфавита), при котором кто-нибудь, например, все время жужжит («ZZZZ…»), потребуется 26 вопросов для каждой буквы. Итак, мы определили границы, в которых будет происходить передача любой информации. У нас никогда не получится лучше, чем при варианте с одной буквой, и хуже, чем со всеми 26.
Оценка будет точнее, если учесть среднее количество вопросов на каждую букву, то есть средний случай. Сделать это не так трудно. В длинном сообщении на каждую «А» где-нибудь еще придется «Z», на каждую «B» найдется «Y» и так далее. Это значит, что в среднем во всей книге на каждую продиктованную букву надо будет задать 13 вопросов. Умножьте число букв в книге на 13, и вы получите примерную оценку работы при ее написании. Умножьте это на среднее время, которое уходит у помощницы, чтобы произнести букву, и вы получите время, необходимое, чтобы написать книгу.
Отметим, что мы снова оцениваем наш алгоритм – но на сей раз нас интересует не то, действует ли он вообще, а то, насколько быстро он действует. У алгоритма оценивают много разных аспектов, но надежность и эффективность – два важнейших для оценки.
Конец ознакомительного фрагмента.
Текст предоставлен ООО «ЛитРес».
Прочитайте эту книгу целиком, купив полную легальную версию на ЛитРес.
Безопасно оплатить книгу можно банковской картой Visa, MasterCard, Maestro, со счета мобильного телефона, с платежного терминала, в салоне МТС или Связной, через PayPal, WebMoney, Яндекс.Деньги, QIWI Кошелек, бонусными картами или другим удобным Вам способом.