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

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

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

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

УДК 004.424:004.422.63(075.8)

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

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

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

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

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

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

ВВЕДЕНИЕ

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

Методические указания покрывают первый семестр двухсеместрового курса «Алгоритмы и структуры данных» и состоит из трёх разделов. Тема первого раздела «Множества» является вводной. В ней показывается, что абстрактные данные могут быть реализованы в программе разными способами и что от способа реализации зависит существенная характеристика алгоритма — его временная сложность. Вводится понятие объекта как естественного расширения языка С++ для поддержки пользовательских типов данных.

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

Вторая тема «Деревья» акцентирует внимание студентов на свойствах рекурсивного определения данных и рекурсивных алгоритмов. Она предусматривает также освоение техники работы с объектами: создание и уничтожение, копирование объектов, совместное использование в программе объектов разных типов (дружественные функции) и т. п. Вводится понятие шаблона функции и класса, в качестве иллюстрации для применения которого используются абстрактные данные «очередь» и «стек».

Третья тема «Графы» выносится на курсовое проектирование для закрепления навыков, полученных при изучении двух первых тем.

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

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

Все примеры проверены в оболочке Visual C++ 2012, используемой в учебном процессе СПбГЭТУ «ЛЭТИ». В более ранних оболочках, например, в Borland C++ 3.1, они могут быть потребовать небольшой модификации.

В частности, может потребоваться исключить предложение «using namespace std», добавить определение enum bool {false, true}, заменить «надёжные» функции _getch(), gets_s() их классическими аналогами getch(), gets() и т. п.

Для самостоятельной работы могут быть использованы любые доступные программные оболочки С++, поддерживающие по крайней мере стандарт C++98: Borland C++ Builder 6.0, Microsoft Visual С++ 2005 и более современные, в том числе свободно распространяемые компиляторы (DEV C++ и т. п.), а также компиляторы в ОС Linux.