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
quelle
Antworten:
Mehrere TCS-Bücher von Now Publishers sind in Entwürfen enthalten:
Grundlagen der Kryptographie - Eine Einführung von Oded Goldreich. Dies ist eine zusammengefasste Version seines berühmten zweibändigen Buches über Kryptographie. (Der Entwurf der zweibändigen Fassung ist in Robins Antwort zu finden .)
Datenströme: Algorithmen und Anwendungen von S. Muthukrishnan.
Mathematische Aspekte der Mischzeiten in Markovketten von Montenegro & Tetali.
Paarweise Unabhängigkeit und Derandomisierung von Luby & Widgerson.
Average-Case-Komplexität von Bogdanov & Trevisan.
Eine Übersicht über niedrigere Grenzen für Zufriedenheit und verwandte Probleme von Melkebeek.
Algorithmen und Datenstrukturen für den externen Speicher von Vitter.
Probabilistische Beweissysteme: Ein Primer von Goldreich. Auch dies ist eine zusammengefasste Version eines Teils von Goldreichs Buch Moderne Kryptographie, Probabilistische Beweise und Pseudozufälligkeit .
Das Design von kompetitiven Online-Algorithmen nach einem Primal-Dual-Ansatz von Buchbinder & Naor.
Spektrale Algorithmen von Kannan & Vempala.
Über die Kraft der Kleinstberechnung von Viola.
Algorithmus- und Analysetechniken beim Testen von Eigenschaften von Ron.
Arithmetische Schaltungen: Ein Überblick über aktuelle Ergebnisse und offene Fragen von Amir Shpilka und Amir Yehudayoff (2010), Grundlagen und Trends® in der theoretischen Informatik: Vol. 5: Nr. 3–4, S. 207–388. http://dx.doi.org/10.1561/0400000039
Darüber hinaus sind Entwürfe mehrerer Springer-Bücher zum Thema "Informationssicherheit und Kryptographie" online verfügbar:
Kryptographie in konstanter Parallelzeit von Applebaum.
Eine Studie über statistische wissensfreie Beweise von Vadhan.
Lokal decodierbare Codes und private Informationsabrufsysteme von Yekhanin.
Concurrent Zero Knowledge von Rosen.
quelle
Rechnerische Komplexität von Arora und Barak : Ein moderner Ansatz , 2010.
quelle
Algorithmen von S. Dasgupta, CH Papadimitriou und UV VaziraniBEARBEITEN (16. September 15): Der Link ist kaputt. Ich glaube, der Entwurf ist online nicht mehr verfügbar.
quelle
Lassen Sie mich Folgendes hinzufügen:
Analytic Combinatorics von Flajolet und Sedgewick
Codes und Automaten(Link Broken) von Berstel, Perrin und Reutenauerquelle
Oded Goldreich hat mehrere Entwürfe auf seiner Webseite zum Download bereitgestellt.
Computerkomplexität: Eine konzeptuelle Perspektive (2008)
P, NP und NP-Vollständigkeit: Grundlagen der Komplexitätstheorie (2010)
Die Grundlagen der Kryptographie (2001 und 2004)
Eine Einführung in Pseudozufallsgeneratoren (2010)
Einführung in das Testen von Eigenschaften (2017)
quelle
Reinhard Diestels Graphentheorie (4. Auflage, 2010) in verschiedenen elektronischen Formaten.
quelle
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/
quelle
Expander Graphen und ihre Anwendungen , von Hoory, Linial und Wigderson. Dies ist auf dem Gebiet der Monographie auf 123 Seiten knapp.
quelle
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.
quelle
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.
quelle
Markov-Ketten und Mischzeiten von DA Levin, Y. Peres, EL Wilmer (2008). Endlich ein Lehrbuch zu diesem breiten und allgegenwärtigen Thema.
quelle
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.
quelle
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!
quelle
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.
quelle
Die Diskrepanzmethode , Bernard Chazelle.
Wahrscheinlichkeit auf Bäumen und Netzen , Russell Lyons mit Yuval Peres
Beide sind großartig zu lesen! Vielleicht möchten Sie Lyons-Peres jetzt kaufen, bevor sie es offline schalten.
quelle
Buch von Bruno Courcelle " Graphstruktur und monadische Logik zweiter Ordnung, ein sprachtheoretischer Ansatz ".
quelle
Algorithmic Game Theory von Noam Nisan, Tim Roughgarden, Eva Tardos und Vijay V. Vazirani (2007).
quelle
Moderne Computerarithmetik von RP Brent und P. Zimmermann.
quelle
Hubert Comon, Max Dauchet, Remi Gilleron, Florent Jacquemard, Denis Lugiez, Sophie Tison, Christof Löding, Marc Tommasi: Techniken und Anwendungen von Baumautomaten
quelle
"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)quelle
Spektren von Graphen von Brouwer und Haemers . Ich bin über Kapitel 16 (geschrieben von Spielman) in Combinatorial Scientific Computing zu diesem Buch gekommen .
quelle
"Computermodelle zur Erforschung der Leistungsfähigkeit von Computern" von John E. Savage. Verfügbar unter http://www.cs.brown.edu/~jes/book/pdfs/ModelsOfComputation.pdf .
quelle
Automatentheorie: Ein algorithmischer Ansatz von Javier Esparza
http://www7.in.tum.de/~esparza/automatanotes.html
quelle
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.
quelle
Anmerkungen oder Bücher zu verteilten Algorithmen:
quelle
"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 .
quelle
"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.
quelle
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.
quelle
Bayesianisches Denken und maschinelles Lernen , von David Barber.
quelle
Netzwerke, Menschenmassen und Märkte: Überlegungen zu einer stark vernetzten Welt von David Easley und Jon Kleinberg.
http://www.cs.cornell.edu/home/kleinber/networks-book/
quelle