Порядок сдачи и защиты курсового проекта
Нормативный срок сдачи КР – предзачетная неделя семестра.
Студент допускается к защите после проверки пояснительной записки преподавателем. При обнаружении серьезных ошибок и упущений записка может быть возвращена на доработку.
Защита проекта включает:
1. Краткий доклад студента по результатам выполненного проектирования.
2. Демонстрацию работающих программ на компьютере с пояснениями.
3. Ответы на вопросы преподавателя.
Результаты курсового проектирования оцениваются с учетом:
a) наличия работающих программ и соответствия их п.3;
b) качества выполнения пояснительной записки и соответствия ее п.4;
c) уровня ответов студента.
ЛИТЕРАТУРА
А) основная
1. Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. М.: Мир, 1979.
2. Ахо А., Хопкрофт Дж., Ульман Дж. Структуры данных и алгоритмы. М.: Вильяме, 2001. 384 с.
3. Бентли Д. Жемчужины творчества программистов. М.: Радио и связь, 1990.
4. Вирт Н. Алгоритмы + структуры данных = программы. М.: Мир, 1985.
5. Вирт Н. Алгоритмы и структуры данных. М: Мир, 1989. 360 с.
6. Грин Д., Кнут Д. Математические методы анализа алгоритмов. М: Мир, 1987.
7. Гудман С, Хидетниеми С. Введение в разработку и анализ алгоритмов. М.: Мир, 1981.
8. Дейкстра Э. Дисциплина программирования. М: Мир, 1978.
9. Кнут Д. Е. Искусство программирования: В 3 т. М.: Вильяме, 2000.
10. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: Построение и анализ. М.: МЦНМО, 2001.
|
|
|
В) русскоязычные ресурсы Internet
1. http://algo.4u.ru/
2. http://algolist.manual.ru/
3. http://alglib.chat.ru/
4. http://algo.do.ru/
5. http://hcinsu.chat.ru/
6. http://algolist.da.ru/
7. http://progstone.narod.ru/links/wantalgo.html
8. http://www.sevmashvtuz.edu/links/algorithms.html
9. http://www.intuit.ru/department/algorithms/staldata/
ПРИЛОЖЕНИЕ
Варианты заданий
Вариант выполнения курсовой работы включает три части. Содержанием каждой части является одно из заданий. Описания вариантов приведены в таблице вариантов, описания заданий представлены ниже.
Таблица вариантов
| Номер варианта | Номера заданий | ||
| Часть 1 | Часть 2 | Часть 3 | |
| 1 | 15 | 1 | 2 |
| 2 | 14 | 15 | 3 |
| 3 | 13 | 2 | 4 |
| 4 | 12 | 14 | 15 |
| 5 | 11 | 3 | 14 |
| 6 | 10 | 13 | 13 |
| 7 | 9 | 4 | 5 |
| 8 | 8 | 12 | 6 |
| 9 | 7 | 5 | 7 |
| 10 | 6 | 11 | 12 |
| 11 | 5 | 6 | 11 |
| 12 | 4 | 10 | 10 |
| 13 | 3 | 7 | 1 |
| 14 | 2 | 9 | 8 |
| 15 | 1 | 8 | 9 |
| 16 | 15 | 14 | 9 |
| 17 | 10 | 11 | 8 |
| 18 | 8 | 7 | 13 |
| 19 | 6 | 9 | 12 |
| 20 | 14 | 13 | 6 |
Описания заданий
Часть 1. Задачи на графах
1. Дан ориентированный граф с N вершинами (N<50). Вершины и дуги окрашены в цвета с номерами от 1 до М (М<6). Указаны две вершины, в которых находятся фишки игрока и конечная вершина. Правило перемещения фишек: игрок может передвигать фишку по дуге, если ее цвет совпадает с цветом вершины, в которой находится другая фишка; ходы можно делать только в направлении дуг графа; поочередность ходов необязательна. Игра заканчивается, если одна из фишек достигает конечной вершины. Написать программу поиска кратчайшего пути до конечной вершины, если он существует.
|
|
|
2. Задан неориентированный граф. При прохождении по некоторым ребрам отдельные (определенные заранее) ребра могут исчезать или появляться. Написать программу поиска кратчайшего пути из вершины с номером q в вершину с номером w.
3. Заданы два числа N и М (20<M<N<150), где N — количество точек на плоскости. Написать программу построения дерева из М точек так, чтобы оно было оптимальным.
Примечание. Дерево называется оптимальным, если сумма всех его ребер минимальна. Все ребра — это расстояния между вершинами, заданными координатами точек на плоскости.
4. Даны два числа N и М. Написать программу построения графа из N вершин и М ребер. Каждой вершине ставится в соответствие число ребер, входящих в нее. Граф должен быть таким, чтобы сумма квадратов этих чисел была минимальна.
5. Задан ориентированный граф с N вершинами, каждому ребру которого приписан неотрицательный вес. Написать программу поиска простого цикла, для которого среднее геометрическое весов его ребер было бы минимально.
|
|
|
Примечание. Цикл называется простым, если через каждую вершину он проходит не более одного раза, петли в графе отсутствуют.
6. Внутрь квадрата с координатами левого нижнего угла (0,0) и координатами верхнего правого угла (100, 100) поместили N (1<N<30) квадратиков. Написать программу поиска кратчайшего пути из точки (0,0) в точку (100,100), который бы не пересекал ни одного из этих квадратиков. Ограничения:
· длина стороны каждого квадратика равна 5;
· стороны квадратиков параллельны осям координат;
· координаты всех углов квадратиков — целочисленные;
· квадратики не имеют общих точек.
Примечание. Строится граф из начальной, конечной точек и вершин квадратиков (ребра не должны пересекать квадраты). Затем ищется кратчайший путь, например, с помощью алгоритма Дейкстры.
7. Задан неориентированный граф с N вершинами, пронумерованными целыми числами от 1 до N. Написать программу, которая последовательно решает следующие задачи:
· выясняет количество компонент связности графа;
· находит и выдает все такие ребра, что удаление любого из них ведет к увеличению числа компонент связности;
|
|
|
· определяет, можно ли ориентировать все ребра графа таким образом, чтобы получившийся граф оказался сильно связным;
· ориентирует максимальное количество ребер, чтобы получившийся граф оказался сильно связным;
· определяет минимальное количество ребер, которые следует добавить в граф, чтобы ответ на третий пункт был утвердительным.
8. Задан ориентированный граф с N (1<N<30) вершинами, пронумерованными целыми числами от 1 до N. Разработать программу, которая подсчитывает количество различных путей между всеми парами вершин графа.
9. Задан ориентированный граф с N вершинами, пронумерованными целыми числами от 1 до N. Разработать программу, которая подсчитывает количество различных путей между всеми парами вершин графа.
Входные данные. Входной файл input.txt содержит количество вершин графа N (1<N<30) и список дуг графа, заданных номерами начальной и конечной вершин.
Выходные данные. В выходной файл output.txt вывести матрицу N×N, элемент (i,j) которой равен числу различных путей, ведущих из вершины i в вершину j или -1, если существует бесконечно много таких путей.
10. Дан ориентированный граф. Вершинам приписаны веса. Начальная и конечная вершины заданы. Требуется найти путь между этими вершинами с максимально возможным суммарным весом. Путь должен удовлетворять следующим условиям:
· по каждой дуге разрешается пройти один раз;
· если в вершину попадаем по входящей дуге, то к суммарному весу вес этой вершины прибавляется;
· если в вершину попадаем по выходящей дуге, то из суммарного веса вес этой вершины вычитается.
Входные данные. Входной файл input.txt содержит данные в следующей последовательности:
· N x1 х2 ... xN — количество вершин графа и их веса (1≤N≤30, 1<хi<30000);
· b,e — номера начальной и конечной вершин;
· М — количество дуг;
· i1, j1 — номера вершин, соединяемых первой дугой;
· i2, j2 — номера вершин, соединяемых второй дугой;
· iM, jM — номера вершин, соединяемых дугой с номером М.
Выходные данные. В выходной файл output.txt требуется вывести максимальный вес пути и путь, на котором он достигается. В случае, если решение не существует, выходной файл должен содержать единственную строку «решения нет».
11. Дан взвешенный (ребрам приписаны веса) связный граф G=(V,E).
Обозначим через D{v,u} минимальное расстояние между вершинами v,u € V. Величина D(G) = Max(D(v,u)) называется диаметром графа. Величина R(v) = Max(D(v,u)) максимальным удалением в графе от вершины v. Величину R(G) = Min(R(v)) называют радиусом графа. Любая вершина t€V, такая, что R(t)=R(G), называется центром графа.
Разработать программу поиска диаметра, радиуса и центров графа.
Примечание. Первый шаг решения заключается в формировании матрицы минимальных расстояний между всеми парами вершин графа.
12. Согласно теореме Д. Кенига (1936 г.) для двудольности графа необходимо и достаточно, чтобы он не содержал циклов нечетной длины. Определить, является ли заданный граф двудольным.
Примечание. При поиске в ширину вершины графа помечаются метками 0, 1, 2 и т. д. Первой вершине, с которой начинается просмотр, приписывается метка 0, вершинам, связанным с ней, — метка 1 и т. д. Разобьем граф после просмотра на два подграфа: подграф X включает вершины с четными метками, подграф Y — с нечетными. Если оба подграфа пусты — исходный граф является двудольным.
13. Задача Штейнера на графах. В связном взвешенном графе G с выделенным подмножеством вершин U (U € V) требуется найти связный подграф Т, удовлетворяющий двум условиям:
· множество вершин подграфа Т содержит заданное подмножество U;
· граф Т имеет минимальный вес среди всех подграфов, удовлетворяющих первому условию.
Примечание. Очевидно, что искомый подграф является деревом, оно называется деревом Штейнера. Задача сводится к нахождению дерева минимального веса в подграфах графа G, множество вершин которых содержит U. Эффективных алгоритмов решения задачи неизвестно, поэтому наиболее простой состоит в переборе вариантов при небольших значениях числа вершин.
14. Задача о пяти ферзях. На шахматной доске 8x8 расставить наименьшее число ферзей так, чтобы каждая клетка доски была под боем.
Примечание. Построить граф для данной доски с учетом правил перемещения ферзя. Всякой искомой расстановке соответствует наименьшее доминирующее множество в графе.
15. Для заданного ориентированного графа с N вершинами разработать:
· структуру представления графа;
· процедуру заполнения графа из N узлов;
· процедуру поиска всех путей от заданной вершины ко всем остальным методом в глубину;
· процедуру поиска кратчайших путей от заданной вершины ко всем остальным методом в ширину;
· процедуру построения остового дерева графа.
Дата добавления: 2018-11-24; просмотров: 254; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!