В течение семестра каждый учащийся должен успешно пройти как минимум три курса. Например, если в основной программе их два, то необходимо выбрать какой-нибудь из спецкурсов.
Знания проверяются в первую очередь с помощью домашних заданий — экзамены и контрольные проводятся только по некоторым предметам.
Первый семестр
Обязательные
Алгоритмы и структуры данных, часть 1
01 Сложность и модели вычислений. Анализ учетных стоимостей (начало)
02 Анализ учетных стоимостей (окончание)
03 Алгоритмы Merge-Sort и Quick-Sort
04 Порядковые статистики. Кучи (начало)
05 Кучи (окончание)
06 Хеширование
07 Деревья поиска (начало)
08 Деревья поиска (продолжение)
09 Деревья поиска (окончание). Система непересекающихся множеств
10 Задачи RMQ и LCA
11 Структуры данных для геометрического поиска
12 Задача о динамической связности в ненаправленном графе
Архитектура компьютера и операционные системы
01 UNIX и программирование на языке С: командная строка, управление процессами, каналы, сигналы. Реализация оболочки командной строки.
02 Ассемблер x86: арифметика, переходы, условия и вызовы функций. Стек, перемещение вверх по стеку.
03 Линковка программ и формат ELF. Динамическая линковка.
04 Понятие контекста и потока исполнения. Реализация легковесных потоков.
05 Вытесняющая многозадачность: поддержка со стороны процессора x86 и реализация процессов в ядре UNIX.
06 Многоядерная архитектура: когерентность кешей и модели памяти. Примитивы синхронизации в многопоточных программах.
07 Планирование процессов на одном ядре и на многих ядрах.
08 Внешняя память: жесткие диски и твердотельные накопители. Принципы работы файловых систем.
09 Виртуализация: аппаратная и программная. Двоичная трансляция.
Обучение языку C++, часть 1
С++ — мощный язык с богатым наследием. Тем, кто только ступил на путь освоения этого языка, очень просто заблудиться в изобилии техник и приёмов, созданных за последние 30 лет. Курс учит "Modern C++" — современному подмножеству языка (стандарты 11, 14 и 17). Много внимания уделяется инструментам и библиотекам — вещам которые не являются частью языка, но без которых не получится построить большой и сложный проект.
01 Введение в С++.
02 Константы. Указатели и ссылки. Передача аргументов в функцию.
03 Классы.
04 Динамическое управление памятью.
05 Переменные, указатели и ссылки.
06 Управление памятью, умные указатели, RAII.
07 Стандартная библиотека шаблонов.
08 Наследование и виртуальные функции.
09 Обработка ошибок.
10 Паттерны проектирования.
11 Пространства имен Move‑семантика Perfect forwarding.
12 Представление структур и классов в памяти. Выравнивание данных. Указатели на члены/методы класса. Variadic templates.
Второй семестр
Обязательные
Алгоритмы и структуры данных, часть 2
01 Обход в ширину. Обход в глубину (начало)
02 Обход в глубину (продолжение)
03 Обход в глубину (окончание). 2-разрезы
04 Поиск кратчайших путей (начало)
05 Поиск кратчайших путей (продолжение)
06 Минимальные остовные деревья
07 Минимальные разрезы. Поиск подстрок (начало)
08 Поиск подстрок (продолжение)
09 Поиск подстрок (окончание)
10 Суффиксные деревья (начало)
11 Суффиксные деревья (окончание). Суффиксные массивы (начало)
12 Суффиксные массивы (окончание)
13 Длиннейшие общие подстроки. Приближенный поиск подстрок.
Обучение языку C++, часть 2
Вторая часть курса по С++, в которой разбираются продвинутые темы и возможности языка.
01 Многопоточное программирование. Синхронизация потоков с использованием мьютексов и условных переменных.
02 Атомарные переменные. Модель памяти С++. Примеры lock-free структур данных.
03 Продвинутые техники мета-программирования в С++. Метафункции, SFINAE, концепты.
04 Конкурентное программирование, взаимодействие с сетью.
05 Архитектура llvm. Работа с синтаксическим деревом разбора С++. Разработка инструментов для анализа С++ кода.
На выбор
Theory and Practice of Concurrency
Курс посвящен конкурентным системам и задачам в самом широком понимании: от уровня конкуренции ядер процессора за запись в одну ячейку памяти до распределенных систем, которые хотят отказоустойчиво и согласованно реплицировать свое состояние между несколькими серверами.
01 https://gitlab.com/Lipovsky/shad-tpcc-course-2019/blob/master/lectures/syllabus.md
или
Язык Go
01 Введение. Программа курса. Отчётность по курсу, критерии оценки. Философия дизайна. if, switch, for. Hello, world. Command line arguments. Word count. Animated gif. Fetching URL. Fetching URL concurrently. Web server. Tour of go. Local IDE setup. gofmt. goimports. linting.
02 Базовые конструкции языка. names, declarations, variables, assignments. type declarations. packages and files. scope. Zero value. Выделение памяти. Стек vs куча. Basic data types. Constants. Composite data types. Arrays. Slices. Maps. Structs. JSON. text/template. string и []byte. Работа с unicode. Unicode replacement character. Функции. Функции с переменным числом аргументов. Анонимные функции. Ошибки.
03 Методы. Value receiver vs pointer receiver. Embedding. Method value. Encapsulation. Интерфейсы. Интерфейсы как контракты. io.Writer, io.Reader и их реализации. sort.Interface. error. http.Handler. Интерфейсы как перечисления. Type assertion. Type switch. The bigger the interface, the weaker the abstraction. Обработка ошибок. panic, defer, recover. errors.{Unwrap,Is,As}. fmt.Errorf. %w.
04 Горутины и каналы. clock server. echo server. Размер канала. Блокирующее и неблокирующее чтение. select statement. Channel axioms. time.After. time.NewTicker. Pipeline pattern. Cancellation. Parallel loop. sync.WaitGroup. Обработка ошибок в параллельном коде. errgroup.Group. Concurrent web crawler. Concurrent directory traversal.
05 Продвинутое тестирование. Subtests. testing.B. (T).Logf. (T).Skipf. (T).FailNow. testing.Short(), testing flags. Генерация моков. testify/{require,assert}. testify/suite. Test fixture. Интеграционные тесты. Goroutine leak detector. TestingMain. Coverage. Сравнение бенчмарков.
06 Продвинутое тестирование. Subtests. testing.B. (T).Logf. (T).Skipf. (T).FailNow. testing.Short(), testing flags. Генерация моков. testify/{require,assert}. testify/suite. Test fixture. Интеграционные тесты. Goroutine leak detector. TestingMain. Coverage. Сравнение бенчмарков.
07 Package context. Passing request-scoped data. http middleware. chi.Router. Request cancellation. Advanced concurrency patterns. Async cache. Graceful server shutdown. context.WithTimeout. Batching and cancellation.
08 database/sql, sqlx, работа с базами данных, redis.
09 Reflection. reflect.Type and reflect.Value. struct tags. net/rpc. encoding/gob. sync.Map. reflect.DeepEqual.
10 Пакет io, реализации Reader и Writer из стандартной библиотеки. Low-level programming. unsafe. Package binary. bytes.Buffer. cgo, syscall.
11 Архитектура GC. Write barrier. Stack growth. GC pause. GOGC. sync.Pool. Шедулер горутин. GOMACPROCS. Утечка тредов.
12 Go tooling. pprof. CPU and Memory profiling. Кросс-компиляция. GOOS, GOARCH. CGO_ENABLED=0. Build tags. go modules. godoc. x/analysis. Code generation.
13 Полезные библиотеки. CLI applications with cobra. Protobuf and GRPC. zap logging.
Третий семестр
Обязательные
Алгоритмы во внешней памяти
Курс знакомит студентов с основными принципами построения алгоритмов для работы с данными, которые не помещаются в оперативную память компьютера.
01 Алгоритмы во внешней памяти.
02 Cache-oblivious алгоритмы.
03 Алгоритмы потоковой обработки данных.
Распределённые системы
Рекомендуемые спецкурсы
Стойкость криптографических систем
01 Основные подходы и принципы современной криптографии. Модель противника, формализация понятия стойкости, задача оценки стойкости и сопутствующие проблемы, разделение на примитивы и протоколы, этапы "жизни" криптографической системы.
02 Конфиденциальность. Бытовые определения конфиденциальности, подходы к формализации (теоретико-информационная модель противника, модели KR, PR, LOR, ROR, IND, CPA, CCA), симметричная система шифрования, применение теоретико-сложностных сведений для определения соотношения между моделями. Соотношения между базовыми моделями противника для оценки стойкости систем шифрования.
03 Подходы к построению систем шифрования. Построение с нуля. Конструкции на основе блочных шифров, определение блочного шифра, основные характеристики, подходы к построению и свойства. Модели PRP и PRF. Парадокс задачи о днях рождения. Лемма о соотношении стойкости в моделях PRF и PRP.
04 Режимы шифрования. Основные режимы шифрования: ECB, CBC, CFB, OFB, CTR. Основные эксплуатационные свойства. Стойкость CTR в LOR-CPA, нестойкость ECB в LOR-CPA. Нестойкость базовых режимов в CCA-моделях.
05 Целостность. Определение понятия целостности. Подходы к формализации (модель UF-CMA, модели на основе задачи различения, модель PRF). Коды аутентификации сообщений и функции выработки имитовставки. Конструкции на основе блочных шифров: CBC-MAC, XCBC, TMAC, OMAC. Уязвимые режимы.
06 Хэш-функции. Определение, основные свойства, подходы к построению, формализация и сопутствующие проблемы. Примеры применения хэш-функций: хэширование паролей, извлечение энтропии. Построение коллизий и прообраза из множества малой мощности.
07 Схемы HMAC, KDF, PRF, DRNG. Схема HMAC, основные шаги получения оценки стойкости. Диверсификация ключа и принцип разделения ключей, схемы KDF и PRF. Псевдослучайный генератор, схемы DRNG.
08 Нагрузка на ключ. Проблема нагрузки на ключ. Основные методы уменьшения нагрузки на ключ: внешнее и внутреннее преобразования ключа. Схемы parallel и serial re-keying, основные свойства. Ключевое дерево. Внутренняя смена ключа и режим CTR-ACPKM.
09 Шифрование с имитозащитой. Формулировка задачи. Общие конструкции (EtA, AtE, A&E) и их свойства. Примеры уязвимых режимов обеспечения конфиденциальности и целостности с помощью одного ключа. AEAD-режимы шифрования: GCM, MGM.
10 Защищенный канал связи. Понятие защищенного канала связи: типы каналов, основные свойства (целостность и конфиденциальность потока данных). Примеры уязвимых протоколов. Протокол Record TLS 1.3.
Четвёртый семестр
На выбор
Theory and Practice of Concurrency
Курс посвящен конкурентным системам и задачам в самом широком понимании: от уровня конкуренции ядер процессора за запись в одну ячейку памяти до распределенных систем, которые хотят отказоустойчиво и согласованно реплицировать свое состояние между несколькими серверами.
01 https://gitlab.com/Lipovsky/shad-tpcc-course-2019/blob/master/lectures/syllabus.md
или
Язык Go
01 Введение. Программа курса. Отчётность по курсу, критерии оценки. Философия дизайна. if, switch, for. Hello, world. Command line arguments. Word count. Animated gif. Fetching URL. Fetching URL concurrently. Web server. Tour of go. Local IDE setup. gofmt. goimports. linting.
02 Базовые конструкции языка. names, declarations, variables, assignments. type declarations. packages and files. scope. Zero value. Выделение памяти. Стек vs куча. Basic data types. Constants. Composite data types. Arrays. Slices. Maps. Structs. JSON. text/template. string и []byte. Работа с unicode. Unicode replacement character. Функции. Функции с переменным числом аргументов. Анонимные функции. Ошибки.
03 Методы. Value receiver vs pointer receiver. Embedding. Method value. Encapsulation. Интерфейсы. Интерфейсы как контракты. io.Writer, io.Reader и их реализации. sort.Interface. error. http.Handler. Интерфейсы как перечисления. Type assertion. Type switch. The bigger the interface, the weaker the abstraction. Обработка ошибок. panic, defer, recover. errors.{Unwrap,Is,As}. fmt.Errorf. %w.
04 Горутины и каналы. clock server. echo server. Размер канала. Блокирующее и неблокирующее чтение. select statement. Channel axioms. time.After. time.NewTicker. Pipeline pattern. Cancellation. Parallel loop. sync.WaitGroup. Обработка ошибок в параллельном коде. errgroup.Group. Concurrent web crawler. Concurrent directory traversal.
05 Продвинутое тестирование. Subtests. testing.B. (T).Logf. (T).Skipf. (T).FailNow. testing.Short(), testing flags. Генерация моков. testify/{require,assert}. testify/suite. Test fixture. Интеграционные тесты. Goroutine leak detector. TestingMain. Coverage. Сравнение бенчмарков.
06 Concurrency with shared memory. sync.Mutex. sync.RWMutex. sync.Cond. atomic. sync.Once. Race detector. Async cache. Работа с базой данных. database/sql. sqlx.
07 Package context. Passing request-scoped data. http middleware. chi.Router. Request cancellation. Advanced concurrency patterns. Async cache. Graceful server shutdown. context.WithTimeout. Batching and cancellation.
08 database/sql, sqlx, работа с базами данных, redis.
09 Reflection. reflect.Type and reflect.Value. struct tags. net/rpc. encoding/gob. sync.Map. reflect.DeepEqual.
10 Пакет io, реализации Reader и Writer из стандартной библиотеки. Low-level programming. unsafe. Package binary. bytes.Buffer. cgo, syscall.
11 Архитектура GC. Write barrier. Stack growth. GC pause. GOGC. sync.Pool. Шедулер горутин. GOMACPROCS. Утечка тредов.
12 Go tooling. pprof. CPU and Memory profiling. Кросс-компиляция. GOOS, GOARCH. CGO_ENABLED=0. Build tags. go modules. godoc. x/analysis. Code generation.
13 Полезные библиотеки. CLI applications with cobra. Protobuf and GRPC. zap logging.
или
Базы данных
01 Интерфейсы современных баз данных: реляционные, ключ-значение, документные, графовые. Реляционная алгебра и язык SQL.
02 Работа с диском в классических реляционных СУБД: страницы, пул страниц, вытеснение из пула.
03 Выполнение SQL запросов: разбор выражения, планирование, исполнение. Интерпретация и кодогенерация с помощью LLVM.
04 Индексы в реляционных СУБД: типы индексов, способы хранения, использование в запросах.
05 Транзакции: аббревеатура ACID, уровни изоляции, реализация транзакций через блокировки и MVCC.
06 Восстановление при аварии: журнал, чекпойнты, алгоритм ARIES.
07 Хранение данных методом Log-Structured Merge Tree.
08 Поколоночные СУБД: преимущества, особенности, алгоритмы сжатия данных.
09 Распределённые СУБД: шардирование, транзакции, выполнение запросов.
10 СУБД, распологающиеся в основной памяти. Структуры данных для индексов в памяти.
или
Компьютерные сети
01 Введение в сетевые технологии. История возникновения сетей, сетевые протоколы, организация сетевого взаимодействия в одноранговой сети и объединение одноранговых сетей друг с другом.
02 Transport. Сетевая модель OSI/ISO. TCP, установление сетевого соединения, сравнение TCP и UDP. Анализ tcpdump – графики bytes in fly, retransmits. Методы управления потоком данных в TCP сессии. Разные типы TCP сессий и управление полосой передаваемых данных в пакетных сетях.
03 Routing. Понятие маршрутизации в сетях. Статическая и динамическая маршрутизация. Основы динамической маршрутизации. Протокол динамической маршрутизации - OSPF. Дистанционно-векторные протоколы маршрутизации. Обзор протокола маршрутизации BGP - типы сообщений, атрибуты BGP, выбор оптимального маршрута в BGP.
04 Как работает Интернет: BGP и DNS. Маршрутизация в сети Интернет. Обзор протокола DNS.
05 Сети в больших дата-центрах. Особенности архитектуры сетей дата-центров. Требования к сетям дата-центров. Архитектура CLOS для сетей дата-центров.
06 Задержки в сетях. Особенности построения больших магистральных сетей. Причины возникновения задержки при передаче данных по магистральным сетям.
07 Масштабирование и доступность сервисов интернета. Технологии балансировки нагрузки и сервисная архитектура.
08 MPLS и SR, Network Programmability. Технологии MPLS и Segment Routing для построения магистральных сетей. Назначение технологии MPLS, протоколы используемые для обмена метками.
09 Принципы работы сетевых устройств. Архитектура маршрутизатора, особенности обработки сетевого трафика внутри сетевых устройств.
10 Облака. Основы программно-определяемых сетей - протоколы, используемые для построения программно определяемых сетей. Интеграция платформ виртуализации и сетевой инфраструктуры.
или
Криптографические протоколы
01 Базовые идеи асимметричной криптографии. Основное отличие асимметричной криптографии от симметричной. Основные идеи: протокол выработки общего ключа, шифрование с открытым ключом, электронная подпись (решаемые задачи, интуитивное понимание свойств безопасности). Конкретные криптографические схемы: протокол Диффи-Хеллмана, схемы шифрования Эль-Гамаля и RSA, подписи Эль-Гамаля и RSA. Фундаментальная проблема асимметричных схем -- доверие к открытому ключу.
02 Стойкость основных схем асимметричной криптографии. Формальное определение стойкости: модели UF-CMA, IND-CPA, DLP, CDH, DDH. Соотношения между ними. Стойкость схемы шифрования Эль-Гамаля. Нестойкость схемы подписи RSA без использования хэш-функции.
03 Дополнительные сведения об асимметричной криптографии. Подпись Лэмпарта, схема Меркля. Атака DSKS.
04 Алгебраические и теоретико-числовые основы асимметричной криптографии. Конечные группы, циклические группы, порядок элемента группы. Задача дискретного логарифмирования (DLP). Мультипликативные группы конечных полей. Начальные сведения об эллиптических кривых.
05 Эллиптические кривые. Теорема Хассе. Сложение точек эллиптической кривой. Группа точек эллиптической кривой. Схема подписи ГОСТ Р 34.10-2012.
06 Дискретное логарифмирование. Алгоритмы дискретного логарифмирования (Ро-метод Полларда, метод согласования, метод Полига-Хеллмана, метод исчисления индексов).
07 Технология PKI. Основные принципы и понятия инфраструктуры открытых ключей (PKI). Сертификат, УЦ, CRL, OCSP, пространство доверия.
08 Протокол TLS. История протокола TLS. Структура протокола, основные принципы работы. Криптонаборы протокола TLS на основе российских криптографических алгоритмов.
09 Основы построения AKE-протоколов. Понятие AKE протокола. Целевые свойства. Основные подходы к построению.
10 Безопасное хранение ключей. Задача безопасного использования закрытых ключей. Ключевые носители, неизвлекаемые ключи. Проблема присутствия противника в канале, протоколы семейства PAKE.
11 Основные концепции технологии блокчейн. Задача согласованного децентрализованного взаимодействия. Основные концепции понятия безопасности. Подходы к обеспечению безопасности.
12 Базовые принципы квантовых технологий и их применения в криптографии
