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

ДЛЯ ПОСТУПАЮЩИХ В МАГИСТРАТУРУ

ПО СПЕЦИАЛЬНОСТИ

1-40 80 03 «Вычислительные машины и системы»

АВТОР:

Родченко В.Г., кандидат технических наук, доцент, заведующий кафедрой

программного обеспечения интеллектуальных и компьютерных систем

УО «ГрГУ им. Я.Купалы»

РЕЦЕНЗЕНТ:

Изосимова Т.Н., кандидат физико-математических наук, доцент, заведующий кафедрой информатики и экономико-математических методов в АПК УО «ГГАУ».

Рекомендована к утверждению учебно-методической комиссией факультета математики и информатики Протокол № 3 от «16» марта 2010 г.

Рекомендована к утверждению Советом факультета математики и информатики Протокол № 3 от «17» марта 2010 г.

ПОЯСНИТЕЛЬНАЯ ЗАПИСКА

Настоящая программа предназначена для подготовки и сдачи вступительного экзамена в магистратуру Учреждения образования «Гродненский государственный университет им. Янки Купалы» по специальности 1-40 80 03 «Вычислительные машины и сети».

Программа для поступающих в магистратуру по специальности 1-40 80 03 «Вычислительные машины и сети» разработана на основе образовательных стандартов высшего образования Республики Беларусь данной специальности и смежных специальностей;

в соответствии с действующими программами дисциплин учебных планов Гродненского государственного университета имени Янки Купалы.

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

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

Программа включает вопросы по 4 разделам – «Теоретические основы информатики», «Архитектуры вычислительных машин и систем», «Технологии разработки программных систем», «Модели данных и СУБД».

Программа снабжена списком обязательной (28 названий) и дополнительной (10 названий) литературы, в которые включены современные и классические учебные издания и работы, ссылки на современные Интернет-ресурсы.

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

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

СОДЕРЖАНИЕ

Теоретические основы информатики Элементы дискретной математики и математической логики Комбинаторный анализ. Множества, покрытия и разбиения множеств. Операции над множествами. Размещения, размещения с повторениями. Сочетания, сочетания с повторениями.

Бином Ньютона. Булевы функции. Полные системы функций в P2 и Рk (k>= 3), замкнутые классы в этих системах. Критерии полноты систем булевых функций, их особенности. Теорема о минимальном базисе. Понятие схемы из функциональных элементов. Предикатные формулы.

Интерпретации. Тождественно-истинные формулы. Проблема разрешения. Алгоритмические модели. Понятие машины Тьюринга (одноленточная детерминированная). Понятие вычислимости. Классы Р и NР. Проблема Р = NP. NP-полные проблемы.

Элементы теории графов Графы. Типы графов. Маршруты и связность. Деревья. Описания деревьев. Связность, реберная связность, разбиения. Плоские и планарные графы. Характеристики планарных графов.

Описание графов матрицами связности и инцидентности. Перечисления. Помеченные графы.

Перечисления графов, деревьев. Орграфы. Орграфы и соединимость. Орграфы и матрицы.

Элементы теории информации Основополагающие результаты К.Шеннона. Мера информации. Энтропия. Условная энтропия.

Преобразование информации: кодирование, сжатие и шифрование. Элементы теории чисел.

Простые числа, методы их получения. Методы генерирования псевдослучайных чисел. Теория вычислительной сложности. Теория эквивалентного преобразования алгоритмов.

Архитектуры вычислительных машин и систем Организация и функционирования компьютера Основные устройства компьютера. Процессоры. Материнские платы. Средства долговременного хранения данных. Вспомогательные устройства. RISC и CISC архитектуры. Архитектура процессоров семейства x86. Система прерываний. Организация функционирования системы прерываний. Оперативная память современного компьютера. Типы памяти. Архитектура оперативной памяти. Типы адресации. Средства долговременного хранения данных.

Многопроцессорные вычислительные системы. Многомашинные вычислительные системы.

Современные распределнные вычислительные системы.

Системное программное обеспечение Классификация программного обеспечения (ПО). Классификация системного ПО. Группы системных программ, их назначение и требования к ним. Файловые системы и их разновидности. Особенности файловых систем: FAT, VFAT FAT32, HPFS, NTFS, UNIX System V (s5), UNIX BSD (ufs), UNIX V7.

Понятие операционной системы (ОС). Назначение и основные функции ОС. Операционная среда. Понятие процесса. Задачи управления процессами. Понятие ресурса. Концепция виртуализации ресурсов. Планирование вычислительных процессов. Классификация ОС. ОС мэйнфреймов. Серверные ОС. Многопроцессорные ОС. ОС для ПК. ОС реального времени.

Встроенные ОС. ОС для смарт-карт. Архитектура ОС. Микроядерные и монолитные ОС. ОС реального времени. Мультимедийные ОС. Многопроцессорные системы. Сетевые ОС. Понятие виртуальной машины.

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

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

Сетевые архитектуры:Ethernet, Token Ring, ArcNet. Основные характеристики сетевых архитектур. Формат кадра. Функционирование. Аппаратные компоненты. Стандарты.

Структура Internet. Адресация в Internet. Основы семейства протоколов TCP/IP. Характеристика основных типов серверов Internet (Word Wide Web, FTP). Гипертекст. Инструменты и языки для создания гипертекстовых документов.

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

Процедурно-ориентированное программирование. Машинно-ориентированное программирование. Функциональное программирование. Логическое программирование.

Объектно-ориентированное программирование: классы, объекты, конструкторы и деструкторы, методы, свойства, наследование, виртуальные методы, шаблоны. Расширяемое программирование. Визуальное программирование. Компонентное программирование.

Концепции объектно-ориентированного программирования в различных языках программирования.

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

Прошивка деревьев. Деревья двоичного поиска. Алгоритмы на графах. Алгоритмы обхода графов. Алгоритм Дейкстры. Методы анализа алгоритмов. Алгоритмы «разделяй и властвуй».

Динамическое программирование. Поиск с возвратом. Алгоритмы локального поиска.

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

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

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

Полиморфизм. Множественное наследование. Общие конструкции языка С и С++. Не связанные с объектами расширения С++ относительно С. Инициализация объектов. Виртуальные функции.

Встроенные функции. Перегружаемые функции и функции с аргументами по умолчанию.

Автоматические, динамические и статические объекты. Параметризация классов и шаблоны функций. Потоки ввода-вывода. Ввод и вывод типов пользователя. Файловый ввод-вывод.

Уникальные свойства конструкторов и деструкторов. Механизмы обработки ошибок и исключительных ситуаций в С++. Основные компоненты объектного подхода при разработке ПО. Объектно-ориентированное проектирование в жизненном цикле разработки.

Технологии разработки программного обеспечения Жизненный цикл (ЖЦ) программных средств (ПС): стратегии разработки ПС, модели ЖЦ, влияние модели ЖЦ на технологию разработки ПС. Структурный подход к проектированию ПС.

Классические технологии проектирования программных средств: модульное проектирование, нисходящее проектирование, восходящее проектирование. Оценка эффективности структурного разбиения программ на модули. Современные структурные технологии разработки программных средств: методологии и нотации визуального моделирования и проектирования программных средств, функциональное моделирование (IDEF0), информационное моделирование (IDEF1), метод Джексона. Объектно-ориентированный подход к проектированию ПС. Унифицированный язык моделирования UML. Построение диаграмм UML. Генерация программного кода в среде Rational Rose.

Методы и средства защиты программ и данных Основные понятия компьютерной безопасности. Криптографические методы защиты информации. Потоковое и блочное шифрование. Симметричное шифрование. Алгоритм DES.

Ассиметричное шифрование. Алгоритм шифрования RSA. Обмен ключами. Однонаправленные функции, функции хеширования. Защита информации в операционных системах.

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

Стеганографические методы защиты авторского права на программное обеспечение.

Модели данных и СУБД Объект, модель, данные, знания, физическое представление. Модели представления данных.

Языки описания и обработки данных. Нормализация отношений. Транзакции и целостность баз данных. Представление знаний. Компиляторы SQL.

Структура, состав, принцип работы СУБД, классификация. Иерархические, сетевые, реляционные и объектно-ориентированные базы данных. Понятие физического и логического представления баз данных. Языковые средства СУБД. Распределенные СУБД. Безопасность и надежность. Администрирование. Системы «клиент-сервер».

Принципы логического проектирования баз данных. Модель "сущность-связь". Теория проектирования реляционных схем баз данных. Средства манипулирования данными в реляционных моделях (реляционная алгебра, реляционное счисление, язык SQL).

Информационные системы. Системы искусственного интеллекта, экспертные системы;

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

ПЕРЕЧЕНЬ

ОСНОВНОЙ И ДОПОЛНИТЕЛЬНОЙ

РЕКОМЕНДУЕМОЙ ЛИТЕРАТУРЫ

1. Ахо А.В., Ульман Д., Хопкрофт Дж. Построение и анализ вычислительных алгоритмов. - М. Мир, 2. Бауэр Ф.Л., Гооз Г. Информатика: вводный курс. В 2-х ч. - М. Мир, 1986.

3. Братко И. Программирование на языке Пролог для искусственного интеллекта. - М. Мир, 1990.

4. Буч Г. Объектно-ориентированный анализ и проектирование с примерами приложений на С++, 2е изд. – М.,СПб.: “Издательство БИНОМ” – “Невский диалект”, 2000.–560с.

5. Васкевич Дж. Системы клиент-сервер. - К. Диалектика, 1996.

6. Вирт Н. Алгоритмы и структуры данных. - М. Мир, 1989.

7. Дейт К. Введение в системы баз данных. - М. Наука, 1980.

8. Липаев В.В Тестирование программ. - М. Радио и связь, 1986 - 296 с.

9. Рейуорд-Смит В.Дж. Теория формальных языков. Вводный курс: Пер. с англ. М.: Радио и связь, 1988 - 128 с.

10. Ульман Д.Д. Основы систем баз данных. - М. Мир, 1985.

11. Хювенен Э., Сеппянен Й. Мир Лиспа. В2-х т. - М. Мир, 1990.

12. Эллис М., Строуструп Б. Справочное пособие по языку программирования С++ с комментариями. - М. Мир, 1992.

13. Яблонский С.В. Введение в дискретную математику. – М.:Мир, 2001.

14. Буза М.К. Архитектура компьютера. - Мн.: Новое знание, 2007 - 560 с.

15. Буч Г., Рамбо Д., Джекобсон А. Язык UML. Руководство пользователя: Пер. с англ. – М.:ДМК Пресс, 2001.

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

17. Гордеев А.В., Молчанов А.Ю. Системное программное обеспечение. - СПб.: Питер, 2001 - 736 с.

18. Змитрович А.И. Интеллектуальные информационные системы. Мн.: НТООО 19. Корнеев В.В., Гареев А.Ф., Васютин С.В., Райх В.В. Базы данных. Интеллектуальная обработка информации. - М.: «Нолидж», 2000 - 352 с.

20. Лафоре Р. Объектно-ориентированное программирование в С++. Классика Computer Science. 4-е изд. - СПб.: Питер, 2003 - 928 с.

21. Прата С. Язык программирования С++. Лекции и упражнения. Учебник: Пер. с англ. / Стивен Прата - СПб.: ООО «ДиаСофтЮП», 2005 - 1104 с.

22. Рихтер Дж. Windows для профессионалов: создание эффективных Win32-приложений с учетом специфики 64-разрядной версии Windows / Пер. с англ.- 4-е изд.- СПб: Питер; М.: Издательскоторговый дом "Русская Редакция", 2004 - 749 с.

23. Таненбаум Э. Архитектура компьютера. - СПб., Питер, 2002 - 992 с.

24. Таненбаум Э. Компьютерные сети. 4-е изд. - СПб., Питер, 2003 - 992с.

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

26. Троелсен Э. Язык программирования C# 2005 и платформа.NET 2.0 - М.: Вильямс, 2007 - 1167с.

27. Шнайер Б. Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си.

М., Издательство ТРИУМФ, 2002 - 816 с.

28. Юров В., Хорошенко С. Assembler: учебный курс СПб: Питер Ком, 1999 - 672 с.

1. Лафоре Р. Объектно-ориентированное программирование в С++. Классика Computer Science. 4-е изд. СПб.: Питер, 2003 - 928 с.

2. Страуструп Б. Язык программирования С++. – М.: СПб. “Издательство БИНОМ” – “Невский Диалект”, 2002 – 1099 с.

3. Троелсен Э. C# и платформа.NET. Библиотека программиста. – СПб: Питер Пресс, 2002 - 800 с.

4. Энджел Й. Практическое введение в машинную графику. - М. :Радио и связь, 1984.

5. Сетевые операционные системы / В.Г. Олифер, Н.А. Олифер. СПб.: Питер, 2002 544 с.

6. Страуструп Б. Язык программирования С++. СПб.: Бином–Пресс, 2007 1104 с.

7. Ахо А.В. Ульман Д. Теория синтаксического анализа, перевода и компиляции. В 2-х т. М. Мир, Ковальски Р. Логика в решении проблем. М. Наука, 1990 - 280 с.

9. Мощенский В.А. Лекции по математической логике. - Мн. БГУ, 10. Уотермен Д. Руководство по экспертным системам. М. Мир, 1989 - 390 с.