Омский государственный университет им. Ф.М. Достоевского

Факультет компьютерных наук

Утверждено ученым советом

факультета компьютерных наук

«21» мая 2010 г.

ПРОГРАММА ГОСУДАРСТВЕННОГО ЭКЗАМЕНА

по специальности 230101.65 - «Вычислительные машины, комплексы, системы и сети»

очная и очно-заочная форма обучения СД.02 Моделирование 1. Потоки случайных событий.

Пуассоновский поток. Функция распределения простейшего потока. Распределения потоков фазового типа. Поток Эрланга. Основные характеристики потоков.

2. Случайный процесс. Марковский случайный процесс. Уравнение Колмогорова.

Типы случайных процессов. Марковские случайные процессы. Вектор состояния системы.

Переходные вероятности. Классификация состояний. Предельный вектор цепи Маркова.

Теорема Маркова. Эргодическая система. Уравнение Колмогорова. Построение системы уравнений.

3. Генерация последовательности случайных чисел с заданным распределением.

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

4. Моделирование систем массового обслуживания.

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

5. Методы обработки результатов моделирования.

Регрессионный анализ. Метод наименьших квадратов. Коэффициент детерминации. Точность предсказания. Допущения регрессионного анализа. Проверка значимости. Анализ остатков.

Рекомендуемая литература:

1. Боев В.Д. Моделирование систем. Инструментальные средства GPSS World: Учеб. пособие. – СПб.:

БХВ-Петербург, 2004.

2. Гнеденко Б.В., Коваленко И.Н. Введение в теорию массового обслуживания. – М.: КомКнига, 2005.

3. Рыжиков Ю.И. Имитационное моделирование. Теория и технологии. – СПб.: КОРОНА принт; М.:

Альтекс – А, 2004.

СД.05 Системное программное обеспечение 1. Трансляторы, компиляторы, интерпретаторы.

Этапы, фазы и стадии трансляции. Схема работы транслятора. Однопроходные и многопроходные трансляторы.

2. Лексический анализ.

Назначение. Выделение лексем. Таблицы лексем. Способы построения лексических анализаторов. Построение анализаторов на основе регулярных выражений, с использованием диаграмм переходов конечных автоматов. Лексические ошибки и способы их обработки.

3. Синтаксический анализ.

Нисходящий и восходящий синтаксический анализ. Понятие LL(K)-грамматик. S-грамматики, q-грамматики. LL(1)-грамматики. Синтаксический анализ методом рекурсивного спуска.

Символы-последователи. Первые порождаемые символы. Понятие о факторизации грамматик.

4. Оптимизация кода.

Критерии оптимизации. Виды оптимизирующих преобразований. Оптимизация линейных участков программы. Удаление бесполезных присваиваний. Исключение лишних операций.

Свертка объектного кода. Перестановка операций. Арифметические преобразования.

Оптимизация вычисления логических выражений. Исключение инвариантных операндов.

Предопределенные операции. Оптимизация передачи параметров в подпрограммы. Метод подстановки кода функции в вызывающий объектный код. Оптимизация циклов. Вынесение инвариантных вычислений из циклов. Замена операций с индуктивными переменными.

Слияние и развертывание циклов.

5. Системы программирования. Интегрированные среды разработки.

Структура современной системы программирования. Текстовые редакторы. Лексический анализ «на лету». Система подсказок и справок. Компоновщики. Загрузчики. Трансляция адресов. Настраивающий загрузчик. Динамические загрузчики. Отладчики. Функции отладчиков. Библиотеки подпрограмм. Статические и динамические библиотеки подпрограмм.

Ресурсы пользовательского интерфейса.

Рекомендуемая литература:

1. Молчанов А.Ю. Системное программное обеспечение: Учебник для вузов. 3-е изд. – СПб.: Питер, 2010. – 400 с.

2. Ахо А.В., Лам М.С., Сети Р., Ульман Дж. Д. Компиляторы: принципы, технологии и инструментарий. 2-е изд. – М.: Вильямс, 2010. – 1184 с.

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

Мир, 1978.

СД.06 Интерфейсы периферийных устройств 1. Интерфейс как комплекс средств сопряжения узлов вычислительной техники и периферийного оборудования.

Классификация интерфейсов и параметры интерфейсов. Функции интерфейсов; программная и аппаратная составляющая интерфейса; параметры интерфейсов; классификация интерфейсов по способу передачи данных, по режимам обмена, по конструктивному исполнению;

интерфейсы периферийных устройств.

2. Принцип построения интерфейсов.

Обобщенная схема взаимодействия периферийного устройства и контроллера ввода-вывода.

Приемник-передатчик; контроллер ввода-вывода; дешифрация адреса; регистры управления, состояния и данных; адресное пространство ввода-вывода; функции контроллеров вводавывода (управление, буферизация данных, контроль ошибок).

3. Синхронизация при передаче данных.

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

взаимоблокирующее квитирование; стробирующий сигнал; синхронизация в последовательных Характеристика шины PCI.

Транзакции PCI. Мосты PCI. Параллельный интерфейс, мультиплексированная шина;

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

Шина USB. Структура и взаимодействие подсистем. Режимы передач данных.

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

Рекомендуемая литература:

1. Гук М. Аппаратные средства IBM PC. Энциклопедия. 3-е изд. Спб: Питер, 2006.

2. Авдеев В.А. Периферийные устройства: интерфейсы, схемотехника, программирование. М.: ДМКПресс, 2009.

3. Цилькер Б.Я., Орлов С.А. Организация ЭВМ и систем. Спб: Питер, 2007.

СД.07 Микропроцессорные системы 1. Архитектура микропроцессорных систем.

Фон-нейманская и гарвардская архитектуры, их достоинства и недостатки, сферы применения.

2. Система команд процессора.

Объем системы команд, деление на группы, связь набора команд и производительности 3. Классификация и структура микроконтроллеров.

Деление микроконтроллеров на интегрируемые, управляющие, универсальные, специальные.

Модульный принцип организации микроконтроллеров – ядро и изменяемый функциональный 4. Разработка цифровых устройств на микроконтроллерах.

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

5. Архитектура суперскалярных микропроцессоров.

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

Рекомендуемая литература:

1. Корнеев В.В., Киселев А.В. Современные микропроцессоры. - М.: Нолидж, 2. Новиков Ю.В., Скоробогатов П.К. Основы микропроцессорной техники. - М.: ИНТУИТ.РУ "Интернет-Университет Информационных технологий", 2003.

3. Микропроцессоры. Учеб для втузов / П.В.Нестеров, В.Ф.Шаньгин, В.Л.Горбунов и др.; под редакцией Л.Н.Преснухина. М.: Высш. шк., 1986.

4. Нарышкин А. К. Цифровые устройства и микропроцессоры : учеб. пособие для студентов вузов радиотехн. специальностей / А. К. Нарышкин. - М. : Академия, 2006. - 317с. - ISBN 5-7695-1618-6.

СД.08 Технологии программирования 1. Проектирование программного обеспечения при структурном подходе.

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

2. Проектирование программного обеспечения при объектном подходе.

Принципы объектного подхода. Язык UML: структурные диаграммы, диаграммы поведения, диаграммы взаимодействия.

3. Информационные структуры.

Линейные списки. Последовательное и связанное распределение. Циклические списки. Дерево и бинарное дерево. Обход бинарных деревьев. Прошитые бинарные деревья. Алгоритмы обхода, вставки и копирования прошитого бинарного дерева.

4. Процесс сортировки.

Основные принципы, предназначение и классификация. Внутренние и внешние сортировки.

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

Линейная конгруэнтная последовательность. Генератор Дж.Ж. Митчела и Д.Ф. Мура.

Алгоритм рандомизации перемешиванием. Критерии оценки качества генераторов Рекомендуемая литература:

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

2. Иванова Г.С. Технология программирования. М.: Изд-во МГТУ им. Н.Э. Баумана, 2002.

3. Кнут Д. Искусство программирования. Т.1: Основные алгоритмы. М.: Addison-Wesley, 2000.

4. Кнут Д. Искусство программирования. Т. 3. Сортировка и поиск. М.: Addison-Wesley, 2001.

5. Соммервил И. Инженерия программного обеспечения. М.: Вильямс, 2002.

ДС.01 Защита в операционных системах 1. Процессы и потоки в операционных системах. Адресное пространство процесса.

Защита адресного пространства.

Понятие процесса и потока. Процессы в ОС Windows и ОС Linux. Атрибуты процесса.

Адресное пространство процесса. Структура контекста процесса. Сегменты адресного пространства процесса. Права доступа к сегментам адресного пространства процесса.

Аппаратная поддержка разграничения адресного пространства.

2. Виды доступа к объектам в ОС Windows. Списки контроля доступа в ОС Windows (SACL, DACL).

Объекты ОС Windows. Права доступа к объектам: общие, специальные, стандартные.

Дескриптор безопасности объекта. SID пользователя. Списки контроля доступа к объектам (структура и алгоритм просмотра).

3. Разграничение доступа к файлам в ОС Linux.

Атрибуты файлов в ОС Linux. Inode файла. Права доступа для владельца группы владельца и остальных пользователей. Биты SUID и SGID. Расширенные атрибуты файлов.

4. Подсистема безопасности в ОС Windows.

Основные структуры данных подсистемы безопасности. Основные процессы подсистемы безопасности. Процесс lsass. Процесс Winlogon (назначение и состояния).

5. Аутентификация пользователей в ОС Windows и ОС Linux.

Процесс входа пользователя в систему в ОС Windows (ппроцесс Winlogon и модули аутентификации). Хранение паролей. Процесс входа пользователя в ОС Linux. Файл паролей.

Рекомендуемая литература:

1. Руссинович М., Соломон Д. Внутреннее устройство Microsoft Windows. СПб.: Питер, 2005. 992 с.

2. Манн С., Митчелл Э., Крелл М. Безопасность Linux. М.:Издательский дом «Вильямс», 2003. 624 с.

ДС.02 Вычислительные сети 1. Сетевая модель ISO/OSI.

Многоуровневый подход к построению сети. Понятие сетевого протокола. Инкапсуляция.

Уровни модели ISO/OSI и их функции. Стек протоколов TCP/IP. Сетевая модель TCP/IP и её Технология Ethernet.

Стандарт IEEE 802.3. Технология множественного доступа к среде с контролем несущей и обнаружением коллизий. Понятие физического адреса. Среды передачи данных Ethernet.

Принцип действия концентратора Ethernet. Принцип действия коммутатора Ethernet.

Технология FastEthernet. Полудуплексный и полнодуплексный режимы работы портов. ARPпротокол. Функции протокола. Примеры работы протокола. ARP-кэш.

Место протокола в модели OSI. Характеристики протокола IP. Формат заголовка IP. Функции протокола: адресация, фрагментация, маршрутизация. Адресация IP: классы IP-адресов, маски сети. Особенности адресации: широковещательные адреса, адреса сетей и адреса хостов.

Транспортный уровень стека TCP/IP.

Протоколы транспортного уровня TCP и UDP. Назначение протоколов. Понятие порта.

Форматы заголовков UDP и TCP. Флаги, управляющие соединением. Установление TCPсоединения. Передача данных в TCP. Завершение TCP-соединения.

5. Сетевые службы.

Служба DNS и ее функции. Понятие домена и зоны DNS. Рекурсивный и нерекурсивный поиск по DNS. Организация электронной почты в Internet. Функции транспортного агента и агента доставки. Протоколы SMTP, POP3 и IMAP4. Служба World Wide Web. URL и его структура.

Рекомендуемая литература:

1. Олифер В.Г., Олифер Н.А. Компьютерные сети. СПб.: Питер, 2002. – 672 с.

2. Храмцов П.Б. Лабиринт Internet. М.: Электроинформ, 1996. – 256 с.

3. Храмцов П.Б. Система доменных имен. URL: http://info.nic.ru/st/14/out_267.shtml.

4. Мамаев М. Организация электронной почты в Internet. URL: http://www.opennet.ru/docs/RUS/mail.

ДС.03 Коммутация и маршрутизация локальных сетей 1. Принципы маршрутизации.

Структура таблиц маршрутизации. Понятие метрики и административной дистанции.

Статическая и динамическая маршрутизацияю. Принцип работы маршрутизатора. Классовое и бесклассовое поведение маршрутизатора. Присоединенные сети. Настройка статических маршрутов на Ciscо IOS. Общая классификация протоколов маршрутизации. Дистанционновекторные протоколы и их принцип действия. Протоколы состояния канала связи и их принцип действия. Внешние и внутренние протоколы маршрутизации.

Протокол маршрутизации RIP.

Основные характеристики протокола. Метрика протокола маршрутизации. Версии протокола и их отличия. Примеры настроек на маршрутизаторе Cisco. Распространение статических маршрутов и маршрута по умолчанию в таблицах маршрутизации RIP.

Протокол маршрутизации OSPF.

Основные характеристики протокола. Метрика протокола OSPF. Понятие области и процесса маршрутизации. Примеры настроек на маршрутизаторе Cisco. Работа OSPF в сетях множественного доступа. Выбор назначенного и запасного назначенного маршрутизатора.

Протокол STP и его разновидности.

Проблемы коммутируемых сетей с избыточными путями: неоптимальность маршрутов и широковещательный шторм. Работа протокола STP (IEEE 802.1d). Формат BPDU кадра. Выбор корневого коммутатора. Выбор корневых портов, выбор назначенных портов. Состояния портов. Разновидности STP протокола: RSTP, PVST+, rapid- PVST+.

5. Виртуальные локальные сети VLAN.

Динамические и статические VLAN. Порты доступа и магистральные порты (транки). Внешняя и внутренняя инкапсуляция (ISL и IEEE 802.1q). Состояния транковых портов и протокол DTP.

Функции и назначение протокола VTP. Маршрутизация между VLAN. Внутренняя и внешняя маршрутизация между VLAN их достоинства и недоставтки. Традиционная маршрутизация между VLAN. Движение трафика при традиционной настройке. Маршрутизация Router-onStick. Движение трафика при конфигурации Router-on-Stick. Типовая настройка Материалы для подготовки*:

1. CCNA Discovery 4.0 (I): Сети для домашних пользователей и малых предприятий. URL:

http://192.168.2.40/cisco/CCNA_Exploration/Discovery1/index.html 2. CCNA Discovery 4.0 (II): Работа на малых предприятиях и у Интернет-провайдеров.

URL: http://192.168.2.40/cisco/CCNA_Exploration/Discovery2/index.html 3. CCNA Discovery 4.0 (III): Введение в маршрутизацию и коммутацию на предприятии.

URL: http://192.168.2.40/cisco/CCNA_Exploration/Discovery3/index.html 4. CCNA Discovery 4.0 (IV): Проектирование и поддержка компьютерных сетей.

URL: http://192.168.2.40/cisco/CCNA_Exploration/Discovery4/index.html 5. Лавров Д.Н. Сети и системы телекоммуникаций. Учебное пособие. Омск.: из-во ОмГУ, 2006. 183 с. URL: \\192.168.2.40\Teachers\Lavrov\_Cisco_1_2_КиМ\Lectures\Сети и системы 6. ARP-spoofing. URL: http://xgu.ru/wiki/ARP-spoofing.

* - URL указан для внутренней сети факультета компьютерных наук ОмГУ. К материалам курса CCNA Exploration 4 и CCNA Discovery 4 можно получить доступ через http://cisco.netacad.net.

ДС.04 Удаленный доступ и компьютерные сети 1. Протокол PPP.

Основные функциональные возможности и характеристики, назначение протокола. Формат кадра PPP. Структура набора протоколов PPP: LCP и NCP. Процедуры установления и завершения соединения. Аутентификация PAP и CHAP: описание протоколов и сравнительный анализ безопасности протоколов.

2. Списки управления доступом ACL.

Стандартные, расширенные и именованные списки доступа. Принципы работы списка управления доступом. Создание ACL на маршрутизаторе Cisco. Назначение списков доступа на интерфейсы и подключения к виртуальному терминалу. Размещение списков доступа.

Расширенные возможности списков доступа: управление правилами по времени; динамические списки доступа, рефлексивные списки; списки, управляемые по содержимому (CBAC).

3. Технология NAT.

Терминология NAT: внутренние локальные, внутренние глобальные, внешние глобальные адреса, внешние локальные адреса. Типы NAT: Source NAT, Distribute NAT. Статический и динамический NAT. Перегрузка NAT (Port Address Translation). Достоинства и недостатки NAT. Примеры настройки NAT на маршрутизаторе.

4. Протокол DHCP.

Формат сообщения DHCP. Работа DHCP. Настройка протокола DHCP на маршрутизаторе.

Работа в DHCP в маршрутизируемой сети (DHCP Relay).

Материалы для подготовки*:

1. CCNA Discovery 4.0 (I): Сети для домашних пользователей и малых предприятий. URL:

http://192.168.2.40/cisco/CCNA_Exploration/Discovery1/index.html 2. CCNA Discovery 4.0 (II): Работа на малых предприятиях и у Интернет-провайдеров.

URL: http://192.168.2.40/cisco/CCNA_Exploration/Discovery2/index.html 3. CCNA Discovery 4.0 (III): Введение в маршрутизацию и коммутацию на предприятии.

URL: http://192.168.2.40/cisco/CCNA_Exploration/Discovery3/index.html 4. CCNA Discovery 4.0 (IV): Проектирование и поддержка компьютерных сетей.

URL: http://192.168.2.40/cisco/CCNA_Exploration/Discovery4/index.html 5. Лавров Д.Н. Сети и системы телекоммуникаций. Учебное пособие. Омск.: из-во ОмГУ, 2006. 183 с. URL: \\192.168.2.40\Teachers\Lavrov\_Cisco_1_2_КиМ\Lectures\Сети и системы 6. ARP-spoofing. URL: http://xgu.ru/wiki/ARP-spoofing.

* - URL указан для внутренней сети факультета компьютерных наук ОмГУ. К материалам курса CCNA Exploration 4 и CCNA Discovery 4 можно получить доступ через http://cisco.netacad.net.