Оценка сложности песен
«Оценка сложности песен» (англ. The Complexity of Songs) — статья, опубликованная теоретиком компьютерных наук Дональдом Кнутом в 1977 году[1], представляющая собой «шутку для посвящённых», связанную с теорией вычислительной сложности. Основной темой статьи является тенденция в эволюции популярной песни, связанная с переходом от длинных и наполненных содержанием баллад к текстам с высокой степенью повторяемости и малым (или вообще отсутствующим) осмысленным содержанием[2]. В статье отмечается, что некоторые песни могут достичь уровня сложности, соответствующего формуле O(log N), где 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 действительно является достижимым.
Оригинальный текст (англ.)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.
Однако европейцы оказались неподготовленными к восприятию этого понятия, и индейские вожди, чтобы найти общую почву для передачи своих достижений, впоследствии продемонстрировали подход, описываемый рекуррентным соотношением <math>S_k = C_1S_{k-1}</math>, где <math>C_1 = 'i'</math>, с субоптимальной сложностью, которую даёт значение c=1[2][3].
Напишите отзыв о статье "Оценка сложности песен"
Примечания
- ↑ 1 2 3 4 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.
- ↑ 1 2 Steven Krantz (2005) «Mathematical Apocrypha Redux», ISBN 0-88385-554-2, pp. 2, 3.
- ↑ 1 2 Kurt Eisemann, «Further Results on the Complexity of Songs», Communications of the ACM, vol 28 (1985), no. 3, p. 235.
Ссылки
- «[www.cs.utexas.edu/users/arvindn/misc/knuth_song_complexity.pdf The Complexity of Songs]», Knuth, Donald E. (1984).
- [www.rsdn.ru/article/alg/song_complexity.xml Перевод статьи].
| ||||||||||||||||||||||||||
|
Эта статья входит в число добротных статей русскоязычного раздела Википедии. |
Отрывок, характеризующий Оценка сложности песен
– Искусный полководец, – сказал Пьер, – ну, тот, который предвидел все случайности… ну, угадал мысли противника.– Да это невозможно, – сказал князь Андрей, как будто про давно решенное дело.
Пьер с удивлением посмотрел на него.
– Однако, – сказал он, – ведь говорят же, что война подобна шахматной игре.
– Да, – сказал князь Андрей, – только с тою маленькою разницей, что в шахматах над каждым шагом ты можешь думать сколько угодно, что ты там вне условий времени, и еще с той разницей, что конь всегда сильнее пешки и две пешки всегда сильнее одной, a на войне один батальон иногда сильнее дивизии, а иногда слабее роты. Относительная сила войск никому не может быть известна. Поверь мне, – сказал он, – что ежели бы что зависело от распоряжений штабов, то я бы был там и делал бы распоряжения, а вместо того я имею честь служить здесь, в полку вот с этими господами, и считаю, что от нас действительно будет зависеть завтрашний день, а не от них… Успех никогда не зависел и не будет зависеть ни от позиции, ни от вооружения, ни даже от числа; а уж меньше всего от позиции.
– А от чего же?
– От того чувства, которое есть во мне, в нем, – он указал на Тимохина, – в каждом солдате.
Князь Андрей взглянул на Тимохина, который испуганно и недоумевая смотрел на своего командира. В противность своей прежней сдержанной молчаливости князь Андрей казался теперь взволнованным. Он, видимо, не мог удержаться от высказывания тех мыслей, которые неожиданно приходили ему.
– Сражение выиграет тот, кто твердо решил его выиграть. Отчего мы под Аустерлицем проиграли сражение? У нас потеря была почти равная с французами, но мы сказали себе очень рано, что мы проиграли сражение, – и проиграли. А сказали мы это потому, что нам там незачем было драться: поскорее хотелось уйти с поля сражения. «Проиграли – ну так бежать!» – мы и побежали. Ежели бы до вечера мы не говорили этого, бог знает что бы было. А завтра мы этого не скажем. Ты говоришь: наша позиция, левый фланг слаб, правый фланг растянут, – продолжал он, – все это вздор, ничего этого нет. А что нам предстоит завтра? Сто миллионов самых разнообразных случайностей, которые будут решаться мгновенно тем, что побежали или побегут они или наши, что убьют того, убьют другого; а то, что делается теперь, – все это забава. Дело в том, что те, с кем ты ездил по позиции, не только не содействуют общему ходу дел, но мешают ему. Они заняты только своими маленькими интересами.
– В такую минуту? – укоризненно сказал Пьер.
– В такую минуту, – повторил князь Андрей, – для них это только такая минута, в которую можно подкопаться под врага и получить лишний крестик или ленточку. Для меня на завтра вот что: стотысячное русское и стотысячное французское войска сошлись драться, и факт в том, что эти двести тысяч дерутся, и кто будет злей драться и себя меньше жалеть, тот победит. И хочешь, я тебе скажу, что, что бы там ни было, что бы ни путали там вверху, мы выиграем сражение завтра. Завтра, что бы там ни было, мы выиграем сражение!
– Вот, ваше сиятельство, правда, правда истинная, – проговорил Тимохин. – Что себя жалеть теперь! Солдаты в моем батальоне, поверите ли, не стали водку, пить: не такой день, говорят. – Все помолчали.
Офицеры поднялись. Князь Андрей вышел с ними за сарай, отдавая последние приказания адъютанту. Когда офицеры ушли, Пьер подошел к князю Андрею и только что хотел начать разговор, как по дороге недалеко от сарая застучали копыта трех лошадей, и, взглянув по этому направлению, князь Андрей узнал Вольцогена с Клаузевицем, сопутствуемых казаком. Они близко проехали, продолжая разговаривать, и Пьер с Андреем невольно услыхали следующие фразы:
– Der Krieg muss im Raum verlegt werden. Der Ansicht kann ich nicht genug Preis geben, [Война должна быть перенесена в пространство. Это воззрение я не могу достаточно восхвалить (нем.) ] – говорил один.
– O ja, – сказал другой голос, – da der Zweck ist nur den Feind zu schwachen, so kann man gewiss nicht den Verlust der Privatpersonen in Achtung nehmen. [О да, так как цель состоит в том, чтобы ослабить неприятеля, то нельзя принимать во внимание потери частных лиц (нем.) ]
– O ja, [О да (нем.) ] – подтвердил первый голос.
– Да, im Raum verlegen, [перенести в пространство (нем.) ] – повторил, злобно фыркая носом, князь Андрей, когда они проехали. – Im Raum то [В пространстве (нем.) ] у меня остался отец, и сын, и сестра в Лысых Горах. Ему это все равно. Вот оно то, что я тебе говорил, – эти господа немцы завтра не выиграют сражение, а только нагадят, сколько их сил будет, потому что в его немецкой голове только рассуждения, не стоящие выеденного яйца, а в сердце нет того, что одно только и нужно на завтра, – то, что есть в Тимохине. Они всю Европу отдали ему и приехали нас учить – славные учители! – опять взвизгнул его голос.
