Программа государственного экзамена по направлению (магистерская подготовка) 230100. 68
| Вид материала | Программа |
- Программа государственного экзамена по направлению 230100 «Информатика и вычислительная, 60.5kb.
- Программа междисциплинарного государственного экзамена на степень (квалификацию) «магистр, 286.38kb.
- Программа вступительного экзамена в магистратуру по направлению 540400 Социально-экономическое, 367.11kb.
- Программа вступительного экзамена в магистратуру по направлению 080200. 68 Менеджмент, 222.57kb.
- Программа итогового государственного экзамена по направлению подготовки дипломированного, 253.1kb.
- Образовательный стандарт по направлению 230100. 62 Информатика и вычислительная техника, 328.94kb.
- Программа вступительных испытаний по направлению 050100. 68 Педагогическое образование, 453.79kb.
- Программа дисциплины управленческий учет и бюджетирование для студентов по направлению, 288.86kb.
- Программа дисциплины управленческий учет и бюджетирование для студентов по направлению, 242.7kb.
- Программа вступительного экзамена в магистратуру по направлению 080100. 68 «Экономика»,, 253.14kb.
ПРОГРАММА
ГОСУДАРСТВЕННОГО ЭКЗАМЕНА ПО НАПРАВЛЕНИЮ
(магистерская подготовка)
230100.68 - Информатика и вычислительная техника
Теоретическая информатика
1. Математические основы информатики
1. Зависимые и независимые случайные события и случайные величины и их математическое описание.
- Марковские цепи и их описание. Классификация марковских цепей и их состояний. Предельные вероятности состояний.
- Случайные процессы и их математическое описание. Классификация случайных процессов.
- Гауссовские случайные процессы. Многомерное нормальное распределение.
- Марковские случайные процессы. Дифференциальные уравнения Колмогорова для переходных вероятностей Марковских процессов.
- Пуассоновский случайный процесс с дискретным и непрерывным временем.
- Пуассоновский поток и поток Эрланга.
- Разложение функций в ряд на конечном и бесконечном интервале. Условия сходимости ряда Фурье.
- Непрерывное и дискретное преобразование Фурье.
2. Теория сложности алгоритмов и вычислений
1. Характеристики сложности алгоритмов. Основные классы сложности алгоритмов.
2. Типы архитектур вычислительных систем. Параллельные вычисления.
3. Детерминированные и недетерминированные машины Тьюринга. Тезис Черча.
4. Классы P и NP.
- Сводимость задач. NP-полнота
- Иерархия классов сложности задач. Труднорешаемые задачи. Неразрешимые задачи.
3. Основные структуры информатики и программирования
1. Графы и деревья. Их представление в памяти вычислительной машины.
- Деревья поиска. Случайные и идеально сбалансированные деревья.
- АВЛ-деревья.
- Б-деревья.
- Двоичные Б-деревья.
- Деревья оптимального поиска.
- Хеш-функции и их применение в задачах поиска.
- Задача сортировки и основные алгоритмы сортировки.
- Формальные грамматики и их классификация.
4. Теория информации
- Формальное представление системы передачи данных.
- Классификация источников информации.
- Энтропия и информация. Условная и предельная энтропия.
- Кодирование источников. Средняя длина кодового слова и избыточность.
- Основные побуквенные коды.
- Кодирование целых чисел.
- Арифметическое кодирование.
- Универсальное кодирование. Код Фитингофа. Кодирование длин серий.
- Адаптивное кодирование. Оптимальный универсальный код.
- Словарные методы сжатия информации.
- Статистические методы сжатия информации.
- Преобразование Берроуза-Уилера и его использование.
- Методы обнаружения ошибок при передаче данных.
- Коды, исправляющие ошибки.
5. Основы криптографии
1. Блоковые и потоковые шифры.
2. Односторонние функции.
3. Система Диффи-Хеллмана.
4. Шифры с открытым ключом.
5. Криптографические хеш-функции.
6. Цифровая подпись.
7. Протоколы идентификации.
8. Доказательства с нулевым знанием.
9. Совершенная секретность. Шифр Вернама.
10. Идеальные шифры.
СПИСОК РЕКОМЕНДУЕМОЙ ЛИТЕРАТУРЫ:
1. Математические основы информатики
1. Савельев Л.Я Элементарная теория вероятностей. 2005.
2. Рябко Б.Я. Теория вероятностей и основы теории массового обслуживания: Сборник задач. 2004.
- Гмурман В.Е. Теория вероятностей и математическая статистика. 2003.
- Лазакович Н.В. и др. Курс теории вероятностей. 2003.
- Пугачев В.С. Теория вероятностей и математическая статистика. 2002.
- Володин И.Н. Лекции по теории вероятностей и математической статистике. 2000.
- Феллер В. Введение в теорию вероятностей и ее приложения: Т. 1. 1984.
2. Теория сложности алгоритмов и вычислений
1. Кормен Т. Лейзерсон Ч., Ривест Р. Алгоритмы. Построение и анализ. 2005.
- Ахо А., Ульман Дж., Хопкрофт Дж. Построение и анализ алгоритмов. М., Мир. 1987.
- Гэри М., Джонсон Д. Вычислительные машины и трудно решаемые задачи. М., Мир. 1982.
3. Основные структуры информатики и программирования
- Кормен Т. Лейзерсон Ч., Ривест Р. Алгоритмы. Построение и анализ. 2005.
- Гордеев А.В., Молчанов А.Ю. Системное программное обеспечение. 2002.
- Седжвик Р. Фундаментальные алгоритмы на С++. 2002.
- Вирт Н. Алгоритмы и структуры данных. 1989.
- Ахо А., Ульман Дж. Теория синтаксического анализа, перевода и компиляции. Т.1,2. 1988.
- Ахо А., Ульман Дж., Хопкрофт Дж. Построение и анализ алгоритмов. М., Мир. 1987.
- Кнут Д. Искусство программирования для ЭВМ, сортировка и поиск. 1978.
4. Теория информации
- Рябко Б.Я., Фионов А.Н. Криптографические методы защиты информации: Учебное пособие. 2005.
- Вернер М. Основы кодирования: Учебник. 2004.
- Галлагер Р. Теория информации и надежная связь. 1974.
- Шеннон К. Работы по теории информации и кибернетике. 1963.
5. Основы криптографии
- Рябко Б.Я., Фионов А.Н. Криптографические методы защиты информации: Учебное пособие. 2005.
- Рябко Б.Я., Фионов А.Н. Основы современной криптографии для специалистов в информационных технологиях. 2004.