Всё для Учёбы — студенческий файлообменник
1 монета
doc

Студенческий документ № 020470 из ГЭИ

Таганрогский государственный радиотехнический университет

Факультет автоматики и вычислительной техники

Кафедра математического обеспечения и применения ЭВМ

Программа

государственного экзамена итоговой аттестации

студентов, обучающихся по специальности 010503

"Математическое обеспечение и администрирование

информационных систем"

Таганрог 2009

РАЗДЕЛ 1. СТРУКТУРЫ И АЛГОРИТМЫ ОБРАБОТКИ

ДАННЫХ ¦ 1.. Сцепленные структуры данных. Линейные списки. Односвязные и двусвязные списки. Кольцевые списки. Использование списков для представления стеков и очередей. Деревья как структуры данных. Представление деревьев. Бинарные деревья и основные операции над ними. Обход дерева.

2. Оценка эффективности алгоритмов и программ. Максимальное, среднее и минимальное время выполнения. Теоретический и экспериментальный подход к оценке эффективности. Размерность задачи. Оценки "в смысле 0-большое". Экспоненциальные и полиномиальные оценки. Примеры оценок для типовых алгоритмов.

3. Сортировка и поиск в массивах. Линейный поиск в массиве. Барьерный поиск. Бинарный поиск в массиве. Оценка эффективности линейного и бинарного поиска. Простые алгоритмы сортировки массивов. Оценка эффективности простых алгоритмов.

4. Усовершенствованные алгоритмы сортировки массивов. Алгоритм Quicksort. Выбор разделяющего элемента. Нерекурсивная реализация Quicksort. Алгоритм HeapSort. Понятие ' пирамиды. Фазы работы алгоритма. Оценка эффективности усовершенствованных алгоритмов.

5. Алгоритмы слияния. Операция слияния массивов. Простое слияние. Фазы разделения и слияния. Естественное слияние. Внешняя сортировка.

6. Бинарные деревья поиска. Поиск с включением в дерево. АВЛ-деревья. Операция балансировки АВЛ-дерева при вставке и удалении ключей.

7. Поиск в фашюх. Страничные деревья поиска. Понятие В-дерева. Операции вставки и удаления ключей для В-дерева.

8. Хеширование. Понятие хеширования. Требования к хеш-функции. Способы построения хеш-функции. Коллизии хеширования и способы их разрешения. Сравнение хеширования с другими стратегиями поиска.

9. Комбинаторные задачи. Задачи поиска, перечисления и

оптимизации. Задачи с фиксированной и нефиксированной

размерностью. Способы организации исчерпывающего перебора.

Способы сокращения перебора.

10. Метод ветвей и границ. Нижние и верхние оценки.

Алгоритм ветвей и границ для задачи о коммивояжере. Метод ос-

Р-отсечений для позиционных игр.

11. Метод динамического программирования. Функция

Беллмана. Уравнения Беллмана для дискретных задач. Алгоритм

Беллмана для задачи о рюкзаке.

12. Приближенные и эвристические алгоритмы. Примеры

приближенных алгоритмов. Локально оптимальные ("жадные")

алгоритмы. Алгоритмы последовательного выбора и

последовательных улучшений. Случайный поиск. Генетические

алгоритмы.

13. Понятие сложности задачи. Массовые и индивидуальные задачи. Длина задачи. Задачи распознавания. Полиномиальные и экспоненциальные алгоритмы. Полиномиальная сводимость.

14. Недетерминированные машины Тьюринга (НМТ). Машина Тьюринга и класс задач Р. Определение НМТ. Функционирование НМТ. Класс задач NP. Полиномиально проверяемые задачи.

15. Понятие NP-полноты задачи. Определения NP-трудных и NP-полных задач. Соотношение между классами Р, NP и NPC. Возможность сведения всех NP-задач к конкретной задаче. Задача о выполнимости КНФ. Теорема Кука.

16. Примеры доказательства NP-полноты задач. Способы доказательства NP-полноты. NP-полнота задачи "3-выполнимость" и задачи о вершинном покрытии графа.

17. Основные понятия теории графов. Неориентированные и ориентированные графы. Способы представления графов: матрицы смежности и инцидентности, списки ребер, списки смежных вершин.

18. Организация поиска в графе. Поиск в глубину и в ширину. Примеры применения алгоритмов поиска.

13.

19. Построение минимального остовного дерева. Постановка задачи. Алгоритмы Прима и Крускала. Оценка эффективности алгоритмов.

20. Задача о кратчайшем пути в графе. Постановка задачи. Алгоритмы Флойда и Дейкстры. Оценка эффективности алгоритмов.

21. Задача о максимальном потоке в сети. Варианты постановки задачи. Аугментальные цепи. Алгоритм Форда-Фалкерсона.

22. Задача о максимальном паросочетании. Постановка задачи. Решение задачи для двудольных графов.

23. Задача о раскраске графа. Постановка задачи. Эвристические алгоритмы раскраски. Алгоритм неявного перебора.

24. Основные понятия теории информации. Задачи сжатия данных. Префиксные коды. Кодовые деревья. Оптимальные префиксные коды (коды Хаффмена) и их построение.

ЛИТЕРАТУРА

1. Вирт Н. Алгоритмы + структуры данных = программы. - М.: "Мир", 1985. - 544 с, ил.

2. Ахо А., Хопкрофт Дж., Ульман Дж. Структуры данных и алгоритмы. - М.: Издательский дом "Вильяме", 2001. - 384 с, ил.

3. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. - М.: МЦНМО, 2000. - 960 с, ил.

4. Рейнгольд Э., Нивергельт Ю., Део Н. Комбинаторные алгоритмы. Теория и практика. - М.: "Мир", 1980. - 476 с, ил.

5. Гудман С, Хидетниеми С. Введение в разработку и анализ алгоритмов. -М.: "Мир", 1981. - 366 с, ил.

6. Кнут Д. Искусство программирования для ЭВМ. т.1. Основные алгоритмы. М.: Вильяме, 2002. - 736 с, ил.; т.2. Получисленные алгоритмы. М.: Вильяме, 2002. - 724 с, ил.; т.З. Сортировка и поиск. - М.: Вильяме, 2002. - 826 с, ил.

7. Кристофидес Н. Теория графов. Алгоритмический подход. -М.:Мир, 1978.-432с, ил.

8. Гэри М., Джонсон Д. Вычислительные машины и

труднорешаемые задачи. - М.: "Мир", 1982. - 416 е., ил.

9. Дроздов С.Н. Комбинаторные задачи и элементы теории

вычислительной сложности. Учебное пособие. - Таганрог: Изд-

воТРТУ,2000.-62с.

РАЗДЕЛ 2. ТЕХНОЛОГИЯ РАЗРАБОТКИ ПРОГРАММНОГО ОБЕСПЕЧЕНИЯ

1. Введение. Краткая характеристика дисциплины, ее цели, задачи, порядок изучения материала, связь с другими дисциплинами учебного плана. Программная инженерия.

2. Понятия технологии программирования. Программа. Компонент программной системы. Программная система. Программный продукт. Программное изделие. Классификация программных систем по сложности. Основные характеристики и критерии качества программ и программных систем. Модели жизненного цикла программных систем. Водопадная, инкрементальная и спиральная модели. Облегченные процессы разработки. Стадии и этапы разработки программных систем и программной документации. Понятие производства программных продуктов.

3. Основные концепции RUP. Введение в RUP. Проблема разработки ПО. Концепции RUP. Лучший опыт: итерационная разработка, управление требованиями, использование компонентной архитектуры, визуальное моделирование, контроль качества, управление изменениями. Инструментальная поддержка: управления требованиями, визуальное моделирование, автоматическое тестирования, управления изменениями. Услуги поставщика.

4. Управление средой разработки. Проект Rational и Rational Administrator. Цели управления средой, основные понятия управления средой, поток работ управления средой, понятие проекта Rational.

5. Бизнес-моделирование. Цели бизнес-моделирования, основные понятия, поток работ, инструментальная поддержка, переход от бизнес-моделей к системным моделям.

1.

6. Визуальное моделирование с использованием Rational Rose. Назначение Rational Rose. Основы графического интерфейса. Представления. Диаграммы. Работа в группе.

7. Управление запросами изменения, Rational ClearQuest. Назначение ClearQuest. Обзор архитектуры. Понятия схем и баз данных ClearQuest. Основные операции.

8. Администрирование Rational ClearQuest. Основные понятия администрирования ClearQuest, процесс управления запросами изменения в проекте, задачи администратора. Интеграция ClearQuest и RequisitePro: введение, отличие запроса расширения от требования, обзор инструментов, необходимость интеграции, настройка интеграции.

9. Управление требованиями, Реализация. Цели управления требованиями. Основные понятия управления требованиями. Инструментальная поддержка. Поток работ управления требованиями. Совместное использование ClearQuest и RequisitePro. Rational Unified Process: Реализация. Цели дисциплины "Реализация". Ограничения. Артефакты дисциплины "Реализация". Поток работ дисциплины.

10. Rational Unified Process: Анализ и проектирование. Цели анализа и проектирования. Артефакты. Поток работ. Пример.

11. Управление конфигурацией и изменениями. Цели управления конфигурацией и изменением. Основные понятия. Поток работ.

12. Обзор Rational SoDA. Назначение SoDA. Основные понятия.Команды. Настройка шаблона. Template View: пример создания шаблона.

13. Rational Unified Process: Управление проектом. Основы управления проектами. Цель дисциплины "Управление проектом". Основные понятия. Поток работ.

14. Универсальный язык моделирования (UML). Назначение и история UML. Применение UML в жизненном цикле проектов. Обзор составных частей языка UML. Нотация и семантика языка. Сущности. Отношения. Диаграммы. Стандартные элементы языка UML.

15. Варианты использования (use cases) - внешнее представление системы. Диаграммы вариантов использования

(use case diagram). Актеры. Роли. Отношения между вариантами использования: включение, обобщение, расширение. Применение вариантов использования на этапе исследования проекта.

16. Диаграммы классов (class diagram) - описание типов объектов и статических отношений между ними. Элементы диаграммы классов: класс, объект, пакет, примечание. Отношения между классами: ассоциация, агрегирование, обобщение, зависимости. Разновидности классов UML: интерфейс, шаблон, утилита. Применение диаграмм классов для построения модели предметной области. Объекты. Диаграммы объектов (object diagram). Стереотипы. Отношение между объектом и его типом -классификация.

17. Диаграммы взаимодействия (interaction diagram) -описание поведения взаимодействующих объектов. Виды диаграмм взаимодействия: диаграммы последовательности (sequence diagram), диаграммы кооперации (collaboration diagram). Применение диаграмм взаимодействия для описания поведения объектов в рамках одного варианта использования.

18. Кооперация - именованное взаимодействие классов. Диаграммы состояний (statechart diagram) - отображение возможных состояний объекта с течением времени. Применение диаграмм состояний для описания поведения объекта в различных вариантах использования. Диаграммы деятельности (activity diagram) - описание последовательности состояний деятельности системы. Возможность изображения условного и параллельного поведений: ветвления, соединения, разделения.

19. Группирование классов в Пакеты (packages). Зависимости пакетов. Диаграмма пакетов. Физические диаграммы: диаграмма развертывания (deployment diagram), диаграмма компонентов (component diagram).

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

21. Анализ и моделирование. Методы анализа и моделирование. Модели с различных точек зрения: с внешней

20.

перспективы (моделируется контекст системы); с поведенческой перспективы (моделируется поведение системы); со структурной точки зрения, в которой моделируется архитектура системы или структура данных, обрабатываемых системой. Модели данных, модель "сущность-связь". Объектные модели.

22. Структура программы. Разработка структуры программы. Оценка структуры программы. Понятие прочности и сцепления модулей, методы количественной оценки прочности и сцепления. Методы разработки структуры программы. Нисходящие и восходящие методы. Методика Джексона. Разработка компонентов программы. Модуль. Внешние спецификации модуля. Способы описания спецификаций. Проектирование логики модуля. Документирование модуля.

23. Испытания программных систем. Верификация, тестирование и отладка программы. Основные методы верификации программы и их сравнительный анализ. Тестирование и отладка. Методы тестирования. Структурное тестирование, функциональное тестирование. Заглушки. Использование инструментальных средств тестирования и отладки. Организация процесса тестирования.

24. Внедрение и сопровождение программных систем. Задачи сопровождения программы. Расширение возможностей, адаптация и коррекция. Средства и методы сопровождения. Организация сопровождения. Эксплуатационная документация. Единая система программной документации (ЕСПД).

25. Конфигурационное управление. Задача конфигурационного управления. Элементы конфигурации. Инструментальные средства. Организация конфигурационного управления.

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

27. Организация разработки программных систем.

Структура организации-разработчика программных систем. Организация коллектива программистов. Характер труда разработчиков программных систем. Бригада - основная форма организации труда программистов. Критерии оценки труда бригады и отдельного члена бригады. Управление качеством разработки ПО. Стандарты СММ, ISO-9000. Управление проектами, управление производством программных продуктов.

ЛИТЕРАТУРА

1. Орлов С.А. Технологии разработки программного обеспечения: Учебник. - СПб.: Питер, 2002. - 464 с.

2. Иан Соммервилл. Инженерия программного обеспечения, 6-е издание. Пер. с англ. - М.: Изд. дом "Вильяме", 2002. - 624 с.

3. Брауде Э. Технология разработки программного обеспечения. -СПб.: Питер, 2004.-655 с.

РАЗДЕЛ 3. СИСТЕМЫ РЕАЛЬНОГО ВРЕМЕНИ

Понятие системы реального времени (СРВ). Критерии эффективности СРВ.

Жизненный цикл ПО для СРВ. UML-диаграммы.

Определение процесса, состояния процесса. Операции над процессами. Равноприоритетные и разноприоритетные процессы.

Реентерабельные процедуры. Обработка прерываний. Параллельные процессы.

Задача взаимного исключения. Семафоры и их реализация. Критические области и условные критические области. Мониторы. Управляющие выражения.

Механизм рандеву языка Ада. Особенности диспетчеризации процессов в языке Ада.

Тупики. Необходимые условия возникновения тупиков. Восстановление после тупиков. Обнаружение тупиков по графу распределения ресурсов.

Проблемы, связанные с обнаружением тупиков. Предотвращение тупиков.

Обход тупиков - алгоритм Хабермана.

Принципы организации мультипрограммирования с фиксированными разделами. Мультипрограммирование с переменными разделами. Сборка мусора. Стратегии занятия памяти FF, BF, LF.

Принципы организации виртуальной памяти. Страничная организация. Сегментная организация. Странично-сегментная организация. Управление виртуальной памятью. Стратегии выталкивания страниц. Управление виртуальной памятью.

Алгоритм RR кругового циклического обслуживания. Алгоритм FB многоуровневого циклического обслуживания. Алгоритм LPT. Планирование периодических процессов.

Понятие драйвера. Архитектура Windows NT, общие сведения о драйверах для этой ОС.

Системы SCADA.

Операционные системы реального времени: QNX, Win32, Linux, VxWorks.

ЛИТЕРАТУРА

1. Дейтел Г. Введение в операционные системы. Т.т. 1,2, М.: Мир, 1987

2. Кравченко П.П., Чефранов А.Г. Методы управления ресурсами вычислительных систем. Таганрог: ТРТИ, 1991

3. Джехани Н. Язык Ада. - М.: Мир, 1988.

4. Рамбо Дж., Якобсон А., Буч Г. UML: специальный справочник.- СПб.: Питер, 2002. - 656 с.

5. Сорокина СИ. и др. Программирование драйверов и систем безопасности: Учеб. Пособие. - СПб.: БХВ-Петербург, М.: Издатель Молгачева СВ., 2003. - 256 с.

РАЗДЕЛ 4. АДМИНИСТРИРОВАНИЕ ИНФОРМАЦИОННЫХ СИСТЕМ

Цели создания, выполняемые функции, структура информационных систем, классификация.

Задачи администратора: области сетевого и системного администрирования, различия между ними.

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

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

Классификация сетей ЭВМ: локальная сеть (LAN), городская сеть (MAN), региональная сеть (WAN).

Иерархия протоколов, основные вопросы организации уровней, сервис и интерфейсы.

Сервис с соединением и сервис без соединения, примитивы сервиса, взаимосвязь услуг и протоколов.

Структура стека TCP/IP. Краткая характеристика протоколов по типу и по предназначению.

Адресация в IP-сетях: физический (МАС-адрес), сетевой (IP-адрес) и символьный (DNS-имя)

Три основных класса IP-адресов. Соглашения о специальных адресах: broadcast, multicast, loopback.

Отображение физических адресов на IP-адреса: протоколы

ARP и RARP.

Отображение символьных адресов на IP-адреса: служба

DNS. Автоматизация процесса назначения IP-адресов узлам сети -

протокол DHCP

Протокол межсетевого взаимодействия IP: Формат пакета IP, Управление фрагментацией, Маршрутизация с помощью IP-адресов. Пример взаимодействия узлов с использованием протокола IP. Структуризация сетей IP с помощью масок.

Протокол доставки пользовательских дейтаграмм UDP: порты UDP. Мультиплексирование и демультиплексирование прикладных протоколов с помощью протокола UDP. Формат

сообщений UDP.

Протокол надежной доставки сообщений TCP: Сегменты TCP. Порты и установление TCP-соединений. Концепция квитирования, Формат сообщений TCP.

Протокол обмена управляющими сообщениями ICMP: Общая характеристика протокола ICMP. Формат сообщений протокола ICMP. Эхо-протокол. Сообщения о недостижимости узла назначения. Перенаправление маршрута.

Пространство имен DNS: Выбор имени домена, Регистрация имени домена второго уровня, Создание собственных поддоменов.

Компоненты системы имен BIND: named, сервер имен системы BIND, Библиотека определителей.

Задачи клиента системы BIND: Конфигурирование определителя, Тестирование определителя, Влияние на остальную часть системы (Начальная загрузка, Файлы конфигурации. Доставка почты)

Настройка сервера имен: Файл начальной загрузки: /etc/named.boot.

База данных DNS: Запись SOA, Записи NS, Записи А, Записи PTR, Записи MX, Записи CNAME, Записи HINFO, Записи WKS, Дополнительные записи для обработки почты, Записи ТХТ, Новые записи о ресурсах

Примеры конфигурации системы BIND: Кэширующий сервер, Кэш-файл, Основной сервер небольшой Фирмы, Основной сервер для крупной организации

Брандмауэр и Proxy-сервер: Назначение и

функционирование брандмауэра. Назначение и

функционирование proxy-сервера.

Электронная почта: Состав систем электронной почты. Понятие свободного релея, анти-спамовые меры. Взаимодействие cDNS.

Web-сервис: Состав web-сервера, управление, CGI, SSI, виртуальные серверы, виртуальные каталоги, SSL, безопасность, нагрузка.

ЛИТЕРАТУРА

1. Ю.А.Семенов. Протоколы и ресурсы Интернет. - М.: Радио и Связь, 1996

2. Д.С.Армстронг. Секреты Unix. - К.: Диалектика, 1996

3. С. Hunt. TCP/IP Network Administration. - O'Reily and Associates, Inc., Second Edition, December 1997

4. Cricket Liu, Paul Albitz "DNS and BIND" - O'Reilly and Associates, Inc., Third Edition, September 1998.

Показать полностью… https://vk.com/doc34719574_66458431
82 Кб, 22 марта 2012 в 20:19 - Россия, Москва, ГЭИ, 2012 г., doc
Рекомендуемые документы в приложении