ПРОГРАММА

вступительных экзаменов в аспирантуру Российского университета дружбы

народов по специальности 05.13.17 «Теоретические основы информатики»

I. Дискретная математика.

1. Модели комбинаторных конфигураций; размещения, перестановки,

сочетания. Биноминальные и полиномиальные коэффициенты и их

свойства.

2. Генерация и сортировка перестановок.

3. Принцип включения и исключения. Основная формула включений и исключений. Формула числа элементов, обладающих ровно m свойствами.

4. Производящие функции. Применение ПФ в комбинаторике, ТВ и ТМО.

5. Неориентированные графы: основные определения, локальные свойства, маршруты, цепи, циклы; связность, деревья и леса.

6. Ориентированные графы: основные определения, локальные свойства, ормаршруты, пути, контуры.

7. Матрицы смежности и инцидентности, списки смежности и списки инцидентности неориентированного графа и орграфа.

8. Метод поиска в глубину, алгоритм метода. Метод поиска в ширину, алгоритм метода.

9. Алгоритм Дейкстры поиска кратчайшего пути между заданными вершинами.

10. Потоки в сетях. Теорема Форда-Фолкерсона.

II. Теория вероятностей.

11. Многомерные СВ и их ФР. Дискретные и непрерывные двумерные СВ.

Условные распределения и независимые СВ.

12. Числовые характеристики одномерных и многомерных СВ. Свойства математического ожидания и дисперсии. Моменты многомерных СВ.

Свойства коэффициента корреляции и корреляционной матрицы. Условные математические ожидания и регрессия. Виды сходимости СВ.

13. Основные одномерные дискретные (биномиальное, пуассоновское, геометрическое) и непрерывные (равномерное, экспоненциальное, нормальное, гамма, эрланговское, Парэта) распределения.

14. Многомерное нормальное распределение.

15. Определение и основные свойства характеристических функций. ХФ основных распределений.

16. Неравенство Чебышева и закон больших чисел. Центральная предельная теорема.

17. Определения и основные свойства однородной цепи Маркова, ее орграф.

Матрицы смежности, достижимости и сообщаемости. Топологическая и вероятностная классификация состояний. Эргодичность и равновесное распределение.

18. Общее определение марковского процесса. Скачкообразный марковский процесс. Определения и инфинитезимальные характеристики.

Конструктивное описание. Эргодичность и равновесное распределение.

Процесс размножения и гибели. Теорема Феллера. Условия КарлинаМакгрегора.

19. Обратимые марковские процессы.

III. Теория систем и сетей массового обслуживания.

20. Система массового обслуживания (СМО). Входящий поток: пуассоновский, марковский, рекуррентный, эрланговский. Длительность обслуживания:

экспоненциальная, гиперэкспоненциальная, эрланговская, гиперэрланговская, фазового типа. Дисциплины обслуживания. Показатели производительности. Структура и классификация СМО.

21. M | M | v | 0 – модель Эрланга с явными потерями. Вывод СУР и ее решение.

µ Распределение Эрланга. Ev ( ) – функция потерь Эрланга и рекуррентная формула ее вычисления. Случай v.

22. M | M | v | 0 – модель Энгсета с явными потерями. Вывод СУР и ее решение N, µ для случаев а) N > v – распределение Энгсета, б) N v - биномиальное распределение.

23. Связь между потерями по времени и по заявкам для распределения Энгсета.

Получение распределения Эрланга из распределения Энгсета с помощью предельного перехода.

24. M | M | v | r – модель Эрланга с неявными потерями. Вывод СУР и ее µ решение, средняя длина очереди. Для 0 r доказать равенство интенсивностей принятого и обслуженного потоков. Для r =, < v вывести формулу для вероятности задержки и выразить ее через Ev ( ).

25. M | M | v | 0 – модель ШЦЛ с явными потерями. Основные понятия и,b µ обозначения. Формулировка и доказательство основной теоремы.

Рекуррентные соотношения для распределения qn, n = 0, v.

26. M | M | v | 0 – модель ШЦЛ с явными потерями и конечным числом N,,b µ источников нагрузки (типа Энгсет-1). Основные понятия и обозначения.

Формулировка и доказательство основной теоремы. Рекуррентные соотношения для qn, n = 0, v и предельная теорема при N.

27. Математическая модель сложной буферной памяти.

28. Математическая модель системы спутниковой связи.

29. Открытая однородная экспоненциальная сеть МО. Описание и параметры модели. Маршрутизация, интенсивность потоков в узлах сети. Условия эргодичности.

30. Частота посещений заявкой узлов сети. Теорема Джексона о равновесном распределении.

31. Замкнутая однородная экспоненциальная сеть МО. Описание и параметры модели. Маршрутизация. Теорема Гордона-Ньюелла о мультипликативности равновесного распределения.

32. Алгоритм свертки для расчета нормировочной константы. Схема вычисления в алгоритме Базена для однолинейных узлов. Вычисление ВВХ.

33. Управление доступом для M | M | v | 0. Резервирование. Координатноb µ выпуклые стратегии. Четыре основных стратегии и связь между ними.

34. Оптимизация. Доходность для СМО с явными потерями.

35. M | M | v | 0 - модель мультисервисной ШЦЛ с ограниченным доступом по числу k-сообщений. Пространство состояний. Теорема о равновесном распределении. Основные характеристики.

36. M | M | v | 0 - модель мультисервисной ШЦЛ с индивидуальными потолками по общему числу занятых БЦК.

IV. Информационные системы.

37. Представление данных. Структуры данных. Уровни представления данных.

38. Система управления базами данных. Архитектура СУБД. Функции СУБД.

Классы структур данных. Иерархическая, сетевая, реляционная структуры.

39. Реляционная модель данных. Реляционная алгебра. Реляционное исчисление. Нормальные формы.

40. Объектно-ориентированное анализ и проектирование. Абстрагирование, инкапсуляция, модульность, иерархия, типизация. Классы и объекты.

Отношения между классами: ассоциация, наследование, агрегация, использование, инстанцирование.

41. Общие принципы построения открытых систем. Иерархия функций взаимодействия открытых систем. Понятие о протоколе и межуровневом интерфейсе.

42. Модель взаимодействия открытых систем. Характеристики протоколов семиуровневой модели. Сравнение семиуровневой модели с моделью стека протоколов TCP/IP 1. Башарин Г.П. Введение в теорию вероятностей. Уч. пособие. // М,: Изд.

УДН, 1990.

2. Башарин Г.П. Введение в математическую статистику. Уч. пособие. // М.:

Изд.УДН,1993.

3. Башарин Г.П. Математическая теория телетрафика. Уч. пособие. // М.:

Изд. УДН, 2004.

4. П.П. Бочаров, А.В. Печинкин Теория вероятностей и математическая статистика. Уч. пособие. // М.: Гардарика, 1998.

5. Клейнрок Л. Теория массового обслуживания. // М.: Машиностроение, 1979.

6. Башарин Г.П., Бочаров П.П., Коган Я.А. Анализ очередей в вычислительных сетях. Теория и методы расчета. // М.: Наука, ИГРФМЛ, 1989.

7. П.П. Бочаров, А.В. Печинкин Теория массового обслуживания. Учебник.// М.: Изд-во РУДН, 1995.

8. Самуйлов К.Е., Севастьянов Л.А., Спесивов С.С. и др. Лекции по дискретной математике: Учебное пособие. Часть1, Часть 2// М.: Изд-во РУДН, Все годы издания.

9. Н. Кристофидес. Теория графов: Пер. с англ. // М.: Мир, 1978.

10. Таненбаум Э. Компьютерные сети // Спб.: «Питер», 11. К.Дейт. Введение в системы баз данных. // Киев-Москва, Диалектика, 1998.

12. Буч Г. Объектно-ориентированный анализ и проектирование // СПб: Бином,