Программа вступительного экзамена в магистратуру по направлению 552800 (230100. 68) «информатика и вычислительная техника» Общие указания icon

Программа вступительного экзамена в магистратуру по направлению 552800 (230100. 68) «информатика и вычислительная техника» Общие указания



Смотрите также:
Программа вступительного экзамена в магистратуру по направлению подготовки 230100...
Программа междисциплинарного вступительного экзамена в магистратуру по направлению 230100...
Программа междисциплинарного экзамена для поступающих в магистратуру 230100 «Информатика и...
Образовательный стандарт по направлению 552800 «Информатика и вычислительная техника» (код оксо...
Образовательный стандарт по направлению 552800 Информатика и вычислительная техника (код оксо...
Образовательный стандарт по направлению 552800 Информатика и вычислительная техника (код оксо...
Программа вступительного междисциплинарного экзамена в магистратуру тки по направлению 230100...
Образовательный стандарт по направлению 552800 Информатика и вычислительная техника (код оксо...
Программа вступительного экзамена в магистратуру по направлению 230100...
Программа вступительного экзамена в магистратуру по направлению 230100 «Информатика и...
Образовательный стандарт по специальности 552800 Информатика и вычислительная техника (код оксо...
Рабочая учебная программа по дисциплине «Информатика» Направление №230100 «Информатика и...



скачать
Новосибирский государственный университет


Факультет информационных технологий


ПРОГРАММА

ВСТУПИТЕЛЬНОГО ЭКЗАМЕНА В МАГИСТРАТУРУ

ПО НАПРАВЛЕНИЮ 552800 (230100.68) «ИНФОРМАТИКА И ВЫЧИСЛИТЕЛЬНАЯ ТЕХНИКА»


Общие указания


Программа вступительного экзамена состоит из трех разделов – информатика, математика, дополнительные вопросы по специализации (в зависимости от выбранной магистерской программы). Каждый раздел содержит перечень основных вопросов, которыми должен владеть поступающий в магистратуру. В конце каждого раздела приведен список рекомендуемой литературы. Экзаменуемый получает по одному вопросу из каждого раздела за сутки до экзамена. На экзамене могут быть заданы дополнительные вопросы. Пользоваться справочными материалами на экзамене не разрешается. Ответы на вопросы из каждого раздела оцениваются отдельно. Если по одному из разделов получена неудовлетворительная оценка, то итоговая оценка за экзамен не может быть положительной.


^ I. ИНФОРМАТИКА


Общие вопросы информатики и вычислительной техники

  1. Понятие архитектуры вычислительных систем (ВС). Классификация ВС. Принципы организации CISC и RISC архитектур.

  2. Многопроцессорные системы. Симметричная и асимметричная многопроцессорность. Методы организации памяти и обработки информации в таких системах.

  3. Методы организации сетей ЭВМ. Основные принципы их функционирования. Классификация сетей по масштабу и топологии. Понятие сетевого протокола. Семиуровневая модель OSI/ISO. Способы маршрутизации сообщений в сетях ЭВМ. Сетевая архитектура TCP/IP: основные принципы организации и функционирования.

^ Операционные системы

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

  2. Стратегии управления оперативной памятью. Виртуальная память. Статическая и динамическая сборка.

  3. Распределение и использование ресурсов вычислительной системы и управление ими. Основные подходы и алгоритмы планирования. Системы реального и разделенного времени.

  4. Взаимодействие процессов. Разделяемая память, средства синхронизации. Очереди сообщений и другие средства обмена данными.

  5. Управление доступом к данным. Файловые системы (основные типы, характеристики).

^ Системы программирования (СП)

  1. Языки программирования. Концепции процедурно-ориентированного, объектно-ориентированного, логического и функционального программирования. Раннее (статическое) и позднее (динамическое) связывание, статическая и динамическая типизация.

  2. Понятие о методах трансляции. Лексический, синтаксический, семантический анализ. Основные алгоритмы генерации объектного кода. Машинно-ориентированные языки (ассемблеры), области применения, мнемоники, метки (символы). Макросредства, макровызовы, языки макроопределений, условная макрогенерация, принципы реализации. Системы программирования, типовые компоненты СП: языки, трансляторы, редакторы связей, отладчики, текстовые редакторы.

  3. Принципы модульного, компонентного, объектно-ориентированного проектирования, шаблоны проектирования. Моделирование программных систем, язык UML. Современные подходы к автоматическому синтезу программ.

  4. Современные методы и технологии построения распределённых программных систем (J2EE, .NET, веб-службы т.д.).

Методы хранения, организация и доступ к данным

  1. Концепция типа и моделей данных. Абстрактные типы данных. Объекты (основные свойства и отличительные черты).

  2. Основные структуры данных, алгоритмы обработки, поиска и сжатия данных.

  3. Реляционная модель. Реляционная алгебра. Нормальные формы отношений.

  4. Структуры физического уровня баз данных. Методы индексирования.

  5. Компоненты систем управления базами данных. Целостность данных. Транзакции.

  6. Архитектура систем баз данных. Независимость, целостность и неизбыточное хранение данных.

  7. Язык SQL. Средства описания данных, определения ограничений целостности.

  8. Язык SQL. Средства манипулирования данными.

  9. Язык XML. Структурная модель документа (DTD). Адресация содержания XML-документов согласно спецификации Xlink/Xpointer/XPath.


Л И Т Е Р А Т У Р А

  1. Таненбаум Э. Архитектура компьютера. – СПб: Питер, 2006.

  2. Таненбаум Э. Компьютерные сети. – СПб: Питер, 2007.

  3. Таненбаум Э. Современные операционные системы. - СПб: Питер, 2007.

  4. Иртегов Д. Введение в операционные системы. – СПб: БХВ-Петербург, 2008.

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

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

  7. Воеводин В.В. Математические модели и методы в параллельных процессах. - М.: Наука, 1986.

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

  9. Буч Г. Объектно-ориентированный анализ и проектирование с примерами приложений на C++. – 2-е изд.- М.: Бином, 2000.

  10. Буч Г., Рамбо Дж., Якобсон А. Язык UML. Руководство пользователя. – М.: ДМК, 2000.

  11. Гамма Э., Хелм Р., Джонсон Р., Влиссидес Дж. Приемы объектно-ориентированного проектирования. Паттерны проектирования. - СПб: Питер, 2001.

  12. Роберт С. Мартин. Быстрая разработка программ: принципы, примеры, практика. – М.: Издательский дом «Вильямс», 2004.

  13. Г. Гарсиа-Молина, Дж.Д. Ульман, Д. Уидом . Системы баз данных. Полный курс [Пер. с англ.] — М.; СПб.; Киев : Вильямс, 2003 .— 1083 с.

  14. Дейт К. Дж. Введение в системы баз данных. - Москва-Санкт-Петербург-Киев: Изд. дом “Вильямс”, 2005.

  15. Грабер М. SQL. - M.: Лори, 1999.

  16. Даконта М., Саганич А. XML и Java 2. – СПб: Питер, 2001.

  17. Ахо А., Сети Р., Ульман Дж. Компиляторы: принципы, технологии и инструменты. - М.: Издательский дом ''Вильямc'', 2001.


^ II. МАТЕМАТИКА


Математический анализ

  1. Предел последовательности. Принцип Больцано-Вейерштрасса. Верхний и нижний пределы.

  2. Предел функции. Непрерывные функции. Основные теоремы о непрерывных функциях.

  3. Производная и дифференциал. Свойства дифференцируемых функций (теоремы Ролля, Лагранжа, Коши, правила Лопиталя, формула Тейлора). Неявные функции. Экстремумы. Условные экстремумы.

  4. Первообразная и неопределенный интеграл. Интеграл Римана. Повторные интегралы. Замена переменных. Криволинейные и поверхностные интегралы. Формулы Грина, Гаусса-Остроградского, Стокса.

  5. Числовые и функциональные ряды. Равномерная сходимость. Ряды Фурье. Представление функций рядами Фурье.

Основы теории функций комплексной переменной

  1. Степенные и функциональные ряды на комплексной плоскости. Первая теорема Абеля. Радиус сходимости. Формула Коши – Адамара.

  2. Комплексное дифференцирование. Условия Коши - Римана.

  3. Комплексное интегрирование. Теорема Коши. Формула Коши. Интеграл типа Коши. Принцип максимума модуля.

  4. Теоремы Тейлора и Лорана. Нули аналитической функции. Внутренняя теорема единственности. Изолированные особые точки. Вычеты. Вычисление несобственных интегралов с помощью теории вычетов.

  5. Преобразования Фурье и Лапласа.

Обыкновенные дифференциальные уравнения

  1. Задача Коши. Теоремы Пеано и Пикара существования решения задачи Коши. Лемма Гронуолла и единственность решений.

  2. Линейные уравнения и линейные системы с переменными коэффициентами. Фундаментальная система решений. Общее решение. Метод вариации постоянных. Уравнения и системы уравнений с постоянными коэффициентами.

  3. Устойчивость и неустойчивость решений. Теоремы Ляпунова и Четаева. Устойчивость по первому приближению. *

Элементы вычислительной математики

  1. Итерационные методы решения линейных алгебраических систем большой размерности.

  2. Численные методы решения обыкновенных дифференциальных уравнений.

  3. Численное интегрирование.

  4. Разностные схемы. Устойчивость разностных схем.

  5. Дискретное преобразование Фурье.


Примечание - Звездочкой * обозначены вопросы, которые не предполагают доказательств.


Л И Т Е Р А Т У Р А

  1. Кудрявцев Л.Д. Математический анализ. - М.: Высшая школа, 1973. - Т. 1, 2.

  2. Решетняк Ю.Г. Курс математического анализа. – Новосибирск: Институт математики, 1999. - Ч. I, 2000 - Ч. II.

  3. Бицадзе А.В. Основы теории аналитических функций комплексного переменного. - М.: Наука, 1972.

  4. Лаврентьев М.А., Шабат Б.В. Методы теории функций комплексного переменного. - М.: Наука, 1987.

  5. Петровский И.Г. Лекции по теории обыкновенных дифференциальных уравнений. - М.: Высшая школа, 1970.

  6. Понтрягин Л.С. Обыкновенные дифференциальные уравнения. - М.: Наука, 1982.

  7. Самарский А.А., Гулин А.В. Численные методы. - М.: Наука, 1989.

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

  9. Бахвалов Н.С. Численные методы. - М.: Наука, 1975.


Математическая логика и теория алгоритмов

  1. Логика высказываний. Основные тождества логики высказываний. Приведение формулы к СДНФ и СКНФ. Секвенциальное исчисление высказываний, теорема о замене. Теорема о существовании КНФ, теорема о полноте исчисления секвенций.

  2. Теория множеств. Основные тождества теории множеств. Теорема об эквивалентностях и разбиениях. Теорема Кантора-Бернштейна, теорема Кантора. Счётность множества слов в счётном алфавите. Несчётность множества вещественных чисел. Равномощность множества вещественных чисел и множества всех подмножеств натуральных чисел. Основные свойства булевых алгебр. Теорема Стоуна для конечных булевых алгебр.

  3. Логика предикатов и теория моделей. Семантическая эквивалентность формул, основные тождества логики предикатов. Секвенциальное исчисление предикатов, теорема о корректности. Теорема о замене. Приведение формулы к предваренной нормальной форме. Теорема о существовании модели. Теорема Гёделя о полноте и теорема компактности Мальцева. Теоремы Ливенгейма-Скулема. Аксиоматизируемые классы, конечно аксиоматизируемые классы. Характеризация классов, замкнутых относительно подмоделей и расширений.

  4. Теория вычислимости. Примитивно-рекурсивные, общерекурсивные и частично-рекурсивные функции. Машины Тьюринга, теорема о правильной вычислимости частично-рекурсивных функций. Кодировка машин Тьюринга. Теорема о нормальной форме Клини. Эквивалентность классов вычислимых функций. Универсальные рекурсивные функции. Клиниевская нумерация, теорема о неподвижной точке. Теорема Райса. Теорема об эквивалентных определениях рекурсивно-перечислимых множеств. Теорема Поста. Теорема о проекции, теорема о графике. Представимость рекурсивных функций в арифметике Пеано. Теорема Гёделя о неполноте. Теоремы о неразрешимости логики предикатов и арифметики. Существование рекурсивно-перечислимого, но не рекурсивного множества, неразрешимость проблемы остановки программы.


Л И Т Е Р А Т У Р А

  1. Кейслер Г., Чэн Ч.Ч. Теория моделей. - М.: Мир, 1977.

  2. Ершов Ю.Л., Палютин Е.А. Математическая логика. - М.: Наука, 1987.

  3. Гончаров С.С. Счетные булевы алгебры и разрешимость. - Новосибирск, 1996.

  4. Лавров И.А., Максимова Л.Л. Задачи по теории множеств, математической логике и теории алгоритмов. - М.: Физмалит, 2001. - 256 с.


Дискретный анализ

  1. Полнота и замкнутость систем булевых функций. Основные замкнутые классы. Теорема Поста о полноте. Сложность реализации булевых функций в классе схем из функциональных элементов. Теорема Шеннона о сложности реализации булевых функций в классе схем из функциональных элементов.

  2. Оценки хроматического числа графов. Раскраска графа. Теорема Брукса. Теорема Визинга. Независимые множества и покрытия в графах. Теорема о числе паросочетаний и числе реберного покрытия. Паросочетания в двудольных графах, теоремы Холла и Кенига.

  3. Формула включений и исключений. Производящие функции, возвратные последовательности и линейные рекуррентные соотношения; общее решение линейного рекуррентного соотношения.

^ Методы оптимизации и принятия решений

  1. Необходимые условия оптимальности для задач нелинейного и выпуклого программирования. Теорема Куна–Таккера (локальная форма). Функция Лагранжа. Понятие седловой точки. Теорема Куна–Таккера (нелокальная форма).

  2. Задачи линейного программирования (ЛП). Эквивалентность понятий базисного допустимого решения и вершины множества допустимых решений. Критерий разрешимости задачи ЛП. Симплекс-метод. Двойственные задачи ЛП. Первая и вторая теоремы двойственности.

  3. Задача коммивояжера. Нижние оценки целевой функции. Метод ветвей и границ. Алгоритм с гарантированной оценкой точности 2 для метрического случая.

  4. Матричные игры. Определение Седловой точки. Необходимые и достаточные условия равенства верхней и нижней цен игры в чистых стратегиях. Теорема фон–Неймана.

^ Теория информации

  1. Циклические коды. Определение циклического кода. Теорема о необходимом и достаточном условии существования циклического кода с порождающим многочленом g(x). Кодирование и декодирование циклических кодов. Примеры циклических кодов: коды Хэмминга, коды Боуза-Чоудхури-Хоквингема (БЧХ-коды).

  2. Разделимые и префиксные коды. Стоимость кодирования. Неравенство Крафта-Макмиллана. Оптимальное кодирование. Метод Хаффмена. Энтропия. Метод Шеннона для бернуллиевских источников. Теорема Шеннона для бернуллиевских источников. Критерий разделимости побуквенного кодирования. Теоремы Маркова.


Л И Т Е Р А Т У Р А

  1. Емеличев В.А. и др. Лекции по теории графов. - М.: Наука, 1990.

  2. Нигматуллин Р.Г. Сложность булевых функций. – Казань: Изд-во Казанского ун-та, 1983.

  3. Холл М. Комбинаторика. - М.: Мир. 1970.

  4. Глебов Н.И. и др. Методы оптимизации. – Новосибирск: НГУ, 2000. http://www.math.nsc.ru/LBRT/k5/mo.html

  5. Кочетов Ю.А. Теория принятия решений. Курс лекций http://www.math.nsc.ru/LBRT/k5/or.html

  6. Соловьева Ф.И. Введение в теорию кодирования: Учебное пособие/ Новосиб. гос. ун-т. Новосибирск, 2006. http://www.codingtheory.gorodok.net/

  7. В. Н. Потапов   "Теория информации. Кодирование вероятностных дискретных источников" Новосибирск: НГУ, 1999. http://www.codingtheory.gorodok.net/


^ III. ДОПОЛНИТЕЛЬНЫЕ ВОПРОСЫ ПО СПЕЦИАЛИЗАЦИИ


Кафедра параллельных вычислений (552802 Высокопроизводительные вычислительные системы)

Организация ЭВМ, комплексов и систем

  1. Традиционная архитектура фон Неймана. Основные архитектурные принципы построения компьютера. Компьютер фон Неймана. Узкие места компьютера фон Неймана и его усовершенствования.

  2. Подсистема памяти современного микропроцессора. Основной принцип построения иерархической памяти. Типичная схема иерархии памяти. Виртуальная память.

  3. Влияние параметров иерархии памяти на время исполнения программы. Рекомендации для написания эффективных программ с учетом параметров иерархической памяти.

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

  5. Архитектуры с параллелизмом на уровне команд. Сравнение способов выявления параллелизма в суперскалярных и VLIW-архитектурах. Примеры архитектур.

  6. Архитектура суперскалярных процессоров. Базисные принципы организации суперскаляров. Основные блоки суперскалярных процессоров. Причины, ограничивающие эффективность суперскаляров. Пути их устранения. Примеры процессоров.

  7. Архитектура процессоров с явным параллелизмом на уровне команд (EPIC). Базисные принципы организации. Itanium – пример EPIC/VLIW-архитектуры. Предикатное выполнение команд. Аппаратная поддержка программной конвейеризации. Спекуляция по данным и управлению. Регистровый стек.

  8. Способы реализации многопоточности в современных микропроцессорах. Примеры многопоточных микропроцессоров.

Тестирование многоядерных микропроцессоров

  1. Уровни тестирования производительности вычислительных систем. Примеры тестов каждого уровня.

  2. Низкоуровневые тесты вычислительной системы. Характеристики производительности подсистемы памяти, исполнительных устройств процессора, сети передачи данных

  3. Примеры современных пакетов тестирования производительности вычислительных систем.

Основы параллельного программирования

  1. Определение процесса. Два главных типа взаимодействия параллельных процессов.

  2. Модель параллельно-последовательного программирования на системах с распределенной памятью и две её подмодели. Характеристика модели. Пример языка, поддерживающего данную модель.

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

  4. Сеть Петри (определение). Графическое изображение сети Петри. Два основных свойства сети Петри. Правила срабатывания переходов.

  5. Определение взаимной блокировки (дедлока) двух и более процессов. Необходимые условия возникновения дедлока. Два подхода в борьбе с дедлоками.

  6. Задача взаимного исключения. Понятие критического интервала, разделяемого и неразделяемого ресурса.

  7. Семафоры. Операции над семафорами (семантика). Привести пример решения задачи взаимного исключения с помощью семафоров при доступе к общему ресурсу для двух и более процессов.

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


Л И Т Е Р А Т У Р А

  1. Таненбаум Э. Архитектура компьютера. Серия "Классика Computer Science". - 5-е изд. - СПб.: Питер, 2007. - 848 с.

  2. Орлов С., Цилькер Б. Организация ЭВМ и систем. - СПб.: Питер, 2007. – 672 с.

  3. Малышкин В.Э., Корнеев В.Д. Параллельное программирование мультикомпьютеров. – Новосибирск: Изд-во НГТУ, 2006.

  4. Эндрюс Г.Р. Основы многопоточного параллельного и распределенного программирования. – М.: Изд. Дом Вильямс, 2003. – 330 с.

  5. Воеводин В.В. , Воеводин Вл.В. Параллельные вычисления. – СПб: БХВ – Петербург, 2002. - 609с.


Кафедра компьютерных систем (552808 Информационное и программное обеспечение автоматизированных систем)


  1. Информация и данные: три уровня представления информации - содержательный, логический и физический. Логическая организация данных: объекты и атрибуты, основные свойства атрибутов.

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

  3. Физическая организация данных. Аппаратные средства организации баз данных. Хешированные файлы. Индексированные файлы. В-деревья. Файлы с плотным индексом. Файлы с записями переменной длины. Вторичное индексирование. Временные характеристики операций.

  4. Архитектура систем управления базами данных: иерархический, сетевой и реляционный подходы к реализации баз данных. Языки манипулирования данными.

  5. Распределенные и параллельные системы баз данных. Архитектура клиент-сервер. Мультипроцессорность. Многопотоковость. Активный сервер. Процедуры БД. Триггеры. Фрагментация и репликация данных. Гетерогенные базы данных. Обработка запросов и управление одновременным доступом в распределенной среде.

  6. Архитектура проблемно-ориентированных программных систем, виды обеспечений: техническое, программное, информационное, математическое, лингвистическое, методическое, организационное.

  7. Типовая структура проблемно-ориентированной системы. Проблемно-ориентированные языки: назначение, требования и принципы реализации.

  8. Автоматизированные системы сбора и обработки информации; системы автоматизированного проектирования; системы автоматизированного управления; системы автоматизации научных исследований; автоматизированные информационно-поисковые системы; системы автоматизации технологических процессов.

  9. Организация графических систем, организация дисплейного файла и файла изображений, графические базы данных и дисплейный файл, порождение на экране новых графических элементов.

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

  11. Специальные графические языки и графические пакеты расширения языков высокого уровня.


Л И Т Е Р А Т У Р А

  1. К. Дж. Дейт, Введение в системы баз данных, 8-ое издание, Москва-Санкт-Петербург-Киев, Изд. дом “Вильямс”, 2005.

  2. В. В. Корнеев, А. Ф. Гареев, С. В. Васютин, В. В. Райх, Базы данных. Интеллектуальная обработка информации, – М.: Нолидж, 2001.- 496с.

  3. Дж. Фоли, А. вэн Дэм. Основы интерактивной машинной графики. В двух книгах. Пер. с англ.-М.:Мир,1985.

  4. Д. Роджерс. Алгоритмические основы машинной графики. Пер. с англ. – М.: Мир, 1989. (2-ое издание – 2001 год).


Кафедра общей информатики, Кафедра систем информатики (552809 Технология разработки программных систем)

  1. Эрбранизация, эрбранова нормальная форма. Теорема Эрбрана.

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

  3. Интуиционисткое исчисление высказываний, семантика Крипке. Теоремы о монотонности и дизъюнкции. Предикатное интуиционисткое исчисление, теорема о дизъюнкции. Модальные логики, семантика Крипке, примеры модальных логик. Свойства шкал Крипке для различных модальных логик. Нечеткие логики. Базисная многозначная логика, свойства. Теорема об 1-тавтологиях. Решётки t-норм.

  4. Синтаксис и семантика языков программирования. Эквивалентность формализмов Бекуса-Наура и синтаксических диаграмм контекстно-свободным грамматикам. Регулярные грамматики, регулярные выражения и конечные автоматы, распознание регулярных языков. Синтаксический разбор контексто–свободных языков, алгоритм Янгера-Коккера-Касами.

  5. Функциональный подход к проектированию трансляторов. Машинно-независимая оптимизация программ. Генерация кода и машинно-зависимая оптимизация. Виды статического анализа. Основы теории абстрактной интерпретации. Частичная и тотальная корректность программ. Логика дерева вычислений, разрешимость, аксиоматизируемость, проверка моделей.


Л И Т Е Р А Т У Р А

  1. Ахо А., Сети Р., Ульман Дж. Компиляторы: принципы, технологии и инструменты. - М.: Издательский дом ''Вильямc'', 2001.

  2. Братко И. Программирование на Прологе для искусственного интеллекта. - М.: Мир, 1990. - 560 с.

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

  4. Емельянов П.Г. Абстрактная интерпретация императивных программ.//Системная Информатика. Вып.6. - Новосибирск: Наука, 1998. - стр.7-47.

  5. Кларк Э., Грамберг О., Пелед Д. Верификация моделей программ. - М.: МЦНМО, 2002.

  6. Клоксин У., Меллиш К. Программирование на языке Пролог. - М.: Мир, 1987. - 336 с.

  7. Метакидес Г., Нероуд А. Принципы логики и логического программирования. - М., изд-во "Факториал", 1998.

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

  9. Чень Ч., Ли Р. Математическая логика и автоматическое доказательство теорем. - М.: Мир, 1983. - 360 с.

  10. E. Turunen. Mathematics Behind Fuzzy Logic. Physica-Verlag Heidelberg New Your, 1999.


Кафедра дискретного анализа и исследования операций (552814 Методы анализа и синтеза проектных решений)

Дискретный анализ

  1. Формула включений и исключений. Производящие функции, возвратные последовательности и линейные рекуррентные соотношения; общее решение линейного рекуррентного соотношения.

  2. Полнота и замкнутость систем булевых функций. Основные замкнутые классы. Теорема Поста. Сложность реализации булевых функций в классе схем из функциональных элементов. Теорема Шеннона о сложности реализации булевых функций в классе схем из функциональных элементов.

  3. Число связности графа. Теорема Менгера. Деревья. Теорема Кэли. Плоские и планарные графы. Формула Эйлера. Правильная вершинная раскраска графа. Теорема Брукса. Правильная реберная раскраска графа. Теорема Визинга. Раскраска карт. Теорема о пяти красках.

  4. Независимые множества и покрытия в графах. Теорема о числе паросочетания и числе реберного покрытия. Паросочетания в двудольных графах. Теоремы Холла, Кенига и Фробениуса.

  5. Конечные автоматы. Теоремы синтеза и анализа конечных автоматов.


Л И Т Е Р А Т У Р А

  1. Емеличев В.А. и др. Лекции по теории графов. - М.: Наука, 1990.

  2. Нигматуллин Р.Г. Сложность булевых функций. – Казань: Изд-во Казанского ун-та, 1983.

  3. Холл М. Комбинаторика. - М.: Мир, 1970.

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

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

  6. Новиков Ф.А. Дискретная математика для программистов. 2000-2001.

Теория принятия решений

  1. Задача коммивояжера. Нижние оценки целевой функции. Метод ветвей и границ. Алгоритм с гарантированной оценкой точности 2 для метрического случая.

  2. Задача календарного планирования. Критические работы, пути и критическое время проекта. Т-поздние расписания для задачи со складируемыми ресурсами. Алгоритм вычисления Т-поздних расписаний.

  3. Матричные игры. Определение Седловой точки. Необходимые и достаточные условия равенства верхней и нижней цен игры в чистых стратегиях. Теорема Фон–Неймана.


Л И Т Е Р А Т У Р А

Ю. А. Кочетов. Теория принятия решений. Курс лекций http://www.math.nsc.ru/LBRT/k5/or.html

^ Методы оптимизации

  1. Необходимые условия оптимальности для задач нелинейного и выпуклого программирования. Теорема Куна–Таккера (локальная форма). Функция Лагранжа. Понятие седловой точки. Теорема Куна–Таккера (нелокальная форма).

  2. Задачи линейного программирования (ЛП). Эквивалентность понятий базисного допустимого решения и вершины множества допустимых решений. Критерий разрешимости задачи ЛП. Симплекс-метод и его лексикографический вариант. Метод искусственного базиса. Двойственные задачи ЛП. Первая и вторая теоремы двойственности.


Л И Т Е Р А Т У Р А

  1. Глебов Н.И. и др. Методы оптимизации. – Новосибирск: НГУ, 2000. http://www.math.nsc.ru/LBRT/k5/mo.html

  2. Карманов В. Г. Математическое программирование. - М.: Наука, 2003.

Теория кодирования

  1. Линейные коды. Кодирование и декодирование. Общие свойства линейных кодов. Теорема о связи проверочной и порождающей матриц. Границы объема кода: граница Синглтона, граница Хэмминга, граница Варшамова-Гилберта, Граница Плоткина.

  2. Циклические коды. Определение циклического кода. Теорема о необходимом и достаточном условии существования циклического кода с порождающим многочленом g(x). Кодирование и декодирование циклических кодов. Примеры циклических кодов: коды Хэмминга, коды Боуза-Чоудхури-Хоквингема (БЧХ-коды), коды Рида-Соломона.

^ Сжатие информации

  1. Разделимые и префиксные коды. Стоимость кодирования. Неравенство Крафта-Макмиллана. Оптимальное кодирование. Метод Хаффмена. Метод Фано.

  2. Энтропия. Метод Шеннона для бернуллиевских источников. Теорема Шеннона для бернуллиевских источников.

  3. Критерий разделимости побуквенного кодирования. Теоремы Маркова. Алгоритм распознавания разделимости.

  4. Адаптивные методы сжатия данных. Методы Лемпела-Зива. Арифметический код.

Элементы криптологии

  1. Криптография и криптоанализ. Криптографические системы с секретными ключами. Подстановки. Перестановки. Шифр с бегущим ключом. Теорема Шеннона о совершенно секретных шифрах, Криптосистемы DES (стандарт шифрования данных) и ГОСТ.

  2. Криптографические системы с открытыми ключами. Односторонняя функция с лазейкой. Криптосистема Диффи и Хэллмана и проблема вычисления дискретного логарифма. Криптосистема RSA и проблема разложения числа на простые сомножители. Криптосистема Меркля-Хэллмана, основанная на задаче об укладке ранца ее криптоанали. Кодирующая система Мак Элиса. Криптосистема, основанная на эллиптических кривых. Цифровая подпись.


Л И Т Е Р А Т У Р А

  1. Соловьева Ф.И. Введение в теорию кодирования: Учебное пособие/ Новосиб. гос. ун-т. Новосибирск, 2006. http://www.codingtheory.gorodok.net/

  2. В. Н. Потапов   "Теория информации. Кодирование вероятностных дискретных источников" Новосибирск: НГУ. 1999.

  3. Рябко Б.Я., Фионов А.Н. Основы современной криптографии. - М.: Научный мир, 2004. - 173 с. http://www.codingtheory.gorodok.net/


Кафедра систем информатики (552818 Компьютерное моделирование)

^ Численные методы и вычислительный эксперимент

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

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

  3. Понятие о вычислительном эксперименте и его инструментальной поддержке. Принципы проведения вычислительного эксперимента. Модель, алгоритм, программа

^ Общие вопросы информатики и вычислительной техники

  1. Управление потоками заданий в ЭВМ. Языковые средства пользователей ЭВМ. Обработка потоков заданий в ЭВМ. Входные и выходные очереди заданий. Понятие входных и выходных классов. Приоритеты заданий. Планирование заданий. Формирование входных очередей. Выборка заданий из очередей. Формирование выходных очередей. Алгоритмы планирования (первый вошел - первый обслужен, кратчайшее задание первым, приоритеты, многоуровневые очереди и другие).

  2. Проблемы и методы защиты информации от несанкционированного доступа

^ Модели, языки, системы и методы программирования

  1. Языки естественные и формальные. Грамматики языков, классификация по Хомскому. Регулярные выражения и их языки. Конечные автоматы, автоматы с магазинной памятью (МП). Детерминированные и недетерминированные конечные автоматы, их эквивалентность. Автоматные грамматики. Языки конечных автоматов и их свойства. Контекстно-свободные грамматики. Контекстно-свободные языки. Характеристика КС-языков в терминах МП-автоматов. Детерминированные КС-языки.

  2. Системы программирования, типовые компоненты СП: языки, трансляторы, редакторы связей, отладчики, текстовые редакторы. Понятие иерархии абстрактных машин.

  3. Модели вычислений и языки программирования. Процедурные и декларативные языки. Функциональные и логические языки.

  4. Основные концепции процедурно-ориентированных языков программирования. Методы процедурного программирования. Примеры.

  5. Основные концепции логического программирования. Методы составления программ и их исполнения в парадигме логического программирования.

  6. Основные концепции функционального программирования. Методы функционального программирования и их реализация. Примеры.

  7. Основные концепции объектно-ориентированного программирования. Организация выполнения объектно-ориентированных программ. Примеры объектно-ориентированных систем программирования.


Л И Т Е Р А Т У Р А

  1. Бахвалов Н.С. Численные методы. М. Наука. 1975.

  2. Попов Ю.П., Самарский А.А. Вычислительный эксперимент. М. Знание. 1983.

  3. Самарский А.А., Михайлов А.П. Математическое моделирование. М.: Физматлит, 1997.

  4. Современные высокопроизводительные компьютеры В. Шнитман, информационно-аналитические материалы Центра Информационных Технологий, 1996 год http://www.citforum.ru/win/hardware/svk/contents.shtml

  5. Иртегов Д. Введение в операционные системы. – СПб: БХВ-Петербург, 2008

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

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

  8. Буч Г. Объектно-ориентированный анализ и проектирование с примерами приложений на C++. – 2-е изд.- М.: Бином, 2000.

  9. Буч Г., Рамбо Дж., Якобсон А. Язык UML. Руководство пользователя. – М.: ДМК, 2000.

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

Кафедра компьютерных систем (552825 Безопасность и защита информации)

Раздел 1. Основные понятия и определения, концептуальные основы информационной безопасности и защиты информации.

  1. Основные понятия и определения: конфиденциальность, целостность, доступность, угроза, уязвимость, риски. Понятие и подходы к построению модели угроз. Принципы защиты информации. Классы средств защиты информации.

Раздел 2. Организационно-правовые аспекты защиты информации. Политика безопасности и управление рисками.

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

  2. Политика ИБ: общее понятие и место в системе защиты информации. Связь процессов управления ИТ-безопасностью с жизненным циклом информационных систем. Управление рисками ИБ: общее понятие, действия по отношению к рискам, этапы управления рисками, типовые модели и методики анализа рисков.

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

Раздел 3. Стандартизация в сфере безопасности информационных технологий.

  1. «Оранжевая книга» как первый в мире стандарт безопасности компьютерных систем. Структура требований к системам защиты информации в компьютерных системах. Интерпретация оранжевой книги для сетевых конфигураций.

  2. Рекомендации X.800. Стандарт ISO/IEC 15408 («Общие критерии») - назначение, основные принципы и качественное отличие от известных ранее оценочных стандартов.

  3. ГОСТ Р 52069.0-2003 (Система стандартов. Основные положения), ГОСТ Р 50922-2006 (термины и определения), ГОСТ Р 51275-2006 (Факторы, воздействующие на информацию), ГОСТ Р ИСО/МЭК 17799-2005 («Информационная технология. Практические правила управления информационной безопасностью»).

  4. Критерии оценки безопасности информационных технологий ISO15408 (ГОСТ Р ИСО/МЭК 15408): назначение и суть методологии, основные понятия, профиль защиты и задание по безопасности, структура требований, принципы оценки.

Раздел 4. Математические методы и модели в задачах защиты информации

  1. Основные понятия криптографии. Принципы замены и перестановки. Симметричное шифрование.

  2. Понятие о стеганографии. Атаки на шифры. Понятие о криптоанализе. Cтойкость шифров. Поточные и блочные шифры

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

  4. Криптографические хеш-функции: общее понятие и их применение. Ключевые и бесключевые функции, их назначение, свойства, принципы построения.

  5. Криптографические протоколы: общее понятие, свойства, примеры. Доказательство с нулевым разглашением и протоколы аутентификации. Открытое распределение ключей - протокол Диффи-Хелмана. Протоколы разделения секрета.

  6. Электронная цифровая подпись (ЭЦП): понятие и назначение ЭЦП, сходство и различия с собственноручной подписью. Инфраструктура открытых ключей (PKI).

  7. Математические модели безопасности в ОС: субъектно-объектный подход, доступы, монитор безопасности, доверенная вычислительная база. Дискреционные модели безопасности. Модель Хариссона-Рузо-Ульмана (HRU).

  8. Мандатные модели безопасности. Модель Белла-Лападула (БЛМ).

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

  10. Модели контроля целостности: модель Биба, модель Кларка-Вилсона.

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

Раздел 5. Многоуровневая защита информации в компьютерных системах и сетях.

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

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

  3. Методы и средства анализа защищенности компьютерных систем и сетей. Сканеры безопасности и их возможности. Автономные и встроенные средства анализа защищенности.

  4. Защита периметра и межсетевые экраны. Общее понятие, решаемые задачи, основные защитные механизмы, классы межсетевых экранов.

  5. Обеспечение безопасности при передаче данных. Защищенные протоколы сетевого взаимодействия. Средства защиты электронной почты. Понятие о виртуальных частных сетях.

  6. Обнаружение вторжений. Системы обнаружения вторжений: общее понятие, принципы функционирования и примеры технологических решений.

  7. Защита от вредоносных программ. Виды вредоносных программ. Принципы организации антивирусной защиты.

  8. Контроль целостности и резервирование. Стандартные требования к системам контроля целостности в автоматизированных системах. Технологии резервирования информации.

  9. Обеспечение доступности информации в компьютерной среде. Направления поддержания высокой доступности: повышение отказоустойчивости и надежного оперативного восстановления.

  10. Классификация информационных систем персональных данных, построение модели угроз, методика выявления актуальных угроз, рекомендации и основные мероприятия при защите персональных данных.



Основная литература*.

  1. Галатенко В. А. Основы информационной безопасности [Электронный ресурс] / В. А. Галатенко. – М.: Интернет-ун-т информ. технологий, 20031 – 280 с. – Режим доступа: www.intuit.ru.

  2. Девянин П. Н. Модели безопасности компьютерных систем / П. Н. Девянин. – М.: Академия, 2005 – 144 с.

  3. А.П.Алферов, А.Ю.Зубов, А.С.Кузьмин, А.В.Черемушкин. Основы криптографии (учебное пособие) – М.: Гелиос АРВ, 2004 – 480 с.

  4. Рябко Б.Я., Фионов А.Н. Основы современной крипографии - М.: Научный мир, 2004.

  5. С.В.Запечников, Н.Г.Милославская, А.И.Толстой, Д.В.Ушаков. Информационная безопасность открытых систем. Том 1. Угрозы, уязвимости, атаки и подходы к защите. – М.: Горячая линия – Телеком, 2006.

  6. С.В.Запечников, Н.Г.Милославская, А.И.Толстой, Д.В.Ушаков. Информационная безопасность открытых систем. Том 2. – М.: Горячая линия – Телеком, 2008.

  7. Тексты государственных концептуально-стратегических документов, Законов РФ, РД Гостехкомиссии и ФСТЭК, упомянутые в программе [Электронный ресурс]. – Режим доступа: www.fstec.ru.


Дополнительная литература.

  1. Петренко С.А., Симонов С.В. Управление информационными рисками. – М.: АйТи, 2005.

  2. В.А.Тихонов, В.В.Райх. Информационная безопасность: концептуальные, правовые, организационные и технические аспекты. -М.: Гелиос АРВ, 2006

  3. Романец Ю.В., Тимофеев П.А., Шаньгин В.Ф. Защита информации в компьютерных системах и сетях. Радио и связь, 2001.

  4. Галатенко В. А. Стандарты безопасности информационных технологий [Электронный ресурс] / В. А. Галатенко. – М.: Интернет-ун-т информ. технологий, 2005 – 280 с. – Режим доступа: www.intuit.ru.

  5. Е.Б.Белов, В.П.Лось, Р.В.Мещеряков, А.А.Шелупанов. Основы информационной безопасности — М.:Горячая линия -Телеком, 2006 — 544 с.

  6. Периодические издания: «Безопасность информационных технологий», «Открытые системы», «Информационная безопасность» (www.itsec.ru), «Джетинфо» (www.jetinfo.ru ).

Ресурсы Интернет: www.fstec.ru , www.securitylab.ru , pd.rsoc.ru, www.ispdn.ru, www.altx-soft.ru, www.cyberpol.ru, www.agentura.ru, www.azi.ru , www.infotecs.ru, www.infosec.ru , www.infoforum.ru, www.cnews.ru, www.pki-forum.ru и др.


Кафедра информационно-измерительных систем (552824 Информационно-измерительные системы, 552812 Системы мультимедиа и компьютерная графика)

  1. Понятие информации, ее измерение. Единицы измерения информации. Кодирование и квантование сигналов. Технические и программные средства информационных технологий.

  2. Системы счисления. Перевод чисел из одной системы счисления в другую. Двоичная система счисления.

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

  4. Функциональная и структурная организация компьютера. Машинные команды. Методы адресации. Организация памяти. Оперативная память.

  5. Организация службы времени. Обработка прерываний.

  6. Моделирование. Типы моделей. Понятие «черного ящика». Проблема идентификации. Адекватность моделей.

  7. Языки программирования. Концепции процедурно-ориентированного и объектно-ориентированного. Способы описания алгоритмов. Единая система программной документации.

  8. Принципы модульного, компонентного, объектно-ориентированного проектирования, шаблоны проектирования. Моделирование программных систем, язык UML.

  9. Управление доступом к данным. Файловые системы (основные типы, характеристики).

  10. Основные понятия систем баз данных. Назначение и основные компоненты систем баз данных: база данных, система управления базами данных (СУБД), программные и языковые средства СУБД, пользователи баз данных, администратор систем баз данных и его функции.

  11. Построение информационных систем (ИС) на концептуальном уровне. ИС в АСУ, системах автоматизации проектирования, системах автоматизации экспериментальных исследований. Формирование информационных моделей процессов и документов.


^ 6. РЕКОМЕНДУЕМАЯ ЛИТЕРАТУРА


  1. Каган Б.М. Электронные вычислительные машины и системы: учебное пособие для вузов. 3-е издание. М.: Энергоатомиздат. 1991, 592с.

  2. М.Гук Аппаратные средства IBM PC, энциклопедия 2-е издание - С.-По.:2001, 816с.

  3. М.Гук Архитектуры и интерфейсы ПК. энциклопедия 2-е издание - С -Пб .2001.

  4. Олифер В.Г., Олифер Н.А. «Компьютерные сети. Принципы, технологии, протоколы» Питер, 2001.

  5. Грузман И.С., Киричук В.С. и др. Цифровая обработка изображений в информационных системах. Учебное пособие. НГТУ, Новосибирск, 2002.

  6. Прэтт У. Цифровая обработка изображений, в 2-х томах.: Мир, Москва, 1982.

  7. Дейт К.Дж. Введение в системы баз данных: Пер. с англ. - 6-е изд. - К.: Диалектика, 1999. - 848 с.

  8. Хансен Г. Базы данных. Разработка и управление: М., Изд. Бином, 2000. - 700 с.

  9. Боггс У., Боггс М. UML и Rational Rose: Пер. с англ. - М.: Издательство "Лори", 2000. - 582 с.

  10. Вендров A.M. CASE-технологии. Современные методы и средства проектирования информационных систем: М.: Финансы и статистика, 1998. - 176 с.

  11. Маклаков СВ. BPWin, ERWin CASE - средства разработки информационных систем: М.: Диалог-МИФИ, 1999. - 256 с.

  12. Гордеев А В., Молчанов А.Ю. Системное программное обеспечение. СПб: Питер, 2001. 736 с.

  13. Дьяконов В., Абраменкова И. Обработка сигналов и изображений. Специальный справочник. СПб.: Питер, 2002.

  14. Поршнев СВ. Компьютерное моделирование физических процессов. М. Горячая линия-Телеком, 2003.

  15. Сергиечко А.Б. Цифровая обработка сигналов. СПб.: Питер, 2006.

  16. Благодатских В.А. Стандартизация разработки программных средств: Учеб. пособие/ В.А. Благодатских, В.А. Волнин, К.Ф. Поскэкалов; Под ред. О С. Разумова - М Финансы и статистика, 2005. 288 с.

  17. Орлов С.А. Технологии разработки программного обеспечения: Учебник для вузов. 3-е изд./ С.А. Орлов. - СПб.: Питер, 2004. - 527 с.

  18. Э.Таненбаум. Современные операционные системы, Издательство: Питер, 2010г.,

  19. Н.Н.Гринченко, Е. В. Гусев, Н. П. Макаров. Проектирование баз данных. СУБД Microsoft Access, Издательство: Горячая Линия – Телеком, 2004г.,




* Не более 10 источников.

1 В связи с изменением в 2006 году законодательства РФ соответствующий раздел в данном учебнике не является актуальным. Утратили силу законы «Об информации, информатизации и защите информации», «Об участии в международном информационном обмене», вступили в силу законы «Об информации, информационных технологиях и защите информации», «О персональных данных». Соответствующие вопросы изучаются по первоисточникам.







Скачать 292,07 Kb.
оставить комментарий
Дата29.09.2011
Размер292,07 Kb.
ТипПрограмма, Образовательные материалы
Добавить документ в свой блог или на сайт

Ваша оценка этого документа будет первой.
Ваша оценка:
Разместите кнопку на своём сайте или блоге:
rudocs.exdat.com

Загрузка...
База данных защищена авторским правом ©exdat 2000-2017
При копировании материала укажите ссылку
обратиться к администрации
Анализ
Справочники
Сценарии
Рефераты
Курсовые работы
Авторефераты
Программы
Методички
Документы
Понятия

опубликовать
Документы

наверх