Учреждение образования «Белорусский государственный университет

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


УТВЕРЖДАЮ

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

_______________ А.А.Хмыль

“ ______ ”____________2007г
ПРОГРАММА

вступительного экзамена в магистратуру

по специальности

1-31 80 09 «Прикладная математика и информатика»

Минск, 2007г

Программу составили:
Минченко Л.И. д.ф.-м.н., профессор, зав. каф. информат. БГУИР

Сиротко С.И. к. ф.-м.н., доцент кафедры информатики БГУИР

Тараканов А.Н ассистент кафедры информатики БГУИР

Программа рассмотрена на заседании кафедры информатики БГУИР

(протокол от " " 2007 г. № )
Зав. кафедрой Минченко Л.И.

Целью экзамена по специальности 1-31 80 09 является проверка знаний основ математики и средств современного программного обеспечения в объеме необходимом для успешной учебы в магистратуре и проведения исследовательской работы в рамках специальности под руководством научного руководителя.

В основу программы положены вузовские дисциплины: «Моделирование сложных систем», «Геометрия и алгебра», «Основы численного анализа», «Дискретная математика», «Методы оптимизации», «Защита информации», «Конструирование программ и языки программирования», «Объектно-ориентированное программирование», «Вычислительные системы и сети», «Системное программирование», «Операционные системы и среды», «Объектно-ориентированное программирование», «Системы управления базами данных», «Методы и технология программирования», «Теория алгоритмов и методы трансляции».

1. 
   МАТЕМАТИЧЕСКИЕ ОСНОВЫ. ТЕОРИЯ АЛГОРИТМОВ.
   

Алгебра логики. Булевы функции. Базис булевых функций. Основы теории графов. Графы и сети. Операции на графах. Отношения на множествах и графы. Исчисление высказываний. Нормальные формы.

Интуитивные свойства алгоритмов. Формальные уточнения: частично рекурсивные функции, функции, которые вычисляются на машинах с неограниченными регистрами, машины Тьюринга и нормальные алгоритмы Маркова.

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

Примитивно рекурсивные, рекурсивные, общерекурсивные и частично рекурсивные функции. Рекурсивные и рекурсивно пересчитанные предикаты. Алгоритмические проблемы: разрешимые, неразрешимые и частично разрешимые.

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

Задачи линейного, выпуклого и нелинейного программирования. Необходимые условия экстремума в конечномерных пространствах. Правило множителей Лагранжа.

ЛИТЕРАТУРА

2. Яблонский СВ. Введение в дискретную математику. - М.: Наука. 1986.

3. Колмогоров А.Н., Фомин СВ. Элементы теории функций и функционального анализа. - Г.: Наука. 1989.

4. Рокафеллар Р.Т. Выпуклый анализ. - М.: Мир. 1973.

5. Кларк Ф. Оптимизация и негладкий анализ. - М.: Наука. 1988.

6. Понтрягин Л.С., Болтянский В.Г., Гамкрелидзе Р.В., Мищенко Э.Ф. Математическая теория оптимальных процессов. - М.: Физматгиз. 1961

7. Алексеев В.М., Тихомиров В.М., Фомин СВ. Оптимальное управление. - М.: Наука. 1979.

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

9. Мальцев А.И. Алгоритмы и рекурсивные функции. - М.: Наука. 1965.

10. Роджерс X. Теория рекурсивных функций и эффективная вычислимость.-М.: Мир.1972.

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

12. Кузнецов О.П., Адельсон-Вельский Г.М. Дискретная математика для инженера. Изд-во "Энергия", М., 1980.

13. Р.Лидл, Г.Нидеррайтер. Конечные поля. В двух томах. Перевод с англ. М.,"Мир",1988.

14. В.Н.Нефедов, В.А.Осипова. Курс дискретной математики. М., Изд-во МАИ, 1992. Кострикин А.И. Введение в алгебру. М.: Наука, 1977.

15. Биркгоф Г., Барти Т. Современная прикладная алгебра. Пер. с англ., М.: Мир, 1976.

16. Виноградов И. М. Основы теории чисел. М.: Наука, 1981.

17. Питерсон У., Уэлдон Э. Коды, исправляющие ошибки. Пер. с англ., М.: Мир, 1976.

18. Ноден П., Китте К. Алгебраическая алгоритмика. Пер. с англ., М.: Мир, 1996.

2. ЧИСЛЕННЫЕ МЕТОДЫ
Классификация погрешностей. Численные методы решения алгебраических и трансцендентных уравнений: методы секущих, касательных, парабол, Лобачевского. Сходимость и скорость сходимости методов, сравнение методов.

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

Методы численного дифференцирования и интегрирования. Квадратурные формулы прямоугольников, трапеций, Симпсона.

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

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

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

ЛИТЕРАТУРА

1. 
   Арушанян О.Б., Залеткин С.Ф. Численное решение обыкновенных дифференциальных уравнений на Фортране. - М.: Изд-во Моск. ун-та. 1990.
   
2. 
   Бахвалов Н.С. Численные методы. - М.: Наука. 1975.
   
3. 
   Воеводин В.В. Численные методы алгебры: теория и алгоритмы. - М.: Наука. 1966.
   
4. 
   Крылов В.И., Бобков В.В., Монастырный П.И. Вычислительные методы высшей математики. - Минск: Вышэйшая школа. Т.1. 1972. Т.2. 1975.
   
5. 
   Марчук Г.И. Методы вычислительной математики. - М.: Наука. 1980.
   
6. 
   Ортега Дж., Рейболдт. Итерационные метод решения нелинейных систем уравнений со многими неизвестными. - М.: Мир. 1975.
   
7. 
   Самарский А.А. Теория разностных схем. - М.: Наука. 1983.
   
8. 
   Самарский А.А., Андреев В.В. Разностные схемы для эллиптических уравнений. - М.: Наука. 1976.
   
9. 
   Самарский А.А., Гулин А.В. Устойчивость разностных схем. - М.: Наука. 1978.
   
10. 
    Самарский А.А., Гулин А.В. Численные методы. - М.: Наука. 1989.
    
11. 
    Самарский А.А., Николаев Е.С. Методы решения сеточных уравнений. - М.: Наука. 1978.
    
12. 
    Фадеев Д.К., Фадеева В.Н. Вычислительные методы линейной алгебры. - М.: Физматгизиздат. 1963.
    
13. 
    Хайрег Э., Нерсетт С., Ваннер Г. Решение обыкновенных дифференциальных уравнений. - М.: Мир. 1990.
    

3. 
   ОРГАНИЗАЦИЯ ДАННЫХ И СИСТЕМ. ТЕОРИЯ И ПРАКТИКА ПРОГРАММИРОВАНИЯ
   

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

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

Защита баз данных: целостность, безопасность, администрирование СУБД в сетях. Объектно-ориентированное программирование. Основные понятия объектно-ориентированного программирования. Инкапсуляция, наследование, полиморфизм. Классы. Конструкторы и деструкторы. Разработка библиотек классов.

Типы и компоненты структур вычислительных систем (ВС).

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

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

Защита по привилегиям в ВС. Передача управления через уровни привилегий.

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

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

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

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

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

Трансляторы. Кросс-трансляторы. Компиляторы и интерпретаторы. Лексика, синтаксис и семантика языка программирования.

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

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

ЛИТЕРАТУРА
1. Боуман Дж., Эмерсон С, Дарновели М. Практическое руководство по SQL. -К.: Диалектика. 1997.

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

3. Дейт К. Введение у системы баз данных. - К.: Диалектика. 1998.

4. Дейт К. Руководство по реляционной СУБД DB-2. - Г.: Фин. и стат. 1988.

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

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

7. Архитектура, протоколы и тестирование открытых информационных сетей. Толковый словарь. - М.: Фин. и стат. 1990.

8. Крол Э. Все об INTERNET.- К.: BVH. 1999.

9. Локальные сеты NetWare. - Рига: О.О.О. Бис. 1991.

10. Хант К. Персональные компьютеры в сетях TCP/IP. - К.: BVH. 1999.

11. Локальные сети NetWare. - Рига: О.О.О. Бис. 1991.;

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

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

14. Грис Д. Наука программирования. - М.: Мир. 1994.

15. Йодан Э. Структурное проектирование и конструирование программ.-М.: Мир. 1979.

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

17. Логическое программирование. Сб. статей. - М.: Мир. 1988.

18. Математическая логика в программировании. Сб. статей. - М.: Мир. 1990.

19. Минаси М.,Кристиансен Э.,Шепер К. Windows 98.Полное руководство.-К.:BVH.1999.

20. Редько В.Н., Басараб И.А. Базы данных и информационные системы.-М.:Знание.1986.

21. Страуструп Б. Язык программирования C++.- К.: Бином, Спб. 1998

22. Хендерсон П. Функциональное программирование. Применение и реализация. - М.: Мир. 1983.

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

24. Янг Майкл Дж. Visual C++6. Полное руководство, т. 1. - К.: BHV. Ирина. 1999.

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

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

27. Пратт Т. Языки программирования: разработка и реализация. - М.: Мир. 1979.

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

29. Архитектуры и среды для разработки приложений.- К.: Крещатик, 1992.

30. Робачевский A.M. Операционная система UNIX.-Cn6,:BNV-Cn6, 1997.