Какие лекционные заметки должен прочитать каждый?

113

Там было несколько вопросов с той же схемой, что и этот:

Я не хотел публиковать еще один, но конспект лекций Джеффа Эриксона об алгоритмах изменил мое мнение. Я подумал: о боже мой! Все эти годы и я не видел эти отличные заметки!

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

Одно простое правило: держать в порядке: один ответ на каждое подполе. (Это будет вики сообщества, поэтому вы можете редактировать существующие ответы и добавлять свои рекомендации.)

reference-request soft-question big-list М.С. Dousti
источник
9
Вы получите мой голос. Если бы только такой список существовал еще тогда, когда я был студентом ...
Энтони Лабарр
7
Спасибо за ссылку на отличные заметки Джеффа Эриксона!
Standa Zivny
2
Тогда должен ли этот вопрос также быть вики-сообществом?
Дэйв Кларк
@Dave: Да, я уже отметил это как CW. Это требует внимания модов.
MS Dousti
Хотел бы я поднять это более одного раза.
Вивек Багария

Ответы:

31

Теория вероятностей и рандомизированные алгоритмы

Derrick Stolee
источник
2
Эта ссылка сейчас мертва. Не могли бы вы исправить или это будет удалено?
Дейв Кларк
5
@ Дэйв, кажется, больше нет ссылки с веб-страницы Райана на курс. Но я не думаю, что удаление записи - это хорошая идея, он может вернуть ссылку в какой-то момент. Ваш комментарий о том, что ссылка не работает, достаточно IMO.
Каве
@DaveClarke Ссылка исправлена. Ура!
Джардин
24

Квантовые вычисления и информация

Некоторые отличные конспекты лекций в этой области:

Вводный курс по квантовым вычислениям. Достаточно хорош, чтобы быть превращенным в книгу. Я знаю нескольких исследователей, у которых есть распечатка этих заметок на их книжной полке.

Продвинутый курс по квантовой информации. Некоторые из лучших примечаний лекции, которые я когда-либо читал.

Продвинутый курс по квантовым алгоритмам. Очень хороший ресурс для последних квантовых алгоритмов. Если оригинальную статью о каком-то квантовом алгоритме трудно понять, то здесь я бы проверил следующее.

Я не могу суммировать этот курс в одну строку. Прочитайте описание на веб-странице курса.

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

Робин Котари
источник
Очень интересно, спасибо. Я всегда хотел научиться квантовым вычислениям, но у меня не было достаточно времени, чтобы прочитать книгу. Знаете ли вы какой-нибудь курс, посвященный квантовой криптографии ? Я нашел один здесь , но, к сожалению, заметки не доступны в Интернете.
MS Dousti
@ Садек: Извините, не знаю.
Робин Котари
23

Вычислительная сложность

Есть много отличных курсов по этой теме. Следующее является лишь верхушкой айсберга. Чтобы выбрать один, я предлагаю взглянуть на материал, охватываемый каждым курсом, а также на уровень, на котором он предлагается:

MS Dousti
источник
22

А Инструментарий теоретика по Санджив Арора.

Мне нравятся эти заметки, потому что они дают вам довольно полный набор инструментов для решения проблем в теории сложности. Например, VC-измерение широко используется для доказательства нижних границ в модели коммуникации, и эти примечания объясняют это так хорошо и с основ.

Marcos Villagra
источник
17

PCP и твердость приближения

Sadeq Dousti
источник
Кого из них ты сам читал?
Томас Але
17

Дискретная математика

Дискретная математика для информатики Лемана, Лейтона и Мейера ( старая версия )

Jeffε
источник
Я получаю 403 Запрещенную ошибку по вашей ссылке.
Деррик Столи
@Derrick: ошибка ушла или ссылка исправлена.
MS Dousti
Да, обе ссылки теперь работают .....
Деррик Столи
Отсюда и ссылка на старую версию.
Джеффс
1
В настоящее время более свежая версия: courses.csail.mit.edu/6.042/spring15/mcs.pdf . Такое ощущение, что найти правильную связь на фоне множества устаревших зеркал стало проблемой, полной NP ...
Дарий Гринберг
16

псевдослучайность

Лучший курс по этому вопросу предлагает Салил Вадхан . См. Также эту тему для черновика книги Салила о псевдослучайности.

М.С. Dousti
источник
15

криптография

Есть множество отличных конспектов лекций на эту тему, известных людей в этой области. Вы можете выбрать один (или два) из следующих предметов для изучения; все зависит от вашей среды, фона и требований:

MS Dousti
источник
11

СИДЕЛ

Я посетил курс SAT несколько лет назад с профессором Вельцлем. Его конспекты лекций являются лучшими из всех, что я видел за все время обучения.

К сожалению, только версия 2005 года онлайн, включая короткий список обновлений .

(Самый быстрый алгоритм SAT, а также конструктивное доказательство локальной леммы Ловаша получены от парней из его группы.)

Sacha
источник
11

Комбинаторная оптимизация

Остин Бьюкенен
источник
1
И Шрайвер: homepages.cwi.nl/~lex/files/dict.pdf
Сашо Николов
1
Заметки Яна Вондрака: syste.stanford.edu/~jvondrak/CS369P.html
Чандра Чекури,
9

Курс "Жемчужины алгоритмов". Часть 3 : вероятностный анализ и рандомизированные алгоритмы. Конспект лекций посвящен сглаженному анализу . Мне особенно нравится рисунок 1.1 на третьей странице.

Александр бондаренко
источник