I. Общие положения
Целью вступительного экзамена в магистратуру является проверка степени подготовленности бакалавров для продолжения обучения в магистратуре по направлению «Информатика и вычислительная техника» (230100) в соответствии с требованиями ГОС ВПО по этому направлению.
II. Структура совокупности знаний и умений
В основу программы положены дисциплины федерального компонента цикла общих математических и естественнонаучных дисциплин и цикла общепрофессиональных дисциплин.
Общие математические и естественнонаучные дисциплины:
1. Математика.
1.1. Дискретная математика.
1.2. Математическая логика и теория алгоритмов.
1.3. Методы оптимизации.
2. Информатика.
Общепрофессиональные дисциплины:
3. Организация ЭВМ и систем.
4. Базы данных.
5. Операционные системы
6. Сети ЭВМ и телекоммуникации.
7. Электротехника и электроника, Раздел – Электроника (Схемотехника).
III. Содержание программы
Дискретная математика.
1. Множества и их способы задания;
2. Диаграммы Венна;
3. Отношения и их свойства;
4. Отношение эквивалентности и классификация множеств;
5. Планарные графы;
6. Матрицы смежности и инцидентности;
7. Пути и контуры в графе;
8. Симметрия графа и его дополнения;
9. Двоичные алгебры;
10. Способы задания бинарных функций;
11. Функциональная полнота базиса бинарных функций;
12. Примеры функционально-полных базисов.
Литература.
1. Андерсон, Джеймс А. Дискретная математика и комбинаторика. - Пер. с англ. — М.: Издатель- Издательский дом "Вильямс", 2004. — 960 с.
2. Иванов Б. Н. Дискретная математика. Алгоритмы и программы: Учеб. пособие — М.: Лаборатория Базовых Знаний, 2003. — 288 с: ил.
3. Новиков Ф.А. Дискретная математика для программистов. -СПб, Питер, 2000. - 304с
4. Яблонский С.В. Введение в дискретную математику. 4-е издание, стереотипное - М.: Высшая школа, 2003. - 484 с.
5. Поздняков С.Н. Рыбин С.В. Дискретная математика.-М: Академия.: 2008.
Математическая логика и теория алгоритмов
1. Логика высказываний;
2. Логика предикатов;
3. Синтаксис и семантика языка логики предикатов;
4. Метод резолюций в логике предикатов;
5. Нечёткая и модальная логики;
6. Аксиоматические системы;
7. Рекурсия и рекурсивные функции;
8. Формализация понятия алгоритма;
9. Меры сложности алгоритмов;
10. Классы задач P и NP.
Литература
1. Ершов Ю.Л., Палютин Е.А.Математическая логика: Учеб. пособие для вузов. - М., Наука, 1987. - 336 с..
2. Игошин В.И. Математическая логика и теория алгоритмов: учеб. пособие для студ. высш. учеб. заведений — 2-е изд., стер. — М.: Издательский центр «Академия», 2008. — 448 с.
3. Колмогоров А.Н., Драгалин А.Г. Математическая логика. Изд. 3-е, стереотипное. — М.: КомКнига, 2006. 240 с.
4. Позняков С.Н., Рыбин С.В. Дискретная математика: Учебник — М. Academia, 2008.
Методы оптимизации
1. Элементы теории оптимизации.
2. Задачи условной оптимизации.
3. Одномерная оптимизация.
4. Методы оптимизации первого порядка.
5. Методы оптимизации второго порядка.
6. Методы оптимизации нулевого порядка.
7. Методы прямого поиска в задачах условной оптимизации.
8. Решение задач условной оптимизации.
9. Организация диалоговой оптимизации в САПР.
Литература
1. Лесин В.В., Лисовец Ю.П. Основы методов оптимизации. / Учеб. пособие. - М.: Изд. МАИ, 1995.
2. Банди Б. Методы оптимизации. Вводный курс. - М.: Радио и связь, 1988.
3. Пантелеев А.В., Летова Т.А. Методы оптимизации в примерах и задачах – Учебное пособие для втузов, М, 2002, 544с.
4. Системный анализ: учебник для вузов по направлению «Информатика и вычислительная техника» и специальности «Автоматизированные системы обработки информации и управления» / А. В. Антонов. - Изд. 2-е. - М.: Высшая школа, 2004. - 453 с.
5. Аттетков А.В., Зарубин В.С., Канатников А.Н. Введение в методы оптимизации –М.: ИНФРА-М, 2008.
6. Измаилов А.Ф., Солодов М.В. Численные методы оптимизации: учеб. Пособие –М.: Физматлит, 2003
Информатика
1. Базовые концептуальные структуры информатики.
2. Методологические принципы информатики.
3. Место и роль формальной теории в информатике.
4. Гипотеза о физической символьной системе.
5. Объекты и функции.
6. Функциональная модель данных.
7. Конструктивный процесс; примеры процессов, порождающих простейшие символьные структуры.
8. Автомат как модель конструктивного процесса.
9. Вычисление как физический процесс.
10. Сообщения и сигналы.
11. Кодирование и квантование сигналов.
12. Задачи информационного поиска и организация информации.
13. Обработка аналоговой и цифровой информации.
14. Понятие и свойства алгоритма.
15. Алгоритм как базис программирования для компьютеров фон-Неймановской архитектуры.
16. Объектная спецификация программы и алгоритмический характер управления процессом её выполнения.
17. Формальные системы и алгоритмы как формы задания вычислительных процессов.
18. Рекурсия и её связь с вычислимой функцией.
19. Интерпретация законов логики в предметной области вычислительной техники.
20. Свойства информационного процесса в компьютере (дискретность, конвенциональность, ограниченность, изолированность).
Литература
1. Герасимов И.В., Калмычков В.А., Чугунов Л.А. Информатика. Применение сетевых компьютерных технологий. Учебн. пособие. – СПб: Изд-во СПбГЭТУ «ЛЭТИ», 2004.
2. Герасимов И.В., Калмычков В.А., Ларистов А.И., Лозовой Л.Н. Информатика. Учебно-методический комплекс по теме «Сетевые компьютерные технологии». Учебн. пособие. – СПб: Изд-во СПбГЭТУ «ЛЭТИ», 2001.
3. Информатика: Энциклопедический словарь для начинающих / Сост. Д.А.Поспелов. — М.: Педагогика Пресс, 1994. — 352с.
4. Опалева Э.А., Самойленко В.П. Языки программирования и методы трансляции. Учебн. пособие. – СПб: Изд-во BHV, 2005. – 480 с.
5. Верещагин Н.К., Шень А. Вычислимые функции. изд. 2-ое, испр. – М.: МЦНМО, 2002 г. – 173 стр.
6. Гиляревский Р.С. Основы информатики. - Издательство Экзамен, 2003. - 320с.
7. Информатика. Базовый курс. 2-е издание / Под ред. С.В. Симоновича. - СПб.: Питер, 2004. - 640 с.
Организация ЭВМ и систем
1. Аппаратное обеспечение (HW):
устройства памяти (MemU); процессор (ProcU); устройства ввода-вывода (IOU); сетевые устройства (NetU).
2. Программное обеспечение (SW):
системное, обеспечивающее управление ресурсами (OS); прикладное, представляющее собой приложения (AP); пользовательские интерфейсы (UI).
3. Интеллектуальное обеспечение (BW):
управление процессами (PR); управление данными (DB); управление объектами (OO); управление человеко-машинным взаимодействием (HC).
4. Сетевое обеспечение (MW):
транспорт данных; группы протоколов мобильных агентов; группы протоколов локальных сетей (Ethernet); группы протоколов глобальных сетей (TCP/IP); группы протоколов корпоративных сетей (VPN).
5. Понятие архитектуры компьютерной системы:
традиционная фон-Неймановская; модели, управляемые потоками данных и потоками команд систем.
6. Зависимость затрат памяти от архитектуры компьютерной системы.
7. Многоуровневая организация ЭВМ. Сущность каждого уровня и их взаимосвязь.
8. Структура процессора. Состав и назначение компонент. Основной цикл работы процессора.
9. Аппаратная и микропрограммная реализация формирователя управляющих сигналов. Основные особенности организации. Достоинства и недостатки.
10. Причины появления, особенности организации компьютеров с сокращенным набором команд (KCHK). Базовая архитектура KCHK (RISK). Формат команды.
11. Назначение системы прерываний в ЭВМ. Механизмы реализации прерываний.
12. Программные и внешние прерывания. Векторы прерываний.
13. Память ЭВМ: основные операции, характеристики и требования к памяти. Классификация видов запоминающих устройств (ЗУ).
14. ЗУ произвольной выборки. Постоянная ЗУ. Ассоциативные ЗУ.
15. Иерархия систем памяти. Кэш-память. Принцип использования. Особенности реализации. Понятие расслоения адресов памяти.
16. Виртуальная память (ВП). Страничный и сегментированный способы организации ВП.
17. Организация дисковой памяти. Физический и логический уровни организации информации на дисках. Назначение и структура таблицы размещения файлов (FAT) в операционной системе (OS) компьютера.
18. Проблема организации ввода-вывода в ЭВМ. Требования к системе ввода-вывода (CBB). Типы архитектуры CBB.
19. Способы управления вводом-выводом: по факту готовности и по программному прерыванию.
20. Обмен данными в режиме прямого доступа в память (аппаратного прерывания). Особенности организации.
Литература
1. Таненбаум Э. Архитектура компьютерных систем. - СПб: Питер, 2002.
2. Корнеев В.В., Киселев А.В. Современные микропроцессоры -М.: «Нолидж», 2000.
3. Цилькер Б.Я., Орлов С.А. Организация ЭВМ и систем. Учебник для вузов. СПб.:, Питер, 2006.
4. Организация ЭВМ. 5-е изд./ К.Хамахер, З.Вранешич, С.Заки. – СПб. Питер; Киев: Издательская группа BHV, 2003. – 848 с.: ил.- (Серия «Классика computer science»).
Базы данных
1. Сферы применения баз данных.
2. Понятие базы данных, СУБД, банка данных.
3. Модель предметной области.
4. Концептуальная модель. Типы моделей данных.
5. Реляционная модель данных. Основные определения: отношения, домены, кортежи, атрибуты. Схема отношения, его степень и мощность.
6. Реляционная БД. Понятие первичного и внешнего ключа. Свойства отношений реляционной БД. Ограничения на отношения, основные операции над отношениями.
7. Цели проектирования. Универсальное отношение и проблемы его использования.
8. Функциональные зависимости (ФЗ). Декомпозиция отношения. Нормальная форма Бойса-Кодда (НФБК).
9. Избыточные ФЗ. Правила вывода. Минимальное покрытие.
10. Декомпозиционный метод проектирования.
11. Модель <сущность-связь> (ER-модель) и её основные нотации. Правила перехода от ER-модели к реляционной модели. Основные этапы проектирования БД методом <сущность-связь>.
12. Нормальные формы: 1НФ-5НФ.
13. Метод нормальных форм.
14. Способы создания и модификации структуры таблицы.
15. Способы занесения информации в БД.
16. Установка связей межу отношениями БД. Цели установки связи. Основные правила и ограничения.
17. Цели и способы упорядочения информации, хранящейся в БД.
18. Два способа проектирования запросов к БД: языки QBE и SQL.
19. Назначение и типы отчётов.
Литература
1. Дейт К.Дж. Введение в системы баз данных. - К.: Диалектика, 2000.
2. Баженова И.Ю. Visual FoxPro 5.0. Объектно-ориентированные средства программирования. - М.: Диалог-Мифи, 1997.
3. Хомоненко А.Р., Цыганков В.М., Мальцев М.Г. Базы данных. Учебник для высших учебных заведений. - СПб: Корона,2004 - 416 с.
4. Т.С. Карпова. Базы данных: модели, разработка, реализация. Учебник. – СПб.: Питер, 2001.
5. Ю.Тихомиров. Microsoft SQL Server 7.0. – СПб.: БХВ – Санкт-Петербург, 2000.
6. Марков А.С., Лисовский К.Ю. Базы данных: Введение в теорию и методологию: Учебник для вузов. – М: Финансы и статистика, 2006. – 512 с.
Операционные системы
1. Архитектура ОС. Назначение и функции операционных систем (ОС).
2. Обеспечение безопасности в ОС. Принципы построения и защита от сбоев и несанкционированного доступа.
3. Файловые системы (ФС). Файлы и их атрибуты. Структура каталогов. Логическая организация ФС. Логическая и физическая организация файлов. Защита ФС
4. Управление памятью. Методы распределения памяти без использования дискового пространства. Методы распределения памяти с использованием дискового пространства. Механизм реализации виртуальной памяти. Страничное распределение. Сегментное и странично-сегментное распределение. Защита памяти. Стратегия подкачки страниц (свопинга). Архитектура виртуальной памяти. Менеджер виртуальной памяти.
5. Управление процессорами. Управление процессором. Понятие процесса и ядра. Сегментация виртуального адресного пространства процесса. Структура контекста процесса. Идентификатор и дескриптор процесса. Иерархия процессов. Диспетчеризация и синхронизация процессов. Понятия приоритета и очереди процессов. Средства обработки сигналов. Понятие событийного программирования.
6. Межпроцессное взаимодействие. Предотвращение критических ситуаций и средства синхронизации процессов. Возникновение гонок (состязаний). Критические секции, условия исключения гонок. Семафоры. Задача о читателях-писателях. Мьютексы. Мониторы.
7. Синхронизация потоков с использованием объектов ядра. Объекты синхронизации и их состояния. Понятие событийного программирования. События, ожидаемые таймеры, семафоры, мьютексы.
8. Передача информации между процессами. Средства коммуникации процессов.
Виды взаимодействия между процессами. Сокеты.
Литература.
1. Таненбаум Э., Вудхалл А. Операционные системы: Разработка и реализация. СПб.: Питер, 2006. – 576 с.
2. Гордеев А.В. Операционные системы: Учебник для вузов/ СПб, Питер, 2009.