Министерство образования Республики Беларусь

Белорусский государственный университет

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

УТВЕРЖДАЮ

Проректор по учебной работе БГУ

А.Л.Толстик_

(подпись) (И.О.Фамилия)

(дата утверждения) Регистрационный № _ Программа основного вступительного испытания по специальности 1-31 81 09 «Алгоритмы и системы обработки больших объемов информации»

для поступающих в магистратуру Минск 2014

СОСТАВИТЕЛИ:

Кастрица О.А., доцент кафедры высшей математики, кандидат физикоматематических наук;

Буза М.К., профессор кафедры многопроцессорных систем и сетей, доктор технических наук, профессор;

Котов В.М., заведующий кафедрой дискретной математики и алгоритмики, доктор физико-математических наук, профессор;

Лиходед Н.А., профессор кафедры вычислительной математики, доктор физико-математических наук;

Орлович Ю.Л., доцент кафедры дискретной математики и алгоритмики, кандидат физико-математических наук;

Соболевская Е.П., доцент кафедры дискретной математики и алгоритмики, кандидат физико-математических наук;

Толстиков А.А., ассистент кафедры вычислительной математики РЕЦЕНЗЕНТ:

Крахотко В.В., доцент кафедры методов оптимального управления, кандидат физико-математических наук.

РЕКОМЕНДОВАНА к утверждению кафедрами:

Вычислительной математики (протокол № 12 от 23.03.2014), Высшей математики (протокол № 12 от 17.04.2014), Дискретной математики и алгоритмики (протокол № 13 от 16.04.2014), Многопроцессорных систем и сетей (протокол № 10 от 21.04.2014).

ОДОБРЕНА на Совете факультета прикладной математики и информатики (протокол № 8 от 22.04.2014).

ОТВЕТСТВЕННЫЙ за редакцию:

Соболева Т.В., доцент кафедры многопроцессорных систем и сетей, кандидат физико-математических наук.

Программа основного вступительного экзамена в магистратуру по специальности: «1 - 31 81 09 Алгоритмы и системы обработки больших объемов информации»

Математический анализ Предел функции и непрерывность. Дифференциальное исчисление функций одной переменной. Интеграл Римана. Дифференциальное исчисление функций нескольких переменных. Несобственные интегралы. Кратные, криволинейные и поверхностные интегралы. Числовые и функциональные ряды. Степенные ряды. Ряды Фурье и преобразование Фурье.

Геометрия и алгебра Аналитическая геометрия на плоскости и в пространстве. Алгебраические структуры. Матрицы и определители. Многочлены. Векторные пространства. Линейные операторы. Билинейные и квадратичные формы. Евклидовы и унитарные пространства.

Дифференциальные уравнения Линейные дифференциальные уравнения и системы с постоянными коэффициентами, методы интегрирования. Элементарные дифференциальные уравнения, интегрируемые в квадратурах. Существование, единственность и продолжимость решений дифференциальных уравнений. Дифференциальные модели процессов и явлений.

Дискретная математика и математическая логика Комбинаторные конфигурации. Производящие функции и комбинаторные подсчеты. Булевы функции и их представление. Полнота систем булевых функций. Графы, основные классы графов и их свойства. Теория сложности вычислений: классы P и NP.

Теория алгоритмов Трудоемкость алгоритмов. Рекуррентные соотношения. Трудоемкость базовых алгоритмов сортировки и поиска. Основные приемы разработки эффективных алгоритмов: динамическое программирование и метод «разделяй и властвуй». Структуры данных: списки, стеки, очереди, приоритетные очереди, система непересекающихся множеств, хеш-таблицы. Основные алгоритмы обхода графов. Алгоритмы поиска кратчайших маршрутов в графах. Максимальный поток в сети и его приложения. Бинарные поисковые деревья, AVLдеревья, 2-3 деревья.

Вычислительные методы алгебры и методы численного анализа Прямые и итерационные методы решения систем линейных алгебраических уравнений. Нелинейные уравнения и системы. Приближение функций.

Приближенное вычисление интегралов. Методы решения задачи Коши и краевых задач для обыкновенных дифференциальных уравнений.

Теория вероятностей и математическая статистика Аксиомы теории вероятностей. Одномерные и многомерные случайные величины. Функции случайных величин. Функции распределения случайных величин. Числовые характеристики случайных величин. Условное математическое ожидание. Характеристические функции. Предельные теоремы. Основные понятия математической статистики. Методы построения точечных оценок. Неравенство информации. Интервальное оценивание. Теория проверки статистических гипотез. Полиномиальная регрессия. Случайные процессы и их характеристики. Стационарные и марковские случайные процессы. Цепи Маркова.

Имитационное и статистическое моделирование Виды моделирования. Принципы имитационного моделирования. Статистическое моделирование. Датчики случайных чисел. Моделирование дискретных и непрерывных случайных величин, случайных процессов. Метод Монте-Карло и его применения.

Методы оптимизации Линейного программирования. Транспортные задачи в сетевой и матричной форме. Выпуклое программирование. Теорема Куна-Таккера. Нелинейное программирование. Динамическое программирование. Метод ветвей и границ.

Исследование операций Матричные игры и методы их решений. Алгоритмы решения задачи коммивояжера и ее приложения. Задачи теории расписаний и их классификация. Общая характеристика задач массового обслуживания. Задача управления запасами.

Программирование Структура компьютера и программного обеспечения. Основные парадигмы программирования и этапы разработки приложений. Классификация и сравнительный анализ языков программирования. Средства разработки приложений. Принципы функционирования микропроцессоров и язык ассемблера. Платформонезависимое программирование сетевых приложений. Основные концепции объектно-ориентированного программирования.

Операционные системы Процессы. Ядро операционной системы. Потоки. Планирование процессов и потоков. Синхронизация процессов и потоков. Межпроцессные взаимодействия и коммуникации. Память и адресное пространство процесса. Файлы, отображаемые в адресное пространство процесса. Управление устройствами.

Файловые системы. Безопасность и механизмы защиты операционных систем.

Параллельные вычисления Информационная структура алгоритма. Зависимости. Функции зависимостей. Графы зависимостей. Параллельные множества операций. Параллельная форма алгоритма. Параллельные последовательности вычислений. Разбиение операций алгоритма на тайлы. Допустимость тайлинга. Локальность параллельного алгоритма. Параллельные вычисления на графических процессорах. Законы Амдала. Модель вычислений MapReduce.

Модели данных и СУБД Классификация, структура, составные части, интерфейсы СУБД. Типы моделей данных. Теория реляционных баз данных. Язык SQL.

Компьютерные сети Компьютерные телекоммуникации. Сетевые модели и протоколы.

Управление каналами связи. Методы передачи дискретных данных. Технологии локальных сетей. Архитектура беспроводных сетей. Принципы коммутации. Построение составных сетей на основе стека протоколов TCP/IP. Принципы маршрутизации. Структура и функции глобальных сетей. Удаленный доступ. Архитектура прикладных протоколов Internet. Управление сетями. IPтелефония.

ЛИТЕРАТУРА

1. Ахо, А. В. Структуры данных и алгоритмы / А. В. Ахо, Д. Э. Хопкрофт, Д.

Д. Ульман. : Учеб. пособие/ пер. с англ. М. : Вильямс, 2000. – 384 с.

2. Богданов Ю.С. Лекции по математическому анализу. Мн.: изд-во БГУ, 1974, 1978. Ч.1-2.

3. Богданов, Ю.С. Математический анализ / Ю.С. Богданов, О. А. Кастрица, Ю. Б. Сыроид М.: ЮНИТИ-ДАНА, 2003. 351 с.

4. Богданов, Ю.С. Дифференциальные уравнения / Ю. С. Богданов, Ю. Б.

Сыроид Мн.: Выш. школа, 1983. 239 с.

5. Богданов, Ю.С. Курс дифференциальных уравнений / Ю. С. Богданов, С.

А. Мазаник, Ю. Б. Сыроид Мн.: Университетское, 1996. 287 с.

6. Вагнер Г. Основы исследования операций: в 3-х томах. М.: Мин, 1972-73.– 335 с., – 487 с., – 501 с.

7. Вентцель Е. С. Исследование операций. М.: Сов. Наука, 1972. – 550 с.

8. Воеводин, В.В. Параллельные вычисления / В. В. Воеводин, Вл. В. Воеводин. СПб. : БХВ-Петербург, 2002. – 608 с.

9. Воробьев Н.Н. Теория игр. Ленинград: ЛГУ, 1975. – 324.

10. Габасов, Р. Методы оптимизации: Учебное пособие / Р. Габасов, Ф. М.

Кириллова – Мн.: Изд-во БГУ, 1981. – 350 с.

11. Гамма, Э. Приемы объектно-ориентированного проектирования. Паттерны проектирования / Гамма Э., Хелм Р., Джонсон Р., Влиссидс Дж. — СПб.: Питер, 2007. — 366 с. — (Серия "Библиотека программиста").

12. Дегтярев Ю.И. Исследование операций. М.: Высшая школа, 1986. – 319с.

13. Дейт К. Дж. Введение в системы баз данных — 8-е изд. — М.: Вильямс, 2006. — 1328 с.

14. Демидович Б.П. Сборник задач и упражнений по математическому анализу. М.: Наука, 1998. 624с.

15.Емеличев, В. А. Лекции по теории графов/ В. А. Емеличев, О. И. Мельников, В. И. Сарванов, Р. И. Тышкевич. М.: Наука, 1990. 383 с.

16. Зорич В. А. Математический анализ. М.: Наука, 1997, 1998. Ч.1- 17. Игошин В. И. Теория алгоритмов: учеб. пособие для студ. высш. учеб. заведений / В. И. Игошин. ИНФРА-М, 2012. – 318 с.

18. Ильин, В.А. Математический анализ / В.А. Ильин, В.А. Садовничий, Бл. Х.

Сендов. М.: изд-во Моск. ун-та, 1985, 1987. Ч.1–2.

19. Иржавский, П. А. Теория алгоритмов: учеб. пособие / П. А. Иржавский, В.М. Котов, А.Ю. Лобанов, Ю.Л. Орлович, Е.П. Соболевская – Минск :

БГУ, 2013. – 159 с.

20. Кормен, Т. Алгоритмы : построение и анализ/ Т. Кормен, Ч. Лейзерсон, Р.

Ривест, К. Штайн. М. : Вильямс, 2005. 1296 с.

21. Котов, В. М. Алгоритмы и структуры данных: учеб. пособие / В.М. Котов, Е.П. Соболевская, А.А. Толстиков – Минск : БГУ, 2011. – 267 с. – (Классическое университетское издание).

22. Краснов, М. Л. Функции комплексного переменного. Операционное исчисление. Теория устойчивости. / М.Л. Краснов, А.И. Киселёв, Г.И. Макаренко М.: Наука, 1981. 303с.

23. Крылов, В.И. Вычислительные методы высшей математики / В. И. Крылов, В. В. Бобков, П. И. Монастырный – Мн.: Выш. школа, 1972.– 594 с.

24. Крылов, В.И. Вычислительные методы / В. И. Крылов, В. В. Бобков, П. И.

Монастырный – Том 1, М.: Наука, 1972.– 594 с.

25. Кудрявцев Л.Д. Курс математического анализа. М.: Высш. шк.: 1988, 1988, 1989. Т.1-3.

26. Липский В. Комбинаторика для программистов. М.: Мир, 1988. 214с.

27. Лиходед Н. А. Методы распараллеливания гнезд циклов: курс лекций. Минск : БГУ, 2008. – 100 с.

28. Олифер, В. Компьютерные сети. Принципы, технологии, протоколы / В.

Олифер, Н. Олифер — 4-е изд. — СПб.: Питер, 2014. — 944 с. — (Серия «Классика computer science»).

29. Пападдимитриу, Х. Комбинаторная оптимизация: Алгоритмы и сложность/ Х. Пападдимитриу, К. Стайглиц. М.: Мир, 1971. 512 с.

30. Размыслович, Г. П. Геометрия и алгебра / Г. П. Размысорвич, М. М. Феденя, В. М. Ширяев – Мн.: Университетское, 1987.– 350 с.

31. Размыслович, Г. П. Сборник задач по геометрии и алегебре / Г. П. Размысорвич, М. М. Феденя, В. М. Ширяев – Мн.: Университетское, 1999.– 32. Рейнгольд, Э. Комбинаторные алгоритмы теория и практика/ Э. Рейнгольд, Ю. Нивергельт, Н. Део. М.: Мир, 1980. 476 c.

33. Сидоров, Ю.В. Лекции по теории функций комплексного переменного / Ю.В. Сидоров, М.В. Федорюк, М.И. Шабунин. М.: Наука, 1989. 408с.

34. Стенли Р. Перечислительная комбинаторика. М.: Мир, 1990. – 440 с.

35. Танаев, В.С. Введение в теорию расписаний / В. С. Танаев, В. В. Шкурба – М.: Наука, 1975.– 256 с.

36. Таненбаум Э. Современные операционные системы — 3-е изд. — СПб.:

Питер, 2010. — 1120 с. — (Серия «Классика computer science»).

37. Таненбаум, Э. Компьютерные сети / Таненбаум Э., Уэзеролл Д. — 5-е изд. — СПб.: Питер, 2014. — 960 с. — (Серия "Классика computer science").

38. Таха Х. А. Введение в исследование операций. М., С.–Петербург, Киев:

Изд. Дом Вильямс, 2001. – 911 с.

39. Тер-Крикоров, Курс математического анализа / А. М. Тер-Крикоров, М.

И. Шабунин М.: Наука, 1997. 720с.

40.Тышкевич, Р.И. Линейная алгебра и аналитическая геометрия / Р. И. Тышкевич, А. С. Феденко – Мн.: Выш. школа, 1976. – 544 с.

41. Форд, Л. Потоки в сетях / Форд Л., Фалкерсон Д. – Мир, 1966.– 276 с.

42. Харин, Ю. С. Математическая и прикладная статистика / Ю. С. Харин, Е.

Е. Жук – Мн.: БГУ, 2005. – 279 с.

43. Харин, Ю. С. Теория вероятностей / Ю. С. Харин, Н. М. Зуев – Мн.: БГУ, 2004. – 199 с.

44. Ширяев А. Н. Вероятность. В 2-х кн. – Москва: МЦНМО, 2004. – 928 с.

45. Яблонский С.В. Введение в дискретную математику. – М.: Наука, 1979. –