Читать книгу "Вычислительное мышление. Метод решения сложных задач - Питер Макоуэн"

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

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

В порядке популярности

Боби предложил другой способ улучшить алгоритм АВС. До того, как оказаться на больничной койке, он был главным редактором французского женского журнала Elle и имел хорошее представление о языке. Например, ему было известно, что E – самая распространенная буква (в английском и французском). Поэтому Боби попросил, чтобы буквы зачитывали в порядке их популярности – то есть частотности. В английском этот порядок таков: E, Т, А, О… Во французском, на котором говорил Боби, это Е, S, А, R… Боби, соответственно, использовал французский порядок. Таким образом, помощница быстрее доходила до распространенных букв.

Похожий трюк использовался веками, чтобы расшифровать секретные коды. Он называется частотный анализ. Алгоритм для использования частотности букв был изобретен арабскими учеными около 1000 лет назад. Марию Стюарт обезглавили, потому что сэр Фрэнсис Уолсингем, начальник разведки королевы Елизаветы I, лучше нее владел вычислительным мышлением. Но это уже другая история. Идея Боби использовать частотный анализ – это пример и сопоставления с образцом, и обобщения. Задачи трансформируются, и решения для них используются повторно. Осознав, что расшифровывание кодов и угадывание букв – процессы схожие, мы видим, что частотный анализ, изобретенный для одного, пригоден для другого.

Насколько это быстро?

Давайте вернемся к алгоритму Боби, который мы определенно усовершенствовали. Новый способ должен быть лучше изначальной идеи – моргать разное количество раз для разных букв. Однако напрашивается вопрос: как быстро это будет – сколько времени уйдет, чтобы написать книгу? Удалось ли найти наилучший способ или можно предложить более быстрый алгоритм, который облегчит написание книги?

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

Можно прибегнуть к аналитическому мышлению. В этом случае необходимо сделать простые вычисления. Например, давайте учитывать не время, а сделанную работу. Если подсчитать, сколько букв алфавита произносит помощница, то мы всегда определим потраченное время. Просто надо знать, сколько времени уходит на произнесение одной буквы, и умножить это время на количество букв. Мы только что произвели действие, которое называется абстрагированием. Это еще один элемент вычислительного мышления, который применяется, чтобы упростить задачи и облегчить написание программ. Абстрагирование – просто длинное слово, которое подразумевает, что некоторые подробности скрывают или игнорируют. Мы проигнорировали такую деталь, как точное время, потраченное на всю книгу, и вместо этого подсчитали произнесенные буквы. «Число произнесенных букв» – это абстракция реально потраченного времени. Такой принцип очень часто используется в вычислительных процессах, чтобы упростить их работу.

Как же нам выяснить, сколько букв надо произнести? Для этого нужно задать несколько вопросов. Самый простой звучит так: сколько это будет в лучшем случае? Каково минимальное количество букв, которое должна произнести помощница, чтобы получилась книга? Рассмотрим и худший случай. Если не повезет, то насколько? Наконец, рассмотрим средний вариант и таким образом получим реалистичную оценку необходимой работы. Давайте чисто теоретически представим, что нам нужны только буквы алфавита, без цифр и знаков пунктуации. И проанализируем наш простой алгоритм, в соответствии с которым помощница говорит: «A, B, C…»

В лучшем случае вся книга будет состоять только из «А»: «АААА…» (возможно, выражая боль автора). Чтобы общаться при помощи одной буквы «А», достаточно сказать «А» один раз (ответить на один вопрос), и ответ будет получен. Здесь мы снова используем абстракцию – сначала анализируем, что будет, если посчитать только одну букву, и игнорируем всю книгу – по крайней мере для начала. Умножьте наш ответ для одной буквы на количество букв в книге и получите упомянутый лучший случай.

В худшем случае (для латинского алфавита), при котором кто-нибудь, например, все время жужжит («ZZZZ…»), потребуется 26 вопросов для каждой буквы. Итак, мы определили границы, в которых будет происходить передача любой информации. У нас никогда не получится лучше, чем при варианте с одной буквой, и хуже, чем со всеми 26.

Оценка будет точнее, если учесть среднее количество вопросов на каждую букву, то есть средний случай. Сделать это не так трудно. В длинном сообщении на каждую «А» где-нибудь еще придется «Z», на каждую «B» найдется «Y» и так далее. Это значит, что в среднем во всей книге на каждую продиктованную букву надо будет задать 13 вопросов. Умножьте число букв в книге на 13, и вы получите примерную оценку работы при ее написании. Умножьте это на среднее время, которое уходит у помощницы, чтобы произнести букву, и вы получите время, необходимое, чтобы написать книгу.

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

Изменение, внесенное Боби, — сначала спрашивать о распространенных буквах — улучшает ситуацию. Вероятно, получится уложиться в 10‒11 произносимых букв. А с учетом частотности, мы рассчитаем это точнее. Частотность можно уточнить или определить самостоятельно. Возьмите отрывок из любимой книги и посчитайте, сколько раз появляется каждая буква. Потом расположите буквы по порядку, начиная с самой распространенной, и посчитайте вероятность их появления. Средний случай — это число букв, которое необходимо произнести для угадывания одной буквы, вероятность появления которой равна 50%.

Итак, частотный анализ привел к улучшениям, но не слишком значительным, и в худшем случае для выяснения одной буквы все равно надо задать 26 вопросов. Но каждый специалист по информатике знает, что можно существенно улучшить этот процесс. Любая буква выясняется всего за пять вопросов! Гарантированно! И это не средний случай, а худший! Знаете, какие пять вопросов надо задать?