Чтобы посмотреть этот PDF файл с форматированием и разметкой, скачайте его и откройте на своем компьютере.
ПРОГРAММА
вступительного экзамена
по сп
ециальности
в аспирантуру
на направление подготовки 09
.06.01
«
Информатика и вычислительная техника
»
Профиль 1 «
Теоретические основы информатики
»
аспирантов
очной формы обучения
кафедры
«
Прикладной информатики и тео
рии вероятностей
»
ОСНОВНАЯ ЧАСТЬ
Введение
В основе настоящей программы лежит материал курсов: теория графов, математическая
теория телетрафика, математическое мо
делирование, численные методы.
Программа
разработана экспертным советом Высшей аттестационной
комиссии Министерства
образования Российской Федерации по управлению, вычислительной технике и
информатике при участии МГУ им. М.В. Ломоносова.
Раздел 1. Теория графов [5], [6], [7]
1.
Графы. Основные определения, пути, маршруты, цепи, циклы; связность, дере
вья и
леса [5] §§1.1
-
1.4, [6] §§1.1.
-
1.5, [7] §§7.1
-
7.3
2.
Типы графов. Сильно связанные графы и компоненты графа. Матричные
представления [5] §§1.6
-
l.8, [7] §7.4
3.
Достижимость и связность. Матрицы достижимостей. Транзитивное замыкание.[5]
§§2.1
-
2.4, [7] §§7.5
, 8.1
-
8.3
4.
Раскраски графов [5] гл.4, [6] гл. 5, [7] §10.7
5.
Циклы и разрезы. Независимые и покрывающие множества. [7] §§10.1, 10.4
-
10.б
6.
Потоки в сетях [5] гл.11, [6] гл.6, [7] §8.4
Раздел 2. Теория марковских процессов [2], [4]
7.
Определение и основные свойст
ва цепи Маркова с дискретным множеством состояний
[2] §1.4.1
8.
Эргодичность и равновесное распределение цепи Маркова с дискретным множеством
состояний [2] § 1.4.1
9.
Марковские процессы с дискретным множеством состояний. Скачкообразный
Марковский процесс. Опред
еления и инфинитезимальные характеристики.
Конструктивное описание. Эргодичность и равновесное распределение [2] §§1.5.1
-
5.2
10.
Марковские процессы с дискретным множеством состояний. Система
дифференциальных уравнений Колмогорова. Стационарные Марковские проц
ессы.
Эргодичность Марковского процесса [2] §§1.5.3
-
1.5.6
11.
Процесс размножения и гибели. Условие Карлина
-
МакГрегора [2] § 1.5.7
12.
Обратимые Марковские процессы. Критерий Колмогорова. Сужение Марковского
процесса [4] §§1.2, 1.5
-
1.7
Раздел 3. Математическая те
ория телетрафика [1], [2], [3]
13.
Системы массового обслуживания (СМО). Входящий поток: пуассоновский,
марковский, рекуррентный, эрланговский. Длительность обслуживания:
экспоненциальная, гиперэкспоненциальная, эрланговская, гиперэрланговская,
фазового типа.
Дисциплины обслуживания. Показатели производительности.
Структура и Классификация СМО [2] §§2.1
-
2.6
14.
Первая модель Эрланга. Распределение и первая формула Эрланга [1] §1.1
15.
Первая модель Эрланга с ожиданием и блокировками. Второе распределение Эрланга
[1] §1
.3
16.
Модель Энгсета. Распределение числа занятых линий [1] §§1.4.1
-
1.4.4
17.
Мультисервисная модель Эрланга с явными потерями. Пространство состояний
системы. Теорема о равновесном распределении. Вероятность потерь. Рекуррентный
алгоритм вычисления макрохарактер
истик [1] §§2.2.
-
2.6, [3] §2.1
18.
Две мультисервисные модели Энгсета с явными потерями. Основные предположения
и параметры. Пространство состояний. Теоремы о равновесном распределении.
Рекуррентный алгоритм вычисления макрохарактеристик [1] §§3.1
-
3.5
ЛИТЕРА
ТУРА
[1].
Бaшарин Г.П.
Лекции по математической теории телетрафика
// М.: Изд
-
во
РУДН, 2004.
[2].
Бочаров П.П., Печинкин А.В.
Теория массового обслуживания
// М.: Изд
-
во
РУДН,1995.
[3].
Лагутин В.С., Степанов С.Н.
Телетрафик мультисервисных сетей связи
//
М.: Радио
и связь, 2000.
[
4
].
Ке
ll
у
F.P.
Reversibi1ity and stochastic networks
// John Wiley & Sons, 1979.
[5].
Кристофидес Н.
Теория графов. Алгоритмический подход
// М.: Мир, 1978.
[
6
].
Diestel R.
Graph
Т
heory
// New York: Springer
-
Verlag, 1997
-
2000
.
[7
].
Новиков
Ф.А.
Дискретная математика для программистов
// СПб.: Питер, 2004.