Список вводных книг по TCS для тех, кто мало знает о TCS [закрыто]
10
Если вам нужно рекомендовать книги для тех, кто хочет больше узнать о TCS на начальном уровне, таких как теория автоматов, алгоритмика, теория сложности и т. Д., Какие книги вы бы порекомендовали для тех, кто заинтересован и хочет узнать больше о TCS, но не было никакого воздействия на это?
@Gigili Нет. Списки книг раньше были CW, но это больше не сделано. Пожалуйста, прочитайте сообщение в блоге, на которое я ссылался.
Жиль "ТАК - перестань быть злым"
Ответы:
9
Если вы хотите получить общее представление, не углубляясь в технические детали, я предлагаю « Алгоритмику Дэвида Харела : дух вычислений» . После этого это мой любимый список:
Алгоритмы S. Dasgupta, CH Papadimitriou и UV Vazirani: наиболее интуитивное введение в алгоритмы с большим вниманием к интуиции, чем технические доказательства.
Jon Bentley's Programming Pearls : это не учебник по алгоритмам, но он прекрасно демонстрирует, как использовать методы проектирования алгоритмов для решения реальных проблем, которые раздражали настоящих программистов. :-) Это может быть хорошим началом, если у вас есть предварительные знания по программированию.
Из-за оценки этого ответа я включил ответы в совокупный ответ . Пожалуйста, рассмотрите возможность удаления вашего ответа для ясности.
Рафаэль
@Raphael DPV был в печати в течение нескольких лет, но он все еще приятно доступен в Интернете. Я старался не ссылаться на коммерческий сайт, как Amazon.
Дай
@Dai: Понятно. На странице, на которую вы ссылаетесь, написано: «Это предпоследний проект нашего учебника, который скоро появится», поэтому я в замешательстве.
Рафаэль
7
Введение в алгоритмы от Cormen, Leiserson, Rivest, Stein - популярный выбор, название говорит само за себя.
Я нахожу книгу Кларка слишком тяжелой для кого-то без опыта TCS. Я знаю (лично) аспирантов, которые находят книгу трудной для понимания.
Дай
@Dai, вы, вероятно, правы, я изменил его на Принципы проверки моделей Байера
Даниил
Можно ли понять проверку модели без основ логики и / или автоматов?
Рафаэль
1
Книга Дракона, безусловно, является хорошей ссылкой; хотя это достаточно теоретически? (Честно говоря, я не знаю)
Рафаэль
@ Рафаэль "Принципы" несколько дает введение в логику (по крайней мере, некоторые необходимые знания) и автоматы. Это тоже довольно большая книга, ~ 980 страниц. Что касается The Dragon Book, я думал, что компиляторы - это довольно теоретическая область, не так ли?
Даниил
6
Для математики, необходимой для анализа алгоритмов, я рекомендую один-единственный GKP:
Конкретная математика Грэма, Кнута, Паташника
Комплексная, высококачественная обработка практически всей математики, которая вам понадобится в (базовой) алгоритмике. Это занимательное чтение и включает в себя множество упражнений (и решений).
Я пытался читать эту книгу, но она мне не нравилась, потому что все это было очень ... неуклюжим и сгруппированным. Я просто не чувствовал красоту математики там. Сравните это с набросками Сипсера теории автоматов, книгами Смулляна по логике или даже с абстрактной алгеброй Даммита и Фута. Может быть, это только я, правда.
Даниил
Я второй Даниил. Это коллекция отличных инструментов для теоретиков. Но он слишком сухой и технический, чтобы быть приятным для начинающих. Мне действительно нравятся книги, о которых я упоминал выше, поскольку у них, кажется, есть свои души. Они читают так, как будто кто-то рассказывает вам интересные истории.
Дай
К сожалению, он не охватывает структурную индукцию, коиндукцию, теорию предметной области и все, что нужно для теории TCS в стиле B.
Дэйв Кларк
@DaveClarke: правильно. Я не уверен, что ожидал бы, что любая математическая книга будет содержать все это. Но тогда, GKP должен быть книгой по математике. Он также не содержит логики, поэтому я должен немного перефразировать.
Рафаэль
2
@DaveClarke, не могли бы вы порекомендовать нам несколько книг по теории B по математике?
Введение в теорию автоматов, языков и вычислений Дж. Э. Хопкрофт, Дж. Д. Уллман, (Р. Мотвани)
Первое издание 1979 г. имеет больше теоретических результатов, которые отсутствуют во втором издании 2001 г. Еще не посмотрел на третьего Эда.
Logicomix, безусловно, драгоценный камень, не говоря о том, что другие нет.
Дэйв Кларк
Мне не очень нравится, как Logicomix изображает логиков как «безумных» людей. Идеи в логике, если их правильно объяснить, очень приземлены и просты, и на самом деле не настолько «безумны».
Дай
1
@Dai Посмотрите на жизнь выдающихся людей, таких как, например, Гёдель, Витгенштейн, Нэш и т. Д., Они были ... ну очень необычными.
Uli
Какие из них действительно новички?
Рафаэль
@ Рафаэль ИМХО все они, иначе я бы не разместил их здесь. У некоторых может быть крутая кривая обучения, но я думаю, что все в порядке.
Uli
4
Если вы новичок в области TCS, « Введение в теорию вычислений» от Sipser - определенно лучшая книга для начала. Я читал другие вводные книги, и ни одна из них, по моему мнению, не приблизилась к способу Сипсера донести этот вопрос.
Другие, более конкретные, хорошие теоретические книги:
@DaveClarke Я планировал добавить больше ресурсов в список, как я сделал с моим редактированием сейчас, но я также хотел подчеркнуть, насколько велика книга Сипсера, упомянув ее снова! :-)
codd
1
Книга Пирса - драгоценный камень. Я хотел бы, чтобы это было где-то, когда я защитил докторскую диссертацию.
Дейв Кларк
@DaveClarke В настоящее время я использую его для своей дипломной работы по рекомендации моего консультанта, и я также очень впечатлен этим!
codd
1
Спасибо за ссылку, я посмотрю на это позже сегодня. Я вижу, что вы профессор KUL, я приеду туда в следующем году, чтобы изучать Secure Software (программное обеспечение Veilige). Какой маленький мир.
codd
3
Несколько хороших книг, охватывающих теорию B, часть TCS:
Логика в CS : Логика в области компьютерных наук: моделирование и рассуждение о системах Майкл Хут и Марк Райан.
Широкий охват различных областей применения логики в информатике. Около 3 курса бакалавриата.
Лямбда-исчисление : лямбда-исчисление и комбинаторы. Введение Дж. Роджера Хиндли и Джонатана П. Селдина.
Представляет лямбда-исчисление, которое является важным компонентом в основах языков программирования. Около 3 курса бакалавриата.
Ведущий в области предметной области : Введение в решетки и порядок (2-е изд.) . Авторы: Davey, BA and Priestley, HA Cambridge University Press. (2002).
Охватывает очень полезную тему, особенно если вы планируете работать с семантикой. Это немного более математично, чем другие темы, но первые главы, безусловно, находятся на продвинутом уровне бакалавриата.
Семантика : семантика с приложениями: закуска от Hanne Riis Nielson и Flemming Nielson.
Действительно хорошее введение в семантику языка программирования. Вместо того, чтобы углубляться в какой-либо конкретный формализм, он дает широкое представление и включает приложения, обычно не рассматриваемые в других книгах по семантике. Может быть полезно для студентов 2 курса.
Я не знаю ни одного из них даже по репутации, поэтому я не могу сказать, насколько они хороши (хотя я склонен поверить вам на слово). : /
Рафаэль
1
Я добавил описание каждой книги. Все хорошо.
Дейв Кларк
3
Это сводный ответ, который содержит книги из ответов с оценкой не менее пяти. Пожалуйста, обсудите его содержание в чате .
Алгоритмы и структуры данных
Введение в алгоритмы . Авторы Cormen, Leiserson, Rivest, Stein (3-е изд. 2009)
. Комплексное рассмотрение основных алгоритмов и структур данных, а также их анализ без углубленного изучения.
Алгоритмы от Dasgupta, Papadimitriou, Vazirani (2006)
Наиболее интуитивное введение в алгоритмы с большим вниманием к интуиции, чем технические доказательства.
Вычислительность и сложность
Введение в теорию вычислений от Sipser (2-е издание 2005 г.)
Лучшее введение в теорию автоматов, вычислимость и сложность.
Baier, Katoen (2008). Принципы проверки моделей.
Массивная книга, которую можно использовать как всеобъемлющее введение в проверку моделей.
«Программирование жемчуга » Джона Бентли (2-е изд. 1999 г.)
Не учебник по алгоритмам, но прекрасно демонстрирует, как использовать методы проектирования алгоритмов для решения реальных задач. Может быть хорошим началом, если у вас есть предварительные знания по программированию.
Это не отвечает на вопрос, или, если оно предназначено, это не хороший ответ. Вы имеете в виду, что кто-то, начинающий TCS, должен прочитать все эти книги? Если нет, то как бы они выбрали? Имейте в виду, что по вашему правилу этот ответ, скорее всего, будет содержать сотни книг
Жиль "ТАК - перестань быть злым"
@ Рафаэль Вы вежливы, когда просите кого-то другого удалить свой ответ? Обычно сам задающий может собирать свои любимые ответы, изменяя свой текст вопроса, но я никогда не видел, чтобы кто-то заставлял другого человека удалять свой пост, чтобы создать свой собственный ответ. Этот cs stackexchange становится странным с этим нарциссическим поведением.
Дай
@ Рафаэль: Делать это CW не дает права просить кого-то удалить свой собственный ответ. Это все равно, что сказать, что я собираюсь написать книгу / обзорную статью (которую я опубликую бесплатно), поэтому я обхожу вокруг и спрашиваю всех авторов, чьи статьи я цитирую, снять их собственные статьи, чтобы избежать путаницы.
Дай
@ Рафаэль Я не вижу нигде в лицензиях ЦК о том, что моя работа будет в конечном итоге запрошена кем-то другим. Я не знаю, какие у тебя фантазии с SE, но это определенно не Википедия. Я знаю, что вы усердно работаете над тем, чтобы «модерировать» этот сайт, но, пожалуйста, уважайте чужую свободу слова и конфиденциальность и просто позвольте голосам «за» и «против» позаботиться обо всем остальном. Я думаю, что цель cs SE состоит в том, чтобы предоставить начинающим более дружественный форум, чем cseheory SE, но предложенный здесь микроуровень управления сделал его намного хуже.
Ответы:
Если вы хотите получить общее представление, не углубляясь в технические детали, я предлагаю « Алгоритмику Дэвида Харела : дух вычислений» . После этого это мой любимый список:
источник
источник
Для математики, необходимой для анализа алгоритмов, я рекомендую один-единственный GKP:
Конкретная математика Грэма, Кнута, Паташника
Комплексная, высококачественная обработка практически всей математики, которая вам понадобится в (базовой) алгоритмике. Это занимательное чтение и включает в себя множество упражнений (и решений).
источник
Алгоритмы 4. Редакция Р. Седжвика
Введение в анализ алгоритмов П. Флажолет, Р. Седжвик
Введение в теорию автоматов, языков и вычислений Дж. Э. Хопкрофт, Дж. Д. Уллман, (Р. Мотвани)
Первое издание 1979 г. имеет больше теоретических результатов, которые отсутствуют во втором издании 2001 г. Еще не посмотрел на третьего Эда.
Введение в теорию формального языка М. А. Харрисон
Это с 1978 года, но я все еще хотел бы видеть его в списке.
Logicomix: эпический поиск истины A. Doxiadis, CH Papadimitriou
Потому что это совершенно потрясающе!
Опять 1979 год
. Компьютеры и труднопреодолимость Гэри и Джонсона : руководство по теории NP-полноты
Я бы хотел, чтобы TAoCP был в списке, но я боюсь, что дотошный подход дона Кнута - это то, что нельзя считать «вводным». К сожалению ...
источник
Если вы новичок в области TCS, « Введение в теорию вычислений» от Sipser - определенно лучшая книга для начала. Я читал другие вводные книги, и ни одна из них, по моему мнению, не приблизилась к способу Сипсера донести этот вопрос.
Другие, более конкретные, хорошие теоретические книги:
источник
Несколько хороших книг, охватывающих теорию B, часть TCS:
Логика в CS : Логика в области компьютерных наук: моделирование и рассуждение о системах Майкл Хут и Марк Райан.
Широкий охват различных областей применения логики в информатике. Около 3 курса бакалавриата.
Лямбда-исчисление : лямбда-исчисление и комбинаторы. Введение Дж. Роджера Хиндли и Джонатана П. Селдина.
Представляет лямбда-исчисление, которое является важным компонентом в основах языков программирования. Около 3 курса бакалавриата.
Ведущий в области предметной области : Введение в решетки и порядок (2-е изд.) . Авторы: Davey, BA and Priestley, HA Cambridge University Press. (2002).
Охватывает очень полезную тему, особенно если вы планируете работать с семантикой. Это немного более математично, чем другие темы, но первые главы, безусловно, находятся на продвинутом уровне бакалавриата.
Семантика : семантика с приложениями: закуска от Hanne Riis Nielson и Flemming Nielson.
Действительно хорошее введение в семантику языка программирования. Вместо того, чтобы углубляться в какой-либо конкретный формализм, он дает широкое представление и включает приложения, обычно не рассматриваемые в других книгах по семантике. Может быть полезно для студентов 2 курса.
источник
Это сводный ответ, который содержит книги из ответов с оценкой не менее пяти. Пожалуйста, обсудите его содержание в чате .
Алгоритмы и структуры данных
. Комплексное рассмотрение основных алгоритмов и структур данных, а также их анализ без углубленного изучения.
Наиболее интуитивное введение в алгоритмы с большим вниманием к интуиции, чем технические доказательства.
Вычислительность и сложность
Лучшее введение в теорию автоматов, вычислимость и сложность.
Формальные языки и автоматы
Стандартная книга о компиляторах; очень всеобъемлющий Прикосновения к теории автоматов тоже.
Прикладная Теория
Массивная книга, которую можно использовать как всеобъемлющее введение в проверку моделей.
Не учебник по алгоритмам, но прекрасно демонстрирует, как использовать методы проектирования алгоритмов для решения реальных задач. Может быть хорошим началом, если у вас есть предварительные знания по программированию.
источник