Эта статья входит в число добротных статей

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

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

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

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

[править | править код]

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

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

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

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

'That’s the way,' 'I like it,' ,
'uh huh,' 'uh huh'

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

[править | править код]

Профессор Курт Айземанн из университета Сан-Диего в письме в журнал Communications of the ACM[3] делает дальнейшие улучшения последней, представлявшейся не подлежащей улучшению оценки, O(1). Он начинает с наблюдения, согласно которому в практических приложениях значение «скрытой константы» c в нотации «O» большого может иметь критическое значение, проводя грань между приемлемостью и неприемлемостью: например, значение константы 1080 приведёт к тому, что объём информации превысит ёмкость любого из известных науке средств хранения информации. Далее он отмечает, что уже в средневековой Европе была известна техника, с использованием которой текстовое содержание любой произвольной мелодии может быть описано рекуррентным соотношением , где , что даёт значение константы c, равное 2. Однако, как оказалось, другая культура достигла абсолютного нижнего предела сложности O(0)! Профессор Айземанн формулирует это следующим образом:

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

Однако европейцы оказались неподготовленными к восприятию этого понятия, и индейские вожди, чтобы найти общую почву для передачи своих достижений, впоследствии продемонстрировали подход, описываемый рекуррентным соотношением , где , с субоптимальной сложностью, которую даёт значение c=1[2][3].

Примечания

[править | править код]
  1. 1 2 3 4 Knuth, D. «The Complexity of Songs», SIGACT News, Summer 1977, 17—24.
  2. 1 2 Steven Krantz (2005) «Mathematical Apocrypha Redux», ISBN 0-88385-554-2, pp. 2, 3.
  3. 1 2 Kurt Eisemann, «Further Results on the Complexity of Songs», Communications of the ACM, vol 28 (1985), no. 3, p. 235.