Читать «Вычислительное мышление: Метод решения сложных задач» онлайн - страница 15

Но если это та же самая задача, то и соответствующая ей стратегия должна обеспечить нам более удачное решение, чем уже найденное. Здесь мы снова используем и Мы преображаем задачу, чтобы повторно использовать решения. Каков эквивалент решения, которое оставит только половину вариантов, применительно к алфавиту? Сначала, наверное, имеет смысл спросить: «Это гласная?» — но как будут выглядеть остальные четыре вопроса? Каждый раз оставлять только половину вариантов из алфавита? Напрашивается такой первый вопрос: «Это между А и М?» Если ответ утвердительный, то потом мы спрашиваем: «Это между А и F?» Если ответ отрицательный, мы спрашиваем: «Это между N и S?» — и так далее. Таким образом мы гарантированно доберемся до любой буквы алфавита, которую задумал человек, всего за пять вопросов, как это показывает на рис. 2. Начните сверху диаграммы и двигайтесь вниз в соответствии с ответами «да/нет».

В этот момент нужно подключить еще один компонент Необходимо прояснить все детали, потому что здесь можно запутаться. Спрашивая «Это между А и М?», надо уточнить, входит ли «М» в этот промежуток (входит).

Попробуем еще больше усовершенствовать эту технику, используя частотный анализ. Поскольку букв только 26, реально добраться до «Е» и других распространенных букв быстрее чем за пять вопросов. Попробуйте сделать дерево решений, которое это обеспечит. Кроме того, можно использовать принцип предиктивного набора текста, чтобы предугадывать набранные не до конца слова. Все подобные решения из более ранних алгоритмов применимы и здесь. Мы повторно используем готовые решения.

Коды для букв

Дерево решений представляет собой совсем другой подход. Если мы примем «да» и «нет» или «моргнуть» и «не моргать» за 1 и 0, тогда дерево решений определит двоичную последовательность, которую должен усвоить больной с синдромом «запертого человека», чтобы обозначить каждую букву (рис. 3).

Таким образом, чтобы ускорить процесс, можно отказаться от вопросов. Человек, передающий информацию, проходит определенную последовательность для каждой буквы, а другой человек — записывает. Таким образом, обозначая морганием код 0110 (не моргать, моргнуть, моргнуть, не моргать), выражаем букву «P». Соответственно, дерево решений преображаем в , как на рис. 4. Тому, кто хочет общаться с больным, можно дать либо дерево решений, либо такую таблицу. В сущности, мы только что изобрели код для общения, похожий на азбуку Морзе. И снова очевидно, что наша задача, в сущности, аналогична той, которую пытался решить Сэмюэл Морзе, чтобы передавать информацию с помощью телеграфа. Точки и тире соответствуют нашем единицам и нулям или вариантам «морг­нуть» и «не моргнуть». И снова мы применяем

Однако не стоит выбирать решение второпях. Детали играют большую роль. Если не задавать вопросов, как узнать, что человек передает информацию? Если он не моргает, что это значит — он уснул или просто ничего не говорит? Как узнать, что он начал передавать буквы? Сколько времени продолжается «неморгание»? Небольшое изменение привело к необходимости решить много новых проблем. Сэмюэл Морзе их решил. В азбуке Морзе с этой целью используются три символа, а не два: точки, тире и тишина. Продолжительность каждого элемента точно определена. Какой бы долгой ни была точка, пауза между точками и тире одинаковая. Между буквами она в три раза дольше точки, между словами — в семь раз. Это обеспечивает структуру, которую мы потеряли, отказавшись от вопросов.