Читать онлайн «Графы. Модели вычислений. Структуры данных»

Министерство образования и науки Российской Федерации Федеральное агентство по образованию Нижегородский государственный университет им. Н. И. Лобачевского В. Е. АЛЕКСЕЕВ, В. А. ТАЛАНОВ ГРАФЫ. МОДЕЛИ ВЫЧИСЛЕНИЙ. СТРУКТУРЫ ДАННЫХ Учебник Рекомендовано Научно-методическим советом по прикладной математике и информатике УМО университетов РФ в качестве учебника для студентов, обучающихся по специальности 010200 – Прикладная математика и информатика и по направлению 510200 – Прикладная математика и информатика Нижний Новгород Издательство Нижегородского госуниверситета 2005 1 УДК 519. 17+510. 58+681. 142 ББК В12 А 47 Рецензенты: д. ф. -м. н. , проф. НГТУ В. М. Галкин д. ф. -м. н. , проф. НГПУ М. И. Иорданский Алексеев В. Е. , Таланов В. А. Графы. Модели вычислений. Структуры данных: Учебник. – Нижний Новгород: Изд-во ННГУ, 2005. 307 с. ISBN 5–85747–810–8 Учебник состоит из трех частей, посвященных вопросам анализа и разработ- ки алгоритмов: графы и алгоритмы, модели вычислений, структуры данных. Для понимания материала достаточно математической подготовки в объеме первого курса университета или технического вуза. Предназначен для студентов, обучающихся по направлению 510200 − При- кладная математика и информатика и по специальности 010200 − Прикладная математика и информатика. Работа выполнена в учебно-исследовательской лаборатории «Математические и программные технологии для современных компьютерных систем (Информационные технологии)» при поддержке корпорации «Интел». ББК В12 ISBN 5–85747–810–8 © В. Е. Алексеев, В. А. Таланов, 2005 2  Предисловие В этой книге под одной обложкой собраны учебные тексты, на первый взгляд разнородные, но относящиеся к одной сравнительно молодой об- ласти человеческой деятельности. Это деятельность по созданию и иссле- дованию алгоритмов, для которой пока не придумано общеупотребитель- ного объединяющего названия (она является частью того, что охватывает- ся терминами «computer science» и «информатика»). Работа в этой области требует определенных математических знаний и представления о пробле- мах, связанных с разработкой компьютерных программ, но она не сводит- ся к математике или программированию. Ее роль можно сравнить с ролью технологии по отношению к науке и производству. Материал настоящего учебника в целом соответствует программе кур- са «Анализ и разработка алгоритмов», читавшегося в течение ряда лет для магистрантов факультета ВМК ННГУ, а отдельные его фрагменты ис- пользуются в различных спецкурсах. Книга состоит из трех частей, кото- рые могут изучаться независимо друг от друга и в произвольном порядке. Первая часть посвящена алгоритмам на графах. Значительный объем в ней занимает глава 1, в которой приводятся базовые понятия и факты из теории графов.