Какие книги должен прочитать каждый?

[ Хронология ]

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

Книги могут быть ориентированы на математику, но вы можете найти это замечательно для компьютерного ученого. Примеры:

• Вероятность
• Неравенства
• логика
• Теория графов
• Комбинаторика
• Разработка и анализ алгоритма
• Теория вычислений / Теория сложности вычислений

Пожалуйста, посвятите каждый ответ книгам по одному предмету (например, по комбинаторике).

Примечание . Название может вводить в заблуждение. Вот пояснение: пусть X и Y - две области в информатике. Есть книги, которые все

• в поле X следует прочитать.
• в поле Y следует прочитать.
• в обоих полях следует читать.

Этот вопрос ищет все 3 случая. Другими словами, это НЕ специфично для последнего случая.

Изменить: В соответствии с предложением Дай Ле , пожалуйста, выделите причину (ы), что вам также нравится книга.

Похожие темы:

• Ссылки на методы доказательства TCS
• Книги по теории автоматов для самостоятельной работы
• Книги для вероятности
• Любимая популярная математическая книга
• Руководство для начинающих по дерандомизации
• Ссылки на нижние границы схемы
• Обзорная статья по теории рекурсивных функций
• Книги по семантике языка программирования
• Каковы последние книги TCS, проекты которых доступны онлайн
• Книги по вероятности

Вычислительная сложность:

Если вы ищете последние учебники сложности. Следующие два должны иметь.

• Вычислительная сложность: современный подход Санджива Арора и Боаза Барака ( домашняя страница учебника )

• Вычислительная сложность: концептуальная перспектива Одеда Голдрайха ( домашняя страница учебника )

Большая часть содержания этих двух книг сопоставима. Однако существуют некоторые ключевые различия: Гольдрайх уделяет больше внимания изучению концептуальных и философских основ теории сложности, тогда как Арора / Барак охватывает более широкий выбор тем, включая конкретные модели сложности, квантовые вычисления и нижние границы схем, которые в основном отсутствуют. от первого.

Другой вариант, более старый, но вневременной по сложности учебник:

• Вычислительная сложность Кристоса Пападимитриу

Книга Пападимитриу примечательна тем, что главы, охватывающие логику первого порядка, а также классы SNP, MaxSNP и APX (теоретические основы твердости аппроксимации), отсутствуют в более современных текстах.$_0$

Еще одна (сравнительно) старая, но довольно заметная классика:

• Введение в теорию вычислений Майкл Сипсер

Это один из немногих / первых учебников, который явно включает «Доказательство идеи:» между «Теорема:» и «Доказательство:», и является одним из самых хорошо написанных математических учебников по любой теме. С другой стороны, это только введение в сложность, посвящение только одной 50-страничной главы «продвинутым темам» (включая аппроксимацию, вероятностные алгоритмы, IP = PSPACE и криптографию). Как первая книга о сложности или как пример действительно превосходного письма, эта книга великолепна .

• Природа вычислений Кристофера Мура и Стефана Мертенса

Скотт Ааронсон пишет, что эта книга «забавна популярной книги с интеллектуальным весом учебника». Он рассказывает истории и дает множество занимательных примеров и ссылок (Игра Жизни и множество других примеров для машин, завершенных по Тьюрингу). Это не слишком глубоко в теории сложности, но имеет большую широту. Особенно следует отметить его связь со статистической физикой.

NP-полнота:

Ну, я думаю, « Компьютеры и труднопреодолимость Гэри и Джонсона : руководство по теории NP-полноты» можно найти среди лучших книг в этом списке.

Разработка и анализ алгоритмов:

Кормен, Томас Х., Чарльз Лейзерсон, Рональд Л. Ривест и Клиффорд Стейн. Введение в алгоритмы.

Р. Мотвани, П. Рагхаван. Рандомизированные алгоритмы.

Я нашел эту книгу , предложенную Ryan Williams на MathOverflow: Алгоритм проектирование по Клейнбергу и Тардосу .

Еще одна замечательная книга - « Введение в алгоритмы: творческий подход » Уди Манбера . Эта книга не каталог алгоритмов; скорее он пытается дать читателю интуицию для «распознавания математической структуры в абстрактных задачах». (цитата из обзора)

Общая математика для информатики:

• Конкретная математика: основа компьютерных наук Грэма, Кнута и Паташника.

• Принстонский компаньон по математике Gowers et al.

• Доказательства из КНИГИ Aigner и Ziegler.

Системы типов и семантика языка программирования:

Типы и языки программирования Бенджамина Пирса и последующий том Расширенные темы по типам и языкам программирования . Они предоставляют четкий, но понятный обзор роли теории типов в проектировании языка программирования, а также используют операционную семантику для выражения семантики языка программирования.

Неравенства:

Еще одна ценная книга для любого человека в области компьютерных наук, который когда-либо хочет связать любое количество (а значит, всех!), - «Мастер-класс Коши-Шварца: Введение в искусство математического неравенства » Майкла Стила.

Энциклопедическая книга на эту тему - «Словарь неравенств» . Хотя это не книга для чтения от корки до корки, хорошо иметь ее в своем распоряжении. Смотрите также приложение к книге.

Более того, в Википедии есть отличный список неравенств .

По конкретным темам вы можете проконсультироваться:

• Вероятностные неравенства
• Матричные неравенства
• Геометрические Неравенства
• Книга "A = B" Петковсека, Вильфа и Цайльбергера.

Интересно. Никто не упомянул тома «Искусство компьютерного программирования » Дональда Кнута . Очень подробная обработка тем с очень хорошими упражнениями.

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

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

Теория конечных моделей

Мы хотим изучить методы, которые имеют дело с конечными структурами. Хорошо известно, что многие традиционные инструменты из теории моделей, например, компактность и теорема Левенгейма-Сколема, не применимы к конечным моделям. Это приводит нас к изучению теории конечных моделей . Для этой области я рекомендую следующие отличные книги:

• Леонид Либкин, Элементы теории конечных моделей . (учебник)
• Гредель и др. Теория конечных моделей и ее приложения . (обзорные статьи и приложения)

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

• Нил Иммерман, Описательная сложность .

Доказательство сложности

Еще одной важной областью логики в информатике является Доказательство Сложности , изучение трехсторонних отношений между классами сложности, слабыми логическими системами и пропозициональной системой доказательств. Рассматриваются следующие два взаимосвязанных аспекта: (i) сложность доказательств формул высказываний и (ii) изучение слабых теорий арифметики, называемых ограниченной арифметикой .

Аспект (i) имеет отношение к следующему вопросу: «Существует ли система пропозиционального доказательства, в которой каждая тавтология имеет доказательство размера полинома в размере тавтологии?»

$C$$VC$$VC$$C$

$\mathsf{PV}$$\mathsf{PV}$

Для отличных исследований по сложности доказательств я рекомендую следующие две книги:

• Стивен Кук и Фуонг Нгуен. Логические основы сложности доказательств . (проект доступен здесь )
• Ян Крайчек, Ограниченная арифметика, пропозициональная логика и теория сложности .

$\mathsf{P}$$V_0$

Книга Крайчека немного сложнее, поскольку он предположил, что читатели уже знакомы с математической логикой и теорией моделей (или достаточно готовы изучить фон, необходимый на этом пути). Но вы многому научитесь, прочитав и поняв эту книгу.

Рандомизированные алгоритмы:

Вероятность и вычисления: рандомизированные алгоритмы и вероятностный анализ Майкла Митценмахера и Эли Упфала.

Отличная книга для объяснения основ рандомизированных алгоритмов. Примеры и доказательства объясняются очень четко, и им легко следовать. Кроме того, упражнения очень весело делать.

(ответил Маркос Вильягра)

Анализ рандомизированных алгоритмов:

Любой, кто работает с алгоритмами, должен иметь концентрацию измерения для анализа рандомизированных алгоритмов , которую также можно скачать в формате PDF здесь .

Криптография:

Двухтомная книга « Основы криптографии » Одеда Голдрайха ( Том 1: Основные инструменты и Том 2: Основные приложения ) является отличной книгой по этому вопросу. (Ранние версии доступны на домашней странице автора .) Также доступна сокращенная версия этой книги.

Еще одна замечательная книга - « Введение в современную криптографию: принципы и протоколы» от Katz & Lindell.

Для тех, кто интересуется математическими основами криптографии , Hoffstein et al. , Введение в математическую криптографию . это естественный выбор.

Другие отличные книги:

• Справочник по прикладной криптографии Menezes et al. (Главы доступны онлайн ).
• Криптография: теория и практика Стинсона.

Конкретные темы:

• Книги, относящиеся к расширенной композиции протоколов безопасности:
  • Составление безопасных многопартийных протоколов: всестороннее исследование Линделла.
  • Параллельное нулевое знание Розена.
• Формальные доказательства в протоколах безопасности
  • Формальная корректность протоколов безопасности Беллы.
• [Математика криптографии с открытым ключом] ( http://www.amazon.com/Matmatics-Public-Cryptography-Steven-Galbraith/dp/1107013925 ) Гэлбрейта

Функциональное программирование

• Чисто функциональные структуры данных по Крис Окасаки . Большинство книг по структурам данных предполагают обязательный язык, такой как C или C ++. Однако структуры данных для этих языков не всегда хорошо переводятся в функциональные языки. Эта книга является одной из лучших экспозиций по реализации структур данных и алгоритмов на функциональном языке.
• Функциональное программирование: практика и теория по Bruce J. MacLennan . Несмотря на название, эта книга больше ориентирована на теорию, чем на практику. Те, кто читает эту книгу, будут иметь намного лучшее представление о предмете, чем те, кто изучает ее с помощью специального программирования.
• Жемчужины функционального алгоритма проектирования по Ричард Берд . Совершенно новая экспозиция на тему, которая использует подход решения проблем и показывает красоту области, демонстрируя привлекательные идеи в разработке функциональных алгоритмов.
• Сертифицированное программирование с зависимыми типами от Адама Члипала . Это один из лучших ресурсов в изучении Coq, и он сосредоточен, в частности, на том, как автоматизировать сертификацию программ и доказательство теорем с использованием систем на основе логики / правил. Примеры обширны и просты для понимания.

Аппроксимационные алгоритмы

Книга « Алгоритмы аппроксимации » Вазирани - лучшая книга на эту тему. Другая книга - Алгоритмы аппроксимации для NP-трудных задач Хохбаума.

Вот сравнения двух рецензентов:

В качестве руководства для моей работы я использовал книгу Дорита Хохбаума об алгоритмах аппроксимации для задач NP-Hard. Книга Хохбаума, без сомнения, потрясающая. Тем не менее, формат опроса скомпрометировал плавный ход в пользу объединения лучших людей в этой области. Книга Вазирани исправляет это, будучи настолько гладкой и элегантной от начала до конца. Отличные наборы задач, отличные советы по большинству задач, и в конце книги есть раздел, посвященный открытым проблемам, который является действительно интересной функцией.

а также

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

Недавняя книга - Разработка алгоритмов аппроксимации Уильямсоном и Шмойсом.

Комбинаторика

Вводные книги. Любая из следующих книг может служить отличным введением в предмет:

• Справочник по дискретной и комбинаторной математике Розена.
• Дискретная и комбинаторная математика: прикладное введение Гримальди. Смотрите также руководство по решению .
• Пройдя через комбинаторику и введение в перечислительную комбинаторику и введение в перечислительную комбинаторику по Bona. Первая книга более всеобъемлющая, чем классическая. Вторая книга в значительной степени совпадает с первой, но гораздо больше внимания уделяется современным методам подсчета.
• Курс по комбинаторике от Ван Линта и Уилсона.
• Комбинаторика: темы, методики, алгоритмы Кэмерона. (В этой книге много хороших упражнений.)
• Комбинаторные задачи и упражнения Ласло Ловаша (отвечает @Sazzad)

Более продвинутые тексты.

• Перечислительная комбинаторика, том 1 и том 2 Стэнли. Это просто шедевр по перечислительной комбинаторике; очень сложный, очень глубокий
• Комбинаторные алгоритмы: генерация, подсчет и поиск по Kreher & Stinson. Больше подходит для информатики приложений комбинаторики.
• Аддитивная комбинаторика Теренса Тао и Ван Х. Ву. Очень полезная ссылка, когда сталкиваешься с комбинаторной проблемой, связанной с теорией чисел.

Комбинаторика

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

Проверка программы

• Математическая теория вычислений Зоара Манны
• Принципы проверки моделей Кристелом Байером и Йост-Питером Катоеном
• Проверка моделей Эдмундом М. Кларком-младшим, Орной Грумберг и Дорон А. Пелед
• Проверка последовательных и параллельных программ Кшиштоф Р. Апт, Франк С. де Бур и Эрнст-Рюдигер Олдерог
• Логика в информатике: моделирование и рассуждение о системах М. Хута и М. Райана

Теория информации

Теория информации, логический вывод и алгоритмы обучения Дэвид Маккей

Другие известные учебники по теории информации можно найти в Википедии .

Распределенные алгоритмы

Распределенные алгоритмы Нэнси Линч Это классический текст, написанный пионером распределенных вычислений;

Введение в Распределенные Алгоритмы от Джерарда Тела Очень хорошее введение, также подходящее для курсов уровня бакалавриата; сосредоточены на модели передачи сообщений

Распределенные вычисления: основы, симуляции и продвинутые темы Хагит Аттия и Дженнифер Уэлч. Содержит передовые материалы, подходящие для курсов уровня PhD; Обсуждаются как модели передачи сообщений, так и модели с общей памятью.

Разработка и анализ распределенных алгоритмов. Николя Санторо. Относительно недавняя книга, может быть использована как на уровне бакалавриата, так и на уровне PhD; материалы представлены с акцентом на дизайн протокола

Квантовые вычисления

• Квантовые вычисления и квантовая информация от Nielsen и Чжуан , является большой справочник книга, идеально подходит для тех , кто хочет исследовать в этой области. Однако, для начала, трудно учиться, и это определенно не для самообучающихся. Поскольку в книге отсутствуют рабочие примеры, я предлагаю следующую книгу:

  • Проблемы и решения в области квантовых вычислений и квантовой информации от Steeb & Hardy . Эта книга включает в себя множество примеров, но это еще не для абсолютного новичка. Для начала предлагается следующая книга:

    • Подход к квантовым вычислениям по Маринеску и Маринеску . В то время как элементарный и простой в освоении, некоторые люди находят его «заполненным ошибками». В связи с этим опечатки книги пригодятся.

• Квантовые вычисления с Демокрита . Скотт Ааронсон . Сила путешествий гораздо большего, чем квантовые вычисления, с отношениями к физике, философии и т. Д.

Две другие превосходные вводные книги по этому вопросу:

• Квантовые вычисления для компьютерных ученых по Yanofsky и Mannucci .
• Введение в квантовых вычислений по Kaye, Лафламм и Моска .

оптимизация

Мне понравился фильм Пола Нахина « Когда меньше всего».

По сути, милая история оптимизации с помощью проблем и личностей. На страницах 32-36 в одной из колонок Билла Гасарха есть хороший обзор .

$e^{i\pi} = -1$

Сложность общения:

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

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

Сложность связи и параллельные вычисления Юрай Хромкович.

Очень полный, хотя иногда немного трудно читать. Интуитивные объяснения очень понятны, и очень приятные упражнения. Во второй части представлены связи с параллельными вычислениями.

• Книги Matousek & Chazelle о несоответствии превосходны.

  На самом деле, почти все книги Матусека , в некоторой степени, заслуживают прочтения.

• Книги Дугласа Уэста по теории графов ( [1] и [2] ) хороши.

• Алон и Спенсер тоже отлично.
• Pach & Agarwal хорош для дискретной геометрии, также как и Sharir & Agarwal, если вы находитесь в последовательностях DS.
• Книга Брасса, Мозера и Паха об открытых задачах в дискретной геометрии также очень хороша.
• Книга Вандербея на LP очень хороша.
• Книги Шрайвера ( [1] и [2] ) удивительны.

Вычислительная алгебра

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

• Современная компьютерная алгебра Йоахима фон Цюра Гатена и Юргена Герхарда.
• Теория алгебраической сложности Петера Бюргиссера, Михаэля Клаузена, Мохаммеда А. Шокроллахи и Т. Ликтейга.
• Алгоритмическая алгебра Бхубанешвара Мишры.
• Компьютерное введение в теорию чисел и алгебру. Автор Виктор Шуп.

Вычислительный анализ

Также интересная область, которая имеет дело с вычислениями в реальных функциях. Также известен как «вычислимый анализ» или «вычислимое исчисление».

• Вычислительный анализ Оливер Аберт.
• Вычислимый анализ: Введение Клауса Вейрауха.

Комбинаторика

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

Перечислительная комбинаторика Ричарда Стэнли - отличный справочник (продвинутый).

Комбинаторика: темы, методы, алгоритмы Питера Кэмерона и « Приглашение к дискретной математике » Матушека и Несетрила - прекрасное введение в комбинаторику.

Прикладная комбинаторика Робертса и Тесмана является энциклопедическим справочником по прикладной комбинаторике.

Логика:

Это дословно мой ответ на этот вопрос .

Знание основ математической логики, на мой взгляд, плюс. Вы можете взглянуть на две книги Кори и Ласкара.

Математическая логика: курс с упражнениями, часть I

Математическая логика: курс с упражнениями, часть II

Логическое / пробное письмо:

1. Как доказать это: структурированный подход Даниэля Дж. Веллемана

Теория чисел

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

• Введение в теорию чисел Hardy et al. Харди - известный британский математик. Он был наставником индийского математика Рамануджана . Его вклад в область теории чисел удивителен .
• Введение в теорию чисел Нивен, Цукерман, Монтгомери. Еще одно классическое введение в области.
• Решенные и нерешенные проблемы теории чисел Шенкса. Это книга для тех , кто ищет еще, чтобы быть испытанными домыслы в этой области.
• Дзета-функция Римана Эдвардса. Важная часть современной теории чисел, а также несколько вероятностных алгоритмов для теоретико-числовых задач основаны на (расширенной) гипотезе Римана, как описано в этой книге.

Гиперграфы

Не так много книг, посвященных исключительно гиперграфам. Одна такая книга

Берге С. Гиперграфы: комбинаторика конечных множеств .

Теория доказательств

Книга Троэльстры и Швичтенберга « Базовая теория доказательств» теперь является фактическим текстом по этой теме.

Girard, Taylor & LaFont's Proofs and Types - более короткая книга на эту тему, и ее версию можно скачать по адресу http://www.paultaylor.eu/stable/Proofs%2BTypes.html.

Теория графов

Для введения в теорию графов: Введение в теорию графов от West

Подробнее о теории графов: теория графов Бонди и Мёрти

Всесторонняя книга, которая содержит новые разработки, а также старые классические результаты в теории графов:

Теория графов: Рейнхард Дистел .

Для графиков на поверхностях с комбинаторным подходом:

Графики на поверхностях

И для орграфов:

Диграфы: теория, алгоритмы и приложения

СБИС Дизайн

Я не в железе. Однако, поскольку FAQ включает в себя VLSI в качестве одного из подразделов TCS, я спросил эксперта об известных книгах по дизайну VLSI. Они здесь:

• Цифровые интегральные схемы
• Проектирование CMOS VLSI: перспектива схем и систем
• Современный дизайн СБИС: IP-дизайн