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

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

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

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

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

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

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

Выводы

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

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

1. Седжвик Р. Алгоритмы на С++.: Пер. с англ. — М., 2011. — 1156 с.: ил.

2. Седжвик Р. Фундаментальные алгоритмы С++. — М., 2002. — 484 с.

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

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

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

6. Страуструп Б. Язык программирования С++. Второе дополненное издание. — М., 2001. – 1098 с. (доп. тир. 2002, 5, 6, 7).

7. С/С++. Программирование на языке высокого уровня / Т. А. Павловская. — СПб., 2013. — 461 с.: ил.

8. Шилдт Г. Полный справочник по С++. 4-е издание: Пер. с англ. — М., 2004. — 800 с.: ил.

9. Страуструп Б. Программирование: принципы и практика использования С++, испр. изд.: Пер. с англ. — М., 2013. — 1248 с.: ил.

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

11. Рао, Сиддхартха. Освой самостоятельно С++ за один день, 7-е изд. — М., 2013. — 688 с.: ил.

12. Дьюхэрст Стефан К. Скользкие места С++. Как избежать проблем при проектировании и компиляции ваших программ. — М., 2012. — 264 с.: ил.

СОДЕРЖАНИЕ

ВВЕДЕНИЕ................................................................................................................................... 3

1. ХЕШ-ТАБЛИЦЫ....................................................................................................................... 4

1.1. Практикум по теме.................................................................................................. 5

1.2. Требования к отчёту................................................................................................ 5

1.3. Варианты индивидуальных заданий к темам «Хеш-таблицы» и «Деревья двоичного поиска»........................................................................................................................... 7

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

2. ДЕРЕВЬЯ ДВОИЧНОГО ПОИСКА....................................................................................... 8

2.1. Практикум по теме................................................................................................ 10

2.2. Требования к отчёту.............................................................................................. 10

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

3. ПОДДЕРЖКА ПРОИЗВОЛЬНОЙ ПОСЛЕДОВАТЕЛЬНОСТИ В СТРУКТУРЕ ДАННЫХ ДЛЯ МНОЖЕСТВ.................................................................................................................... 12

3.1. Практикум по теме................................................................................................ 13

3.2. Индивидуальные задания к теме «Последовательности»................................. 14

3.3. Требования к отчёту.............................................................................................. 15

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

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

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

4.2. Практикум по теме................................................................................................ 24

4.3. Варианты индивидуальных заданий к теме «Наследование и изоморфизм» 27

4.4. Требования к отчёту.............................................................................................. 28

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

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

5.1. Практикум по теме................................................................................................ 30

5.2. Требования к отчёту.............................................................................................. 30

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

6. ИСПОЛЬЗОВАНИЕ СТАНДАРТНОЙ БИБЛИОТЕКИ ШАБЛОНОВ........................... 32

6.1. Практикум по теме................................................................................................ 32

6.2. Требования к отчёту.............................................................................................. 33

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

7. КУРСОВАЯ РАБОТА. Измерение временной сложности алгоритма.............................. 34

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

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

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

7.4. Выводы................................................................................................................... 39

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

Приложение. Измерение времени запросом внутреннего счётчика тактов процессора 42

Приложение. Измерение времени запросом внутреннего счётчика тактов процессора

Современные процессоры (начиная с Pentium II последних серий) поддерживают команду RDTSC, возвращающую 64-битное значение внутреннего счётчика тактов. Это достойная альтернатива применению функция clock (): можно измерить время выполнения даже одной команды процессора. Надёжный способ добраться до счётчика тактов состоит в применении ассемблерной вставки в код на С++. Можно написать функцию, аналогичную clock (). В программе под Borland C++ 3.1 эта функция может возвращать отсчёт в формате double, как наиболее информативном, и дублировать его массивом из 8 байт, содержащим само значение отсчёта для дополнительного контроля. Функция может выглядеть так:

#include < dos.h>

#include < mem.h>

double Ti (unsigned char *u) // u – массив из 8 байт для контроля

{ struct W { unsigned long P, Q; }; // Структура из двух длинных целых

union { unsigned char tb[8]; // Объединение структуры и массива байтов

W tt; } T;

asm { // Ассемблерная вставка:

// команда RTDSC не поддерживается, задана кодом

db 0x0f, 0x31, 0x66; mov WORD PTR T.tt.P, AX; // Младшие 32 бита

db 0x66; mov WORD PTR T.tt.Q, DX; // Старшие 32 бита

}

memcpy(u, T.tb, 8); // Копирование в контрольный массив

return (double) T.tt.P/65536 + T.tt.Q*65536; // Вычисление результата

}

В оболочках Visual C++ 6.0 и более современных (32-битных) ассемблерная вставка будет выглядеть иначе: нет нужды задавать команду RTDSC кодом и использовать префиксы 32-битной операции.

asm { // Ассемблерная вставка для 32-битной программной оболочки

RTDSC; mov DWORD PTR T.tt.P, EAX; // Младшие 32 бита

mov DWORD PTR T.tt.Q, EDX; // Старшие 32 бита

}

Этим способом время меряется с максимально возможной точностью. Этот способ хорош не только тем, что не требует зацикливания исследуемого фрагмента программы. Он позволяет исключать из измеряемого интервала части кода, не относящиеся собственно к алгоритму, например, генерацию или вывод данных.

В системах программирования Visual С++ от Microsoft можно также воспользоваться функцией QueryPerformanceCounter () из библиотеки windows.h. Подробности — в справочнике MSDN. Ещё один способ использован выше в примере программы для статистического эксперимента.

Редактор Г. Г. Петров

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

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

Бумага офсетная. Печать офсетная. Печ. л..

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

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

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

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