Программа государственного экзамена

Программа государственного экзамена

по направлению «ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ»

(бакалавр)

Утверждена на заседании Ученого совета факультета ВМК 2 апреля 2007 года

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

Пределы последовательностей и функций. Первый и второй замечательные пределы и следствия из них. Эквивалентные бесконечно-малые величины. Раскрытие основных неопределенностей, правила Лопиталя. Непрерывность функций одной и нескольких переменных (в точке, на множестве). Совокупная и покоординатная непрерывность. Теоремы о непрерывных функциях. Производная и дифференциал функции одной переменной. Критерий дифференцируемости функции. Дифференцируемость функции нескольких переменных. Частные производные и дифференциал функции. Производная по направлению. Необходимые и достаточные условия локального экстремума функции нескольких переменных. Условный экстремум функции нескольких переменных. Метод неопределенных множителей Лагранжа. Неопределенный и определенный интегралы. Основные приемы интегрирования функций. Геометрические приложения интегралов. Вычисление площадей плоских областей и объемов тел. Длина плоской кривой в различных координатах. Основные теоремы для криволинейных и поверхностных интегралов. Формулы Грина, Остроградского - Гаусса, Стокса. Достаточное условие регулярности функции. Представление функций рядами Тейлора.

[Ф] Алгебра и геометрия

Понятие алгебраической системы. Полугруппы, группы, кольца и поля. Гомоморфизмы и изоморфизмы алгебраических систем. Линейные векторные пространства. Линейная независимость систем векторов. Ранг систем векторов. Базис и размерность линейного пространства. Координаты вектора в базисе, изменение координат при изменении базиса. Детерминант матрицы, его свойства и способы вычисления. Матричные операции. Кольцо квадратных матриц. Способы обращения матриц. Теорема о ранге произведения матриц. Системы линейных алгебраических уравнений. Правило Крамера, метод Гаусса, условие совместности и разрешимости. Представление общего решения в виде линейного многообразия. Линейные преобразования конечномерного линейного векторного пространства и их матричное представление. Собственные числа и векторы линейного преобразования, методы их вычисления. Отношение подобия матриц. Диагонализируемые матрицы. Билинейные и квадратичные формы и их матричное представление. Каноническое представление положительно определенной квадратичной формы. Евклидовы и унитарные пространства. Процесс ортогонализации системы векторов. Аффинная и ортогональная классификация кривых и поверхностей второго порядка.

[Ф] Основы дискретной математики

Бинарные отношения. Отношения эквивалентности. Теорема о факторизации. Отношения порядка. Свойства конечных упорядоченных множеств. Функциональные отношения. Перестановки и сочетания с повторениями и без повторений. Бином Ньютона и полиномиальная теорема. Метод включений и исключений. Число разбиений множества. Понятие графа. Типы графов. Изоморфизм. Метрические характеристики графа. Деревья. Двудольные графы. Планарные графы. Функции алгебры логики, их табличное и формульное представление. Нормальные формы и полиномы. Понятие о полноте системы функций. Критерий полноты. Задача оптимального алфавитного кодирования. Свободные и префиксные коды. Алгоритм построения оптимального кода.

[Ф] Математическая логика и теория алгоритмов. Неклассические логики

Основные понятия, используемые при определении синтаксиса языка предикатов. Правила построения формул. Свободные и связанные переменные. Префиксные и антипрефиксные формы предложений. Стандартная интерпретация формул логики предикатов. Выполнимость, общезначимость, логическое следование. Объем и доля выполнимости логической формулы. Асимптотическое поведение доли выполнимости. Логический вывод. Варианты построения дедуктики. Теорема об адекватности дедуктики. Элементарные теории. Консервативное расширение теории. Расширение теории с помощью определений. Основные теоретические модели вычислений. Понятие вычислимости и алгоритмической разрешимости (варианты определений). Тезис Тьюринга-Черча. Универсальная машина Тьюринга. Типы модальностей и модальных систем. Модели Крипке. Интуиционистская логика. Математические основы нечеткой логики

[Ф] Теория автоматов и формальных языков

Конструктивные способы задания формальных языков (Формальные грамматики, конечные автоматы, регулярные выражения). Иерархия Хомского. Замкнутость класса конечно-автоматных языков относительно основных операций. Алгоритмы анализа, синтеза, детерминизации и минимизации конечного автомата. Теорема Клини о совпадении классов конечно-автоматных и регулярных языков. Решение систем линейных уравнений с регулярными коэффициентами. Описание праволинейного языка с помощью системы линейных уравнений с регулярными коэффициентами. Теорема о разрастании для регулярных языков и ее применение для доказательства нерегулярности. Класс контекстно свободных языков. Неоднозначность в КС-языках и грамматиках. Решение проблем пустоты и бесконечности для КС-языка. Соотношение между КС-языками и языками, допускаемыми магазинными автоматами. Алгоритмы синтаксического анализа для КС-языков. Лемма о разрастании для КС-языков. Пример языка, не являющегося контекстно-свободным.

[Ф] Теория конечных графов и ее приложения

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

[Ф] Дифференциальные уравнения и элементы функционального анализа

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

[Ф] Теория вероятностей и математическая статистика

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

2.  Случайные одномерные величины, функции распределения. Классификация случайных величин. Числовые характеристики случайных величин. Типовые законы распределения случайных величин.

3.  Случайные многомерные величины, функции распределения. Условные законы распределения. Частные распределения случайного вектора. Ковариация случайных величин и коэффициент корреляции.

4.  Неравенство Чебышева, закон больших чисел и предельные теоремы для сумм независимых случайных величин.

5.  Основные понятия математической статистики и выборочные характеристики. Оценивание математического ожидания, дисперсии, вероятности, статистическая функция распределения. Свойства статистических оценок Методы получения точечных оценок. Проверка простой гипотезы с использованием критерия «c-квадрат».

6.  Основные понятия о случайных процессах. Способы задания случайных процессов. Классификация случайных процессов.

[Ф] Исследование операций

Модель операции в нормальной форме. Оценка решений по гарантированному результату. Устойчивость и эффективность решений. Совместимость устойчивости и эффективности. Позиционная форма игры, переход к нормальной форме. Устойчивые решения в играх с полной информацией. Смешанное расширение конечной игры. Упрощение условий устойчивости. Существование устойчивых решений в смешанных стратегиях для 2´2 игр. Решение двойственных задач линейного программирования как седловая точка матричной игры. Сведение задачи решения матричной игры к решению задачи линейного программирования.

[Ф] Вычислительная математика Численные методы

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

[Вуз] Методы оптимизации

Линейное программирование, симплекс-метод и варианты его конкретизации, теорема двойственности. Задачи динамического программирования. Метод рекуррентных уравнений Беллмана. Условия оптимальности в гладких выпуклых задачах математического программирования. Теоремы Лагранжа, Каруша-Куна-Таккера. Вычислительные методы локальной и многоэкстремальной оптимизации. Общие методы учета ограничений равенств и неравенств. Методы внешнего штрафа.

[Ф] Информатика

Основы программирования

Структурное программирование. Операторы, реализующие основные структуры управления (на примере языков Pascal или С) Структурированные типы данных: массивы, структуры (записи), перечисления, множества. Технология модульного программирования. Использование внутренних и внешних подпрограмм. Методы работы с внешней памятью. Файлы. Основные принципы объектно-ориентированного подхода (инкапсуляция, наследование, полиморфизм). Основные понятия объектно-ориентированного программирования в языке С++ (классы, объекты, конструкторы, деструкторы, перегрузка операций).

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

Структуры данных и структуры хранения. Динамические структуры и динамическое управление памятью (перепаковка, указатели, линейные и иерархические списки). Организация доступа по имени. Упорядоченные таблицы. Таблицы с вычислимыми адресами.

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

Операционные системы и их основные функции.

Технологии баз данных

Модели баз данных. Основные функции СУБД.

Компьютерные сети

Сетевые протоколы передачи данных. Структура протокола TCP/IP.

Компьютерная графика

Структуры графических данных. Базовые средства программирования задач компьютерной графики.

Алгоритмы и сложность

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

Литература

1.  , Позняк математического анализа. – М.: Наука, 1982 , (в двух частях).

2.  Кудрявцев математического анализа. Учебник, т. 1, 2, 3 // М.: Высшая школа, 1988, 1989.

3.  и др. Сборник задач по математическому анализу. Учебное пособие в 2-х частях //М: Наука, 1984-1986, 1, 2 ч.

4.  Демидович задач и упражнений по математическому анализу. Учебное пособие //М: Наука, 1990.

5.  Беклемишев аналитической геометрии и линейной алгебры. – М.: Наука 1985.

6.  Яблонский в дискретную математику. – М.: Наука 1986.

7.  , Адельсон-Вельский математика для инженеров. М.:Энергоатомиздат,1988.

8.  Емеличев по теории графов / и др. – М.: Наука 1990.

9.  Понтрягин дифференциальные уравнения. – М.: Наука 1982.

10.  Гнеденко теории вероятности. – М.: Наука 1988.

11.  Федоткин прикладной теории вероятностей и статистики: Учебник/. – М.: Высш. шк., 2006. – 368с.: ил.

12.  , , Кобельков методы. – М.: Наука 1987.

13.  , , Методы сплайн-функций, М.: Наука 1980, 352с.

14.  , Золотых методы линейной алгебры. Лабораторный практикум. – Н. Новгород, изд. ННГУ 2006. – 198с.

15.  , Войтенко программирование в примерах и задачах. – М.: Высшая школа, 1979.

16.  Карманов программирование. – Учеб. пособие – М.: Наука, 2000.

17.  Васильев методы решения экстремальных задач. – М.:Наука, 1982.

18.  . Золотых и целочисленное линейное программирование: Учебник. – Н. Новгород, изд-во ННГУ, 2005. – 307с.

19.  , Таланов . Модели вычислений. Структуры данных: Учебник. – Н. Новгород, изд. ННГУ 2005. – 307с.

20.  , Золотых методы линейной алгебры. Лабораторный практикум. – Н. Новгород, изд. ННГУ 2006. – 198с.

21.  Стронгин операций. Модели экономического поведения: Учебник. – Нижний Новгород: изд. ННГУ, 2002. – 244с.

22.  Хопкрофт Дж. И др., 2002. Дж. Хопкрофт, Р. Мотвани, Дж. Ульман, Введение в теорию автоматов, языков и вычислений., Вильямс, 2002.

23.  И др., 1978. А. Ахо, Дж. Ульман. Теория синтаксического анализа, перевода компиляции. Т.1, Синтаксический анализ., Мир, 1978.

24.  , Языки и исчисления. М.: МЦНМО, 2000.

25.  Таланов логика и модели вычислений, Н. Новгород, изд. ННГУ 1994. – 116с.

26.  Рыжов нечетких множеств и измерения нечеткости. – М.: Диалог-ММГУ, 1998. – 116с.

27.  , , Сысоев прогаммирования. Курс на основе языка Object Pascal. - Н. Новгород: ННГУ, 2006.

28.  Практика программирования: Visual Basic, C++ Builder, Delphi. Самоучитель.– СПб.: БХВ-Петербург, 2002.

29.  и др. Методы программирования. Учебное пособие. Н. Новгород: ННГУ, 1997

30.  , . Основы операционных систем. Курс лекций. М: "Интернет-университет информационных технологий", 2004 г.

31.  , Свистунов практикум по курсу «Операционные системы»: Учебное пособие. Н. Новгород, Изд. ННГУ, 2006г, 230с.

32.  Компьютерные сети, 4-е издание. СПб: Питер, 2004.

33.  , , Мееров данных. Н. Новгород: Изд-во ННГУ, 2004.

34.  Адамс Дж. Математические основы машинной графики: Пер. с англ. - М.: Мир, 2001. 604 с.

Дополнительная литература

1.  Алгоритмы: построение и анализ.- МЦМО, 1999

2.  Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982.

3.  Мальцев и рекурсивные функции. 2-е изд., М.: Наука, 1986.

4.  , Максимова по теории множеств, математической логике и теории алгоритмов. М.: “Физико-математическая литература”, 1995.

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

6.  Язык программирования С++. – М.: Бином, 2001.

7.  Структуры данных в С++.– М. Бином, 1999.

8.  Базы данных. Модели, разработка, реализация. СПб.: Питер, 2001.

9.  OpenGL. Программирование компьютерной графики. – С. Пб: Питер, 2002. 1088 с.

10.  Никулин геометрия и алгоритмы машинной графики. – С. Пб : БХВ-Петербург, 2003. 560 с.

11.  . Операционные системы. СПб: "Питер", 2004.

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

13.  , Олифер сети. Принципы, технологии, протоколы. СПб: Питер, 1999.

14.  , , Маркина методы принятия оптимальных решений. Учебник. - Н. Новгород: ННГУ, 2002.

15.  Марчук вычислений. – М.: Наука 1980.

16.  Чистяков теории вероятности. – М.: Наука 1987.

17.  , Оврагов вероятности и ее инженерное применение. – М.: Наука 1988.

18.  , Морозов игр и модели математической экономики: Учебное пособие. – М.: МАКС Пресс, 2005. – 272с.

Для справки список курсов

[Ф] Логическое программирование

[Ф] Основы программирования

[Ф] Алгоритмы и анализ сложности

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

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

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

[Ф] Компьютерные сети

[Ф] Компьютерная графика

[Ф] Интеллектуальные системы

[Ф] Технологии баз данных

[Ф] Программная инженерия

[Ф] Социальные и этические вопросы ИТ

[Ф] Практикум на ЭВМ

[Вуз] Основы безопасности ИТ

[Выб] Технологии Сети Интернет

[Выб] Объектная распределенная обработка

[Выб] CASE - технологии и язык UML

[Выб] Суперкомпьютеры и их применение

[Спец] Методы конструирования. и разр. прогр. комплексов

[Фак] Методы принятия решений

[Фак] Системы искусств. интеллекта и принятие решений

[Фак] Программирование СИ++

[Фак] Управление дискретными процессами

[Вуз] Основы функционального анализа

[Вуз] Мат. основы криптографии

[Выб] Аналитическая геометрия

[Выб] Программирование на СИ