Задача распространения информации в сети

МИНИСТЕРСТВО ОБРАЗОВАНИЯ РЕСПУБЛИКИ БЕЛАРУСЬ

БЕЛОРУССКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

ФАКУЛЬТЕТ ПРИКЛАДНОЙ МАТЕМАТИКИ И ИНФОРМАТИКИ

Кафедра дискретной математики и алгоритмики

ЗАДАЧА РАСПРОСТАНЕНИЯ ИНФОРМАЦИИ В СЕТИ

Курсовой проект

Клицунов Андрей Владимирович

студента 3 курса, 3 группы

специальность «Информатика»

Научный руководитель:

доцент О.И. Дугинов

Минск, 2016

БЕЛОРУССКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

Факультет прикладной математики и информатики

Кафедра дискретной математики и алгоритмики

УТВЕРЖДАЮ

Заведующий кафедрой

                           В.М. Котов

«      »                          20    

ЗАДАНИЕ ПО ПОДГОТОВКЕ КУРСОВОЙ РАБОТЫ

Студенту   3   курса                                         Клицунову Андрею                                                 

1. Тема работы                       Задача распространения информации в сети                             

2. Срок сдачи студентом законченной работы                                                                             

3. Перечень вопросов подлежащих разработке или краткое содержание работы                

1) задача распространения информации по сети и её различные варианты: вариант задачи, когда граф ориентированный, вариант задачи с несколькими источниками сообщения;

2) сложность решения задачи;

3) разработать эвристические алгоритмы для решения указанной задачи;

4) реализовать разработанные алгоритмы и протестировать их на батарее случайных графов.

5) модель случайного графа Эрдёша-Реньи

4. Дата выдачи задания «       »                              20     г.

[pic 1]

Руководитель                                                      /   Дугинов О.И.   /

Задание принял к исполнению «       »                        20     г.

    (подпись студента)

ОГЛАВЛЕНИЕ

ВВЕДЕНИЕ        5

1 Задача распространения информации в сети        6

1.1 Необходимая теоретическая информация        6

1.2 Классическая постановка задачи и её обобщения         6

1.3 Полезные утверждения        7

1.4 Эвристические алгоритмы        8
    1.4.1 Алгоритмы первой группы        ..8

     1.4.2 Алгоритмы второй группы        10

      1.4.3 Алгоритмы третьей группы        12

      1.4.4 Алгоритмы четвёртой группы        14        

1.5 Реализация алгоритмов, вывод и краткий анализ результатов        16

1.6 Итоги        23

ЗАКЛЮЧЕНИЕ        25

СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ        26

ПРИЛОЖЕНИЯ        27

Реферат

Курсовой проект, 30 с., 3 источника, 13 таблиц, 1 изображение, 1 приложение.

ЗАДАЧА РАСПРОСТАНЕНИЯ ИНФОРМАЦИИ В СЕТИ.

Объект исследования – графы.

Цель работы – разработать алгоритмы приближённого решения задачи, протестировать их на батарее случайных графов (модель Эрдёша-Реньи), сделать сравнительный анализ алгоритмов.