Написать сообщение
Скачать
Screenshot_560.jpg
Лабораторной работе №4. По дисциплине Алгоритмы и структуры данных. Тема Построение минимального остовного дерева.
-
Категории:
Алгоритмы и структуры данных, Санкт-Петербургский государственный электротехнический университет ЛЭТИ, Работа Лабораторная
-
Добавлен:
28.03.2023
-
Размер:
964 KB
-
Покупок:
0
-
Добавил:
DiKey
Состав работы
|
Лабораторная 4.docx
|
Screenshot_560.jpg
|
|
Screenshot_561.jpg
|
|
Screenshot_562.jpg
|
Дополнительная информация
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 руб.
Контрольная работа по дисциплине: Алгоритмы и структуры данных. Вариант № 11
IT-STUDHELP
: 14 апреля 2021
Вариант № 11
Выполнение работы
Таблица 1. Варианты заданных предметных областей (ХХ – 2 последние цифры пароля)
ХХ Предметная область Атрибуты информации Критерий отбора
11 36 61 86 Сведения о студентах фамилия студента, имя, отчество, факультет, количество братьев и сестер Студенты с ненулевым числом братьев и сестер
Часть I – Статические структуры
1. На основе материалов конспекта лекций, рекомендуемой литературы и материалов сети Интернет изучить теоретический материал по программировани
IT-STUDHELP
: 14 апреля 2021
850 руб.
Контрольная работа по дисциплине: Алгоритмы и структуры данных. Вариант № 13
IT-STUDHELP
: 14 апреля 2021
Вариант № 13
Выполнение работы
Таблица 1. Варианты заданных предметных областей (ХХ – 2 последние цифры пароля)
ХХ Предметная область Атрибуты информации Критерий отбора
13 38 63 88 Описание изображения тип фигуры (квадрат, окружность и т.п.), координаты на плоскости, числовые характеристики (длина стороны, радиус и т.п.). Многоугольники
Часть 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 руб.
Контрольная работа по дисциплине: Алгоритмы и структуры данных. Вариант №05
IT-STUDHELP
: 17 июля 2020
Таблица 1. Варианты заданных предметных областей (ХХ –2 последние цифры пароля)
ХХ Предметная область Атрибуты информации Критерий отбора
05 Программы наименование, фирма-разработчик, операционная система, стоимость Программы с нулевой стоимостью
Часть I – Статические структуры
1. На основе материалов конспекта лекций, рекомендуемой литературы и материалов сети Интернет изучить теоретический материал по программированию статических структур данных (раздел 1 конспекта лекций) и области их эффек
IT-STUDHELP
: 17 июля 2020
850 руб.
Контрольная работа по дисциплине: Алгоритмы и структуры данных. Вариант №04
IT-STUDHELP
: 17 июля 2020
Таблица 1. Варианты заданных предметных областей (ХХ –2 последние цифры пароля)
ХХ Предметная область Атрибуты информации Критерий отбора
04 Радиодетали обозначение, тип, номинал, количество на схеме, обозначение возможного заменителя Детали, не имеющие заменителей
Часть I – Статические структуры
1. На основе материалов конспекта лекций, рекомендуемой литературы и материалов сети Интернет изучить теоретический материал по программированию статических структур данных (раздел 1 конспекта лекций)
IT-STUDHELP
: 17 июля 2020
850 руб.
Другие работы
Вычислительная математика. Лабораторные работы №№1-3. Вариант №7
Damovoy
: 27 октября 2020
Лабораторная работа 1
Линейная интерполяция
Задание на лабораторную работу
1. Рассчитать h – шаг таблицы функции f(x), по которой с помощью линейной интерполяции можно было бы найти промежуточные значения функции с точностью 0.0001, если табличные значения функции округлены до 4-х знаков после точки.
2. Написать программу, которая
а) выводит таблицу значений функции с рассчитанным шагом h на интервале [c, c+15h] (таблица должна содержать 2 столбца: значения аргумента и соответствующее ему округ
Damovoy
: 27 октября 2020
190 руб.
Зачетная работа по дисциплине: История экономики
Amor
: 16 октября 2013
1. Основные закономерности экономического развития, выявленные эмпирически (перечислить).
2. Основные факторы, определяющие экономическое развитие страны ( добавить недостающий):
1. географическое положение и климат;
2. менталитет;
3. ... .
3. Немецкий неолиберализм определяет роль государства в экономике как роль ... (продолжить определение).
4. Структурная перестройка экономики послевоенной Германии производилась за счет (отметить нужную цифру):
1. государственных средств;
2. частного
Amor
: 16 октября 2013
100 руб.
Гидромеханика РГУ нефти и газа им. И. М. Губкина Гидростатика Задача 4 Вариант 5
Z24
: 6 декабря 2025
Определить суммарную силу давления на торцевую стенку АВ горизонтальной цилиндрической цистерны диаметром d, заполненной жидкостью плотностью ρ, если уровень жидкости находится на расстоянии Н от дна.
Цистерна герметически закрыта и над поверхностью жидкости находится газ. Давление газа может быть больше атмосферного (тогда показание мановакуумметра равно рм0) или меньше атмосферного (тогда показание мановакуумметра равно рv0).
Определить также координаты точки приложения силы давления.
Z24
: 6 декабря 2025
150 руб.
Контрольная работа по дисциплине: Пакетная телефония. Вариант 05
Учеба "Под ключ"
: 23 марта 2025
«Проект информационного сервиса на примере SIP-телефонии»
Содержание
1. Задание 1 – Проект услуги IP- телефонии 3
2. Задание 2 – Расшифровать речевой IP-пакет 14
3. Задание 3 – Отобразить стеки протоколов 17
4. Задание 4 – Диаграммы основных процедур реализации услуг IP 22
Список использованных источников 26
1. Задание 1 - Проект услуги IP- телефонии
Спроектировать услугу IP-телефонии для локальной сети.
В данном задании необходимо:
Р
Учеба "Под ключ"
: 23 марта 2025
1500 руб.
