Was sind die neuesten TCS-Bücher, deren Entwürfe online verfügbar sind?

99

Im Anschluss an den Beitrag Welche Bücher sollten alle lesen , habe ich festgestellt, dass es neuere Bücher gibt, deren Entwürfe online verfügbar sind.

Beispielsweise zitiert der Eintrag zu Approximationsalgorithmen im obigen Beitrag ein 2011 erscheinendes Buch mit dem Titel The design of approximation algorithms .

Ich denke, dass es sehr nützlich ist, aktuelle Arbeiten zu kennen, um einen Eindruck von TCS-Trends zu bekommen. Wenn Entwürfe verfügbar sind, kann man die Bücher überprüfen, bevor man sie tatsächlich kauft.

Damit,

Was sind die neuesten TCS-Bücher, deren Entwürfe online verfügbar sind?

Mit "kürzlich" meine ich hier etwas, das nicht älter als ~ 5 Jahre ist.

reference-request big-list books Rahab
quelle
2
Ich habe es als CW gekennzeichnet.
Rahab
2
Es wäre schön, wenn die Antworten auch in CW umgewandelt würden, damit wir sie abstimmen können.
Kaveh
Antworten werden standardmäßig CW, wenn die Frage CW ist.
Suresh Venkat
3
@ Suresh: Wir haben aber bereits Antworten, die nicht in CW sind, und sie sollten auch in CW umgewandelt werden.
Jukka Suomela
@Suresh und @Jukka, wie kann ich meine Antwort ändern?
Alessandro Cosentino

Antworten:

43

Mehrere TCS-Bücher von Now Publishers sind in Entwürfen enthalten:

Darüber hinaus sind Entwürfe mehrerer Springer-Bücher zum Thema "Informationssicherheit und Kryptographie" online verfügbar:

MS Dousti
quelle
38

Rechnerische Komplexität von Arora und Barak : Ein moderner Ansatz , 2010.

M. Alaggan
quelle
29
Eine Warnung. der entwurf ist wirklich nur das: ein entwurf. Es gibt zahlreiche Fehler im Entwurf, die in der gedruckten Version behoben wurden (ich weiß das, weil ich eine Sommerlesegruppe mit dem Entwurf leitete und ihn ständig aus dem Buch korrigieren musste)
Suresh Venkat
4
Das Buch ist wirklich einen Kauf wert. Nicht teuer für seinen Wert und Größe.
Dai Le
37

Algorithmen von S. Dasgupta, CH Papadimitriou und UV Vazirani

BEARBEITEN (16. September 15): Der Link ist kaputt. Ich glaube, der Entwurf ist online nicht mehr verfügbar.

Alessandro Cosentino
quelle
Der Link ist seit dem 10.12.2013 nicht mehr funktionsfähig. Vielleicht ist der Online-Zugang nicht mehr verfügbar?
Logan Mayfield
1
@LoganMayfield das ist seltsam, weil Sie immer noch die einzelnen Kapitel hier zugreifen können
Alessandro Cosentino
1
Hier ist ein Link für das Buch cse.iitd.ernet.in/~naveen/courses/CSL630/all.pdf
drzbir
34

Lassen Sie mich Folgendes hinzufügen:

Analytic Combinatorics von Flajolet und Sedgewick

Codes und Automaten (Link Broken) von Berstel, Perrin und Reutenauer

Hermann Gruber
quelle
27

Sariel Har-Peled hat ein bevorstehendes Buch über geometrische Approximationsalgorithmen. Es liegt seit einiger Zeit als Skriptentwurf vor.

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

Chandra Chekuri
quelle
arggh. Wie um alles in der Welt habe ich das vergessen!
Suresh Venkat
1
@ Suresh: (nur ein Scherz) Ein älterer Moment vielleicht;)
MS Dousti
arggh. eher wie ein Moment, in dem es an Kaffee mangelt :)
Suresh Venkat
5
Und es ist nicht mehr online verfügbar - der Veröffentlichungstermin rückt näher und ich habe dem Verlag (AMS) versprochen, es nicht online zu stellen. Entschuldigung ...
Sariel Har-Peled
25

Boolesche Funktionskomplexität: Fortschritte und Grenzen von Stasys Jukna.

(Vorwort) (Inhaltsverzeichnis)

Früher stand ein kostenloser Entwurf als direkter Download zur Verfügung (wenn ich mich recht erinnere), aber jetzt können Sie ihn anscheinend erhalten, indem Sie ein Formular auf seiner Webseite ausfüllen oder ihm eine E-Mail senden.

Robin Kothari
quelle
1
Zum Thema Boolesche Funktionen und Fourier-Analyse: Analyse von Booleschen Funktionen , von Ryan O'Donnell (2014): Die PDF-Version finden Sie hier .
Clement C.
24

Stephen Cook & Phuong Nguyen veröffentlichte ein Buch namens logische Grundlagen der Beweiskomplexität im März 2010 Es gibt einen Entwurf auf Cooks Webseite: hier . Leider habe ich es nicht gelesen.

Michael Blondin
quelle
3
Kapitel 2 selbst ist bereits eine sehr elegante Einführung in die Aussagenlogik und die Logik erster Ordnung mit wichtigen Werkzeugen wie Vollständigkeit, Kompaktheit, Löwenheim-Skolem und Hebrands Theorem.
Dai Le
3
Ich habe viele Teile des Buches gelesen und kann es allen empfehlen, die sich für Komplexität und Logik interessieren. Für Leute, die mit Beweiskomplexität arbeiten, denke ich, ist dies möglicherweise ein Muss. Es behandelt nicht die unteren Schranken der Beweiskomplexität, die das Hauptthema des Themas sind, sondern den wesentlichen logischen Kontext der Beweiskomplexität. Es ist besonders für Anfänger und zum Selbststudium geeignet. Wörtlich wird kein Vorwissen vorausgesetzt, alles wird von Grund auf erklärt und für alles werden vollständige Details bereitgestellt. (Auch der Entwurf ist fast der gleiche wie das Buch.)
Iddo Tzameret
22

Markov-Ketten und Mischzeiten von DA Levin, Y. Peres, EL Wilmer (2008). Endlich ein Lehrbuch zu diesem breiten und allgegenwärtigen Thema.

Martin Schwarz
quelle
1
Das ist ein schönes Buch.
Suresh Venkat
21

Es gibt ein neues Buch über Spektralalgorithmen von Ravi Kannan und Santosh Vempala, das verschiedene neueste Entwicklungen behandelt. Es behandelt verschiedene Anwendungen von Spektralmethoden, Algorithmen zur Schätzung von Spektralparametern und die Annäherung von Matrizen mit niedrigem Rang.

Shiva Kintali
quelle
20

Da Suresh Venkat die Monographie über Expander erwähnte, werde ich auch die folgenden verwandten Monographien zum Thema Pseudozufälligkeit erwähnen . Der Entwurf der Pseudozufälligkeit von Salil Vadhan (220 Seiten) ist sehr lesenswert. Die Monographie Parwise Independence and Derandomization von Luby und Wigderson ist auch schön!

Dai Le
quelle
18

Die Bücher in Open Access von der Website des Mathematical Sciences Research Institute:

Hier habe ich nur die Bücher aufgelistet, die für mich am besten zur Definition von TCS passen.

NB. Bücher sind keine Entwürfe und wurden veröffentlicht.

Oleksandr Bondarenko
quelle
2
Wow, exzellente Quelle!
Dai Le
12

Hubert Comon, Max Dauchet, Remi Gilleron, Florent Jacquemard, Denis Lugiez, Sophie Tison, Christof Löding, Marc Tommasi: Techniken und Anwendungen von Baumautomaten

Hermann Gruber
quelle
12

"Deskriptive Komplexität, Kanonisierung und definierbare Graphstrukturtheorie" von Martin Grohe. Datum des Manuskripts: 7. März 2013. Verfügbar unter: http://www.automata.rwth-aachen.de/~grohe/pub.en . (Link gebrochen)

lgidwani
quelle
10

Es gibt einen Online-Entwurf des neuen Buches "Iterative Methoden in der kombinatorischen Optimierung" von Lap Chi Lau, R. Ravi und Mohit Singh:

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

Es geht um die iterative Rundungsmethode: eine neue Technik, mit der Approximationsalgorithmen für viele Probleme entworfen werden können.

Bart
quelle
10

"Logik und diskrete Mathematik für Informatiker", von James Caldwell. Manuskriptdatum: 22. August 2011. Verfügbar unter: http://www.cs.uwyo.edu/~jlc/courses/2300/book.pdf .

"Datenstrukturen und Algorithmen, The Basic Toolbox" von Kurt Mehlhorn. Manuskript Datum: August 2008. Verfügbar unter: http://www.mpi-inf.mpg.de/~mehlhorn/ftp/Toolbox/ .

"Eine Einführung in die Graphentheorie und komplexe Netzwerke", von Martin Van Steen. Manuskriptdatum: Januar 2010. Verfügbar unter: http://www.distributed-systems.net .

"Kategorietheorie für Informatik" von Michael Barr und Charles Wells. Verfügbar unter http://www.tac.mta.ca/tac/reprints/articles/22/tr22.pdf .

"Philosophie der Informatik" von William J. Rappaport. Manuskriptdatum: 24. Dezember 2013. Verfügbar unter: http://www.cse.buffalo.edu/~rapaport/Papers/phics.pdf .

"Fractional Graph Theory: Ein rationaler Ansatz zur Theorie der Graphen" von Edward Scheinerman und Daniel Ullman. Verfügbar unter http://www.ams.jhu.edu/~ers/fgt/fgt.pdf .

lgidwani
quelle
10

"Grundlagen der Datenwissenschaft" ( pdf ) von Hopcroft und Kannan. Der Text wurde von Lipton in seinem Blog diskutiert . Wie der Titel andeutet, scheint der Schwerpunkt des Textes auf Anwendungen und Problemen im Zusammenhang mit Big Data und Lernproblemen zu liegen. Es scheint aus diesem Kurs herausgewachsen zu sein .

(Update 8/2015) Das Buch hat jetzt einen dritten Autor, Avrim Blum. Der pdf-Link wurde aktualisiert.

Logan Mayfield
quelle
1
neuere Version: cs.cornell.edu/jeh/book112013.pdf
domotorp
und ich denke, der Titel lautet Foundations of Data Science.
Domotorp
Der Link zur Version vom April 2014 auf der Hopcroft-Website wurde aktualisiert.
Logan Mayfield
8

PlanetMath listet über 150 Bücher auf, die online verfügbar sind. Die Liste wird regelmäßig aktualisiert (der neueste Eintrag ist der 09.01.2011). Bücher beziehen sich auf Mathematik, aber einige von ihnen sind auch in TCS nützlich.

MS Dousti
quelle
Link bitte? Ich konnte diese Liste auf PlanetMath nicht finden ...
Joshua Grochow
@JoshuaGrochow: Leider funktioniert der alte Link, den ich oben angegeben habe, nicht mehr. Ich werde es ersetzen, sobald ich den neuen Link finde.
MS Dousti