Сложность песен

«Сложность песен» — научная статья ученого -компьютерщика Дональда Кнута , опубликованная в 1977 году. как шутка о теории сложности вычислений . В статье делается акцент на тенденции популярных песен превращаться из длинных и содержательных баллад в повторяющиеся тексты с небольшим содержанием или вообще без него. В статье отмечается, что песню длиной N слов можно создать, запомнив, например, только O ( log N ) слов (« пространственная сложность » песни) или даже меньше.

Краткое содержание статьи

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

Кнут далее демонстрирует способ создания песен со сложностью O ( √ N ) - подход, «далее усовершенствованный шотландским фермером по имени О. Макдональд ».

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

Finally, the progress during the 20th century—stimulated by the fact that "the advent of modern drugs has led to demands for still less memory"—leads to the ultimate improvement: Arbitrarily long songs with space complexity Наконец, прогресс 20-го века, стимулированный тем фактом, что «появление современных лекарств привело к необходимости еще меньшей памяти», приводит к окончательному улучшению: произвольно длинные песни с пространственной сложностью $O(1)$существует exist, e.g. a song defined by the , например, песня, определяемая рекуррентным соотношением

$S_{0}=\epsilon ,S_{k}=V_{k}S_{k-1},\,k\geq 1,$

V _k = ' Вот так ' U 'Мне это нравится' U для всех k ≥ 1

U = «ага», «ага»

Дальнейшие разработки

Профессор Курт Эйземан из Государственного университета Сан-Диего в своем письме в информационное агентство ACM. еще больше улучшает последнюю, казалось бы, непревзойденную оценку. Он начинает с наблюдения, что для практических приложений значение «скрытой константы» c в большой записи O может иметь решающее значение для определения разницы между выполнимостью и невозможностью: например, постоянное значение 10 ⁸⁰ превысит мощность любого известного устройства. уже был известен метод Далее он отмечает, что в средневековой Европе , с помощью которого текстовое содержание произвольной мелодии можно записать на основе рекуррентного соотношения. $S_{k}=C_{2}S_{k-1}$, где $C_{2}={\texttt {'la'}}$, что дает значение big -O константы c, равное 2. Однако оказывается, что другая культура достигла абсолютной нижней границы O (0). Как говорит профессор Эйземан:

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

Затем утверждается, что европейцы были не готовы понять это понятие, и вожди , чтобы установить общую основу для передачи своих достижений, позже приступили к демонстрации подхода, описываемого повторяющимся соотношением $S_{k}=C_{1}S_{k-1}$, где $C_{1}={\texttt {'i'}}$, с субоптимальной сложностью, заданной c = 1 .

Результат пространственной сложности O (1) также был реализован Гаем Л. Стилом-младшим , что, возможно, было оспорено статьей Кнута. доктора Стила TELNET В песне использовался совершенно другой алгоритм, основанный на экспоненциальной рекурсии, что является пародией на некоторые реализации TELNET.

Дарра Чейви предположила, что анализ сложности человеческих песен может быть полезным педагогическим инструментом для обучения студентов теории сложности.

Статья «О суперполилогарифмических субэкспоненциальных функциях». профессора Алана Шермана пишет, что статья Кнута оказалась плодотворной для анализа специального класса функций.

Внешние ссылки

• « Сложность песен », Кнут, Дональд Э. (1984).