Информатика и вычислительная техника Теоретическая информатика Математические основы информатики



Дата15.01.2013
Размер36.5 Kb.
ТипПрограмма
ПРОГРАММА

ГОСУДАРСТВЕННОГО ЭКЗАМЕНА ПО НАПРАВЛЕНИЮ
(магистерская подготовка)

230100.68 - Информатика и вычислительная техника

Теоретическая информатика

1. Математические основы информатики

1. Зависимые и независимые случайные события и случайные величины и их математическое описание.

  1. Марковские цепи и их описание. Классификация марковских цепей и их состояний. Предельные вероятности состояний.

  2. Случайные процессы и их математическое описание. Классификация случайных процессов.

  3. Гауссовские случайные процессы. Многомерное нормальное распределение.

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

  5. Пуассоновский случайный процесс с дискретным и непрерывным временем.

  6. Пуассоновский поток и поток Эрланга.

  7. Разложение функций в ряд на конечном и бесконечном интервале. Условия сходимости ряда Фурье.

  8. Непрерывное и дискретное преобразование Фурье.

2. Теория сложности алгоритмов и вычислений

1. Характеристики сложности алгоритмов. Основные классы сложности алгоритмов.

2. Типы архитектур вычислительных систем. Параллельные вычисления.

3. Детерминированные и недетерминированные машины Тьюринга. Тезис Черча.

4. Классы P и NP.

  1. Сводимость задач. NP-полнота

  2. Иерархия классов сложности задач. Труднорешаемые задачи. Неразрешимые задачи.

3. Основные структуры информатики и программирования

1. Графы и деревья. Их представление в памяти вычислительной машины.

  1. Деревья поиска. Случайные и идеально сбалансированные деревья.

  2. АВЛ-деревья.

  3. Б-деревья.

  4. Двоичные Б-деревья.

  5. Деревья оптимального поиска.

  6. Хеш-функции и их применение в задачах поиска.

  7. Задача сортировки и основные алгоритмы сортировки.

  8. Формальные грамматики и их классификация.

4. Теория информации

  1. Формальное представление системы передачи данных.

  2. Классификация источников информации.

  3. Энтропия и информация. Условная и предельная энтропия.

  4. Кодирование источников. Средняя длина кодового слова и избыточность.

  5. Основные побуквенные коды.

  6. Кодирование целых чисел.

  7. Арифметическое кодирование.

  8. Универсальное кодирование. Код Фитингофа. Кодирование длин серий.

  9. Адаптивное кодирование. Оптимальный универсальный код.

  10. Словарные методы сжатия информации.

  11. Статистические методы сжатия информации.

  12. Преобразование Берроуза-Уилера и его использование.


  13. Методы обнаружения ошибок при передаче данных.

  14. Коды, исправляющие ошибки.

5. Основы криптографии

1. Блоковые и потоковые шифры.

2. Односторонние функции.

3. Система Диффи-Хеллмана.

4. Шифры с открытым ключом.

5. Криптографические хеш-функции.

6. Цифровая подпись.

7. Протоколы идентификации.

8. Доказательства с нулевым знанием.

9. Совершенная секретность. Шифр Вернама.

10. Идеальные шифры.
СПИСОК РЕКОМЕНДУЕМОЙ ЛИТЕРАТУРЫ:

1. Математические основы информатики

1. Савельев Л.Я Элементарная теория вероятностей. 2005.

2. Рябко Б.Я. Теория вероятностей и основы теории массового обслуживания: Сборник задач. 2004.

  1. Гмурман В.Е. Теория вероятностей и математическая статистика. 2003.

  2. Лазакович Н.В. и др. Курс теории вероятностей. 2003.

  3. Пугачев В.С. Теория вероятностей и математическая статистика. 2002.

  4. Володин И.Н. Лекции по теории вероятностей и математической статистике. 2000.

  5. Феллер В. Введение в теорию вероятностей и ее приложения: Т. 1. 1984.

2. Теория сложности алгоритмов и вычислений

1. Кормен Т. Лейзерсон Ч., Ривест Р. Алгоритмы. Построение и анализ. 2005.

  1. Ахо А., Ульман Дж., Хопкрофт Дж. Построение и анализ алгоритмов. М., Мир. 1987.

  2. Гэри М., Джонсон Д. Вычислительные машины и трудно решаемые задачи. М., Мир. 1982.

3. Основные структуры информатики и программирования

  1. Кормен Т. Лейзерсон Ч., Ривест Р. Алгоритмы. Построение и анализ. 2005.

  2. Гордеев А.В., Молчанов А.Ю. Системное программное обеспечение. 2002.

  3. Седжвик Р. Фундаментальные алгоритмы на С++. 2002.

  4. Вирт Н. Алгоритмы и структуры данных. 1989.

  5. Ахо А., Ульман Дж. Теория синтаксического анализа, перевода и компиляции. Т.1,2. 1988.

  6. Ахо А., Ульман Дж., Хопкрофт Дж. Построение и анализ алгоритмов. М., Мир. 1987.

  7. Кнут Д. Искусство программирования для ЭВМ, сортировка и поиск. 1978.

4. Теория информации

  1. Рябко Б.Я., Фионов А.Н. Криптографические методы защиты информации: Учебное пособие. 2005.

  2. Вернер М. Основы кодирования: Учебник. 2004.

  3. Галлагер Р. Теория информации и надежная связь. 1974.

  4. Шеннон К. Работы по теории информации и кибернетике. 1963.

5. Основы криптографии

  1. Рябко Б.Я., Фионов А.Н. Криптографические методы защиты информации: Учебное пособие. 2005.

  2. Рябко Б.Я., Фионов А.Н. Основы современной криптографии для специалистов в информационных технологиях. 2004.







Похожие:

Информатика и вычислительная техника Теоретическая информатика Математические основы информатики iconВ. Ф. Пономарев математическая логика
Утверждено Ученым советом университета в качестве учебного пособия для студентов направления 552800 – Информатика и вычислительная...
Информатика и вычислительная техника Теоретическая информатика Математические основы информатики iconВ. Ф. Пономарев математическая логика
Утверждено Ученым советом университета в качестве учебного пособия для студентов направления 552800 – Информатика и вычислительная...
Информатика и вычислительная техника Теоретическая информатика Математические основы информатики iconРабочая программа дисциплина Дискретная математика Направление 230100 Информатика и вычислительная техника
Информатика и вычислительная техника, специальности 230102 – Автоматизированные системы обработки информации и управления, утвержденным...
Информатика и вычислительная техника Теоретическая информатика Математические основы информатики iconРабочая программа дисциплины математическая логика и теория алгоритмов
Для подготовки бакалавров по направлению 552800 – “Информатика и вычислительная техника” и дипломированных специалистов по направлению...
Информатика и вычислительная техника Теоретическая информатика Математические основы информатики iconЕ. Н. Матюхина организация ЭВМ и систем учебное пособие
Учебное пособие предназначено для студентов направления 552800 «Информатика и вычислительная техника» инаправления 654600 «Информатика...
Информатика и вычислительная техника Теоретическая информатика Математические основы информатики iconОбразовательная программа по направлению 230100 " Информатика и вычислительная техника" специальность 230101, «Вычислительные машины, комплексы, системы и сети»
Рабочая программа составлена на основании Государственного образовательного стандарта высшего профессионального образования по направлению...
Информатика и вычислительная техника Теоретическая информатика Математические основы информатики iconКнига адресована студентам старших курсов технических специальностей, соискателям степени магистра по направлению 552800 «Информатика и вычислительная техника»
Информатика и вт", 230105. 65 "Програм обеспеч. Вт и автоматизированных систем " Современные проблемы информатики и вычислительной...
Информатика и вычислительная техника Теоретическая информатика Математические основы информатики iconТеоретическая информатика Глава Теоретические основы информатики
Примерно то же с информатикой: можно изучить несколько программ и даже освоить некоторое ремесло, но это отнюдь не вся информатика,...
Информатика и вычислительная техника Теоретическая информатика Математические основы информатики iconРабочая программа дисциплины «Информатика» для направления 552800 «Информатика и вычислительная техника»
Целью преподавания дисциплины «Информатика» в 3-м семестре является получение базового уровня компьютерной грамотности, знаний и...
Информатика и вычислительная техника Теоретическая информатика Математические основы информатики iconПрактикум по дисциплине «информатика» для студентов направлений 230100. 62 «Информатика и вычислительная техника»
Лабораторная работа Команды работы с дисками, файлами и каталогами ос ms dos 9
Разместите кнопку на своём сайте:
ru.convdocs.org


База данных защищена авторским правом ©ru.convdocs.org 2016
обратиться к администрации
ru.convdocs.org