ПК 2102. ПК(2102). П. Г. Колинько пользовательские контейнеры

• Название: П. Г. Колинько пользовательские контейнеры
• Анкор: ПК 2102
• Дата: 28.11.2021
• Размер: 0.78 Mb.
• Имя файла: ПК(2102).docx
• Тип: Учебно-методическое пособие; #284768
• страница: 12 из 12

4.3. Оформление результатов эксперимента

Результаты эксперимента следует оформить в виде графика зависимости времени решения задачи как функции размера входа. На графике должны быть представлены:

— точки, соответствующие измеренным значениям;

— кривая регрессии для уравнения, отобранного по результатам сравнения выборочных дисперсий;

— границы доверительного интервала (регрессия ±3 СКО).

Значения СКО выдаются программой RG41. Ожидается, что все измеренные значения попадут в доверительную область (с вероятностью 99,7 %), а  кривая регрессии будет усреднять их.

График можно взять из заготовок в электронной таблице EXAMPLE. Возможно, для этого таблицу придется подкорректировать под фактический объем обработанных измерений (размножить строки в расчетной части и исправить диапазоны данных в графике). Достаточно доработать только тот график, который пойдет в отчет (см. рис. 4.2).

4.4. Выводы

По итогам эксперимента дается заключение о том, насколько экспериментальная оценка временной сложности алгоритма обработки данных соответствует теоретической. Исследуются особенности реализации алгоритмов, позволяющие объяснить полученные результаты.

Алгоритмы отдельных операций следует доработать таким образом, чтобы получилась итоговая линейная сложность или обосновать, почему это невозможно.

Список литературы

1. Ахо Дж., Хопкрофт А., Ульман Дж. Построение и анализ вычислительных алгоритмов. М.: Мир, 1979. 536 с.

2. Галовиц Я. C++17 STL. Стандартная библиотека шаблонов. СПб.: Питер, 2018. 432 с.: ил.

3. Готтшлинг П. Современный С++ для программистов, инженеров и уче­ных. М.: ИД «Вильямс», 2016. 512 с.: ил.

4. Джоссатис Н. М. Стандартная библиотека С++: справочное руководство. 2-е изд. / пер. с англ. М.: ИД «Вильямс», 2014. 1136 с.: ил.

5. Кнут Д. Искусство программирования для ЭВМ. Т. 3: Сортировка и поиск. М.: Мир, 2013. 736 с.

6. Липпман С. Б., Лажойе Ж., Му Б. Э. Язык программирования С++. Базовый курс. 5-е изд. / пер. с англ. М.: ИД «Вильямс», 2014. 1120 с.: ил.

7. Мейерс С. Наиболее эффективное использование С++. 35 новых рекомендаций по улучшению ваших программ и проектов. / пер. с англ. М.: Изд-во «ДМК Пресс», 2012. 294 с.: ил.

8. Мэйерс С. Эффективный и современный С++: 42 рекомендации по использованию С++11 и С++14 / пер. с англ. — М.: ИД «Вильямс», 2018. 304 с.: ил.

9. Новиков Ф. А. Дискретная математика: учеб. для вузов. 2-е изд. Стандарт третьего поколения. СПб.: Питер, 2013. 432 с.: ил.

10. О'Двайр, А. Осваиваем С++17 STL. М.: Изд-во «ДМК Пресс», 2019. 352 с.: ил.

11. Прата С. Язык программирования C++. 6‑е изд. М.: ИД «Вильямс», 2011. 1244 с.: ил.

12. Саттер Г. Решение сложных задач на С++ / пер. с англ. М.: ИД «Вильямс», 2015. 400 с.: ил.

13. Седжвик Р. Алгоритмы на С++ / пер. с англ. М.: ИД «Вильямс», 2011. 1156 с.: ил.

14. Страуструп Б. Программирование: принципы и практика с использованием С++. 2-е изд. / пер. с англ. СПб.: ООО «Диалектика», 2019. 1328 с.: ил.

15. Страуструп Б. Язык программирования С++. 2‑е изд., доп. М.: Изд‑во «Бином-пресс», 2001. 1098 с.

16. Страуструп Б. Язык программирования С++ (стандарт С++11). Краткий курс / пер. с англ. М.: Изд‑во «Бином-пресс», 2019. 176 с.: ил.

ПРИЛОЖЕНИЕ

Измерение времени запросом внутреннего
счетчика тактов процессора

Современные процессоры (начиная с Pentium II последних серий) поддерживают команду RDTSC, возвращающую 64-битное значение внутреннего счетчика тактов. Это достойная альтернатива применению функции clock( ): можно измерить время выполнения даже одной команды процессора. Самый простой и универсальный способ добраться до счетчика тактов состоит в применении возможностей библиотеки std∷chrono. В ней доступна функция now( ), снимающая текущие показания часов высокого разрешения. Ее можно применить тем же способом, что и clock( ), но без необходимости зацикливать измеряемый процесс. Чтобы избежать ненужных сложностей, рекомендуется действовать следующим образом:

1) перед началом измеряемого процесса снимается отсчет времени t1:

auto t1 = std::chrono::high_resolution_clock::now( );

2) по завершении процесса таким же образом снимается отсчет t2;

3) для получения разности отсчетов dt используется выражение

auto dt = duration_cast>( t2–t1 );

4) в результате используется выражение dt.count( ):

cout << " DT=" << (dt.count( )) <<")\n";

Именно этот способ измерения времени использован в примере программы для статистического эксперимента (см. 4.1).

СОДЕРЖАНИЕ

ВВЕДЕНИЕ 3

1. РАБОТА С ИЕРАРХИЕЙ ОБЪЕКТОВ: НАСЛЕДОВАНИЕ И ПОЛИМОРФИЗМ 5

1.1. Учебная программа «Библиотека фигур» 6

1.2. Практикум по гл. 1 13

1.3. Требования к отчету 20

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

2. ПОДДЕРЖКА ОБРАБОТКИ ИСКЛЮЧИТЕЛЬНЫХ СИТУАЦИЙ 22

2.1. Практикум по гл. 2 25

2.2. Дополнительные требования к отчету 25

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

3. КОМБИНИРОВАННЫЕ СТРУКТУРЫ ДАННЫХ И СТАНДАРТНАЯ БИБЛИОТЕКА ШАБЛОНОВ 27

3.1. Хеш-таблицы 27

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

3.2. Деревья двоичного поиска 29

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

3.3. Поддержка произвольной последовательности в структуре данных для множеств 34

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

3.4. Использование стандартной библиотеки шаблонов 37

3.5. Превращение в контейнер пользовательской структуры данных 38

3.6. Практикум по гл. 3 41

3.6.1. Дополнительные требования к отчету 41

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

4. КУРСОВАЯ РАБОТА. «ИЗМЕРЕНИЕ ВРЕМЕННОЙ СЛОЖНОСТИ АЛГОРИТМА В ЭКСПЕРИМЕНТЕ НА ЭВМ» 48

4.1. Пример программы для эксперимента 48

4.2. Обработка результатов эксперимента 56

4.3. Оформление результатов эксперимента 63

4.4. Выводы 63

Список литературы 64

ПРИЛОЖЕНИЕ 65

Измерение времени запросом внутреннего счетчика тактов процессора 65

Колинько Павел Георгиевич

Пользовательские контейнеры

Учебно-методическое пособие


Редактор Е. А. Ушакова

––––––––––––––––––––––––––––––––––––––––––––––––––––––––––

Подписано в печать . .2020 . Формат 60×84 1/16.

Бумага офсетная. Печать цифровая. Печ. л. 4,0.

Гарнитура «Times New Roman». Тираж 151 экз. Заказ

––––––––––––––––––––––––––––––––––––––––––––––––––––––––––

Издательство СПбГЭТУ «ЛЭТИ»

197376, С.-Петербург, ул. Проф. Попова, 5