Программирование на С++ основной и продвинутый потоки — различия между версиями

Материал из Public ATP Wiki
Перейти к: навигация, поиск
(Новая страница: «= Общие сведения = * Семестр: 1 (первый курс курс) * Форма контроля: дифференцированный заче…»)
 
(→‎План курса)
 
(не показано 6 промежуточных версий этого же участника)
Строка 19: Строка 19:
 
|-  
 
|-  
 
! №
 
! №
−
! Тема
+
! Введение
 
|-
 
|-
  
−
|1|| Асимптотические обозначения: O, Ω, Θ. Независимость от стартового индекса.
+
|1|| Общие слова и немного истории
 +
|-
 +
|2|| Знакомство с компилятором, первая программа
 +
|-
 +
|3|| Основные типы и операции над ними
 +
|-
 +
|4|| Объявления, определения и области видимости
 +
|-
 +
|5|| Выражения (expressions) и операторы
 +
|-
 +
|6|| Управляющие инструкции (control statements)
 +
|-
 +
|7|| Ошибки компиляции, ошибки времени выполнения и UB
 +
|}
 +
{|  class="wikitable"
 +
|-
 +
! №
 +
! Модификаторы типов
 +
|-
  
 +
|1|| Указатели
 +
|-
 +
|2|| Виды памяти
 +
|-
 +
|3|| Массивы
 +
|-
 +
|4|| Функции
 +
|-
 +
|5|| Ссылки
 +
|-
 +
|6|| Константы
 +
|-
 +
|7|| Приведения типов
 +
|}
 +
{|  class="wikitable"
 +
|-
 +
! №
 +
! Основы ООП. Инкапсуляция
 
|-
 
|-
  
−
|2|| Сумма на отрезке в статическом массиве: префиксные суммы.
+
|1|| Классы и структуры
 +
|-
 +
|2|| Модификаторы доступа, инкапсуляция
 +
|-
 +
|3|| Конструкторы и деструкторы
 +
|-
 +
|4|| Правило трех
 +
|-
 +
|5|| Перегрузка операторов
 +
|-
 +
|6|| Константные методы
 +
|-
 +
|7|| Статические поля и методы
 +
|-
 +
|8|| Пользовательские приведения типов
 +
|-
 +
|9|| Указатели на члены
 +
|-
 +
|10|| Перечисления (енумы)
 +
|}
 +
{|  class="wikitable"
 +
|-
 +
! №
 +
! Наследование
 +
|-
  
 +
|1|| Приватное, публичное и защищенное наследование
 +
|-
 +
|2|| Видимость и доступность членов класса при наследовании
 +
|-
 +
|3|| Размещение объектов в памяти и порядок вызова конструкторов при наследовании
 +
|-
 +
|4|| Приведения типов при наследовании
 +
|-
 +
|5|| Множественное наследование
 +
|-
 +
|6|| Виртуальное наследование
 +
|}
 +
{|  class="wikitable"
 +
|-
 +
! №
 +
! Шаблоны
 
|-
 
|-
  
−
|3|| Проверка вхождения числа в отсортированный массив: бинарный поиск.
+
|1|| Идея шаблонов и простые примеры
 +
|-
 +
|2|| Перегрузка шаблонных функций
 +
|-
 +
|3|| Специализации шаблонов
 +
|-
 +
|4|| Нетиповые параметры шаблонов
 +
|-
 +
|5|| Простейшие compile-time вычисления
 +
|-
 +
|6|| Зависимые имена
 +
|-
 +
|7|| Простейшие метафункции и type_traits
 +
|-
 +
|8|| Шаблоны с переменным количеством аргументов (variadic templates)
 +
|}
  
 +
{|  class="wikitable"
 +
|-
 +
! №
 +
! Полиморфизм и виртуальные функции
 
|-
 
|-
−
 
+
|1|| Идея полиморфизма и виртуальных функций
−
|4|| Структура данных стек: реализация на указателях, использование std::stack.
+
|-
−
 
+
|2|| Более сложные примеры с виртуальными функциями
 
|-
 
|-
−
 
+
|3|| Абстрактные классы и чисто виртуальные функции
−
|5|| Поиск ближайшего меньшего/большего слева/справа в статическом массиве.
 
−
 
 
 
|-
 
|-
−
 
+
|4|| Виртуальный деструктор
−
|6|| Поддержка минимума в стеке.
 
−
 
 
 
|-
 
|-
−
 
+
|5|| RTTI и dynamic_cast
−
|7|| Реализация очереди на двух стеках.
 
−
 
 
 
|-
 
|-
−
 
+
|6|| Реализация механизма виртуальных функций
−
|8|| Поддержка минимума в очереди.
 
−
 
 
 
|-
 
|-
−
 
+
|7|| Виртуальные функции при множественном наследовании
−
|9|| Проверка правильности скобочной последовательности с несколькими типами скобок.
 
−
 
 
 
|-
 
|-
−
 
+
|8|| Некоторые нюансы, связанные с виртуальными функциями
−
|10|| Доказательство формулы: log(n!) = Θ(n log n).
+
|}
−
 
+
{| class="wikitable"
 +
|-
 +
! №
 +
! Исключения
 
|-
 
|-
−
 
+
|1|| Идея и базовые примеры использования исключений
−
|11|| Нижняя оценка на число сравнений в сортировке сравнениями.
 
−
 
 
 
|-
 
|-
−
 
+
|2|| Разница между RE и исключениями
−
|12|| Сортировка слиянием (Merge Sort).
 
−
 
 
 
|-
 
|-
−
 
+
|3|| Более подробно о механизме бросания и ловли исключений
−
|13|| Поиск числа инверсий в массиве.
 
−
 
 
 
|-
 
|-
−
 
+
|4|| Идиома RAII, исключения в конструкторах и деструкторах
−
|14|| Нерекурсивная реализация сортировки слиянием.
 
−
 
 
 
|-
 
|-
−
 
+
|5|| Безопасность относительно исключений, спецификации исключений
−
|15|| Быстрая сортировка (Quick Sort). Асимптотика — б/д.
+
|}
−
 
+
{| class="wikitable"
 +
|-
 +
! №
 +
! Контейнеры и итераторы
 
|-
 
|-
−
 
+
|1|| Понятие контейнера, обзор контейнеров
−
|16|| Поиск k-й порядковой статистики с выбором случайного пивота (Quick Select). Асимптотика — б/д.
 
−
 
 
 
|-
 
|-
−
 
+
|2|| Понятие итератора, виды итераторов
−
|17|| Детерминированный алгоритм поиска k-й порядковой статистики за O(n), где n — длина массива.
 
−
 
 
 
|-
 
|-
−
 
+
|3|| Реализация и правильное использование итераторов
−
|18|| Детерминированный алгоритм быстрой сортировки за O(n log n), где n — длина массива.
 
−
 
 
 
|-
 
|-
−
 
+
|4|| Output-итераторы и итераторы над потоками
−
|19|| Стабильная сортировка подсчётом. Сортировка пар чисел.
 
−
 
 
 
|-
 
|-
−
 
+
|5|| Внутреннее устройство std::vector
−
|20|| Цифровая сортировка (LSD).
 
−
 
 
 
|-
 
|-
−
 
+
|6|| Внутреннее устройство std::deque
−
|21|| Двоичная куча: определение и представление в массиве. Требование кучи.
 
−
 
 
 
|-
 
|-
−
 
+
|7|| Внутреннее устройство std::list
−
|22|| Операции siftUp и siftDown с доказательством корректности.
 
−
 
 
 
|-
 
|-
−
 
+
|8|| Внутреннее устройство std::map
−
|23|| Выражение insert, getMin, extractMin и decreaseKey через siftUp и siftDown.
 
−
 
 
 
|-
 
|-
−
 
+
|9|| Внутреннее устройство std::unordered_map
−
|24|| Построение кучи (heapify) за линейное время (сходимостью ряда можно пользоваться б/д).
+
|}
−
 
+
{| class="wikitable"
 +
|-
 +
! №
 +
! Аллокаторы и управление памятью
 
|-
 
|-
−
 
+
|1|| Идея и базовое применение аллокаторов
−
|25|| Сортировка кучей с привлечением O(1) дополнительной памяти (Heap Sort). Несуществование кучи (основанной на сравнениях), обрабатывающей insert и extractMin за O(1).
 
−
 
 
 
|-
 
|-
−
 
+
|2|| Примеры нестандартных аллокаторов, понятие allocator-awareness
−
|26|| Технические сложности и их преодоление для операции decreaseKey в куче.
 
−
 
 
 
|-
 
|-
−
 
+
|3|| Структура allocator_traits
−
|27|| Удаление из кучи по значению.
 
−
 
 
 
|-
 
|-
−
 
+
|4|| Перегрузка операторов new и delete
−
|28|| Удаление из кучи по указателю.
 
−
 
 
 
|-
 
|-
−
 
+
|5|| Выравнивания и битовые поля
−
|29|| Биномиальное дерево, биномиальная куча: определение.
 
−
 
 
 
|-
 
|-
−
 
+
|6|| Scoped-аллокаторы
−
|30|| Операции merge, insert, getMin, extractMin и decreaseKey в биномиальной куче.
 
−
 
 
 
|-
 
|-
−
 
+
|7|| Полиморфные аллокаторы
−
|31|| Амортизационный анализ, учётное время работы: определение.
+
|}
−
 
+
{| class="wikitable"
 +
|-
 +
! №
 +
! Move-семантика и rvalue-ссылки
 
|-
 
|-
−
 
+
|1|| Мотивировка move-семантики и волшебная функция std::move
−
|32|| Метод монеток (бухгалтерский учёт).
 
−
 
 
 
|-
 
|-
−
 
+
|2|| Move-конструкторы и move-assignment операторы
−
|33|| Структура данных вектор, реализация на массиве и оценка асимптотики методом монеток.
 
−
 
 
 
|-
 
|-
−
 
+
|3|| Реализация функции std::move
−
|34|| Метод потенциалов.
 
−
 
 
 
|-
 
|-
−
 
+
|4|| Формальное определение lvalue и rvalue
−
|35|| Вставка в биномиальной куче в отсутствие других операций, применение метода потенциалов.
 
−
 
 
 
|-
 
|-
−
 
+
|5|| Особенности rvalue-ссылок
−
|36|| Sparse Table: модельная задача, построение за O(n log n), ответ на запрос за O(1).
 
−
 
 
 
|-
 
|-
−
 
+
|6|| Проблема perfect forwarding
−
|37|| Дерево отрезков: модельная задача. Обработка запросов с доказательством времени работы.
 
−
 
 
 
|-
 
|-
−
 
+
|7|| Реализация функции std::forward
−
|38|| Дерево отрезков: двоичный спуск, поиск k-го нуля на отрезке массива за O(log n).
 
−
 
 
 
|-
 
|-
−
 
+
|8|| Expired values (xvalues), RVO и copy elision
−
|39|| Дерево отрезков, отложенные операции: присвоение константы на отрезке, операция push.
 
−
 
 
 
|-
 
|-
−
 
+
|9|| Функция move_if_noexcept
−
|40|| Количество чисел на отрезке, значения которых лежат в отрезке: Fractional Cascading.
+
|}
−
 
+
{| class="wikitable"
 +
|-
 +
! №
 +
! Вывод типов
 
|-
 
|-
−
 
+
|1|| Ключевое слово auto
−
|41|| Персистентный массив.
 
−
 
 
 
|-
 
|-
−
 
+
|2|| Ключевое слово decltype и конструкция decltype(auto)
−
|42|| Персистентное дерево отрезков.
 
−
 
 
 
|-
 
|-
−
 
+
|3|| Class template argument deduction (CTAD)
−
|43|| Количество чисел на отрезке, значения которых лежат в отрезке: решение с персистентным деревом отрезков.
 
−
 
 
 
|-
 
|-
−
 
+
|4|| Structured bindings
−
|44|| Динамическое дерево отрезков.
+
|}
−
 
+
{| class="wikitable"
 +
|-
 +
! №
 +
! Умные указатели
 
|-
 
|-
−
 
+
|1|| Класс std::unique_ptr
−
|45|| Онлайн vs. оффлайн: сжатие координат.
 
−
 
 
 
|-
 
|-
−
 
+
|2|| Класс std::shared_ptr
−
|46|| Онлайн vs. оффлайн: дерево поиска оффлайн.
 
−
 
 
 
|-
 
|-
−
 
+
|3|| Функции make_unique и make_shared
−
|47|| Онлайн vs. оффлайн: количество чисел на отрезке, значения которых лежат в отрезке.
 
−
 
 
 
|-
 
|-
−
 
+
|4|| Класс std::weak_ptr
−
|48|| Дерево Фенвика: классическая задача, операции update и getSum.
 
−
 
 
 
|-
 
|-
−
 
+
|5|| Проблема нестандартного аллокатора и удалителя в shared_ptr
−
|49|| Обобщение дерева Фенвика на б´oльшие размерности. Изменение асимптотики.
 
−
 
 
 
|-
 
|-
−
 
+
|6||Структура enable_shared_from_this и паттерн CRTP
−
|50|| Обратное дерево Фенвика: максимум на отрезке и изменение (увеличение) в точке (update — без реализации).
+
|}
−
 
+
{| class="wikitable"
 +
|-
 +
! №
 +
! Лямбда-функции
 
|-
 
|-
−
 
+
|1|| Идея и базовое использование лямбда-функций
−
|51|| Дерево Фенвика деревьев Фенвика.
 
−
 
 
 
|-
 
|-
−
 
+
|2|| Списки захвата в лямбда-функциях
−
|52|| Дерево поиска: определения и операции (без реализации) find, insert, erase, а также опциональные merge и split.
 
−
 
 
 
|-
 
|-
−
 
+
|3|| Лямбда-функции как функциональные объекты
−
|53|| Наивное дерево поиска, обработка операций.
 
−
 
 
 
|-
 
|-
−
 
+
|4|| Класс std::function
−
|54|| AVL-дерево: определение.
+
|}
−
 
+
{| class="wikitable"
 +
|-  
 +
! №
 +
! Стирание типов, юнионы
 
|-
 
|-
−
 
+
|1|| Идиома type erasure и класс std::any
−
|55|| Оценка глубины AVL-дерева на n вершинах.
 
−
 
 
 
|-
 
|-
−
 
+
|2||Решение проблемы с нестандартным deleter’ом для shared_ptr
−
|56|| Устранение дисбаланса в AVL-дереве для случая ∆(a) = −2.
 
−
 
 
 
|-
 
|-
−
 
+
|3|| Юнионы
−
|57|| AVL-дерево: реализация операций insert и erase.
 
−
 
 
 
|-
 
|-
−
 
+
|4|| Small objects optimization и empty base optimization
−
|58|| Splay-дерево: определение и практическая значимость.
 
−
 
 
 
|-
 
|-
−
 
+
|5|| Реализация std::function
−
|59|| Splay-дерево: операции zig, zig-zig и zig-zag, операция splay.
 
−
 
 
 
|-
 
|-
−
 
+
|6|| Класс std::variant и его реализация
−
|60|| Амортизированное время работы операции splay с помощью метода потенциалов.
 
−
 
 
 
|-
 
|-
−
 
+
|7|| Функция std::launder
−
|61|| Splay-дерево: реализация insert, erase и find, связь с операцией splay, оценка времени работы.
+
|}
−
 
+
{| class="wikitable"
 +
|-  
 +
! №
 +
! Шаблонное метапрограммирование, SFINAE и концепты
 
|-
 
|-
−
 
+
|1|| Основные примитивы шаблонного метапрограммирования
−
|62|| B-дерево: определение и практическая значимость.
 
−
 
 
 
|-
 
|-
−
 
+
|2|| Идиома SFINAE и структура std::enable_if
−
|63|| Оценка глубины B-дерева на n ключах при фиксированном параметре t.
 
−
 
 
 
|-
 
|-
−
 
+
|3|| Метафункции для проверки наличия методов в классе
−
|64|| Реализация операции insert в B-дереве.
 
−
 
 
 
|-
 
|-
−
 
+
|4|| Реализация move_if_noexcept
−
|65|| Реализация операции erase в B-дереве.
 
−
 
 
 
|-
 
|-
−
 
+
|5|| Реализация is_base_of
−
|66|| Декартово дерево: определение и теорема о глубине (б/д).
 
−
 
 
 
|-
 
|-
−
 
+
|6|| Реализация common_type
−
|67|| Реализация операций merge и split в декартовом дереве.
 
−
 
 
 
|-
 
|-
−
 
+
|7|| Ограничения, ключевое слово requires
−
|68|| Выражение insert и erase в декартовом дереве через merge и split.
 
−
 
 
 
|-
 
|-
−
 
+
|8|| Концепты
−
|69|| Декартово дерево по неявному ключу: в массиве вставить, удалить элемент, узнать сумму на отрезке.
+
|}
−
 
+
{| class="wikitable"
 +
|-
 +
! №
 +
! Compile-time вычисления
 
|-
 
|-
−
 
+
|1|| Constexpr-функции и переменные
−
|70|| Красно-чёрное дерево: определение.
 
−
 
 
 
|-
 
|-
−
 
+
|2|| Новые возможности constexpr в C++20
−
|71|| Оценка глубины красно-чёрного дерева на n ключах.
 
−
 
 
 
|-
 
|-
−
 
+
|3|| Consteval и constinit
−
|72|| Реализация операции insert в красно-чёрном дереве.
 
−
 
 
 
|-
 
|-
−
 
+
|4|| Метаконтейнер typelist
−
|73|| Реализация операции erase в красно-чёрном дереве.
 
−
 
 
 
|-
 
|-
−
 
+
|5|| Реализация qiucksort для метаконтейнера
−
|74|| Сравнительный анализ различных реализаций дерева поиска: наивное, AVL-, splay-, B-, декартово и красно-чёрное дерево.
 
−
 
 
 
|}
 
|}
  

Текущая версия на 18:06, 4 декабря 2022

Общие сведения

  • Семестр: 1 (первый курс курс)
  • Форма контроля: дифференцированный зачет

Важные ссылки

  • Регистрация на курс (доступ для физтех-аккаунтов)
  • Материалы курсa (доступ для физтех-аккаунтов)
  • Чат курса
  • Таблица с оценками

Требования

  • Физтех-почта (домен phystech.edu)
  • Аккаунт на GitHub
  • Ноутбук на занятиях

План курса

№ Введение
1 Общие слова и немного истории
2 Знакомство с компилятором, первая программа
3 Основные типы и операции над ними
4 Объявления, определения и области видимости
5 Выражения (expressions) и операторы
6 Управляющие инструкции (control statements)
7 Ошибки компиляции, ошибки времени выполнения и UB
№ Модификаторы типов
1 Указатели
2 Виды памяти
3 Массивы
4 Функции
5 Ссылки
6 Константы
7 Приведения типов
№ Основы ООП. Инкапсуляция
1 Классы и структуры
2 Модификаторы доступа, инкапсуляция
3 Конструкторы и деструкторы
4 Правило трех
5 Перегрузка операторов
6 Константные методы
7 Статические поля и методы
8 Пользовательские приведения типов
9 Указатели на члены
10 Перечисления (енумы)
№ Наследование
1 Приватное, публичное и защищенное наследование
2 Видимость и доступность членов класса при наследовании
3 Размещение объектов в памяти и порядок вызова конструкторов при наследовании
4 Приведения типов при наследовании
5 Множественное наследование
6 Виртуальное наследование
№ Шаблоны
1 Идея шаблонов и простые примеры
2 Перегрузка шаблонных функций
3 Специализации шаблонов
4 Нетиповые параметры шаблонов
5 Простейшие compile-time вычисления
6 Зависимые имена
7 Простейшие метафункции и type_traits
8 Шаблоны с переменным количеством аргументов (variadic templates)
№ Полиморфизм и виртуальные функции
1 Идея полиморфизма и виртуальных функций
2 Более сложные примеры с виртуальными функциями
3 Абстрактные классы и чисто виртуальные функции
4 Виртуальный деструктор
5 RTTI и dynamic_cast
6 Реализация механизма виртуальных функций
7 Виртуальные функции при множественном наследовании
8 Некоторые нюансы, связанные с виртуальными функциями
№ Исключения
1 Идея и базовые примеры использования исключений
2 Разница между RE и исключениями
3 Более подробно о механизме бросания и ловли исключений
4 Идиома RAII, исключения в конструкторах и деструкторах
5 Безопасность относительно исключений, спецификации исключений
№ Контейнеры и итераторы
1 Понятие контейнера, обзор контейнеров
2 Понятие итератора, виды итераторов
3 Реализация и правильное использование итераторов
4 Output-итераторы и итераторы над потоками
5 Внутреннее устройство std::vector
6 Внутреннее устройство std::deque
7 Внутреннее устройство std::list
8 Внутреннее устройство std::map
9 Внутреннее устройство std::unordered_map
№ Аллокаторы и управление памятью
1 Идея и базовое применение аллокаторов
2 Примеры нестандартных аллокаторов, понятие allocator-awareness
3 Структура allocator_traits
4 Перегрузка операторов new и delete
5 Выравнивания и битовые поля
6 Scoped-аллокаторы
7 Полиморфные аллокаторы
№ Move-семантика и rvalue-ссылки
1 Мотивировка move-семантики и волшебная функция std::move
2 Move-конструкторы и move-assignment операторы
3 Реализация функции std::move
4 Формальное определение lvalue и rvalue
5 Особенности rvalue-ссылок
6 Проблема perfect forwarding
7 Реализация функции std::forward
8 Expired values (xvalues), RVO и copy elision
9 Функция move_if_noexcept
№ Вывод типов
1 Ключевое слово auto
2 Ключевое слово decltype и конструкция decltype(auto)
3 Class template argument deduction (CTAD)
4 Structured bindings
№ Умные указатели
1 Класс std::unique_ptr
2 Класс std::shared_ptr
3 Функции make_unique и make_shared
4 Класс std::weak_ptr
5 Проблема нестандартного аллокатора и удалителя в shared_ptr
6 Структура enable_shared_from_this и паттерн CRTP
№ Лямбда-функции
1 Идея и базовое использование лямбда-функций
2 Списки захвата в лямбда-функциях
3 Лямбда-функции как функциональные объекты
4 Класс std::function
№ Стирание типов, юнионы
1 Идиома type erasure и класс std::any
2 Решение проблемы с нестандартным deleter’ом для shared_ptr
3 Юнионы
4 Small objects optimization и empty base optimization
5 Реализация std::function
6 Класс std::variant и его реализация
7 Функция std::launder
№ Шаблонное метапрограммирование, SFINAE и концепты
1 Основные примитивы шаблонного метапрограммирования
2 Идиома SFINAE и структура std::enable_if
3 Метафункции для проверки наличия методов в классе
4 Реализация move_if_noexcept
5 Реализация is_base_of
6 Реализация common_type
7 Ограничения, ключевое слово requires
8 Концепты
№ Compile-time вычисления
1 Constexpr-функции и переменные
2 Новые возможности constexpr в C++20
3 Consteval и constinit
4 Метаконтейнер typelist
5 Реализация qiucksort для метаконтейнера

Оценивание

Оценка по курсу состоит из нескольких частей:

  1. Тесты
  2. Контесты
  3. Практические проекты
  4. Лабораторная работа

Тесты

  • Небольшие тесты на 10 минут в начале каждого занятия
  • Вопросы по материалам прошлого занятия
  • Для прохождения нужен phystech.edu-аккаунт
  • За каждый тест - 10 баллов.

Контесты

  • Набор задач с автоматической проверкой тестирующей системой Я.Контест (нужен phystech.edu-аккаунт)
  • Всего 6 тестов - после каждой темы базового блока
  • Срок решения - 2 недели
  • За каждый контест - 10 баллов
  • Списывание детектируется и наказуемо!

Практические проекты

  • 2 проекта - консольное приложение (после ООП) и серверное приложение (после Сети-2)
  • Работа над кодом в несколько итераций на GitHub (нужен аккаунт)
  • Срок работы - 2 недели + 1 неделя на каждую следующую итерацию
  • Список тем проектов будет позднее
  • Оценка за проект: зачет / незачет + до 2 доп. баллов (wow-эффект)

Лабораторная работа

  • Анализ данных с помощью Pandas и Matplotlib
  • Выдается после “Инструменты визуализации”
  • Срок работы - 2 недели
  • Оценка - 10 баллов
  • Является блокирующей! Для получения зачета за курс необходимо набрать хотя бы 1 балл

Команда курса

  • Преподаватели:
    • Мещерин Иллья
Источник — «http://wiki.atp-fivt.org/index.php?title=Программирование_на_С%2B%2B_основной_и_продвинутый_потоки&oldid=1511»