Каковы последние книги TCS, проекты которых доступны онлайн?

99

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

Например, в статье « Алгоритмы аппроксимации» вышеприведенного поста цитируется книга 2011 года (еще не опубликованная) под названием «Разработка алгоритмов аппроксимации» .

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

Так,

Каковы последние книги TCS, проекты которых доступны онлайн?

Здесь под «недавним» я подразумеваю то, что не старше ~ 5 лет.

Рахаб
источник
2
Я отметил это для того, чтобы стать CW.
Рахаб
2
Было бы неплохо, если бы ответы также превратились в CW, чтобы мы могли проголосовать за них.
Каве
ответы становятся CW по умолчанию, если вопрос CW.
Суреш Венкат
3
@Suresh: Но у нас уже есть ответы не-CW, и их тоже нужно превратить в CW.
Юкка Суомела
@Suresh и @Jukka, как мне узнать мой ответ?
Алессандро Косентино

Ответы:

43

Несколько книг TCS от Now Publishers можно найти в черновиках:


Кроме того, в Интернете можно найти проекты нескольких книг Springer на тему «Информационная безопасность и криптография» :

MS Dousti
источник
38

Вычислительная сложность ароры и барака: современный подход , 2010.

М. Алагган
источник
29
Предупреждение. проект на самом деле просто: проект. В черновике есть множество ошибок, которые были исправлены в печатной версии (я знаю это, потому что я руководил группой летнего чтения, используя черновик, и мне приходилось постоянно исправлять ее из книги)
Суреш Венкат
4
Книга действительно стоит покупать. Совсем не дорого за свою стоимость и размер.
Дай Ле
37

Алгоритмы С. Дасгупты, К. Х. Пападимитриу и У. В. Вазирани

РЕДАКТИРОВАТЬ (16 сентября '15): ссылка не работает, я думаю, что черновик больше не доступен в Интернете.

Алессандро Косентино
источник
Ссылка не работает по состоянию на 10.10.2013. Возможно, онлайн-доступ больше не доступен?
Логан Мэйфилд
1
@LoganMayfield это странно, потому что вы все еще можете получить доступ к отдельным главам здесь: cs.berkeley.edu/~vazirani/algorithms
Алессандро
1
Вот ссылка на книгу cse.iitd.ernet.in/~naveen/courses/CSL630/all.pdf
drzbir,
32

У Одеда Голдрайха есть несколько черновиков, доступных для скачивания на его веб-странице.

Робин Котари
источник
27

У Сариэля Хар-Пеледа есть новая книга по алгоритмам геометрической аппроксимации. Некоторое время он был доступен в виде черновика в виде конспекта лекции.

http://valis.cs.uiuc.edu/~sariel/teach/notes/aprx/

Чандра Чекури
источник
arggh. как же я забыл это!
Суреш Венкат
1
@Suresh: (шучу) Может быть, старший момент;)
MS Dousti
arggh. больше похоже на момент отсутствия кофе :)
Суреш Венкат
5
И он больше не доступен в Интернете - дата публикации приближается, и я пообещал издателю (AMS) не размещать его в Интернете. Извините ...
Сариэль Хар-Пелед
25

Сложность булевой функции: достижения и границы . Стасис Юкна.

(Предисловие) (Содержание)

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

Робин Котари
источник
1
По теме булевых функций и анализа Фурье: анализ булевых функций , автор Райан О'Доннелл (2014): PDF-версия доступна здесь .
Климент С.
24

Стивен Кук и Фуонг Нгуен опубликовали книгу под названием « Логические основы сложности доказательств» в марте 2010 года. На сайте Кука есть черновик: здесь . К сожалению, я не читал это.

Майкл Блондин
источник
3
Сама глава 2 уже является очень изящным введением в логику высказываний и логику первого порядка с важными инструментами, такими как Полнота, Компактность, Левенгейм-Сколем и Теорема Хебранда.
Дай Ле
3
Я прочитал много частей книги и очень рекомендую ее людям, интересующимся сложностью и логикой. Для людей, работающих в доказательственной сложности, я думаю, что это возможно. Он не имеет дело с нижними границами сложности доказательства, что является основной проблемой темы, но он дает существенный логический контекст сложности доказательства. Особенно подходит как для начинающих, так и для самостоятельных занятий. Буквально, никаких предварительных знаний не предполагается, все объясняется с нуля, и все детали предоставляются для всего. (Кроме того, черновик почти такой же, как и в книге.)
Иддо Цамерет,
21

Новая книга о спектральных алгоритмах Рави Каннана и Сантоша Вемпалы, посвященная нескольким последним разработкам. Он охватывает несколько применений спектральных методов, алгоритмов оценки спектральных параметров и аппроксимации матриц низкого ранга.

Шива Кинтали
источник
20

Поскольку Суреш Венкат упомянул монографию о расширителях, я также упомяну следующие смежные монографии на тему псевдослучайности . Черновик псевдослучайности Салила Вадхана (220 страниц) очень стоит прочитать. Монография Parwise Independence и Derandomization от Люби и Вигдерсона также хороша!

Dai Le
источник
18

Книги в открытом доступе с сайта НИИ математических наук:

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

NB. Книги не являются черновиками и были опубликованы.

Александр Бондаренко
источник
2
Вау, отличный источник!
Дай Ле
12

«Описательная сложность, канонизация и теория определимых структур графов», Мартин Грох. Дата в рукописи: 7 марта 2013 г. Доступно по адресу: http://www.automata.rwth-aachen.de/~grohe/pub.en . (Ссылка не работает)

lgidwani
источник
10

Лап Чи Лау, Р. Рави и Мохит Сингх опубликовали черновик новой книги «Итерационные методы в комбинаторной оптимизации»:

http://www.cs.mcgill.ca/~mohit/book/book.html

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

Барт
источник
10

Заметки или книги о распределенных алгоритмах:

Клаудио Биале
источник
10

«Логика и дискретная математика для компьютерных ученых», Джеймс Колдуэлл. Дата рукописи: 22 августа 2011 г. Доступно по адресу: http://www.cs.uwyo.edu/~jlc/courses/2300/book.pdf .

«Структуры данных и алгоритмы, базовый инструментарий», Курт Мелхорн. Дата рукописи: август 2008 г. Доступно по адресу: http://www.mpi-inf.mpg.de/~mehlhorn/ftp/Toolbox/ .

«Введение в теорию графов и сложные сети», Мартин Ван Стин. Дата рукописи: январь 2010 г. Доступно по адресу: http://www.distributed-systems.net .

«Теория категорий для вычислительной науки», Майкл Барр и Чарльз Уэллс. Доступно по адресу http://www.tac.mta.ca/tac/reprints/articles/22/tr22.pdf .

«Философия информатики», Уильям Дж. Раппопорт. Дата рукописи: 24 декабря 2013 г. Доступно по адресу: http://www.cse.buffalo.edu/~rapaport/Papers/phics.pdf .

«Теория дробных графов: рациональный подход к теории графов», Эдвард Шейнерман и Даниэль Уллман. Доступно по адресу http://www.ams.jhu.edu/~ers/fgt/fgt.pdf .

lgidwani
источник
10

«Основы науки о данных» ( pdf ) Хопкрофта и Каннана. Текст обсуждался Липтоном в его блоге. Как видно из названия, акцент текста, похоже, делается на приложениях и проблемах, связанных с проблемами больших данных и обучения. Кажется, вырос из этого курса .

(Обновление 8/2015) У книги появился третий автор, Аврим Блум. Ссылка в формате PDF была обновлена.

Logan Mayfield
источник
1
более новая версия: cs.cornell.edu/jeh/book112013.pdf
domotorp
и я думаю, что название - Основы Науки Данных.
Домоторп
Обновлена ​​ссылка на апрельскую версию 2014 года, найденную на сайте Хопкрофт.
Логан Мэйфилд
8

PlanetMath перечисляет более 150 книг, которые доступны в Интернете. Список регулярно обновляется (последнее добавление 2011-01-09, на момент написания статьи). Книги связаны с математикой, но некоторые из них полезны и в TCS.

М.С. Дусти
источник
ссылку пожалуйста? Я не смог найти этот список на PlanetMath ...
Джошуа Грохов
@JoshuaGrochow: К сожалению, старая ссылка, которую я указал выше, больше не работает. Я заменю его, как только найду новую ссылку.
MS Dousti