Методические указания алгоритмы и структуры данных. Методические указания к лабораторным работам, практическим занятиям и курсовому проектированию Часть 2 Выпуск 1606
 Скачать 429.85 Kb.
|
Список литературы1. Седжвик Р. Алгоритмы на С++ / пер. с англ. — М.: И. Д. Вильямс, 2011. — 1156 с.: ил. 2. Седжвик Р. Фундаментальные алгоритмы С++. — К.: Диасофт, 2001. — 484 с. 3. Ахо Дж., Хопкрофт А., Ульман Дж. Построение и анализ вычислительных алгоритмов. — М.: Мир, 1979. 4. Кнут Д. Искусство программирования для ЭВМ. Т. 3: Сортировка и поиск. — М.: Мир, 2013. 5. Новиков Ф. А. Дискретная математика: учеб. для вузов. 2-е изд. Стандарт третьего поколения. — СПб.: Питер, 2013. — 432 с.: ил. 6. Страуструп Б. Язык программирования С++. 2‑е доп. изд. — М.: Бином-пресс, 2001. – 1098 с. 7. Павловская Т. А. С/С++. Процедурное и объектно-ориентированное программирование: Учеб. для вузов. — СПб.: Питер, 2015. — 496 с.: ил. 8. Шилдт Г. Полный справочник по С++. 4-е изд. Пер. с англ. — М.: И. Д. Вильямс, 2004. — 800 с.: ил. 9. Страуструп Б. Программирование: принципы и практика использования С++. Испр. изд. / пер. с англ. — М.: И. Д. Вильямс, 2013. —1248 с.: ил. 10. Прата С. Язык программирования C++. 6‑е изд. — М.: И. Д. Вильямс, 2011. — 1244 с.: ил. 11. Липпман С. Б., Лакойе Ж., Му Б. Э. Язык программирования С++. Базовый курс. 5-е изд. Пер. с англ. — М.: И. Д. Вильямс, 2014. — 1120 с.: ил. 12. Дьюхэрст Стефан К. Скользкие места С++. Как избежать проблем при проектировании и компиляции ваших программ. — М.: ДМК Пресс, 2012. — 264 с.: ил. 13. Мейерс С. Наиболее эффективное использование С++. 35 новых рекомендаций по улучшению ваших программ и проектов. — М.: ДМК Пресс, 2012. — 294 с.: ил. 14. Саттер Г. Решение сложных задач на С++. Пер. с англ. — М.: И. Д. Вильямс, 2015. — 400 с.: ил. 15. Джоссатис Н. М. Стандартная библиотека С++: справочное руководство. 2-е изд. Пер. с англ. — М.: И. Д. Вильямс, 2014. — 1136 с.: ил. ПРИЛОЖЕНИЕИзмерение времени запросом внутреннего счётчика тактов процессораСовременные процессоры (начиная с Pentium II последних серий) поддерживают команду RDTSC, возвращающую 64-битное значение внутреннего счётчика тактов. Это достойная альтернатива применению функции clock( ): можно измерить время выполнения даже одной команды процессора. Надёжный способ добраться до счётчика тактов состоит в применении ассемблерной вставки в код на С++. Можно написать функцию, аналогичную clock( ). В программе под Borland C++ 3.1 эта функция может возвращать отсчёт в формате double, как наиболее информативном, и дублировать его массивом из 8 байт, содержащим само значение отсчёта для дополнительного контроля. Функция может выглядеть так: #include #include 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(long *lpPerformanceCount) из библиотеки winbase.h Следует отметить, что частота, на которой работает процессор в современных ЭВМ, особенно в портативных, не постоянна, она может искусственно уменьшаться для экономии ресурса аккумуляторной батареи. Запросить текущую частоту можно с помощью функции QueryPerformanceFrequency(long*lpFrequency). Функция формирует указатель на количество тактов процессора в секунду. Подробности — в справочнике MSDN (https://msdn.microsoft.com/en-us/library/ms644904.aspx). Можно использовать функции из класса std∷chrono∷highresolutionclock( ) из библиотеки STL. Этот способ особенно рекомендуется использовать в системах программирования, работающих не под MS Windows, Ещё один способ измерения времени использован в примере программы для статистического эксперимента. Вопросы к экзамену1. Способы хранения множеств, облегчающие произвольный доступ к данным. 2. Значение упорядоченности для двуместных операций над множествами. 3. Дерево двоичного поиска как расширяемый список с сохранением упорядоченности. 4. Упорядоченный массив как способ хранения дерева двоичного поиска. 5. Хеширование как обобщение для хранения множества в массиве битов. 6. Открытые и закрытые хеш-таблицы: способы разрешения коллизий. 7. Рекомендации по составлению хеш-функций. 8. Двуместные операции с множествами в форме хеш-таблиц. 9. Дерево двоичного поиска: алгоритмы вставки и удаления. 10. Вырождение ДДП при произвольной вставке последовательности узлов. 11. АВЛ-дерево: алгоритмы балансировки при вставке и удалении. 12. Красно-чёрное дерево: балансировка при вставке и удалении. 13. 2-3-дерево. Алгоритмы вставки и удаления. Рекомендация по кодированию в виде варианта ДДП. 14. Получение ДДП с автобалансировкой из упорядоченного массива. 15. Получение 2-3-дерева из упорядоченной последовательности. 16. Двуместные операции с множествами в форме ДДП. 17. Алгоритм пошагового обхода ДДП. 18. Множества с повторениями в хеш-таблице, ДДП, АВЛ-дереве, 2-3-дереве. 19. Множество и последовательность. Хранение последовательностей в структуре данных для множеств. Варианты: обход, разметка, связи, массив ссылок. 20. Алгоритм реализации двуместной операции с АВЛ-деревьями: схема слияния с использованием массивов ссылок на узлы дерева. 21. Алгоритм слияния для двуместной операции: чистка хвостов и восстановление дерева-результата. 22. Иерархия классов. Производные классы — что это даёт. Функции-члены. Конструкторы и деструкторы. Пример иерархии классов. 23. Управление доступом к объектам в иерархии. Виртуальные функции. Абстрактные классы. Идентификаторы override и final. 24. Пример программы с иерархией классов. Монитор экрана. Библиотека фигур. Возможная иерархия классов и её смысл. 25. Множественное наследование. Множественное вхождение базового класса. Разрешение неоднозначности. 26. Закрытое наследование и его альтернатива — включение. 27. Виртуальные базовые классы. 28. Контроль доступа к членам базовых классов. Защищённые члены. 29. Шаблоны. Обобщённые функции. 30. Шаблоны. Обобщённые классы. 31. Исключительные ситуации: основные понятия. 32. Исключительные ситуации: иерархия и способы передачи информации в обработчик. 33. Исключительные ситуации — неожиданные. Возможности для их обработки. 34. Проектирование системы обработки особых ситуаций. Базовые и расширенные гарантии. 35. Идиома «захват ресурса через инициализацию». 36. Функции, не генерирующие исключений. Функции, прозрачные для исключений. 37. Преобразования типов: в стиле Си, статические, константные, произвольные. 38. Преобразования типов: динамические; неожиданные. Блокировка неявного вызова конструктора или функции преобразования типа. 39. Перегрузка функций для предотвращения преобразования типа. Функции-члены для преобразования типа. 40. Свободная память (перегрузка new и delete). Явное указание размещения. Размещение, не вырабатывающее исключений. 41. STL: Библиотека string как (плохой) образец контейнера. 42. STL: Перегрузка разыменования и взятия адреса. Итераторы: сущность и классификация. 43. STL: Функциональные объекты: указатели, функторы, лямбда. 44. STL: Полезные алгоритмы. Особенности применения библиотеки algorithm. 45. Последовательные контейнеры: vector, list, deque. 46. Адаптеры последовательного контейнера: стек и очередь; очередь с приоритетами. 47. Ассоциативные контейнеры — краткий обзор. Множество и отображение. 48. Ассоциативные контейнеры — мультимножество и мультиотображение. 49. Контейнеры — хеш-таблицы. 50. Умные указатели: уникальный указатель. 51. Умные указатели: разделяемый и слабый указатели. 52. Измерение временной сложности алгоритма с помощью ЭВМ. СОДЕРЖАНИЕ ВВЕДЕНИЕ 3 1. ХЕШ-ТАБЛИЦЫ 5 1.1. Практикум по теме 6 1.2. Требования к отчёту 8 1.3. Контрольные вопросы 8 2. ДЕРЕВЬЯ ДВОИЧНОГО ПОИСКА 9 2.1. Практикум по теме 11 2.2. Требования к отчёту 12 2.3. Контрольные вопросы 12 3. ПОДДЕРЖКА ПРОИЗВОЛЬНОЙ ПОСЛЕДОВАТЕЛЬНОСТИ В СТРУКТУРЕ ДАННЫХ ДЛЯ МНОЖЕСТВ 13 3.1. Практикум по теме 14 3.2. Требования к отчёту 16 3.3. Контрольные вопросы 16 4. РАБОТА С ИЕРАРХИЕЙ ОБЪЕКТОВ: 4 НАСЛЕДОВАНИЕ И ПОЛИМОРФИЗМ 17 4.1. Учебная программа «Библиотека фигур» 18 4.2. Практикум по теме 25 4.3. Требования к отчёту 31 4.4. Контрольные вопросы 31 5. ПОДДЕРЖКА ОБРАБОТКИ ИСКЛЮЧИТЕЛЬНЫХ СИТУАЦИЙ 32 5.1. Практикум по теме 34 5.2. Требования к отчёту 35 5.3. Контрольные вопросы 35 6. ИСПОЛЬЗОВАНИЕ СТАНДАРТНОЙ БИБЛИОТЕКИ ШАБЛОНОВ 36 6.1. Практикум по теме 37 6.2. Требования к отчёту 37 6.3. Контрольные вопросы 37 7. КУРСОВАЯ РАБОТА. Измерение временной сложности алгоритма 39 7.1. Пример программы для эксперимента 39 7.2. Обработка результатов эксперимента 42 7.3. Оформление результатов эксперимента 45 7.4. Выводы 45 Список литературы 46 ПРИЛОЖЕНИЕ 47 Измерение времени запросом внутреннего счётчика тактов процессора 47 Вопросы к экзамену 48 Редактор И. Г. Скачек –––––––––––––––––––––––––––––––––––––––––––––––––––––––––– Комплектация 1 CD-ROM. Объём данных 1,3 Мб. Гарнитура «Times New Roman». Заказ –––––––––––––––––––––––––––––––––––––––––––––––––––––––––– Издательство СПбГЭТУ «ЛЭТИ» 197376, С.-Петербург, ул. Проф. Попова, 5 |