Jakie notatki z wykładu powinien przeczytać każdy?

Było kilka pytań o tym samym schemacie jak ten:

• Jakie gazety każdy powinien przeczytać
• Jakie książki każdy powinien przeczytać
• Jakie są najnowsze książki TCS, których wersje robocze są dostępne online
• jakie filmy wszyscy powinni oglądać

Nie chciałem publikować jeszcze jednego, ale notatki z wykładów na temat algorytmów Jeffa Ericksona zmieniły zdanie. Pomyślałem: o mój! Przez te wszystkie lata i nie widziałem tych doskonałych nut!

Pomyślałem więc, że mogą istnieć inne świetne notatki z wykładów, które naprawdę warto przeczytać. Tak więc, dla każdego podpola informatyki ( struktury danych, algorytmy, teoria obliczeń, złożoność obliczeniowa, kryptografia itp.), Polecam doskonałe wybrane notatki z wykładu i powiedz, dlaczego uważasz, że jest ono doskonałe.

Jedna prosta zasada, aby utrzymać porządek: Jedna odpowiedź na każde podpole. (To będzie wiki społeczności, więc możesz edytować istniejące odpowiedzi i dodać swoją rekomendację).

Teoria prawdopodobieństwa i algorytmy losowe

• Notatki z wykładu z kursu Ryana O'Donnella Prawdopodobieństwo i informatyka są całkiem fajne.

• Notatki z wykładu z kursu Amit Chakrabarti Algorytmy strumienia danych

Obliczenia kwantowe i informacje

Kilka doskonałych notatek z tej dziedziny:

• Notatki z wykładu Johna Preskilla na temat obliczeń kwantowych.

Kurs wprowadzający do obliczeń kwantowych. Wystarczająco dobry, aby zrobić z niego książkę. Znam kilku badaczy, którzy mają wydruk tych notatek na półce.

• Notatki z wykładu Johna Watrousa na temat teorii informacji kwantowej.

Zaawansowany kurs informacji kwantowej. Niektóre z najlepszych notatek z wykładów, jakie kiedykolwiek czytałem.

• Notatki z wykładu Andrew Childsa na temat algorytmów kwantowych.

Zaawansowany kurs algorytmów kwantowych. Bardzo dobre źródło najnowszych algorytmów kwantowych. Jeśli oryginalny artykuł na temat jakiegoś algorytmu kwantowego jest trudny do zrozumienia, sprawdzę to w następnej kolejności.

• Notatki z wykładu Scotta Aaronsona na temat obliczeń kwantowych od czasów Demokryta.

Nie mogę streścić tego kursu w jednym wierszu. Przeczytaj opis na stronie kursu.

• Notatki z wykładu Unruha na temat kryptografii kwantowej.

Obejmuje ogólne wprowadzenie do obliczeń kwantowych, a także tematy specyficzne dla kryptografii, takie jak dystrybucja klucza kwantowego, zobowiązania kwantowe, ograniczony model przechowywania kwantowego i kwantowa zerowa wiedza.

Złożoność obliczeniowa

Istnieje wiele doskonałych kursów na ten temat. Poniżej znajduje się zaledwie wierzchołek góry lodowej. Aby wybrać jeden, proponuję przyjrzeć się materiałowi omawianemu na każdym kursie, a także oferowanemu poziomowi:

• Wprowadzenie do teorii złożoności przez Oded Goldreich . Dostępne w dwóch wariantach: notatki na dwuletni kurs wprowadzający i notatki na semestr . Możesz także sprawdzić książkę Goldreicha o złożoności obliczeniowej .
• Dwa różne kursy złożoności obliczeniowej oferowane w Princeton przez Sanjeev Arora i Boaz Barak . Możesz także sprawdzić ich książkę na temat złożoności obliczeniowej .
• Teoria złożoności przez Erica Allender . Sugerowany przez Boaza Baraka na jego stronie głównej.
• Teoria złożoności autorstwa Lucy Trevisana . Sugerowany przez Boaza Baraka na jego stronie głównej.
• Zaawansowana teoria złożoności autorstwa Madhu Sudan . Sugerowany przez Boaza Baraka na jego stronie głównej.
• Wykłady o złożoności obliczeniowej autorstwa Jin-Yi Cai . Napisane mniej więcej w formie książki.
• Podejścia do pytania P kontra NP i związane z tym pytania dotyczące złożoności autorstwa Tonianna Pitassiego , z gościnnymi wykładami Steve'a Cooka, Miki Goos, Joshua Grochow, David Liu i Roberta Robere. Kurs dla absolwentów obejmujący wiele najnowocześniejszych technik dolnej granicy, z których kilka nie jest dobrze opisanych (lub w ogóle) w innych notatkach z wykładów.

A teoretyk za Toolkit przez Sanjeev Arora.

Uwielbiam te notatki, ponieważ daje raczej kompletny zestaw narzędzi do atakowania problemów w teorii złożoności. Na przykład wymiar VC jest szeroko stosowany do udowodnienia dolnych granic w modelu komunikacyjnym, a te uwagi wyjaśniają to tak dobrze i od podstaw.

Teoria informacji

• Anup Rao „s teoria informacji notatki wykładowe podać szczegółowy opis narzędzi najnowocześniejszych i jak są one stosowane w najnowszych badaniach, w tym pracy z 2010 r.

PCP i twardość aproksymacji

• Kurs oferowany przez Uri Feige jest bardzo dobry.
• Kolejny doskonały kurs oferuje Luca Trevisan .
• Jeszcze inny kurs oferują Irit Dinur i Dana Moshkovitz . Ten wygląda bardziej jak farma linków i ma niewiele notatek.
• Granice algorytmów aproksymacyjnych: PCP i unikalne gry autorstwa Prahladha Harsha

Dyskretna matematyka

Discrete Mathematics for Computer Science autorstwa Lehmana, Leightona i Meyera ( starsza wersja )

Pseudolosowość

Najlepszy kurs na ten temat oferuje Salil Vadhan . Zobacz także ten temat, aby zapoznać się z szkicem książki Salila o pseudolosie.

Kryptografia

Istnieje wiele doskonałych notatek z wykładów na ten temat, wszystkie autorstwa znanych osób w tej dziedzinie. Możesz wybrać jeden (lub dwa) z poniższych do nauki; wszystko zależy od środowiska, tła i wymagań:

• Lecture Notes na kryptografii przez Shafrira Goldwasser i Mihir Bellare 2008. serię wykładów dla kryptografii i bezpieczeństwa komputera [6.87s] , o długości jednego tygodnia kurs na kryptografii wykładał na MIT.
• Zaawansowane tematy w kryptografii , obejmujące bardziej zaawansowane tematy niż zwykłe kursy.
• Zaawansowane tematy w kryptografii autorstwa Jonathana Katza 2004. Obejmuje interesujący zakres tematów w zaawansowanej kryptografii. Bardziej podstawowe leczenie można znaleźć tutaj .
• (Sugerowane przez Yasser ): Wykłady Jewgienija Dodisa na temat kryptografii wprowadzającej i zaawansowanej .
• Kryptografia autorstwa Boaza Baraka (2010).
• Podstawy kryptografii autorstwa Jehudy Lindell 2010. Na podstawie słynnej książki Goldreich użytkownika .
• Kryptografia przez Luca Trevisan . Notatki Lucy bardzo ładnie obejmują podstawowe tematy.
• Zaawansowana kryptografia autorstwa Daniele Micciancio . Obejmuje wiele zaawansowanych tematów i jest szczególnie skłonny do bezpiecznych protokołów wielostronnych .
• Wprowadzenie do kryptografii przez Salil Vadhan . Dobry dla początkującego / średniozaawansowanego.

Wykresy ekspanderów

Autorytatywny kurs jest oferowany przez Nati Linial i Avi Wigderson . Zobacz ten temat, aby uzyskać więcej informacji,

Geometria obliczeniowa

Lecture Notes autorstwa Davida Górze .

SAT

Kilka lat temu odwiedziłem kurs SAT u profesora Welzla. Jego notatki z wykładów są zdecydowanie najlepsze, jakie widziałem przez całe moje studia.

Niestety tylko wersja 2005 jest dostępna online, w tym krótka lista aktualizacji .

(Najszybszy algorytm SAT oraz konstruktywny dowód lokalnej lematy Lovásza pochodzą od facetów z jego grupy.)

Optymalizacja kombinatoryczna

• Tematy Chandra Chekuri w optymalizacji kombinatorycznej
• Tematy Michela Goemansa w optymalizacji kombinatorycznej
• Kurs Lexa Schrijvera na temat optymalizacji kombinatorycznej
• Techniki wielościenne Jana Vondraka w optymalizacji kombinatorycznej

Kurs „Perły algorytmów”. Część 3 : Analiza probabilistyczna i algorytmy losowe. Te wykłady notatki są na wygładzonej analizy . Szczególnie podoba mi się rysunek 1.1 na trzeciej stronie.

Teoria wykresów spektralnych

• Spielman (Yale, 2009)
• Chung (UCSD, 2010)