Сложность песен
«Сложность песен» — научная статья ученого -компьютерщика Дональда Кнута , опубликованная в 1977 году. [1] как шутка о теории сложности вычислений . В статье делается акцент на тенденции популярных песен превращаться из длинных и содержательных баллад в повторяющиеся тексты с небольшим содержанием или вообще без него. [2] В статье отмечается, что песню длиной N слов можно создать, запомнив, например, только O ( log N ) слов (« пространственная сложность » песни) или даже меньше.
Краткое содержание статьи [ править ]
Кнут пишет, что «наши древние предки изобрели концепцию рефрена », чтобы уменьшить пространственную сложность песен, что становится решающим, когда нужно запомнить большое количество песен . Кнута Лемма 1 утверждает, что если N — длина песни, то припев уменьшает сложность песни до cN , где коэффициент c < 1 . [1]
Кнут далее демонстрирует способ создания песен со сложностью O ( √ N ) - подход, «далее усовершенствованный шотландским фермером по имени О. Макдональд ». [1]
Более изобретательные подходы дают более сложные песни. , класс, известный как « м бутылок пива на стене ».
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-го века, стимулированный тем фактом, что «появление современных лекарств привело к необходимости еще меньшей памяти», приводит к окончательному улучшению: произвольно длинные песни с пространственной сложностью существует exist, e.g. a song defined by the , например, песня, определяемая рекуррентным соотношением [1]
- V k = ' Вот так ' U 'Мне это нравится' U для всех k ≥ 1
- U = «ага», «ага»
Дальнейшие разработки [ править ]
Профессор Курт Эйземан из Государственного университета Сан-Диего в своем письме в информационное агентство ACM. [3] еще больше улучшает последнюю, казалось бы, непревзойденную оценку. Он начинает с наблюдения, что для практических приложений значение «скрытой константы» c в большой записи O может иметь решающее значение для определения разницы между выполнимостью и невозможностью: например, постоянное значение 10 80 превысит мощность любого известного устройства. уже был известен метод Далее он отмечает, что в средневековой Европе , с помощью которого текстовое содержание произвольной мелодии можно записать на основе рекуррентного соотношения. , где , что дает значение big -O константы c, равное 2. Однако оказывается, что другая культура достигла абсолютной нижней границы O (0). Как говорит профессор Эйземан:
Когда путешественники «Мэйфлауэр» впервые спустились на эти берега, коренные американцы, гордые своими достижениями в теории хранения и поиска информации, поначалу приветствовали чужаков полным молчанием. Это было призвано продемонстрировать их высшее достижение в сложности песен, а именно продемонстрировать, что такой низкий предел, как c действительно достижим = 0.
Затем утверждается, что европейцы были не готовы понять это понятие, и вожди , чтобы установить общую основу для передачи своих достижений, позже приступили к демонстрации подхода, описываемого повторяющимся соотношением , где , с субоптимальной сложностью, заданной c = 1 . [2] [3]
Результат пространственной сложности O (1) также был реализован Гаем Л. Стилом-младшим , что, возможно, было оспорено статьей Кнута. [4] доктора Стила TELNET В песне использовался совершенно другой алгоритм, основанный на экспоненциальной рекурсии, что является пародией на некоторые реализации TELNET. [5] [6] [7]
Дарра Чейви предположила, что анализ сложности человеческих песен может быть полезным педагогическим инструментом для обучения студентов теории сложности. [8]
Статья «О суперполилогарифмических субэкспоненциальных функциях». профессора Алана Шермана [9] пишет, что статья Кнута оказалась плодотворной для анализа специального класса функций.
Ссылки [ править ]
- ↑ Перейти обратно: Перейти обратно: а б с д Кнут, Дональд (лето 1977 г.). «Сложность песен» . Новости СИГАКТ . 9 (2): 17–24. дои : 10.1145/1008354.1008355 . S2CID 17533775 . Перепечатано в: Кнут, Дональд (1984). «Сложность песен» . Коммуникации АКМ . 27 (4): 344–346. дои : 10.1145/358027.358042 . МР 0784131 .
- ↑ Перейти обратно: Перейти обратно: а б Стивен Кранц (2005) «Математический повтор апокрифов», ISBN 0-88385-554-2 , стр. 2, 3.
- ↑ Перейти обратно: Перейти обратно: а б Курт Эйземан, «Дальнейшие результаты по сложности песен», Сообщения ACM , том. 28 (1985), вып. 3, с. 235.
- ^ Питер Г. Нейман, «Дальнейший взгляд на первую четверть века», Communications of ACM , vol. 27, вып. 4 апреля 1984 г., с. 343
- ↑ Гай Л. Стил-младший , «Песня Telnet», Communications of the ACM , апрель 1984 г.
- ↑ Текст песни TELNET (получено 5 января 2012 г.).
- ^ Песня Telnet в формате MIDI .
- ^ Чави, Дарра (1996). «Песни и анализ алгоритмов» . Материалы двадцать седьмого технического симпозиума SIGCSE по компьютерному образованию . Зигче '96 . стр. 4–8. дои : 10.1145/236452.236475 . ISBN 089791757X . S2CID 148247 . Проверено 7 января 2013 г.
- ^ Алан Шерман, «О суперполилогарифмических субэкспоненциальных функциях» ( формат PostScript ), ACM SIGACT News , vol. 22, нет. 1, 1991, с. 65.
Внешние ссылки [ править ]
- « Сложность песен », Кнут, Дональд Э. (1984).