ВВЕДЕНИЕ. Методические указания к лабораторным работам, практическим занятиям и курсовому проектированию

АЛГОРИТМЫ И СТРУКТУРЫ ДАННЫХ

Методические указания к лабораторным работам,
практическим занятиям
и курсовому проектированию.
Часть 2

Санкт-Петербург
Издательство СПбГЭТУ «ЛЭТИ»
2014

УДК 004.424: 004.422.63(075.8)

Алгоритмы и структуры данных: Методические указания к лабораторным работам, практическим занятиям и курсовому проектированию. Часть 2 / Сост.: П. Г. Колинько. –– СПб.: Изд-во СПбГЭТУ «ЛЭТИ», 2014. – 43 с.: ил.

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

Пособие предназначено для студентов-бакалавров по направлению 230100.62 «Информатика и вычислительная техника» дневной, очно-заочной и заочной форм обучения.

Утверждено
редакционно-издательским советом университета
в качестве методических указаний

© П. Г. Колинько, 2012–2014

© СПбГЭТУ «ЛЭТИ», 2014

ВВЕДЕНИЕ

Цель практикума — завершение двухсеместрового курса «Алгоритмы и структуры данных». Практикум содержит шесть разделов. Первые три раздела посвящены комбинированным структурам данных. В них рассматриваются способы размещения множеств в памяти ЭВМ, оптимизированные под различные задачи работы с ними. Изучаются алгоритмы эффективного выполнения двуместных операций над множествами в этих структурах данных, а также применение их для поддержки произвольных последовательностей.

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

Содержанием курсового проектирования является эксперимент по прямому измерению временной сложности алгоритма, построенного на использовании стандартной библиотеки шаблонов. Результат эксперимента позволит дать заключение об эффективности этой библиотеки.

В каждом разделе даны ссылки на литературу, которую следует проработать для изучения темы.

По каждой из тем и по курсовой работе должны быть представлены отчёты. Отчёты должны содержать: название темы; текст индивидуального задания; тесты для проверки программ; результаты их работы; выводы, обязательно содержащие заключение о временной сложности использованных алгоритмов; список использованных источников; перечень приложений. Обязательное приложение: исходный текст отлаженной программы на машинном носителе. Допускается объединение нескольких тем в одном отчёте. Отчёт по теме 6 можно включить в курсовую работу.

Все примеры, имеющиеся в пособии, проверены в оболочке Visual C++ 2012. Для обучения могут быть использованы любые программные оболочки с поддержкой С++, выпущенные не ранее 2005 г. Рекомендуется оболочка Visual C++ 2012 как поддерживающая стандарт С++11. Информация об этом стандарте имеется в Википедии. Подробное изложение всех нововведений см. в книге С. Прата [10], c 1049–1151. Изучить программирование на С++ в новом стандарте можно также по книге С. Рао [11]. Типовые ошибки программирования обсуждаются в книге С. Дьюхэрста [12].