Перейти к содержанию

С++, 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, …)

  1. using
  2. Передача контейнеров в функции и возврат

7.10
- auto

  1. for (e : v) — цикл по контейнеру
  2. Идея итератора
  3. Виды итераторов
  4. “Специальные” итераторы (back_inserter, …)
  5. Алгоритмы с итераторами (sort, max_element, copy, iota, …)

14.10
- Еще немного алгоритмов, повторение, обсуждение

  1. Задачи, обсуждение домашней работы

21.10
- Алгоритмы, параметризованные функцией (std::copy_if, std::sort, etc)

  1. Функторы, statefull/stateless
  2. Функции высших порядков
  3. Утиная типизация, шаблоны и функции
  4. Примеры реализации функторов с помощью классов

28.10
- std::bind

  1. std::function, полиморфные функторы реального времени
  2. lambda-функции, список захвата

11.11
- move(), rvalue references, copy elision
Задание Дореализовать пример из класса — класс-массив с move assignment и move constructor и продемонстрировать на его примере, как работает move и copy elision.

18.11
- RTTI, dynamic_cast

  1. Представление о сборке мусора (GC)
  2. Умные указатели (smart pointers): unique_ptr, shared_ptr, weak_ptr, make_shared, make_unique

25.11
- exceptions (исключения)

02.12
- Средства параллелизма C

++

11 (threads, async, mutex, …), OpenMP

[Исходник примера из класса](http://pastebin.com/TWLn3bGe)

Опционально (темы по согласованию)

  1. Как перегружать шаблоны (SFINAE, traits, …)
  2. Регулярные выражения (regex)
  3. “Как написать полиморфную обертку для шаблона”, т.е. как превратить шаблонный полиморфизм в объектно-ориентированный, на примере, допустим std::function
  4. Что-то из мира boost
  5. Высокоуровневые контейнеры (stack, deque, priority_queue)
  6. Что-то еще, что всем интересно, но я забыл

Очевидно, что из этого списка ВСЕ рассказать не получится, поэтому я предлагаю вам выбрать самим и сообщить мне ближе к делу

Задания

  1. Сайт Требования: несколько страниц, меню, адекватный соверменный код, работать во всех разумных браузерах, использовать JavaScript
  2. Поиск экстремума I Требования: должен работать случайны и детерминированный поиск, на разумных тестовых случаях. Структура программы и оптимальность реализации несущественны (на этом этапе). Существенно выбрать алгоритм и разобраться с ним
  3. VCS “Система контроля версий”. Описание ниже.
  4. Поиск экстремума II Требования: на этом этапе должна быть готова структура классов и шаблонов, должна быть возможность вызвать метод от любой функции и получить результат и всю траекторию поиска (для визуализации)
  5. Умный указатель Описание ниже
  6. Поиск экстремума 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
  • ??? (У нас демократия, предлагайте)

Литература (и другие источники)

  1. The C++ Programming Language (4th Edition) Новое издание легендарной книги от создателя языка. Моя любимая книга, я буду рассказывать по ней.
  2. http://cplusplus.com/ Всякая инфа по языку и документация по использованию встроенной библиотеки с примерами. Коротко и удобно.
  3. http://en.cppreference.com/w/ Аналогично предыдущему ресурсу.
  4. C++11 Standard latest draft Последний черновой вариант1 предыдущего (реально, актуального) стандарта C

++

. Чтение не очень захватывающее, документ пропитан духом формализма. Но позволяет точно ответить на вопрос “А как это должно быть на самом деле?” 5. C++14 Standard latest draft Последний черновой вариант новейшего стандарта C

++

. Обратите внимание, что далеко не все популярные компиляторы поддерживают новейший стандарт целиком. 6. C++11/14 compiler and library shootout Сводная таблица по поддержке новых возможностей различными компиляторами. 7. MSDN C++ Позволяет ответить на вопрос “А как же оно на самом деле работает” применительно к майкрософтовской реализации C++ (Visual C++). В целом, удобная онлайн-справка по языку и Visual Studio IDE. Некоторыми признается вообще лучшей документацией по языку. 8. "The home of Standard C++ on the web" Много материалов по новому и новейшему стандарту, сжато и информативно 9. Предлагайте свои источники, у нас демократия=)

Занятия по C++ advanced прошлых лет

  1. 24/09/2014. Множественное наследование. Виртуальный базовый класс. Приведение типа static_cast.
  2. 01/10/2014. Отступление про R-value reference &&, move, конструкторы и оператор= с перемещением. Namespace.
  3. 08/10/2014. Приведение типа const_cast (заодно про mutable, volatile), reinterpret_cast, dynamic_cast. RTTI (typeid, dynamic_cast), начало.
  4. 15/10/2014. RTTI (typeid, dynamic_cast): пример c shape. Vector с move и без move. Начало про исключения. (assert)
  5. 16/10/2014. Исключения (как выбрасывать, как ловить, переброска и пр.). Упражнение.
  6. 22/10/2014. set_terminate. Исключения в конструкторах, “голые” и “одетые” указатели, идиома RAII, unique_ptr, shared_ptr, weak_ptr. Стандартные классы исключений exception и пр.
  7. 29/10/2014. Строки string. Использование for(auto: a), свой класс, позволяющий это делать. Шаблоны: компиляция программы с шаблонами (инстанцирование шаблона), шаблон шаблонного класса вместе с определением функций. Пример шаблонного массива фиксированной длины (сами писали), способ реализации и требования к типу. Пример с “ленивым” массивом (holder).
  8. 05/11/2014. Использование ::. Шаблоны: компиляция программы с шаблонами (зависимые имена, инстанцирование шаблона). Параметр шаблона для задания области видимости, использование typename внутри шаблона, шаблон в качестве параметра шаблона (этого не было). Паттерны с traits (bear_corner).
  9. 06/11/2014. Приведение типов для шаблонных классов. Специализация шаблонов (пример Sortable). Паттерны с traits. Пример с разной функцией copy для Matrix. (Переопределение операций в шаблонных классах (пример box, шаблонное и нешаблонное) - только упомянула про проблему).
  10. 12/11/2014. Шаблоны: метапрограммирование на этапе компиляции (static assert для ошибок на этапе компиляции - не было. Шаблонная реализация быстрых операций с матрицами. Шаблонные функции, выведение параметров шаблона, специализация - не было). Потоковый ввод-вывод: общее устройство, флаги форматирования, форматированный вывод, манипуляторы. Cоздание своих манипуляторов. fstream (режимы открытия, ошибочные состояния, getline, get, копирование файлов: посимвольное, построковое, поблочное, через streambuf и rdbuf()).
  11. 19/11/2014. Потоковый ввод-вывод: stringstream (ostringstream, istringstream, чтение файла в массив строк). Домашнее задание - разбор файл с табличными данными. STL: обзор контейнеров с трудоемкостью операций. (Моделирование распределений в Cplusplus 11 - самостоятельно со ссылкой на wiki). STL: иерархия концепций итераторов. Общая структура алгоритмов STL (умение самостоятельно написать реализацию алгоритма на примере copy).
  12. 20/11/2014. STL: итераторы прямой и обратный, итераторы вставки, итераторы для потоков ввода-вывода. .
  1. 06/11/2013. STL: иерархия концепций итераторов, итераторы прямой и обратный, итераторы вставки, итераторы для потоков ввода-вывода. Общая структура алгоритмов STL (умение самостоятельно написать реализацию алгоритма на примере copy и transform). Функциональные объекты, использование for_each для суммирования.
  2. 13/11/2013. Функциональные объекты (использование лямбда-функций). Модифицирующие и немодифицирующие алгоритмы. for_each vs transform. Функциональные объекты: стандартные функц.объекты из . STL: читаем , алгоритмы типа replace (replace_if, replace_copy, replace_copy_if), find, transform, generate.
  3. 13/11/2013. STL: алгоритмы типа inner_product (самост.реализация). STL: алгоритмы поиска, сортировки, манипуляций. Операции с множествами.
  4. 20/11/2013. STL: адаптеры стек, очередь, очередь с приоритетами; ассоциативные контейнеры set, multiset, map, multimap. Контейнеры bitset, valarray. Разное: limits, complex.

Материалы в виде архивов к занятиям в прошлые годы

  1. (08/09/2010). Множественное наследование. Виртуальный базовый класс. “Виртуальные конструкторы”.
  2. (16/09/2009). RTTI (typeid, dynamic_cast), вспомнили static_cast, const_cast, reinterpret_cast. Вспомнили assert. Исключения - начало.
  3. (23/09/2009). Исключения (как выбрасывать, как ловить), исключения в конструкторах, “голые” указатели, set_unexpected, set_terminate, auto_ptr.
  4. (25/09/2013). cleanup, “голые” указатели, auto_ptr, unique_ptr, shared_ptr, weak_ptr.
  5. (30/09/2009). Окончание темы про исключения (“одетые” указатели, стандартные классы исключений). Строки (string). Шаблоны - начало.
  6. (07/10/2009). Шаблоны: компиляция программы с шаблонами (зависимые имена, инстанцирование (конкретизация) шаблона), параметр шаблона для задания области видимости, использование typename внутри шаблона, шаблон в качестве параметра шаблона, специализация шаблонов.
  7. (14/10/2009 09/10/201316/10/2013). Шаблоны: специализация шаблонов, паттерны с traits (идея с использованием typedef для задания разным типам одинаковых псевдонимов) и policy, псевдорекурсия при наследовании от шаблонного класса без типо-зависимых элементов, метапрограммирование на этапе компиляции, функции-друзья шаблонные/нешаблонные.
  8. (21/10/2009). Немного о vector из STL: size, capacity, reserve и пр. Потоковый ввод-вывод: общее устройство, флаги форматирования, форматированный вывод, манипуляторы.
  9. (28/10/2009). Потоковый ввод-вывод: создание своих манипуляторов, fstream (режимы открытия, ошибочные состояния, getline, get, копирование файлов: посимвольное, построковое, поблочное, через streambuf и rdbuf()), stringstream (в частности, разбор строки на слова). Домашнее задание - разбор файл с табличными данными.
  10. (11/11/2009 13/11/2013). STL: общая структура, обзор контейнеров с трудоемкостью операций, иерархия концепций итераторов, итераторы прямой и обратный, итераторы вставки, итераторы для потоков ввода-вывода. Общая структура алгоритмов STL (умение самостоятельно написать реализацию алгоритма на примере copy и transform).
  11. (18/11/2009). STL: продолжение про алгоритмы на примере replace, replace_if, replace_copy, replace_copy_if. Также - алгоритм типа remove (принцип неудаления элементов после remove, разница между last и end). Функциональные объекты, стандартные функц.объекты из . Суммирование элементов контейнера с помощью for_each. Алгоритмы работы с числовыми последовательностями (accumulate, inner_product, partial_sum), алгоритмы для работы с множествами (объединение, пересечение и пр.)
  12. (25/11/2009 20/11/2013). STL: адаптеры стек, очередь, очередь с приоритетами; ассоциативные контейнеры set, multiset, map, multimap. Алгоритмы перестановки, поиска, сортировки и пр.: из книги Эккеля manipulations.cpp, SearchReplace.cpp, Nstring.h
  13. (02/12/2009). STL: Алгоритмы сравнения, бин.поиска, сортировки, удаления и пр. Контейнеры bitset, valarray. Разное: limits, complex.

  1. за окончательный вариант стандарта ISO требует весьма круглую сумму денег, но последний черновик отличается от окончательно варианта в исключительно мелких деталях (если не ошибаюсь, двумя опечатками), поэтому простые смертные обычно довольствуются этим самым черновиком. Впрочем, существуют и другие пути получения финальной версии стандарта ↩