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

Научная статья Дональда Кнута 1977 г.

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

Резюме статьи

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

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

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

Наконец, прогресс в течение 20-го века, стимулируемый тем фактом, что «появление современных лекарств привело к потребности в еще меньшем объеме памяти», приводит к конечному улучшению: существуют произвольно длинные песни с пространственной сложностью , например ${\displaystyle O(1)}$ , песня, определяемая рекуррентным соотношением ^[1]

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

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

U = 'угу', 'угу'

Дальнейшее развитие событий

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

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

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

Результат сложности пространства O (1) был также реализован Гаем Л. Стилом-младшим , возможно, оспоренным статьей Кнута. ^[4] Песня доктора Стила TELNET использовала совершенно другой алгоритм, основанный на экспоненциальной рекурсии, пародию на некоторые реализации TELNET. ^{[5] [6] [7]}

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

В статье «О суперполилогарифмических субэкспоненциальных функциях » профессора  Алана Шермана ^[9] говорится, что статья Кнута была основополагающей для анализа специального класса функций.

Ссылки

1. Кнут, Дональд (лето 1977). «Сложность песен». ACM SIGACT News . 9 (2): 17–24. doi : 10.1145/1008354.1008355 . S2CID  17533775.Перепечатано в: Кнут, Дональд (1984). «Сложность песен». Сообщения ACM . 27 (4): 344–346. doi : 10.1145/358027.358042 . MR  0784131.
2. Стивен Кранц (2005) «Математический апокриф Redux», ISBN 0-88385-554-2 , стр.2, 3. 
3. Ashenhurst, Robert L. (1985). «Форум ACM». Сообщения ACM . 28 (3): 235–240. doi :10.1145/3166.315004.
4. Нойманн, Питер Г. (1984). «Дальнейший взгляд на первую четверть века». Сообщения ACM . 27 (4): 343. doi :10.1145/358027.358040.
5. Стил, Гай Л. (1984). "ПЕСНЯ TELNET: ("Control-Uparrow Q.")". Сообщения ACM . 27 (4): 347–348. doi :10.1145/358027.1035691.
6. Текст песни TELNET (получено 5 января 2012 г.).
7. Песня Telnet в формате MIDI.
8. Чави, Дарра (1996). «Песни и анализ алгоритмов». Труды двадцать седьмого технического симпозиума SIGCSE по образованию в области компьютерных наук . стр. 4–8. doi :10.1145/236452.236475. ISBN 089791757X. S2CID  148247 . Получено 7 января 2013 г. .
9. Шерман, Алан Т. (1991). «О суперполилогарифмических субэкспоненциальных функциях (часть I)». ACM SIGACT News . 22 : 65. doi : 10.1145/122413.990652 .

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

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