Après le post Ce que les livres doivent être lus par tous , j'ai remarqué qu'il existe des livres récents dont les brouillons sont disponibles en ligne.
Par exemple, l' entrée Algorithmes d'approximation de l'article ci-dessus cite un livre de 2011 (à paraître) intitulé La conception d'algorithmes d'approximation .
Je pense que connaître les travaux récents est vraiment utile pour quiconque veut avoir une idée des tendances du SDC. Lorsque des brouillons sont disponibles, on peut vérifier les livres avant de les acheter.
Alors,
Quels sont les récents ouvrages du SDC dont les brouillons sont disponibles en ligne?
Ici, par "récent", je veux dire quelque chose qui n’a pas plus de 5 ans.
Réponses:
Plusieurs ouvrages de TCS de Now Publishers peuvent être trouvés dans les brouillons:
Fondements de la cryptographie - Une introduction par Oded Goldreich. Ceci est une version résumée de son célèbre livre en deux volumes sur la cryptographie. (Le brouillon de la version en deux volumes se trouve dans la réponse de Robin .)
Flux de données: algorithmes et applications par S. Muthukrishnan.
Aspects mathématiques des temps de mélange dans les chaînes de Markov du Monténégro et de Tetali.
Indépendence par paires et dénormalisation par Luby & Widgerson.
Complexité moyenne par Bogdanov & Trevisan.
Enquête sur les limites inférieures de la satisfiabilité et des problèmes connexes par Melkebeek.
Algorithmes et structures de données pour la mémoire externe par Vitter.
Systèmes de preuve probabilistes: Un apprêt par Goldreich. Encore une fois, il s’agit d’une version résumée du livre d’une partie de Goldreich sur la cryptographie moderne, les preuves probabilistes et le pseudo-aléa .
La conception d’algorithmes en ligne compétitifs via une approche Primal-Dual de Buchbinder & Naor.
Algorithmes spectraux de Kannan & Vempala.
Sur la puissance du calcul de faible profondeur de Viola.
Techniques algorithmiques et d'analyse dans les tests de propriétés par Ron.
Circuits arithmétiques: une enquête sur les résultats récents et les questions ouvertes d'Amir Shpilka et Amir Yehudayoff (2010), Foundations and Trends® in Theoretical Computer: Vol. 5: N ° 3–4, pp 207-388. http://dx.doi.org/10.1561/0400000039
Des brouillons de plusieurs livres Springer sur «la sécurité de l’information et la cryptographie» sont également disponibles en ligne:
Cryptographie en temps parallèle constant par Applebaum.
Une étude des preuves statistiques de zéro connaissance par Vadhan.
Codes localement décodables et schémas de récupération d'informations privées par Yekhanin.
Connaissance zéro simultanée par Rosen.
la source
Complexité informatique d' Arora et de Barak : une approche moderne , 2010.
la source
Algorithmes de S. Dasgupta, CH Papadimitriou et UV VaziraniEDIT (16 sept '15): Le lien est cassé, je pense que le brouillon n'est plus disponible en ligne.
la source
Permettez-moi d'ajouter ce qui suit:
La combinatoire analytique , par Flajolet et Sedgewick
Codes et automates(Link Broken), de Berstel, Perrin et Reutenauerla source
Oded Goldreich a plusieurs brouillons à télécharger sur sa page Web.
Complexité informatique: une perspective conceptuelle (2008)
Complétude P, NP et NP: les bases de la théorie de la complexité (2010)
Les fondements de la cryptographie (2001 et 2004)
Introduction aux générateurs pseudo-aléatoires (2010)
Introduction aux tests de propriété (2017)
la source
La théorie des graphes de Reinhard Diestel (4ème édition, 2010), sous divers formats électroniques.
la source
Sariel Har-Peled a un livre à paraître sur les algorithmes d’approximation géométrique. Il est disponible sous forme de brouillon sous forme de notes de cours depuis un moment.
http://valis.cs.uiuc.edu/~sariel/teach/notes/aprx/
la source
Expander Graphs et leurs applications , par Hoory, Linial et Wigderson. Cela frôle le territoire de la monographie avec 123 pages.
la source
Complexité des fonctions booléennes: avancées et frontières par Stasys Jukna.
(Préface) (Table des matières)
Un brouillon gratuit était disponible en téléchargement direct il y a quelque temps (si je me souviens bien), mais il semble maintenant que vous puissiez l'obtenir en remplissant un formulaire sur sa page Web ou en l'envoyant par courrier électronique.
la source
Stephen Cook et Phuong Nguyen ont publié un livre intitulé Fondements logiques de la complexité de la preuve en mars 2010. Il existe un brouillon sur le site Web de Cook: ici . Malheureusement, je ne l'ai pas lu.
la source
Chaînes de Markov et temps de mélange de DA Levin, Y. Peres, EL Wilmer (2008). Enfin, un livre de texte couvrant ce sujet vaste et omniprésent.
la source
Il y a un nouveau livre à venir sur les algorithmes spectraux par Ravi Kannan et Santosh Vempala couvrant plusieurs derniers développements. Il couvre plusieurs applications des méthodes spectrales, des algorithmes d'estimation des paramètres spectraux et de l'approximation des matrices à faible rang.
la source
Puisque Suresh Venkat a mentionné la monographie sur les expandeurs, je mentionnerai également les monographies suivantes sur le sujet du pseudo - aléa . Le brouillon de Pseudoaléatoire de Salil Vadhan (220 pages) est très intéressant à lire. La monographie Parwise Independence and Derandomization de Luby et Wigderson est également intéressante!
la source
Les livres en libre accès depuis le site de l’Institut de recherche en sciences mathématiques:
Ici, je n'ai répertorié que les livres qui me correspondent le mieux à la définition du SDC.
NB Les livres ne sont pas des brouillons et ont été publiés.
la source
La méthode de la discordance , Bernard Chazelle.
Probabilité sur les arbres et les réseaux , Russell Lyons avec Yuval Peres
Les deux sont de bonnes lectures! Vous voudrez peut-être saisir Lyons-Peres maintenant avant de le déconnecter.
la source
Livre de Bruno Courcelle " Structure de graphe et logique monadique de second ordre, une approche théorique du langage ".
la source
Théorie des jeux algorithmiques , par Noam Nisan, Tim Roughgarden, Eva Tardos et Vijay V. Vazirani (2007).
la source
Arithmétique informatique moderne par RP Brent et P. Zimmermann.
la source
Hubert Comon, Max Dauchet, Rémi Gilleron, Florent Jacquemard, Denis Lugiez, Christof Löding, Sophie Tison et Marc Tommasi: Techniques et applications de l'automate d'arbre
la source
"Complexité descriptive, canonisation et théorie de la structure de graphe définissable", par Martin Grohe. Date sur le manuscrit: 7 mars 2013. Disponible à l'
adresse:http://www.automata.rwth-aachen.de/~grohe/pub.en.(Lien cassé)la source
Spectra of Graphs de Brouwer et Haemers . Je suis arrivé à ce livre par le biais du chapitre 16 (écrit par Spielman) dans Compinatorial Scientific Computing .
la source
"Modèles de calcul, Exploration de la puissance de l'informatique", par John E. Savage. Disponible sur http://www.cs.brown.edu/~jes/book/pdfs/ModelsOfComputation.pdf .
la source
Théorie des automates: une approche algorithmique par Javier Esparza
http://www7.in.tum.de/~esparza/automatanotes.html
la source
Il existe une version en ligne du nouveau livre "Méthodes itératives dans l'optimisation combinatoire" de Lap Chi Lau, R. Ravi et Mohit Singh:
http://www.cs.mcgill.ca/~mohit/book/book.html
Il s’agit de la méthode d’arrondissement itératif: une nouvelle technologie qui peut être utilisée pour concevoir des algorithmes d’approximation de nombreux problèmes.
la source
Notes ou livres sur les algorithmes distribués:
la source
"Logique et mathématiques discrètes pour informaticiens", par James Caldwell. Date du manuscrit: 22 août 2011. Disponible à l' adresse suivante : http://www.cs.uwyo.edu/~jlc/courses/2300/book.pdf .
"Structures de données et algorithmes, La boîte à outils de base", de Kurt Mehlhorn. Date du manuscrit: août 2008. Disponible à l' adresse : http://www.mpi-inf.mpg.de/~mehlhorn/ftp/Toolbox/ .
"Une introduction à la théorie des graphes et aux réseaux complexes", de Martin Van Steen. Date du manuscrit: janvier 2010. Disponible à l' adresse suivante : http://www.distributed-systems.net .
"Théorie des catégories pour la science informatique", par Michael Barr et Charles Wells. Disponible à http://www.tac.mta.ca/tac/reprints/articles/22/tr22.pdf .
"Philosophie de l'informatique", de William J. Rappaport. Date du manuscrit: 24 décembre 2013. Disponible à l' adresse suivante : http://www.cse.buffalo.edu/~rapaport/Papers/phics.pdf .
"Théorie des graphes fractionnaires: une approche rationnelle de la théorie des graphes", par Edward Scheinerman et Daniel Ullman. Disponible à l' adresse http://www.ams.jhu.edu/~ers/fgt/fgt.pdf .
la source
"Foundations of Data Science" ( pdf ) de Hopcroft et Kannan. Le texte a été discuté par Lipton sur son blog. Comme le titre l'indique, le texte semble mettre l'accent sur les applications et les problèmes liés au Big Data et aux problèmes d'apprentissage. Il semble être sorti de ce cours .
(Mise à jour 8/2015) Le livre a maintenant un troisième auteur, Avrim Blum. Le lien pdf a été mis à jour.
la source
PlanetMath répertorie plus de 150 livres disponibles en ligne. La liste est mise à jour régulièrement (le dernier ajout date du 2011-01-09 à ce jour). Les livres sont liés aux mathématiques, mais certains d'entre eux sont également utiles dans le TCS.
la source
Bayesian Reasoning and Machine Learning , par David Barber.
la source
Réseaux, foules et marchés: raisonnement sur un monde hautement connecté par David Easley et Jon Kleinberg.
http://www.cs.cornell.edu/home/kleinber/networks-book/
la source