¿Qué apuntes deberían leer todos?

113

Ha habido varias preguntas con el mismo esquema que este:

Era reacio a publicar otro más, pero las notas de clase de Jeff Erickson sobre algoritmos me hicieron cambiar de opinión. Pensé: ¡Dios mío! ¡Todos estos años y no he visto estas excelentes notas!

Entonces, pensé que podría haber otras excelentes notas de clase, que realmente valga la pena leer. Por lo tanto, para cada subcampo de ciencias de la computación ( estructuras de datos, algoritmos, teoría de la computación, complejidad computacional, criptografía , etc.), recomiende las excelentes notas de clase de su elección y explique por qué cree que son excelentes .

Una regla simple para mantenerlo ordenado: una respuesta por cada subcampo. (Esta será una wiki comunitaria, por lo que puede editar las respuestas existentes y agregar su recomendación).

reference-request soft-question big-list M.S. Dousti
fuente
99
Tienes mi voto. Si tan solo tal lista hubiera existido cuando era estudiante ...
Anthony Labarre
77
¡Gracias por el enlace a las excelentes notas de Jeff Erickson!
Standa Zivny
2
Entonces, ¿esta pregunta también debería ser wiki comunitaria?
Dave Clarke el
@Dave: Sí, ya lo he marcado como CW. Requiere mod atención.
MS Dousti
Desearía poder votar esto más de una vez.
Vivek Bagaria el

Respuestas:

31

Teoría de la probabilidad y algoritmos aleatorizados

Derrick Stolee
fuente
2
Este enlace ahora está muerto. ¿Podría arreglarlo o se eliminará?
Dave Clarke
55
@Dave, parece que ya no hay un enlace desde la página web de Ryan al curso. Pero no creo que eliminar la entrada sea una buena idea, podría volver a poner el enlace en algún momento. Su comentario de que el enlace está roto es suficiente OMI.
Kaveh
@DaveClarke El enlace es fijo. ¡Hurra!
Jardine
24

Computación cuántica e información

Algunas excelentes notas de clase de este campo:

Un curso introductorio sobre computación cuántica. Lo suficientemente bueno como para convertirse en un libro. Conozco varios investigadores que tienen una copia impresa de estas notas en su estantería.

Un curso avanzado sobre información cuántica. Algunas de las mejores notas de conferencias que he leído.

Un curso avanzado sobre algoritmos cuánticos. Un muy buen recurso para algoritmos cuánticos recientes. Si el documento original sobre algún algoritmo cuántico es difícil de entender, aquí es donde verificaría a continuación.

No puedo resumir este curso en una línea. Lea la descripción en la página web del curso.

Incluye una introducción general a la computación cuántica, así como temas específicos de criptografía como la distribución de claves cuánticas, compromisos cuánticos, modelo de almacenamiento cuántico limitado y conocimiento cero cuántico.

Robin Kothari
fuente
Muy interesante, gracias. Siempre quise aprender computación cuántica, pero no tuve suficiente tiempo para leer un libro. ¿Conoces algún curso dedicado a la criptografía cuántica ? Encontré uno aquí , pero desafortunadamente, las notas no están disponibles en línea.
MS Dousti
@Sadeq: Lo siento, no tengo idea.
Robin Kothari
23

Complejidad computacional

Hay muchos cursos excelentes sobre este tema. Lo siguiente es simplemente la punta del iceberg. Para elegir uno, sugiero echar un vistazo al material cubierto en cada curso, así como al nivel que se ofrece:

MS Dousti
fuente
22

El juego de herramientas de un teórico de Sanjeev Arora.

Me encantan estas notas porque te da un conjunto bastante completo de herramientas para atacar problemas en la teoría de la complejidad. Por ejemplo, la dimensión VC se usa ampliamente para probar límites inferiores en el modelo de comunicación, y estas notas lo explican muy bien y desde lo básico.

Marcos Villagra
fuente
17

PCP y dureza de aproximación

Sadeq Dousti
fuente
¿Cuál de ellos leíste?
Thomas Ahle
17

Matemáticas discretas

Matemáticas discretas para informática por Lehman, Leighton y Meyer ( versión anterior )

Jeffε
fuente
Recibo un error prohibido 403 en su enlace.
Derrick Stolee
@Derrick: el error desapareció o el enlace se corrigió.
MS Dousti
Sí, ambos enlaces funcionan ahora .....
Derrick Stolee
De ahí el enlace a la versión anterior.
Jeffε
1
Actualmente versión más actualizada: cursos.csail.mit.edu/6.042/spring15/mcs.pdf . Se siente como encontrar el enlace correcto en medio de los muchos espejos obsoletos se ha convertido en un problema NP-completo ...
Darij grinberg
16

Pseudoaleatoriedad

El mejor curso sobre el tema lo ofrece Salil Vadhan . Vea también este tema para un borrador del libro de Salil sobre pseudoaleatoriedad.

M.S. Dousti
fuente
15

Criptografía

Hay una serie de excelentes notas de clase sobre el tema, todas de personas famosas en el campo. Puede elegir uno (o dos) de los siguientes para estudiar; todo depende de su entorno, antecedentes y requisitos:

MS Dousti
fuente
11

SAB

Visité un curso SAT hace unos años con el profesor Welzl. Sus apuntes son, con mucho, los mejores que he visto en todos mis estudios.

Desafortunadamente, solo la versión 2005 está en línea, incluida una breve lista de actualizaciones .

(El algoritmo SAT más rápido, así como la prueba constructiva del lema local de Lovász, provienen de los chicos de su grupo).

Sacha
fuente