Методические указания алгоритмы и структуры данных. Методические указания к лабораторным работам, практическим занятиям и курсовому проектированию Часть 2 Выпуск 1606
 Скачать 429.85 Kb.
|
|
МИНОБРНАУКИ РОССИИ –––––––—————–––—————––––––– Санкт-Петербургский государственный электротехнический университет «ЛЭТИ» —————————————————— АЛГОРИТМЫ И СТРУКТУРЫ ДАННЫХ Методические указания к лабораторным работам, практическим занятиям и курсовому проектированию Часть 2 Выпуск 1606 Санкт-Петербург Издательство СПбГЭТУ «ЛЭТИ» 2016 УДК 004.424:004.422.63(075.8) Алгоритмы и структуры данных: методические указания к лабораторным работам, практическим занятиям и курсовому проектированию. Ч. 2. Вып. 1606 / сост. П. Г. Колинько. — СПб.: Изд-во СПбГЭТУ «ЛЭТИ», 2016. — 53 с.: ил. Описывается цикл лабораторных работ и практических занятий в компьютерном классе. Содержатся материалы для курсовой работы. Предназначены для студентов бакалавриата по направлению 230100.62 «Информатика и вычислительная техника» дневной, очно-заочной и заочной форм обучения. Утверждено редакционно-издательским советом университета в качестве методических указаний © П. Г. Колинько, 2012–2016(0628) © СПбГЭТУ «ЛЭТИ», 2014 ВВЕДЕНИЕЦель методических указаний — завершение двухсеместрового курса «Алгоритмы и структуры данных». Методические указания содержат шесть разделов. Первые три раздела посвящены комбинированным структурам данных. В них рассматриваются способы размещения множеств в памяти ЭВМ, оптимизированные под различные задачи работы с ними. Изучаются алгоритмы эффективного выполнения двуместных операций над множествами в этих структурах данных, а также применение их для поддержки произвольных последовательностей. Следующие три темы предусматривают полное знакомство с возможностями объектного программирования. На простом примере изучается иерархическая структура классов и механизм поддержки обработки особых ситуаций. Обучение завершается знакомством со стандартной библиотекой шаблонов. Содержанием курсового проектирования является эксперимент по прямому измерению временной сложности алгоритма, построенного на использовании стандартной библиотеки шаблонов. Результат эксперимента позволит дать заключение об эффективности этой библиотеки. В каждом разделе даны ссылки на литературу, которую следует проработать для изучения темы. По каждой из тем и по курсовой работе должны быть представлены отчёты, содержащие название темы; текст индивидуального задания; тесты для проверки программ; результаты их работы; выводы, обязательно содержащие заключение о временной сложности использованных алгоритмов; список использованных источников; перечень приложений. Обязательное приложение: исходный текст отлаженной программы на машинном носителе. Допускается объединение нескольких тем в одном отчёте. Отчёт по теме 6 можно включить в пояснительную записку к курсовой работе. Все примеры, имеющиеся в методических указаниях, проверены в оболочке Visual C++ 2012. Для обучения могут быть использованы любые программные оболочки с поддержкой С++, выпущенные не ранее 2005 г. Рекомендуется оболочка Visual C++ 2012 как поддерживающая стандарт С++11. Информация об этом стандарте имеется в Википедии. Нововведения подробно изложены в [10, c. 1049–1151]. Изучить программирование на С++ в новом стандарте можно также по [11]. С основами библиотеки STL можно ознакомиться по [7] и [15]. Типовые ошибки в программах на С++ обсуждаются в [12], [13] и [14]. ОСОБЫЕ ТРЕБОВАНИЯ К ЗАОЧНИКАМ Для заочников темы 1–3 факультативны, отчётности по ним нет. Материалы этих тем используются для подготовки отчётного задания по теме 6. Варианты индивидуальных заданий комбинируются из содержимого таблиц 1.1 и 3.1. Из табл. 1.1 берётся выражение с операциями над множествами, а из табл. 3.1 — набор операций над последовательностями, а также указание на выбор базового контейнера — для дерева двоичного поиска (set и т. п.) или для хеш-таблицы (unordered_set). Из индивидуального набора операций с множествами и последовательностями составляется цепочка, для которой выполняется статистический эксперимент: измерение времени выполнения цепочки для изменяемых размеров множеств. Результаты измерений будут использованы в курсовой работе. Отчёты по темам с текстами программ, составленных по индивидуальным заданиям, высылаются по адресу «clgn@mail.ru»: — до восьмой недели семестра — по теме 4 «наследование и полиморфизм»; — до двенадцатой недели — по теме 5 «исключительные ситуации»; — до начала сессии — по теме 6 «стандартная библиотека шаблонов». По этому же адресу можно получить консультации. Обработка статистики, полученной в работе по теме 6, и оформление курсовой работы будет выполняться на занятиях во время сессии. Вопросы к экзамену размещены в конце каждой темы и в приложении. |