Какие бумаги должны прочитать все?

454

Этот вопрос (вдохновленный) / (позорно украденный) похож на вопрос в MathOverflow , но я ожидаю, что ответы здесь будут совсем другими.

У всех нас есть любимые статьи в наших соответствующих областях теории. Время от времени каждый находит бумагу настолько поразительной (например, важной, неотразимой, обманчиво простой и т. Д.), Что каждый хочет поделиться ею со всеми. Так что перечислите эти документы здесь! Они не должны быть из теоретической информатики - все, что, по вашему мнению, может понравиться сообществу, является хорошим ответом.

Вы можете дать столько ответов, сколько захотите; пожалуйста, положите одну бумагу за ответ ! Также обратите внимание, что это вики сообщества, поэтому голосуйте за все, что вам нравится!

(Обратите внимание, что ранее был задан вопрос о работах с теоретико-рекурсивной сложностью, но он довольно специализированный.)

Райан Уильямс
источник
65
В ответах я хотел бы видеть больший акцент на том, является ли в действительности хорошей идеей чтение оригинальной статьи в настоящее время (или имеет ли смысл читать ее в современном учебнике). Я слишком часто видел документы TCS, которые действительно являются оригинальными, но я бы предпочел избавить моих коллег от боли попыток расшифровать оригинальную рецензию - которая слишком часто является наспех написанным 10-страничным рефератом конференции со ссылками к "полной версии", которая никогда не появлялась ...
Юкка Суомела
7
Да, я надеюсь, что ясно, что документы этого типа не подходят для списка (если вы хотите поделиться им со всеми, читать не должно быть больно)
Райан Уильямс
30
Слишком много людей просто публикуют однострочники. Любой может опубликовать сотни уникальных статей, не задумываясь об этом. Пожалуйста, напишите, почему вы думаете, что все должны читать эти статьи. Это означает оправдание того, почему они должны читать эту статью вместо чьей-либо записи этого результата , и что такого удивительного в этой статье, что все должны ее прочитать.
Робин Котари
Хороший вопрос. Мое мнение таково, что если вы хотите понять мысли изобретателей и, возможно, понять, как придумывать вещи, вы должны читать свои слова. Чем больше вы работаете, тем ближе вы подходите к их реальному мыслительному процессу.
ixtmixilix

Ответы:

145

Статья 1936 года, которая, возможно, положила начало информатике:

  • Алан Тьюринг, «О вычислимых числах, с приложением к проблеме Энтшайдунгса», Труды Лондонского математического общества s2-42, 230–265, 1937. doi: 10.1112 / plms / s2-42.1.230

Всего лишь на 36 страницах Тьюринг формулирует (но не называет) машину Тьюринга, пересматривает знаменитую первую теорему Гёделя о неполноте в терминах вычислений, описывает концепцию универсальности и в приложении показывает, что вычислимость машинами Тьюринга эквивалентна вычислимости по определяемые функции (как изучал Черч и Клини).λ

András Salamon
источник
7
Это также очень доступно и читабельно ...
Сариэль Хар-Пелед
25
и вместе с ним «Аннотированная Тьюринг» Чарльза Петцольда [
настоятельно
123

« Размышления о доверии » Кена Томпсона . Короткий, сладкий и умопомрачительный.

оборота Jɛ ff E
источник
5
Также очень доступно. Я читал это довольно давно, когда у меня практически не было опыта работы с CS, не было опыта программирования и я даже не знал, что такое компилятор.
Йорг Миттаг
1
«На прошлой неделе Гуглер Кен Томпсон был удостоен Японской премии в области информации и связи за его раннюю работу над операционной системой UNIX». (источник: Buzz сообщение от Life в Google)
Себастьян Гриньоли
4
Я думаю, что эту статью будет довольно трудно переварить, хотя бы не зная, что такое компилятор.
Fixee
2
В статье я думаю, что цифры 2.1 и 2.2 поменялись местами.
Деннис
1
Не согласен - ничего удивительного или умопомрачительного в этой статье. TL; DR 6 страниц с середины 80-х о «необходимости изменить уголовный кодекс, чтобы начать наказывать хакеров [как воров или грабителей]». О да, упоминает о квине , не называя ее по имени.
c69
94

Что каждый ученый должен знать об арифметике с плавающей точкой

Эта статья объясняет и усиливает представление о том, что с плавающей точкой не волшебство. Это объясняет переполнение, недостаток, что такое денормализованные числа, что такое NaN, что такое inf, и все, что они подразумевают. Прочитав эту статью, вы поймете, почему a == a + 1.0 может быть истинным, почему a == a может быть ложным, почему запуск вашего кода на двух разных машинах может дать вам два разных ответа, почему суммирование чисел в разных порядок может дать вам разность порядка величины и все дурацкие вещи, которые происходят в мире отображения бесконечно бесконечного множества чисел на счетно конечное множество.

Отредактированная версия также доступна в Интернете.

Рик Вебер
источник
3
Пожалуйста, исправьте ссылку. Это сломано.
Оскар Медерос
1
С тех пор как Oracle приобрел Sun, он разрушил большинство ссылок с веб-страницы Sun. Хотя вы можете добраться до оригинальной статьи отсюда .
системный сбой
это могло быть этим? ece.uwaterloo.ca/~dwharder/NumericAnalysis/02Numerics/Double/…
Blackle Mori
1
Исправлена ​​неработающая ссылка.
Райан
85

Кешава Как читать газету . Вы также можете скачать статью здесь .

Dai Le
источник
Действительно, приятно читать.
Энтони Лабарре
Я всегда думаю, что исследовательские работы по CS написаны на каком-то иностранном языке.
Берлин Браун
3
Отлично! Стоит поставить на баннер слоган на сайте, чтобы никто из студентов не пропустил это.
Vag
Вторая ссылка в настоящее время не работает
Кристофер Мэннинг
2
Это мой любимый из списка. Также обратите внимание, что это живой документ, в отличие от большинства статей, которые не получают обновлений после публикации.
Деннис
67

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

ильяраз
источник
61

Приводимость среди комбинаторных проблем Ричард Карп. В статье содержится то, что часто называют «оригинальными 21-полными задачами» Карпа. Во многих отношениях эта статья действительно мотивировала изучение NP-полноты, демонстрируя ее применимость к более широкой области. Очень читабельно.

Daniel Apon
источник
6
Мне нравится эта статья, но некоторые сокращения действительно отрывочны, и за ними трудно следовать. Смотрите любой текст сложности для более подробной информации.
Андрас Саламон
2
@ Андрас Саламон Я согласен на 100%.
Tayfun Pay
52

Хартманис и Стернс, «О вычислительной сложности алгоритмов» , Труды Американского математического общества 117: 285–306 (1965)

Это была первая статья, в которой всерьез изучалось изучение сложности времени, и, безусловно, это стало главным стимулом для совместной премии Хьюрманиса и Стернса Тьюринга. Хотя их первоначальные определения не совсем то, что мы используем сегодня, документ остается чрезвычайно читабельным. Вы действительно чувствуете, как обстоят дела на старой границе Дикого Запада 60-х годов.

Райан Уильямс
источник
Рабочая ссылка. pdfs.semanticscholar.org/1ce8/…
Гарднер
51

Квантово-механические компьютеры (PDF) Ричард Фейнман.

Он вводит идею квантовых вычислений, описывает квантовые схемы, объясняет, как классические схемы могут быть смоделированы квантовыми схемами, и показывает, как квантовые схемы могут вычислять функции без большого количества мусорных кубитов (используя невычисление).

Затем он показывает, как любая классическая схема может быть закодирована в не зависящий от времени гамильтониан! Его доказательство распространяется и на квантовые схемы, поэтому он показывает, что эволюционирующие во времени гамильтонианы BQP-сложны! Его гамильтонова конструкция также используется в доказательстве квантовой версии теоремы Кука-Левина, доказанной Китаевым, которая показывает, что k-локальный гамильтониан является QMA-полным.

Робин Котари
источник
Ссылка не действительна. У вас есть другой источник? edit> Поиск в Google: wjzeng.net/Ref/Feynman_QuantumMechanicalComputers.pdf Это один?
2010 года
Это тот самый. Я добавил новую ссылку и ссылку на ее страницу на сайте издателя.
Робин Котари
Существовали ли понятия BQP и QMA, когда Фейнман писал эту статью? Или есть недавняя статья, которая рисует эту связь? Любая ссылка / изложение этого факта, что k-локальный гамильтониан QMA полон?
Anirbit
48

Графы расширителей и их приложения, С. Хори, Н. Линиал и А. Вигдерсон - очень хороший обзор графов расширителей. Не удивительно, что он выиграл приз AMS Conant 2008 года.

Я хочу напомнить, что графики расширителей являются ключевым компонентом в недавних открытиях в TCS, например.

и не так давно

Dai Le
источник
1
Вы должны следить за комбинаторными или вспомогательными прекондиционерами. Графики расширителей даже используются в численном анализе сегодня.
Шухало
44

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

Аарон Стерлинг
источник
Версия издателя: doi.org/10.1007/s00446-003-0091-y
Андрас Саламон,
Можете
44

Я удивлен тем, что никто не придумал «Некоторые оптимальные результаты неадекватности» Хастада (JACM 2001; первоначально STOC 1997). Эта знаковая статья написана так хорошо, что вы можете прийти к ней с небольшой математической зрелостью, и это заставит вас захотеть хорошо изучить несколько вещей, таких как методы Фурье, параллельное повторение, гаджеты и еще много чего.

user289
источник
44

O((logN)3)O(exp((649b)13(logb)23))

Pratik Deoghare
источник
42

Les искателя в Теория Обучающийся (1984) установить программу для теории обучения на протяжении десятилетий, и это приятно и читаемым бумага!

В статье также есть довольно интуитивное объяснение, которое делает его увлекательным и убедительным. Различные части этого документа все еще регулярно цитируются в разговорах COLT / ALT.

Лев Рейзин
источник
42

Возможно, слишком простой, но я шокирован тем, что никто не упомянул оригинальные лямбда-статьи Стила и Суссмана: SCHEME: интерпретатор расширенного лямбда-исчисления , Lambda: конечный императив , Lambda: окончательный декларативный .

sclv
источник
3
Я бы проголосовал один раз за каждую лямбда-газету, если бы мог.
jkff
41

Рекурсивные функции символических выражений Джона Маккарти и их вычисление на машине, часть I.

Это основополагающая статья о Лиспе. Здесь мы находим первый метакруглый оценщик, помещающийся на одной странице. Его влияние невозможно переоценить, и оно все еще в высшей степени читаемо.

Пер Вогсен
источник
37

Сложность процедур доказательства теорем Стивена А. Кука. Эта статья доказывает, что все языки, определяемые недетерминированными машинами Тьюринга с полимитами, могут быть (Кука) сведены к набору пропозициональных тавтологий.

Важность этого результата (по крайней мере) двояка: во-первых, он показывает, что в NP существуют проблемы, которые, по крайней мере, такие же сложные, как у всего класса, NP- полные проблемы; кроме того, он предоставляет конкретный пример такой проблемы, которая затем может быть сведена к другим, чтобы доказать, что они решены.

В настоящее время сокращения Карпа используются чаще, чем сокращения Кука, но основное доказательство этой статьи легко адаптировать, чтобы показать, что SAT является NP- полной по отношению к сокращениям Карпа.

Антонио Э. Поррека
источник
7
Это одна из тех конференций, для которых не было опубликовано ни одной версии журнала, но к этой, безусловно, стоит вернуться: хорошо написано и полно замечательных дополнительных комментариев.
Андрас Саламон
36

CAR Hoare, Аксиоматическая основа для компьютерного программирования .

Из аннотации: В этой статье сделана попытка исследовать логические основы компьютерного программирования с использованием методов, которые были впервые применены при изучении геометрии, а затем были распространены на другие разделы математики.

Он имеет шесть страниц, за которыми довольно легко следить.

оборота Раду ГРИГОРЕ
источник
34

Алон, Матиас и Сегеди, Пространственная сложность аппроксимации частотных моментов , JCSS 58 (1): 137-147, 1999.

Эта довольно волшебная статья была первой, которая формализовала алгоритмы потоковой передачи и доказала строгие верхние и нижние оценки для основных задач в потоковой модели. Его методы просты, его доказательства прекрасны, и его влияние было глубоким. Работа получила Алон, Матиас и Сегеди премии Геделя в 2005 году.

Арнаб
источник
Данг. Я собирался добавить это :)
Суреш Венкат
30

Статья Иммермана, доказывающая теорему, теперь известную как теорема Иммермана – Селецкого, является отличным примером легко читаемой, умной и короткой статьи. Мне нравится история, рассказанная во вступлении.

Н. Иммерман, Недетерминированное пространство закрыто при дополнении, SIAM Journal of Computing 17, 1988, pp. 935–938.

Михаэль Кадилхак
источник
1
Справедливости ради следует отметить, что статья Селецченьи «Метод принудительного перечисления недетерминированных автоматов» также хороша.
Лев Рейзин
30

f(n)log(n)

NSPACE(f(n))DSPACE((f(n))2).

NPSPACE=PSPACEPNP

Савич, Уолтер Дж. (1970), «Отношения между недетерминированными и детерминированными лентными сложностями», Journal of Computer and System Sciences 4 (2): 177–192.

оборота Садек Дусти
источник
27

Рассел Импальяццо « Персональный взгляд на сложность среднего случая» . Это отличная статья, потому что она умно написана и суммирует положение дел в пяти «мирах», где наши предположения о сложности решаются различными способами, давая реальные последствия в каждом случае.

Стив Фламмия
источник
26

Усовершенствованные алгоритмы аппроксимации для задач максимального разреза и выполнимости с использованием полуопределенного программирования Геманса и Уильямсона.

Прекрасный пример внедрения новой методики для получения результатов, которые намного лучше, чем известные ранее.

Джанлука Делла Ведова
источник
24

Экстракторы и псевдослучайные генераторы Лука Тревизан. В этой статье хороший экстрактор случайностей построен с помощью кодов с коррекцией ошибок и комбинаторных конструкций. Конструкцию довольно легко понять, но она совершенно ошеломительна, потому что совершенно не очевидно, какова связь между экстракторами, кодами и конструкциями.

В конце концов, это хороший пример результата в TCS, который требует некоторой причудливой комбинаторики.

ilyaraz
источник
24

Как написать доказательство , Лесли Лэмпорт.

Энтони Лабарре
источник
5
Я прочитал это и прочитал «Плач Математика» Локхарта ( maa.org/devlin/LockhartsLament.pdf ). ИМХО, я полагаю, что стратегия, предложенная Лампортом, идет вразрез с тем, что Локхарт утверждает в отношении красоты математики.
Маркос Вильягра
5
Очень интересно читать. Я понимаю ваше мнение, но если я не ошибаюсь, Лампорт направляет свое послание на людей, которые более "математически образованы", чем те, на кого ориентируется Локхарт, который стремится помочь ученикам развить вкус к математике. Я также признаю, что следование строгому формату делает доказательства довольно скучными для чтения, но я согласен с Лампортом в идее доказательств по уровням: вы не всегда хотите / должны / иметь время, чтобы прочитать все подробно, и даже когда вы сделать, что краткое изложение того, что должно прийти, может быть весьма полезным. Гораздо больше, чем те, которые «легко увидеть / ясно / wlog / ...» ;-)
Энтони Лабарр,
19

Если я могу процитировать Сару Пэйлин по этому вопросу: «Все они».

Более серьезно, я думаю, что большинство статей не следует читать в оригинале. Со временем люди находят лучший способ понимания и представления оригинальной проблемы / решения. За исключением оригинальной статьи Тьюринга, которая имеет историческое значение, я бы не рекомендовал читать большинство оригинальных работ, если есть последующие работы, которые очистили ее. В частности, многие вещи представлены в книгах гораздо лучше, чем в оригинале.

Сариэль Хар-Пелед
источник
16
Этот комментарий в целом верен, но Райан явно просит примеры, для которых это не так. Существует много классических работ, в которых содержатся предположения, которые еще не доказаны, методы, которые были упущены из виду, или результаты, о которых обычно забывают, но которые можно стереть с лица земли и использовать для новых целей.
Андрас Саламон
12
Я не согласен. Это правда, что оригинальные статьи иногда недоступны для чтения, а второстепенные работы дают лучшее изложение результатов, но иногда оригинальные статьи содержат идеи, которые опущены в более поздних работах. Кроме того, чтение оригинальных статей может научить нас, как автор придумал эту идею. Взгляните на этот пост Тимоти Чоу на МО: mathoverflow.net/questions/28268/do-you-read-the-masters
Каве
4
Здорово, когда это происходит. Я просто утверждаю, что это несколько редко.
Сариэль Хар-Пелед
6
Вы говорите «Все из них», но разве вы не спорите за «Никого из них»?
Питер Тейлор
2
@ Питер Тейлор, я думаю, именно поэтому упоминается Сара. :)
Раду GRIGore
18
  • Н. Хомский. Три модели для описания языка. IEEE Труды по теории информации 3. 1956 г. doi: 10.1109 / TIT.1956.1056813

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

András Salamon
источник
3
Кстати, я не защищаю этот документ - просто отредактировал, чтобы исправить опечатки и добавить ссылку. Я предпочитаю статью Голда, если хочешь классическую статью о языке.
Андрас Саламон