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

229

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


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

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

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

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

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

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

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

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


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

MS Dousti
источник
Поскольку я не могу ответить на вопрос, я сделаю это здесь. Дискретная математика - TTC: Дискретная математика Артура Т. Бенджамина. Это набор лекций на различные темы от теории множеств до графиков и вероятности.
Питикос
Может быть интересно сравнить этот список замечательных книг со списком вводных книг из ... Есть ли список канонических вводных учебников, охватывающих основные отрасли информатики? вопрос по reddit / compsci. Есть некоторые совпадения, но, к счастью, различия достаточно значительны.
Томас Климпел

Ответы:

91

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

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

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

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

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

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

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

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

Мохаммед Аль-Туркистани
источник
2
Помимо тех, кто интересуется тем, как эти книги сравниваются друг с другом, я также могу предложить рецензию на книгу Арора / Барак и Голдрайх, которую я недавно написал для рецензии на книгу SIGACT.
Даниэль Апон
1
см. также список своих любимых книг о вычислительной сложности на Amazon на Ланс Фортноу: amzn.com/l/22R1UX0Y9YRT2
Алессандро
5
Единственный комментарий к книге Сипсера заключается в том, что он иногда использует нестандартные имена при освещении теории вычислимости. Например, он использует «узнаваемый» вместо «полуразрешимый». Но я полагаю, что поскольку учебник широко используется, он может стать стандартом уже сейчас.
Дай Ле
4
На самом деле, это отличный комментарий, @Dai Le. Я могу думать о похожих различиях между Гольдрайхом и Аророй / Бараком. Например, Голдрайх использует имя а Арора / Барак использует имя , хотя они оба говорят об одной и той же концепции. F N PPCFNP
Даниэль Апон
1
Я обнаружил, что Сипсер гораздо полезнее Пападимитриу для преподавания теории сложности, мммм.
Джефф Берджес
49

NP-полнота:

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

Sadeq Dousti
источник
6
Все еще лучшее введение в теорию сложности после 30 лет.
Эмиль
1
после десятилетий эта книга по-прежнему является наиболее полным списком проблем с NP в одном месте, по-видимому, почти энциклопедией, и многие исследователи CS, похоже, разделяют эту точку зрения
vzn
1
рекомендуем добавить это в FAQ для общего вопроса, "моя проблема X NP завершена?" с ответом «1-й чек эту книгу 1-й, а затем
вернись
47

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

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

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

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

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

Никита Жильцов
источник
7
«Введение в анализ алгоритмов» Седжвика и Флажолета великолепно.
Джей
Даниэль Спилман использует книгу Кляйнберга и Тардоса в своем курсе «Разработка и анализ алгоритмов». Я взял это, и действительно любил книгу. Я нашел это гораздо более доступным, чем CLRS.
Алекс Рейкинг
41

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

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

Дейв Кларк
источник
7
Для более математического взгляда на теорию типов, «Лекции по изоморфизму Карри-Говарда» Соренсена и Уржичина - отличное начало, дающее хороший обзор типизированных лямбда-исчислений вплоть до исчисления конструкций и далее.
Доминик Маллиган
4
Я бы предложил «Основы языков программирования» Джона Митчелла на эту тему. Как и в предыдущем комментарии, это более математически зрелый.
Артем Пеленицын
2
Upvote для TAPL. К вашему сведению Бенджамин Пирс является одним из авторов новой книги «Software Foundation», в которой используется Coq.
Кунджан Кшетри
40

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

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

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

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

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

Sadeq Dousti
источник
1
Если я могу добавить ссылку на что-то, что я сам собрал (из множества разных источников, включая некоторые из вышеперечисленных), вот шпаргалка распространенных неравенств: lkozma.net/inequalities_cheat_sheet
László Kozma
1
Харди, Литтлвуд, Поля, «Неравенство», драгоценный камень 1930-х годов (?)
Кодлу
38

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

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

Fakrudeen
источник
4
TAOCP по-прежнему актуален и Vol. 4A только что был выпущен.
dbasnett
33

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

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

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

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

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

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

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

CVCVCC

PVPV

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

PV0

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

Dai Le
источник
32

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

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

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

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

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

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

Сянь-Чи Чан 張顯 之
источник
3
Эта книга была предложена в другой теме (я думаю, Суреш). Я нашел это отлично. Спасибо Аарону за упоминание этого здесь.
MS Dousti
29

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

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

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

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

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


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

Sadeq Dousti
источник
2
С момента их появления в 1993 году случайные оракулы широко использовались в литературе; особенно в схемах подписи. Я не знаю книгу, которая освещает эту область соответствующим образом. Предложения приветствуются.
MS Dousti
1
Книга о случайных оракулов будет огромная помощь. Я не работаю в крипто, но я читал Кац / Линделл спереди назад. По этой конкретной причине переход от учебника к крипто литературе был грубым. Кроме того, @Sadeq, из любопытства: какая-нибудь из прочитанных книг хорошо освещает перемотку?
Даниэль Апон
1
@Daniel: тезис Мартина Гагне «Исследование модели случайного Оракула» (UC Davis, 2008) - относительно хороший справочник по случайным оракулам (хотя он еще далек от завершения). Относительно вопроса «перемотки»: я не знаю книги об этом, но думаю, что полностью это понял. Не могли бы вы уточнить, какая часть кажется вам проблематичной? Вы даже можете спросить об этом по отдельной теме.
MS Dousti
@ Садек, я склонен не начинать независимый вопрос об этом, потому что это будет чуть больше, чем «Помогите, что перематывает?» :) Проблематичным является то, что перемотки не было в учебнике, который использовался в курсе крипто, который я взял (например, Кац / Линделл), поэтому я никогда не видел введение в концепцию. Я знаю, что это регулярно появляется в крипто-литературе, но, как кто-то, кто не принимает активного участия в крипто-исследованиях, я сомневаюсь, что прочитаю достаточно статей, чтобы получить твердое понимание перемотки, просто встретившись с ней достаточно. Может быть, я мог бы задать вопрос о происхождении перемотки ...
Даниэль Апон
3
@Daniel: введение в мою книгу о параллельном нулевом знании объясняет перемотку и трудности, связанные с ней в контексте составления протокола. Другие источники: (1) Одед Голдрайх, Уго Кравчик: О составе систем доказательства с нулевым знанием. SIAM J. Comput. 25 (1): 169-192 (1996) и (2) Синтия Дворк, Мони Наор, Амит Сахай: Одновременное нулевое знание. J. ACM 51 (6): 851-898 (2004).
Алон Розен
25

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

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

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

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

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

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

а также

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

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

Sadeq Dousti
источник
21

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

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

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

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

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

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

Lamine
источник
20

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

Чан Ли
источник
1
Некоторые из книг («Манна и Апт и др.») Довольно датированы («Манна» с 1977 г. и «Апт и др.» С 1991 г.), в области верификации программ на основе логики произошел значительный прогресс за последнее десятилетие. Увы, актуального текста пока нет.
Мартин Бергер
@MartinBerger Есть какие-нибудь намеки на то, где можно узнать об этом важном прогрессе, если его нет в каких-либо недавних учебниках?
Митч
@ Боюсь, это еще не написано в учебниках. Может быть, посмотрите на некоторую литературу об интерактивных инструментах, таких как Isabelle / HOL и Coq. Также посмотрите на недавние инструменты автоматической проверки, такие как «вывод» Facebook и теорию, лежащую в основе этого.
Мартин Бергер
Хут и Райан очень дружелюбны для начинающих. Для кого-то, кто не очень знаком со всей строгой математикой в ​​CS, это хорошее начало. Это первая книга, которую я прочитал о формальной стороне CS, и с тех пор меня зацепили! Это также первый учебник, в котором я закончил все чтения.
RexYuan
19

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

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

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

Sadeq Dousti
источник
Название «Какие книги должен прочитать каждый?», Поэтому рекомендация должна быть выборочной. Любой может найти большой список книг по «теории информации» в Amazon / library, но если у вас есть только 2-3 варианта, что они будут? Вы должны только рекомендовать книги или статьи, которые вы прочитали, очень внимательно и сузить до ваших абсолютных фаворитов!
Дай Ле
1
@Dai Le: Вы правы. Я думаю, что список должен быть сужен. (Я лично несу ответственность за раздувание списка!) Тем не менее, это сообщение вики сообщества . Я добавил длинный список, предлагающий кандидатов. Пожалуйста, обрежьте список, чтобы включить только самые подходящие книги.
MS Dousti
1
@ Садек: Боюсь, редко бывает, что один человек урезает список другого. Пока сообщение все еще находится в текущей форме, оно совершенно бесполезно в отношении цели сообщения.
Дай Ле
@Dai: Вы правы. Но, так как я не специалист по «теории информации», я не могу урезать список самостоятельно. Я могу: 1) удалить список, который я вообще добавил (оставив исходный список), или 2) добавить уведомление в текст, чтобы привлечь внимание эксперта. Что ты предлагаешь?
MS Dousti
@ Садек: Я тоже не работаю над теорией информации, иначе я бы помог урезать список. Я знаю, что книга "Томас М. Ковер, Джой А. Томас. Элементы теории информации" рекомендуется многими, в том числе Лэнсом Фортнау. Но я не уверен, должны ли все это читать или нет. Я думаю, что мы должны уважать оригинальный постер, так как книга может быть его самой любимой. Таким образом, удаление всего списка является хорошим вариантом. Я действительно извиняюсь за то, что был слишком прямым. Также не могли бы вы попросить людей объяснить, почему они предлагают свои книги?
Дай Ле
19

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

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

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

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

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

Massimo Cafaro
источник
19

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

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

Sadeq Dousti
источник
17

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


Сложность общения Эяля Кушилевица и Ноама Нисана.

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

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


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

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

Marcos Villagra
источник
16
  • Книги Matousek & Chazelle о несоответствии превосходны.

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

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

  • Алон и Спенсер тоже отлично.
  • Pach & Agarwal хорош для дискретной геометрии, также как и Sharir & Agarwal, если вы находитесь в последовательностях DS.
  • Книга Брасса, Мозера и Паха об открытых задачах в дискретной геометрии также очень хороша.
  • Книга Вандербея на LP очень хороша.
  • Книги Шрайвера ( [1] и [2] ) удивительны.
Hsien-Chih Chang 張顯 之
источник
Еще один, отличный для булева анализа Фурье (как следует из названия) и охватывающий как основы, более сложные темы и (многие) приложения, это « Анализ булевых функций » Райана О'Доннелла (2014). Он также доступен онлайн бесплатно здесь .
Климент С.
16

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

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

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

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

Сянь-Чжи Чан 張顯 之
источник
16

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

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

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

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

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

Jay
источник
14

Логика:

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

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

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

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

Sylvain Peyronnet
источник
Как насчет математического введения в логику Герберта Эндертона?
RexYuan
14

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

  1. Как доказать это: структурированный подход Даниэля Дж. Веллемана
Sazzad Bin Kamal
источник
3
Как это соотносится с «Как решить» Г. Поля? Я думаю, что прочитал совет, что Поля - оригинал и намного лучше, но я не уверен и не могу перефразировать это на интервалах;)
DaveBall aka user750378
2
В книге Поли «Как ее решить» (HTSI) речь идет не о предмете книги Веллемана. Поля - это своего рода размышление о том, как найти решение сложных проблем, тогда как Веллеман - это учебник о том, как формализовать решения, используя соглашения и язык математики. HTSI действительно имеет информацию о доказательствах, но она представлена ​​в виде «глоссария» без какой-либо структуры, тогда как Velleman представляет вам систематический учебный план с упражнениями. И то, и другое стоит прочитать, но одно не заменяет другое.
Nate CK
13

Теория чисел

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

оборота Садек Дусти
источник
Что вы думаете о книге Розена или переиздании Дувра?
Марк С
@Mark: они тоже хороши. Почему бы не редактировать пост, а также добавить эти книги?
MS Dousti
11

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

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

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

Роб
источник
11

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

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

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

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

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

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

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

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

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

dpufrj
источник
1
Существует также Теория графов Клода Берге, одного из основателей теории графов. И графики и алгоритмы Мишеля Мину и Мишеля Гондрана.
Ламин
9

СБИС Дизайн

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

М.С. Dousti
источник
В этой области я бы порекомендовал эту чрезвычайно читаемую книгу: «Синтез и оптимизация цифровых схем» Джованни де Микели
Чан Ли,