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

Шаблон:Научная статья «Оценка сложности песен» (Шаблон:Lang-en) — статья, опубликованная теоретиком компьютерных наук Дональдом Кнутом в 1977 году, представляющая собой «шутку для посвящённых», связанную с теорией вычислительной сложности. Основной темой статьи является тенденция в эволюции популярной песни, связанная с переходом от длинных и наполненных содержанием баллад к текстам с высокой степенью повторяемости и малым (или вообще отсутствующим) осмысленным содержанием. В статье отмечается, что некоторые песни могут достичь уровня сложности, соответствующего формуле Шаблон:Nowrap, где N — число слов в песне.

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

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

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

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

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

$S_0=ϵ,S_k=V_k{S}_{k-1},k\ge 1,$

$V_k=$ 'That’s the way,' $U$ 'I like it,' $U$, $\mathrm{\forall }$ $k\ge 1$

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

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

Профессор Курт Айземанн из университета Сан-Диего в письме в журнал Communications of the ACM делает дальнейшие улучшения последней, представлявшейся не подлежащей улучшению оценки, O(1). Он начинает с наблюдения, согласно которому в практических приложениях значение «скрытой константы» c в нотации «O» большого может иметь критическое значение, проводя грань между приемлемостью и неприемлемостью: например, значение константы 10⁸⁰ приведёт к тому, что объём информации превысит ёмкость любого из известных науке средств хранения информации. Далее он отмечает, что уже в средневековой Европе была известна техника, с использованием которой текстовое содержание любой произвольной мелодии может быть описано рекуррентным соотношением $S_k=C_2{S}_{k-1}$, где $C_2{=}^{\prime }l{a}^{\prime }$, что даёт значение константы c, равное 2. Однако, как оказалось, другая культура достигла абсолютного нижнего предела сложности O(0)! Профессор Айземанн формулирует это следующим образом: Шаблон:Начало цитаты Когда путешественники с «Мейфлауэра» сошли на этот берег, коренные американцы, гордые своими достижениями в теории хранения и доступа к информации, сперва встретили незнакомцев полным молчанием. Это было средством донести их высшее достижение в сложности песен, а именно продемонстрировать, что низший предел c=0 действительно является достижимым. Шаблон:Oq Шаблон:Конец цитаты Однако европейцы оказались неподготовленными к восприятию этого понятия, и индейские вожди, чтобы найти общую почву для передачи своих достижений, впоследствии продемонстрировали подход, описываемый рекуррентным соотношением $S_k=C_1{S}_{k-1}$, где $C_1{=}^{\prime }{i}^{\prime }$, с субоптимальной сложностью, которую даёт значение c=1.

Ссылки

• «The Complexity of Songs», Knuth, Donald E. (1984).
• Перевод статьи Шаблон:Wayback.