ПРОГРAММА
кандидатского экзамена по специальности
«Теоретические основы информатики» (05.13.17)
аспиранта очной формы обучения кафедры
«Прикладной информатики и теории вероятностей»
Этезова Шамиля Асхатовича
ОСНОВНАЯ ЧАСТЬ
Введение
В основе настоящей программы лежит материал курсов: теория графов, математическая теория телетрафика, математическое моделирование, численные методы. Программа разработана экспертным советом Высшей аттестационной комиссии Министерства образования Российской Федерации по управлению, вычислительной технике и информатике при участии МГУ им. .
Раздел 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
СПЕЦИАЛЬНАЯ ЧАСТЬ
Раздел 4. Математические модели для анализа мультисервисных сетей [8]-[16]
19. Модель отдельного звена мультисервисной сети с многоадресными соединениями [8,11]
20. Модель звена мультисервисной сети в условиях предоставления одной услуги мультивещания в виде СМО с «прозрачными» заявками с учетом двух моделей поведения пользователей [10]
21. Рекуррентный алгоритм расчета вероятностных характеристик модели звена с многоадресными соединениями [8,11]
22. Метод просеянной нагрузки для расчета вероятностей блокировок в сети с многоадресными соединениями [8]
23. Модель отдельного звена мультисервисной сети с одноадресными и многоадресными соединениями [8,11]
24. Метод свертки для расчета вероятностных характеристик модели звена с одноадресными и многоадресными соединениями [8,11]
25. Метод просеянной нагрузки для расчета вероятностей блокировок в сети с одноадресными и многоадресными соединениями [8,9]
26. Модели отдельного звена сети с эластичным трафиком [12,13]
27. Метод просеянной нагрузки для расчета вероятностей блокировок в сети с эластичным трафиком [14]
28. Модели и приближенные методы анализа отдельного звена мультисервисной сети с одноадресными соединениями и эластичным трафиком [15,16]
ЛИТЕРАТУРА
Литература для основной части
[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.
Литература для специальной части. Тема «Математические модели для анализа мультисервисных сетей»
[[8]. Наумов В. А., Самуйлов К. Е., Яркина Н. В. Теория телетрафика мультисервисных сетей: Монография. – М.: РУДН. – 2007. – 191 с.
[9]. Степанов телетрафика мультисервисных сетей. – М.: Эко-Трендз. – 2010. – 392 с.
[10]. Плаксина О. Н. О двух системах массового обслуживания с «прозрачными» заявками и их применении к анализу услуг мультивещания // Вестник РУДН. Серия «Математика, информатика, физика». – 2010. – № 2(1). – С. 37–41.
[11]. Boussetta K., Belyot A.-L. Multirate resource sharing for unicast and multicast connections // Proc. of the 5th International Conference on Broadband Communications, Hong Kong. – 1999. – P. 561–570.
[12]. Bonald T., Virtamo J. A recursive formula for multirate systems with elastic traffic // IEEE Communications Letters. – 2005. – Vol. 9, No. 8. – P. 753–755.
[13]. Bonald T., Tran M.-A. Balancing elastic traffic sources // IEEE Communications Letters. – 2007. – Vol. 11, No. 8. – P. 692–694.
[14]. Гудкова И. А. Метод просеянной нагрузки для мультисервисной сети с эластичным трафиком // T-Comm – Телекоммуникации и Транспорт. – М.: Издательский дом Медиа Паблишер. – 2011. – (в печати).
[15]. Bonald T., Proutiere A. On performance bounds for the integration of elastic and adaptive streaming flows // Proc. of the Joint International Conference on Measurement and Modeling of Computer Systems, New York, USA, 12–16 June 2004. – Vol. 32, No. 1. – P. 235–245.
[16]. Boxma O. J., Gabor A. F., Núñez-Queija R., Tan H. P. Performance analysis of admission control for integrated services with minimum rate guarantees // Proc. of the 2nd Conference on Next Generation Internet Design and Engineering, Valencia, Spain, 3–5 April 2006. – P. 41–47.
Научный руководитель д. т.н., профессор
Заведующий кафедрой д. т.н., профессор
