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

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

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

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

Видеолекции курса Алгоритмы и структуры данных. Часть 2.

Лекторы: Александр Куликов, Михаил Дворкин.

Лекция 1. Пути в графах.
Кратчайшие пути при наличии рёбер отрицательного веса: алгоритм Беллмана-Форда; определение наличия цикла отрицательного веса в графе. Кратчайшие пути в ациклических ориентированных графах. Кратчайшие пути между всеми парами вершин: алгоритм Флойда-Уоршолла, алгоритм Джонсона.

Лекция 2. Жадные алгоритмы.
Общие принципы жадного метода. Непрерывная и дискретная задачи о рюкзаке. Задача о выборе заявок. Минимальное покрывающее дерево: свойство разреза, жадная стратегия.

Лекция 3. Алгоритм Крускала, система непересекающихся множеств.
Алгоритм Крускала, система непересекающихся множеств.

Семинар 1. Алгоритм Прима.

Семинар 2.

Семинар 3.

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

Семинар 4.

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

Семинар 5.

Лекция 6. RSA.
Генерация случайных простых чисел. Криптография: схемы с закрытым ключом, RSA.

Семинар 6.

Лекция 7. Быстрое преобразование Фурье.
Быстрое вычисление значений многочлена в точках: два способа задания многочленов — коэффициентами и значениями в точках; вычисление значений многочлена в точках методом «разделяй и властвуй»; дискретное преобразование Фурье; быстрое преобразование Фурье. Интерполяция: интерполяция в терминах матриц; матрица Вандермонда; интерполяция как домножение на обратную матрицу.

Семинар 7.

Лекция 8. Линейное программирование.
Линейное программирование: общий вид задачи, двойственность. Задача о макси
мальном потоке. Задача о паросочетании в двудольном графе.

Семинар 8.

Лекция 9. Симплекс-метод.
Подробнее о двойственности, симплекс-метод.

Семинар 9.

Лекция 10. Алгоритм Кнута-Морриса-Пратта.
Задача поиска подстроки в строке. Наивный алгоритм, алгоритм Карпа-Рабина, алгоритм Кнута-Морриса-Пратта.

Семинар 10.

Лекция 11. Суффиксные деревья.
Построение суффиксного дерева за линейное время.

Семинар 11.

Лекция 12. NP-полные задачи.
Задачи поиска, классы P и NP. Сведения. Доказательство NP-полноты задач выполнимости, 3-выполнимости, выполнимости схемы, задачи о независимом множестве.

Семинар 12.

Автор: Roman Brovko

Видеолекции курса Алгоритмы и структуры данных. Часть 1.

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

Лекция 1. Введение.
Вычисление чисел Фибоначчи: экспоненциальный рекурсивный алгоритм, полиномиальный алгоритм, более детальный анализ. Время работы алгоритма, O-символика. Скорость роста функций: логарифм, полином, экспонента.

Лекция 2. Рекуррентные соотношения.
Метод «разделяй и властвуй». Умножение n-битовых чисел: простой рекурсивный алгоритм, улучшенный рекурсивный алгоритм. Рекуррентные соотношения: основная теорема. Двоичный поиск.

Лекция 3. Алгоритмы сортировки.
Сортировка слиянием: с рекурсией и без. Сортировка с помощью кучи. Нижняя оценка (n log n) для сортировки. Быстрая сортировка: анализ среднего времени работы, анализ глубины рекурсии, элиминация хвостовой рекурсии.

Лекция 4. Алгоритмы сортировки (продолжение).
Быстрая сортировка (продолжение). Порядковые статистики: нахождение за линейное в среднем время.

Лекция 5. Элементарные структуры данных.
Абстрактные типы данных, интерфейс и реализация. Массивы переменного размера: аддитивная и мультипликативная схемы реаллокации. Анализ учётных стоимостей операций: функция потенциала, истинные и учётные стоимости. Стек, очередь, дек. Реализация на основе массива переменного размера и на основе связанного списка. Моделирование очереди с помощью двух стеков. Корневое дерево: бинарное дерево, дерево с произвольным ветвлением, представление «левый ребёнок — правый сосед».

Лекция 6. Динамическое программирование.
Предварительные сведения: ациклические ориентированные графы. Общие принципы динамического программирования, часто используемые подзадачи. Кратчайшие пути в ациклических ориентированных графах. Наибольшая возрастающая подпоследовательность: подзадачи, порядок на подзадачах, граф подзадач, сравнение с рекурсивным алгоритмом; нахождение не только длины, но и самой подпоследовательности. Стоимость редактирования: граф на подзадачах, нахождение кратчайшего пути в данном графе.

Лекция 7. Динамическое программирование (продолжение).
Задача о рюкзаке: рюкзак с повторениями и без, ленивые вычисления. Перемножение последовательности матриц: представление порядка перемножения в виде дерева, оценка на количество порядков. Независимые множества в деревьях. О времени и памяти алгоритмов, основанных на методе динамического программирования.

Лекция 8. Двоичные деревья поиска.
Дерево поиска: поиск, вставка, удаление, поиск следующего и предыдущего элемента за время, пропорциональное высоте. АВЛ-дерево (или какое-нибудь другое сбалансированное дерево): верхняя оценка на высоту, малое и большое вращение.

Лекция 9. Декартовы деревья.
Декартовы деревья, операции split и merge, реализация стандартных операций деревьев поиска через split и merge.

Лекция 10. Сплей-деревья.
Верхняя оценка O(log n) на среднюю стоимость операций.

Лекция 11. Декомпозиция графов.
Графы и способы их представления, способы использования графов. Поиск в глубину в неориентированных графах, выделение компонент связности.

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

Лекция 13. Пути в графах.
Расстояния в графе. Поиск в ширину: обход, дерево кратчайших путей, сравнение с поиском в глубину. Алгоритм Дейкстры: адаптация поиска в ширину введением дополнительных вершин; установка будильников; алгоритм Дейкстры; альтернативный взгляд на алгоритм: последовательное расширение множества вершин, до которых расстояние уже посчитано; время работы алгоритма при различных реализациях очереди с приоритетами.

Автор: Roman Brovko

Видеолекции курса Распределенные системы хранения и обработки данных.

Лектор: Владислав Белогрудов.

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

Лекция 1. Введение в системы хранения данных (СХД).

• данные и информация
• типы данных
• большие данные
• эволюция СХД
• архитектура центра обработки данных (ЦОД)
• характеристики ЦОД
• жизненный цикл информации
• иерархическое управление носителями

Лекция 2. Среда систем хранения данных.

• Oсновные элементы
• Виртуализация приложений и серверов
• Компоненты жесткого диска и его производительность
• Накопители SSD

Лекция 3. Защита данных с помощью RAID.

• Методы и техники
• Типы
• Производительность
• Cравнение и области применения

Лекция 4. Архитектура СХД.

• основные компоненты
• управление кешированием, защита от сбоев
• классы СХД

Лекция 5. Сети хранения FC SAN.

1. DAS
2. SCSI
3. SAN
   • компоненты
   • архитектура
   • топологии
   • зонирование

Лекция 6. IP SAN, FCoE, NAS, CAS.

• протоколы
• компоненты
• топологии

Лекция 7. OpenStack.

• Собственное облако
  • Зачем
  • Отличия от решений виртуализации серверов
• История развития
• Проекты
  • Swift
  • Glance
  • Nova
  • Cinder
  • Quantum

Посмотреть видео на сайте Лекториума
Дополнительные материалы

Скачать: Презентация

Лекция 8. Непрерывность бизнеса, резервное копирование и восстановление.

• необходимость
• метрики непрерывности
• методы борьбы с SPOF
• топологии резервного копирования
• дедупликация
• резервное копирование в виртуальной среде

Посмотреть видео на сайте Лекториума
Дополнительные материалы

Скачать: Презентация

Лекция 9. Локальная и удаленная репликация.

• синхронный и асинхронный режим
• методы
• топологии

Посмотреть видео на сайте Лекториума
Дополнительные материалы

Скачать: Презентация

Лекция 10. Безопасность инфраструктуры хранения в облачных датацентров.

• угрозы
• уязвимости
• методы борьбы

Посмотреть видео на сайте Лекториума
Дополнительные материалы

Скачать: Презентация

Лекция 11. Программно определяемые сети (SDN).

• Предпосылки
• История
• Принципы
• Технологии
• Области применения
Дополнительные материалы

Скачать: Презентация

Лекция 12. Управление инфраструктурой хранения и обработки данных.

• Ключевые понятия
• Стандарты управления
• Технологии
• Архитектуры
Дополнительные материалы

Скачать: Презентация

Автор: Roman Brovko

Видеолекции курса Современные технологии разработки ПО.

Лектор: Александр Смаль.

Курс предназначен для краткого знакомства с некоторыми широко распространёнными с технологиями, которые используются при разработке программного обеспечения. В курсе будет рассказано о Linux, скриптовых языках, VCS, XML и многом другом.

Лекция 1. История UNIX систем.

• Создание UNIX.
• Ответвление BSD.
• Коммерческие версии UNIX.
• Возникновение GNU.
• Становление Linux систем.
• Развитие BSD систем.
• Краткая характеристика современных дистрибутивов Linux.

Лекция 2. Файлы и пользователи в Linux.

• Зачем нужен shell?
• Основы работы в bash-e.
• Файлы и файловая система.
• Пользователи и группу.
• Права доступа.

Лекция 3. Работа и программирование в shell-e.

• Процессы
• Маски файлов
• «Одна задача — одна программа».
• Работа с потоками ввода-вывода (stdout, stdin, stderr).
• Перенаправление потоков.
• Создание конвееров.
• Редакторы. Как выйти из vi =).
• Создание скриптов.
• Основы программирования bash: переменные, циклы, условные выражения.

Лекция 4. Регулярные выражения.

• Зачем нужны регулярные выражения?
• Типы регулярных выражений.
• Введение в синтаксис PCRE.
• «Жадные» и не «жадные» регулярные выражения.
• Способы применения регулярных выражений: поиск и замена.

Лекция 5. Язык Perl.

• История.
• Что значит «интерпретируемый язык».
• Основные типы данных.
• Основы синтаксиса.
• Основные операции с числами и строками («.», сравнение строк)
• Основные конструкции (циклы, услоные выражения, switch).
• Регулярные выражения.
• Массивы и хэши.
• Функции.

Лекция 6. Язык Ruby.

• История.
• Области применения.
• Основы синтаксиса.
• Основные типы данных.
• Структуры данных.
• ООП.

Лекция 7. XML.

• Зачем нужны языки разметки?
• Почему именно XML?
• Какие проблемы решаются использованием XML, а какие нет.
• Что такое DOM и SAX?
• XML библиотеки для разных языков программирования.
• Описания XML схем.
• XSLT.
• XPath.

Лекция 8. Системы контроля версий.

• История систем контроля версий.
• Основные понятия.
• CVS, SVN.
• Распределённые системы контроля версий.
• Основные сценарии работы.

Лекция 9. LaTeX.

• WYSISWG.
• История не WYSISWG издательских систем: ROFF, TeX, LaTeX.
• Как TeX обрабатывает документы.
• Математические формулы в TeX.
• Как LaTeX расширяет TeX.
• Основные средства разметки LaTeX.
• Создание презентаций в LaTeX.

Лекция 10. Кодировки текста.

• История появления кодировок.
• Кодировки для кириллического текста.
• Много байтовые кодировки.
• Unicode.
• Передача данных через почтовый протокол: base64.

Лекция 11. Технологии Web-разработки.

• Протокол HTTP.
• CGI.
• DHTML.
• CMF и CMS.

Автор: Roman Brovko