Методы программирования 2: Множества на основе битовых полей

Новости

2015-10-02
- Создан Gitter-чат, в котором можно задавать вопросы про выполнение лабораторных работ
2015-09-25
- ~~Опубликованы видеозаписи с живой демонстрацией Git и Google Test.~~
- Опубликованы слайды с лекций про Git и Google Test.

Цели и задачи

Цель данной работы — разработка структуры данных для хранения множеств с использованием битовых полей, а также освоение таких инструментов разработки программного обеспечения, как система контроля версий Git и фрэймворк для разработки автоматических тестов Google Test.

Предполагается, что перед выполнением работы студенты получают данный проект-шаблон, содержащий следующее:

Интерфейсы классов битового поля и множества (h-файлы)
Готовый набор тестов для каждого из указанных классов
Пример использования класса битового поля и множества для решения задачи поиска простых чисел с помощью алгоритма "Решето Эратосфена"

Выполнение работы предполагает решение следующих задач:

Реализация класса битового поля TBitField согласно заданному интерфейсу.
Реализация класса множества TSet согласно заданному интерфейсу.
Обеспечение работоспособности тестов и примера использования.
Реализация нескольких простых тестов на базе Google Test.
Публикация исходных кодов в личном репозитории на GitHub.

Используемые инструменты

Система контроля версий Git. Рекомендуется использовать один из следующих клиентов на выбор студента:
- Git
- GitHub Desktop
Фреймворк для написания автоматических тестов Google Test. Не требует установки, идет вместе с проектом-шаблоном.
Среда разработки Microsoft Visual Studio (2008 или старше).
Опционально. Утилита CMake для генерации проектов по сборке исходных кодов. Она может быть использована для генерации решения для среды разработки, отличной от Microsoft Visual Studio 2008 или 2010, предоставленных в данном проекте-шаблоне.

Общая структура проекта

Структура проекта:

docs — инструкции по выполнению лабораторной работы, полезные документы.
gtest — библиотека Google Test.
include — директория для размещения заголовочных файлов.
samples — директория для размещения демо-приложений.
sln — директория с файлами решений и проектов для VS 2008 и VS 2010, вложенные директории vc9 и vc10 соответственно.
src — директория с исходными кодами (cpp-файлы).
test — директория с модульными тестами и основным приложением, инициализирующим запуск тестов.
README.md — информация о проекте, которую вы сейчас читаете.
Служебные файлы
- .gitignore — перечень расширений файлов, игнорируемых Git при добавлении файлов в репозиторий.
- CMakeLists.txt — корневой файл для сборки проекта с помощью CMake. Может быть использован для генерации проекта в среде разработки, отличной от Microsoft Visual Studio.
- .travis.yml — конфигурационный файл для системы автоматического тестирования Travis-CI. Тесты, входящие в состав шаблонного проекта, регулярно запускаются на удаленной инфраструктуре.

В решении содержатся следующие модули:

Модуль tbitfield, содержащий реализацию класса битового поля (файлы ./include/tbitfield.h, ./src/tbitfield.cpp). Предполагается, что в ходе выполнения работы реализуются методы класса в файле ./src/tbitfield.cpp, при этом заголовочный файл ./include/tbitfield.h с объявлениями должен оставаться неизменным.
Модуль tset, содержащий реализацию класса множества (файлы ./include/tset.h, ./src/tset.cpp). При выполнении работы так же, как и в случае класса битового поля, разрабатывается только реализация методов класса.
Тесты для классов битовое поле и множество (файлы ./test/test_tbitfield.cpp, ./test/test_tset.cpp).
Пример использования класса битового поля и множества для поиска простых чисел с использованием алгоритма, называемого "Решетом Эратосфена" (файл ./samples/sample_prime_numbers.cpp).

Инструкция по выполнению работы

~~Кроме текстовых инструкций вы также можете обратиться к видеозаписи с демонстрацией основных операций.~~