М
инистерство
образования Российской Федерации
ФГБОУ ВПО «Сибирский государственный технологический университет»
Кафедра системотехники
Дискретная математика
Сборник заданий
для курсовых работ
с примерами выполнения
для студентов направлений 230400.62, 230100.62, 231000.62 всех форм обучения
Красноярск
2012
Иванилова Т.Н. Дискретная математика: Сборник заданий для курсовых работ с примерами выполнения для студентов направлений 230400.62, 230100.62, 231000.62 всех форм обучения.- Красноярск: СибГТУ, 2012.-27с.
Одобрено и рекомендовано к печати редакционно-издательским советом СибГТУ __________.
Рецензенты
© Сибирский государственный технологический университет, 2012
Введение
Перед выполнением задания, которое выдает преподаватель, студент должен овладеть знаниями по «Дискретной математике», навыками работы в операционной системе Windows, в текстовом редакторе Word, в среде программирования Turbo Pascal.
Для контроля подготовленности студента к выполнению работы приведен перечень контрольных вопросов.
В указаниях к выполнению курсовой работы содержится рекомендуемая последовательность действий для правильного выполнения и оформления отчета. Отчет по выполнению расчетно-графической работы должен быть оформлен в соответствии со стандартами СТП.
1 Задания для курсовой работы
Создайте программную реализацию алгоритм Тэрри для нахождения компонент связности графа.
Создайте программную реализацию алгоритма ”Фронта волны”, в которой наглядно было бы отражено соответствие названия и сути алгоритма (для неориентированного графа).
Создайте программную реализацию алгоритма ”Фронта волны”, в которой наглядно было бы отражено соответствие названия и сути алгоритма (для ориентированного графа).
Вы - директор фирмы, прокладывающей газопровод по местности с несколькими населенными пунктами, которые обязательно должны быть связаны газопроводом. Ваша задача провести предварительное проектирование строительства с минимальными затратами (затраты пропорциональны расстоянию).
Создать программную реализацию алгоритма нахождения остовного дерева графа.
Создать программную реализацию нахождения минимального расстояния в нагруженном графе.
Создать программную реализацию нахождения максимального расстояния в нагруженном орграфе.
Компьютерная фирма, занимающаяся прокладкой кабелей для локальной сети, задумалась над экономией средств - то бишь над уменьшением метража используемого кабеля. Помогите им справиться с этой задачей. Топология сети не ограничивается.
Для произвольного неориентированного графа разработать алгоритм и составить программу, позволяющую выделять в нем цепь, цикл. Граф и количество ребер в данных путях - входные параметры.
Для произвольного неориентированного графа разработать алгоритм и составить программу, позволяющую выделять в нем простую цепь, простой цикл. Граф и количество ребер в данных путях - входные параметры.
Спроектировать телефонную сеть с минимальной суммарной длиной линий для баз горноспасательных служб. Расположение баз и расстояние между ними указать на рисунке.
Вывести путешественников, попавших в лабиринт, к выходу. Лабиринт представляет собой совокупность коридоров и перекрестков. Местом начала пути может быть любой из имеющихся перекрестков.
Для произвольного ориентированного графа разработать алгоритм и составить программу, позволяющую выделять в нем цепь, цикл. Орграф и количество ребер в данных путях - входные параметры.
Для произвольного ориентированного графа разработать алгоритм и составить программу, позволяющую выделять в нем простую цепь, простой цикл. Орграф и количество ребер в данных путях - входные параметры.
Создайте обучающую программу, предназначенную для студентов, изучающих алгоритм обхода графа в глубину.
Создайте обучающую программу, предназначенную для студентов, изучающих алгоритм обхода графа по ширине.
Реализовать:
Алгоритм Тэрри нахождения пути в графе из заданной вершины x в заданную вершину y.
Алгоритм Тэрри нахождения компонент связности графа.
Алгоритм Фронта волны нахождения минимального пути в графе из заданной вершины x в заданную вершину y.
Алгоритм Фронта волны нахождения минимального пути в ориентированном графе из заданной вершины x в заданную вершину y.
Алгоритм нахождения остовного дерева графа.
Алгоритм нахождения минимального остовного дерева в графе.
Алгоритм обхода графа в ширину.
Алгоритм обхода графа в глубину.
Алгоритм нахождения компонент связности графа.
Алгоритм расчета числовых характеристик графа.
Алгоритм расчета степеней вершин графа.
Алгоритм расчета полустепеней исхода и захода графа.