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

  1. Детеминированный поиск экстремума

9.09

  1. Стохастический поиск экстемума

16.09

  1. Библиотека Eigen

23.09

  1. Шаблонные функции и шаблонные классы

30.09

  1. STL, структуры данных (vector, list, map, set, …)
  2. using
  3. Передача контейнеров в функции и возврат

7.10

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

14.10

  1. Еще немного алгоритмов, повторение, обсуждение
  2. Задачи, обсуждение домашней работы

21.10

  1. Алгоритмы, параметризованные функцией (std::copy_if, std::sort, etc)
  2. Функторы, statefull/stateless
  3. Функции высших порядков
  4. Утиная типизация, шаблоны и функции
  5. Примеры реализации функторов с помощью классов

28.10

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

11.11

  1. move(), rvalue references, copy elision

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

18.11

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

25.11

  1. exceptions (исключения)

02.12

  1. Средства параллелизма C++11 (threads, async, mutex, …), OpenMP

Исходник примера из класса

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

  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. Функциональные объекты: стандартные функц.объекты из <functional>. STL: читаем <algorithm>, алгоритмы типа 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). Функциональные объекты, стандартные функц.объекты из <functional>. Суммирование элементов контейнера с помощью 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 требует весьма круглую сумму денег, но последний черновик отличается от окончательно варианта в исключительно мелких деталях (если не ошибаюсь, двумя опечатками), поэтому простые смертные обычно довольствуются этим самым черновиком. Впрочем, существуют и другие пути получения финальной версии стандарта
study/fall2015/4cpp_pract.txt · Последнее изменение: 2015/12/15 14:48 — ash
Наверх
CC Attribution-Noncommercial-Share Alike 4.0 International
Driven by DokuWiki Recent changes RSS feed Valid CSS Valid XHTML 1.0