Видеолекции курса Базы данных.

Лекторы: Илья Тетерин, Вадим Цесько, Антон Волохов, Дмитрий Щитинин, Герман Андреев.

Лекция 1. Введение.

• О лекторе
• Организация курса
• Содержание курса
• Определения и примеры
• Классификация БД
• Домашнее задание

Лекция 2. Hash & Cache. CAP.

Hash & Cache:

• Hash table
• Архитектуры Web-приложений
• Cache
• Distributed cache
• Memcached
• Consistent hashing
• Redis

Consistency, Availability and Partition Tolerance:

• Remembrance Inc.
• CAP Theorem
• Транзакции

Лекция 3. Distributed Commit.

• 2PC & 3PC
• Отношение happens-before: Lamport Timestamps & Vector Clocks
• Протокол Raft
• Альтернативное домашнее задание

Лекция 4. Cassandra.

Лекция 5. MongoDB is a web-scale.

• Введение: терминология

• API: декларированные цели, особенности, запросы

• Устройство хранилища: работа с ФС, сложные запросы, индексы

• Репликация

• Шардирование: выбор ключа

• Секретный ингредиент

• Заключение: выводы, материалы

Лекция 6. Haystack.
Лекция «Haystack» про хранение фоток в Facebook по статье «Finding a Needle in Haystack: Facebook's Photo Storage»:

• Введение: материалы, мотивация, цифры, характер запросов, основные цели
• Background: типичная архитектура, предыдущее решение на NFS + NAS
• Архитектура: новая версия, задача, подход, компоненты (Directory, Cache, Store)
• Детали реализации: Store-файл, запросы, индекс, оптимизации
• Заключение: нагрузка
• Домашнее задание: промежуточные итоги, feature requests, общие замечания, тулзы

Лекция 7. HDFS.

Лекция 8. HBase.

Лекция 9. ZooKeeper.

Лекция 10. Lucene.

Лекция 11. Graph DB.

Презентация

Лекция 12. Multidimensional indexing.

Лекция 13. STM.

Дополнительные материалы:
Видеолекции курса Базы данных (2012).

Автор: Roman Brovko

Видеолекции курса Архитектура ЭВМ и основы ОС.

Лекторы: Кирилл Кринкин, Михаил Кринкин.

Курс предназначен для всех, кто уже имеет опыт разработки на языках высокого уровня и интересуется базовыми механизмами работы компьютера, образующими программный стек от аппаратуры до уровня интерфейсов операционной системы. Основная цель курса – познакомиться с архитектурой различных процессоров (Intel, ARM), понять как аппаратные компоненты связаны с программными, рассмотреть базовые механизмы операционной системы (реализация многозадачности, управление памятью, межпроцессные коммуникации), освоить на практике инструменты и методы системного программирования.

Лекция 1. Введение. История развития ВТ. Аппаратное и системное программное обеспечение.

Лекция 2. Архитектура ЭВМ. Процессоры. Системы команд и модели вычислений. CISC. RISC. Виртуальные машины.

Лекция 3. Системообразующие компоненты. Аппаратная архитектура.
Чипсеты. Шины. Микроконтроллеры (классификация, обзор семейств).

Лекция 4. Ассемблер в Linux.

Лекция 5. Архитектура программного стека. Основные компоненты ОС. Понятие ресурсов.
Сходства и различия современных операционных систем: windows, linux, qnx, iOS, Android. Управление процессами и потоками. Диспетчеризация.

Лекция 6. Управление памятью в операционной системе.

Лекция 7. Межпроцессное взаимодействие и примитивные сетевые возможности.

Лекция 8. Система команд ARM.

Лекция 9. Загрузчик.

Лекция 10. IPC: сокеты.

Лекция 11. Компоновка и загрузка программ.

Лекция 12. Операционные системы.

Дополнительные материалы:
Скачать Краткое введение в reverse engineering для начинающих
Ассемблер в Linux для программистов C
Видеолекции курса Параллельное программирование (2012).
Видеолекции курса Параллельное программирование (2014).
Таненбаум Э.Современные операционные системы. 3-е изд. — СПб.: Питер, 2010. — 1120 с.
Таненбаум Э., Вудхалл А. Операционные системы. Разработка и реализация (+CD). Классика CS. 3-е изд. — СПб.: Питер, 2007. — 704 с: ил.
Руководство по созданию простой UNIX-подобной ОС

Автор: Roman Brovko

Видеолекции курса Языки программирования и компиляторы.

Лектор: Дмитрий Булычев.

Литература по курсу:

1. S.Muchnik. Advanced Compiler Design & Implementation. Academic Press, Morgan Kaufmann, 1998.
2. А.Ахо, Р.Сети, С.Ульман. Компиляторы: принципы, технологии, инструменты. Вильямс, 2003.
3. А.Ахо, С.Ульман. Теория синтаксического анализа, перевода и компиляции. Том 1. М., «Мир», 1978.
4. F.Nielsen. Principles of Program Analysis. Springer, 2005.
5. F.Nielse, H-R.Nielsen. Semantics with Applications. Wiley Professional Computing, 1992.
6. B.Pierce. Types and Programming Languages. MIT Press, 2002.
7. T.Пратт. Языки программирования: разработка и реализация. 1978.
8. Б.К.Мартыненко. Языки и трансляции. Из-во СПбГУ, 2008.

Лекция 1. Введение.
Языки программирования, синтаксис, семантика, прагматика. Когнитивные особенности человеческого мышления и их влияние на развитие языков программирования. Языки программирования в ретроспективе. Процедурное, объектно-ориентированное, логическое и функциональное программирование. Предметно-ориентированные языки. Языки вне классификации. Абстрактный и конкретный синтаксис. Статическая и динамическая семантика.

Лекция 2.
Компиляция и интерпретация. Смешанные вычисления. Проекции Футамуры-Ершова.

Лекция 3. Операционная семантика большого шага.

Лекция 4. Операционная семантика малого шага.

Лекция 5.
Свойства семантик большого и малого шага. Структурная индукция. Эквивалентность семантик. Разная выразительная сила семантик большого и малого шагов.

Лекция 6.
Семантика параллельного исполнения. Основные определения лямбда-исчисления. Семантика произвольного и нормального порядка редукций.

Лекция 7.
Статическая семантика. Замкнутые программы; свободные программы. Неразрешимость проблемы свободы. Живые переменные и достигающие определения.

Лекция 8.
Элементарная типизация в виде статической семантики большого шага. Полурешетка типов, решение задачи типизации на основе достигающих определений.

Лекция 9.

Лекция 10.

Лекция 11.

Автор: Roman Brovko

Видеолекции курса Алгоритмы для NP-трудных задач.

Лектор: Александр Куликов.

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

Отдельное внимание будет уделено открытым задачам данной области.

Курс предполагает знакомство слушателей лишь с базовыми алгоритмическими идеями.

Основная литература:

• Книги:
  1. [FK10] Fedor V. Fomin and Dieter Kratsch. Exact Exponential Algorithms. Springer. 2010. [official]
  2. [V01] Vijay V. Vazirani. Approximation Algorithms. Springer. 2001. [official], [PDF]
  3. [WS11] David P. Williamson and David B. Shmoys. The Design of Approximation Algorithms. Cambridge University Press. 2011. [official], [PDF]
  4. [DPV06] Sanjoy Dasgupta, Christos Papadimitriou, Umesh Vazirani. Algorithms. McGraw-Hill. 2006. [official], [PDF]
  5. [CLR01] Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест. Алгоритмы: построение и анализ. Издательство МЦНМО. 2001.
• Обзоры:
  1. [W03] Gerhard J. Woeginger. Exact algorithms for NP-hard problems: a survey. Combinatorial optimization — Eureka, you shrink! Springer. 2003. [official], [PDF]
  2. [FK13] Fedor V. Fomin, Petteri Kaski. Exact exponential algorithms. Communications of the ACM. 2013. [official], [PDF]
  3. [YWHL13] Dongxiao Yu, Yuexuan Wang, Qiang-Sheng Hua, Francis C.M. Lau. Faster and Space Efficient Exact Exponential Algorithms: Combinatorial and Algebraic Approaches. Handbook of Combinatorial Optimization, Springer. 2013, pp 1249-1291. [official], [PDF]
• Lecture notes:
  1. [A09] AGAPE Spring School on Fixed Parameter and Exact Algorithms. [PDF]

Лекция 1. Введение.
Обзор курса, мотивация изучения приближённых и точных экспоненциальных алгоритмов.

Лекция 2. NP-полные задачи.

Задачи поиска, сведения, доказательство NP-полноты задач выполнимости, 3-выполнимости, задачи о независимом множестве, задачи о вершинном покрытии.

Литература: [DPV06, глава 8].

Лекция 3. Точные алгоритмы для задачи коммивояжёра и задачи о гамильтоновом цикле.

Метод динамического программирования (время: , память: ). [DPV06, глава 6]

Метод включений-исключений (время: , память: ). [FK10, глава 4]

Матрица Татта и перманент, решение для двудольного графа за времени и памяти. [Andreas Bjorklund. Determinant Sums for Undirected Hamiltonicity. FOCS 2010. [official], [PDF]], [Beating A Forty Year Old Result: Hamilton Cycles] [FK13]

Лекция 4. Приближённые алгоритмы для задачи коммивояжёра.

Лемма Шварца-Зиппеля. [
wikipedia]

Приближённые алгоритмы: 1.5-приближённый алгоритм для задачи коммивояжёра в метрическом пространстве, неприближаемость общего случая, 0.5-приближение для максимизационного варианта. [CLR01, V01]

Лекция 5. Приближённые алгоритмы для задачи коммивояжёра (продолжение).

2/3-приближение для максимального цикла коммивояжера в ориентированном графе. [Katarzyna E. Paluch, Khaled M. Elbassioni, Anke van Zuylen: Simpler Approximation of the Maximum Asymmetric Traveling Salesman Problem. STACS 2012: 501-506. PDF]

Эвристики: метод локального поиска и метод ветвей и границ. [DPV06]

Лекция 6. Точные алгоритмы для задачи о максимальном разрезе и задачи максимальной 2-выполнимости.
Точные алгоритмы со временем работы и памятью . [Ryan Williams. Algorithms and Resource Requirements for Fundamental Problems. PhD thesis, 2007. PDF] [W03] [FK13]

Лекция 7. Эвристики для задачи коммивояжёра, алгоритмы для задачи о надстроке.

Эвристики для задачи коммивояжёра: метод ветвей и границ, локальный поиск. [DPV, глава 9], [пост Ричарда Липтона: Branch And Bound—Why Does It Work?]

Алгоритмы для задачи о надстроке: точный алгоритм со временем работы и полиномиальной памятью, жадная гипотеза.

Лекция 8. Точные алгоритмы для задачи раскраски графа.

3-раскраска: время и полиномиальная память с помощью перебора, улучшение до ; вероятностный алгоритм через сведение к задаче 2-выполнимости; через использование максимальных по включению независимых множеств. Общая задача: время и память через динамическое программирование, улучшение до через максимальные по включению независимые множества; время и память через формулу включений-исключений и быстрое преобразование Фурье. [Thore Husfeldt, Graph colouring algorithms]

Лекция 9. Алгоритмы для задачи выполнимости: локальный поиск.

Локальный поиск: поиск выполняющего набора в шаре радиуса за ; оценки и с помощью покрытия шарами радиуса и .

Литература:
Uwe Schöning: A Probabilistic Algorithm for -SAT and Constraint Satisfaction Problems. FOCS 1999: 410-414. [official, PDF]
Evgeny Dantsin, Andreas Goerdt, Edward A. Hirsch, Ravi Kannan, Jon M. Kleinberg, Christos H. Papadimitriou, Prabhakar Raghavan, Uwe Schöning: A deterministic algorithm for -SAT based on local search. Theor. Comput. Sci. 289(1): 69-83 (2002). [official, PS]

Лекция 10. Алгоритмы для задачи выполнимости: метод расщепления.

DPLL-алгоритмы, основные идеи метода расщепления, вектор и число расщепления. для задачи 3-выполнимости одновыполнимой формулы через расщепление относительно случайной перестановки. Запоминание дизъюнктов: решение задачи выполнимости на формулах константной плотности за . Комбинированные меры сложности, measure and conquer: для задачи максимальной 2-выполнимости.

Литература:
Timon Hertli: 3-SAT Faster and Simpler — Unique-SAT Bounds for PPSZ Hold in General. FOCS 2011: 277-284
Ramamohan Paturi, Pavel Pudlák, Michael E. Saks, Francis Zane: An improved exponential-time algorithm for k-SAT. J. ACM 52(3): 337-364 (2005)
Alexander S. Kulikov, Konstantin Kutzkov: New Bounds for MAX-SAT by Clause Learning. CSR 2007: 194-204
Arist Kojevnikov, Alexander S. Kulikov: A new approach to proving upper bounds for MAX-2-SAT. SODA 2006: 11-17

Лекция 11. Приближённые алгоритмы.

2-приближённый алгоритм для задачи о вершинном покрытии через максимальное по включению паросочетание, 2-приближение для взвешенного случая через линейное программирование. Жадный -приближённый алгоритм для задачи о покрытии множествами. -приближённый алгоритм для задачи о множестве представителей через линейное программирование и вероятностное округление.

Лекция 12. Приближённые алгоритмы (продолжение).

4-приближённый алгоритм для задачи о кратчайшей общей надстроке через покрытие циклами.

0.878-приближённый алгоритм для задачи о максимальном разрезе через полуопределённое программирование и вероятностное округление.

Автор: Roman Brovko