Содержание
С++, 422 гр., спец. СМ
«Программирование для решения вероятностных задач» и Практикум по СПП
Место и время проведения: среда, первая (ауд. …) и третья (ауд. …) пары.
Преподаватель: Шлемов Александр Юрьевич
(По созданию сайта на 1 паре по средам в сентябре занятия ведет Коробейников А.И.)
Задание на семестр прошлого года.
Сайт
TBD
Программа для поиска экстремума функции
Красивые примеры программ прошлых лет. Еще один
Комментарии к стилю программирования
Минимальные требования к программе с MFC
Примеры на combo-box и графику VS2010 Примеры на combo-box и графику VS2013
Список литературы с описанием методов поиска экстремумов
Задание по STL
STL - это Standard Template Library.
Задание: TBD Список алгоритмов можно найти, например, здесь: http://en.cppreference.com/w/cpp/algorithm
Темы по датам
2.09
- Детеминированный поиск экстремума
9.09
- Стохастический поиск экстемума
16.09
- Библиотека Eigen
23.09
- Шаблонные функции и шаблонные классы
30.09
- STL, структуры данных (vector, list, map, set, …)
- using
- Передача контейнеров в функции и возврат
7.10
- auto
- for (e : v) — цикл по контейнеру
- Идея итератора
- Виды итераторов
- «Специальные» итераторы (back_inserter, …)
- Алгоритмы с итераторами (sort, max_element, copy, iota, …)
14.10
- Еще немного алгоритмов, повторение, обсуждение
- Задачи, обсуждение домашней работы
21.10
- Алгоритмы, параметризованные функцией (std::copy_if, std::sort, etc)
- Функторы, statefull/stateless
- Функции высших порядков
- Утиная типизация, шаблоны и функции
- Примеры реализации функторов с помощью классов
28.10
- std::bind
- std::function, полиморфные функторы реального времени
- lambda-функции, список захвата
11.11
- move(), rvalue references, copy elision
Задание Дореализовать пример из класса — класс-массив с move assignment и move constructor и продемонстрировать на его примере, как работает move и copy elision.
18.11
- RTTI, dynamic_cast
- Представление о сборке мусора (GC)
- Умные указатели (smart pointers): unique_ptr, shared_ptr, weak_ptr, make_shared, make_unique
25.11
- exceptions (исключения)
02.12
- Средства параллелизма C++11 (threads, async, mutex, …), OpenMP
Опционально (темы по согласованию)
- Как перегружать шаблоны (SFINAE, traits, …)
- Регулярные выражения (regex)
- «Как написать полиморфную обертку для шаблона», т.е. как превратить шаблонный полиморфизм в объектно-ориентированный, на примере, допустим std::function
- Что-то из мира boost
- Высокоуровневые контейнеры (stack, deque, priority_queue)
- Что-то еще, что всем интересно, но я забыл
Очевидно, что из этого списка ВСЕ рассказать не получится, поэтому я предлагаю вам выбрать самим и сообщить мне ближе к делу
Задания
- Сайт Требования: несколько страниц, меню, адекватный соверменный код, работать во всех разумных браузерах, использовать JavaScript
- Поиск экстремума I Требования: должен работать случайны и детерминированный поиск, на разумных тестовых случаях. Структура программы и оптимальность реализации несущественны (на этом этапе). Существенно выбрать алгоритм и разобраться с ним
- VCS «Система контроля версий». Описание ниже.
- Поиск экстремума II Требования: на этом этапе должна быть готова структура классов и шаблонов, должна быть возможность вызвать метод от любой функции и получить результат и всю траекторию поиска (для визуализации)
- Умный указатель Описание ниже
- Поиск экстремума III Требования: законченная программа с графическим интерфейсом. Можно выбирать функцию для оптимизации и метод. Для каждого метода задавать параметры. Для двумерной функции рисуется карта и траектория поиска. Для других измерений — график зависимости значения от номера шага (для особых случаев типа дискретной оптимизации визуализация может отличаться).
Задача: Система контоля версий
Пусть у нас имеется некоторый документ (хранимый, например, в виде большой строки) и мы можем выполнять над ним некоторые операции. Мы хотим иметь возможность отменить произвольный набор операций и вернуться к предыдущему состоянию, но при этом мы не хотим хранить каждую ревизию документа (т.е. результат применения каждой операции).
Предлагается следующая идея. Давайте хранить исходное состояние документа и набор всех совершенных операций. Когда мы хотим вернуться к предыдущему состоянию, мы сначала откатываемся до начального состояния документа, а затем, последовательно применяя операции, доходим до нужного состояния.
Начальный вариант задания: доступны операции get() — получить текущее состояние, checkout(n) — вернуться к результату n-й операции и apply(F) — применить команду. Операция REDO (отмена отмены) нереализована. Также необходимо сделать несколько Юнит-тестов (нпример, gtest) для проверки корректности
Усложнение 1: Класс документа сделать шаблонным (по типу хранимого документа, пусть он может быть не только строкой) и добавить make_функцию, оборачивающую любую переменную в VCS
Усложнение 2: Хранить не только начальное состояние, но и набор промежуточных. При откате выбирать «ближайшее снизу» сохраненное состояние и двигаться дальше от него. Реализовать дополнительные методы для контроля за сохраненными состояниями (сохранить текущее, удалить все, старше определенного времени, …) Указание использовать std::map для хранения состояний
Усложнение 3: Для каждого состояния вычислять и хранить хеш (контрольную сумму). При восстановлении сверять хеш, и при несовпадении падать с ошибкой (выбрасывать исключение). Хеш-функцию сделать параметром шаблона, при этом в качестве дефолтного значения использовать std::hash
Усложение 4: Хранить историю всех состояний документа в виде дерева. Для каждого состояния хранить предыдущее состояние и операцию. Реализовать возможность отката к любому состоянию по его номеру. Реализовать вывод дерева или его части человекочитаемом виде
Усложение 5: (для 3+4) Реализовать возможность отката к любому состоянию по хешу документа (если хеш неоднозначен, то ошибка)
Усложнение 6: (для 4) Реализовать операцию rebase, когда произвольный набор операций переносится с одной ветки дерева на другую
Если кому-то все равно слишком легко, у меня есть еще варианты расширения задачи. Обращайтесь!
Задача: Умный указатель
Все просто. Сделать свой шаблонный класс умных указателей. Для тех, кто чувствует себя неуверенно — unique_ptr. Для более уверенных — shared_ptr. Для самых уверенных — shared_prt + weak_ptr. Требования: Реализация должна быть максиально оптимальной как по времени работы основных операций, так и по памяти, т.е. не должно хранитья лишней информации или делаться лишних обращений. Реализовывать все методы не обязательно, достаточно основных. move и =&& должны поддерживаться, разумеется.
Усложнение 1. Сделать возможным задавать пользовательский deleter. При этом указатель с делитером и без должны быть корректными специализациями класса и лишней информации быть не должно (т.е. не надо реализовывать указатель без делитера как указатель с путым делитером, это неоптимально. Используйте шаблоны и специализации)
Усложнение 2. Сделать указатели полноценно thread-safe, аналогично оригинальным, т.е. при одновременном обращении из разных потоков к одному и тому же объекту, используя РАЗНЫЕ экземпляры указателеля, не должно возникать конфликтов (например, при инкременте счетчика). ПРОТЕСТИРОВАТЬ!
Усложнение 3. Реализовать аналог make_shared и make_unique. Определить их для произвольного числа аргументов (использовать variadic templates) и передавать аргументы в конструктор, используя forward.
Посещаемость
2.09 | 9.09 | 16.09 | 23.09 | 30.09 | 07.10 | 14.10 | 21.10 | 28.10 | 11.11 | 18.11 | 25.11 | 02.12 | |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Жорникова Полина | + | + | + | + | + | + | + | + | + | + | + | + | |
Белоусов Юрий | + | + | + | + | + | + | + | + | + | + | + | + | + |
Пимахов Кирилл | + | + | + | + | + | + | + | + | + | + | + | + | + |
Коврыга Лера | + | + | + | + | + | + | + | + | + | + | + | + | + |
Черниговская Мария | + | + | + | + | + | + | + | + | + | + | + | + | + |
Явейн Анна | + | + | + | + | + | + | + | + | |||||
Грязнов Святослав | + | + | + | + | + | + |
Друзья, касаемо посещаемсти и работы в классе у меня нет претензий. Но убедительная просьба не опаздывать на первую пару! Кхе-кхе!
Личный зачет
Сайт | Методы оптимизации | VCS | Методы оптимизации с классами | smart_ptr | Методы оптимизации с интерфейсом | ИТОГ | |
---|---|---|---|---|---|---|---|
Жорникова Полина | + | + | + | ||||
Белоусов Юрий | + | + | + | + | + | ||
Пимахов Кирилл | + | + | |||||
Коврыга Лера | + | ||||||
Черниговская Мария | +/2 | ||||||
Явейн Анна | + | ||||||
Грязнов Святослав | + |
C++ advanced
Примерные темы
- Сложное наследование
- RTTI, dynamic_cast
- Исключения
- STL: string, vector, map и другие контейнеры, STL-алгоритмы, потоки (iostream), etc
- Шаблоны (templates)
- Библиотека Eigen
- ??? (У нас демократия, предлагайте)
Литература (и другие источники)
- The C++ Programming Language (4th Edition) Новое издание легендарной книги от создателя языка. Моя любимая книга, я буду рассказывать по ней.
- http://cplusplus.com/ Всякая инфа по языку и документация по использованию встроенной библиотеки с примерами. Коротко и удобно.
- http://en.cppreference.com/w/ Аналогично предыдущему ресурсу.
- C++11 Standard latest draft Последний черновой вариант1) предыдущего (реально, актуального) стандарта C++. Чтение не очень захватывающее, документ пропитан духом формализма. Но позволяет точно ответить на вопрос «А как это должно быть на самом деле?»
- C++14 Standard latest draft Последний черновой вариант новейшего стандарта C++. Обратите внимание, что далеко не все популярные компиляторы поддерживают новейший стандарт целиком.
- C++11/14 compiler and library shootout Сводная таблица по поддержке новых возможностей различными компиляторами.
- MSDN C++ Позволяет ответить на вопрос «А как же оно на самом деле работает» применительно к майкрософтовской реализации C++ (Visual C++). В целом, удобная онлайн-справка по языку и Visual Studio IDE. Некоторыми признается вообще лучшей документацией по языку.
- "The home of Standard C++ on the web" Много материалов по новому и новейшему стандарту, сжато и информативно
- Предлагайте свои источники, у нас демократия
Занятия по C++ advanced прошлых лет
- 24/09/2014. Множественное наследование. Виртуальный базовый класс. Приведение типа static_cast.
- 01/10/2014. Отступление про R-value reference &&, move, конструкторы и оператор= с перемещением. Namespace.
- 08/10/2014. Приведение типа const_cast (заодно про mutable, volatile), reinterpret_cast, dynamic_cast. RTTI (typeid, dynamic_cast), начало.
- 15/10/2014. RTTI (typeid, dynamic_cast): пример c shape. Vector с move и без move. Начало про исключения. (assert)
- 16/10/2014. Исключения (как выбрасывать, как ловить, переброска и пр.). Упражнение.
- 22/10/2014. set_terminate. Исключения в конструкторах, «голые» и «одетые» указатели, идиома RAII, unique_ptr, shared_ptr, weak_ptr. Стандартные классы исключений exception и пр.
- 29/10/2014. Строки string. Использование for(auto: a), свой класс, позволяющий это делать. Шаблоны: компиляция программы с шаблонами (инстанцирование шаблона), шаблон шаблонного класса вместе с определением функций. Пример шаблонного массива фиксированной длины (сами писали), способ реализации и требования к типу. Пример с «ленивым» массивом (holder).
- 05/11/2014. Использование ::. Шаблоны: компиляция программы с шаблонами (зависимые имена, инстанцирование шаблона). Параметр шаблона для задания области видимости, использование typename внутри шаблона, шаблон в качестве параметра шаблона (этого не было). Паттерны с traits (bear_corner).
- 06/11/2014. Приведение типов для шаблонных классов. Специализация шаблонов (пример Sortable). Паттерны с traits. Пример с разной функцией copy для Matrix. (Переопределение операций в шаблонных классах (пример box, шаблонное и нешаблонное) - только упомянула про проблему).
- 12/11/2014. Шаблоны: метапрограммирование на этапе компиляции (static assert для ошибок на этапе компиляции - не было. Шаблонная реализация быстрых операций с матрицами. Шаблонные функции, выведение параметров шаблона, специализация - не было). Потоковый ввод-вывод: общее устройство, флаги форматирования, форматированный вывод, манипуляторы. Cоздание своих манипуляторов. fstream (режимы открытия, ошибочные состояния, getline, get, копирование файлов: посимвольное, построковое, поблочное, через streambuf и rdbuf()).
- 19/11/2014. Потоковый ввод-вывод: stringstream (ostringstream, istringstream, чтение файла в массив строк). Домашнее задание - разбор файл с табличными данными. STL: обзор контейнеров с трудоемкостью операций. (Моделирование распределений в Cplusplus 11 - самостоятельно со ссылкой на wiki). STL: иерархия концепций итераторов. Общая структура алгоритмов STL (умение самостоятельно написать реализацию алгоритма на примере copy).
- 20/11/2014. STL: итераторы прямой и обратный, итераторы вставки, итераторы для потоков ввода-вывода. .
- 06/11/2013. STL: иерархия концепций итераторов, итераторы прямой и обратный, итераторы вставки, итераторы для потоков ввода-вывода. Общая структура алгоритмов STL (умение самостоятельно написать реализацию алгоритма на примере copy и transform). Функциональные объекты, использование for_each для суммирования.
- 13/11/2013. Функциональные объекты (использование лямбда-функций). Модифицирующие и немодифицирующие алгоритмы. for_each vs transform. Функциональные объекты: стандартные функц.объекты из <functional>. STL: читаем <algorithm>, алгоритмы типа replace (replace_if, replace_copy, replace_copy_if), find, transform, generate.
- 13/11/2013. STL: алгоритмы типа inner_product (самост.реализация). STL: алгоритмы поиска, сортировки, манипуляций. Операции с множествами.
- 20/11/2013. STL: адаптеры стек, очередь, очередь с приоритетами; ассоциативные контейнеры set, multiset, map, multimap. Контейнеры bitset, valarray. Разное: limits, complex.
========================================
Материалы в виде архивов к занятиям в прошлые годы
- (08/09/2010). Множественное наследование. Виртуальный базовый класс. «Виртуальные конструкторы».
- (16/09/2009). RTTI (typeid, dynamic_cast), вспомнили static_cast, const_cast, reinterpret_cast. Вспомнили assert. Исключения - начало.
- (23/09/2009). Исключения (как выбрасывать, как ловить), исключения в конструкторах, «голые» указатели, set_unexpected, set_terminate, auto_ptr.
- (25/09/2013). cleanup, «голые» указатели, auto_ptr, unique_ptr, shared_ptr, weak_ptr.
- (30/09/2009). Окончание темы про исключения («одетые» указатели, стандартные классы исключений). Строки (string). Шаблоны - начало.
- (07/10/2009). Шаблоны: компиляция программы с шаблонами (зависимые имена, инстанцирование (конкретизация) шаблона), параметр шаблона для задания области видимости, использование typename внутри шаблона, шаблон в качестве параметра шаблона, специализация шаблонов.
- (14/10/2009 09/10/201316/10/2013). Шаблоны: специализация шаблонов, паттерны с traits (идея с использованием typedef для задания разным типам одинаковых псевдонимов) и policy, псевдорекурсия при наследовании от шаблонного класса без типо-зависимых элементов, метапрограммирование на этапе компиляции, функции-друзья шаблонные/нешаблонные.
- (21/10/2009). Немного о vector из STL: size, capacity, reserve и пр. Потоковый ввод-вывод: общее устройство, флаги форматирования, форматированный вывод, манипуляторы.
- (28/10/2009). Потоковый ввод-вывод: создание своих манипуляторов, fstream (режимы открытия, ошибочные состояния, getline, get, копирование файлов: посимвольное, построковое, поблочное, через streambuf и rdbuf()), stringstream (в частности, разбор строки на слова). Домашнее задание - разбор файл с табличными данными.
- (11/11/2009 13/11/2013). STL: общая структура, обзор контейнеров с трудоемкостью операций, иерархия концепций итераторов, итераторы прямой и обратный, итераторы вставки, итераторы для потоков ввода-вывода. Общая структура алгоритмов STL (умение самостоятельно написать реализацию алгоритма на примере copy и transform).
- (18/11/2009). STL: продолжение про алгоритмы на примере replace, replace_if, replace_copy, replace_copy_if. Также - алгоритм типа remove (принцип неудаления элементов после remove, разница между last и end). Функциональные объекты, стандартные функц.объекты из <functional>. Суммирование элементов контейнера с помощью for_each. Алгоритмы работы с числовыми последовательностями (accumulate, inner_product, partial_sum), алгоритмы для работы с множествами (объединение, пересечение и пр.)
- (25/11/2009 20/11/2013). STL: адаптеры стек, очередь, очередь с приоритетами; ассоциативные контейнеры set, multiset, map, multimap. Алгоритмы перестановки, поиска, сортировки и пр.: из книги Эккеля manipulations.cpp, SearchReplace.cpp, Nstring.h
- (02/12/2009). STL: Алгоритмы сравнения, бин.поиска, сортировки, удаления и пр. Контейнеры bitset, valarray. Разное: limits, complex.
—-