[ МИНОБРНАУКИ РОССИИ
Федеральное государственное бюджетное образовательное учреждение
высшего профессионального образования
«Санкт-Петербургский государственный электротехнический университет “ЛЭТИ”
имени В.И. Ульянова (Ленина)» (СПбГЭТУ)
ПРОГРАММА
ВСТУПИТЕЛЬНОГО ЭКЗАМЕНА В МАГИСТРАТУРУ
ПО НАПРАВЛЕНИЮ
09.04.01 «Информатика и вычислительная техника»Санкт-Петербург 2014 Содержание программы Раздел 1.
Дискретная математика 1. Множества и их способы задания;
2. Диаграммы Венна;
3. Отношения и их свойства;
4. Отношение эквивалентности и классификация множеств;
5. Планарные графы;
6. Матрицы смежности и инцидентности;
7. Пути и контуры в графе;
8. Симметрия графа и его дополнения;
9. Двоичные алгебры;
10. Способы задания бинарных функций;
11. Функциональная полнота базиса бинарных функций;
12. Примеры функционально-полных базисов.
Математическая логика и теория алгоритмов 1. Логика высказываний;
2. Логика предикатов;
3. Синтаксис и семантика языка логики предикатов;
4. Метод резолюций в логике предикатов;
5. Нечёткая и модальная логики;
6. Аксиоматические системы;
7. Рекурсия и рекурсивные функции;
8. Формализация понятия алгоритма;
9. Меры сложности алгоритмов;
10. Классы задач P и NP.
Методы оптимизации 1. Элементы теории оптимизации.
2. Задачи условной оптимизации.
3. Одномерная оптимизация.
4. Методы оптимизации первого порядка.
5. Методы оптимизации второго порядка.
6. Методы оптимизации нулевого порядка.
7. Методы прямого поиска в задачах условной оптимизации.
8. Решение задач условной оптимизации.
9. Организация диалоговой оптимизации в САПР.
Раздел 2. Информатика 1. Базовые концептуальные структуры информатики.
2. Методологические принципы информатики.
3. Место и роль формальной теории в информатике.
4. Гипотеза о физической символьной системе.
5. Объекты и функции.
6. Функциональная модель данных.
7. Конструктивный процесс; примеры процессов, порождающих простейшие символьные структуры.
8. Автомат как модель конструктивного процесса.
9. Вычисление как физический процесс.
10. Сообщения и сигналы.
11. Кодирование и квантование сигналов.
12. Задачи информационного поиска и организация информации.
13. Обработка аналоговой и цифровой информации.
14. Понятие и свойства алгоритма.
15. Алгоритм как базис программирования для компьютеров фонНеймановской архитектуры.
16. Объектная спецификация программы и алгоритмический характер управления процессом её выполнения.
17. Формальные системы и алгоритмы как формы задания вычислительных процессов.
18. Рекурсия и её связь с вычислимой функцией.
19. Интерпретация законов логики в предметной области вычислительной техники.
20. Свойства информационного процесса в компьютере (дискретность, конвенциональность, ограниченность, изолированность).
Раздел 3. Организация ЭВМ и систем 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. Обмен данными в режиме прямого доступа в память (аппаратного прерывания). Особенности организации.
Раздел 4.Базы данных 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. Назначение и типы отчётов.
Раздел 5. Операционные системы 1. Архитектура ОС. Назначение и функции операционных систем (ОС).
2. Обеспечение безопасности в ОС. Принципы построения и защита от сбоев и несанкционированного доступа.
3. Файловые системы (ФС). Файлы и их атрибуты. Структура каталогов. Логическая организация ФС. Логическая и физическая организация файлов. Защита ФС 4. Управление памятью. Методы распределения памяти без использования дискового пространства. Методы распределения памяти с использованием дискового пространства. Механизм реализации виртуальной памяти. Страничное распределение. Сегментное и странично-сегментное распределение. Защита памяти. Стратегия подкачки страниц (свопинга).
Архитектура виртуальной памяти. Менеджер виртуальной памяти.
5. Управление процессорами. Управление процессором. Понятие процесса и ядра. Сегментация виртуального адресного пространства процесса.
Структура контекста процесса. Идентификатор и дескриптор процесса.
Иерархия процессов. Диспетчеризация и синхронизация процессов. Понятия приоритета и очереди процессов. Средства обработки сигналов. Понятие событийного программирования.
6. Межпроцессное взаимодействие. Предотвращение критических ситуаций и средства синхронизации процессов. Возникновение гонок (состязаний). Критические секции, условия исключения гонок. Семафоры.
Задача о читателях-писателях. Мьютексы. Мониторы.
7. Синхронизация потоков с использованием объектов ядра. Объекты синхронизации и их состояния. Понятие событийного программирования.
События, ожидаемые таймеры, семафоры, мьютексы.
8. Передача информации между процессами. Средства коммуникации процессов. Виды взаимодействия между процессами. Сокеты.
Раздел 6. Сети ЭВМ и телекоммуникации 1. Вычислительные сети. Понятие. Назначение. Услуги, предоставляемые пользователю.
2. Архитектуры распределённых систем. Модели распределённых систем в архитектуре «клиент-сервер».
3. Локальные ВС. Назначение. Архитектура. Протоколы. Пример реализации.
4. Корпоративные ВС. Особенности. Архитектура. Протоколы. Пример реализации.
5. Глобальные ВС. Архитектура. Протоколы. Пример реализации.
Сервисы ГВС.
6. Топологии ВС. Достоинства и недостатки.
7. Сетевые интерфейсные контроллеры, концентраторы и коммутаторы.
8. Серверы ВС. Особенности и варианты реализации.
9. Модели взаимодействия открытых систем. Семиуровневая модель OSI. Модель TCP/IP. Протоколы и интерфейсы.
10. Протоколы физического и канального уровней. Сетевые технологии: Ethernet, Token Ring, FDDI.
11. Протоколы сетевого и транспортного уровня.
12. Протоколы прикладного уровня.
13. Протоколы ГВС. Стек TCP/IP. Адресация в IP сетях.
14. Структура сетевой операционной системы (СОС). Сетевые службы.
Одноранговые СОС и СОС с выделенным сервером.
15. Структура Windows NT. Особенности. Управление процессами.
Управление файлами. Сетевые средства.
16. Пиринговые сети (peer-to-peer (P2P)).
ЛИТЕРАТУРА
Раздел 1. Андерсон, Джеймс А. Дискретная математика и комбинаторика. Пер. с англ. — М. : Издатель- Издательский дом "Вильямс", 2004. — 960 с.2. Поздняков С.Н. Рыбин С.В. Дискретная математика.-М: Академия.:
2008.
3. Игошин В.И. Математическая логика и теория алгоритмов : учеб.
пособие для студ. высш. учеб. заведений — 2-е изд., стер. — М. :
Издательский центр «Академия», 2008. — 448 с.
4. Колмогоров А.Н., Драгалин А.Г. Математическая логика. Изд. 3-е, стереотипное. — М.: КомКнига, 2006. 240 с.
5. Позняков С.Н., Рыбин С.В. Дискретная математика: Учебник — М.
Academia, 2008.
6. Системный анализ: учебник для вузов по направлению «Информатика и вычислительная техника» и специальности «Автоматизированные системы обработки информации и управления» / А. В.
Антонов. - Изд. 2-е. - М.: Высшая школа, 2004. - 453 с.
7. Аттетков А.В., Зарубин В.С., Канатников А.Н. Введение в методы оптимизации –М.: ИНФРА-М, 2008.
Раздел 1. Герасимов И.В., Калмычков В.А., Чугунов Л.А. Информатика.
Применение сетевых компьютерных технологий. Учебн. пособие. – СПб:
Изд-во СПбГЭТУ «ЛЭТИ», 2004.
2. Опалева Э.А., Самойленко В.П. Языки программирования и методы трансляции. Учебн. пособие. – СПб: Изд-во BHV, 2005. – 480 с.
3. Информатика. Базовый курс. 2-е издание / Под ред. С.В.
Симоновича. - СПб.: Питер, 2004. - 640 с.
Раздел 1. Цилькер Б.Я., Орлов С.А. Организация ЭВМ и систем. Учебник для вузов. СПб.:, Питер, 2006.
2. Организация ЭВМ. 5-е изд./ К.Хамахер, З.Вранешич, С.Заки. – СПб.
Питер; Киев: Издательская группа BHV, 2003. – 848 с.: ил.- (Серия «Классика computer science»).
Раздел 1. Хомоненко А.Р., Цыганков В.М., Мальцев М.Г. Базы данных.
Учебник для высших учебных заведений. - СПб: Корона,2004 - 416 с.
2. Марков А.С., Лисовский К.Ю. Базы данных: Введение в теорию и методологию: Учебник для вузов. – М: Финансы и статистика, 2006. – 512 с.
Раздел 1. Таненбаум Э., Вудхалл А. Операционные системы: Разработка и реализация. СПб.: Питер, 2006. – 576 с.
2. Гордеев А.В. Операционные системы: Учебник для вузов/ СПб, Питер, 2009.
Раздел 1. Олифер В.Г., Олифер Н.А. Компьютерные сети. Принципы, технологии, протоколы. 4-е издание. СПб.: Питер, 2010. - 918 с.
«