Лабораторной работе №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 руб.
Другие работы
Расчет искуственного освещения шиномонтажного комплекса ПАТП
Рики-Тики-Та
: 28 мая 2019
Чертеж Выполнен в программе Компас на формате А1. Расчет искуственного освещения шиномонтажного комплекса ПАТП
Рики-Тики-Та
: 28 мая 2019
20 руб.
Налогообложение малого предпринимательства на примере ИП Ушакова М. А.
Slolka
: 26 октября 2013
СОДЕРЖАНИЕ
Введение………………………………………………………………………...…… 1
1. Теоретические аспекты налогообложения малого бизнеса…………..……….. 4
1.1. Характеристика объекта исследования ………………………….…….……... 4
1.2. Малые предприятия и условия их формирования ……………………........... 5
1.3. Эволюция налогообложения малого предпринимательства в России…….. 11
2. Анализ существующих налоговых режимов, применяемых субъектами малого предпринимательства ……………………………………………..………………. 14
2.1. Сущность и роль специальных налоговых режим
Slolka
: 26 октября 2013
45 руб.
Буровая лебедка ЛБУ-1100. Курсовая работа-Оборудование для бурения нефтяных и газовых скважин
https://vk.com/aleksey.nakonechnyy27
: 15 марта 2016
Изобретение относится к области машиностроения, в частности к оборудованию для бурения нефтяных и газовых скважин, а именно к тормозам буровых лебедок. Тормоз содержит автономные с независимым пневмоуправлением разъемные части, каждая из которых включает резинокордные баллоны с тормозными колодками, облицованными фрикционными накладками, закрепленные на ободе и стопорный подпружиненный палец, установленный на раме. Разъемные части попарно соединены коромыслами (рычагами), между которыми установл
https://vk.com/aleksey.nakonechnyy27
: 15 марта 2016
1392 руб.
ЭПУС. Тестовое (итоговое) задание. 6-й семестр. СБТ/МБТ. Билет № 13.
sanco25
: 21 августа 2013
1. Наибольшим потоком рассеяния обладает трансформатор:
2. Стержневые магнитопроводы типа ПЛ имеют сечение сердечника (см2) (установите соответствие):
3. Установите логическую последовательность работы трансформатора на холостом ходу, когда к первичной обмотке прикладывается напряжение U1
4. Схемы с трансформаторами расположите в порядке уменьшения напряжения на нагрузке U2, при U1 = 100 В, коэффициент трансформации n = 1
5. На векторной диаграмме трансформатора векторы ЭДС (Е2), тока во вторич
sanco25
: 21 августа 2013
99 руб.
