1. ЦЕЛИ И ЗАДАЧИ ДИСЦИПЛИНЫ
Целью курса является освоение обучаемыми мирового опыта построения моделей сложных объектов программирования и выработка практических навыков применения этих знаний.
Задачами дисциплины являются описание основных структур данных и алгоритмов их обработки в современном программировании.
2. МЕСТО ДИСЦИПЛИНЫ В СТРУКТУРЕ ООП
2.1. Междисциплинарные связи с обеспечивающими (предыдущими) дисциплинами
Программирование. Специальные разделы информатики
2.2. Междисциплинарные связи с обеспечиваемыми (последующими) дисциплинами
Компьютерное моделирование
3. ТРЕБОВАНИЯ К РЕЗУЛЬТАТАМ ОСВОЕНИЯ ДИСЦИПЛИНЫ
В результате освоения дисциплины студент должен:
Знать:
основные понятия и методы современного программированияУметь:
реализовывать алгоритмы обработки основных структур данных в современном программировании
Владеть:
навыками работы со сложными объектами в программировании
4. ОБЪЕМ ДИСЦИПЛИНЫ И ВИДЫ УЧЕБНОЙ РАБОТЫ
Виды учебной работы по дисциплине и формы итогового контроля знаний, соответствующие данной образовательной программе, с разбивкой объема работы по часам и семестрам для существующих форм обучения приведены в табл. 4.1.
Таблица 4.1. Трудоемкость дисциплины в академических часах для очной формы обучения
Виды учебной работы, формы контроля | Всего, час. | Учебные семестры |
N4 | ||
Общая трудоемкость по учебному плану | 110 | 110 |
Аудиторные занятия | 68 | 68 |
Лекции (Л) | 34 | 34 |
Практические занятия (ПЗ) | 34 | 34 |
Лабораторные работы (ЛР) | 0 | |
Самостоятельная работа студентов (СРС) | 42 | 42 |
кол-во контр. меропр. | 0 | 0 |
объем в часах | 0 | 0 |
Курсовой проект (КП) | 0 | |
Курсовая работа (КР) | 0 | |
Расч.-граф. работа (РГР) | 40 | 2 |
Расчетная работа (РР) | 0 | |
Графическая работа (ГР) | 0 | |
Домашняя работа (ДР) | 0 | |
Реферат | 0 | |
Коллоквиум | 0 | |
Контрольная работа | 0 | |
Подготовка к ауд. занятиям | 0 | 0 |
Вид промежуточного контроля | 0 | 0 |
Зачет (З) | 2 | 2 |
Экзамен (Э) | 0 | |
Зачет дифференцир. (ЗД) | 0 | |
Трудоемкость в зачетных единицах | 3 | 3 |
5. СОДЕРЖАНИЕ ДИСЦИПЛИНЫ
5.1 Содержание разделов дисциплины
5.1.1 Представление чисел
Двоичное кодирование в позиционной системе счисления. Обратный и дополнительный код для отрицательных целых чисел. Арифметические операции над целыми в дополнительном коде. Представление целых произвольной длины и операции над ними. Представление вещественных с фиксированной и плавающей точкой. Арифметические операции сложения и умножения над вещественными. Потеря значащих цифр.
5.1.2 Массивы и структуры. Строки
Размещение структурных значений. Выравнивание и упаковка. Порядок размещения элементов массива памяти. Индексация. Массивы с постоянными границами. Массивы с динамическими границами. Косвенная адресация. Базовый адрес и смещение. Паспорт (дескриптор) массива. Массивы с изменяемыми размерами и/или размерностью. Строки с объявленным максимальным размером. Списковое представление строк. Символьный пул для представления строк в языках обработки строк.
5.1.3 Представление процедур
Структура стека вызовов процедур. Хранение в стеке параметров и локальных переменных. Структура фрейма процедуры. Связь фреймов в динамическую цепочку (цепочку вызовов) и статическую цепочку (контекст). Хранение и преобразование контекстов при процедурных переходах. Представление процедуры как хранимого объекта. Запоминание контекста.
5.1.4 Представление объектов
Поля и методы объектов. Наследование. Таблица виртуальных методов. Динамические свойства объектов. Проблемы множественного наследования.
5.1.5 Представление списковых структур
Стек и его представление в виде массива и списка. Стеки, растущие «навстречу» друг другу. Очереди и их реализация. Примеры применения стеков и очередей.
5.1.6 Деревья, их использование и алгоритмы их обработки
Реализация АТД "Дерево" с помощью реляционной таблицы. Улучшение реализации АТД "Дерево" путём добавления списков сыновей. Улучшение реализации АТД "Дерево" путём добавления списков левых сыновей и правых братьев. Двоичные деревья. Коды Хаффмана. Двоичные деревья поиска. Вставка и удаление элементов. Двоичные деревья поиска. Среднее время выполнения операторов. Частично упорядоченные сбалансированные деревья. Вставка и удаление элементов. Реализация очереди с приоритетами с помощью heap-массива (куча). АТД "Множество". Словари. Реализации словарей.
5.1.7 Хэширование
Закрытое хэширование. Повторное хэширование. Вставка и удаление элементов. Анализ закрытого хэширования. Реструктуризация хэш-таблиц. Деревья. Вставка и удаление элементов.
5.1.8 Орграфы
Орграфы (определения, терминология). Представления орграфов. Задача нахождения кратчайшего пути с одним источником. Алгоритм Дейкстры. Анализ времени выполнения алгоритма Дейкстры. Общая задача нахождения кратчайших путей. Варианты решения. Алгоритм Флойда для решения общей задачи нахождения кратчайших путей. Транзитивное замыкание орграфа. Алгоритм Уоршелла. Эксцентриситет вершины орграфа. Нахождение центра орграфа. Обход вершин орграфа методом поиска в глубину. Глубинный остовной лес. Типы дуг. Время построения. Проверка ацикличности орграфа. Алгоритм нахождения сильно связных компонент (без доказательства).
5.1.9 Графы
Графы (определения, терминология). Представления обыкновенных графов. Остовные деревья минимальной стоимости. Алгоритм Прима. Остовные деревья минимальной стоимости. Алгоритм Крускала.. Обход графов методом поиска в глубину. Обход графов методом поиска в ширину.
5.2 Разделы дисциплины и виды занятий
Перечень разделов дисциплины с указанием трудоемкости их освоения в академических часах, видов учебной работы с учетом существующих форм освоения приведен в табл. 5.1.
Таблица 5.1 - Перечень разделов дисциплины с указанием трудоемкости их освоения для очной формы обучения
Разделы дисциплины | Трудоемкость освоения раздела дисциплины, час. | ||||||||||||||||
Номер раздела | Наименова-ние раздела | Семестр изучения | Общая трудоемкость раздела, час | Аудиторные занятия по данному разделу, час | Лекции | Практические занятия | Лабораторные работы | Самостоятельная работа студентов | Курсовой проект (КП) | Курсовая работа (КР) | Расчетно-граф. работа (РГР) | Расчетная работа (РР) | Контрольная работа (КР) | Домашняя работа (ДР) | Реферат | Коллоквиум | Подготовка к ауд. занятиям |
1 | Представление чисел | 5 | 4 | 2 | 2 | 1 | 1,4 | ||||||||||
2 | Массивы и структуры. Строки. | 11 | 8 | 4 | 4 | 3 | 1 | 2,8 | |||||||||
3 | Представление процедур | 11 | 8 | 4 | 4 | 3 | 2,8 | ||||||||||
4 | Представление объектов | 11 | 8 | 4 | 4 | 3 | 2,8 | ||||||||||
5 | Представление списковых структур | 11 | 8 | 4 | 4 | 3 | 2,8 | ||||||||||
6 | Деревья, их использование и алгоритмы их обработки | 11 | 8 | 4 | 4 | 3 | 1 | 2,8 | |||||||||
7 | Хэширование | 11 | 8 | 4 | 4 | 3 | 2,8 | ||||||||||
8 | Орграфы | 11 | 8 | 4 | 4 | 3 | 2,8 | ||||||||||
9 | Графы | 11 | 8 | 4 | 4 | 3 | 2,8 | ||||||||||
Итого по дисциплине | 92 | 68 | 34 | 34 | 0 | 24 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 24 |
6. ПРАКТИЧЕСКИЕ ЗАНЯТИЯ И САМОСТОЯТЕЛЬНАЯ РАБОТА
6.1. Лабораторный практикум
Не предусмотрено учебным планом
6.2. Практические занятия
Примерные темы практических занятий с указанием разделов дисциплины, к которым они относятся, приведены в табл. 6.2.
Таблица 6.2 - Распределение практических работ по разделам дисциплины для очной формы обучения
Номер работы | Номер раздела | Тема занятия | Время на выполнение работы, час |
1 | 1 | Номер раздела | 2 |
2 | 2 | Представление чисел | 4 |
3 | 3 | Массивы и структуры. Строки. | 4 |
4 | 4 | Представление процедур | 4 |
5 | 5 | Представление объектов | 4 |
6 | 6 | Представление списковых структур | 4 |
7 | 7 | Деревья, их использование и алгоритмы их обработки | 4 |
8 | 8 | Хэширование | 4 |
9 | 9 | Орграфы | 4 |
6.3. Перечень тем рефератов
[список]
6.4 Перечень тем домашних работ
[список]
6.5 Перечень тем контрольных работ
[список]
6.6 Перечень тем расчетных работ
[список]
6.7 Перечень тем расчетно-графических работ
1. Реализация АТД “Дерево” различными способами. Сравнение времени выполнения операций вставки, удаления и поиска элементов в дереве. Анализ результатов.
3. Задача нахождения кратчайшего пути с одним источником. Алгоритм Дейкстры.
4. Алгоритм Флойда для решения общей задачи нахождения кратчайших путей.
6.8 Тематика коллоквиумов
[список]
7. Тематика курсового проектирования
[текст]
8. УЧЕБНО-МЕТОДИЧЕСКОЕ ОБЕСПЕЧЕНИЕ
8.1 Рекомендуемая литература
8.1.1 Основная литература
1. Хопкрофт Дж., Ульман Дж. Структуры данных и алгоритмы, 2000 г.
2. Искусство программирования, т.1-3. «Вильямс», Москва-Петербург-Киев, 2000 г.
8.1.2 Дополнительная литература
лгоритмы + структуры данных = программы. М.:Мир, 1985.8.1.3 Методические разработки кафедры
8.2 Программное обеспечение
Microsoft Visual 2003 Microsoft Windows Script Host 5.68.3 Базы данных, информационно-справочные и поисковые системы
http://www. intuit. ru/ - Национальный открытый университет «ИНТУИТ»
http://www. edu. ru/ - Федеральный портал. Российское образование.
http://study. ustu. ru –портал информационно-образовательных ресурсов УрФУ
http://rtf. ustu. ru - официальный сайт ИРИТ-РтФ
http://vmumf. rtf. ustu. ru –официальный сайт кафедры ВМиУМФ
9. МАТЕРИАЛЬНО-ТЕХНИЧЕСКОЕ ОБЕСПЕЧЕНИЕ ДИСЦИПЛИНЫ
9.1 Общие требования
Компьютерный класс, оборудованный для проведения лекционных и практических занятий средствами оргтехники, персональными компьютерами, объединенными в сеть, имеющей выход в Интернет
9.2 Сведения об оснащенности дисциплины специализированным и лабораторным оборудованием
Специально оборудованные аудитории института радиоэлектроники и информационных технологий - РТФ: Р-402, Р-135.
10. МЕТОДИЧЕСКИЕ РЕКОМЕНДАЦИИ ПО ИЗУЧЕНИЮ ДИСЦИПЛИНЫ
10.1 Рекомендации для преподавателя
Рекомендации для преподавателя включают в себя следующее:
• глубокое освоение теоретических аспектов тематики курса, поиск, подбор и изучение литературных источников; составление списка литературы, обязательной для изучения и дополнительной литературы;
• разработку методики изложения курса: структуры и последовательности изложения материала; составление тестовых заданий, контрольных вопросов;
• разработку методики проведения и совершенствование тематики практических работ; использование в практикуме реальных данных и получение результатов, имеющих практический смысл для будущей практической деятельности инженера;
• разработка методики самостоятельной работы студентов;
• постоянную корректировку структуры, содержания курса.
10.2 Рекомендации для студента
Рекомендации для студента включают в себя следующее:
• обязательное посещение лекций ведущего преподавателя; лекции – основное методическое руководство при изучении дисциплины, наиболее оптимальным образом структурированное и скорректированное на современный материал;
• в лекции глубоко и подробно, аргументировано и методологически строго рассматриваются главные проблемы темы;
• в лекции даются необходимые разные подходы к исследуемым проблемам;
• подготовку и активную работу на практических занятиях; подготовка к ним включает проработку материалов лекций, рекомендованной учебной литературы
10.3 Перечень контрольных вопросов для подготовки к итоговой аттестации по дисциплине
Двоичное кодирование в позиционной системе счисления. Обратный и дополнительный код для отрицательных целых чисел. Арифметические операции над целыми в дополнительном коде. Представление целых произвольной длины и операции над ними. Представление вещественных с фиксированной и плавающей точкой. Арифметические операции сложения и умножения над вещественными. Потеря значащих цифр. Размещение структурных значений. Выравнивание и упаковка. Порядок размещения элементов массива памяти. Индексация. Массивы с постоянными границами. Массивы с динамическими границами. Косвенная адресация. Базовый адрес и смещение. Паспорт (дескриптор) массива. Массивы с изменяемыми размерами и/или размерностью. Строки с объявленным максимальным размером. Списковое представление строк. Символьный пул для представления строк в языках обработки строк. Структура стека вызовов процедур. Хранение в стеке параметров и локальных переменных. Структура фрейма процедуры. Связь фреймов в динамическую цепочку (цепочку вызовов) и статическую цепочку (контекст). Хранение и преобразование контекстов при процедурных переходах. Представление процедуры как хранимого объекта. Запоминание контекста. Поля и методы объектов. Наследование. Таблица виртуальных методов. Динамические свойства объектов. Проблемы множественного наследования. Стек и его представление в виде массива и списка. Стеки, растущие «навстречу» друг другу. Очереди и их реализация. Примеры применения стеков и очередей. Реализация АТД "Дерево" с помощью реляционной таблицы. Улучшение реализации АТД "Дерево" путём добавления списков сыновей. Улучшение реализации АТД "Дерево" путём добавления списков левых сыновей и правых братьев. Двоичные деревья. Коды Хаффмана. Двоичные деревья поиска. Вставка и удаление элементов. Двоичные деревья поиска. Среднее время выполнения операторов. Частично упорядоченные сбалансированные деревья. Вставка и удаление элементов. Реализация очереди с приоритетами с помощью heap-массива (куча). АТД "Множество". Словари. Реализации словарей. Закрытое хэширование. Повторное хэширование. Вставка и удаление элементов. Анализ закрытого хэширования. Реструктуризация хэш-таблиц. Деревья. Вставка и удаление элементов. Орграфы (определения, терминология). Представления орграфов. Задача нахождения кратчайшего пути с одним источником. Алгоритм Дейкстры. Анализ времени выполнения алгоритма Дейкстры. Общая задача нахождения кратчайших путей. Варианты решения. Алгоритм Флойда для решения общей задачи нахождения кратчайших путей. Транзитивное замыкание орграфа. Алгоритм Уоршелла. Эксцентриситет вершины орграфа. Нахождение центра орграфа. Обход вершин орграфа методом поиска в глубину. Глубинный остовной лес. Типы дуг. Время построения. Проверка ацикличности орграфа. Алгоритм нахождения сильно связных компонент (без доказательства). Графы (определения, терминология). Представления обыкновенных графов. Остовные деревья минимальной стоимости. Алгоритм Прима. Остовные деревья минимальной стоимости. Алгоритм Крускала. Обход графов методом поиска в глубину. Обход графов методом поиска в ширину.Перечень ключевых слов дисциплины
Таблица 10.4. Ключевые слова
№ раздела | № модуля | Наименование раздела | Ключевые слова раздела |
1 | Представление чисел. | кодирование, арифметические операции, числа с фиксированной и плавающей точкой | |
2 | Массивы и структуры. Строки | структурные значения, выравнивание, упаковка, индексация, паспорт массива | |
3 | Представление процедур | стек вызова процедур, фрейм, цепочка вызовов, контекст | |
4 | Представление объектов. | наследование, виртуальные методы | |
5 | Представление списковых структур. | массив, списки, стеки, очереди | |
6 | Деревья, их использование и алгоритмы их обработки | реляционная таблица, список сыновей, АТД "Дерево", двоичные деревья, словари | |
7 | Хэширование. | хэширование, вставка/удаление элементов, хэш-таблица, деревья | |
8 | Орграфы. | орграфы, алгоритм Флойда, остовной лес, дуга, сильно связные компоненты | |
9 | Графы | графы, остовные деревья, поиск в глубину и в ширину |
СОДЕРЖАНИЕ
1. ЦЕЛИ И ЗАДАЧИ ДИСЦИПЛИНЫ 3
2. МЕСТО ДИСЦИПЛИНЫ В СТРУКТУРЕ ООП 3
2.2. Междисциплинарные связи с обеспечиваемыми (последующими) дисциплинами 3
3. ТРЕБОВАНИЯ К РЕЗУЛЬТАТАМ ОСВОЕНИЯ ДИСЦИПЛИНЫ 3
4. ОБЪЕМ ДИСЦИПЛИНЫ И ВИДЫ УЧЕБНОЙ РАБОТЫ 3
5. СОДЕРЖАНИЕ ДИСЦИПЛИНЫ 4
5.1 Содержание разделов дисциплины 4
5.1.1 Представление чисел 4
5.1.2 Массивы и структуры. Строки 4
5.1.3 Представление процедур 4
5.1.4 Представление объектов 4
5.1.5 Представление списковых структур 5
5.1.6 Деревья, их использование и алгоритмы их обработки 5
5.1.7 Хэширование 5
5.1.8 Орграфы 5
5.1.9 Графы 5
5.2 Разделы дисциплины и виды занятий 5
6. ПРАКТИЧЕСКИЕ ЗАНЯТИЯ И САМОСТОЯТЕЛЬНАЯ РАБОТА 6
6.1. Лабораторный практикум 6
6.2. Практические занятия 6
6.3. Перечень тем рефератов 7
6.4 Перечень тем домашних работ 7
6.5 Перечень тем контрольных работ 7
6.6 Перечень тем расчетных работ 7
6.7 Перечень тем расчетно-графических работ 7
6.8 Тематика коллоквиумов 7
7. Тематика курсового проектирования 7
8. УЧЕБНО-МЕТОДИЧЕСКОЕ ОБЕСПЕЧЕНИЕ 7
8.1 Рекомендуемая литература 7
8.1.1 Основная литература 7
8.1.2 Дополнительная литература 7
8.1.3 Методические разработки кафедры 8
8.2 Программное обеспечение 8
8.3 Базы данных, информационно-справочные и поисковые системы 8
9. МАТЕРИАЛЬНО-ТЕХНИЧЕСКОЕ ОБЕСПЕЧЕНИЕ ДИСЦИПЛИНЫ 8
9.1 Общие требования 8
9.2 Сведения об оснащенности дисциплины специализированным и лабораторным оборудованием 8
10. МЕТОДИЧЕСКИЕ РЕКОМЕНДАЦИИ ПО ИЗУЧЕНИЮ ДИСЦИПЛИНЫ 8
10.1 Рекомендации для преподавателя 8
10.2 Рекомендации для студента 8
10.3 Перечень контрольных вопросов для подготовки к итоговой аттестации по дисциплине 8
10.4 Перечень ключевых слов дисциплины 10
