Утверждаю
Декан ФИВТ
" 20" января 2009 г.
ПРОГРАММА
государственного итогового междисциплинарного экзамена по специальности 230105.65
"Программное обеспечение вычислительной техники
"СТРУКТУРЫ И ОРГАНИЗАЦИЯ ДАННЫХ В ЭВМ"
1. Линейные списки. Стеки и очеpеди.
2. Деpевья и способы их оpганизации в памяти. Рекуpсивные алгоpитмы обхода бинарных деpевьев.
3. Представления графов с помощью матрицы смежности и списковых структур.
4. Бинаpные деpевья поиска и их коppектиpовка.
5. АВЛ-деpевья и их балансиpовка.
6. Хеширование.
7. Быстрая сортировка Хоара.
8. Методы внешней сортировки.
"ОРГАНИЗАЦИЯ И ФУНКЦИОНИРОВАНИЯ АППАРАТНЫХ
И ПРОГРАММНЫХ СРЕДСТВ ЭВМ "
1. Центральный процессор. Назначение и структура. Архитектура процессоров фирмы INTEL на ассемблерном уровне.
2. Управление вводом-выводом. Основные понятия. Шинный и канальный ввод-вывод. Ввод-вывод в персональных ЭВМ
3. Понятие о прерывании процесса. Система прерываний и обработка прерываний. Причины прерываний, приоритет в прерывании.
4. Память ЭВМ. Иерархическая структура памяти. Виды памяти и их особенности. Внешние запоминающие устройства.
5. Принцип программного управления фон Неймана. Достоинства и недостатки.
6. Организация защиты памяти в ЭВМ.
7. Таймер в IBM PC. Назначение, состав и программирование.
8. Контроллер прерываний в IBM PC. Назначение, состав и программирование.
ВОПРОСЫ ГОСЭКЗАМЕНА
по дисциплине "Базы данных"
1. Реляционная модель данных. Операции реляционной алгебры.
2. Нормализация отношений. Первая, вторая и третья нормальные формы.
3. Семантическое моделирование данных. ER-диаграммы.
4. Оператор SELECT языка SQL. Запросы на чтение из одной таблицы. Виды условий поиска.
5. Многотабличные запросы SQL. Внутренние соединения.
Псевдонимы. Внешнее соединение таблиц в SQL.
6. Запросы с группировкой и вложенные запросы в SQL.
7. Целостность данных. Транзакции.
8. Представления и работа с ними. Триггеры и хранимые процедуры.
"Технология разработки программного обеспечения"
1. Технология программирования. Система разработки ПО.
2. Процесс разработки программного обеспечения
3. Проектирование, как составляющая Система разработки ПО
4. Основные технологии разработки ПО
5. Модели жизненного цикла.
6. Качество программной системы. Модель характеристик качества. Характеристики качества ПО.
7. Сравнение технологий разработки ПО.
8. Уровень формализма. Количество итераций.
9. Требования. АНАЛИЗ ТРЕБОВАНИЙ
10. Управление проектом. Этапы. Задачи. Треугольник проекта.
11. Риски. Управление рисками.
12. Разработка пользовательских интерфейсов компьютерных программ.
13. Технология SADT. Системы и модели. Пример.
14. Информационно-потоковая технология проектирования. Область применения? Пример.
15. Экстремальное программирование.
16. RUP.
17. Документирование проекта.
18. Индивидуальный процесс разработки программного обеспечения (PSP). Оценка.
19. Командный процесс разработки программного обеспечения (TSP). Оценка.
20. Основы структурных методов проектирования
21. Стиль руководства. Психология программирования
22. UML. Назначение.
23. UML. Диаграмма вариантов использования (прецедентов) (use case diagram). Назначение. Пример использования.
24. UML. Диаграмма классов (class diagram). Пример использования.
25. UML. Диаграммы поведения (behavior diagrams) . Назначение. Пример использования.
26. UML. Диаграмма состояний (statechart diagram) . Назначение. Пример использования.
27. -UML. Диаграмма активности (activity diagram) . Назначение. Пример использования.
28. UML. Диаграммы взаимодействия (interaction diagrams) . Назначение. Пример использования.
29. UML. Диаграмма последовательности (sequence diagram) . Назначение. Пример использования.
30. UML. Диаграмма кооперации (collaboration diagram) . Назначение. Пример использования.
31. UML. Диаграммы реализации (implementation diagrams) . Назначение. Пример использования.
32. UML. Диаграмма компонентов (component diagram) . Назначение. Пример использования.
33. UML. Диаграмма размещения(развертывания) (deployment diagram) . Назначение. Пример использования.
34. Управление проектами. Сущность управления проектами.
35. Управление проектами. Этапы структурного руководства проектом. Индикатор вероятности успеха (psi).
36. Принципы тестирования. Философия тестирования.
37. Отладка. Основные методы отладки.
38. CASE-системы. Назначение, классификация.
39. Архитектура программы. Цели выбора архитектуры. Декомпозиция.
40. Классификация архитектур.
41. Архитектуры, основанные на потоках данных
42. Архитектура. Независимые компоненты.
43. Виртуальные машины.
44. Репозиторные архитектуры.
45. Уровневые архитектуры.
46. Модели, каркасы, образцы проектирования, компоненты.
47. Сопровождение ПО.
Сети ЭВМ и телекоммуникации
1. Назовите и охарактеризуйте уровни управления ИВС по эталонной модели ВОС. Назовите сетевые устройства и ПО, работающие на этих уровнях.
2. Адресация в протоколах TCP/IP для сети Internet. Протокол ARP. Схемы рекурсивного и нерекурсивного режимов работы DNS-серверов.
3. Реализация случайных методов доступа к моноканалу в ЛВС (МДКН и МДКН/ОК). Каким образом на основе МДКН/ОК мосты и маршрутизаторы имеют преимущество для доступа к моноканалу по сравнению с другими узлами сети?
4. Объясните фазы работы протокола УЛК с установлением и без установления логического соединения. Ответ дополните диаграммой. Как для таких сетей отслеживается потеря передаваемых кадров?
5. Назовите принципы формирования протокольных блоков данных в рамках протоколов ЛВС. Инкапсуляция и декапсуляция сообщений. Принципы передачи команд между смежными протоколами одного узла сети и одинаковыми протоколами двух взаимодействующих узлов.
6. Зарисуйте структуру и назовите основные функциональные отличия повторителей, трансиверов и концентраторов ЛВС. На каком уровне эталонной модели ВОС функционирует каждое из этих устройств?
7. Реализация маркерного метода доступа к моноканалу в ЛВС с кольцевой топологией. Особенности организации сети Token Ring на переключающих концентраторах.
8. Объясните основные отличия в методе доступа для таких локальных сетей, как Token Ring и FDDI. Чем вызваны эти отличия. Синхронный и асинхронный режимы работы сети FDDI. Каким образом в сети FDDI определяется обрыв кабеля или отказ станции?
9. Основные функции транспортных и сетевых протоколов ИВС на примере протоколов TCP и IP. Взаимосвязь этих протоколов с другими протоколами ЭМ ВОС. Стратегии управления потоком данных.
10. Объясните понятие “окно конфликтов”. Как в сети Ethernet определяется эта величина и на что она влияет? Как в сети Ethernet на витой паре проводов уменьшить окно конфликтов?
" СИСТЕМHЫЙ АHАЛИЗ ".
1. Сущность системного анализа.
2. Стадия развития технических систем.
3. Виды подобия моделей.
4. Модель "черного ящика".
5. Модель состава системы.
6. Модель отношений системы.
7. Моделирование систем на уровне физических эффектов.
8. Графические модели технических систем.
9. Функциональная аналогия.
10. Структурная аналогия.
11. Аналогия отношений.
12. Дерево технических решений.
13. Порядок проведения предметного патентного поиска.
"Теория языков программирования и методы трансляции"
1. Трансляция. Интерпретация и компиляция. Общие синтаксические критерии. Стадии трансляции.
2. Грамматики и автоматы. Классификация Хомского.
3. Практические ограничения, налагаемые на грамматики.
4. Отношения применимые к грамматикам
5. Синтаксический анализ. Синтаксические деревья. Задача разбора. Однозначность разбора.
6. Канонический разбор Основа. Разбор сверху вниз, снизу вверх.
7. Сканер. Принципы построения.
8. Синтаксический анализ. Нисходящий разбор, рекурсивный спуск.
9. Проблемы нисходящего разбора.
10. LL(K)-грамматики. Направляющие символы. Идея разбора.
11. Построение LL(1)таблицы разбора.
12. Разбор по LL(1)таблице.
13. Проблемы LL(1)-разбора. Достоинство и недостатки метода.
14. Восходящий разбор. Проблемы. Общий метод разбора.
15. LR(K)-грамматики. Идея разбора.
16. Построение LR(0)таблицы разбора.
17. Построение SLR таблицы разбора.
18. Разбор по LR(1)таблице.
19. Включение действий в синтаксис. Транслирующие грамматики.
20. Атрибутивные грамматики. Синтезируемый и наследуемый атрибуты.
21. Таблица символов. Назначение, структура.
22. Распределение памяти. Статическая и динамическая память
23. Распределение памяти. Адреса времени компиляции.
24. Организация памяти во время выполнения. Области данных при статическом и динамическом распределении памяти.
25. Генерация кода.
26. Генерация кода на примере одного из операторов Паскаля.
27. Свойства КС-грамматик. Лемма подкачки.
28. Автоматы с магазинной помятью.
"ФУНКЦИОНАЛЬНОЕ И ЛОГИЧЕСКОЕ ПРОГРАММИРОВАНИЕ"
1. Рекурсия и циклы в Лиспе.
2. Внутреннее представление списков в Лиспе.
3. Декларативная и процедурная семантика Пролог-программ.
4. Отсечение. Графическая иллюстрация действия cut. Формальное описание действия отсечения.
5. Сравнительная характеристика функционального, логического и процедурного подхода к программированию.
"Объектно-ориентированное программирование"
1. Определение класса в языке С++. Функции-члены класса в языке С++. Друзья класса в языке С++. Область видимости класса в языке С++. Инициализация класса в языке С++.
2. Наследование в языке С++.
3. Виртуальные функции в языке С++.
4. Полиморфизм. На примере С++.
5. Инкапсуляция. На примере С++.
Методы и средства защиты информации
1. Системотехнические основы построения датчиков случайных чисел. Принципы аналого-цифрового преобразования. Причины выбора данного принципа аналого-цифрового преобразования.
2. Понятие Фон Нэймановской архитектуры вычислительной системы. Базовые принципы. Проблема получения случайных чисел в рамках данной архитектуры. Основной вывод.
3. Системы гарантированной секретности. Теоретические основы.
4. Длиннопериодические ключевые последовательности. Датчики псевдослучайных чисел и их роль для создания длиннопериодических ключевых последовательностей. Анализ стойкости длиннопериодических ключевых последовательностей.
5. Простейшие протоколы обеспечения многократной электронной цифровой подписи. Пример применения.
6. Модель угроз «Несанкционированный доступ к передаваемой через открытый канал информации». Криптографические методы противодействия данной угрозе.
7. Модель угроз «Искажение передаваемой в открытом канале информации». Криптографические методы противодействия данной угрозе. Классификация методов. Пример.
8. Модели угроз «Нарушение целостности программного обеспечения внутри периметра защиты». Формализация. Субъектно-объектный подход.
9. Теорема о неразрешимости множества доверенных субъектов в вычислительной системе Фон Нэймановской архитектуры. Связь с одним из базовых принципов Фон Нэймановской архитектуры. Понятие доверенной аппаратной компоненты.
10. Примеры аппаратных решений для создания изолированных программных сред.
"ОПЕРАЦИОHHЫЕ СИСТЕМЫ".
1. Классификация ОС
2. Структура сетевой ОС.
3. Управление процессами. Понятие процесса. Дескриптор и контекст процесса. Алгоритмы планирования процессов. Вытесняющая и не вытесняющая многозадачность.
4. Средства синхронизации взаимодействия процессов. Блокирующие переменные, семафоры.
5. Взаимные блокировки процессов. Тупики распознавание, рекомендации как избежать тупик, выход из тупика.
6. Проблемы взаимодействия процессов. Основные задачи, возникающие при взаимодействии процессов.
7. Нити и процессы.
8. Управление памятью. Типы адресов. Обзор методов распределения памяти.
9. Методы управления памятью без использования внешней памяти
10. Оверлеи. Виртуальная память. Способы организации виртуальной памяти
11. Свопинг и кэширование
12. ОС. Управление вводом/выводом
13. Файловая система. Основные функции. Общая схема.
14. Логическая и физическая организация файлов. Права доступа к файлу. Кэширование файла. Отображение файла в оперативную память. Проблемы совместного использования.
"ТЕОРИЯ ВЫЧИСЛИТЕЛЬHЫХ ПРОЦЕССОВ И СТРУКТУР"
1. Операции над формальными языками.
2. Двоичное кодирование переменных и функций трехзначной логики.
3. Перечислить способы представления конечного автомата.
5. Определение недетерминированного и конечного автомата.
6. Программная реализация логических функций.
"АРХИТЕКТУРА ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМ"
1. Виды систем обработки данных. Режимы обработки данных. Сформулируйте различия между многомашинными вычислительными комплексами и вычислительными сетями.
2. Уровни комплексирования устройств в вычислительных системах. Постройте структурную схему ПЭВМ, состоящей из двух процессоров. Покажите на ней используемые уровни комплексирования. Ответ поясните.
3. Методы улучшения ОКОД структуры. Степень, уровни и виды параллелизма. Какой из видов параллелизма реализуется в современных универсальных процессорах (например, в процессоре Pentium)? Ответ обоснуйте.
4. Подсистема памяти. Методы повышения быстродействия памяти. Виды ЗУ. Иерархическая организация памяти. Какие вычислительные системы, на каком уровне иерархической организации памяти требуют организации пакетного доступа к памяти. Ответ поясните.
5. Организация кэш-памяти. Зарисуйте структуру памяти (ОЗУ и кэш) для секторированного наборно-ассоциативного кэша, состоящего из трех банков. Поясните ее.
6. Операционный и командный конвейер. Необходимые условия организации конвейеров этих типов. Режимы работы конвейеров. Объясните, почему при организации конвейера команд не целесообразно использовать Принстонскую архитектуру ЭВМ?
7. Многопроцессорные вычислительные комплексы (МПВК). Типы структур. Проблемы организации. Способы распределения ресурсов в МПВК. Сравните типы структур МПВК по следующим критериям: а) быстродействию; в) аппаратным затратам на систему коммутации; г) надежности.
8. Машины, управляемые потоком данных. Недостатки принципа управления потоком данных. Граф потока данных. Типы вершин графа потока данных. Можно ли использовать принцип управления потоком данных в конвейерных вычислительных системах? Ответ обоснуйте.
