ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ
«НОВОСИБИРСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ»
Факультет автоматики и вычислительной техники
“УТВЕРЖДАЮ”
Декан АВТФ
профессор, д. т.н.
“___ ”______________ г.
РАБОЧАЯ ПРОГРАММА учебной дисциплины
Структуры и алгоритмы обработки данных
ООП: направление 230100.62 Информатика и вычислительная техника
Шифр по учебному плану: СД. Р.4
Факультет: автоматики и вычислительной техники
очная форма обучения
Курс: 3, семестр: 5, 6
Лекции: 34
Лабораторные работы: 18
РГЗ: 6
Самостоятельная работа: 50
Экзамен: 5
Зачет: 6
Всего: 102
Новосибирск
2011
Рабочая программа составлена на основании Государственного образовательного стандарта высшего профессионального образования по направлению (специальности): 552800 Информатика и вычислительная техника.(№ 35 тех/бак от 01.01.2001)
СД. Р.4, дисциплины национально - регионального (вузовского) компонента
Рабочая программа обсуждена на заседании кафедры Вычислительной техники
протокол № от
Программу разработал
старший преподаватель,
Заведующий кафедрой
профессор, д. т.н.
Ответственный за основную образовательную программу
профессор, д. т.н.
профессор, д. т.н.
1. Внешние требования
Таблица 1.1
Шифр дисциплины | Содержание учебной дисциплины | Часы |
Внешние требования федерального государственного образовательного стандарта (ГОС) по направлению подготовки 230100 Информатика и вычислительная техника: Выпускник должен обладать следующими общекультурными компетенциями (ОК): - владеет культурой мышления, способен к обобщению, анализу, восприятию информации, постановке цели и выбору путей её достижения (ОК-1); - готов к кооперации с коллегами, работе в коллективе (ОК-3); - использует основные законы естественнонаучных дисциплин в профессиональной деятельности, применяет методы математического анализа и моделирования, теоретического и экспериментального исследования (ОК-10); - осознает сущность и значение информации в развитии современного общества; владеет основными методами, способами и средствами получения, хранения, переработки информации (ОК-11); - имеет навыки работы с компьютером как средством управления информацией (ОК-12); Выпускник должен обладать следующими профессиональными компетенциями (ПК): - осваивать методики использования программных средств для решения практических задач (ПК-2); - разрабатывать компоненты программных комплексов и баз данных, использовать современные инструментальные средства и технологии программирования (ПК-5); - обосновывать принимаемые проектные решения, осуществлять постановку и выполнять эксперименты по проверке их корректности и эффективности (ПК-6); | 102 |
2. Особенности (принципы) построения дисциплины
Таблица 2.1
Особенности (принципы) построения дисциплины
Особенность | Содержание |
Основания для введения дисциплины в учебный план по направлению или специальности | Основание для введения дисциплины в учебный план направления 230100 - ФГОС ВПО по направлению подготовки 230100, Информатика и вычислительная техника, утвержденный приказом министерства образования и науки от 9.11. 2009 г. |
Адресат курса | Студенты 3 курса, обучающиеся по направлению 230100, "Информатика и вычислительная техника" (бакалаврская подготовка). |
Основная цель (цели) дисциплины | Формирование и закрепление знаний и умений по использованию фундаментальных алгоритмов и структур данных при проектировании и реализации сложных программных систем. |
Ядро дисциплины | Ядро дисциплины включает следующие темы: - базовый анализ алгоритмов: асимптотический анализ максимальной и средней сложности, установление различий между лучшим, средним и худшим случаями, нотации «О-большое» и «о-маленькое», «омега» и «тета», - стандартные классы сложности, - эмпирические измерения производительности, затраты по времени и объему памяти; - основные вычислительные алгоритмы: алгоритмы сортировки со сложностью O(NlogN); - базовые структуры данных: стеки, очереди, связанные списки, хэш-таблицы, деревья, графы; - алгоритмы для двоичных деревьев поиска, хэш-таблиц, представления графов, обходы в глубину и в ширину, алгоритмы для ориентированых и взвешенных графов; - программная инженерия: аттестация программного обеспечения, основы тестирования, включая создание плана тестирования и генерации тестовых сценариев, объектно-ориентированное тестирование. |
Связи с другими учебными дисциплинами основной образовательной программы | Дисциплина является логическим продолжением таких дисциплин, как "Программирование", "Объектно - ориентированное программирование". Также необходимо предварительное изучение дисциплин : дискретная математика, теория вероятности и математической статистики. |
Требования к первоначальному уровню подготовки обучающихся | Обучающийся предварительно овладел следующими знаниями и умениями: - базовые конструкции программирования: синтаксис и семантика языков высокого уровня; переменные, типы, выражения и присваивания, - простейший ввод/вывод; условные предложения и итеративные конструкции; функции и передача параметров; структурная декомпозиция, - алгоритмы и решение задач: стратегии решения задач, роль алгоритмов в решении задач, стратегии реализации алгоритмов, стратегии отладки, - понятие алгоритма, свойства алгоритмов, - базовые структуры данных: примитивные типы; массивы; структуры; строки и операции над строками, - принципы объектно - ориентированного программирования: определение и использование классов, инкапсюляция, наследование, полиморфизм, иерархии классов, - представление данных в памяти компьютера: биты, байты, слова; представление числовых данных и системы счисления; представление символьных данных, - человеко-машинное взаимодействие: введение в вопросы проектирования, - методология разработки программного обеспечения: основные понятия и принципы проектирования, структурная декомпозиция, стратегии тестирования и отладки, разработка сценариев тестирования, - среды разработки программ, инструменты тестирования и отладки программ на С++. |
Особенности организации учебного процесса по дисциплине | Дисциплина включает теоретический курс и практическую часть. По основным разделам дисциплины прослушивается и изучается курс лекций (34 часа). Практическая часть включает лабораторные занятия (17 часов), расчетно-графическое задание (6 семестр). Текущая аттестация проводится в 5 семестре по итогам выполнения и защиты 4 - х лабораторных работ, в 6 - м семестре - по итогам выполнения и защиты РГЗ. Итоговая аттестация студентов проводится с помощью экзамена (5 семестр) и зачета (6 семестр). |
3. Цели учебной дисциплины
Таблица 3.1
После изучения дисциплины студент будет
иметь представление | |
1 | о назначении, формах и области применения алгоритмов обработки данных и структур данных в реальных программных системах; |
2 | о разнообразии форм представления данных для обработки на ЭВМ |
3 | о подходах к оценке сложности алгоритмов и методах построения эффективных алгоритмов |
знать | |
4 | методы анализа и оценки вычислительной сложности алгоритмов |
5 | технологию проектирования структуры данных на основе абстрактного типа данных |
6 | "библиотеку" фундаментальных структур и алгоритмов обработки данных |
7 | способы представления структур данных в ЭВМ |
уметь | |
8 | выбирать, использовать, реализовывать и применять оптимальные в конкретных условиях базовые структуры данных и алгоритмы для организации сложных управляющих и информационных структур |
9 | проводить предварительную оценку эффективности проектируемых алгоритмов и структур данных |
иметь опыт (владеть) | |
10 | экспериментального исследования эффективности реализации алгоритмов и структур данных |
11 | формирования документального сопровождения программной разработки |
4. Содержание и структура учебной дисциплины
Лекционные занятия Таблица 4.1
(Модуль), дидактическая единица, тема | Часы | Ссылки на цели |
Семестр: 5 | ||
Модуль: базовый анализ алгоритмов | ||
Дидактическая единица: теория сложности алгоритмов: NP-сложные и труднорешаемые задачи | ||
Эффективность алгоритмов обработки данных. | 2 | 10, 3, 4, 9 |
Модуль: основные вычислительные алгоритмы: алгоритмы сортировки | ||
Дидактическая единица: задачи сортировки; внутренняя и внешняя сортировки; алгоритмы сортировки | ||
Быстрый бинарный поиск. Задача сортировки данных. Внутренняя сортировка. Внешняя сортировка | 5 | 1, 3, 6, 8 |
Модуль: базовые структуры данных: стеки, очереди, списки | ||
Дидактическая единица: линейные структуры данных: стек, очередь, дек, список | ||
Базовые структуры данных: стек, очередь, дек, список. Формы представления элементарных линейных структур. | 2 | 1, 2, 6, 7, 8 |
Модуль: деревья поиска и алгоритмы для двоичных деревьев поиска | ||
Дидактическая единица: деревья и леса, бинарные деревья; обходы деревьев; | ||
Использование деревьев в задачах поиска. Бинарное дерево поиска. Обход дерева поиска: прямой, обратный, симметричный обходы. Рекурсивные и итеративные алгоритмы основных операций. Случайное и вырожденное дерево поиска. Анализ эффективности операций. | 2 | 1, 3, 6, 7 |
Модуль: сбалансированные деревья поиска | ||
Дидактическая единица: бинарные деревья поиска, случайные, оптимальные, сбалансированные по высоте (АВЛ) и рандомизированные деревья, 2-3 деревья, 2-3-4-деревья, RB - деревья поиска | ||
Сбалансированные по высоте деревья поиска. Методы балансировки дерева поиска. Рандомизированное дерево, АВЛ-дерево, 2-3 дерево, 2-3-4 - дерево, красно-черное дерево. Оценка эффективности операций для сбалансирован-ных деревьев. | 3 | 1, 6, 7, 8 |
Модуль: хэш-таблицы | ||
Дидактическая единица: быстрый поиск: бинарный поиск, хеширование | ||
Хеш-таблицы. Свойства функций расстановки. Основные методы расстановки: деление, умножение, универсальное хеширование. Методы разрешения коллизий: метод цепочек, метод проб. Линейное, квадратичное и двойное повторное хеширование. Анализ эффективности методов хеширования. | 2 | 1, 3, 6, 8 |
Модуль: внешние структуры поиска | ||
Дидактическая единица: файлы: организация и обработка, представление деревьями: B-деревья | ||
Структуры данных и алгоритмы для внешней памяти. Файлы: организация и обработка. Индексированные, хешированные файлы. Внешние деревья поиска: B - дерево. Оценка вычислительной сложности операций для структур внешнего поиска. | 2 | 1, 2, 6, 7, 8, 9 |
Семестр: 6 | ||
Модуль: графы | ||
Дидактическая единица: представления графов | ||
Алгоритмы на графах. Неориентированные графы и орграфы, основные определения. Представление графов: L - граф, М - граф. Генераторы графов. Абстрактный тип данных "Граф": спецификация, представление, реализация. | 2 | 1, 2, 5, 6, 7, 8 |
Модуль: обходы графов и алгоритмы для графов | ||
Дидактическая единица: алгоритмы на графах | ||
Алгоритмы, основанные на обходе графа. | 4 | 1, 3, 6, 8, 9 |
Дидактическая единица: схемы поиска в глубину и ширину | ||
Схемы поиска в глубину и ширину. Поиск в ширину, деревья поиска в ширину. Поиск в глубину, глубинный остовный лес. Обобщенный поиск. Классификация ребер в графе. | 2 | 1, 3, 6, 8, 9 |
Модуль: алгоритмы для ориентированных графов | ||
Дидактическая единица: алгоритмы на графах | ||
Ориентированные графы. Циклический и ациклический орграф. Топологическая сортировка. Сильно связные компоненты орграфа. Транзитивное замыкание орграфа. | 2 | 1, 3, 6, 8, 9 |
Модуль: алгоритмы для взвешенных графов | ||
Дидактическая единица: минимальное остовное дерево | ||
Взвешенные графы, основные определения. Минимальное остовное дерево. Алгоритмы построения остовного дерева: алгоритм Прима, алгоритм Крускала. | 2 | 1, 3, 6, 8, 9 |
Дидактическая единица: кратчайшие пути | ||
Задачи поиска кратчайших путей. Представление кратчайших путей. Деревья кратчайших путей. Алгоритм построения кратчайших путей для выделенной вершины: алгоритм Дейкстры, алгоритм Белмана - Форда | 2 | 1, 3, 6, 8, 9 |
Алгоритмы нахождения кратчайших путей для всех пар вершин: алгоритм Флойда - Уоршолла, алгоритм Джонсона. | 2 | 1, 3, 6, 8, 9 |
Лабораторная работа Таблица 4.2
(Модуль), дидактическая единица, тема | Учебная деятельность | Часы | Ссылки на цели |
Семестр: 5 | |||
Модуль: базовые структуры данных: стеки, очереди, списки | |||
Дидактическая единица: линейные структуры данных: стек, очередь, дек, список | |||
Коллекция данных - список | 4 | 10, 11, 2, 5, 6, 8, 9 | |
Модуль: деревья поиска и алгоритмы для двоичных деревьев поиска | |||
Дидактическая единица: бинарные деревья поиска, случайные, оптимальные, сбалансированные по высоте (АВЛ) и рандомизированные деревья, 2-3 деревья, 2-3-4-деревья, RB - деревья поиска | |||
Коллекция данных - дерево поиска | 4 | 10, 11, 5, 6, 8, 9 | |
Модуль: сбалансированные деревья поиска | |||
Дидактическая единица: бинарные деревья поиска, случайные, оптимальные, сбалансированные по высоте (АВЛ) и рандомизированные деревья, 2-3 деревья, 2-3-4-деревья, RB - деревья поиска | |||
Коллекция данных - сбалансированное дерево поиска | 4 | 10, 11, 5, 6, 8, 9 | |
Модуль: хэш-таблицы | |||
Дидактическая единица: быстрый поиск: бинарный поиск, хеширование | |||
Коллекция данных - хеш - таблица | 4 | 10, 11, 5, 6, 8, 9 |
5. Самостоятельная работа студентов
Семестр - 5, Индив. работа
Освоение технологии проектирования и реализации Абстрактных Типов Данных, реализующих множества данных различных типов (коллекции).
Изучение методов аттестации программного обеспечения, основ тестирования, включая создание плана тестирования и генерации тестовых сценариев.
Семестр - 5, Подготовка к занятиям
Поиск и изучение теоретического материала (модули 1 - 7), необходимого для усваивания лекционного курса, выполнения заданий к лабораторным работам.
Проектирование, программирование и отладка классов для коллекций, проектируемых в рамках лабораторных занятий.
Эмпирическое исследование эффективности реализации коллекции.
Семестр- 6, : Подготовка к зачету
Изучение теоретического материала по разделу курса "Графы" (модули 8 - 14).
Семестр - 6, РГЗ
Цель РГЗ - освоение технологии разработки комплексного программного обес-печения для решения задач в заданной прикладной области.
Задание к РГЗ включает проектирование и реализацию универсальной программной коллекции для АТД "Граф" и использование коллекции для решения различных задач для неориентированных, ориентированных и взвешенных графов.
Семестр - 6, Подготовка к занятиям
Поиск и изучение теоретического материала (модули 8 - 14), необходимого для усваивания лекционного курса и выполнения задания по РГЗ.
Правила аттестации студентов по учебной дисциплине
5 семестр
Правила текущей аттестации:
1. В течение пятого семестра необходимо представить и защитить 4 лабораторных работы, установленные учебным графиком (см. таблицу в разделе 9).
2. К защите лабораторных работ допускаются студенты, выполнившие лабораторные работы в полном объеме (все задания согласно варианту) и оформившие отчет по работе в соответствии с требованиями.
3. На защите предлагается один теоретический вопрос и два практических вопроса (по заданию преподавателя).
4. Максимальное количество баллов (12 или 22 - 24 в зависимости от вида работы) выставляется, если студент полностью ответил на все вопросы, без серьезных замечаний и недочетов.
5. Количество баллов 8-10 или 16-20 (в зависимости от вида работы) выставляется, если студент полностью ответил на два вопроса из трех, причем один из вопросов - практический.
6. Минимальное количество баллов 6 или 12-13 (в зависимости от вида работы) выставляется, если студент ответил один вопрос из трех частично, с серьезными замечаниями, недочетами.
7. Назначается пересдача лабораторной работы, если студент не ориентируется в учебном материале, не может объяснить ход и результаты выполнения работы. В случае пересдачи работы происходит потеря баллов (максимальное количество баллов составляет 10 или 20 в зависимости от вида работы).
8. В случае представления и защиты работ с опозданием от учебного графика происходит потеря баллов (опоздание на 1 неделю - потеря 2 или 4 баллов в зависимости от вида работы, опоздание на 2 недели - потеря 4 или 8 баллов, 3 недели и более - потеря 50% баллов от максимально возможного).
Правила итоговой аттестации:
1. К экзамену допускаются студенты, сдавшие лабораторные работы и набравшие не менее 40% (24 баллов) по результатам текущей аттестации.
2. Экзамен проводится в письменном виде, предлагается одна задача и один теоретический вопрос (образцы заданий в экзаменационном билете приведены в разделе 8).
3. Максимальное количество 36-40 баллов выставляется, если оба задания выполнены полностью, без серьезных замечаний.
4. Количество баллов 30-35 выставляется, если успешно выполнено одно задание из двух, причем отвеченный вопрос - практический (решена задача).
5. Минимальное количество баллов 20-29 выставляется, если выполнено одно теоретическое задание, но с серьезными ошибками, замечаниями, недочетами.
6. Возможно получить "автомат" (отлично) по дисциплине без сдачи экзамена, если студент в течение семестра выполняет дополнительные задания повышенной сложности и набирает свыше 90 баллов по текущему рейтингу.
6 семестр
Правила текущей аттестации:
1. В течение 6-го семестра обучения (до 15 учебной недели) необходимо представить и защитить расчетно - графическое задание согласно варианту (см. задание и примеры вариантов в разделе 9).
2. Максимальное количество баллов 55- 70 выставляется в случае, если успешно выполнены пункты 1- 3 задания при условии соответствующей защиты.
3. Количество баллов 41-54 выставляется в случае, если успешно выполнены пункты 1, и один из пунктов 2-3 при условии соответствующей защиты.
4. Минимальное количество баллов 35-40 выставляется в случае, если успешно выполнен пункт 1.
5. В случае пересдачи или представления и защиты работы с опозданием от учебного графика происходит потеря баллов (опоздание на 1 неделю - потеря 10 баллов, опоздание на 2 недели - потеря 20 баллов, 3 недели и более - потеря 30 - 35 баллов).
Правила итоговой аттестации:
1. К зачету допускаются студенты, сдавшие и защитившие РГЗ и набравшие не менее 35 баллов по результатам текущей аттестации.
2. Зачет проводится в устной форме, предлагаются один теоретический вопрос и одно задание (образец задания приведен в разделе 8).
3. Максимальное количество 25 -30 баллов выставляется, если оба задания выполнены полностью, без серьезных замечаний.
4. Количество баллов 11-24 выставляется, если успешно выполнено одно задание из двух, причем отвеченный вопрос - практический (решена задача).
5. Минимальное количество баллов 5-10 выставляется, если выполнено одно теоретическое задание, но с серьезными ошибками, замечаниями, недочетами.
Подробная таблица бально - рейтинговой оценки выполнения лабораторных работ и РГЗ приведена в разделе 9.
Список литературы
7.1 Основная литература
В печатном виде
1. Алгоритмы и структуры данных : с примерами на Паскале / Никлаус Вирт ; [пер. с англ. ]. - СПб., 2007. - 350, [1] с. : ил.
2. Хусаинов и алгоритмы обработки данных. Примеры на языке Си : учебное пособие / . - М., 2004. - 463, [1] с. : ил. + 1 CD-ROM. - Рекомендовано УМО.
3. Основы современных алгоритмов : учебное пособие по направлению "Информатика и вычислительная техника" / Дж. Макконелл ; пер. с англ. под ред. ; доп. . - М., 2006. - 366 с. : ил.
7.2 Дополнительная литература
В печатном виде
1. Кнут программирования. Т. 1, вып. 1 / Кнут. - М. [и др.], 2007. - 150 с.
2. Кнут программирования. Т. 1 : пер. с англ. / Кнут ; под общ. ред. . - М. [и др.], 2007. - 712 с. : ил.
3. Кнут программирования. Т. 3 / Кнут; под общ. ред. ; [пер. с англ. и ред. , ]. - М. [и др.], 2000. - 822 с. : ил., табл.. - На обл.: Классический труд. Исправленное и дополненное издание.
4. Ахо данных и алгоритмы / Ахо, Хопкрофт, Ульман ; пер. с англ. и ред. . - М., 2001. - 382 с. : ил.
5. Алгоритмы: построение и анализ / Т. Кормен, Ч. Лейзерсон, Р. Ривест ; [пер. с англ. К. Белов и др. ; под ред. А. Шеня]. - М., 1999. - 955 с. : ил.
6. Бакнелл алгоритмы и структуры данных в Delphi : [пер. с англ.] / Джулиан Бакнелл. - СПб., 2006. - 556 с.
7. Левитин : введение в разработку и анализ : [пер. с англ.] / . – М. [и др.] : Диалектика : Вильямс, 2006. – 574 с. : ил.
8. Гагарина и структуры данных / , . – М. : Финансы и статистика, Инфра-М, 2011. – 304 с.
9. Кнут программирования. Т. 1. Основные алгоритмы / . – 3-е изд. – М. : ИД Вильямс, 2011. – 720 с.
10. Алгоритмы на С++ : анализ, структуры данных, сортировка, поиск, алгоритмы на графах : [пер. с англ.] / Р. Седжвик. – М. [и др.] : Вильямс, 2011. – 1056 с. : ил.
8. Методическое и программное обеспечение
8.1 Методическое обеспечение
В печатном виде
1. Романенко и реализация коллекций данных : учебно-методическое пособие / ; Новосиб. гос. техн. ун-т. - Новосибирск, 2005. - 110, [1] с. : ил.
В электронном виде
1. Романенко и реализация коллекций данных : учебно-методическое пособие / ; Новосиб. гос. техн. ун-т. - Новосибирск, 2005. - 110, [1] с. : ил.. - Режим доступа: http://www. ciu. nstu. ru/fulltext/textbooks/2005/05_romanenko. rar
9. Контролирующие материалы для аттестации студентов по дисциплине
Контролирующие материалы к лабораторным работам (5 семестр).
Для проведения защит лабораторных работ используются контрольные вопросы и задания:
Образцы вопросов и заданий:
1. Что понимается под средним и худшим случаем работы алгоритма? Приведите примеры.
2. Приведите изображение структуры изначально пустого RB-дерева после рекурсивной вставки ключей 30, 40, 20,.90, 10, 50, 70, 60, 80.
31. Приведите размер хеш-таблицы с открытой адресацией, предназначенной для хранения 200 элементов, если она использует мультипликативный метод хеширования, модульный метод хеширования.
Контролирующие материалы к итоговому экзамену (5 семестр).
Для проведения экзамена используются экзаменационные вопросы и задания, составленные по курсу лекций дисциплины за 5 семестр.
Образцы вопросов:
1. АВЛ - дерево поиска. Алгоритм удаления элементов, эффективность операций в АВЛ-дереве.
2. Разновидности функций расстановки в хеш-таблицах, преобразования ключей для хеширования.
3. Структуры внешнего поиска. Основные принципы организации структур внешнего поиска. Разреженный индексный файл. Эффективность операций.
Образцы заданий:
Образец 1.
Приведите краткое описание структуры данных и алгоритмов, заданных псевдоко-дами:
назначение алгоритмов,
назначение вспомогательного алгоритма,
нотация трудоемкости алгоритмов.
Selection_Sort (A, n)
1. for i <- 1 to n-1
2. do imin <- i
3. for j <- i+1 to n
4. do if A[j]<A[imin]
5. then imin <- j
6. temp <- A[imin]
7. A[imin] <- A[i]
8. A[i] <- temp
Heap_Sort (A, n)
1. l <- 1
2. r <- n
3. while l >1
4. do l <- l -1
5. Shift (A, l, r)
6. while r >1
7. do x <- A[1]
8. A[1] <- A[r]
9. A[r] <- x
10. r <- r -1
11 Shift (A, 1, r)
Выполните графическую трассировку алгоритма Heap_Sort (по результатам повторе-ний циклов 4 - 6 и 7 - 12 с отображением переменных A, L, R) для следующих данных: 11 1 23 17 4 5 16 4 12 7
Образец 2.
Приведите краткое описание структуры данных и алгоритмов, заданных псевдокодами:
назначение структуры данных,
основные операции,
схема программного представления структуры,
назначение алгоритмов,
назначение вспомогательных алгоритмов,
нотация трудоемкости алгоритма BST_Predecessor.
BST_Predecessor(t, x)
1 if left[x] не равно nil
2 then return Max(left[x])
3 else
4 return R_Parent (t, x)
Max (t)
1 if t=nil then return nil
2 while right[t] не равно nil
3 do t <- right[t]
4 return t
R_Parent(t, x)
1 t-корень дерева/поддерева
2 x-заданный узел дерева
3 if t = x then return nil
4 if key[x] > key[t]
5 then rp <- R_Parent(right[t],x)
6 if rp не равно nil then return rp
7 else return t
8 else return R_Parent(left[t], x)
На заданной схеме дерева для помеченных элементов структуры пометьте теми же метками результаты работы алгоритма.
Контролирующие материалы к зачету (6 семестр).
Для проведения зачета в 6 семестре используются вопросы и задания, составленные по курсу лекций дисциплины (модули 8 - 14).
Образец:
Приведите краткое описание структуры данных и алгоритма, заданного псевдокодом:
назначение структуры данных,
схема программного представления структуры,
назначение алгоритма,
назначение, операции и схема программного представления вспомогательной структуры,
нотация трудоемкости алгоритма MST_Prim.
MST_Prim(G, W, s)
1. W - весовая функция
2. Q <- {V[G]}
3. for (для)каждой вершины u из Q
4. do pr[u] <- "бесконечность"
5. pr[r] <- 0
6. pr[r] <- nil
7. while Q не пуста
8. do u <- Deque (Q)
9. for (для) каждой вершины из Adj[u]
10. do if v находится в Q и w(u, v) < pr[v]
11. then p[v] <- u
12. pr[v] <- w(u, v)
Для заданной структуры приведите результат вызова алгоритма MST_Prim (G, 5) (p[u] и pr[u] для каждой вершины). Приведите последовательность выбираемых элементов структуры.
Задание к РГЗ включает проектирование и реализацию универсальной программной коллекции для АТД «Граф» и использование коллекции для решения различных задач для неориентированных, ориентированных и взвешенных графов.
Цель РГР – освоение технологии разработки комплексного программного беспечения для решения задач в заданной прикладной области.
Образец задания к РГЗ:
1. Разработать АТД «Простой граф».
Интерфейс АТД «Простой граф» включает операции:
Конструктор пустого графа для заданных числа вершин, типа, и формы представления
V( ) - опрос числа вершин в графе,
E( ) - опрос числа ребер в графе,
Directed( ) опрос типа графа (ориентированный / неориентированный)
Dense опрос формы представления графа (L - граф / M- граф),
ToListGraph() преобразование графа к L - графу,
ToMatrixGraph() преобразование графа к M - графу,
Insert(v1,v2) вставка ребра, соединяющего вершины v1, v2,
Delete (v1,v2) удаление ребра, соединяющего вершины v1, v2,
Edge(v1,v2) опрос наличия ребра, соединяющего вершины v1, v2,
SetEdge(v1,v2, data) задание параметров ребра,
Iterator(v) создание итератора смежных вершин для вершины v,
Iterator. beg( ) установка итератора на первую смежную вершину,
Iterator. off( ) опрос окончания просмотра смежных вершин,
Iterator. next( ) переход к следующей смежной вершине,
operator * доступ к данным текущего ребра.
2. Задача 1. На основе АТД «Простой граф» реализовать интерфейс для реализации алгоритма, заданного вариантом.
Пример варианта алгоритма: формирование двудольного неориентированного графа.
Пример варианта алгоритма: обратная топологическая сортировка ациклического орграфа.
3. Задача 2. На основе АТД «Простой граф» реализовать интерфейс взвешенного графа для реализации алгоритма, заданного вариантом.
Пример варианта алгоритма: определение списка вершин, которые лежат в пределах заданного расстояния d от заданной вершины взвешенного орграфа на основе алгоритма Дейкстры.
Требования к оформлению пояснительной записки к РГР.
Пояснительная записка по РГР должна содержать:
· титульный лист,
· содержание,
· общее задание к РГР и варианты для задач 1, 2,
· описание схемы взаимосвязи объектов, предназначенных для реализации графа и задач 1, 2,
· АТД « Простой граф»,
· АТД вспомогательных объектов для решения задач 1, 2,,
· описание методов и алгоритмов решения задач 1, 2,
· описание интерфейса демонстрационной программы,
· заключение,
· список литературы,
· приложение с текстами реализации графа, задач 1, 2,
