Оценка сложности песен

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

Оценка сложности песен
Общая информация
Автор	Дональд Эрвин Кнут
Название	англ. The Complexity of Songs
Дата публикации	1977
Опубликовано в	Communications of the ACM
Том	27
Выпуск	4
Страницы	17–24
Лицензия	проприетарная
Идентификаторы
DOI	10.1145/358027.358042
Полный текст
Информация в Викиданных ?

Содержание статьи

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

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

Ещё более сложный подход дают песни сложностью O($\log N$). Это класс песен, известный как «m бутылок пива на стене».

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

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

$V_{k}=$ 'That’s the way,' $U$ 'I like it,' $U$, $\forall$ $k\geq 1$

$U=$ 'uh huh,' 'uh huh'

Последующие исследования

Профессор Курт Айземанн из университета Сан-Диего в письме в журнал Communications of the ACM делает дальнейшие улучшения последней, представлявшейся не подлежащей улучшению оценки, O(1). Он начинает с наблюдения, согласно которому в практических приложениях значение «скрытой константы» c в нотации «O» большого может иметь критическое значение, проводя грань между приемлемостью и неприемлемостью: например, значение константы 10⁸⁰ приведёт к тому, что объём информации превысит ёмкость любого из известных науке средств хранения информации. Далее он отмечает, что уже в средневековой Европе была известна техника, с использованием которой текстовое содержание любой произвольной мелодии может быть описано рекуррентным соотношением $S_{k}=C_{2}S_{k-1}$, где $C_{2}='la'$, что даёт значение константы c, равное 2. Однако, как оказалось, другая культура достигла абсолютного нижнего предела сложности O(0)! Профессор Айземанн формулирует это следующим образом:

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

Оригинальный текст (англ.)

When the Mayflower voyagers first descended on these shores, the native Americans proud of their achievement in the theory of information storage and retrieval, at first welcomed the strangers with the complete silence. This was meant to convey their peak achievement in the complexity of songs, namely the demonstration that a limit as low as c=0 is indeed obtainable.

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

Ссылки

• «The Complexity of Songs», Knuth, Donald E. (1984).
• Перевод статьи Архивная копия от 26 февраля 2013 на Wayback Machine.