Русская Википедия:Оценка сложности песен
Шаблон:Научная статья «Оценка сложности песен» (Шаблон:Lang-en) — статья, опубликованная теоретиком компьютерных наук Дональдом Кнутом в 1977 году[1], представляющая собой «шутку для посвящённых», связанную с теорией вычислительной сложности. Основной темой статьи является тенденция в эволюции популярной песни, связанная с переходом от длинных и наполненных содержанием баллад к текстам с высокой степенью повторяемости и малым (или вообще отсутствующим) осмысленным содержанием[2]. В статье отмечается, что некоторые песни могут достичь уровня сложности, соответствующего формуле Шаблон:Nowrap, где N — число слов в песне.
Содержание статьи
Кнут делает утверждение, согласно которому «наши далёкие предки изобрели концепцию припева», чтобы уменьшить пространственную сложность песен, которая становится важным фактором, когда необходимо запомнить большое число песен. Лемма 1 в статье устанавливает, что если длина песни обозначена N, то добавление припева уменьшает сложность песни до cN, где коэффициент c < 1[1].
Далее Кнут демонстрирует способ построения песен со сложностью O(<math>\sqrt N</math>), указывая, что этот подход «позже был улучшен шотландским фермером по имени С. Макдональд»[1].
Ещё более сложный подход дают песни сложностью O(<math>\log N</math>). Это класс песен, известный как «m бутылок пива на стене».
Наконец, в ходе XX века прогресс, стимулируемый тем фактом, что «распространение современных наркотиков привело к потребности в ещё меньшем использовании памяти», привёл к тому, что появились песни произвольной длины с пространственной сложностью O(1), например, песня, определяемая следующим рекуррентным соотношением[1]:
- <math>S_0=\epsilon, S_k = V_kS_{k-1},\, k\ge 1,</math>
- <math>V_k =</math> 'That’s the way,' <math>U</math> 'I like it,' <math>U</math>, <math>\forall</math> <math> k \ge 1</math>
- <math>U=</math> 'uh huh,' 'uh huh'
Последующие исследования
Профессор Курт Айземанн из университета Сан-Диего в письме в журнал Communications of the ACM[3] делает дальнейшие улучшения последней, представлявшейся не подлежащей улучшению оценки, O(1). Он начинает с наблюдения, согласно которому в практических приложениях значение «скрытой константы» c в нотации «O» большого может иметь критическое значение, проводя грань между приемлемостью и неприемлемостью: например, значение константы 1080 приведёт к тому, что объём информации превысит ёмкость любого из известных науке средств хранения информации. Далее он отмечает, что уже в средневековой Европе была известна техника, с использованием которой текстовое содержание любой произвольной мелодии может быть описано рекуррентным соотношением <math>S_k = C_2S_{k-1}</math>, где <math>C_2 = 'la'</math>, что даёт значение константы c, равное 2. Однако, как оказалось, другая культура достигла абсолютного нижнего предела сложности O(0)! Профессор Айземанн формулирует это следующим образом: Шаблон:Начало цитаты Когда путешественники с «Мейфлауэра» сошли на этот берег, коренные американцы, гордые своими достижениями в теории хранения и доступа к информации, сперва встретили незнакомцев полным молчанием. Это было средством донести их высшее достижение в сложности песен, а именно продемонстрировать, что низший предел c=0 действительно является достижимым. Шаблон:Oq Шаблон:Конец цитаты Однако европейцы оказались неподготовленными к восприятию этого понятия, и индейские вожди, чтобы найти общую почву для передачи своих достижений, впоследствии продемонстрировали подход, описываемый рекуррентным соотношением <math>S_k = C_1S_{k-1}</math>, где <math>C_1 = 'i'</math>, с субоптимальной сложностью, которую даёт значение c=1[2][3].
Примечания
Ссылки
- «The Complexity of Songs», Knuth, Donald E. (1984).
- Перевод статьи Шаблон:Wayback.
Шаблон:Дональд Кнут Шаблон:Добротная статья
- ↑ 1,0 1,1 1,2 1,3 Knuth, D. «The Complexity of Songs», SIGACT News, Summer 1977, 17—24.
- Reprinted in: Knuth, D. «The Complexity of Songs», Communications of the ACM, 1984, 27 (4) pp. 344—346.
- ↑ 2,0 2,1 Steven Krantz (2005) «Mathematical Apocrypha Redux», ISBN 0-88385-554-2, pp. 2, 3.
- ↑ 3,0 3,1 Kurt Eisemann, «Further Results on the Complexity of Songs», Communications of the ACM, vol 28 (1985), no. 3, p. 235.
