Методические указания к лабораторным работам по курсу «Дискретная математика».
Оглавление.
Введение. 1
Задания к работе №1. 1
Задания к работе №2. 4
Задания к работе №3. 7
Задания к работе №4. 10
Задания к работе №5. 13
Задания к работе №6. 16
Задания к работе №7. 19
Задания к работе №8. 22
Введение.
Курс лабораторных работ состоит из 8 работ. Все работы состоят в создании алгоритма решающего определенную задачу дискретной математики, кодировании алгоритма на одном из языков высокого уровня, отладки программы и сдаче программы системе автоматического тестирования.
Все входные данные для программы задаются в текстовом файле test.in, результаты работы программы представляются в текстовом файле test.out.
В большинстве заданий в файле test.in задается неориентированный граф. В первой строке приводится целое число, определяющее число вершин графа. Каждая следующая строка файла содержит строку матрицы смежности графа, элементы которой отделены друг от друга пробелами.
В большинстве заданий в файле test.out выводится целое число.
Всего подготовлено 80 заданий из расчета того, что все бригады получают разные задания и число бригад – 10.
Допускается кодирование алгоритмов на языках C++ и Pascal.
Задания к работе №1.
Задание № 1.
Разработать алгоритм, составить его описание на алгоритмическом
языке высокого уровня, отладить программу.
Входные данные:
число вершин неориентированного графа
матрица смежности графа
Выходные данные:
радиус графа
Задание № 2.
Разработать алгоритм, составить его описание на алгоритмическом
языке высокого уровня, отладить программу.
Входные данные:
число вершин неориентированного графа
матрица смежности графа
Выходные данные:
число компонент связности
Задание № 3.
Разработать алгоритм, составить его описание на алгоритмическом
языке высокого уровня, отладить программу.
Входные данные:
число вершин неориентированного графа
матрица смежности графа
Выходные данные:
диаметр графа
Задание № 4.
Разработать алгоритм, составить его описание на алгоритмическом
языке высокого уровня, отладить программу.
Входные данные:
число вершин неориентированного графа
матрица смежности графа
Выходные данные:
вершины максимальной клики
Задание № 5.
Разработать алгоритм, составить его описание на алгоритмическом
языке высокого уровня, отладить программу.
Входные данные:
число вершин неориентированного графа
матрица смежности графа
Выходные данные:
квадрат графа
Задание № 6.
Разработать алгоритм, составить его описание на алгоритмическом
языке высокого уровня, отладить программу.
Входные данные:
число вершин неориентированного графа
матрица смежности графа
Выходные данные:
куб графа
Задание № 7.
Разработать алгоритм, составить его описание на алгоритмическом
языке высокого уровня, отладить программу.
Входные данные:
число вершин неориентированного графа
матрица смежности графа
Выходные данные:
композиция графов
Задание № 8.
Разработать алгоритм, составить его описание на алгоритмическом
языке высокого уровня, отладить программу.
Входные данные:
число вершин неориентированного графа
матрица смежности графа
Выходные данные:
произведение графов
Задание № 9.
Разработать алгоритм, составить его описание на алгоритмическом
языке высокого уровня, отладить программу.
Входные данные:
число вершин неориентированного графа
матрица смежности графа
Выходные данные:
матрица расстояний в графе
Задание № 10.
Разработать алгоритм, составить его описание на алгоритмическом
языке высокого уровня, отладить программу.
Входные данные:
число вершин неориентированного графа
матрица смежности графа
Выходные данные:
матрица обходов