Лабораторной работе №4. По дисциплине Алгоритмы и структуры данных. Тема Построение минимального остовного дерева.
-
Категории:
Алгоритмы и структуры данных, Санкт-Петербургский государственный электротехнический университет ЛЭТИ, Работа Лабораторная
-
Добавлен:
28.03.2023
-
Размер:
964 KB
-
Покупок:
0
-
Добавил:
DiKey
Написать сообщение
Скачать
Состав работы
|
Лабораторная 4.docx
|
Screenshot_560.jpg
|
|
Screenshot_561.jpg
|
|
Screenshot_562.jpg
|
Работа представляет собой rar архив с файлами (распаковать онлайн), которые открываются в программах:
- Microsoft Word
- Программа для просмотра изображений
Описание
Лабораторной работе №4. По дисциплине Алгоритмы и структуры данных. Тема Построение минимального остовного дерева.
ЦЕЛЬ РАБОТЫ
Ознакомление с вариантами реализации алгоритмов на графах на примере задачи построения минимального остовного дерева.
ОСНОВНЫЕ ТЕОРЕТИЧЕСКИЕ СВЕДЕНИЯ
Алгоритм Прима
Алгоритм начинается с выбора произвольной вершины. Она принимается за часть построенного минимального остовного дерева.
Далее в цикле в каждой итерации рассматриваются только те ребра исходного графа, одна из вершин которых строго принадлежит уже построенной части, а другая строго не принадлежит (если второе условие не проверять, то в графе возникнут циклы). Из списка всех ребер, удовлетворяющих этому условию, выбирается ребро с наименьшим весом и добавляется к построенной части.
Итерации повторяются до тех пор, пока все вершины не окажутся включенными в остовное дерево.
Алгоритм Краскала
Алгоритм начинается с того, что каждая вершина исходного графа помещается в свое множество (состоящее из одной вершины) – компоненту связности.
Далее в цикле в каждой итерации из всех ребер, которые соединяют разные компоненты связности, выбирается ребро с наименьшим весом, и с помощью него две отдельные компоненты связности объединяются в одну.
Итерации повторяются до тех пор, пока количество компонент связности не уменьшится до одной – она и будет представлять собой остовное дерево.
ЦЕЛЬ РАБОТЫ
Ознакомление с вариантами реализации алгоритмов на графах на примере задачи построения минимального остовного дерева.
ОСНОВНЫЕ ТЕОРЕТИЧЕСКИЕ СВЕДЕНИЯ
Алгоритм Прима
Алгоритм начинается с выбора произвольной вершины. Она принимается за часть построенного минимального остовного дерева.
Далее в цикле в каждой итерации рассматриваются только те ребра исходного графа, одна из вершин которых строго принадлежит уже построенной части, а другая строго не принадлежит (если второе условие не проверять, то в графе возникнут циклы). Из списка всех ребер, удовлетворяющих этому условию, выбирается ребро с наименьшим весом и добавляется к построенной части.
Итерации повторяются до тех пор, пока все вершины не окажутся включенными в остовное дерево.
Алгоритм Краскала
Алгоритм начинается с того, что каждая вершина исходного графа помещается в свое множество (состоящее из одной вершины) – компоненту связности.
Далее в цикле в каждой итерации из всех ребер, которые соединяют разные компоненты связности, выбирается ребро с наименьшим весом, и с помощью него две отдельные компоненты связности объединяются в одну.
Итерации повторяются до тех пор, пока количество компонент связности не уменьшится до одной – она и будет представлять собой остовное дерево.
Дополнительная информация
2022
Похожие материалы
Контрольная работа по дисциплине: Алгоритмы и структуры данных. Вариант №13
IT-STUDHELP
: 3 мая 2023
Контрольная работа
Задание
Таблица 1. Варианты заданных предметных областей (ХХ – 2 последние цифры пароля)
ХХ Предметная область Атрибуты информации Критерий отбора
13 38 63 88 Описание изображения тип фигуры (квадрат, окружность и т.п.), координаты на плоскости, числовые характеристики (длина стороны, радиус и т.п.). Многоугольники
------------------------------------------------------------------------------
Содержание:
Задание
Часть I – Статические структуры
1.Текст задания
2.Текст п
IT-STUDHELP
: 3 мая 2023
850 руб.
Контрольная работа по дисциплине: Алгоритмы и структуры данных. Вариант № 13
IT-STUDHELP
: 14 апреля 2021
Вариант № 13
Выполнение работы
Таблица 1. Варианты заданных предметных областей (ХХ – 2 последние цифры пароля)
ХХ Предметная область Атрибуты информации Критерий отбора
13 38 63 88 Описание изображения тип фигуры (квадрат, окружность и т.п.), координаты на плоскости, числовые характеристики (длина стороны, радиус и т.п.). Многоугольники
Часть I – Статические структуры
1. На основе материалов конспекта лекций, рекомендуемой литературы и материалов сети Интернет изучить теоретический материал
IT-STUDHELP
: 14 апреля 2021
850 руб.
Контрольная работа по дисциплине: Алгоритмы и структуры данных. Вариант № 11
IT-STUDHELP
: 14 апреля 2021
Вариант № 11
Выполнение работы
Таблица 1. Варианты заданных предметных областей (ХХ – 2 последние цифры пароля)
ХХ Предметная область Атрибуты информации Критерий отбора
11 36 61 86 Сведения о студентах фамилия студента, имя, отчество, факультет, количество братьев и сестер Студенты с ненулевым числом братьев и сестер
Часть I – Статические структуры
1. На основе материалов конспекта лекций, рекомендуемой литературы и материалов сети Интернет изучить теоретический материал по программировани
IT-STUDHELP
: 14 апреля 2021
850 руб.
Контрольная работа по дисциплине "Алгоритмы и структуры данных" (вариант 5)
Greenberg
: 28 августа 2020
Таблица 1. Варианты заданных предметных областей (ХХ – 2 последние цифры пароля
Предметная область Программы
Атрибуты информации наименование, фирма-разработчик, операционная система, стоимость
Критерий отбора Программы с нулевой стоимостью
Часть I – Статические структуры
1. На основе материалов конспекта лекций, рекомендуемой литературы и материалов сети Интернет изучить теоретический материал по программированию статических структур данных (раздел 1 конспекта лекций) и области их эффективно
Greenberg
: 28 августа 2020
440 руб.
Контрольная работа по дисциплине «Алгоритмы и структуры данных». Вариант №01.
teacher-sib
: 27 августа 2020
Выполнение работы
Таблица 1. Варианты заданных предметных областей (ХХ – 2 последние цифры пароля)
ХХ Предметная область Атрибуты информации Критерий отбора
01 26 51 76 Производство обозначение изделия, группа к которой оно относится, год выпуска, объем выпуска, расход металла Изделия заданной группы
Часть I – Статические структуры
1. На основе материалов конспекта лекций, рекомендуемой литературы и материалов сети Интернет изучить теоретический материал по программированию статических ст
teacher-sib
: 27 августа 2020
800 руб.
Контрольная работа по дисциплине: Алгоритмы и структуры данных. Вариант №05
IT-STUDHELP
: 27 августа 2020
Контрольная работа
Таблица 1. Варианты заданных предметных областей (ХХ –2 последние цифры пароля)
ХХ Предметная область Атрибуты информации Критерий отбора
05 Программы наименование, фирма-разработчик, операционная система, стоимость Программы с нулевой стоимостью
Часть I – Статические структуры
1. На основе материалов конспекта лекций, рекомендуемой литературы и материалов сети Интернет изучить теоретический материал по программированию статических структур данных (раздел 1 конспекта лекций)
IT-STUDHELP
: 27 августа 2020
850 руб.
Контрольная работа по дисциплине: Алгоритмы и структуры данных. Вариант №04
IT-STUDHELP
: 17 июля 2020
Таблица 1. Варианты заданных предметных областей (ХХ –2 последние цифры пароля)
ХХ Предметная область Атрибуты информации Критерий отбора
04 Радиодетали обозначение, тип, номинал, количество на схеме, обозначение возможного заменителя Детали, не имеющие заменителей
Часть I – Статические структуры
1. На основе материалов конспекта лекций, рекомендуемой литературы и материалов сети Интернет изучить теоретический материал по программированию статических структур данных (раздел 1 конспекта лекций)
IT-STUDHELP
: 17 июля 2020
850 руб.
Контрольная работа по дисциплине: Алгоритмы и структуры данных. Вариант №05
IT-STUDHELP
: 17 июля 2020
Таблица 1. Варианты заданных предметных областей (ХХ –2 последние цифры пароля)
ХХ Предметная область Атрибуты информации Критерий отбора
05 Программы наименование, фирма-разработчик, операционная система, стоимость Программы с нулевой стоимостью
Часть I – Статические структуры
1. На основе материалов конспекта лекций, рекомендуемой литературы и материалов сети Интернет изучить теоретический материал по программированию статических структур данных (раздел 1 конспекта лекций) и области их эффек
IT-STUDHELP
: 17 июля 2020
850 руб.
Другие работы
ИГ.06.09.02 - Пирамида с вырезами
Чертежи СибГАУ им. Решетнева
: 6 августа 2023
Все выполнено в программе КОМПАС 3D v16
Вариант 9
ИГ.06.09.02 - Пирамида с вырезами
1. По двум видам построить вид слева, горизонтальный, фронтальный и профильный разрезы.
2. Нанести размеры.
3. Построить прямоугольную изометрическую проекцию с четвертью выреза. Отверстия сквозные.
В состав работы входят 4 файла:
- 3D модель данной детали, разрешение файла *.m3d;
- ассоциативный чертеж формата А3 в трёх видах с выполненными горизонтальным, фронтальным и профильным разрезами с совмещением поло
Чертежи СибГАУ им. Решетнева
: 6 августа 2023
100 руб.
Определение рыночной стоимости кредитных организаций
Qiwir
: 5 ноября 2013
Среди множества финансовых институтов, функционирующих на сегодняшний день на российском рынке, банки занимают одно из ведущих мест. Специфика деятельности и отличительные черты развития банков, связанные с правовой системой и особенностями данного бизнеса, делают оценку рыночной стоимости банков достаточно сложной.
Оценку рыночной стоимости банков можно условно разделить на аутсайдерскую и инсайдерскую. Основное отличие этих двух оценок заключается в том, что при проведении инсайдерской оценки
Qiwir
: 5 ноября 2013
10 руб.
Водоснабжение промышленного предприятия
Anurdin
: 10 мая 2013
При разработке курсового проекта необходимо использовать следующие исходные данные.
1.Водопотребление для технологических нужд предприятия при Ку = 1 и характеристика качества воды до и после технологического процесса:
Q1j – вода питьевого качества (оборота не допускается); может быть использована после удаления из нее масел, жиров и бактериологических загрязнений для технологических процессов, потребляющих воду с расходом Q5j
Q2j – вода питьевого качества, умягченная; используется для под-питк
Anurdin
: 10 мая 2013
Разработка механического участка обработки фланца. Чертеж шпинделя
wolfire
: 15 мая 2012
Разработка механического участка обработки фланца. Чертеж шпинделя
wolfire
: 15 мая 2012
