Помощничек
Главная | Обратная связь


Археология
Архитектура
Астрономия
Аудит
Биология
Ботаника
Бухгалтерский учёт
Войное дело
Генетика
География
Геология
Дизайн
Искусство
История
Кино
Кулинария
Культура
Литература
Математика
Медицина
Металлургия
Мифология
Музыка
Психология
Религия
Спорт
Строительство
Техника
Транспорт
Туризм
Усадьба
Физика
Фотография
Химия
Экология
Электричество
Электроника
Энергетика

Задания для аудиторной работы. № 1. Построить остовное дерево наименьшего веса для следующих графов:



№ 1. Построить остовное дерево наименьшего веса для следующих графов:

а) б)

в) г)

№ 2. Дан граф П с 7 вершинами, где заданы длины ребер:

а)AB=7, AD=12, AM=5, BE=11, BK=9, BM=7, CM=6, CD=10, EM=5, EK=12, DM=5, KM=6, AK=6;

б) AB=6, AC=11, AM=4, BE=12, BK=10, BM=8, CM=5, CD=9, EM=7, EA=13, DM=4, KM=7, EC=6.

Построить остовное дерево графа П, не выполняя построение исходного графа.

№ 3. Известны длины ребер графа П: АБ=7, АД=12, АМ=5, БГ=11, БК=9, БМ=7, ВМ=6, ВД=10, ГМ=6, ГК=12, ДМ=5, КМ=6, АК=6. Найти кратчайшее расстояние:

а) от вершины А до всех остальных и восстановить путь от А до всех вершин графа;

б) от вершины М до всех остальных и восстановить путь от М до всех вершин графа;

в) от вершины Г до всех остальных и восстановить путь от Г до всех вершин графа.

№ 4. Дана сеть П. Найти максимальный поток через сеть.

а) б)

в) г)

Задания для самостоятельной работы

№ 1. Построить остовное дерево наименьшего веса для следующих графов:

а) б)

в) г)

№ 2. Дан граф П с 7 вершинами, где заданы длины ребер:

а) AB=9, BC=5, CD=2, DE=8, EF=3, FG=7, AG=2, AM=3, AH=5, BM=8, BK=4, CK=3, DK=9, EK=9, MK=6, KH=8, EH=6, FH=1,GH=4;

б) AB=7, AK=9, AM=6, AH=2, AG=4, BK=5, BM=7, BC=4, CD=3, CM=9, DM=4, DE=8, KM=2, MH=3, ME=6, DE=8, EH=5, EF=4, FG=9, GH=8.

Построить остовное дерево графа П, не выполняя построение исходного графа.

№ 3. Известны длины ребер графа П: AB=7, BC=5, CD=4, DE=7, EF=8, FG=6, AG=5, AH=2, BH=9, GH=4, HK=7, BK=3, CK=9, DK=8, KM=5, DM=9, KF=8, FM=2. Найти кратчайшее расстояние

а) от вершины А до всех остальных и восстановить путь от А до всех вершин графа;

б) от вершины М до всех остальных и восстановить путь от М до всех вершин графа;

в) от вершины C до всех остальных и восстановить путь от C до всех вершин графа.

№ 4. Дана сеть П. Найти максимальный поток через сеть.

а) б)

 

Литература

Основная

1. Бабаш, А. Криптография / А. Бабаш, Г. Шанкин. – М. : Солон-Пресс, 2007. – 512 с. – ил.

2. Громкович, Ю. Теоретическая информатика / Ю. Громкович. – 3-е изд. – СПб. : BHV, 2010. – 336 с.

3. Могилев, А. В. Практикум по информатике / А. В. Могилев, Н. И. Пак, Е. К. Хеннер. – М. : Академия, 2005. – 608 с.

4. Новиков, Ф. А. Дискретная математика для программистов / Ф. А. Новиков. – СПб. : Питер, 2009. – 384 с. – ил.

5. Острейковский, В. А. Информатика. Теория и практика / В. А. Острейковский. – М. : Оникс, 2008. – 608 с. – ил.

Дополнительная

1. Алгоритм Дейкстры. – Режим доступа: algolist.manual.ru/maths/graphs/shortpath/dijkstra.php

2. Алгоритм Флойда. – Режим доступа: algolist.manual.ru/maths/graphs/shortpath/floyd.php

3. Белова, И. М. Компьютерное моделирование / И. М. Белова. – Режим доступа: window.edu.ru/window/

4. Будко, В. Н. Информационная безопасность и защита информации : конспект лекций / В. Н. Будко. – Режим доступа: window.edu.ru/window/

5. Иванов, Б. Н. Дискретная математика. Алгоритмы и программы : учеб. пособие / Б. Н. Иванов. – М. : Лаборатория базовых знаний, 2001. – 288 с.

6. Информатика : учеб. / под ред. проф. Н. В. Макаровой. – 2-е изд. – М. : Финансы и статистика, 1998. – 768 с.

7. Кассами, Т. и др. Теория кодирования / Т. Кассами. – М. : Мир, 1978. – 876 с.

8. Могилев, А.В. Информатика / А. В. Могилев, Н. И. Пак, Е. К. Хеннер. – М. : Академия, 2004. –848 с.

9. Брукшир, Дж. Г. Введение в компьютерные науки. Общий обзор / Дж. Г. Брукшир. – 6-е изд. – М. : Вильямс, 2001. – 688 с.

10.Нахождение максимального пропускного потока. – Режим доступа: algolist.manual.ru/maths/graphs/netflow.php

11. Нахождение на графе минимального остовного дерева. – Режим доступа: algolist.manual.ru/maths/graphs/span.php

12. Основы современных компьютерных технологий : сборник / под. ред. проф. А. Д. Хомоненко. – СПб. : Корона принт, 1998. – 448 с.

13. Рыжиков, Ю. И. Информатика : лекции и практикум / Ю. И. Рыжиков. – СПб. : Корона принт, 2000. – 256 с.

14. Кузнецов, С. Д. Методы сортировки и поиска / С. Д. Кузнецов. – Режим доступа: algolist.manual.ru/

15. Сергиевская, И. М. Математическая логика и теория алгоритмов : учебное пособие / И. М. Сергиевская. – Режим доступа: window.edu.ru/window/

16. Тарасевич Ю.Ю. Математическое и компьютерное моделирование: Учебное пособие - М.: Едиториал, 2003. - 144с.

17. Тарасевич Ю.Ю. Элементы дискретной математики для программистов. window.edu.ru/window/

18. Яблонский С.В. Введение в дискретную математику. – М.: Высшая школа. 2001. – 384 с.

 

Учебное издание

 

 


 




Поиск по сайту:

©2015-2020 studopedya.ru Все права принадлежат авторам размещенных материалов.