Указания по выполнению расчетно-графической работы
Расчетно-графическая работа выполняется самостоятельно по вариантам. Оценка за контрольную работу учитывается при выставлении зачетной оценки.
Расчетно-графическая работа оформляется согласно принятым в университете требованиям (см. http://narfu.ru/upload/iblock/225/sto_2013.pdf).
Состав РГР:
1. Титульный лист.
2. Лист для замечаний.
3. Лист с заданием и вариантом
4. Описания решенных задач
5. Заключение
6. Список использованных источников
Оформление текста основной части работы
Каждая задача оформляется в следующем порядке:
· Формулировка задачи.
· Алгоритм решения в виде словесного описания, псевдокода или блок-схемы.
· Реализация на С++.
Код программы (в том числе псевдокод) оформляется как рисунок. Нумерация рисунков сквозная, в работе должна присутствовать ссылка на рисунок. Например, листинг кода программы, выводящей строку «Hello, world!», приведен на рисунке 1.
cout<<”Hello, world!<<endl;
Рисунок 1 – Реализация алгоритма «Hello, world!»
В случае невыполнения требований по содержанию и оформлению работы (в том числе по оформлению списка источников) может быть снижена оценка.
Варианты
Задания брать из методички «Практикум на ЭВМ. Структуры данных и алгоритмы», лабораторная работа №4.
Задание №1 – построение остовного дерева указанным методом.
Задания №2 и №3 – индивидуальные задачи.
Таблица 1. Распределение вариантов
| № | Фамилия, Имя | №1 | №2 | №3 |
| Баков Дмитрий | Обход в ширину | |||
| Буштаков Олег | Метод Прима | |||
| Дарноступ Владислав | Обход в глубину | |||
| Журавлева Мария | Метод Краскала | |||
| Зубрецов Виктор | Обход в ширину | |||
| Качаева Хрисия | Метод Краскала | |||
| Мамонтов Николай | Обход в глубину | |||
| Пилипенко Александр | Метод Прима | |||
| Таран Игорь | Обход в ширину | |||
| Ундозерова Маргарита | Метод Прима | |||
| Чемакина Марина | Обход в глубину | |||
| Черепанова Алена | Метод Краскала |
Рекомендуемые источники
Ниже приведен список рекомендуемых источников информации. Разумеется, можно (в некоторых случаях нужно) использовать и другие источники информации. Помните, что Википедия не является релевантным источником!
Список источников обязательно выполняется по действующему ГОСТу. Обратите внимание на оформление электронных источников! Список должен быть отсортирован в алфавитном порядке.
По тексту работы необходимо расставить ссылки на источники информации, которые были использованы для подготовки работы.
Для удобства рекомендуемые источники поделены на несколько групп, однако в РГР необходимо оформить единый список источников.
Учебники и учебно-методическая литература:
1. Павловская, Татьяна Александровна. С/С++. Программирование на языке высокого уровня [Текст]: учебник для студ. вузов, обуч. по напр. "Информатика и вычислит. техника" / Т. А. Павловская. - СПб.: Питер, 2006. (или более позднее издание).
2. Павловская, Татьяна Александровна. С/С++. Структурное программирование [Текст]: практикум / Т. А. Павловская, Ю. А. Щупак. - СПб.: Питер, 2007. - 240 с.: ил. (или более позднее издание).
3. Павловская, Татьяна Александровна. С++. Объективно-ориентированное программирование [Текст]: практикум: учеб. пособие для студ. вузов, обуч. по напр. подгот. дипломир. спец. "Информатика и вычислит. техника" / Т. А. Павловская, Ю. А. Щупак. - СПб.: Питер, 2006. - 264 с. (или более позднее издание).
4. Лаптев, Валерий Викторович. C++. Объектно-ориентированное программирование [Текст]: задачи и упражнения: учеб. пособие для студ. вузов, обуч. по напр. подгот. "Информатика и вычислит. техника" / В. В. Лаптев, А. В. Морозов, А. В. Бокова. - М.; СПб.; Нижний Новгород: Питер, 2007. - 288 с.: рис.
5. Практикум на ЭВМ. Структуры данных и алгоритмы [Текст] / Е.А. Латухина; Северный (Арктический) федеральный университет им. М.В. Ломоносова. — Архангельск, 2013. — 44 с. (в печати).
Литература по алгоритмам (имеющаяся в библиотеке):
1. Ахо, Альфред В. Структуры данных и алгоритмы [Текст]: пер. с англ. / А. В. Ахо, Д. Э. Хопкрофт, Д. Д. Ульман; ред., пер. А. А. Минько. - М.: Изд. дом "Вильямс", 2007. - 391[8] с.: рис.
2. Крупский, Владимир Николаевич. Теория алгоритмов [Текст]: учеб. пособие для студ. вузов, обуч. по напр. "Информатика и вычислительная техника", "Информационные системы и технологии" / В. Н. Крупский, В. Е. Плиско. - Москва: Академия, 2009. - 205, [1] с.
3. Алексеев, Владимир Евгеньевич. Графы и алгоритмы. Структуры данных. Модели вычислений [Текст]: учебник для студ., обуч. по спец. 010200 - Прикладная математика и информатика и по напр. 510200 - Прикладная математика и информатика / В. Е. Алексеев, В. А. Таланов. - М.: БИНОМ. ЛЗ; М.: Интернет университет информ. технологий, 2006. - 319 с.
4. Алгоритмы [Текст]: построение и анализ / Т. Кормен [и др.]. - 2-е изд. - М.; СПб.; Киев: ИД "Вильямс", 2005. - 1290[6] с.
5. Кнут, Дональд Э. Искусство программирования [Текст]: пер. с англ. / Д.Э. Кнут; ред. Ю.В. Козаченко. - М.; СПб.; Киев: ИД "Вильямс". - (Классический труд: испр. и доп. изд.). Т. 1, 2, 3, 4.
6. Касьянов, Виктор Николаевич. Графы в программировании: обработка, визуализация и применение [Текст] / В.Н. Касьянов, В.А. Евстигнеев. - СПб.: БХВ-Петербург, 2003. - 1104 с.
7. Вирт Н., Алгоритмы и структуры данных. – СПб.: Невский диалект, 2001 г.
8. Касьянов В.Н., Сабельфельд В.К., Сборник заданий по практикуму на ЭВМ. – М.: Наука, главная редакция физико-математической литературы, 1986 г.
9. Новиков Ф.А. Дискретная математика для программистов. – СПб.: Питер, 2001. – 304 с.: ил.
10. Хусаинов Б.С. Структуры и алгоритмы обработки данных. Примеры на языке Си (+CD): Учебное пособие. – Финансы и статистика, 2004. – 464 с.: ил.
Интернет-ресурсы:
1. Алексеев В. Графы и алгоритмы [Электронный ресурс]. / Алексеев В., Таланов В. – http://www.intuit.ru/studies/courses/101/101/info
2. Костюкова Н. Графы и их применение алгоритмы [Электронный ресурс].– http://www.intuit.ru/studies/courses/58/58/info
3. Швед Д., Алгоритмы: построение и анализ [Электронный ресурс].– http://www.intuit.ru/studies/courses/534/390/info
Балльно-рейтинговая система
Для оценки выполнения РГР используется балльно-рейтинговая система. РГР связана с лабораторной работой №4 и выполняется после нее. К лабораторной работе №4 относятся:
· Задачи на организацию хранения графов (до 5 баллов в сумме).
· Поиск и построение Эйлерова цикла (до 4 баллов).
· Реализация алгоритмов Дейкстры и Флойда (до 3 баллов за каждый).
Итого за лабораторную работу №4 можно получить до 15 баллов.
За каждую задачу РГР можно получить до 5 баллов. Кроме того, за оформление РГР можно получить до 5 баллов. Итого за расчетно-графическую работу можно получить до 20 баллов. Для зачета работы достаточно получить 11 и более баллов.
