Министерство образования Республики Беларусь
Учреждение образования
«Белорусский государственный университет
информатики и радиоэлектроники»
ПРОГРАММА
вступительного экзамена в магистратуру по специальности
1-31 80 09 Прикладная математика и информатика
Минск, 2011
Программа составлена на основании типового учебного плана по специальности 1-31 03 04 Информатика.
СОСТАВИТЕЛИ:
Минченко Леонид Иванович - доктор физико-математических наук, профессор, заведующий кафедрой информатики БГУИР;Волосевич Алексей Александрович - кандидат физико-математических наук, доцент, доцент кафедры информатики БГУИР;
Сиротко Сергей Иванович - кандидат физико-математических наук, доцент, доцент кафедры информатики БГУИР
РЕКОМЕНДОВАНА К УТВЕРЖДЕНИЮ:
Кафедрой информатики учреждения образования «Белорусский государственный университет информатики и радиоэлектроники»(протокол № 17 от «24» апреля 2011 г.) Заведующий кафедрой Минченко Л. И.
Пояснительная записка Целью экзамена по специальности 1-31 80 09 Прикладная математика и информатика является проверка знаний основ математики и средств современного программного обеспечения в объёме, необходимом для успешной учёбы в магистратуре и проведения исследовательской работы в рамках специальности под руководством научного руководителя.
В основу программы экзамена положены следующие дисциплины:
1. Математический анализ.
2. Геометрия и алгебра.
3. Дискретная математика и математическая логика.
4. Методы численного анализа.
5. Прикладная алгебра и элементы теории информации.
6. Методы оптимизации.
7. Конструирование программ и языки программирования.
8. Инструменты и средства программирования.
9. Объектно-ориентированное программирование.
10. Компьютерные сети.
11. Теория алгоритмов.
12. Архитектура вычислительных систем.
13. Системное программирование.
14. Методы трансляции.
15. Операционные системы и среды.
16. Модели данных и СУБД.
Раздел 1. Математические основы. Теория алгоритмов.
Алгебра логики. Булевы функции. Базис булевых функций. Нормальные формы. Исчисление высказываний.
Основы теории графов. Операции на графах. Свойства графов. Отношения на множествах и графы.
Интуитивные свойства алгоритмов. Формальные уточнения: машины Тьюринга, регистровые машины, частично вычислимые (частично рекурсивные) функции. Разрешимые и неразрешимые массовые проблемы (задачи).
Классификация массовых задач по сложности. Основные классы сложности и соотношения между ними. Сложность по Колмогорову.
Теория групп и её приложения. Кольца. Поля. Основные теоретикочисловые алгоритмы: расширенный алгоритм Евклида, алгоритм быстрого возведения в степень. Модулярная арифметика.
Классификация алгоритмов шифрования. Блочные алгоритмы шифрования. Шифрование с открытым ключом. Функция хеширования и алгоритмы её вычисления. Электронная цифровая подпись, алгоритмы генерации ЭЦП. Алгоритм Диффи-Хеллмана.
Задачи линейного, выпуклого и нелинейного программирования. Необходимые условия экстремума в конечномерных пространствах. Правило множителей Лагранжа.
Раздел 2. Численные методы.
Классификация погрешностей. Численные методы решения алгебраических и трансцендентных уравнений: метод секущих, метод касательных, метод парабол, метод Лобачевского. Сходимость и скорость сходимости методов.
Аппроксимация функций. Интерполяционные многочлены Лагранжа и Ньютона. Равномерное и среднеквадратичное приближение. Многочлен наилучшего среднеквадратического приближения. Метод наименьших квадратов. Интерполяция сплайнами.
Методы численного дифференцирования и интегрирования. Квадратурные формулы прямоугольников, трапеций, Симпсона.
Задачи линейной алгебры. Методы решения систем линейных алгебраических уравнений (СЛАУ): метод Гаусса, метод главного элемента, метод квадратного корня, метод прогонки. Итерационные методы решения СЛАУ (метод простых итераций и метод Зейделя). Метод Гаусса вычисление обратной матрицы и определителя. Методы решения полной проблемы собственных значений. Метод решения частичной проблемы собственных значений.
Численное решение задачи Коши для обыкновенных дифференциальных уравнений. Методы Эйлера, Рунге-Кутта, Адамса, Милна для решения задач Коши.
Уравнения в частных производных. Основные понятия теории разностных схем. Методы сведение задач к дискретным (разностным) аналогам. Разностные схемы для уравнений эллиптического, параболического и гиперболического типов.
Раздел 3. Организация данных и систем. Теория и практика программирования.
Машинное представление различных структур данных. Математические модели структур данных. Четыре модели данных: реляционная, иерархическая, объектно-ориентированная и сетевая.
Объектно-ориентированное программирование. Основные понятия объектно-ориентированного программирования. Классы. Инкапсуляция, наследование, полиморфизм. Конструкторы и деструкторы.
Общие концепции СУБД. Требования к СУБД. Защита баз данных: целостность, безопасность, администрирование баз данных.
Языки манипулирования данными для реляционной модели: алгебра реляций Кодда, исчисление на кортежах и доменах. Язык SQL и его версии.
Типы и компоненты структур вычислительных систем (ВС). Понятие архитектуры вычислительной системы. Вычислительные и логические возможности, аппаратные средства, программное обеспечение. Элементы архитектуры традиционных ВС. Структура и формат команд. Способы адресации. Особенности адресации и системы команд современных ВС.
Принципы организации многоуровневой памяти. Проблемы организации памяти мультипроцессорных систем. Динамическое распределение памяти.
Сегментная и страничная организация памяти. Виртуальная память. Защита памяти. Алгоритмы управления многоуровневой памятью.
Задачи и процессы. Список готовности, блоки управления процессами.
Операции над процессами, координация и синхронизация процессов. Особенности управления процессами в вычислительных системах различной структуры.
Компьютерные сети. Структура компьютерных сетей. Основные виды протоколов, применяемых в сетях. Internet, главные принципы построения и использование. Программирование для компьютерных сетей. Средства программирования серверов. Технические средства реализации сетей. Защита информации в сетях.
Языки программирования высокого уровня. Традиционные технологии программирования. Структурное программирование. Средства ускоренной разработки программ.
Непроцедурные языки программирования. Параллельные алгоритмы, классификация, особенности, модели и методы оценки эффективности. Лингвистическое обеспечение параллельного программирования.
Операционная система Windows. Многозадачность в Windows. Взаимодействие процессов. Работа с файлами.
Трансляторы. Кросс-трансляторы. Компиляторы и интерпретаторы. Лексика, синтаксис и семантика языка программирования.
Надёжность и безопасность программ. Защита программ и данных. Спецификация, верификация, тестирование и отладка программного обеспечения.
Характеристики качества.
Организация взаимодействия программ различного уровня и на разных языках. Модульное программирование. Сложности, возникающие при разработке многомодульной многоязыковой системы.
К разделу 1. Алексеев В. М., Тихомиров В. М., Фомин С. В. Оптимальное управление. – М.: Наука. 1979.
2. Биркгоф Г., Барти Т. Современная прикладная алгебра. Пер. с англ. – 3. Виноградов И. М. Основы теории чисел. – Спб.: Лань. 2009.
4. Катленд Н. Вычислимость. Введение в теорию рекурсивных функций.
Пер. с англ.– М.: Мир. 1983.
5. Кларк Ф. Оптимизация и негладкий анализ. Пер. с англ. – М.: Наука.
6. Колмогоров А. Н., Фомин С. В. Элементы теории функций и функционального анализа. – М.: Физматлит. 2006.
7. Кострикин А. И. Введение в алгебру. – М.: Физматлит. 2001.
8. Кузнецов О. П. Дискретная математика для инженера. – Спб.: Лань.
9. Лидл Р., Нидеррайтер Г. Конечные поля. В двух томах. Перевод с 10. Мальцев А. И. Алгоритмы и рекурсивные функции. – М.: Наука. 1986.
11. Мендельсон Э. Введение в математическую логику. Пер. с англ. – 12. Нефедов В. Н., Осипова В. А. Курс дискретной математики. – М.: Издво МАИ. 1992.
13. Ноден П., Китте К. Алгебраическая алгоритмика. Пер. с франц. – 14. Питерсон У., Уэлдон Э. Коды, исправляющие ошибки. Пер. с англ. – 15. Понтрягин Л. С., Болтянский В. Г., Гамкрелидзе Р. В., Мищенко Э. Ф.
Математическая теория оптимальных процессов. – М.: Наука. 1976.
16. Роджерс X. Теория рекурсивных функций и эффективная вычислимость. Пер. с англ. – М.: Мир. 1972.
17. Рокафеллар Р. Выпуклый анализ. Пер. с англ. – М.: Мир. 1973.
18. Успенский В. А. Лекции о вычислимых функциях. – М.: ГИФМЛ. 1960.
19. Яблонский С. В. Введение в дискретную математику. – М.: Высшая К разделу 1. Арушанян О. Б., Залеткин С. Ф. Численное решение обыкновенных дифференциальных уравнений на Фортране. – М.: Изд-во МГУ. 1990.
2. Бахвалов Н. С., Жидков Н. П., Кобельков Г. М. Численные методы. – М.: Бином. Лаборатория знаний. 2011.
3. Воеводин В. В. Численные методы алгебры. Теория и алгорифмы. – М.:
4. Крылов В. И., Бобков В. В., Монастырный П. И. Вычислительные методы высшей математики. – Минск: Вышэйшая школа. Т.1. 1972. Т.2.
5. Марчук Г. И. Методы вычислительной математики. – Спб.: Лань. 2009.
6. Самарский А. А. Теория разностных схем. – М.: Наука. 1977.
7. Самарский А. А., Гулин А. В. Устойчивость разностных схем. – М.:
8. Самарский А. А., Гулин А. В. Численные методы математической физики. – М.: Научный мир. 2003.
9. Самарский А. А., Николаев Е. С. Методы решения сеточных уравнений. – М.: Наука. 1978.
10. Фаддеев Д. К., Фаддеева В. Н. Вычислительные методы линейной алгебры. – Спб.: Лань. 2009.
11. Хайрер Э., Ваннер Г. Решение обыкновенных дифференциальных уравнений. – М.: Мир. 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.