Лабораторная работа 1 Теория сложности вычислительных процессов и структур Вариант 6
Состав работы
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Необходимые программы
Работа представляет собой zip архив с файлами (распаковать онлайн), которые открываются в программах:
- Программа для просмотра текстовых файлов
- Microsoft Word
Описание
Теория сложности вычислительных процессов и структур
Лабораторная работа №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
Лабораторная работа №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
Дополнительная информация
Лабораторная работа 1 20.09.2026 20.09.2026 Зачет Уважаемый, замечаний нет. Галкина Марина Юрьевна
Похожие материалы
Теория сложностей вычислительных процессов и структур. Лабораторная работа №1. Вариант №6
zhekaersh
: 1 марта 2015
Сортировка массивов
Написать программу для сортировки массива из 50 элементов методом “пузырьковой” сортировки (Bubble Sort) или прямого выбора (Select Sort) (по вариантам). Массив считать из файла. Вывести на экран трудоемкость метода (количество сравнений).
Номер варианта выбирается по последней цифре зачетной книжки
Вариант6
Метод прямого выбора.
Массив из 50 элементов для сортировки:
722, 867, 288, 172, 310, 935, 709, 898, 66, 405, 766, 63, 990, 97, 431, 641, 326, 826, 500, 981, 370, 6
40 руб.
Теория сложностей вычислительных процессов и структур. Лабораторная работа №1 (вариант 6)
dryan
: 4 декабря 2012
Написать программу для сортировки массива из 50 элементов методом “пузырьковой” сортировки (Bubble Sort) или прямого выбора (Select Sort) (по вариантам). Массив считать из файла. Вывести на экран трудоемкость метода (количество сравнений).
Метод прямого выбора.
50 руб.
Теория сложности вычислительных процессов и структур. Лабораторная работа №1 (2021). Вариант №6.
nik200511
: 9 июня 2021
ЛАБОРАТОРНАЯ РАБОТА №1
Написать программу, которая по алгоритму Краскала находит остов минимального веса для связного взвешенного неориентированного графа, имеющего 10 вершин. Граф задан матрицей смежности (0 означает, что соответствующей дуги нет). Данные считать из файла.
Вывести ребра остова минимального веса в порядке их присоединения и вес остова.
Номер варианта выбирается по последней цифре пароля.
Вариант 6
0 0 24 0 14 16 24 13 16 0
0 0 9 23 6 26 19 0 10 27
24 9 0 14 5 23 22 19 8 10
0
138 руб.
Теория сложности вычислительных процессов и структур. Лабораторные работы №1-5. Вариант №6.
Cole82
: 8 октября 2015
Лабораторная работа №1.
Сортировка массивов
Написать программу для сортировки массива из 50 элементов методом “пузырьковой” сортировки (Bubble Sort) или прямого выбора (Select Sort) (по вариантам). Массив считать из файла. Вывести на экран трудоемкость метода (количество сравнений).
Номер варианта выбирается по последней цифре зачетной книжки.
Вариант6
Метод прямого выбора.
Массив из 50 элементов для сортировки:
722, 867, 288, 172, 310, 935, 709, 898, 66, 405, 766, 63, 990, 97, 431, 641, 326, 82
75 руб.
Теория сложностей вычислительных процессов и структур. Лабораторные работы №1-5. Вариант №6.
zhekaersh
: 5 марта 2015
Лабораторная работа 1.
Сортировка массивов
Написать программу для сортировки массива из 50 элементов методом “пузырьковой” сортировки (Bubble Sort) или прямого выбора (Select Sort) (по вариантам). Массив считать из файла. Вывести на экран трудоемкость метода (количество сравнений).
Метод прямого выбора.
Массив из 50 элементов для сортировки:
722, 867, 288, 172, 310, 935, 709, 898, 66, 405, 766, 63, 990, 97, 431, 641, 326, 826, 500, 981, 370, 624, 716, 484, 3, 646, 686, 120, 239, 784, 460, 8
200 руб.
Лабораторные работы 1-3 по дисциплине: Теория сложностей вычислительных процессов и структур. Вариант №6
IT-STUDHELP
: 16 ноября 2022
Лабораторная работа №1
Задание
Написать программу, которая по алгоритму Краскала находит остов минимального веса для связного взвешенного неориентированного графа, имеющего 10 вершин. Граф задан матрицей смежности (0 означает, что соответствующей дуги нет). Данные считать из файла.
Вывести ребра остова минимального веса в порядке их присоединения и вес остова.
Номер варианта выбирается по последней цифре пароля.
Вариант 6
0 0 24 0 14 16 24 13 16 0
0 0 9 23 6 26 19 0 10 27
24 9 0 14 5 23 22 1
600 руб.
Лабораторные работы №№1-3 по дисциплине: Теория сложности вычислительных процессов и структур. Вариант №6
IT-STUDHELP
: 19 ноября 2021
ЛАБОРАТОРНАЯ РАБОТА №1
по дисциплине
«Теория сложности вычислительных процессов и структур»
Задание
Написать программу, которая по алгоритму Краскала находит остов минимального веса для связного взвешенного неориентированного графа, имеющего 10 вершин. Граф задан матрицей смежности (0 означает, что соответствующей дуги нет). Данные считать из файла.
Вывести ребра остова минимального веса в порядке их присоединения и вес остова.
Номер варианта выбирается по последней цифре пароля.
Вариант 6
0
600 руб.
Теория сложности вычислительных процессов и структур. Лабораторные работы №№1-3 (2021). Вариант №6.
nik200511
: 9 июня 2021
ЛАБОРАТОРНАЯ РАБОТА №1
Написать программу, которая по алгоритму Краскала находит остов минимального веса для связного взвешенного неориентированного графа, имеющего 10 вершин. Граф задан матрицей смежности (0 означает, что соответствующей дуги нет). Данные считать из файла.
Вывести ребра остова минимального веса в порядке их присоединения и вес остова.
Номер варианта выбирается по последней цифре пароля.
Вариант 6
0 0 24 0 14 16 24 13 16 0
0 0 9 23 6 26 19 0 10 27
24 9 0 14 5 23 22 19 8 10
0
408 руб.
Другие работы
Развитие памяти в дошкольном возрасте
Slolka
: 18 октября 2013
Введение
В Послании Президента Казахстана Н.А. Назарбаева «Рост благосостояния граждан республики Казахстан – главная цель государственной политики» от 6 февраля 2008 года, говорится о том, что особое внимание должно быть уделено системе дошкольного образования как первой ступени непрерывного обучения, стимулирующего развитие детей дошкольного возраста, обеспечив их эффективными программами для развития творческих и интеллектуальных способностей. Надо помнить, что именно на этом этапе закладыва
Экзамен по: Математическому анализу. Часть 1. Билет №2
ulibka
: 17 января 2015
Экзаменационная работа
по дисциплине: Математический анализ. (часть 1)
Билет №2
1. Замечательные пределы и их следствия. Неопределенности. Приемы их раскрытия
2. Вычислить производные функций
3. Провести полное исследование функции и построить её график
4. Исследовать на экстремум функцию двух переменных
5. Найти неопределенные интегралы
Оценка: хорошо
150 руб.
Лабораторная работа №2 по дисциплине: Элементная база телекоммуникационных систем. Вариант №11
IT-STUDHELP
: 17 ноября 2022
Лабораторная работа No2
Изучение интегральных операционных усилителей
по дисциплине
«Элементная база телекоммуникационных систем»
1 Цель работы
Изучить типы, характеристики и параметры интегральных операционных усилителей (ИОУ).
2 Задание
2.1 Привести схему устройства на ИОУ, предусмотренную
индивидуальным заданием.
3.2 Пояснить назначение устройства, привести виды амплитудный и
амплитудно-частотной характеристик.
3.3 Оформить отчет о проделанной работе, отчет должен содержать:
схему устрой
350 руб.
Расчет шиномонтажного отделения АТП на 536 автомобилей ВАЗ-2109
DocentMark
: 24 августа 2011
Введение
1. Общая часть
2. Технологический расчет проектируемого предприятия
2.1 Исходные данные для расчета
2.2 Расчет годовой производственной программы
2.2.1 Корректирование периодичности ТО и пробега автомобилей до КР
2.2.2 Расчет годового пробега автомобилей
2.2.3 Расчет годовой производственной программы
2.2.4 Расчет суточной производственной программы
2.3 Расчет годового объема работ
2.3.1 Корректирование трудоемкости ТО и ТР
2.3.2 Расчет годового объема работ по ТО, ТР и самообслуж
244 руб.