metoda_2013
.pdfПОВОЛЖСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНОЛОГИЧЕСКИЙ УНИВЕРСИТЕТ
Методическое пособие для студентов специальности 230105
Эффективная подготовка к государственным междисциплинарным экзаменам для студентов технических специальностей
ПРЕДИСЛОВИЕ
Уважаемый читатель, мы представляем вашему вниманию очередной релиз Методического пособия для студентов специальности 230105 «Программное обеспечение вычислительной техники и автоматизированных систем», которое дает вам неограниченные возможности в процессе сдачи междисциплинарного экзамена.
В этом релизе собраны лучшие лекции, шпаргалки, конспекты наших студентов. Мы постарались как можно лучше проанализировать всю имеющуюся информацию и довести ее до вас в наиболее удобном для усвоения виде.
Особую благодарность хотим выразить всем, кто помог создать, собрать, а самое главное переработать информацию, помещенную в данном пособии.
2013 г. специальность ПС.
Оглавление |
|
I. СТРУКТУРЫ И ОРГАНИЗАЦИЯ ДАННЫХ В ЭВМ. |
11 |
1. Линейные списки. Стеки и очереди |
11 |
2. Деревья и способы их организации в памяти. |
|
Рекурсивные алгоритмы обхода бинарных деревьев. |
16 |
3.Представления графов с помощью матрицы
|
смежности и списковых структур |
18 |
4. |
Бинаpные деpевья поиска и их коppектиpовка |
19 |
5. |
АВЛ-деpевья и их балансиpовка |
21 |
6. |
Хеширование |
22 |
7. |
Быстрая сортировка Хоара |
26 |
8. |
Методы внешней сортировки |
28 |
II. |
БАЗЫ ДАННЫХ. |
31 |
1. |
Реляционная модель данных. Операции реляционной |
|
|
алгебры. |
31 |
2. |
Нормализация отношений. Первая, вторая и третья |
|
|
нормальная формы. |
36 |
3.Семантическое моделирование данных. ER-
диаграммы. |
40 |
4. Оператор SELECT языка SQL. Запросы на чтение из |
|
одной таблицы. Виды условий поиска. |
44 |
5.Многотабличные запросы SQL. Внутренние
|
соединения. |
|
|
48 |
6. |
Псевдонимы. Внешнее соединение таблиц в SQL. |
52 |
||
7. |
Запросы с группировкой и вложенные запросы в SQL. |
52 |
||
8. Целостность данных. Транзакции. |
|
54 |
||
9. Представления |
и работа с |
ними. Триггеры и |
|
|
|
хранимые процедуры. |
|
58 |
|
III. ТЕХНОЛОГИЯ |
РАЗРАБОТКИ |
ПРОГРАММНОГО |
|
|
|
ОБЕСПЕЧЕНИЯ. |
|
|
61 |
1. |
Технология программирования. Система разработки |
|
||
|
ПО. |
|
|
61 |
2. |
Процесс разработки программного обеспечения |
64 |
||
|
|
2 |
|
|
3.Проектирование, как составляющая Система
|
разработки ПО |
66 |
4. |
Основные технологии разработки ПО |
69 |
5. |
Модели жизненного цикла (ЖЦ). |
72 |
6.Качество программной системы. Модель
|
характеристик качества. Характеристики качества ПО |
77 |
7 Сравнение технологий разработки ПО |
81 |
|
8. |
Уровень формализма. Количество итерации |
84 |
9. |
Требования. Анализ требований. |
87 |
10. Управление проектом. Этапы. Задачи. Треугольник |
|
|
|
проекта. |
91 |
11. Риски. Управление рисками. |
94 |
|
12. Технология SADT. Системы и модели. Пример. |
98 |
13.Информационно-потоковая технология
|
проектирования. Область применения? Пример. |
101 |
||||
14. Экстремальное программирование. |
|
|
103 |
|||
15. RUP |
|
|
|
|
108 |
|
16. Документирование проекта |
|
|
|
111 |
||
17. Индивидуальный процесс разработки программного |
|
|||||
|
обеспечения (PSP). Оценка. |
|
|
|
115 |
|
18. Командный процесс разработки |
программного |
|
||||
|
обеспечения (TSP). Оценка. |
|
|
|
118 |
|
19. Основы структурных методов проектирования |
119 |
|||||
20. UML. Назначение |
|
|
|
|
121 |
|
21. |
UML.Диаграмма |
вариантов |
использования |
|
||
|
(прецедентов) (use case diagram). Назначение. |
|
||||
|
Пример использования. UML.Диаграмма классов |
|
||||
|
(class diagram). Пример использования. |
|
124 |
|||
22. UML.Диаграммы |
поведения |
(behavior |
diagrams). |
|
||
|
Назначение. Пример использования. |
|
|
127 |
||
23. UML. Диаграмма |
состояний (statechart diagram). |
|
||||
|
Назначение. Пример использования. |
|
|
130 |
||
24. UML.Диаграмма |
активности |
(activity |
diagram) . |
|
||
|
Назначение. Пример использования. |
|
|
134 |
||
|
|
3 |
|
|
|
|
25. UML. Диаграммы взаимодействия (interaction |
|
diagrams) . Назначение. Пример использования. |
135 |
26. UML. Диаграмма последовательности (sequence |
|
diagram) . Назначение. Пример использования. |
137 |
27. UML. Диаграмма кооперации (collaboration diagram) . |
|
Назначение. Пример использования. |
140 |
28.UML. Диаграммы реализации (implementation
|
diagrams) . Назначение. Пример использования. |
142 |
|||||
29. UML. Диаграмма компонентов (component diagram). |
|
||||||
|
Назначение. Пример использования. |
|
146 |
||||
30. |
|
UML.Диаграмма |
размещения(развертывания) |
|
|||
|
(deployment diagram) . Назначение. Пример |
|
|||||
|
использования. |
|
|
|
|
150 |
|
31. |
Управление |
проектами. |
Сущность |
управления |
|
||
|
проектами. |
|
|
|
|
153 |
|
32. |
Управление |
проектами. |
Этапы |
структурного |
|
||
|
руководства проектом. Индикатор вероятности успеха |
|
|||||
|
(psi). |
|
|
|
|
153 |
|
33. Управление проектом. Этапы. Задачи. Треугольник |
|
||||||
|
проекта. |
|
|
|
|
157 |
|
34. Принципы тестирования. Философия тестирования. |
161 |
||||||
35. Уровни тестирования. Этапы тестирования. |
164 |
||||||
36. Метрики проекта. |
|
|
|
171 |
|||
37. Отладка. Основные методы отладки. |
|
174 |
|||||
38. Архитектура программы. Цели выбора архитектуры. |
|
||||||
|
Декомпозиция. |
|
|
|
|
174 |
|
39. Сопровождение ПО. |
|
|
|
174 |
|||
IV. СЕТИ ЭВМ И ТЕЛЕКОММУНИКАЦИИ |
|
184 |
|||||
1. Назовите и охарактеризуйте уровни управления ИВС |
|
||||||
|
по эталонной модели ВОС. Назовите сетевые |
|
|||||
|
устройства и ПО, работающие на этих уровнях. |
184 |
2.Адресация в протоколах TCP/IP для сети Internet. Протокол ARP. Схемы рекурсивного и нерекурсивного
режимов работы DNS-серверов. |
187 |
3.Реализация случайных методов доступа к моноканалу
вЛВС (МДКН и МДКН/ОК). Каким образом на основе
4
МДКН/ОК мосты и маршрутизаторы имеют |
|
преимущество для доступа к моноканалу по |
|
сравнению с другими узлами сети? |
191 |
4. Объясните фазы работы протокола УЛК с |
|
установлением и без установления логического |
|
соединения. Ответ дополните диаграммой. Как для |
|
таких сетей отслеживается потеря передаваемых |
|
кадров? |
194 |
5. Назовите принципы формирования протокольных |
|
блоков данных в рамках протоколов ЛВС. |
|
Инкапсуляция и декапсуляция сообщений. Принципы |
|
передачи команд между смежными протоколами |
|
одного узла сети и одинаковыми протоколами двух |
|
взаимодействующих узлов. |
197 |
6. Зарисуйте структуру и назовите основные |
|
функциональные отличия повторителей, трансиверов |
|
и концентраторов ЛВС. На каком уровне эталонной |
|
модели ВОС функционирует каждое из этих |
|
устройств? |
200 |
7.Реализация маркерного метода доступа к моноканалу
вЛВС с кольцевой топологией. Особенности
организации сети Token Ring на переключающих |
|
концентраторах. |
203 |
8.Объясните основные отличия в методе доступа для таких локальных сетей, как Token Ring и FDDI. Чем
вызваны эти отличия. Синхронный и асинхронный |
|
режимы работы сети FDDI. Каким образом в сети |
|
FDDI определяется обрыв кабеля или отказ станции? |
207 |
9. Основные функции транспортных и сетевых |
|
протоколов ИВС на примере протоколов TCP и IP. |
|
Взаимосвязь этих протоколов с другими протоколами |
|
ЭМ ВОС. Стратегии управления потоком данных. |
208 |
10. Объясните понятие “окно конфликтов”. Как в сети |
|
Ethernet определяется эта величина и на что она |
|
влияет? Как в сети Ethernet на витой паре проводов |
|
уменьшить окно конфликтов? |
211 |
V. ТЕОРИЯ ЯЗЫКОВ ПРОГРАММИРОВАНИЯ И МЕТОДЫ |
|
ТРАНСЛЯЦИИ |
213 |
1. Трансляция. Интерпретация и компиляция. Общие |
|
синтаксические критерии. Стадии трансляции. |
213 |
5 |
|
2. Грамматики и автоматы. Классификация Хомского |
217 |
3.Практические ограничения, налагаемые на
|
грамматики. Отношения применимые к грамматикам. |
221 |
|||
4. |
Синтаксический анализ. Синтаксические деревья. |
|
|||
|
Задача |
разбора. |
Однозначность |
разбора. |
|
|
Канонический разбор. Основа. Разбор сверху вниз, |
|
|||
|
снизу вверх. |
|
|
227 |
|
5. |
Сканер. Принципы построения. |
|
235 |
6.Синтаксический анализ. Нисходящий разбор,
|
рекурсивный спуск. Проблемы нисходящего разбора. |
238 |
7. |
LL(K)-грамматики. Направляющие символы. Идея |
|
|
разбора. |
242 |
8. |
Построение LL(1)таблицы разбора.Разбор по |
|
|
LL(1)таблице.Проблемы LL(1)-разбора. Достоинство и |
|
|
недостатки метода. |
244 |
9.Восходящий разбор. Проблемы. Общий метод
разбора.LR(K)-грамматики. Идея разбора. |
249 |
10. Построение таблиц разбора(LR(0), SLR(1),LALR(1)). |
258 |
11. Разбор по LR(1)таблице |
265 |
12. Включение действий в синтаксис. Транслирующие |
|
грамматики. |
269 |
13.Атрибутивные грамматики. Синтезируемый и
наследуемый атрибуты. |
275 |
14.Таблица символов. Назначение, структура. |
280 |
15. Распределение памяти. Статическая и динамическая |
|
память. |
286 |
16.Распределение памяти. Адреса времени
|
компиляции. |
|
|
|
290 |
|
17. |
Организация памяти во время выполнения. Области |
|
||||
|
данных |
при |
статическом |
и |
динамическом |
|
|
распределении памяти. |
|
|
295 |
||
18. |
Генерация кода. Генерация кода на примере одного |
|
||||
|
из операторов Паскаля. |
|
|
298 |
||
19.Свойства КС-грамматик. Лемма подкачки. |
306 |
|||||
20.Автоматы с магазинной памятью. |
|
|
307 |
|||
|
|
|
6 |
|
|
|
VI. ФУНКЦИОНАЛЬНОЕ |
И |
ЛОГИЧЕСКОЕ |
|||
ПРОГРАММИРОВАНИЕ |
|
311 |
|||
1. |
Рекурсия и циклы в Лиспе |
|
311 |
||
2. |
Внутpеннее пpедставление списков в Лиспе |
315 |
|||
3. |
Декларативная и процедурная семантика Пролог- |
||||
|
программ |
|
|
|
317 |
4. |
Отсечение. Графическая иллюстрация действия cut. |
||||
|
Формальное описание действия отсечения |
320 |
|||
5. |
Сравнительная |
|
характеристика |
функционального, |
|
|
логического |
и |
процедурного |
подхода |
к |
|
программированию. |
|
323 |
||
VII. ОБЪЕКТНО-ОРИЕНТИРОВАННОЕ |
|
|
|||
ПРОГРАММИРОВАНИЕ |
|
328 |
1.Определение класса в языке С++. Функции-члены класса в языке С++. Друзья класса в языке С++.
|
Область видимости класса в языке С++. |
|
|||
|
Инициализация класса в языке С++. |
|
328 |
||
2. |
Наследование в языке С++. |
|
332 |
||
3. |
Виртуальные функции в языке С++. |
|
334 |
||
4. |
Полиморфизм. На примере С++. |
|
337 |
||
5. |
Инкапсуляция. На примере С++. |
|
339 |
||
VIII. МЕТОДЫ И СРЕДСТВА ЗАЩИТЫ ИНФОРМАЦИИ |
341 |
||||
1. |
Системотехнические |
основы построения датчиков |
|
||
|
случайных чисел. Принципы аналого-цифрового |
|
|||
|
преобразования. Причины выбора данного принципа |
|
|||
|
аналого-цифрового преобразования. |
|
341 |
||
2. |
Понятие |
Фон |
Нэймановской |
архитектуры |
|
|
вычислительной системы. Базовые принципы. |
|
|||
|
Проблема получения случайных чисел в рамках |
|
|||
|
данной архитектуры. Основной вывод |
|
344 |
3.Системы гарантированной секретности.
Теоретические основы. |
346 |
4.Длиннопериодические ключевые последовательности. Датчики псевдослучайных чисел и их роль для создания длиннопериодических ключевых
последовательностей. |
Анализ |
стойкости |
7
длиннопериодических |
|
ключевых |
|
|
последовательностей |
|
|
347 |
|
5. Простейшие протоколы обеспечения многократной |
|
|||
электронной цифровой подписи. Пример применения |
349 |
|||
6. Модель угроз «Несанкционированный доступ к |
|
|||
передаваемой через открытый канал информации». |
|
|||
Криптографические методы противодействия данной |
|
|||
угрозе |
|
|
|
350 |
7. Модель угроз «Искажение передаваемой в открытом |
|
|||
канале информации». Криптографические методы |
|
|||
противодействия данной угрозе. Классификация |
|
|||
методов. Пример. |
|
|
351 |
|
8. Модель угроз «Нарушение целостности программного |
|
|||
обеспечения |
внутри |
периметра |
защиты». |
|
Формализация. Субъектно-объектный подход. |
356 |
9.Теорема о неразрешимости множества доверенных субъектов в вычислительной системе Фон
Нэймановской архитектуры. Связь |
с одним |
из |
базовых принципов Фон Нэймановской архитектуры. |
||
Понятие доверенной аппаратной компоненты. |
362 |
10.Примеры аппаратных решений для создания
|
изолированных программных сред. |
|
363 |
|||
IX. ОПЕРАЦИОHHЫЕ СИСТЕМЫ |
|
|
366 |
|||
1. |
Классификация ОС |
|
|
366 |
||
2. |
Структура сетевой операционной системы |
|
372 |
|||
3. |
Управление процессами. Понятие процесса. |
|
||||
|
Дескриптор |
и |
контекст |
процесса.Алгоритмы |
|
|
|
планирования процессов. Вытесняющая и не |
|
||||
|
вытесняющая многозадачность. |
|
|
376 |
||
4. |
Средства синхронизации взаимодействия процессов. |
|
||||
|
Блокирующие переменные, семафоры |
|
383 |
|||
5. |
Взаимные |
|
блокировки |
процессов. |
Тупики |
|
|
распознавание, рекомендации как избежать тупик, |
|
||||
|
выход из тупика. |
|
|
|
389 |
|
6. |
Проблемы взаимодействия процессов. Основные |
|
||||
|
задачи, возникающие при взаимодействии процессов. |
392 |
||||
7. |
Нити и процессы |
|
|
|
392 |
|
|
|
|
8 |
|
|
|
8. Управление памятью. Типы адресов. Обзор методов
|
распределения памяти. |
395 |
9. Методы управления памятью без использования |
|
|
|
внешней памяти |
398 |
10. |
Оверлеи. Виртуальная память. Способы организации |
|
|
виртуальной памяти |
402 |
11. |
Свопинг и кэширование |
412 |
12. |
ОС. Управление вводом-выводом |
415 |
13. |
Файловая система. Основные функции. Общая |
|
|
схема. |
419 |
14. |
Логическая и физическая организация файлов. |
|
|
Права доступа к файлу. Кэширование файла. |
|
|
Отображение файла в оперативную память. |
|
|
Проблемы совместного использования. |
423 |
X. ТЕОРИЯ ВЫЧИСЛИТЕЛЬHЫХ ПРОЦЕССОВ |
И |
СТРУКТУР |
429 |
1. Операции над формальными языками |
429 |
2.Двоичное кодирование переменных и функций
трехзначной логики |
432 |
3.Перечислить способы представления конечного
автомата |
435 |
4. Определение недетерминированного и конечного |
|
автомата |
437 |
5. Программная реализация логических функций |
439 |
XI. АРХИТЕКТУРА ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМ |
442 |
1.Виды систем обработки данных. Режимы обработки данных. Сформулируйте различия между
многомашинными вычислительными комплексами и |
|
вычислительными сетями. |
442 |
2.Уровни комплексирования устройств в вычислительных системах. Постройте структурную схему ПЭВМ, состоящей из двух процессоров.
Покажите |
на |
ней |
используемые |
уровни |
комплексирования. Ответ поясните. |
444 |
3. Методы улучшения ОКОД структуры. Степень, уровни и виды параллелизма. Какой из видов параллелизма реализуется в современных универсальных
9