Сложность песен - The Complexity of Songs

« Сложность песен » - это журнальная статья, опубликованная компьютерным ученым Дональдом Кнутом в 1977 году в качестве шутки о теории вычислительной сложности . В статье используется тенденция популярных песен превращаться из длинных и содержательных баллад в очень повторяющиеся тексты с небольшим содержанием или без него. В статье отмечается, что песня длиной N слов может быть создана с запоминанием, например, только O ( log N ) слов (« пространственная сложность » песни).

Резюме статьи

Кнут пишет, что «наши древние предки изобрели концепцию рефрена », чтобы уменьшить пространственную сложность песен, что становится критически важным, когда большое количество песен должно быть сохранено в памяти . Лемма Кнута 1 утверждает, что если N - длина песни, то припев снижает сложность песни до cN , где коэффициент  c  <1.

Кнут далее демонстрирует способ создания песен со сложностью O ( ), подход, «усовершенствованный шотландским фермером по имени О. Макдональд ». ${\ displaystyle {\ sqrt {N}}}$

Более изобретательные подходы дают песни сложности O ( ), класс, известный как « m бутылок пива на стене ». ${\ displaystyle \ log N}$

Наконец, прогресс в 20-м веке - стимулированный тем фактом, что «появление современных лекарств привело к потребностям еще меньшего объема памяти» - ведет к окончательному улучшению: существуют произвольно длинные песни с пространственной сложностью O (1), например песня определяется рекуррентным отношением

${\ Displaystyle S_ {0} = \ epsilon, S_ {k} = V_ {k} S_ {k-1}, \, k \ geq 1,}$

${\ displaystyle V_ {k} =}$ « Вот так» , « Мне это нравится» , для всех ${\ displaystyle U}$${\ displaystyle U}$${\ Displaystyle к \ geq 1}$

${\ Displaystyle U =}$ 'ага,' ага '

Дальнейшие разработки

Профессор Курт Эйсеманн из Государственного университета Сан-Диего в своем письме в Коммуникацию ACM дополнительно уточняет последнюю, казалось бы, непревзойденную оценку. Он начинает с наблюдения, что для практических приложений значение «скрытой константы» c в нотации Big Oh может иметь решающее значение для определения разницы между осуществимостью и невозможностью: например, постоянное значение 10 ⁸⁰ превысит возможности любого известное устройство. Далее он отмечает, что в средневековой Европе уже был известен метод, при котором текстовое содержание произвольной мелодии может быть записано на основе соотношения рекуррентности , где значение константы big-Oh c равно 2. Однако оказывается, что другая культура достигла абсолютной нижней границы O (0). Как сказал профессор Эйсеманн: ${\ Displaystyle S_ {k} = C_ {2} S_ {k-1}}$${\ displaystyle C_ {2} = 'la'}$

"Когда путешественники Мэйфлауэр впервые спустились на эти берега, коренные американцы, гордящиеся своими достижениями в теории хранения и поиска информации, сначала приветствовали незнакомцев полной тишиной. Это должно было передать их высшее достижение в сложности песен , а именно демонстрация того, что такой низкий предел, как c  = 0, действительно возможен ".

Однако европейцы не были готовы понять это понятие, и вожди , чтобы установить общую основу для передачи своих достижений, позже приступили к демонстрации подхода, описываемого рекуррентным соотношением , где с субоптимальной сложностью, задаваемой c  = 1. ${\ Displaystyle S_ {k} = C_ {1} S_ {k-1}}$${\ displaystyle C_ {1} = 'я'}$

Результат о сложности пространства O (1) был также реализован Гаем Л. Стилом-младшим , что, возможно, оспаривалось статьей Кнута. Песня доктора Стила TELNET использовала совершенно другой алгоритм, основанный на экспоненциальной рекурсии, пародию на некоторые реализации TELNET.

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

В статье профессора Алана Шермана «О суперполилогарифмических субэкспоненциальных функциях» написано, что статья Кнута является плодотворной для анализа специального класса функций.

Рекомендации

внешняя ссылка

• « Сложность песен », Кнут, Дональд Э. (1984).