Программа вступительного испытания в магистратуру
по направлению 230100.68 – «Информатика и вычислительная техника»
магистерская программа «Информатика и вычислительная техника»
Функциональное и логическое программирование
1. Базовые функции для обработки списков в Лиспе.
2. Лямбда-определение функций в Лиспе.
3. Создание поименованных функций в Лиспе.
4. Функционалы в Лиспе: применяющие и отображающие.
5. Разделы программы в Турбо-Прологе.
6. Основные элементы Пролога: предикаты, факты, правила.
7. Рекурсия в Турбо-Прологе. Использование стека.
8. Соединение списков и определение длины списка (Турбо-Пролог).
9. Компоновка списка на основе базы данных (Турбо-Пролог).
10. Встроенные предикаты для работы со строками в Турбо-Прологе.
11. Работа с файлами в Турбо-Прологе.
12. Динамические базы данных в Турбо-Прологе.
Системы искусственного интеллекта и
нейрокомпьютерные системы
1. Продукционная модель представления знаний.
2. Фреймовая модель представления знаний.
3. Семантические сети.
4. Системы общения на естественном языке. Основные компоненты.
5. Сеть встречного распространения. Структура. Функционирование. Обучение.
6. Решение интеллектуальных задач. Поиск в пространстве состояний и в пространстве задач.
7. Эвристический поиск.
8. Генетические алгоритмы.
9. Сеть обратного распространения. Структура. Функционирование. Обучение.
10. Искусственный нейрон: входы, веса, передаточная функция.
11. Персептрон. Структура. Функционирование. Обучение.
12. Понятие об обучении нейронной сети.
Объектно-ориентированное программирование
1. Принципы ООП. Основные понятия: объект (класс), поле, метод.
2. Наследование и полиморфизм. Раннее и позднее связывание. Виртуальные динамические методы.
3. Создание и уничтожение экземпляров объектов. Конструкторы и деструкторы.
4. Свойства. Векторные свойства.
5. Структура и иерархия классов в известных вам системах программирования.
6. Компонент (определение). Группы свойств компонентов по их предназначению.
7. Понятие класса в Delphi (C-builder). Свойства классов. Создание и удаление экземпляров классов.
8. Состав и назначение класса TObject.
9. Основные составляющие программы: форма, проект. Основные типы файлов.
10. Обработка исключительных ситуаций при выполнении программы.
Класс Exception.
11. Структура справочной системы в приложениях и средства ее создания.
12. Класс TApplication. Его предназначение. Основные свойства.
13. События (определение). Виды событий. Описание реакции на события.
14. Оконные и неоконные элементы управления.
Структуры и алгоритмы обработки данных
1. Абстрактные типы данных, АДТ-формат.
2. Классы коллекций: линейные коллекции.
3. Классы коллекций: нелинейные коллекции.
4. Критерий эффективности алгоритмов, последовательный и бинарный поиск.
5. Стеки, АДТ. Оценка выражений, постфиксная оценка.
6. Очереди, АДТ. Очереди приоритетов.
7. Сортировка на базе шаблона. Вычисление инфиксного выражения.
8. Надежные массивы.
9. Сопоставление с образцом.
10. Целочисленные множества.
11. Создание связанных списков.
12. Циклические и двусвязанные списки.
13. Рекурсия: происхождение лабиринта.
14. Терминология деревьев, бинарные деревья.
15. Алгоритмы происхождения деревьев.
16. Бинарные деревья поиска. Конкорданс.
17. Итераторы, слияние сортированных последовательностей.
18. Бинарные деревья, представленные массивами, турнирная сортировка.
19. Пирамиды, Пирамидальная сортировка.
20. AVI-деревья. Оценка сбалансированных деревьев.
21. Графы, способы прохождения графов.
22. Достижимость и алгоритм Уоршалла.
23. Основные алгоритмы сортировки массивов: выбора, пузырька, вставками.
24. Быстрая сортировка.
25. Хэширование: ключи и хэш-функции.
26. Разрешение коллизий при хэшировании.
27. Бинарные файлы: внешний поиск.
28. Бинарные файлы: внешняя сортировка.
29. Бинарные файлы: сортировка естественным слиянием.
30. Словари.
Операционные системы
1. Предназначение и функции ОС.
2. Виды структур ОС. Примеры ОС.
3. Архитектура ОС Windows 2000. Подсистемы окружения. Исполнительная система. Ядро. Уровень абстрагирования от оборудования.
4. Архитектура ОС Unix.
5. Процессы. Состояния процессов. Структуры управления процессами. Создание процессов. Переключение процессов.
6. Потоки. Многопоточность. Потоки на пользовательском уровне и на уровне ядра.
7. Процессы в ОС Windows 2000. Структуры данных, сопоставляемые с процессами. Создание процессов.
8. Потоки в ОС Windows 2000. Внутренне устройство потоков. Создание потоков.
9. Объекты ядра в ОС Windows 2000.
10. Подсистема Win32. Win32 API.
11. Планирование в системах с одним процессором. Типы планирования. Критерии планирования, стратегии планирования.
12. Многопроцессорное планирование.
13. Планирование реального времени.
14. Планирование в ОС Windows 2000. Уровни приоритета. Кванты. Структуры данных связанные с планированием. Сценарии планирования. Планирование в системах с симметричной мультипроцессорной обработкой.
15. Понятие синхронизации. Назначение. Способы синхронизации. Примеры.
16. Синхронизация в ОС Windows 2000. Синхронизация потоков в пользовательском режиме. Синхронизация потоков с использованием объектов ядра.
17. Технологии управления памятью. Страничная организация памяти. Сегментная организация памяти. Комбинация сегментации и страничной организации.
18. Виртуальная память. Стратегии ОС для виртуальной памяти.
19. Управление памятью в ОС Windows 2000. Диспетчер памяти. Структура адресного пространства процесса. Дескрипторы виртуальных адресов. Рабочие наборы. Проецируемые в память файлы.
20. Динамически подключаемые библиотеки. Неявное, явное, отложенное связывание.
21. Защита в ОС Windows 2000. Компоненты системы защиты. Маркеры. Дескрипторы защиты.
22. Подсистема ввода-вывода в ОС Windows 2000. Компоненты подсистемы ввода-вывода. Диспетчер ввода-вывода. Драйверы устройств. Диспетчер Play and Play. Диспетчер электропитания. Структуры данных, связанные с вводом-выводом.
23. Запуск работы ОС Windows 2000.
24. Кэш. Диспетчер кэша, структура кэша, размер кэша в ОС Windows 2000.
Теория вычислительных процессов
1. Асинхронный процесс. Основные определения.
2. Свойства систем управления.
3. Структурирование процессов.
4. Модельные интерпретации. Предметные интерпретации.
5. Изобразительные средства для асинхронных процессов.
6. Сети Петри. Основные определения.
7. Графовое представление сети Петри.
8. Маркированные сети Петри. Основные соглашения выполнения сети.
9. Анализ сетей (дерево достижимости).
10. Свойства сетей Петри.
Архитектура вычислительных систем
1. Архитектура системы команд. Классификация процессоров.
2. Конвейерная организация. Основные этапы выполнения машинной команды.
3. Конфликты в конвейере, их классификация.
4. Структурные конфликты и способы их минимизации.
5. Конфликты по данным, их минимизация.
6. Классификация конфликтов по данным.
7. Конфликты по управлению, минимизация конфликтов по управлению.
8. Планирование загрузки конвейера и разворачивание циклов.
9. Прогнозирование условных переходов. Двухбитная схема предсказания переходов.
10. Суперскалярная обработка. Архитектура Intel Pentium.
11. Архитектура машин с длинным командным словом.
12. Принципы организации подсистемы памяти.
13. Кэширование.
14. Память с расслоением.
15. Концепция виртуальной памяти.
16. Дисковые массивы.
Организация ЭВМ и систем
1. Расширенная и дополнительная память (XMS и EMS).
2. Служебные области памяти в реальном режиме процессоров х86.
3. Сегментная модель памяти, вычисление адреса в реальном режиме процессоров Intel.
4. Организация стека и работа с ним.
5. Регистры. Группы регистров по функциональному назначению.
6. Вызов процедур в машинном коде. Дальний и ближний вызов. Передача параметров.
7. Таблица векторов прерываний. Векторы прерываний. Процедуры ISR.
8. Механизм обработки прерываний.
9. Основные сведения о жестких дисках.
10. Размещение информации на жестком диске.
11. Порядок загрузки операционных систем.
12. Основные сведения о видеоадаптерах.
13. Способы программирования видеоподсистемы.
14. Программирование портов ввода-вывода.
15. Адресация в защищенном режиме процессоров x86.
Базы данных
1. Базы данных. СУБД. Модели данных. Архитектуры данных
2. Иерархическая модель данных
3. Сетевая модель данных
4. Реляционная модель данных (структурная часть). Отношение. Свойства отношений
5. Реляционная модель данных (манипуляционная часть). Реляционная алгебра. Теоретико-множественные операторы, специальные реляционные операторы. Запросы, невыразимые средствами реляционной алгебры.
6. Функциональные зависимости. Замыкание множества функциональных зависимостей. Минимальное покрытие. Декомпозиция без потерь
7. Теория нормальных форм. 1, 2, 3 нормальные формы. Нормальная форма Бойса-Кодда
8. Многозначные зависимости. 4 и 5 нормальные формы.
9. Реляционная модель данных (целостная часть). Ограничения целостности, классификация.
10. Основы SQL. Программные объекты, операторы, команды.
11. Оператор SELECT. Структура, синтаксис, порядок выполнения.
12. Операторы INSERT, UPDATE, DELETE.
13. Оператор CREATE TABLE, реализация декларативных ограничений целостности.
14. Реализация связей между таблицами средствами Transact SQL (1:0|N, 1:N, транзитивное замыкание, иерархические связи)
15. Триггеры
16. Хранимые процедуры
17. Функции, определяемые пользователем. Реализация транзитивного замыкания
18. Представления.
19. Курсоры. Создание кросс-таблиц
20. Индексы
21. Транзакции. Свойство ACID. Работа транзакции в смеси. Проблемы параллельной работы транзакций. Блокировки. Метод временных меток. Механизм выделения версий данных
22. Транзакции и восстановление данных. Виды восстановления данных. Индивидуальный откат, восстановление после мягкого сбоя, восстановление после жесткого сбоя
23. Технологии доступа к данным (JET, ODBC, OleDB). Модели DAO, ADO, .
24. Организация доступа к данным с помощью . Работа с отсоединенными объектами (DataSet, DataTable, DataColumn, DataRow)
25. Организация доступа к данным с помощью . Работа с присоединенными объектами (Connection, Command, DataReader, DataAdapter, Transaction)
26. Предметная область. Функциональная модель предметной области. Бизнес-модель процессов, модель потоков данных.
27. Информационная модель предметной области. Диаграммы «сущность-связь». Сущности, атрибуты, отношения.
Технология разработки программного обеспечения
1. Объясните понятия «жизненный цикл программного обеспечения» (ЖЦПО) и «модель жизненного цикла программного обеспечения». Перечислите основные модели жизненного цикла программного обеспечения (ЖЦПО).
2. Дайте краткую характеристику спиральной модели жизненного цикла программного обеспечения.
3. Объясните, как соотносятся понятия «класс» и «объект»? Опишите основные категории объектов. (ТРПО)
4. Опишите основные типы связей между классами. (ТРПО)
5. UML – общая характеристика, назначение основных диаграмм. (ТРПО)
6. Дайте краткую характеристику основных фаз процесса объектно-ориентированной разработки программного обеспечения, согласно UML. (ТРПО)
7. Объясните понятие «модуль» (функция, логика и контекст модуля). (ТРПО)
8. Объясните понятия «связность модулей» и «сцепление модулей». Какие типы связности и сцепления модулей считаются желательными и почему? (ТРПО)
9. Методология функционального моделирования SADT: состав функциональной модели (рассмотрите на примере). (ТРПО)
10. Методология моделирования потоков данных: внешние сущности, системы и подсистемы, процессы, накопители данных, потоки данных (рассмотрите на примере). (ТРПО)
11. Моделирование данных, методология IDEF1 (рассмотрите на примере). (ТРПО)
12. Цели стандартизации. Перечислите известные Вам организации и комитеты по стандартизации (в области разработки программного обеспечения). (ТРПО)
13. Проведите краткий сравнительный анализ стандартов, определяющих жизненный цикл программного обеспечения (ЖЦПО) (ГОСТ 19.102-78, ГОСТ 34.601, DO-178, ИСО/МЭК ). (ТРПО)
14. Опишите основные виды и назначение документов, сопровождающих процесс разработки программного обеспечения (software process documentation, software product documentation, user documentation, system documentation). (ТРПО)
15. Объясните понятия «отладка» и «тестирование». Общий анализ методов тестирования.
16. Объясните понятия «CASE-технология» и «CASE-средство». Опишите назначение, возможности и состав CASE-средств.
Методы и средства защиты компьютерной информации
1. Защита информации. Основные понятия. Угрозы и меры защиты. Виды атак. Лица, атакующие компьютеры и сети.
2. Локальные атаки. Методы защиты. Устройства идентификации пользователя.
3. Сетевые атаки. Атаки на электронную почту. Методы защиты.
4. Сетевые атаки. Атаки на браузер. Методы защиты.
5. Криптография. Основные термины и определения. Задачи криптографии.
6. Шифрование данных. Основные термины и определения. Классификация алгоритмов шифрования.
7. Поточные шифры простой замены. Классификация. Примеры. Методы криптоанализа.
8. Блочные шифры простой замены. Методы криптоанализа блочных шифров простой замены. Шифры Плейфера и Хилла.
9. Блочные шифры простой замены. Методы криптоанализа блочных шифров простой замены. Американский стандарт шифрования DES.
10. Шифры гаммирования. Шифр Виженера.
11. Шифры перестановки. Примеры. Методы криптоанализа.
12. Асимметричные системы шифрования. Основной принцип работы. Система шифрования RSA. Методы криптоанализа и защиты.
13. Обеспечение целостности. Код аутентификации сообщения. Требования и средства реализации.
14. Ключевые хэш-функции. Основные требования и примеры построения. Атаки на хэш-функции.
15. Обеспечение неоспоримости. Цифровая подпись. Задачи и алгоритмы реализации.
16. Информационная безопасность. Определение и основные задачи. Политика информационной безопасности. Составные элементы политики информационной безопасности.
17. Информационная безопасность. Основные направления. Служба информационной безопасности. Критерии необходимости создания службы.
18. Автоматизированные средства безопасности. Антивирусы. Межсетевые экраны.
19. Управления ключами.
