скачать
МИНОБРНАУКИ РОССИИ
Государственное образовательное учреждение высшего профессионального образования
Санкт-Петербургский государственный электротехнический университет «ЛЭТИ»
имени В.И. Ульянова (Ленина)» (СПбГЭТУ)
УТВЕРЖДАЮ
Проректор по учебной работе профессор
______________________ Лысенко Н.В.
«______»_______________2011 г.
ПРОГРАММА
ВСТУПИТЕЛЬНОГО ЭКЗАМЕНА В МАГИСТРАТУРУ
ПО НАПРАВЛЕНИЮ ПОДГОТОВКИ
230100.68 «Информатика и вычислительная техника»
2011
^
Целью вступительного экзамена в магистратуру является проверка степени подготовленности бакалавров для продолжения обучения в магистратуре по направлению «Информатика и вычислительная техника» (230100) в соответствии с требованиями ГОС ВПО по этому направлению.
^
В основу программы положены дисциплины федерального компонента цикла общих математических и естественнонаучных дисциплин и цикла общепрофессиональных дисциплин.
Общие математические и естественнонаучные дисциплины:
Математика.
Дискретная математика.
Математическая логика и теория алгоритмов.
Методы оптимизации.
Информатика.
Общепрофессиональные дисциплины:
Организация ЭВМ и систем.
Базы данных.
Сети ЭВМ и телекоммуникации.
Объектно-ориентированное программирование.
Схемотехника.
Содержание программы
Дискретная математика.
Множества и их способы задания;
Диаграммы Венна;
Отношения и их свойства;
Отношение эквивалентности и классификация множеств;
Планарные графы;
Матрицы смежности и инцидентности;
Пути и контуры в графе;
Симметрия графа и его дополнения;
Двоичные алгебры;
Способы задания бинарных функций;
Функциональная полнота базиса бинарных функций;
Примеры функционально-полных базисов.
Литература.
Андерсон, Джеймс А. Дискретная математика и комбинаторика. - Пер. с англ. — М. : Издатель- Издательский дом "Вильямс", 2004. — 960 с.
Грэхем Р., Кнут Д., Паташник О. Конкретная математика. Основание информатики. - М., Мир, 1998. - 704 с.
Иванов Б. Н. Дискретная математика. Алгоритмы и программы: Учеб. пособие — М.: Лаборатория Базовых Знаний, 2003. — 288 с: ил.
Новиков Ф.А. Дискретная математика для программистов. -СПб, Питер, 2000. - 304с
Яблонский С.В. Введение в дискретную математику. 4-е издание, стереотипное - М.: Высшая школа, 2003. - 484 с.
Математическая логика и теория алгоритмов
Логика высказываний;
Логика предикатов;
Синтаксис и семантика языка логики предикатов;
Метод резолюций в логике предикатов;
Нечёткая и модальная логики;
Аксиоматические системы;
Рекурсия и рекурсивные функции;
Формализация понятия алгоритма;
Меры сложности алгоритмов;
Классы задач P и NP.
Литература
Ершов Ю.Л., Палютин Е.А.Математическая логика: Учеб. пособие для вузов. - М. , Наука, 1987. - 336 с..
Игошин В.И. Математическая логика и теория алгоритмов : учеб. пособие для студ. высш. учеб. заведений — 2-е изд., стер. — М. : Издательский центр «Академия», 2008. — 448 с.
Колмогоров А.Н., Драгалин А.Г. Математическая логика. Изд. 3-е, стереотипное. — М.: КомКнига, 2006. 240 с.
Методы оптимизации
Элементы теории оптимизации.
Задачи условной оптимизации.
Одномерная оптимизация.
Методы оптимизации первого порядка.
Методы оптимизации второго порядка.
Методы оптимизации нулевого порядка.
Методы прямого поиска в задачах условной оптимизации.
Решение задач условной оптимизации.
Организация диалоговой оптимизации в САПР.
Литература
Батищев Д.И. Методы оптимального проектирования. / Учеб. пособие. - М.: Советское радио, 1984.
Лесин В.В., Лисовец Ю.П. Основы методов оптимизации. / Учеб. пособие. - М.: Изд. МАИ, 1995.
Химмельбау Дж. Прикладное нелинейное программирование. - М.: Мир, 1975.
Моисеев Н.Н., Иванилов Ю.П., Столяров Е.М. Методы оптимизации: Учебное пособие для вузов по специальности «прикладная математика» – М.: Наука, 1978, 351 с.
Банди Б. Методы оптимизации. Вводный курс. - М.: Радио и связь, 1988.
Пантелеев А.В., Летова Т.А. Методы оптимизации в примерах и задачах – Учебное пособие для втузов, М, 2002, 544с.
Системный анализ: учебник для вузов по направлению «Информатика и вычислительная техника» и специальности «Автоматизированные системы обработки информации и управления» / А. В. Антонов. - Изд. 2-е. - М.: Высшая школа, 2004. - 453 с.
2. Информатика
Базовые концептуальные структуры информатики.
Методологические принципы информатики.
Место и роль формальной теории в информатике.
Гипотеза о физической символьной системе.
Объекты и функции.
Функциональная модель данных.
Конструктивный процесс; примеры процессов, порождающих простейшие символьные структуры.
Автомат как модель конструктивного процесса.
Вычисление как физический процесс.
Сообщения и сигналы.
Кодирование и квантование сигналов.
Задачи информационного поиска и организация информации.
Обработка аналоговой и цифровой информации.
Понятие и свойства алгоритма.
Алгоритм как базис программирования для компьютеров фон-Неймановской архитектуры.
Объектная спецификация программы и алгоритмический характер управления процессом её выполнения.
Формальные системы и алгоритмы как формы задания вычислительных процессов.
Рекурсия и её связь с вычислимой функцией.
Интерпретация законов логики в предметной области вычислительной техники.
Свойства информационного процесса в компьютере (дискретность, конвенциональность, ограниченность, изолированность).
Литература
Герасимов И.В., Стеклова Г.А., Чугунов Л.А. Информатика. Информационные объекты и модели. Учебн. пособие. – СПб: Изд-во СПбГЭТУ «ЛЭТИ», 1998.
Герасимов И.В., Чугунов Л.А. Информатика. Конструктивные объекты и процессы. Учебн. пособие. – СПб: Изд-во СПбГЭТУ «ЛЭТИ», 1999.
Герасимов И.В., Калмычков В.А., Чугунов Л.А. Информатика. Применение сетевых компьютерных технологий. Учебн. пособие. – СПб: Изд-во СПбГЭТУ «ЛЭТИ», 2004.
Герасимов И.В., Калмычков В.А., Ларистов А.И., Лозовой Л.Н. Информатика. Учебно-методический комплекс по теме «Сетевые компьютерные технологии». Учебн. пособие. – СПб: Изд-во СПбГЭТУ «ЛЭТИ», 2001.
Информатика: Энциклопедический словарь для начинающих / Сост. Д.А.Поспелов. — М.: Педагогика Пресс, 1994. — 352с.
Опалева Э.А., Самойленко В.П. Языки программирования и методы трансляции. Учебн. пособие. – СПб: Изд-во BHV, 2005. – 480 с.
Верещагин Н.К., Шень А. Вычислимые функции. изд. 2-ое, испр. – М.: МЦНМО, 2002 г. – 173 стр.
Под ред. С.В. Симонович. Информатика. Базовый курс : учеб. пособие для втузов. - СПб. : Питер, 2001. - 638 с.
Гиляревский Р.С. Основы информатики. - Издательство Экзамен, 2003. - 320с.
3. Организация ЭВМ и систем
Аппаратное обеспечение (HW):
устройства памяти (MemU);
процессор (ProcU);
устройства ввода-вывода (IOU);
сетевые устройства (NetU).
Программное обеспечение (SW):
системное, обеспечивающее управление ресурсами (OS);
прикладное, представляющее собой приложения (AP);
базы данных (DB);
пользовательские интерфейсы (UI).
Интеллектуальное обеспечение (BW):
управление процессами (PR);
управление данными (DB);
управление объектами (OO);
управление человеко-машинным взаимодействием (HC).
Сетевое обеспечение (MW):
транспорт данных;
группы протоколов мобильных агентов;
группы протоколов локальных сетей (Ethernet);
группы протоколов глобальных сетей (TCP/IP);
группы протоколов корпоративных сетей (VPN).
Понятие архитектуры компьютерной системы:
традиционная фон-Неймановская;
модели, управляемые потоками данных и потоками команд систем.
Зависимость затрат памяти от архитектуры компьютерной системы.
Многоуровневая организация ЭВМ. Сущность каждого уровня и их взаимосвязь.
Структура процессора. Состав и назначение компонент. Основной цикл работы процессора.
Аппаратная и микропрограммная реализация формирователя управляющих сигналов. Основные особенности организации. Достоинства и недостатки.
Причины появления, особенности организации компьютеров с сокращенным набором команд (KCHK). Базовая архитектура KCHK (RISK). Формат команды.
Назначение системы прерываний в ЭВМ. Механизмы реализации прерываний.
Программные и внешние прерывания. Векторы прерываний.
Память ЭВМ: основные операции, характеристики и требования к памяти. Классификация видов запоминающих устройств (ЗУ).
ЗУ произвольной выборки. Постоянная ЗУ. Ассоциативные ЗУ.
Иерархия систем памяти. Кэш-память. Принцип использования. Особенности реализации. Понятие расслоения адресов памяти.
Виртуальная память (ВП). Страничный и сегментированный способы организации ВП.
Организация дисковой памяти. Физический и логический уровни организации информации на дисках. Назначение и структура таблицы размещения файлов (FAT) в операционной системе (OS) компьютера.
Проблема организации ввода-вывода в ЭВМ. Требования к системе ввода-вывода (CBB). Типы архитектуры CBB.
Способы управления вводом-выводом: по факту готовности и по программному прерыванию.
Обмен данными в режиме прямого доступа в память (аппаратного прерывания). Особенности организации.
Литература
Таненбаум Э. Архитектура компьютерных систем. - СПб: Питер, 2002.
Таненбаум Э. Многоуровневая организация ЭВМ.-М.:Мир,1979.
Корнеев В.В., Киселев А.В. Современные микропроцессоры -М.: «Нолидж», 2000.
Базы данных
Сферы применения баз данных.
Понятие базы данных, СУБД, банка данных.
Модель предметной области.
Концептуальная модель. Типы моделей данных.
Реляционная модель данных. Основные определения: отношения, домены, кортежи, атрибуты. Схема отношения, его степень и мощность.
Реляционная БД. Понятие первичного и внешнего ключа. Свойства отношений реляционной БД. Ограничения на отношения, основные операции над отношениями.
Цели проектирования. Универсальное отношение и проблемы его использования.
Функциональные зависимости (ФЗ). Декомпозиция отношения. Нормальная форма Бойса-Кодда (НФБК).
Избыточные ФЗ. Правила вывода. Минимальное покрытие.
Декомпозиционный метод проектирования.
Модель <сущность-связь> (ER-модель) и её основные нотации. Правила перехода от ER-модели к реляционной модели. Основные этапы проектирования БД методом <сущность-связь>.
Нормальные формы: 1НФ-5НФ.
Метод нормальных форм.
Способы создания и модификации структуры таблицы.
Способы занесения информации в БД.
Установка связей межу отношениями БД. Цели установки связи. Основные правила и ограничения.
Цели и способы упорядочения информации, хранящейся в БД.
Два способа проектирования запросов к БД: языки QBE и SQL.
Назначение и типы отчётов.
Литература
Джексон Г. Проектирование реляционных баз данных для использования с микро-ЭВМ. -М.: Мир. 1991.
Дейт К.Дж. Введение в системы баз данных. - К.: Диалектика, 2000.
Баженова И.Ю. Visual FoxPro 5.0. Объектно-ориентированные средства программирования. - М.: Диалог-Мифи, 1997.
Менахем Базиян и др. Использование Visual FoxPro 6. Специальное издание. - К., М., СПб: Издательский дом «Вильямс», 1999.
Хомоненко А.Р., Цыганков В.М., Мальцев М.Г. Базы данных. Учебник для высших учебных заведений. - СПб: Корона - 416 с.
Сети ЭВМ и телекоммуникации
Вычислительные сети. Понятие. Назначение. Услуги, предоставляемые пользователю.
Архитектуры распределённых систем. Модели распределённых систем в архитектуре «клиент-сервер».
Локальные ВС. Назначение. Архитектура. Протоколы. Пример реализации.
Корпоративные ВС. Особенности. Архитектура. Протоколы. Пример реализации.
Глобальные ВС. Архитектура. Протоколы. Пример реализации. Сервисы ГВС.
Топологии ВС. Достоинства и недостатки.
Сетевые интерфейсные контроллеры, концентраторы и коммутаторы.
Серверы ВС. Особенности и варианты реализации.
Модели взаимодействия открытых систем. Семиуровневая модель OSI. Модель TCP/IP. Протоколы и интерфейсы.
Протоколы физического и канального уровней. Сетевые технологии: Ethernet, Token Ring, FDDI.
Протоколы сетевого и транспортного уровня.
Протоколы прикладного уровня.
Протоколы ГВС. Стек TCP/IP. Адресация в IP сетях.
Структура сетевой операционной системы (СОС). Сетевые службы. Одноранговые СОС и СОС с выделенным сервером.
Структура Windows NT. Особенности. Управление процессами. Управление файлами. Сетевые средства.
Пиринговые сети (peer-to-peer (P2P)).
Литература
Кульгин М. Технологии корпоративных сетей: Энциклопедия. - СПб.: Питер, 1999.
Гладцын В.А., Яновский В.В. Сетевые технологии. Учеб. пособие СПбГЭТУ «ЛЭТИ». - СПб, 1998.
Гладцын В.А., Яновский В.В. Управление вычислительными сетями. Учеб. пособие СПбГЭТУ «ЛЭТИ». - СПб, 2000.
Щербо В.К. Стандарты вычислительных сетей. Взаимосвязи сетей. Справочник. - М.: КУДИЦ-ОБРАЗ, 2000.
Олифер В.Г., Олифер Н.А. Компьютерные сети. Принципы, технологии, протоколы. - СПб: Питер, 1999.
Объектно-ориентированное программирование
Эволюция методологий программирования. Парадигмы программирования: процедурное, модульное, объектно-ориентированное, обобщённое. Модуль как единица построения программных систем. Абстракция данных. Объектные и объектно-ориентированные языки программирования.
Основные положения объектного подхода к разработке программ. Принципы объектного подхода (классы, объекты, сообщения, наследование, полиморфизм). Составные части объектного подхода: абстрагирование, инкапсуляция, ограничение доступа, модульность, иерархия, типизация, параллелизм.
Понятие объекта и класса. Свойства, присущие объектам: состояние, поведение, идентичность. Инкапсуляция и спецификация правил доступности элементов класса.
Определение класса. Собственная и общая части определения класса. Члены класса: данные (механизм реализации состояния объекта) и методы (механизм реализации поведения объекта). Примеры описания и использования классов.
Доступ к членам класса (обеспечение инкапсуляции). Функции-элементы класса и функции-друзья.
Создание (конструирование) и уничтожение объектов и массивов объектов класса. Конструкторы и деструкторы. Указатели на объекты. Особенности использования конструктора копирования, конструктора по умолчанию, оператора присваивания. Использование this. Инициализация объектов. Отличия инициализации от присваивания.
Статические члены объектов класса. Инициализация статических полей.
Наследование как средство организации иерархий классов. Базовый и производный классы. Примеры описания и использования классов с наследованием.
Правила доступа к элементам производного класса. Конструкторы и деструкторы производного класса. Совмещение имён методов при наследовании.
Иерархия классов: одиночное и множественное наследование. Виды классов: конкретный, абстрактный, интерфейсный и др.
Перегрузка функций и операторов языка C++ как реализация поведения с предопределённым смыслом.
Полиморфизм. Раннее и позднее связывание.
Виртуальные функции. Таблицы виртуальных функций. Распределение таблиц виртуальных функций в многофайловых программах. Чистые виртуальные функции и абстрактные базовые классы.
Отношения между объектами: типы отношений, связь (ассоциация), агрегация. Отношения между классами: типы отношений, ассоциация, агрегация и композиция, использование, наследование, инстанцирование. Объекты при передаче параметров и возврате из методов.
Унифицированный язык моделирования UML. Обзор наиболее популярных элементов нотации UML. Описание классов и их взаимосвязей: диаграммы классов. Динамика поведения объектов: диаграммы перехода состояний. Диаграммы объектов. Видимость и синхронизация объектов: временные диаграммы. Диаграмма процессов.
Шаблоны классов и функций. Определение шаблона. Инстанцирование.
Наследование шаблонных классов. Специализация.
Применение шаблонных классов для создания контейнерных классов. Интерфейс и реализация контейнерных классов для моделирования структур данных. Описание селекторов и модификаторов.
Управление последовательностью действий в объектно-ориентированной программе. Объект и процесс. Инициализация и взаимодействие объектов и процессов. Сообщения. Реализация механизмов посылки сообщений. Примеры функционирования объектно-ориентированной программы.
Обработка ошибок. Группировка и перехват исключений. Обработка и генерация исключений. Исключения и эффективность. Блок try, оператор catch, throw.
Литература
Буч Г. Объектно-ориентированный анализ и проектирование с примерами приложений на C++. / Пер. с англ. под ред. И. Романовского, Ф. Андреева. - СПб: «Невский диалект», 1998.
Страуструп Б. Язык программирования C++. / Пер. с англ. С. Анисимова, М. Кононова под ред. Ф. Андреева, А. Ушакова. - СПб: «Невский диалект», 1991, 2001.
Бадд Т. Объектно-ориентированное программирование в действии. - СПб: «Питер», 1997.
Лафоре Р. Объектно-ориентированное программирование в C++. - СПб: «Питер», 2000.
Пол А. Объектно-ориентированное программирование на C++. - СПб: «Невский диалект», 2001.
Дейтел Харви, Дейтел Пол. Как программировать на C++. 3-е изд. / Пер. с англ. - М.: ЗАО «Издательство БИНОМ», 2001.
Буч Г., Рамбо Д., Джекобсон А. Язык UML. - М.: «ДМК Пресс», 2001.
Остерн М.Г. Обобщённое программирование и STL: использование и наращивание стандартной библиотеки шаблонов C++. / Пер. с англ. С. Анисимова, В. Калмычкова, Ю. Прокофьева под ред. А. Махоткина и И. Романовского. - СПб: «Невский диалект», 2004.
Топп У., Форд У. Структуры данных в C++. / Пер. с англ. под ред. В. Кузьменко. - М.: ЗАО «Издательство БИНОМ», 1999.
Телло Э.Р. Объективно-ориентированное программирование в среде Windows. / Пер. с англ. Д.М. Арапова, А.К. Петренко. 1993.
Схемотехника
Общая хаpактеpистика усилительных устpойств.
Понятие об обратных связях (ОС) в электронных устройствах.
Устойчивость электpонных устpойств с обpатной связью.
Интегральные операционные усилители (ОУ) и решающие усилители (РУ).
Электронные ключи.
Логические интегральные микросхемы.
Триггеры.
Счётчики.
Литература
Е.П. Угрюмов. Цифровая схемотехника. СПб, 2000.
Искусство схемотехники. Хоровиц П., Хилл У. В 3-х томах. Пер.с англ. – М.: Мир, 1993.
Председатель МС ЭТУ по направлению
230100 - «Информатика и вычислительная техника»
д.т.н., профессор И.В. Герасимов
Добавить документ в свой блог или на сайт
|
