Институт (НОЦ) систем управления и информационных технологий

ЮГОРСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

Институт (НОЦ) систем управления и информационных технологий

Кафедра компьютерного моделирования и информационных технологий

 

 

Программа утверждена

на заседании кафедры КМИТ

И(НОЦ)СУТ ЮГУ

Протокол №___

________________г.

 

______________________

Директор И(НОЦ)СУИТ

Ю.В. Колоколов

 

РАБОЧАЯ УЧЕБНАЯ ПРОГРАММА

Итогового государственного экзамена по специальности

«Информатика и вычислительная техника» (230100)

Учебный год

 

Составители:

доцент к.ф.-м.н. Семенов С.П.

доцент к.ф-м.н. Алексеев А.В.,

доцент к.ф-м.н. Бурлуцкий В.В.

 

 

Ханты–Мансийск, 2012
ПОЯСНИТЕЛЬНАЯ ЗАПИСКА

 

Программа Итогового государственного экзамена составлена в соответствии с требованиями Государственного образовательного стандарта высшего профессионального образования по направлению 230100– «Информатика и вычислительная техника» и Положением об итоговой государственной аттестации выпускников высших учебных заведений.

Программа государственного экзамена включает ключевые и практически значимые вопросы по комплексам дисциплин, входящих в цикл специальных дисциплин Госстандарта по по направлению 230100– «Информатика и вычислительная техника».

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

Экзаменуемый студент должен подтвердить знание фундаментальных основ:

САОД (Структуры и Алгоритмы Обработки Данных).

· знание и использование в профессиональной деятельности различных способов организации хранения данных;

· умение выбора оптимального для решаемой проблемы алгоритма обработки данных.

Технологии проектирования и разработки программного обеспечения

• знание и использование методологии проектирования АСОИУ;
• умение строить модели различных этапов жизненного цикла программного продукта.

Методологии программирования

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

· умение применять базовые навыки логического и функционального программирования;

Сети ЭВМ и телекоммуникации

· знание тенденций развития структур систем телеобработки и вычислительных сетей и основных стандартах вычислительных сетей;

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

· умение инсталлировать локальную вычислительную сеть, настраивать ее конфигурацию;

Критерии оценки знаний экзаменуемых:

При оценке знаний на Итоговом государственном экзамене учитывается:

• правильность и осознанность изложения содержания ответа на вопросы, полнота раскрытия понятий и закономерностей, точность употребления и трактовки общенаучных и специальных терминов;

• степень сформированности интеллектуальных и научных способностей экзаменуемого;

• самостоятельность ответа;

• речевая грамотность и логическая последовательность ответа.

 

Оценка "отлично":

• полно раскрыто содержание вопросов в объеме программы и рекомендованной литературы;

• четко и правильно даны определения и раскрыто содержание концептуальных понятий, закономерностей, корректно использованы научные термины;

• для доказательства использованы различные теоретические знания, выводы из наблюдений и опытов;

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

Оценка "хорошо":

• раскрыто основное содержание вопросов;

• в основном правильно даны определения понятий и использованы научные термины;

• ответ самостоятельный;

• определения понятий неполные, допущены нарушения последовательности изложения, небольшие неточности при использовании научных терминов или в выводах и обобщениях, исправляемые по дополнительным вопросам экзаменаторов.

Оценка "удовлетворительно":

• усвоено основное содержание учебного материала, но изложено фрагментарно, не всегда последовательно;

• определение понятий недостаточно четкое;

• не использованы в качестве доказательства выводы из наблюдений и опытов или допущены ошибки при их изложении;

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

Оценка "неудовлетворительно":

• ответ неправильный, не раскрыто основное содержание программного материала;

• не даны ответы на вспомогательные вопросы экзаменаторов;

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

 

СОДЕРЖАНИЕ ПРОГРАММЫ

 

Технологии проектирования и разработки ПО

 

Основные понятия проектирования ИС

Основные особенности современных проектов ИС. Этапы создания ИС: формирование требований, концептуальное проектирование, спецификация приложений, разработка моделей, интеграция и тестирование информационной системы. Методы программной инженерии в проектировании ИС.

Жизненный цикл программного обеспечения ИС

Понятие жизненного цикла ПО ИС. Процессы жизненного цикла: основные, вспомогательные, организационные. Содержание и взаимосвязь процессов жизненного цикла ПО ИС. Модели жизненного цикла: каскадная, модель с промежуточным контролем, спиральная. Стадии жизненного цикла ПО ИС. Регламентация процессов проектирования в отечественных и международных стандартах.

Организация разработки ИС

Каноническое проектирование ИС. Стадии и этапы процесса канонического проектирования ИС. Цели и задачи предпроектной стадии создания ИС. Модели деятельности организации ("как есть" и "как должно быть"). Состав работ на стадии технического и рабочего проектирования. Состав проектной документации. Типовое проектирование ИС. Понятие типового проекта, предпосылки типизации. Объекты типизации. Методы типового проектирования. Оценка эффективности использования типовых решений. Типовое проектное решение (ТПР). Классы и структура ТПР. Состав и содержание операций типового элементного проектирования ИС. Функциональные пакеты прикладных программ (ППП) как основа ТПР. Адаптация типовой ИС. Методы и средства прототипного проектирования ИС.

Анализ и моделирование функциональной области внедрения ИС

Основные понятия организационного бизнес-моделирования. Миссия компании, дерево целей и стратегии их достижения. Статическое описание компании: бизнес-потенциал компании, функционал компании, зоны ответственности менеджмента. Динамическое описание компании. Процессные потоковые модели. Модели структур данных. Полная бизнес-модель компании. Шаблоны организационного бизнес-моделирования. Построение организационно-функциональной структуры компании. Этапы разработки Положения об организационно-функциональной структуре компании. Информационные технологии организационного моделирования.

5. Спецификация функциональных требований к ИС

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

Технологии проектирования

Понятие технологии проектирования. Понятие CASE-средства. Общая характеристика. Типовые компоненты CASE-средств. Классификация и сравнительный анализ основных CASE-средств. Выбор и технология внедрения CASE-средств. Промышленные технологии проектирования ИС. Экстремальное программирование. DATARUN. RUP. Метод Oracle.

Линейные структуры данных.

Стеки. Очереди. Деки. Операции над линейными списками.

 

Сортировка данных.

Общие понятия. Внутренняя сортировка: основные методы, быстрые методы. Внешняя сортировка.

 

Алгоритмы комбинаторики.

Генерация комбинаторных объектов. Перебор всех вариантов. Перестановки. Сочетания.

 

Табличные структуры.

Виды таблиц. Линейные таблицы. Древовидные таблицы. Таблицы с вычисляемыми входами.

 

Алгоритмы на графах.

Основные определения. Представление графов. Пути в графе. Кратчайшие пути. Обходы графов. Остовное дерево наименьшего веса.

 

Перечень рекомендуемой литературы:

1. Ахо А., Хопкрофт Д., Ульман Д. Структуры данных и алгоритмы. М., Изд. "Вильямс", 2000 г.

2. Вирт Н. Алгоритмы + структуры данных = программы. М., Изд. "Мир", 1985 г.

3. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М., «Мир», 1982 г.

4. Кнут Д. Искусство программирования для ЭВМ. Т.1. Основные алгоритмы. М., "Мир", 1976 г., (переиздание - М., Изд. "Вильямс", 2000 г.)

5. Кнут Д. Искусство программирования для ЭВМ. Т.3. Сортировка и поиск. М., "Мир", 1978 г., (переиздание - М., Изд. Изд. Вильямс", 2000 г.)

6. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы. Анализ и построение. М., Изд. "БИНОМ", 2000 г.

7. Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. Алгоритмы: построение и анализ, 2-е издание. – М.: Вильямс, 2005.

8. Липский В. Комбинаторика для программистов. – М.: Мир, 1988.

9. Хусаинов Б.С. Структуры и алгоритмы обработки данных. Примеры на языке Си: Учебное пособие. – М.: Финансы и статистика, 2004.

 

Вопросы САОД

 

1. Динамические типы данных: список, стек, очередь, дек.

2. Нелинейные структуры данных: деревья, представление деревьев в ЭВМ, операции над деревьями.

3. Идеально сбалансированное бинарное дерево. Сбалансированные деревья поиска.

4. Алгоритмы с возвратом.

5. Динамическое программирование.

6. Методы сортировки массивов.

7. Внешняя сортировка.

8. Генерация комбинаторных объектов. Перебор всех вариантов.

9. Генерация комбинаторных объектов. Перестановки.

10. Линейные таблицы: поиск в неупорядоченных и упорядоченных таблицах.

11. Таблицы с вычисляемыми входами.

12. Построение матрицы достижимости (путевая матрица).

13. Кратчайшие пути: алгоритм Дейкстры, алгоритм Флойда.

14. Поиск в ширину и глубину на графе.

15. Остовное дерево минимального веса: алгоритм Прима, алгоритм Крускала.

 

Задачи САОД

1. Для задачи «Бросание кубика» разработать два-три алгоритма её решения, провести анализ их сложности.

Условие задачи: Кубик, грани которого помечены цифрами от 1 до 6, бросают N раз. Найти вероятность того, что сумма выпавших чисел будет равна Q.

2. Для задачи «Выражение» разработать два-три алгоритма её решения, провести анализ их сложности.

Условие задачи: Расставить между заданными N целыми числами знаки «+» и «-» так, чтобы значение получившего выражения было равно заданному S.

3. Для задачи «Дележ» разработать два-три алгоритма её решения, провести анализ их сложности.

Условие задачи: Заданные N предметов разделить на две примерно одинаковые части.

4. Для задачи «Максимальный квадрат» разработать два-три алгоритма её решения, провести анализ их сложности.

Условие задачи: На заданной дискретной карте найти свободный квадрат максимального размера.

5. Для задачи «Коммивояжер» разработать два-три алгоритма её решения, провести анализ их сложности.

Условие задачи: Найти последовательность посещения заданных N городов.

6. Для задачи «Маршрут» разработать два-три алгоритма её решения, провести анализ их сложности.

Условие задачи: В заданной квадратной таблице размера N найти такой путь из левого верхнего угла в правый нижний, у которого сумма чисел минимальна.

7. Для задачи «Музей» разработать два-три алгоритма её решения, провести анализ их сложности.

Условие задачи: В музее регистрируется время прихода и ухода посетителей. Найти максимальное число посетителей, находящихся в музее одновременно.

8. Для задачи «Перемножение матриц» разработать два-три алгоритма её решения, провести анализ их сложности.

Условие задачи: Вычислить произведение N матриц A₁A₂…A_N за наименьшее количество действий.

9. Для задачи «Монетки» разработать два-три алгоритма её решения, провести анализ их сложности.

Условие задачи: Имеется по две монетки достоинством a₁, a₂, …, a_N. Можно ли ими заплатить сумму в S рублей.

10. Для задачи «Разделение сред» разработать два-три алгоритма её решения, провести анализ их сложности.

Условие задачи: Имеется N материалов, из которых необходимо сделать перегородку с наибольшим временем разделения сред.

11. Для задачи «Подпоследовательность» разработать два-три алгоритма её решения, провести анализ их сложности.

Условие задачи: Для двух заданных последовательностей найти общую подпоследовательность наибольшей длины.

 

12. Для задачи «Рюкзак» разработать два-три алгоритма её решения, провести анализ их сложности.

Условие задачи: Имеется N предметов различных типов весом a_i и стоимостью b_i. Найти максимальную стоимость груза, помещающегося в рюкзак, выдерживающий максимальный вес W.

13. Для задачи «Сплочённая команда» разработать два-три алгоритма её решения, провести анализ их сложности.

Условие задачи: Команда будет сплочённой, если профессионализм каждого не превосходит суммы профессионализмов любых двух других игроков. Сформировать из N игроков наиболее сплочённую команду.

14. Для задачи «Счастливые билеты» разработать два-три алгоритма её решения, провести анализ их сложности.

Условие задачи: Найти количество счастливых билетов из 2N цифр.

15. Для задачи «Точки» разработать два-три алгоритма её решения, провести анализ их сложности.

Условие задачи: Найти количество точек с целочисленными координатами в круге радиуса N.

Модели вычислений

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

Языки программирования

Традиционные языки и традиционная архитектура. Структура традиционной программы. Основные традиционные языки. Преобразование текста программы в исполняемый код. Синтаксис, семантика и прагматика языка программирования. Понятие НБФ грамматики. Определение порождающей и распознающей грамматики. Описание процесса трансляции.

Вопросы Методологии программирования

1. Модель вычислений. Понятие стиля и методологии программирования.

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

3. Архитектура вычислительных машин и их связь с моделями вычислений.

4. Языки программирования. Синтаксис, семантика и прагматика.

5. Формальные теории. Теоремы Геделя.

6. Исчисления высказываний. Модальные и темпоральные логики.

7. Исчисление предикатов. Метод резолюций.

8. Основные принципы логического программирования.

9. Рекурсия. Виды рекурсии.

10. Язык программирования Пролог.

11. Объектно-ориентированное программирование. Основные принципы.

Сети ЭВМ и телекоммуникации

ЛВС FDDI.

Составляющие стандарта, принцип действия. Протокол доступа и структура кадра. Алгоритмы маршрутизации. Цели маршрутизации. Требования к алгоритму маршрутизации. функции алгоритма маршрутизации. Классифи-кация алгоритмов маршрутизации. Стратегии маршрутизации де-централизованные изолированные. Стратегии маршрутизации децентра-лизованные глобальные. Метод рельефа.

Вопросы по Сетям ЭВМ и телекоммуникациям

1. Вычислительные сети, общее понятие назначение.

2. Эталонная модель взаимодействия открытых систем.

3. Модель OSI: уровень приложения, уровень представления, уровень сессии, транспортный уровень.

4. Модель OSI: транспортный, сетевой, канальный и физические уровни.

5. Протокол V.24.

6. Протокол V.35.

7. Среда передачи данных: коаксиальный кабель, неэкранированная витая пара. Линия связи. Характеристики линий связи.

8. Среда передачи данных: экранированная витая пара, оптоволоконный кабель. Линия связи. Характеристики линий связи.

9. Амплитудная, частотная и фазовая модуляция сигнала.

10. Цифровое кодирование: потенциальный код NRZ, биполярное кодирование с альтернативной инверсией, манчестерский код, потенциальный код 2B1Q.

11. Логическое кодирование: Избыточные коды. 4B/5B, скремблирование, искусственное искажение с использованием запрещенных символов.

12. Методы многоуровневой модуляции.

13. Дискретная модуляция аналоговых сигналов.

14. Сжатие данных: LZW. Метод помехоустойчивого кодирования Хаффмена.

15. Контроль ошибок: паритет, избыточная циклическая сумма, код Хэмминга.

16. Шифрование данных: шифрование с открытым ключом.

17. Топологии LAN.

18. Топология шина, CSMA/SD.

19. Физический уровень: MAC, LLC.

20. Концентраторы, Ethernet.

21. Коммутаторы.

22. Алгоритм Spanning tree.

23. Протокол IP.

24. Фрагментация сетевого уровня.

25. Опции фрагментации.

26. Классовая и бесклассовая IP адресация.

27. Адресация IP6.

28. Протокол IPsec.

29. Режим туннеля и транспортный режим IPsec.

30. Протокол АН.

31. Протокол ESP.

32. AH, ESP и NAT.

33. Построение VPN посредством IPsec.

34. Ассоциации безопасности и SPI в IPsec.

35. Транспортный уровень. Протокол UDP.

36. Транспортный уровень. Протокол TCP.

37. Протокол "скользящего окна". Синдром "глупого окна".

38. Таймеры TCP.

39. Статическая маршрутизация.

40. Динамическая маршрутизация RIP.

Экзаменационные билеты

Итогового государственного экзамена по направлению 230100 “Информатика и вычислительная техника”

 

Билет №1

 

1. Эталонная модель взаимодействия открытых систем.

2. Модель вычислений. Понятие стиля и методологии программирования.

3. Динамические типы данных: список, стек, очередь, дек.

4. Жизненный цикл ПО. Процессы и стации жизненного цикла ПО. Модели жизненного цикла ПО.

5. Для задачи «Бросание кубика» разработать два-три алгоритма её решения, провести анализ их сложности.

Условие задачи: Кубик, грани которого помечены цифрами от 1 до 6, бросают N раз. Найти вероятность того, что сумма выпавших чисел будет равна Q.

 

ЮГОРСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

Институт (НОЦ) систем управления и информационных технологий