Программа вступительного экзамена в магистратуру по направлению 552800 «информатика и вычислительная техника»




Скачать 230.12 Kb.
НазваниеПрограмма вступительного экзамена в магистратуру по направлению 552800 «информатика и вычислительная техника»
Дата23.12.2012
Размер230.12 Kb.
ТипПрограмма
ГОУ ВПО “Уфимский государственный нефтяной технический университет”

Факультет автоматизации производственных процессов

Кафедра вычислительной техники и инженерной кибернетики


ПРОГРАММА ВСТУПИТЕЛЬНОГО ЭКЗАМЕНА В МАГИСТРАТУРУ

ПО НАПРАВЛЕНИЮ 552800 «ИНФОРМАТИКА И ВЫЧИСЛИТЕЛЬНАЯ ТЕХНИКА»

Специальность: 552808 - Информационное и программное обеспечение автоматизированных систем


Общие указания

Программа вступительного экзамена состоит из трех разделов – математические, профессиональные и специальные дисциплины, соответствующих циклам дисциплин теоретической подготовки бакалавра. Каждый раздел содержит перечень основных вопросов, которыми должен владеть поступающий в магистратуру. В конце каждого раздела приведен список рекомендуемой литературы. Экзаменуемый получает по одному вопросу из каждого раздела за сутки до экзамена. На экзамене могут быть заданы дополнительные вопросы. Пользоваться справочными материалами на экзамене не разрешается. Ответы на вопросы из каждого раздела оцениваются отдельно. Если по одному из разделов получена неудовлетворительная оценка, то итоговая оценка за экзамен не может быть положительной.

Раздел 1 Математические дисциплины

1. Математический анализ

2. Основы теории функций комплексной переменной

3. Обыкновенные дифференциальные уравнения

4. Элементы вычислительной математики

5. Математическая логика и теория алгоритмов

6. Дискретная математика

7. Методы оптимизации и принятия решений

Раздел 2 ПРОФЕССИОНАЛЬНЫЕ ДИСЦИИПЛИНЫ

1. Операционные системы

2. Организация ЭВМ и систем

3. Программирование на языке высокого уровня

4. Методы хранения, организация и доступ к данным

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

6. Методы и средства защиты компьютерной информации

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

Раздел 3 Специальные дисциплины

1. Объектно-ориентированное программирование

2. Структуры и алгоритмы обработки данных

3. Теория вычислительных процессов

4. Архитектура вычислительных систем

5. Функциональное и логическое программирование

6. Теория языков программирования и методы трансляции


МАТЕМАТИКА

Математический анализ

  1. Предел последовательности. Принцип Больцано-Вейерштрасса. Верхний и нижний пределы.

  2. Производная и дифференциал. Свойства дифференцируемых функций (теоремы Ролля, Лагранжа, Коши, правила Лопиталя, формула Тейлора). Неявные функции. Экстремумы. Условные экстремумы.

  3. Первообразная и неопределенный интеграл. Интеграл Римана. Повторные интегралы. Замена переменных. Криволинейные и поверхностные интегралы. Формулы Грина, Гаусса-Остроградского, Стокса.

  4. Числовые и функциональные ряды. Равномерная сходимость. Ряды Фурье. Представление функций рядами Фурье.

Основы теории функций комплексной переменной

  1. Степенные и функциональные ряды на комплексной плоскости. Первая теорема Абеля. Радиус сходимости. Формула Коши – Адамара.

  2. Интегрирование и дифференцирование функций комплексного аргумента. Условия Коши - Римана. Теорема и формула Коши.

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

  4. Преобразования Фурье.

  5. Преобразование Лапласа.

Обыкновенные дифференциальные уравнения (ОДУ)

  1. Задача Коши. Теоремы Пеано и Пикара существования и единственности решения задачи Коши.

  2. Линейные однородные и неоднородные дифференциальные уравнения и системы с переменными коэффициентами. Фундаментальная система решений. Методы решения ОДУ. Общее и частное решение. Метод вариации постоянных.

  3. Устойчивость и неустойчивость решений. Теоремы Ляпунова. Устойчивость по первому приближению.

Элементы вычислительной математики

  1. Итерационные методы решения линейных алгебраических систем большой размерности.

  2. Численные методы решения обыкновенных дифференциальных уравнений.

  3. Численное интегрирование функций.

Математическая логика и теория алгоритмов

16. Алгебра высказываний. Логические операции. Равносильность формул. Закон двойственности. Проблема разрешения. Совершенные нормальные формы.

17. Исчисление высказываний. Общие принципы аксиоматизации.

Теорема дедукции, правила и законы исчисления высказываний. Эквивалентные формулы. Непротиворечивость исчисления высказываний. Полнота, независимость аксиом исчисления высказываний.

18. Логика предикатов. Основные понятия, определения и отношения над предикатами. Кванторы. Теоретико-множественный смысл предикатов. Нормальные формулы и нормальные формы. Проблема разрешения.

19. Исчисления предикатов. Формулы и аксиомы исчисления предикатов. Правила образования выводимых формул. Проблема разрешения в исчислении высказываний. Тезис Черча. Вторая теорема Геделя. Некоторые теоремы исчисления высказываний.

20. Теория алгоритмов. Рекурсивные функции. Частично рекурсивные функции. Нормальные алгоритмы Маркова. Алгоритмы и машины Тьюринга. Нумерация вычислимых формул. Универсальные программы.

Дискретная математика

  1. Теория множеств. Основные тождества теории множеств. Теорема об эквивалентностях и разбиениях. Теорема Кантора-Бернштейна, теорема Кантора. Счётные и несчетные множества. Несчётность множества вещественных чисел. Равномощность множества вещественных чисел и множества всех их подмножеств. Основные свойства булевых алгебр. Теорема Стоуна для конечных булевых алгебр.

  2. Полнота и замкнутость систем булевых функций. Основные замкнутые классы. Теорема Поста о полноте. Сложность реализации булевых функций в классе схем из функциональных элементов. Теорема Шеннона о сложности реализации булевых функций в классе схем из функциональных элементов.

  3. Оценки хроматического числа графов. Раскраска графа. Теорема Брукса. Теорема Визинга. Независимые множества и покрытия в графах. Теорема о числе паросочетаний и числе реберного покрытия. Паросочетания в двудольных графах, теоремы Холла и Кенига.

  4. Формула включений и исключений. Производящие функции, возвратные последовательности и линейные рекуррентные соотношения; общее решение линейного рекуррентного соотношения.

Методы оптимизации и принятия решений

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

  2. Задачи линейного программирования (ЛП). Эквивалентность понятий базисного допустимого решения и вершины множества допустимых решений. Критерий разрешимости задачи ЛП. Симплекс-метод. Двойственные задачи ЛП. Первая и вторая теоремы двойственности.

  3. Задача коммивояжера. Нижние оценки целевой функции. Метод ветвей и границ. Алгоритм с гарантированной оценкой точности для метрического случая.

  4. Матричные игры. Определение Седловой точки. Необходимые и достаточные условия равенства верхней и нижней цен игры в чистых стратегиях. Теорема фон–Неймана.

Л И Т Е Р А Т У Р А

1. Кудрявцев Л.Д. Математический анализ. - М.: Высшая школа, 1973. - Т. 1, 2.

2. Бугров Я.С., Никольский С.М. Дифференциальное и интегральное исчисление. М., Наука, 1980.

3. Лаврентьев М.А., Шабат Б.В. Методы теории функций комплексного переменного. - М.: Наука, 1987.

4. Понтрягин Л.С. Обыкновенные дифференциальные уравнения. - М.: Наука, 1982.

5. Самарский А.А., Гулин А.В. Численные методы. - М.: Наука, 1989.

6. Самарский А.А. Теория разностных схем. - М.: Наука, 1977.

7. Бахвалов Н.С. Численные методы. - М.: Наука, 1975, 631 с.

8. Карманов В. Г. Математическое программирование. - М.: Наука, 2003.

9. Балдин К. В. Брызгалов Н. А. Рукосуев А. В. Математическое программирование. 2009, -М.:Издательский дом Дашков и К, 216 стр.

10. Плотников А.Д. Математическое программирование: экспресс-курс Новое знание 2006, - 171 с.

11. Грешилов А.А. Прикладные задачи математического программирования. –М.:Логос. 2006. -286 с.

12. Орлов А. И. Теория принятия решений: Учебник – М.: Изд-во Экзамен, 2006.

13. Волков И.К., Загоруйко Е.А. Исследование рпераций:/Под ред. В.С. Зарубина,– М.: Изд-во МГТУ им. Н.Э. Баумана, 2002 г.

14. Коломоец Ф.Г.Основы системного анализа и теории принятия решений. – М.: Изд-во Тесей, 2006 г.

15. Хемди А, Таха. Введение в исследование операций/7-е изд. –М.:Вильямс, 2007 г.

16. Кейслер Г., Чэн Ч.Ч. Теория моделей. - М.: Мир, 1977.

17. Ершов Ю.Л., Палютин Е.А. Математическая логика. - М.: Наука, 1987.

18. Лавров И.А., Максимова Л.Л. Задачи по теории множеств, математической логике и теории алгоритмов. - М.: Физмалит, 2001. - 256 с.

ПРОФЕССИОНАЛЬНЫЕ ДИСЦИИПЛИНЫ

Операционные системы

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

  2. Стратегии управления оперативной памятью. Виртуальная память. Статическая и динамическая сборка.

  3. Распределение и использование ресурсов вычислительной системы и управление ими. Основные подходы и алгоритмы планирования. Системы реального и разделенного времени.

  4. Взаимодействие процессов. Разделяемая память, средства синхронизации. Очереди сообщений и другие средства обмена данными.

  5. Управление доступом к данным. Файловые системы (основные типы, характеристики).

Л И Т Е Р А Т У Р А

1. Таненбаум Э. Архитектура компьютера. – СПб: Питер, 2006.

2. Таненбаум Э. Современные операционные системы. - СПб: Питер, 2007.

3. Иртегов Д. Введение в операционные системы. – СПб: БХВ-Петербург, 2008.

Организация ЭВМ и систем

6. Традиционная архитектура фон Неймана. Основные архитектурные принципы построения компьютера. Компьютер фон Неймана. Узкие места компьютера фон Неймана и его усовершенствования.

7. Подсистема памяти современного микропроцессора. Основной принцип построения иерархической памяти. Отображаемая (EMS) и расширенная (XMS) память. Типичная схема иерархии памяти. Сегментно–страничная организация памяти. Виртуальная память. Управление физической и виртуальной памятью.

8. Техника конвейеризации. Командный конвейер. Примеры командного конвейера. Количество ступеней. Причины приостановки конвейера и техника их преодоления.

9. Архитектура микропроцессоров 486. Регистр флагов, регистры общего назначения: аккумулятор AX, регистр данных DX, базовый регистр BX, счетчик CX, регистры SI, DI. Регистры управления процессом: ES, SP, IP. Сегментные регистры: CS, DS, SS, ES. Стек.

10. Система команд языка ассемблер. Команды передачи данных MOV, XCHG. Команды стековых передач PUSH, POP. Команды передач адресных объектов. Команды ввода/вывода. Флаговые команды. Арифметические команды: команды сложения, вычитания, умножения. Команды десятичной арифметики, логических операций и сдвигов, передачи управления.

Л И Т Е Р А Т У Р А

1. Организация ЭВМ. /К.Хамахер, З.Вранешич, С.Заки. –СПб.:Питер, 2003, -848 с.

2. Орлов С., Цилькер Б. Организация ЭВМ и систем. - СПб.:Питер, 2007. - 672 с.

3. Таненбаум Э. Архитектура компьютера. Серия "Классика Computer Science". - СПб.: Питер, 2007. - 848 с.

Программирование на языке высокого уровня

11. Характеристика и особенности современных языков программирования. Концепции процедурно-ориентированного и объектно-ориентированного, программирования. Языки Си и С++.

12. Переменные стандартных базовых типов данных, указатели и ссылки, адресные операции. Использование указателей для создания динамических массивов. Области действия и области видимости переменных, классы памяти, локальные, глобальные и статические переменные.

13. Лексемы, операции и выражения языка Си: - арифметические, логические, поразрядные и адресные. Их синтаксис, семантика и особенности применения.

14. Операторы языка Си, их синтаксис, семантика и особенности применения.

15. Сложные типы данных: - массивы, структуры, объединения, их синтаксис, семантика и особенности применения. Конструирование новых типов данных с помощью модификаторов *, [ ] и ( ).

16. Процедуры и функции языка Си, объявление, определение и вызов, механизмы передачи данных через формальные/фактические параметры. Входные, выходные и возвращаемые параметры.

литература

1. Подбельский В. В. Программирование на языке Си: Учеб пособие, - М: Финансы и статистика, 2004, -356 с.

2. Подбельский В.В. Практикум по программированию на языке Си 2004.

3. Прата Стивен. Язык программирования Си. Лекции и упражнения. -К.:ДиаСофт, 2000. -432 с.

4. Демидович Е. М. Основы алгоритмизации и программирования. Язык Си. 2006

5. Шилдт Герберт. Полный справочник по Cи. –М: Диалектика, 2005г.

Методы хранения, организация и доступ к данным

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

18. Понятие транзакции. Понятие целостности (consistency) данных.

19. Реляционная модель. Нормальные формы. Язык SQL. Средства управления и изменения схемы базы данных, определения ограничений целостности.

литература

1. Дейт К. Введение в системы баз данных. - М.:Изд. дом «Вильямс», 2008. - 1328 с.

2. Карпова Т.С. Базы данных: модели, разработка, реализация. - СПб.:Питер, 2001. - 304 с.

3. Кузнецов С.Д. Базы данных: модели и языки: Учебник. - М.: Бином-Пресс, 2008. - 720 с.

4. Маклаков С.В. BPwin и ERwin. CASE-средства разработки информационных систем. - М.: Диалог-МИФИ, 2001. - 304 с.

5. Фиайли Крис. SQL. Руководство по изучению языка. - М.:ДМК Пресс; СПб.: Питер, 2004. - 464 с.

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

20. Общие принципы построения вычислительных сетей. Основные компоненты сети, их возможности. Проблемы физической передачи данных по линиям связи. Топология и структуризация. Эталонная модель взаимосвязи открытых систем, модель OSI, её уровни. Стандартные стеки коммуникационных протоколов. Понятие сетевых протоколов. Основные функции физического, канального, сетевого, транспортного, сеансового, представительного и прикладного уровней.

21. Основы передачи дискретных данных. Линии связи, их характеристики, типы, аппаратура, стандарты кабелей. Методы передачи дискретных данных. Модуляция. Цифровое и логическое кодирование. Методы передачи данных канального уровня. Асинхронные/синхронные протоколы.

22. Базовые технологии локальных сетей. Протоколы и стандарты локальных сетей. Технология Ethernet. Спецификации физической среды Ethernet. Технологии TokingRing, FDDI, FastEthernet, Gigabit Ethernet.

21. Построение локальных сетей по стандартам физического и канального уровней. Структурированная кабельная система. Сетевые адаптеры. Концентраторы, мосты, коммутаторы. Принципы объединения сетей на основе каналов сетевого уровня. Понятия, принципы протоколов маршрутизации.

23. Протокол TCP/IP. Адресация в IP–сетях, классы IP–адресов, особые IP–адреса. Использование масок, назначение адресов. Протокол IP. Маршрутизация, таблицы маршрутизации. Протоколы маршрутизации RIP и OSPF.

24. Глобальные сети. Глобальные связи на основе выделенных линий. Глобальные связи на основе сетей с коммутацией каналов (ISDN). Компьютерные глобальные сети с коммутацией пакетов (Х.25, FrameRelay, ATM). Удаленный доступ. Виртуальные частные сети (VPN).

литература

1. Компьютерные сети./ Э.Таненбаум. –СПб.:Питер, 2003, -992 с.

1. Н.Олиффер, В.Олиффер Компьютерные сети. СПб.: Питер, 1999 г.

2. Норенков И.П., Трудоношин В.А. Телекоммуникационные технологии и сети. - М.: МГТУ им. Н.Э.Баумана, 2000.

4. Ю.Блэк. Сети ЭВМ: протоколы, стандарты, интерфейсы.- М.; Мир, 1990.

5. Уолренд Дж. Телекоммуникационные и компьютерные сети. Вводный курс. /М.: ПОСТМАРКЕТ, 2001.-480 с.

5. Олифер В.Г. Новые технологии и оборудование IP-сетей. СПб.:BHV, 2000 – 512 с.

6. Компьютерные сети. Учебный курс. М.: Русская Редакция, 1999 – 576 с.

7. Кульгин М. Технологии корпоративных сетей. Энциклопедия. СПб.:Питер, 2000-704 с.

Методы и средства защиты компьютерной информации

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

Нормативно правовая база защиты компьютерной информации и информационных технологий.

26. Политика и стандарты безопасности. Ограничение и разграничение доступа. Контроль доступа к аппаратуре. Защита от побочных электромагнитных излучений и наводок. Защита от разрушающих программных воздействий и компьютерных вирусов. Модели взаимодействия прикладной программы и программы злоумышленника.


Наиболее популярные антивирусные средства. Программы детекторов-фагов. Выбор и использование антивирусных средств. Использование вирусов для защиты информации.

27. Теоретические основы компьютерной безопасности. Криптографические модели и алгоритмы шифрования. Шифрование данных и программ. Способы шифрования. Комбинированные методы шифрования. Символьное и смысловое кодирование. Шифрование с закрытым и открытым ключом. Программные и аппаратные средства шифрования с закрытыми и закрытыми ключами.

28. Модели безопасности операционных систем. Сетевая защита Windows 9x. Организация доступа к разделяемым ресурсам в качестве клиента и сервера. Способы защиты разделяемых ресурсов. Защита на уровне ресурсов и пользователей. Основные компоненты системы безопасности Windows NT, возможные атаки и методы противодействия им. Основные компоненты системы безопасности Unix.


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

литература

1. Рябко Б.Я., Фионов А.Н. Основы современной криптографии. - М.: Научный мир, 2004. - 173 с.

2. Петров А.А. Компьютерная безопасность. Криптографические методы защиты. –М.:ДМК, 2000. -448 с.

3. Анин Б. Защита компьютерной информации. СПб.:БХВ-Петербург, 2002, - 384 с.

4. Ярочкин В. И. Информационная безопасность. Учебное пособие для студентов. – М.: Междунар. отношения, 2000. – 400 с.

5. Введение в криптографию/Под ред. В. В. Ященко. – СПб.: Питер, 2001. – 288 с.

6. Мельников, В. П. Информационная безопасность и защита информации :учеб. пособие для вузов. – М. :Академия, 2006. – 331 с.

7. Введение в защиту информации : учеб. пособие для вузов/В. Б. Байбурин - М. : ФОРУМ : ИНФРА-М, 2004. – 127 с.

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

30. Жизненный цикл программного обеспечения (ПО). Концепция программного изделия. Модели жизненного цикла ПО: каскадная, поэтапная, спиральная. Формализация и автоматизации отдельных стадий и этапов жизненного цикла. Стандартизация процесса проектирования и разработки ПО. Государственные стандарты.

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

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

33. Спецификации программного обеспечения. Внешнее проектирование ПО, принцип концептуальной целостности. Логическая модель – модель требований к ПО. Средства описания и разработки логической модели: диаграммы потоков данных, словари данных, диаграммы сущность-связь, диаграммы переходов состояний. Виды и последовательность работ при построении логической модели.

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

Состав спецификаций ПО. Проверка правильности спецификаций. Управление спецификациями: анализ, утверждение, хранение, внесение изменений.

34. Проектирование программного обеспечения. Проектирование архитектуры ПО: разработка структуры и интерфейсов компонентов, согласование функций и технических требований к компонентам, методам и стандартам проектирования. Детальное проектирование: разработка спецификаций компонентов, интерфейсов между компонентами, разработка плана комплексирования компонентов. Тестирование и отладка. Статическое тестирование компонента. Тестирование сопряжений компонент. Комплексное тестирование. Документирование тестирования и отладки. Проектирование тестов. Драйверы и заглушки.

35. Испытания и контроль качества программного обеспечения. Испытания - процесс экспериментального определения количественных и качественных характеристик ПО, как результат воздействия на него, при его функционировании. Виды испытаний и контроля качества ПО. Функциональные, приемочные, приемо-сдаточные, контрольные испытания. Цели, методы и средства проведения испытаний. Государственные стандарты в области испытаний и контроля качества ПО.

литература

1. Брукс Фредерик. Мифический человеко-месяц или как создаются программные системы:– СПб.: Символ, 2000. – 298 с.

2. Вендров А.М. CASE – технологии. Современные методы и средства проектирования информационных систем. – М. : Финансы и статистика, 1998. – 176 с.

3. Маклаков С.В. BPwin и ERwin: CASE-средства разработки информационных систем. – М. : ДИАЛОГ-МИФИ, 1999. – 256 с.

4. Орфали Р., Харки Д., Эдвардс Д. Основы CORBA: Пер. с англ. – М., МАЛИП, Горячая линия – Телеком, 1999. – 318 с.

5. С. Канер, Дж. Фолк, Енг Кек Нгуен. Тестирование программного обеспечения. – К.: Диасофт, 2000. – 544 с.

6. Калянов Г.Н. CASE структурный системный анализ (автоматизация и применение). – М.: "ЛОРИ", 1996. – 242 с.

7. Г.Буч. Объектно-ориентированный анализ и проектирование с примерами приложений на С++,– М.:" Бином", 1999. – 560 с.


Раздел 3 Специальные дисциплины


Объектно-ориентированное программирование (ООП)

1. Парадигма объектно-ориентированного подхода в программировании, инкапсуляция, наследование и полиморфизм. ООП, как средство обеспечения требований предъявляемых к современному программному обеспечению.

2. Классы и объекты. Члены класса: - данные, методы и указатель this. Статус доступа к данным и методам класса. Конструктор и деструктор, их назначение, синтаксис и вызов. Конструктор и деструктор по умолчанию, конструктор без параметров, конструктор копии, конструктор-инициализатор.

3. Перегрузка функций. Перегрузка операций (унарных, бинарных), как внутри, так и вне класса. Причины необходимости перегрузки конструктора копии и операции присваивания.

4. Производные классы. Механизмы наследования данных и методов базовых классов. Конструкторы и деструкторы производных классов. Полиморфизм и виртуальные функции, раннее и позднее связывание.

5 Стандартная библиотека потоковых классов ввода/вывода iostream. Операции вставки/извлечения <</>> . Объекты cin и cout. Форматирование данных, флаги и манипуляторы потоков. Перегрузка операций << / >> для нестандартных типов данных.

6. Шаблоны функций и классов – параметризированные типы. Синтаксис определение шаблонов семейства функций и шаблонов семейства классов.

литература

1. Подбельский В.В. Язык Си++: Учеб. пособие. - 5-е изд. – М.: Финансы и статистика, 2004, 560 с.

2. Глушаков С.В., Коваль А.В., Смирнов С.В. Язык программирования С++. –Харьков:Фолио, 2002, 500 с.

3. Павловская Т.А. C/C++ Программирование на языке высокого уровня Учебник. – СПб.: Питер 2001, 454 с.

4. Павловская Т.А., Щупак Ю.А. C++. Объектно-ориентированное программирование. Практикум. СПб.: Питер 2004.

5. Гилберт С., Маккарти Б. Самоучитель Visual C++ 6 в примерах.–К.:ООО ТИД, 2002. –496 с.

6. Хабибуллин И. Ш. Программирование на языке высокого уровня С/С++. Учебное пособие. СПб.:БХВ-Петербург, 2006, 512 с.

7. Круглински Д. и др. Программирование на Visual C++ 6 для профессионалов/ Пер. с англ. – СПб.: “Русская редакция”, 2001, -864 с.

8. Буч Г. Объектно-ориенторованный анализ и проектирование с примерами приложений на С++:– М.:" БИНОМ", 1998.

Структуры и алгоритмы обработки данных

7. Абстрактные типы данных (АТД) для создания динамических структур: - списков, очередей, стеков. Логическая структура, представление и основные операции. Спецификация, представление и реализация АТД с помощью классов и объектов языка С++.

8. Абстрактные типы для реализации деревьев. Деревья и леса, бинарные деревья. Операции, выполняемые над деревьями. Вставка и удаление поддеревьев, преобразование деревьев, алгоритмы обхода деревьев - прямой обратный и симметричные обходы.

9. Использование деревьев в задачах поиска. Бинарные деревья поиска, случайные, оптимальные и сбалансированные по высоте деревья поиска. Добавление, удаление элемента. Понятие хеш – таблицы. Внешнее и внутренне хеширование. Эффективность алгоритмов поиска на случайном, оптимальном и сбалансированном по высоте дереве.

10. Задачи сортировки. Внутренняя и внешняя сортировки. Алгоритмы сортировки; оптимальная сортировка; порядковые статистики. Анализ сложности и эффективности алгоритмов поиска и сортировки. Алгоритмы сортировок вставками, слиянием, с помощью бинарной кучи. Алгоритмы сортировок: быстрая, подсчетом, цифровая и вычёрпыванием.

11. Организация и обработка файлов, как древовидных структур. Хранение данных в файлах. Индексированные файлы. Вторичные индексы. В–деревья. Поиск, вставка и удаление записей.

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

литература

1. Сэджевик Р. Фундаментальные алгоритмы на С++. – М., DiaSoft 2002. – 970 с.

2. Хэзфилд Б., Кирби В. Исскуство программирования на С. Фундаментальные алгоритмы, структуры данных и приложения и примеры приложений. – М.. DiaSoft, 2004 – 728 с.

3. Кнут Д. Искусство программирования в 3-х томах. М.: Вильямс 2000.

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

5. Вирт Н. Алгоритмы и структуры данных. - СПб.:Невский Диалект, 2001. - 352 с.

6. Кубенский А.А. Структуры и алгоритмы обработки данных: объектно-ориентированный подход и реализация на С++. –Спб.:БХВ-Петербург, 2004, -464 с.

Теория вычислительных процессов

13. Формальные модели вычислительных процессов. Понятие дискретной динамической системы. Асинхронные процессы (АП), классы эквивалентности. Простой, эффективный, управляемый АП, его протокол и репозиция.

14. Сети Петри. Граф; маркировка; выполнение сети Петри. Пространство состояний и множество достижимости. Интерпретация АП сетью Петри. Свойства сетей Петри: безопасность, ограниченность, сохранение, активность переходов и основные задачи их анализа. Дерево достижимости и алгоритм его построения.

Моделирование систем сетями Петри. Асинхронность, мгновенность, стохастичность, параллелизм и конфликтность.

15. Конечные автоматы (КА), как модель дискретной динамической системы. Основные задачи теории конечных автоматов. Автоматы, как преобразователи информации и акцепторы (распознаватели). Понятие связности и способы задания автоматов. Специальные классы КА: - автономный, автомат Мура, автомат-часы, переходная система, автомат без памяти, без потери информации. Алгоритм построения минимального КА.

16. Управляющие автоматы. Задачи диагностики КА. Автомат Тьюринга. Этапы процесса синтеза конечных автоматов. Структурные автоматы.

17. Семантическая теория программ. Схемы программ. Методы формальной спецификации и верификации.

литература

1. Кудрявцев В.Б. Введение в теорию конечных автоматов –М.: Наука, 1985.

2. Ю.Г. Карпов. Теория автоматов. – СПб: Питер, 2003.

3. Питерсон Дж. Теория сетей Петри и моделирование систем. -М.: Наука, 1984.

4. Салихова Ю.Р. и др. Теория вычислительных процессов: учебно-методическое пособие. – Уфа: УГНТУ, 2002.;

Архитектура вычислительных систем

18. Архитектуры вычислительных систем. Классификация систем обработки данных по способу построения. Особенности организации многопроцессорных и многомашинных вычислительных систем.

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

20. Векторные, матричные, ассоциативные системы. Однородные системы и среды. CISC и RISC-архитектуры. Функционально распределенные ВС. Системы с перестраиваемой структурой.

21. Особенности архитектуры семейства процессоров Intel. Суперскалярные процессоры, процессоры со сверхдлинным командным словом.

22. Особенности архитектур современных процессоров. Системные шины. Процессоры с поддержкой технологии Hyper-Threading. Двухъядерные процессоры.

литература

1. Степанов А.Н. Архитектура вычислительных систем и компьютерных сетей. – СПб.: Питер, 2007.– 509 с.

2. Буза М.К. Архитектура компьютеров. Учебник для Вузов. Минск: Новое знание, 2007, -600 с.

4. Таненбаум Э. Архитектура компьютера. – СПб.: Питер, 2007

5. Бройдо В.Л., Ильина О.П. Архитектура ЭВМ и систем: Учебник для вузов. – СПб.:Питер, 2006

Функциональное и логическое программирование

23. Языки функционального программирования. Виды функций, композиции функций, функции с функциональными аргументами, функциональная программа. Рекурсия. Виды рекурсий. Рекурсивные функциональные программы. Вычисления с задержкой. Программы с возвратами.

24. Программирование на языке Lisp. Lisp – объекты. S- выражения. Понятие функции и предиката в Лиспе. Префиксная нотация. Базовые функции и предикаты. Диалог с интерпретатором. Блокировка вызовов. Предикаты сравнения. Функции печати. Определение функции пользователем.


25. Вычисления в Лиспе. Управляющие структуры. Типы данных Лиспа. Функции работы с типами данных. Рекурсивные программы на Лиспе. Внутреннее представление списков. Функционалы. Массивы данных.

26 Логическое программирование. Представление знаний и рассуждения. Индивидуумы, отношения, предикаты, связки и формулы, переменные, предложения. Логические следствие и вывод. Резолюция. Вычисления и исполнения логической программ. Процедурная интерпретация. Пространство вычислений. Стандартная стратегия управления. Верификация программ.


27. Общие правила языка Prolog. Структура Пролог-программы. Описание областей. Синтаксис языка. Возможность трассировки. Встроенные предикаты. Отсечение cut и предикат неудачи fail. Согласование параметров. Итерирование и рекурсия.

28. Обработка списков и строк. Представления фактов. Представление списков посредством структурированных термов. Поиск в списке. Задача о подстроке. Представления фактов. Контроль соответствия типов. Индексация. Массивы данных. Обработка данных в виде фактов. Формирование базы данных. Доступ к файлу базы данных.

литература

1. Э. Хювенен, И. Сепянен. Мир Лиспа. В 2-х томах. -М.: Мир, 1990

2. П. Хендерсон. Функциональное программирование. Применение и реализация. –М.: Мир, 1983

3. К. Хоггер. Введение в логическое программирование. – М.: Мир, 1988

4. В.Э. Вольфенгаген. Конструкции языков программирования. – М.: «Центр ЮрИнфоР», 2001

Теория языков программирования и методы трансляции

29. Введение в компиляцию и теорию формальных языков. Понятие компилятора, их виды. Модель анализа-синтеза компиляции. Лексический, синтаксический, семантический анализ. Анализ в программах форматирования текста.

30. Фазы компилятора, группировка фаз. Управление таблицей символов, обнаружение ошибок. Фазы анализа. Оптимизация кода. Препроцессоры, ассемблеры, двухпроходный ассемблер, загрузчики и редакторы связей. Группировка фаз. Проходы. Уменьшение количества проходов. Инструментарий для создания компиляторов.

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

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

33. Синтаксический анализ. Роль синтаксического анализатора. Обработка синтаксических ошибок. Контекстно-свободные грамматики. Обозначения. Порождение. Неоднозначность. Деревья разбора и приведения.

34. Разработка грамматики. Устранение неоднозначности и левой рекурсии. Построение не-контекстно-свободных грамматик. Нисходящий анализ. Анализ методом рекурсивного спуска и нерекурсивный предикатный анализ. LL(1)-, LL(k)-грамматики. Восстановление после ошибок.

литература

1. Ахо А., Сети Р., Ульман Дж. Компиляторы: принципы, технологии и инструменты. - М.: ''Вильямc'', 2001.

2. Опалева Э.А. , Самойленко В.П. Языки программирования и методы трансляции: -СПб.:BHV: 2005 : 480 с.

3. Свердлов С. Языки программирования и методы трансляции: Учебное пособие (+CD). -СПб.:БХВ-Петербург, 2007, - 484 с.

4. Хантер Р. Основные концепции компиляторов. –М.:Вильямс, 2002.

5. Бек Л. Введение в системное программирование. М., Мир, 1988

6. Дал У., Дейкстра Э., Хоор К. Структурное программирование. М., Мир, 1975

7. Зелковиц М., Шоу А., Геннон Дж. Принципы разработки программного обеспечения. М., Мир, 1982




Похожие:

Программа вступительного экзамена в магистратуру по направлению 552800 «информатика и вычислительная техника» iconПрограмма междисциплинарного вступительного экзамена в магистратуру по направлению 230100. 68 «информатика и вычислительная техника»
Программа утверждена на заседании умкн 230100. 68 «Информатика и вычислительная техника»
Программа вступительного экзамена в магистратуру по направлению 552800 «информатика и вычислительная техника» iconПрограмма междисциплинарного вступительного экзамена в магистратуру по направлению 230100. 68 «информатика и вычислительная техника»
Программа утверждена на заседании умкн 230100. 68 «Информатика и вычислительная техника»
Программа вступительного экзамена в магистратуру по направлению 552800 «информатика и вычислительная техника» iconРабочая программа дисциплины программирование на языке высокого уровня Рекомендовано Методическим советом угту-упи для направления 552800 «Информатика и вычислительная техника»
Государственным образовательным стандартом высшего профессионального образования направления 552800 «Информатика и вычислительная...
Программа вступительного экзамена в магистратуру по направлению 552800 «информатика и вычислительная техника» iconРабочая программа дисциплины программирование на языке высокого уровня Рекомендовано Методическим советом угту-упи для направления 552800 «Информатика и вычислительная техника»
Государственным образовательным стандартом высшего профессионального образования направления 552800 «Информатика и вычислительная...
Программа вступительного экзамена в магистратуру по направлению 552800 «информатика и вычислительная техника» iconПрограмма вступительного экзамена в магистратуру для направления 230100 «Информатика и вычислительная техника»
...
Программа вступительного экзамена в магистратуру по направлению 552800 «информатика и вычислительная техника» iconРабочая программа дисциплины микропроцессорные системы рекомендовано Методическим советом угту-упи для направления 552800 «Информатика и вычислительная техника»
Государственным образовательным стандартом высшего профессионального образования для направления 552800 «Информатика и вычислительная...
Программа вступительного экзамена в магистратуру по направлению 552800 «информатика и вычислительная техника» icon“Технология программирования” для направления 552800 “Информатика и вычислительная техника”
Рабочая программа составлена на основании решения кафедры “Вычислительная техника ” Ульяновского государственного технического университета...
Программа вступительного экзамена в магистратуру по направлению 552800 «информатика и вычислительная техника» iconРабочая программа дисциплины "параллельные алгоритмы и системы" Для подготовки магистров по направлению 552800 -"Информатика и вычислительная техника" всех специализаций
Для подготовки магистров по направлению 552800 -"Информатика и вычислительная техника"
Программа вступительного экзамена в магистратуру по направлению 552800 «информатика и вычислительная техника» iconПрограмма вступительного экзамена в магистратуру по направлению 230100 «Информатика и вычислительная техника»
Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования
Программа вступительного экзамена в магистратуру по направлению 552800 «информатика и вычислительная техника» iconРабочая программа дисциплины сети ЭВМ и телекоммуникации для подготовки бакалавров по направлению 552800 “Информатика и вычислительная техника”
Для подготовки бакалавров по направлению 552800 – “Информатика и вычислительная техника”
Разместите кнопку на своём сайте:
Библиотека


База данных защищена авторским правом ©lib.znate.ru 2014
обратиться к администрации
Библиотека
Главная страница