Вопросы к экзамену по курсу
«Архитектура и программное обеспечение вычислительных систем и сетей»
Математические основы
1. Отношения. Свойства отношений. Отношения эквивалентности и частичного порядка. Функции и отображения. Виды функций.
2. Понятие универсальной алгебры. Свойства бинарных операций. Гомоморфизм и изоморфизм. Типы универсальных алгебр.
3. Графы, основные понятия. Представление графов. Виды графов. Виды частей графов. Маршруты и циклы. Некоторые специальные виды циклов. Связность. Расстояние. Планарные графы.
4. Деревья, основные понятия и свойства. Цикломатическое число графа. Орграфы, основные понятия. Связность и достижимость.
5. Алгоритмы и их основные свойства. Машины Тьюринга: формальное определение, программа, конфигурация. Функция, вычислимая на машине Тьюринга. Тезис Тьюринга. Другие модели алгоритмов.
6. Вычислимые функции. Примитивно-рекурсивные функции. Примитивно-рекурсивные операторы. Операторы минимизации. ЧРФ и ОРФ. Соотношение множеств ПРФ, ЧРФ и ОРФ. Тезис Черча. Теорема Черча-Тьюринга. Геделизация.
7. Алгоритмическая неразрешимость. Нумерация алгоритмов. Алгоритмически неразрешимые проблемы. Самоприменимость. Разрешимые множества. Теорема Райса и ее интерпретации.
8. Сложность задачи и алгоритма. Асимптотические оценки сложности. Временная и пространственная сложность. Сложность в лучшем, в худшем, в среднем.
9. Сложностные классы P и NP. P-NP проблема. Полиномиальная сводимость. NP-полные и NP-трудные задачи. Некоторые свойства задач из класса NPC. Доказательство принадлежности классу NPC. Способы решения задач из NP.
10. Некоторые алгоритмы поиска и сортировки: AVL-деревья, B-деревья, сортировка с помощью кучи (пиримидальная). Хэширование. Коллизии и способы их разрешения.
11. Алгоритмы перебора на графах в ширину и глубину. Альфа-бета отсечение. Алгоритм Дейкстры. Другие алгоритмы на графах.
Основы Hardware
12. Архитектура вычислительной системы. Свойства архитектуры фон Неймана. Машинный цикл. Регистры процессора и их классификация. Характеристики и архитектура процессора.
13. Прерывания: типы, источники, этапы обработки. Конвейер: этапы, способы реализации, предсказание переходов.
14. Системные ресурсы, способы уничтожения конфликтов. Память: иерархия, параметры и закономерности, классификация. Кэш-память: понятие, структура и стратегии отображения. Виртуальная машина.
15. Модули ввода-вывода: функции, виды, структура, мультиплексирование, plug-and-play. Устройство управления. Микропрограммы и микрооперации.
16. Компьютеры c архитектурой Intel. Материнская плата, чипсеты, хабы. Системная шина: типы линий, синхронизация, арбитраж. Особенности основных шин (PCI, AGP и т.д.).
17. История развития процессоров Intel (особенности каждой модели), поколения процессоров. Процессор Рentium IV, концепция NetBurst.
18. Классификации вычислительных комплексов: по аппаратным решениям, по степени параллельности потоков команд и данных, по типу памяти, по степени централизации, по архитектуре набора команд. Системы RISC: особенности, история, свойства, основные процессоры.
19. Системы SMP: свойства, классификация, обеспечение целостности кэшей. Кластеры. Системы NUMA. Векторные вычисления. Технологии распределенной обработки данных.
Операционные системы
20. Понятие программного обеспечения. Многоуровневая классификация ПО (системное ПО, инструментарий технологии программирования, пакеты прикладных программ). Основные разновидности ППП.
21. Операционные системы: понятие, функции, принципы разработки. Классификация ОС (5 направлений). Характеристика поколений ОС.
22. Процессы: определение, отличие от программы, образ процесса, ресурсы. Состояния процессов и схема их связей. Действия при создании и переключении процессов. Блок управления процессом (РСВ). Разделение времени. Потоки: отличия от процесса, достоинства.
23. Параллельные процессы. Критические ресурсы и секции. Проблемы параллельных процессов - взаимоисключения, взаимоблокировки, голодания. Шесть требований к взаимоисключениям. Программный и аппаратный подходы к обработке взаимоисключений. Семафоры, мониторы Хоара, сообщения.
24. Взаимоблокировки (тупики). Виды ресурсов. Модель Холта. Четыре условия возникновения тупиков. Способы борьбы с тупиками: игнорирование, предотвращение, обход и обнаружение. Действия при обнаружении тупика.
25. Планирование в ОС и его виды. Критерии и параметры планирования. Бесприоритетные и приоритетные способы планирования.
26. Оперативная память: организация, адресация. Виды памяти: по носителю, по технологии, по конструкции. Корректирующие коды, контроль четности. Требования к управлению памятью. Виды распределения памяти, их плюсы и минусы.
27. Страничная организация памяти. Сегментная организация. Виртуальная память, способы ее организации, процесс обработки. Стратегии управления памятью: стратегии выборки, замещения, управления резидентным множеством, очистки и загрузки.
28. Задачи управления вводом-выводом. Некоторые устройства ввода-вывода (порты COM, LPT, видеоадаптер). Четыре способа управления вводом-выводом. Эволюция модулей ввода-вывода. Процесс ввода-вывода. Буферизация при вводе-выводе, типы буферов. Кэширование при вводе-выводе.
29. Задачи управления файлами. Файл и его компоненты. Характеристика устройств внешней памяти: HDD, CD, FDD. Способы организации файлов. Права доступа. Способы размещения файлов. Способы выбора свободных блоков и управления свободным пространством.
30. ОС Unix: основные особенности, история развития. Ядро и оболочка Unix. Особенности управления процессами, памятью, вводом–выводом и памятью в ОС Unix. Особенности некоторых ОС: Solaris, Linux, OS/2, QNX.
31. История развития ОС Windows (основные особенности разных версий). Особенности Windows 7. API Windows. Реестр Windows. Объекты Windows. Архитектура Windows. Особенности управления процессами, памятью, вводом–выводом и памятью в ОС Windows.