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

Учреждение образования

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

информатики и радиоэлектроники»

УТВЕРЖДАЮ

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

и социальным вопросам

А.А. Хмыль

12» _июня_ 2013 г.

ПРОГРАММА

вступительного экзамена в магистратуру по специальности 1-40 81 01 Информатика и технологии разработки программного обеспечения Минск 2013 Программа составлена на основании типовых учебных программ дисциплин «Программирование», «Геометрия и алгебра», «Дискретная математика и математическая логика», «Методы численного анализа», «Компьютерные сети», «Системное программирование», «Модели данных и системы управления базами данных» специальности «Информатика» первой ступени высшего образования.

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

Минченко Леонид Иванович – доктор физико-математических наук, профессор, заведующий кафедрой информатики БГУИР;

Волосевич Алексей Александрович – кандидат физико-математических наук, доцент, доцент кафедры информатики БГУИР;

Сиротко Сергей Иванович – кандидат физико-математических наук, доцент, доцент кафедры информатики БГУИР.

РЕКОМЕНДОВАНА К УТВЕРЖДЕНИЮ:

Кафедрой информатики учреждения образования «Белорусский государственный университет информатики и радиоэлектроники»

(протокол № 17 от «08» апреля 2013 г.) Заведующий кафедрой Минченко Л. И.

Раздел 1. Математические основы. Теория алгоритмов.

Тема 1.1. Множества и отображения.

Множества. Операции над множествами. Мощность множеств. Счётные и несчётные множества. Отображения. Линейные пространства. Норма и нормированные пространства. Матричные нормы. Полные метрические пространства.

Принцип сжимающих отображений и его приложения.

Тема 1.2. Алгебра логики.

Булевы функции. Базис булевых функций. Нормальные формы.

Тема 1.3. Основы теории графов.

Графы и сети. Свойства графов. Операции на графах. Отношения на множествах и графы.

Тема 1.4. Элементы теории алгоритмов.

Интуитивные свойства алгоритмов. Алгоритмические проблемы: разрешимые, неразрешимые и частично разрешимые. Формальные уточнения понятия «алгоритм»: частично рекурсивные функции, регистровые машины, машины Тьюринга. Сложностная классификация массовых задач. Сложность по Колмогорову.

Тема 1.5. Алгебраические структуры.

Теория групп и её приложения. Сравнения. Кольца. Поля Галуа. Основные теоретико-числовые алгоритмы: расширенный алгоритм Евклида, алгоритм быстрого возведения в степень. Модулярная арифметика. Классификация алгоритмов шифрования. Блочные алгоритмы шифрования. Шифрование с открытым ключом. Функция хэширования и её алгоритмы вычисления.

Раздел 2. Численные методы.

Тема 2.1. Задачи линейной алгебры.

Методы решения систем линейных алгебраических уравнений (СЛАУ):

метод Гаусса, метод главного элемента, метод квадратного корня, метод прогонки. Итерационные методы решения СЛАУ (метод простых итераций и метод Зейделя).

Тема 2.2. Проблема собственных значений.

Собственные значения и векторы матриц. Метод Данилевского, метод вращений.

Тема 2.3. Методы решения нелинейных уравнений и систем.

Методы простых итераций, метод Ньютона. Сходимость и скорость сходимости.

Тема 2.4. Аппроксимация и интерполяция функций.

Задача интерполяции. Интерполяционные многочлены Лагранжа и Ньютона. Равномерное и среднеквадратичное приближение. Многочлен наилучшего среднеквадратического приближения. Многочлен наилучшего равномерного приближения. Точки Чебышевского альтернанса. Сплайны и интерполяция сплайнами.

Тема 2.5. Методы численного интегрирования и решения обыкновенных дифференциальных уравнений.

Квадратурные формулы прямоугольников, трапеций, Симпсона, Гаусса, Чебышева. Численное решение задачи Коши для обыкновенных дифференциальных уравнений. Методы Эйлера, Рунге-Кутта, Адамса, Адамса-Милна для решения задач Коши.

Тема 2.6. Уравнения в частных производных.

Основные понятия теории разностных схем. Сходимость, устойчивость разностных схем. Методы сведение задач к дискретным (разностным) аналогам.

Разностные схемы для уравнений эллиптического, параболического и гиперболического типов.

Раздел 3. Организация данных и систем. Теория и практика Тема 3.1. Основные понятия объектно-ориентированного программирования.

Объектно-ориентированное программирование. Инкапсуляция, наследование, полиморфизм. Классы. Конструкторы и деструкторы. Разработка библиотек классов.

Тема 3.2. Архитектура вычислительной системы.

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

Тема 3.3. Принципы организации многоуровневой памяти.

Проблемы организации памяти мультипроцессорных систем. Динамическое распределение памяти. Сегментная и страничная организация памяти.

Виртуальная память. Защита памяти. Алгоритмы управления многоуровневой памятью. Защита по привилегиям в ВС. Передача управления через уровни привилегий. Задачи и процессы. Структуры: список готовности, блоки управления процессами. Операции над процессами, координация и синхронизация процессов. Особенности управления процессами в ВС различной структуры.

Тема 3.4. Модели данных и СУБД.

Машинное представление различных структур данных. Математические модели структур данных. Общие концепции СУБД; модели данных: реляционная, иерархическая, объектно-ориентированная и сетевая. Требования к СУБД.

Языки манипулирования данными для реляционной модели: алгебра реляций Кодда, исчисление на кортежах и доменах; эквивалентность. Язык SQL и его версии. Защита баз данных: целостность, безопасность, администрирование СУБД в сетях.

Тема 3.5. Компьютерные сети.

Структура компьютерных сетей. Основные виды протоколов, которые применяются в сетях. Internet, главные принципы построения и использование.

Сетевые серверы, их классификация и свойства. Программирование для компьютерных сетей. Средства программирования серверов. Технические средства реализации сетей. Защита информации в сетях.

Тема 3.6. Лингвистическое обеспечение.

Языки программирования высокого уровня. Трансляторы. Кросстрансляторы. Компиляторы и интерпретаторы. Лексика, синтаксис и семантика языка программирования. Традиционные технологии программирования.

Структурное программирование. Средства ускоренной разработки программ.

Непроцедурные языки программирования. Параллельные алгоритмы, классификация, особенности, модели и методы оценки эффективности. Лингвистическое обеспечение параллельного программирования.

Тема 3.7. Операционные системы.

Операционная система Windows. Многозадачность в Windows. Взаимодействие процессов. Работа с файлами.

Тема 3.8. Организация взаимодействия программ различного уровня и на разных языках.

Модульное программирование. Сложности, возникающие при разработке многомодульной многоязыковой системы. Надёжность и безопасность программ. Защита программ и данных. Спецификация, верификация, тестирование и отладка программного обеспечения. Характеристики качества.

К разделу 1. Биркгоф Г., Барти Т. Современная прикладная алгебра. Пер. с англ. – 2. Виноградов И. М. Основы теории чисел. – Спб.: Лань. 2009.

3. Катленд Н. Вычислимость. Введение в теорию рекурсивных функций.

4. Колмогоров А. Н., Фомин С. В. Элементы теории функций и функционального анализа. – М.: Физматлит. 2006.

5. Кострикин А. И. Введение в алгебру. – М.: Физматлит. 2001.

6. Кузнецов О. П. Дискретная математика для инженера. – Спб.: Лань.

7. Лидл Р., Нидеррайтер Г. Конечные поля. В двух томах. Перевод с 8. Мальцев А. И. Алгоритмы и рекурсивные функции. – М.: Наука. 1986.

9. Мендельсон Э. Введение в математическую логику. Пер. с англ. – 10. Нефедов В. Н., Осипова В. А. Курс дискретной математики. – М.: Издво МАИ. 1992.

11. Ноден П., Китте К. Алгебраическая алгоритмика. Пер. с франц. – 12. Питерсон У., Уэлдон Э. Коды, исправляющие ошибки. Пер. с англ. – 13. Роджерс X. Теория рекурсивных функций и эффективная вычислимость. Пер. с англ. – М.: Мир. 1972.

14. Успенский В. А. Лекции о вычислимых функциях. – М.: ГИФМЛ. 1960.

15. Яблонский С. В. Введение в дискретную математику. – М.: Высшая К разделу 1. Алексеев В. М., Тихомиров В. М., Фомин С. В. Оптимальное управление. – М.: Наука. 1979.

2. Арушанян О. Б., Залеткин С. Ф. Численное решение обыкновенных дифференциальных уравнений на Фортране. – М.: Изд-во МГУ. 1990.

3. Бахвалов Н. С., Жидков Н. П., Кобельков Г. М. Численные методы. – М.: Бином. Лаборатория знаний. 2011.

4. Крылов В. И., Бобков В. В., Монастырный П. И. Вычислительные методы высшей математики. – Минск: Вышэйшая школа. Т.1. 1972. Т.2.

5. Марчук Г. И. Методы вычислительной математики. – Спб.: Лань. 2009.

6. Понтрягин Л. С., Болтянский В. Г., Гамкрелидзе Р. В., Мищенко Э. Ф.

Математическая теория оптимальных процессов. – М.: Наука. 1976.

7. Рокафеллар Р. Выпуклый анализ. Пер. с англ. – М.: Мир. 1973.

8. Самарский А. А. Теория разностных схем. – М.: Наука. 1977.

9. Самарский А. А., Гулин А. В. Устойчивость разностных схем. – М.:

10.Самарский А. А., Гулин А. В. Численные методы математической физики. – М.: Научный мир. 2003.

11.Самарский А. А., Николаев Е. С. Методы решения сеточных уравнений.

12.Фаддеев Д. К., Фаддеева В. Н. Вычислительные методы линейной алгебры. – Спб.: Лань. 2009.

13.Хайрер Э., Ваннер Г. Решение обыкновенных дифференциальных уравнений. – М.: Мир. 1999.

К разделу 1. Андерсен Р. Доказательство правильности программ. – М.: Мир. 1982.

2. Боуман Дж. С., Эмерсон С. Л., Дарновски М. Практическое руководство по SQL. – М.: Вильямс. 2002.

3. Буч Г. Объектно-ориентированный анализ и проектирование с примерами приложений на C++. – К.: Бином, 1998.

4. Грей П. Логика, алгебра и базы данных. – М.: Машиностроение. 1989.

5. Грис Д. Конструирование компиляторов для цифровых вычислительных машин. – М.: Мир. 1975.

6. Грис Д. Наука программирования. – М.: Мир. 1984.

7. Дейт К. Дж. Введение в системы баз данных. – М.: Вильямс. 2006.

8. Зельковиц М., Шоу А., Гэннон Дж. Принципы разработки программного обеспечения. – М.: Мир. 1982.

9. Йодан Э. Структурное проектирование и конструирование программ. – 10. Крол Э. Все об Internet. – К.: BHV. 1995.

11. Лингер Р., Миллс X., Уатт Б. Теория и практика структурного программирования. – М.: Мир. 1982.

12. Льюис Ф., Розенкранц Д., Стирнз Р. Теоретические основы проектирования компиляторов. – М.: Мир. 1979.

13. Мейер Д. Теория реляционных баз данных. – М.: Мир. 1987.

14. Минаси М., Кристиансен Э., Шепер К. Windows 98. Полное руководство. – Спб.: BHV.1999.

15. Немет Э., Снайдер Г., Сиббасс С, Хейн Т. UNIX. Руководство системного администратора. – Спб.: Питер. 2005.

16. Пратт Т., Зельковиц М. Языки программирования: разработка и реализация. – Спб.: Питер. 2002.

17. Робачевский A. M., Стесик О. Л., Немнюгин С. Операционная система UNIX. – Спб.: BHV-Петербург. 2010.

18. Страуструп Б. Язык программирования C++. – М.: Бином. 2011.

19. Ульман Дж. Основы систем баз данных. – М.: Фин. и стат. 1983.

20. Хант К. Персональные компьютеры в сетях TCP/IP. – Спб.: BHVПетербург. 21. Хендерсон П. Функциональное программирование. Применение и реализация. – М.: Мир. 1983.

22. Хоггер К. Введение в логическое программирование. – М.: Мир. 1988.

23. Янг М. Дж. Visual C++6. Полное руководство, т. 1. – К.: BHV. 1999.