WikiSort.ru - Музыка

ПОИСК ПО САЙТУ | о проекте
Оценка сложности песен
Общая информация
Автор: Дональд Эрвин Кнут
Название: англ. The Complexity of Songs
Дата публикации: 1977
Опубликовано в Communications of the ACM
Том 27
Выпуск 4
Страницы 17–24
Лицензия All rights reserved
Идентификаторы
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.

Ссылки

Данная страница на сайте WikiSort.ru содержит текст со страницы сайта "Википедия".

Если Вы хотите её отредактировать, то можете сделать это на странице редактирования в Википедии.

Если сделанные Вами правки не будут кем-нибудь удалены, то через несколько дней они появятся на сайте WikiSort.ru .




Текст в блоке "Читать" взят с сайта "Википедия" и доступен по лицензии Creative Commons Attribution-ShareAlike; в отдельных случаях могут действовать дополнительные условия.

Другой контент может иметь иную лицензию. Перед использованием материалов сайта WikiSort.ru внимательно изучите правила лицензирования конкретных элементов наполнения сайта.

2019-2024
WikiSort.ru - проект по пересортировке и дополнению контента Википедии