|
Теория сложности вычислительных процессов и структур Вар 6
|
|
| engineerklub | Дата: Понедельник, 28.09.2026, 06:09 | Сообщение # 1 |
 Генералиссимус
Группа: Администраторы
Сообщений: 40278
Статус: Offline
| Теория сложности вычислительных процессов и структур Вариант 6
Теория сложности вычислительных процессов и структур
Лабораторная работа №1
Поиск минимального остова графа
Присылаемый на проверку архив должен содержать 2 файла:
файл отчета, содержащий титульный лист, условие задачи, описание алгоритма Краскала, исходный текст программы (с указанием языка реализации) и результаты работы программы (можно в виде скриншотов);
файл с исходным текстом программы (программу можно писать на любом языке программирования).
1. Задание на лабораторную работу
Написать программу, которая по алгоритму Краскала находит остов минимального веса для связного взвешенного неориентированного графа, имеющего 10 вершин. Граф задан матрицей смежности размера 10х10 (где 0 означает, что соответствующего ребра нет). Данные необходимо считывать из файла. Программа должна выводить ребра остова минимального веса в порядке их присоединения, а также суммарный вес остова.
2. Теоретическая часть и описание алгоритма Краскала
Минимальный остов (или остовное дерево минимального веса, MST) — это подграф данного связного взвешенного неориентированного графа, который содержит все его вершины, является деревом (связен и не содержит циклов) и имеет минимально возможную сумму весов входящих в него рёбер.
Алгоритм Краскала относится к категории «жадных» (greedy) алгоритмов и состоит из следующих шагов:
1. Инициализация: каждая вершина графа изначально объявляется отдельной связной компонентой (изолированным деревом). Создается пустое множество рёбер для будущего остова.
2. Сортировка рёбер: выписываются все существующие рёбра графа с их весами, после чего они сортируются в порядке строгого возрастания их весов.
3. Перебор и добавление рёбер: последовательно рассматриваются рёбра из отсортированного списка:
o Если текущее ребро соединяет вершины, находящиеся в разных компонентах связности, оно добавляется в остов, а эти две компоненты объединяются в одну.
o Если вершины ребра уже принадлежат одной компоненте, то добавление ребра приведет к образованию цикла. Такое ребро игнорируется.
4. Критерий остановки: Процесс завершается, когда в остов будет добавлено ровно (V - 1) рёбер, где V — количество вершин графа (для графа из 10 вершин в остове должно быть ровно 9 рёбер).
3. Исходные данные (Вариант 6)
Граф состоит из 10 вершин (пронумеруем их от 1 до 10). Матрица смежности из задания имеет вид:
Вершины 1 2 3 4 5 6 7 8 9 10
1 0 0 24 0 14 16 24 13 16 0
2 0 0 9 23 6 26 19 0 10 27
3 24 9 0 14 5 23 22 19 8 10
4 0 23 14 0 22 7 16 5 11 25
5 14 6 5 22 0 15 18 22 23 26
6 16 26 23 7 15 0 29 0 23 21
7 24 19 22 16 18 29 0 4 8 26
8 13 0 19 5 22 0 4 0 8 7
9 16 10 8 11 23 23 8 8 0 28
10 0 27 10 25 26 21 26 7 28 0
СКАЧАТЬ
|
| |
|
|
| engineerklub | Дата: Понедельник, 28.09.2026, 06:10 | Сообщение # 2 |
|
Генералиссимус
Группа: Администраторы
Сообщений: 40278
Статус: Offline
| Теория сложности вычислительных процессов и структур
Лабораторная работа №2
Поиск кратчайшего расстояния между двумя вершинами
Присылаемый на проверку архив должен содержать 2 файла:
файл отчета, содержащий титульный лист, условие задачи, описание используемого алгоритма, исходный текст программы (с указанием языка реализации) и результаты работы программы (можно в виде скриншотов);
файл с исходным текстом программы (программу можно писать на любом языке программирования).
1. Задание на лабораторную работу
Написать программу, которая по алгоритму Форда-Беллмана находит кратчайшее расстояние от вершины с номером Вашего варианта (вершина 6) до всех остальных вершин связного взвешенного неориентированного графа, имеющего 10 вершин (нумерация от 0 до 9).
Граф задан матрицей смежности размера 10х10 (0 означает отсутствие ребра). Данные необходимо считывать из файла. Программа должна вывести все найденные кратчайшие расстояния и соответствующие им пути в виде последовательности ребер.
2. Теоретическая часть и описание алгоритма Форда-Беллмана
Алгоритм Форда-Беллмана — это эффективный метод динамического программирования для поиска кратчайших путей из одной фиксированной вершины-источника во все остальные вершины взвешенного графа. В отличие от алгоритма Дейкстры, данный метод корректно работает с графами, содержащими ребра с отрицательным весом.
Суть алгоритма:
Алгоритм последовательно улучшает (релаксирует) текущее знание о кратчайших расстояниях. Для графа с количеством вершин V кратчайший путь без циклов не может содержать более чем (V - 1) ребро. Поэтому алгоритм выполняет ровно (V - 1) итераций.
Пошаговое описание:
1. Инициализация: создается массив расстояний D размера V. Для стартовой вершины-источника расстояние D [start]принимается равным 0, для всех остальных вершин расстояние инициализируется бесконечностью (практически — очень большим числом). Также инициализируется массив предков P для последующего восстановления маршрутов.
2. Основной цикл (Релаксация рёбер): выполняется (V - 1) внешних итераций. На каждой итерации перебираются абсолютно все рёбра графа (u, v) с весом W. Выполняется проверка условия релаксации:
o Если D + W < D[v], то мы нашли более короткий путь к вершине v через вершину u. Расстояние обновляется: D [v]= D + W, а в массив предков записывается P [v]= u.
3. Восстановление путей: на основе заполненного массива предков P для каждой вершины выполняется обратный обход от целевой вершины к стартовой, формируя точную последовательность пройденных рёбер.
3. Исходные данные (Вариант 6)
Граф состоит из 10 вершин (пронумерованных от 0 до 9). Стартовая вершина-источник: 6.
Матрица смежности из задания имеет следующий вид:
Вершины 0 1 2 3 4 5 6 7 8 9
0 0 0 8 8 7 5 5 6 1 2
1 0 0 3 1 6 3 7 3 0 9
2 8 3 0 11 2 3 0 8 1 10
3 8 1 11 0 6 4 0 11 7 9
4 7 6 2 6 0 2 11 6 3 4
5 5 3 3 4 2 0 2 1 3 3
6 5 7 0 0 11 2 0 3 3 7
7 6 3 8 11 6 1 3 0 0 8
8 1 0 1 7 3 3 3 0 0 8
9 2 9 10 9 4 3 7 8 8 0
Примечание: значение 0 на пересечении строки 6 и столбцов 2 и 3 означает, что прямых рёбер из вершины 6 в вершины 2 и 3 не существует.
СКАЧАТЬ
|
| |
|
|
| engineerklub | Дата: Понедельник, 28.09.2026, 06:11 | Сообщение # 3 |
|
Генералиссимус
Группа: Администраторы
Сообщений: 40278
Статус: Offline
| Лабораторная работа №3
Решение задачи о рюкзаке методом динамического программирования
Присылаемый на проверку архив должен содержать 2 файла:
файл отчета, содержащий титульный лист, условие задачи, описание используемого алгоритма, исходный текст программы (с указанием языка реализации) и результаты работы программы (можно в виде скриншотов);
файл с исходным текстом программы (программу можно писать на любом языке программирования).
1. Задание на лабораторную работу
Имеется склад, на котором присутствует некоторый ассортимент из 4 видов товаров. Запас каждого товара неограничен. У каждого товара своя стоимость c(i) и масса m(i).
Написать программу, которая методом динамического программирования формирует набор товаров максимальной стоимости таким образом, чтобы его суммарная масса не превышала заданную грузоподъемность М = 63. Программа должна выводить таблицу промежуточных вычислений, сформированный оптимальный набор предметов, его итоговую стоимость и массу.
2. Теоретическая часть и описание алгоритма
В данной работе рассматривается неограниченная задача о рюкзаке (Unbounded Knapsack Problem), поскольку запас каждого товара на складе неограничен (предметы одного и того же типа можно брать многократно).
Для решения задачи используется метод диначеского программирования. Вместо полного перебора всех комбинаций (который имеет экспоненциальную сложность) строится функция, определяющая максимальную ценность для каждого промежуточного веса от 0 до М.
Расчетная формула метода:
Пусть W — текущая вместимость рёкзака (изменяется от 0 до М). Обозначим через f(W) максимальную стоимость товаров, которую можно набрать в рюкзак весом W.
Формула имеет вид:
f(W) = максимум по всем предметам i (у которых масса m(i) <= W) от выражения:
f(W - m(i)) + c(i)
Где:
• f(W - m(i)) — максимальная стоимость рюкзака меньшего веса, оставшегося после добавления i-го предмета.
• c(i) — стоимость добавляемого i-го предмета.
База индукции:
Для рюкзака нулевой вместимости максимальная ценность равна нулю: f(0) = 0.
Для восстановления набора предметов параллельно заполняется массив решений S(W), куда записывается номер товара i, на котором был достигнут максимум стоимости для веса W. После заполнения массива от финальной вместимости М производится обратный шаг: берется товар из S(M), его вес вычитается из М, и процесс повторяется, пока свободное место не станет равным нулю.
3. Исходные данные (Вариант 6)
• Грузоподъемность рюкзака: M = 63
• Количество видов товаров: 4
Характеристики доступных товаров представлены в таблице:
Номер товара (i) Масса товара, m(i) Стоимость товара, c(i) Удельная ценность (c/m)
1 6 11 1.83
2 4 15 3.75
3 10 45 4.50
4 9 37 4.11
СКАЧАТЬ
|
| |
|
|
| engineerklub | Дата: Понедельник, 28.09.2026, 06:12 | Сообщение # 4 |
|
Генералиссимус
Группа: Администраторы
Сообщений: 40278
Статус: Offline
| Теория сложности вычислительных процессов и структур Вариант 6
Задача о перемножении матриц
Присылаемый на проверку архив должен содержать 2 файла:
• файл отчета, содержащий титульный лист, условие задачи, формулы используемых методов, исходный текст программы (с указанием языка реализации) и результаты работы программы (можно в виде скриншотов);
• файл с исходным текстом программы (программу можно писать на любом языке программирования).
Задание на контрольную работу
• Написать программу, которая оптимальным образом расставляет скобки при перемножении матриц M1M2M3M4M5M6M7M8M9M10M11M12. Матрицы имеют следующие размерности:
Размерности матриц считать из файла.
Вывести промежуточные вычисления, результат расстановки скобок и трудоемкость полученной расстановки.
Номер варианта r0 r1 r2 r3 r4 r5 r6 r7 r8 r9 r10 r11 r12
6 6 3 9 4 9 4 8 6 4 7 9 9 6
СКАЧАТЬ
|
| |
|
|
