Задания

Л.р.№3. Последовательные контейнеры
Измерить время выполнения следующих операций:
  1. В изначально пустой вектор вставить 100 тыс. элементов путем вставки в начало.
  2. В изначально пустой вектор вставить 100 тыс. элементов путем вставки в конец.
  3. В изначально пустой вектор вставить 100 тыс. элементов путем вставки в случайную позицию. Случайная позиция генерируется каждый раз заново при вставке очередного элемента.
  4. Из вектора, содержащего 100 тыс. элементов, удалить все элементы путем многократного удаления первого элемента.
  5. Из вектора, содержащего 100 тыс. элементов, удалить все элементы путем многократного удаления последнего элемента.
  6. Из вектора, содержащего 100 тыс. элементов, удалить все элементы путем многократного удаления элемента из случайной позиции. Случайная позиция генерируется каждый раз заново при удалении очередного элемента.
  7. В векторе, содержащем 100 тыс. элементов, произвести 100 тыс. модификаций, каждый раз выбирая для модификации случайный элемент (вернее, его номер).
Те же эксперименты провести с контейнерами deque и list.
 
Результаты экспериментов объяснить и занести в следующую таблицу:
  вставка
удаление изменение
 vector       
 deque      
 list      

(вам понадобится три таких таблицы - для каждого "места" вставки - начала, конца, случайной позиции)

Примечания
  1. Не все операции, время выполнения которых надо измерить, реализованы в виде методов классов vector и deque. Поэтому некоторые из них нужно будет написать самостоятельно (например, для вставки в начало вектора можно воспльзоваться методом insert.).
  2. Итератор, указывающий на i-ый элемент вектора или деки, можно получить, прибавив i к begin-итератору:
typedef std::deque<int> deq;
deq d(100);
deq::iterator i = d.begin();
i = i + 10;            // теперь i указывает на 10-ый элемент!

     3. Для точного измерения времени можно использовать функцию clock() из time.h (http://www.cplusplus.com/reference/clibrary/ctime/)

Контрольные вопросы

  1. В каких ячейках ваших таблиц получились наиболее "ужасные" значения? (неприемлемо большие)
  2. Выводы? При каком "паттерне" использования контейнера лучше всего будет работать вектор, при каком - deque, и при каком - list?
  3. Какой контейнер лучше всего работает в каждой из следующих ситуаций:
    1. Много вставок и удалений с обоих концов контейнера?
    2. Много вставок и удалений с одного конца?
    3. Много вставок и удалений в разные позиции в середине массива?
  4. Оцените асимптотическую сложность каждой операции с контейнерами, с которой Вы экспериментировали.

Л.р.№4 Ассоциативные контейнеры

Создать класс "Студент" (ФИО, ср.балл + другие поля по желанию).
Написать для старосты группы программу для управления множеством студентов в его группе со следующими возможностями:
  • просмотреть список всех студентов;
  • добавить нового студентв;
  • удалить одного из студентов.
Студентов хранить в контейнере multimap или multiset. Ключ - фамилия (только фамилия). Записывать данные на диск не требуется.
При добавлении нового студента в случае, если студент с такой фамилией уже имеется - вывести пользователю предупреждение и уточнить, действительно ли он хочет добавить однофамильца.
Для удаления студента пользователь вводит его фамилию. В случае наличия однофамильцев ему предлагают выбрать, кого из них удалять.

Контрольные вопросы

  1. Как проверить наличие одновфамильцев? Как предоставить пользователю возможность удалить лишь одного выбранного им человека из списка однофамильцев?
  2. Чем отличается set от map?
  3. Какие основные операции (методы ) поддерживают ассоциативные контейнеры?
  4. В чем отличие между set и multiset, map и multimap? Продемонстрировать на примере кода.
  5. Какие типы данных могут быть ключом в ассоциативном контейнере, а какие-нет?
  6. От чего зависит порядок, в котором будут обходиться элементы set'а при обходе их в цикле по итераторам от begin() до end()?
  7. Что представляет собой структура std::pair и как она используется при работе с ассоциативными контейнерами?
  8. Если в Вашей реализации STL авторы забыли реализовать контейнер map, то как для тех же целей приспособить set?
  9. Как устроены контейнеры map и set? Какова асимптотическая сложность операций поиска, добавления и удаления элемента? Почему?

Л.р.№5 Адаптеры

Заполнить объектами класса "студент" из предыдущей лабораторной очередь с приоритетами (студентов можно вводить с клавиатуры, можно задать в коде).
Извлечь из очереди и вывести на экран список 10-ти студентов с наибольшим баллом.

Контрольные вопросы

  1. Почему очередь с приоритетом - "адаптер" (а непросто контейнер)? Какие Вы еще знаете контейнеры-адаптеры?
  2. Какие требования предъявляет priority_queue к типу (кассу), к которому принадлежат хранимые элементы? От чего зависит "приоритет"?

Л.р.№6 Стандартные алгоритмы

  1. Заполнить std::vector объектами класса "студент". Реализовать меню:
  2. Добавление, удаление.
  3. Просмотр всех студентов (std::for_each).
  4. Сортировка студентов по возрастанию и убыванию среднего балла (std::sort).
  5. Поиск первого студента со средним баллом выше заданного (std::find_if)
  6. Использовать стандартные алгоритмы, связыватели и адаптеры функций-элементов.

Перед сдачей убедитесь, что используемые а Вашей программе циклы не могут быть заменены использованием стандартных алгоритмов.

То же касается собственноручно написанных функторов: если вместо них можно обойтись всевозможными binder'ами из <functional> - то это необходимо сделать.

Контрольные вопросы

  1. Что такое функтор? Как написать свой функтор?
  2. Что такое предикат? Напишите пример.
  3. Приведите пример использования binder'ов (без привлечения стандартных алгоритмов).
  4. Напишите свою реализацию bind1st.
  5. Напишите свою реализацию mem_fun_ref.

Л.р.№1 Java Вводная

Составить массив из NxM случайных чисел. Для каждой строки вычислить среднее арифметическое и отсортировать строки в порядке убывания полученных значений.

(4 балла)

Л.р.№2 Java Классы и наследование

Л.р.№5 прошлого семестра (про военную базу, Vehicle, Bus и Truck) переделать на Java. Создать гетерогенный массив из одного Vehicle'а, одного Bus'а и одного Truck'а и втроем приехать на базу. Объяснить, где здесь проявляется полиморфное поведение.

Альтернативное задание: любую лабу из прошлого семестра с наследованием и полиморфизмом переделать на Java. Продемонстрировать полиморфное поведение.

Подсказки:

  1. Вместо глобальных переменных вида "something"_on_base можно создать класс Base и статические переменные в нем (с теми же именами). В нем же написать функцию main().
  2. Закрытого наследования в Java не бывает.
  3. Для вызова унаследованного конструктрора или метода используйте ключевое слово super.
  4. Константных методов в Java нет. Константные поля называются "final".
  5. Функции min(), max(), random(), abs(), floor() - в классе Math.
  6. Для явного приведения double к int используйте следующий синтаксис: int i = (int)(somebody.getSomeDouble());
  7. delete в Java нет.
  8. Обязательно  загляните в учебник и документацию по платформе. Также могут быть полезны официальные уроки.

Ожидаемое время: 1 час.

(6 баллов)

Проект

Первое. Установление требований.

До 28 ноября необходимо выслать мне на e-mail краткое описание Вашего проекта. Основной критерий "правильности" этой работы: после ее прочтения у постороннего читателя должна появиться в голове четкая цветная картинка с его (проекта) изображением, возникнуть ощущение, что проект уже готов и он с ним работал. Формат - произвольный (но обязательно последовательный и логичный). Для вдохновления используйте gdd.doc (см. внизу страницы) и шаблоны проектных документов с сайта http://readyset.tigris.org/nonav/templates/frameset.html В случае использования формата из gdd.doc необходимо написать полностью части 1 и 2, а также продумать (и написать) названия подзаголовков части 3 и под каждым из них пояснить, что именно должно быть описано в этом подразделе. Но в любом случае то, что Ваш документ оставит в голове своего читателя, должно ему понравиться (согласно требованию выше).

Второе. Проектирование.

В разделе 12.2 книги Рэмбо описано, как вывлять классы, их атрибуты и связи между ними и получать на основе этого "модель классов предметной области" в виде диаграммки (а-ля рис. 12.12 в книге). Для понимания, как устроена эта диаграммка см. главы 3-4. Для собственно рисования можно использовать программу Dia или любую другую. Результат высылать на ту же почту до 5 декабря. К диаграммке обязательно приложить текстовое описание каждого из изображенных классов: какое понятие из предметной области моделирует ("инкапсулирует") этот класс и, если надо, краткое пояснение других непонятных моментов.

Дополнительные источники информации:

  1. Великий и могучий
  2. Концепция web-проекта или почему мы убиваем свои идеи?
  3. Документирование по ГОСТ 34* — это просто
  4. Примеры GDD тут и тут
  5. Примеры SRS и ТЗ

Примечание: ни в случае с "описанием проекта" ни с "моделью классов предметной области" от Вас не требуется более 1-2 страниц A4 (12-ым шрифтом, но считая картинки). Кстати в обоих документах картинки категорически приветствуются!

Оба этих документа Вам понядобятся при защите проекта, а те, кто их пришлет в пределах указанных сроков - получат за это 5 баллов (максимум) из тех 20-ти, которые отводятся на проект.


SelectionFile type iconFile nameDescriptionSizeRevisionTimeUser
ĉ
Просмотр Скачать
  73 кб версия 3 20 нояб. 2013 г., 7:22 Dima Litvinov
Comments