Geum.ru

Программа вступительных испытаний в магистратуру по направлению 010200. 68 Математика. Прикладная математика «Математический анализ»

Вид материалаПрограмма

Содержание


2. Указатели. Указатель – средство хранения адреса. Имена указателей. Оператор разыменовывания. Использование адреса, хранящегос
Часть 2. Микро- и макроэкономическая статистика
Мировые информационные ресурсы Компьютеры, сети и приложения, построенные на их основе.
Проектирование баз данных.
Всемирная информационная сеть – Internet.
Протоколы интернет
Программирование WWW.
Основы XML
Программа вступительных испытаний
Дифференциальные уравнения
Глава 1. Задачи 2.1-2.31.
Глава 1. Задачи 3.21, 3.24.
Глава 2. Задачи 6.2, 6.4.
Глава 4. Задачи 1.14, 1.2, 1.3.
Глава 4. Задачи 1.6-1.11.
Справочник по теории вероятностей и математической статистике.
Сборник задач по теории вероятностей, математической статистике и теории случайных функций.
1. Атомно-молекулярное учение. основные этапы развития химии
2. Строение атома. периодический закон и периодическая система д.и.менделеева
3. Химическая связь. строение и свойства вещества
...
Полное содержание
Подобный материал:
  1   2   3   4   5   6   7   8

Программа

вступительных испытаний в магистратуру

по направлению 010200.68 – Математика. Прикладная математика

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


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

  1. Предел числовой последовательности. Основные свойства: единственность предела; ограниченность сходящейся последовательности; сходимость подпоследовательности сходящейся последовательности. Предел и арифметические операции. Принцип Больцано  Вейерштрасса. Критерий Коши сходимости числовой последовательности.
  2. Предел и непрерывность функции. Эквивалентные определения (по Коши и по Гейне). Основные свойства непрерывных функций. Связь с арифметическими операциями. Непрерывность композиции. Односторонние пределы и односторонняя непрерывность.
  3. Теорема Вейерштрасса об ограниченности и о достижении экстремальных значений функции непрерывной на отрезке. Теорема Коши о промежуточных значениях непрерывной функции. Непрерывность обратной функции.
  4. Дифференцируемость числовой функции. Производная и дифференциал. Непрерывность дифференцируемой функции. Геометрический смысл производной. Дифференцируемость и арифметические операции. Дифференцируемость композиции и обратной функции.
  5. Теоремы Ферма, Ролля, Коши и Лагранжа о дифференцируемых функциях. Необходимые и достаточные условия экстремума функции в терминах производной.
  6. Интеграл Римана. Основные свойства интеграла: линейность, монотонность, аддитивность. Классы функций интегрируемых по Риману.
  7. Числовые ряды. Понятие сходимости числового ряда Необходимое условие сходимости. Признаки сравнения, Коши и Даламбера сходимости положительных рядов. Признак Лейбница сходимости знакопеременного ряда.
  8. Степенные ряды. Теорема Коши  Адамара о структуре области сходимости степенного ряда. Радиус и интервал сходимости. Равномерная сходимость степенных рядов. Теорема Абеля о равномерной сходимости степенного ряда на отрезке, содержащемся в интервале сходимости. Непрерывность суммы степенного ряда. Почленное дифференцирование и интегрирование степенных рядов.


Дифференциальные уравнения

  1. Линейное уравнение n-ого порядка с постоянными коэффициентами. Методы нахождения общего решения.


Теория функций комплексного переменного

  1. Моногенные и голоморфные функции. Критерии моногенности и голоморфности. Изолированные особые точки и вычеты.



Литература к разделу

Ма­те­ма­ти­че­ский ана­лиз
  1. Ильин В.А., Садовничий В.А., Сендов Б. Х. Математический анализ. М., 1981;
  2. Кудрявцев Л.Д. Курс математического анализа. М. 1981;
  3. Гусев А.И. Обзорные лекции по математическому анализу. Сервер локальной сети ТвГУ М:\Для студентов А.И. Гусева\ 5 курс.


Литература к разделу

Диф­фе­рен­ци­аль­ные урав­не­ния


1. Петровский И.Г. Лекции по теории обыкновенных дифференциальных уравнений. М.: Наука, 1970.

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

3. Арнольд В.И. Обыкновенные дифференциальные уравнения. М.: Наука, 1976.

4. Федорюк М.В. Обыкновенные дифференциальные уравнения. М.: Наука, 1985.

6. Филлипов А.В. Сборник задач по дифференциальным уравнениям. М., Наука, 1975.

Литература к разделу

Тео­рия функ­ций ком­плекс­но­го пе­ре­мен­но­го
  1. Шабат Б.В. Введение в комплексный анализ. Т.1. М., 1969 и другие издания.
  2. Привалов И.И. Введение в теорию функций комплексного переменного. М, 1984 и другие издания.
  3. Сидоров Ю.В., Федорюк М.В., Шабунин М.И. Лекции по теории функций комплексного переменного. М., 1982 и другие издания.
  4. Голубев А.А., Граф С.Ю., Шеретов В.Г. Практический курс комплексного анализа Тверь, 2003.
  5. Маркушевич А.Н. Краткий курс теории аналитических функций. М., 1978 и другие издания.
  6. Евграфов М.А. Аналитические функции. М, 1991 и другие издания.
  7. Волковыский Л.И., Лунц Г.Л., Араманович И.Г. Сборник задач по теории функций комплексного переменного. М., 1975.



Программа

вступительных испытаний в магистратуру

по направлению 010200.68– Математика. Прикладная математика

«Методы оптимизации и оптимального управления»


Математический анализ
  1. Предел числовой последовательности. Основные свойства: единственность предела; ограниченность сходящейся последовательности; сходимость подпоследовательности сходящейся последовательности. Предел и арифметические операции. Принцип Больцано  Вейерштрасса. Критерий Коши сходимости числовой последовательности.
  2. Предел и непрерывность функции. Эквивалентные определения (по Коши и по Гейне). Основные свойства непрерывных функций. Связь с арифметическими операциями. Непрерывность композиции. Односторонние пределы и односторонняя непрерывность.
  3. Теорема Вейерштрасса об ограниченности и о достижении экстремальных значений функции непрерывной на отрезке. Теорема Коши о промежуточных значениях непрерывной функции. Непрерывность обратной функции.
  4. Дифференцируемость числовой функции. Производная и дифференциал. Непрерывность дифференцируемой функции. Геометрический смысл производной. Дифференцируемость и арифметические операции. Дифференцируемость композиции и обратной функции.
  5. Теоремы Ферма, Ролля, Коши и Лагранжа о дифференцируемых функциях. Необходимые и достаточные условия экстремума функции в терминах производной.
  6. Интеграл Римана. Основные свойства интеграла: линейность, монотонность, аддитивность. Классы функций интегрируемых по Риману.
  7. Числовые ряды. Понятие сходимости числового ряда Необходимое условие сходимости. Признаки сравнения, Коши и Даламбера сходимости положительных рядов. Признак Лейбница сходимости знакопеременного ряда.
  8. Степенные ряды. Теорема Коши  Адамара о структуре области сходимости степенного ряда. Радиус и интервал сходимости. Равномерная сходимость степенных рядов. Теорема Абеля о равномерной сходимости степенного ряда на отрезке, содержащемся в интервале сходимости. Непрерывность суммы степенного ряда. Почленное дифференцирование и интегрирование степенных рядов.


Дифференциальные уравнения

1. Линейное уравнение n-ого порядка с постоянными коэффициентами. Методы нахождения общего решения.


Вариационное исчисление и методы оптимизации
  1. Конечномерные задачи минимизации.
  2. Выпуклые множества. Теорема Куна – Таккера. Понятие седловой точки, ее свойства.
  3. Задача оптимального управления. Понятие допустимого процесса, локально оптимального процесса. Классификация задач оптимального управления.
  4. Принцип максимума Понтрягина.
  5. Двойственный метод. Теорема Гамильтона-Якоби.
  6. Двойственная задача оптимального управления. Метод построения решения двойственной задачи.
  7. Уравнение Беллмана. Принцип оптимальности Беллмана. Связь метода Беллмана с методом Гамильтона-Якоби.
  8. Связь метода Беллмана с принципом максимума Понтрягина.
  9. Дискретная задача оптимального управления. Необходимое условие оптимальности в дискретной задаче оптимального управления.
  10. Необходимые условия оптимальности (Теорема Лагранжа). Предельный переход.
  11. Численные методы решения задач оптимального управления. Метод функции штрафа.


Литература к разделу

Математический анализ
  1. Ильин В.А., Садовничий В.А., Сендов Б. Х. Математический анализ. М., 1981;
  2. Кудрявцев Л.Д. Курс математического анализа. М. 1981;
  3. Гусев А.И. Обзорные лекции по математическому анализу. Сервер локальной сети ТвГУ М:\Для студентов А.И. Гусева\ 5 курс.


Литература к разделу

Диф­фе­рен­ци­аль­ные урав­не­ния

1. Петровский И.Г. Лекции по теории обыкновенных дифференциальных уравнений. М.: Наука, 1970.

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

3. Арнольд В.И. Обыкновенные дифференциальные уравнения. М.: Наука, 1976.

4. Федорюк М.В. Обыкновенные дифференциальные уравнения. М.: Наука, 1985.

6. Филлипов А.В. Сборник задач по дифференциальным уравнениям. М., Наука, 1975.

Литература к разделу

Вариационное исчисление и методы оптимизации

  1. Андреева Е.А., Цирулева В.М. Вариационное исчисление и методы оптимизации. М.: Высшая школа, 2006.
  2. Андреева Е.А., Цирулева В.М. Численные методы решения задач оптимального управления. Тверь: МЭСИ, 2004.
  3. Васильев Ф.П. Численные методы решения экстремальных задач. М.: Наука, 1989.


Программа

вступительных испытаний в магистратуру

по направлению 010400.68 Информационные технологии


Алгебра и геометрия
  1. Системы линейных уравнений. Метод Гаусса решения систем линейных уравнений. Определитель матрицы. Свойства определителя. Метод Крамера решения систем линейных уравнений.
  2. Линейные пространства. Линейная зависимость и линейная независимость систем векторов. Базис и ранг системы векторов. Матрица перехода от одного базиса к другому. Координаты вектора в базисе. Изменение координат вектора при изменении базиса.
  3. Кольцо многочленов. Делимость многочленов. Наибольший общий делитель двух многочленов. Алгоритм Евклида нахождения наибольшего общего делителя.
  4. Линейные преобразования линейных пространств. Матрица линейного преобразова­ния в базисе. Изменение матрицы линейного преобразования при изменении базиса.
  5. Собственные числа и собственные векторы линейного преобразования. Характери­стический многочлен линейного преобразования. Нахождение собственных чисел и собственных векторов линейного преобразования.
  6. Евклидовы пространства. Симметрические преобразования. Нахождение ортонормированного базиса, состоящего из собственных векторов симметрического преобра­зования.
  7. Квадратичные формы. Приведение квадратичной формы к каноническому и нор­мальному виду. Метод Лагранжа и метод Якоби. Положительно определённые квад­ратичные формы. Критерий Сильвестра.
  8. Гиперповерхности второго порядка в евклидовом пространстве. Классификация ги­перповерхностей второго порядка.

Задачи
  1. Вычислите определитель матрицы размера п х п.
  2. Для данной системы векторов арифметического пространства найдите базис и ранг этой системы.
  3. Даны два многочлена из R[x]. Найдите наибольший общий делитель этих многочле­нов.
  4. Даны два базиса линейного пространства. Найдите матрицу перехода от первого базиса ко второму.
  5. Даны координаты вектора x в базисе E и матрица перехода от базиса A к базису E. Найдите координаты вектора x в базисе A.
  6. Дана матрица линейного преобразования ϕ линейного пространства Rn в базисе E и матрица перехода от базиса E к базису A. Найдите матрицу преобразования ϕ в базисе A.
  7. Дана матрица линейного преобразования ϕ линейного пространства Rn в некотором базисе E. Найдите собственные числа и собственные векторы преобразования ϕ.
  8. Дана квадратичная форма. Приведите её к каноническому виду.
  9. Дана квадратичная форма. Выясните, является ли она положительно определённой.
  1. Дано уравнение поверхности второго порядка в R3. Определите тип этой поверхно­сти.


Литература
  1. Курош А.Г. Курс высшей алгебры. М.: Наука, 1975.
  2. Глухов М.М., Елизаров В.П., Нечаев А.А. Алгебра: Учебник. В 2-х т.-М.: Гелиос АРВ, 2003.
  3. Кострикин А.И. Введение в алгебру. М.: Наука, учебник, 1977.
  4. Фаддеев Д.К., Соминский И.С. Сборник задач по высшей алгебре. М.: Наука, 1977.
  5. Сборник задач по алгебре. Под ред. А.И.Кострикина, М.: Наука, 1995.
  6. Мальцев А.И. Основы линейной алгебры. М.: Наука, 1970.
  7. Калужнин А.Г. Введение в общую алгебру. М.: Наука, 1973
  8. Скорняков Л.А. Элементы общей алгебры. М.: Наука, 1983.
  9. Фаддеев Д.К. Лекции по алгебре. М.: Наука, 1984.



  1. Куликов Л.Я. Алгебра и теория чисел. М.: Высшая школа, 1979.
  2. Проскуряков И.В. Сборник задач по линейной алгебре. М.: Юнимедиастайл, 2002.


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

1. Введение в анализ.
  1. Вещественные числа. Десятичная запись вещественного числа. Свойства веще­ственных чисел. Аксиома Архимеда. Свойство непрерывности.
  2. Верхняя и нижняя грани числового множества, их характеристические свой­ства. Теорема о существовании верхней (нижней) грани у ограниченного сверху (снизу) числового множества.
  3. Ограниченные отображения, верхняя и нижняя грани отображения.

2. Предел последовательности.

2.1. Предел числовой последовательности, теорема о единственности предела чис­ловой последовательности.
  1. Бесконечно малые, бесконечно большие последовательности, их свойства. Арифметические свойства сходящихся последовательностей.
  2. Предельный переход в неравенствах. Теорема о существовании предела у огра­ниченной монотонной последовательности. Число “е”.
  3. Теорема Больцано–Вейерштрасса о существовании частичного предела у огра­ниченной числовой последовательности. Верхний и нижний пределы последо­вательности.
  4. Критерий Коши сходимости последовательности.

3. Предел функции.
  1. Предел функции в точке по Гейне и по Коши; эквивалентность этих определе­ний. Односторонние пределы в точке. Арифметические операции над функци­ями, имеющими предел.
  2. Критерий Коши существования предела функции в точке.
  3. Замечательные пределы.
  4. Бесконечно малые и бесконечно большие функции, теоремы о них. Сравнение бесконечно малых функций. Эквивалентные бесконечно малые функции.
  5. Теорема о пределе сложной функции.

4. Непрерывность функции.
  1. Непрерывность функции в точке. Односторонняя непрерывность. Арифметиче­ские операции над непрерывными функциями.
  2. Свойство устойчивости знака непрерывной в точке функции.
  3. Свойство локальной ограниченности непрерывной в точке функции.
  4. Непрерывность элементарных функций.
  5. Точки разрыва функции и их классификация. Теорема о точках разрыва моно­тонной на отрезке функции.
  6. Первая теорема Коши (о прохождении непрерывной функции через нуль при смене знаков).
  7. Вторая теорема Коши (о промежуточных значениях непрерывной на отрезке функции).
  8. Первая теорема Вейерштрасса (об ограниченности непрерывной на отрезке функции).
  9. Вторая теорема Вейерштрасса (о достижении верхней и нижней граней непре­рывной на отрезке функцией).



  1. Равномерная непрерывность. Теорема Кантора о равномерной непрерывности функции, непрерывной на отрезке.
  2. Свойства открытых и замкнутых множеств. Компакт.
  3. Теорема о равномерной непрерывности функции, непрерывной на компакте.

5. Производная и дифференциал.
  1. Производная, ее геометрический смысл. Односторонние производные.
  2. Непрерывность функции, дифференцируемой в точке.
  3. Производная суммы, произведения и частного двух функций.
  4. Производная сложной и обратной функций. Дифференцирование функции, за­данной параметрически.
  5. Производные элементарных функций.
  6. Производные высших порядков. Формула Лейбница.
  7. Дифференциал функции, геометрический смысл дифференциала. Правила вы­числения дифференциала. Инвариантность формы первого дифференциала.
  8. Дифференциалы высших порядков.
  9. Лемма Дарбу о возрастании или убывании функции в точке.



  1. Теорема Ферма о локальном экстремуме функции.
  2. Теорема Ролля о нуле производной.
  3. Теорема Лагранжа (формула конечных приращений).
  4. Теорема Коши (обобщенная формула конечных приращений).
  5. Первое и второе правило Лопиталя.
  6. Формулы Тейлора и Маклорена с остаточным членом в форме Пеано.
  7. Формула Тейлора с остаточным членом в форме Лагранжа.
  8. Разложение элементарных функций по формуле Маклорена.
  9. Необходимое и достаточное условия локального экстремума.
  10. Выпуклость графика функции. Достаточное условие выпуклости графика функции.
  11. Необходимое и достаточное условия точки перегиба.
  12. Асимптоты графика функции. Необходимое и достаточное условие существова­ния наклонной асимптоты.

6. Неопределенный интеграл.
  1. Первообразная и неопределенный интеграл. Основные свойства неопределенно­го интеграла. Таблица интегралов.
  2. Замена переменной в неопределенном интеграле. Формула интегрирования по частям.
  3. Интегрирование рациональных дробей.
  4. Интегрирование тригонометрических выражений, универсальная тригономет­рическая подстановка.
  5. Интегрирование простейших иррациональных функций.

7. Определенный интеграл.
  1. Определенный интеграл Римана. Неинтегрируемость по Риману неограничен­ной на [а,в] функции.
  2. Верхняя и нижняя интегральные суммы Дарбу, их основные свойства. Верхний и нижний интегралы Дарбу, их свойства. Основная лемма Дарбу.
  3. Необходимые и достаточные условия интегрируемости функции по Риману. Тео­рема об интегрируемости непрерывной функции. Теорема об интегрируемости монотонной функции.
  4. Свойства определенного интеграла.
  5. Оценка определенных интегралов. Интегрирование неравенств. Первая теорема среднего значения.
  6. Интеграл с переменным верхним пределом. Производная интеграла по перемен­ному верхнему пределу. Формула Ньютона – Лейбница.
  7. Замена переменной под знаком определенного интеграла. Правило интегриро­вания по частям для определенного интеграла.
  8. Приложения определенного интеграла: вычисление площадей; вычисление дли­ны дуги кривой.

8. Несобственные интегралы.
  1. Несобственные интегралы первого и второго рода. Критерий Коши сходимости несобственных интегралов.
  2. Абсолютная и условная сходимость несобственных интегралов.
  3. Признаки сходимости несобственных интегралов (общий и частный признаки сравнения).

9. Числовые ряды.
  1. Числовой ряд, сходимость и расходимость. Гармонический ряд. Необходимое условие сходимости ряда. Арифметические действия со сходящимися рядами. Критерий Коши сходимости числового ряда.
  2. Признаки сравнения числовых рядов. Признаки Даламбера и Коши сходимости ряда.
  3. Абсолютная и условная сходимость ряда. Переместительный закон для абсо­лютно сходящегося ряда.

9.4. Признак Лейбница сходимости знакочередующегося ряда.
10. Функциональные последовательности и ряды.
  1. Функциональные последовательности и ряды. Поточечная и равномерная схо­димость последовательностей и рядов.
  2. Критерий Коши равномерной сходимости последовательности и ряда. Необходи­мое условие равномерной сходимости ряда. Признак Вейерштрасса равномерной сходимости функционального ряда.
  3. Теорема о непрерывности суммы (предельной функции) равномерно сходяще­гося ряда (функциональной последовательности).
  4. Теорема об интегрируемости суммы (предельной функции) равномерно сходя­щегося на [а,в] ряда (функциональной последовательности).
  5. Теорема о дифференцируемости суммы (предельной функции) сходящегося на [а,в] ряда (функциональной последовательности).
  6. Степенные ряды. Первая теорема Абеля. Радиус и интервал сходимости сте­пенного ряда. Теорема о радиусе сходимости степенного ряда. Формулы для вычисления радиуса сходимости степенного ряда.
  7. Функция, аналитическая в точке. Единственность представления аналитиче­ской в точке функции степенным рядом. Теорема о почленном дифференцировании интегрировании степенного ряда.
  8. Ряды Тейлора и Маклорена. Необходимое и достаточное условие разложимости функции в степенной ряд. Пример бесконечно дифференцируемой функции, не являющейся аналитической. Разложение в ряд Маклорена некоторых элемен­тарных функций.

11. Функции нескольких переменных.
  1. Предел последовательности точек пространства Rn. Лемма о сходимости после­довательности точек в пространстве Rn. Лемма о фундаментальной последова­тельности; критерий Коши сходимости последовательности точек пространства Rn. Теорема Больцано – Вейерштрасса.
  2. Предел функции n переменных в точке по Гейне и по Коши; эквивалентность этих определений. Арифметические операции над функциями, имеющими пре­дел. Бесконечно малые функции n переменных.
  3. Критерий Коши существования предела функции n переменных в точке.
  4. Повторные пределы.
  5. Непрерывность функции нескольких переменных в точке. Арифметические опе­рации над непрерывными функциями. Непрерывность сложной функции.
  6. Теорема об устойчивости знака непрерывной в точке функции. Теорема о про­хождении непрерывной функцией через любое промежуточное значение.
  7. Первая теорема Вейерштрасса (об ограниченности функции, непрерывной на компакте).
  8. Вторая теорема Вейерштрасса (о достижении непрерывной на компакте функ­цией своих точных граней).
  9. Равномерная непрерывность функции нескольких переменных. Теорема Канто­ра о равномерной непрерывности функции, непрерывной на компакте.



  1. Частные производные. Дифференцируемость функции нескольких переменных. Теорема о существовании частных производных дифференцируемой в точке функции.
  2. Непрерывность дифференцируемой в точке функции. Достаточное условие дифференцируемости функции в точке. Дифференциал функции нескольких пере­менных.
  3. Дифференцирование сложной функции. Однородные функции степени p. Тео­рема Эйлера об однородных функциях. Инвариантность формы первого диффе­ренциала.
  4. Производная по направлению. Градиент. Теорема о производной функции по направлению градиента.
  5. Частные производные высших порядков. Достаточное условие равенства сме­шанных производных (случай функции двух переменных и случай функции n переменных). Дифференциалы высших порядков.
  6. Формула Тейлора с остаточным членом в форме Лагранжа. Формула Тейлора с остаточным членом в форме Пеано (без доказательства).
  7. Понятие локального экстремума. Необходимое условие локального экстремума.
  8. Достаточное условие локального экстремума.
  9. Условный экстремум. Метод множителей Лагранжа, необходимое условие ло­кального экстремума.
  10. Достаточные условия локального экстремума.
  11. Касательная плоскость; нормальный вектор.
  12. Понятие функции, заданной неявно. Теорема о неявной функции для случая а) одного уравнения с двумя переменными; в) одного уравнения с (n+1) перемен­ной.
  13. Неявные функции, определяемые системой функциональных уравнений. Теоре­ма о существовании неявных функций, определяемых системой уравнений (без доказательства). Вычисление частных производных функций, заданных неявно системой уравнений.
  14. Замена переменных для неявно заданных функций.

12. Кратные интегралы.
  1. Собственные интегралы, зависящие от параметра. Теорема о непрерывности ин­теграла по параметру. Теорема о дифференцируемости интеграла по параметру (правило Лейбница).
  2. Двойной интеграл. Теорема об интегрируемости непрерывной функции двух пе­ременных (без доказательства). Свойства двойного интеграла. Теорема о сред­нем.
  3. Приведение двойного интеграла к повторному а) случай прямоугольной области б) случай произвольной области.
  4. Двойной интеграл в полярных координатах
  5. Замена переменных в двойном интеграле
  6. Геометрические приложения двойных интегралов: а) вычисление площадей б) вычисление объемов в) вычисление площадей поверхностей.
  7. Тройной интеграл. Переход к повторному интегралу (без доказательства). За­мена переменных (без доказательства); цилиндрическая и сферическая системы координат.
  8. Криволинейный интеграл 1-го рода; его свойства.
  9. Криволинейный интеграл 2-го рода; его свойства.



  1. Формула Грина. Вычисление площадей с помощью криволинейных интегралов.
  2. Независимость криволинейного интеграла от пути интегрирования.
  3. Поверхностные интегралы 1-го и 2-го рода. Теорема Гаусса–Остроградского (без доказательства).

13. Ряды Фурье.
  1. Ортогональная тригонометрическая система. Ряд Фурье для абсолютно инте­грируемой на [a,b] функции; ряд Фурье для четной и нечетной функции. Ряд Фурье в случае произвольного интервала.
  2. Сходимость ряда Фурье для кусочно-гладкой функции.
  3. Неравенство Бесселя.
  4. Признак Дини (без доказательства).
  5. Сходимость рядов Фурье для функций, удовлетворяющих условию Гельдера.
  6. Приближение непрерывных функций тригонометрическими и алгебраическими многочленами.
  7. Минимальное свойство коэффициентов Фурье. Равенство Парсеваля. Почлен­ное дифференцирование и интегрирование рядов Фурье.

Литература

Основная литература
  1. Рудин Основы математического анализа. М.: Мир. 1976.
  2. Фихтенгольц Г.М. Курс дифференциального и интегрального исчисления. Т. 1–3. М.: Наука.
  3. Кудрявцев Л.Д. Математический анализ. Т.1,2. М.: Высшая школа. 1970.
  4. Ляшко И.И. Основы классического и современного математического анализа. - Киев, Высшая школа. 1988.

Дополнительная литература
  1. Дьедоне. Основы современного анализа. М.: Мир, 1964.
  2. Шварц, Лоран. Анализ т.1,2. М.:, 1972.

Задачники
  1. Берман Г.Н. Сборник задач по курсу математического анализа. М.: Наука, 1985.
  2. Демидович Б.П. Сборник задач и упражнений по математическому анализу. М.: Наука, 1977.
  3. Кузнецов Л.А. Сборник заданий по высшей математике. Типовые расчеты. “Высшая школа”, М., 1994.

Прикладные задачи теории вероятностей. Дискретное вероятностное пространство.
  1. Дискретное вероятностное пространство.
  2. Классическое определение вероятности. Гипергеометрическое распределение.
  3. Теорема сложения. Условная вероятность. Теорема умножения. Независимость со­бытий. Формула полной вероятности. Формулы Байеса.
  4. Последовательность испытаний Бернулли. Наиболее вероятное число успехов в ис­пытаниях Бернулли. Теорема Пуассона.
  5. Математическое ожидание случайной величины.
  6. Дисперсия случайной величины.
  7. Независимость случайных величин. Математическое ожидание произведения слу­чайных величин.
  8. Ковариация. Дисперсия суммы n случайных величин.
  9. Коэффициент корреляции и его свойства.

10. Неравенство Чебышева. Закон больших чисел. Теорема Бернулли.

II. Общее вероятностное пространство.
  1. Аксиоматика теории вероятностей в общем случае.
  2. Непрерывность вероятностной меры.
  3. Измеримые функции. Определение случайной величины.
  4. Функция распределения случайной величины и ее свойства.
  5. Плотность распределения случайной величины и ее свойства.
  6. Примеры непрерывных распределений.
  7. Плотность распределения функции от случайной величины.
  8. Многомерная функция распределения и ее свойства.
  9. Многомерная плотность распределения и ее свойства.



  1. Свертка распределений.
  2. Характеристические функции и их свойства.
  3. Центральная предельная теорема.
  4. Интегральная теорема Муавра -Лапласа.
  5. Цепи Маркова. Матрица вероятностей перехода. Вычисление переходных вероятно­стей.

III. Математическая статистика.
  1. Предмет и задачи математической статистики. Простой случайный выбор.
  2. Точечное оценивание. Статистика. Несмещенность, состоятельность, эффектив­ность.
  3. Выборочное среднее. Его несмещенность и состоятельность.
  4. Выборочная дисперсия. Смещеность, состоятельность.
  5. Эмпирическая функция распределения.
  6. Достаточные условия состоятельности оценок.
  7. Метод моментов. Условия состоятельности оценок, полученных методом моментов. Примеры.
  8. Метод максимального правдоподобия.

9. Получение оценок параметров распределения методом минимума χ2.
10. Распределения Пирсона и Стьюдента.
  1. Интервальное оценивание. Доверительный интервал для математического ожидания случайной величины с известной дисперсией.
  2. Доверительный интервал для вероятности события.
  3. Интервальные оценки параметров нормального распределения.
  4. Понятие статистической гипотезы. Простая гипотеза. Статистические критерии. Критерий согласия, общая схема. Уровень значимости критерия. Ошибки первого и второго рода. Критическая область.
  5. Критерий согласия Пирсона (критерий согласия χ2) проверки простой гипотезы.
  6. Модель линейной регрессии и метод наименьших квадратов.
  7. Критерий χ2 проверки гипотезы независимости случайных величин. "Проверка со­пряжённости признаков".
  8. Критерий χ2 проверки гипотезы об однородности наблюдений.
  9. Модель линейной регрессии. Коэффициент линейной регрессии. Остаточная диспер­сия. Метод наименьших квадратов.

Литература
  1. Севастьянов Б. А. Курс теории вероятностей и математической статистики.
  2. Боровков А.А. Курс теории вероятностей.
  3. Чистяков В.П. Курс теории вероятностей.
  4. Ивченко Г. И., Медведев Ю.И. Математическая статистика
  5. Гнеденко Б.В. Курс теории вероятностей.
  6. Тутубалин Б.Н. Теория вероятностей.
  7. Солодовников А.С. Теория вероятностей.
  8. Ширяев А.Н. Вероятность.

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

1. Введение
  1. Первый взгляд на архитектуру ЭВМ. Виртуальная машина, трансляция, интер­претация.
  2. Современная многоуровневая машина
  3. Архитектура фон-Неймана. Основные принципы, устройство. Примеры фон-Неймановской и не фон-Неймановской архитектур.
  4. Основные компоненты компьютера: центральный процессор, память, устрой­ства ввода-вывода, шина.
  5. Эволюция вычислительных систем, основные периоды.

2. Базовое устройство виртуальной машины
  1. Устройство центрального процессора. Блок управления, АЛУ.
  2. Регистры
  3. Трак данных
  4. Цикл работы центрального процессора
  5. Память. Иерархическая структура памяти. Типы памяти.
  6. Кэш-память, принцип локальности
  7. Устройства ввода-вывода. Порты ввода-вывода.
  8. Базовое устройство языка ассемблера виртуальной машины. Типы команд, при­мер программы.

3. Цифровой логический уровень
  1. Устройство транзистора, транзисторный инвертор
  2. Вентиль. Простейшие булевы вентили. Выражение любой булевой формулы с помощью цифровой логической микросхемы. Интегральная схема.
  3. Устройство мультиплексора.
  4. Устройство декодера.
  5. Устройство компаратора.
  6. Устройство полусумматора.
  7. Устройство полного сумматора.
  8. Устройство одноразрядного арифметико-логического устройства. Принцип по­строения 8-битного АЛУ
  9. Устройство защелки.



  1. Устройство синхронной SR-защелки, синхронной D-защелки
  2. Устройство 8-ми битной схемы памяти. 12-ти битная схема памяти с 3-мя выхо­дами.

4. Уровень архитектуры команд
  1. Четыре основных блока уровня архитектуры команд: модель памяти, регистры, типы данных, команды.
  2. Модель памяти: ячейка памяти, слово памяти, выравнивание, адресное про­странство.
  3. Адресное пространство, регистры.
  4. Команды, формат команд, типы команд.

5. Уровень операционной системы
  1. Определение операционной системы как расширенной виртуальной машины
  2. Определение операционной системы как менеджера ресурсов
  3. Принцип работы ОС. Один цикл жизнедеятельности ОС.
  4. Когда начинает работать ОС.
  5. Прерывания. Прерывания по таймеру, программное прерывание.

6. Ввод-вывод
  1. Устройство ввода-вывода. Контроллер устройства. Регистры контроллера, на­значение, принцип работы.
  2. Общение контроллера с процессором: при помощи портов, при помощи адрес­ного пространства ввода-вывода.
  3. Общее описание способов ввода-вывода: программный, при помощи прерыва­ний, DMA.
  4. Принцип работы ввода-вывода при помощи прерываний. Достоинства и недо­статки.
  5. Принцип работы ввода-вывода при помощи прямого доступа в память (DMA). Достоинства и недостатки.

7. Уровень языка ассемблера
  1. Уровни языков. Компиляторы, трансляторы, ассемблеры.
  2. Специфика языков ассемблера. Зачем нужны ассемблерные языки сегодня?
  3. Пример формата языка ассемблера.
  4. Процесс ассемблирования.
  5. Компоновщик, описание процесса компоновки. Структура объектного модуля.
  6. Связывание: раннее связывание, позднее связывание. Где, как и когда исполь­зуется. Преимущества и недостатки.

Литература
  1. Буза М.К. Архитектура ЭВМ. Минск: Новое знание, 2007. 560 стр.
  2. Э. Таненбаум. Архитектура компьютера. 5-изд. СПБ.: Издательство “Питер”, 2007. 848 стр.
  3. Полунов Ю.Л. От абака до компьютера: судьбы людей и машин. Книга для чтения по истории вычислительной техники в двух томах. Издательство “Русская редакция”, 2004.

Операционные системы
  1. Понятие вытесняющей и невытяснющей многозадачности.
  2. Различия между процессами и потоками.
  3. Состояния процессов в многозадачной ОС.
  4. Критерии планирования процессов и требования к алгоритмам планирования.
  5. Алгоритм планирования First Come First Served (FCFS).
  6. Алгоритм планирования Round Robin (RR).
  7. Оптимальный алгоритм планирования и практические приближения к нему.
  8. Механизмы синхронизации процессов.
  9. Принцип локальности и организация памяти компьютера.



  1. Связывание адресов.
  2. Страничная и сегментно-страничная организация памяти.
  3. Архитектурные средства поддержки страничной памяти. Многоуровневые таблицы страниц и ассоциативная память (TLB).
  4. Алгоритмы First In First Out (FIFO) и Second Chance замещения страниц.
  5. Алгоритм выталкивания не часто используемой страницы (NFU).
  6. Рабочее множество страниц процесса и тренинг.
  7. Модель взаимодействия открытых систем OSI.
  8. Объединение сетей. Ретрансляторы, коммутаторы и маршрутизаторы.
  9. Основные протоколы уровня Интернет стека сетевых протоколов TCP/IP.
  10. IP-адреса и маршрутизация в Интернет.
  11. Основные протоколы уровня узлов стека сетевых протоколов TCP/IP.
  12. Служба доменных имен DNS.

Литература
  1. Танненбаум Э. Современные операционные системы. 2-е издание.
  2. Танненбаум Э. Вудхалл А. Операционные системы. Разработка и реализация. Клас­сика CS.
  3. Дейтел Х., Дейтел П., Чорнес Д. Операционные системы. Основы и принципы. Книга 1.
  4. М. Руссинович. Внутреннее устройство Microsoft Windows: Windows Server 2003, Windows XP и Windows 2000.
  5. Кабелова А., Досталек Л. TCP/IP и DNS в теории и на практике. Полное руковод­ство.
  6. Фейт С. TCP/IP. Архитектура, протоколы и реализация (включая IP версии 6 и IP Security).

Компьютерные сети
  1. Требования, предъявляемые к XML документу. Правильные и состоятельные доку­менты.
  2. DTD. Назначение схем. Правила подключения DTD к XML документам. Внутренние и внешние DTD.
  3. DTD. Правила и синтаксис описания элементов. Модель содержания.
  4. DTD. Правила описания атрибутов.
  5. DOM. Представление XML документа в DOM.
  6. Пространство имен NameSpace. Назначение, связь с XML документом.
  7. Область действия объявлений пространства имен в XML документе.
  8. XML Schema. Синтаксис объявления элементов и атрибутов. Простые и сложные элементы.
  9. XML Schema. Зачем и как объединяются элементы в группы. Элементы group, choice и all.



  1. XML Schema. Задание правил вхождения элементов и атрибутов в XML документе с использованием атрибутов manicures и maxOccurs.
  2. XML Schema. Задание правил вхождения элементов и атрибутов в XML документе с использованием атрибутов default, fixed и use.
  3. XML Schema. Содержание элементов. Образование сложных элементов от простых.
  4. XML Schema. Содержание элементов. Смешанное содержание.
  5. XML Schema. Содержание элементов. Пустое содержание.
  6. XML Schema. Ограничения. Задание ограничений на диапазон значений и на основе перечислений.
  7. Ограничения. Задание ограничений на длину и с помощью шаблона.

Литература
  1. Д. Мартин и др. XML для профессионалов. М.: Лори, 2001.
  2. Ф. Бумфлей и др. XML: новые перспективы WWW. М.: ДМК, 2000.
  3. Г.Е. Берман. Введение в XML Schema. Тверь. 2005.

Компьютерная графика
  1. Растровые и векторные изображения. Рисование прямых линий на растровых устройствах.
  2. Рисование простых графических примитивов.
  3. Заполнение областей на растровых устройствах.
  4. Аффинные преобразования на плоскости (сдвиг, масштабирование, вращение).
  5. Определение принадлежности точки треугольнику.
  6. Представление кривых сплайнами Безье. Свойства кривых Безье.
  7. Алгоритмы обрисовки параметрических кривых.
  8. Однородные координаты, аффинные и проективные преобразования в пространстве.
  9. Удаление невидимых линий. Синтез трехмерной сцены.

10. Моделирование освещенности. Закрашивание грани (плоское, по Гуро, по Фонгу).

Литература
  1. Роджерс Д., Адамс Дж. Математические основы машинной графики. М.,Мир, 2001.
  2. Роджерс Д. Алгоритмические основы машинной графики. М.,Мир, 1989.
  3. Шикин Е.В., Плис А.И. Кривые и поверхности на экране компьютера. М., Диалог-МИФИ, 1996.
  4. Ньюмен У., Спрулл Р. Основы машинной графики. М., Мир, 1976.
  5. Фоли Д., вэн Дэм А. Основы интерактивной машинной графики: В 2 кн. М, Мир, 1985.
  6. Энджел И. Практическое введение в машинную графику. М., Радио и связь, 1984.
  7. Препарата Ф., Шеймос М. Вычислительная геометрия: введение. М., Мир, 1989.
  8. Шикин Е.В., Боресков А.В. Компьютерная графика. Полигональные модели. М., Диалог-МИФИ, 2000
  9. Иванов В.П., Батраков А.С. Трехмерная компьютерная графика. М., Радио и связь, 1995.
  1. Никулин Е.А. Компьютерная геометрия и алгоритмы машинной графики. BHV-Санкт-Петербург, 2003.
  2. Математика и САПР, книга 2. М., Мир, 1989.


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

1. Булевы функции
  1. Булевы функции. Табличное и геометрическое представления булевых функций. Формулы. Реализация булевых функций формулами. Булевы функции и логика высказы­ваний.
  2. Эквивалентность формул. Основные элементарные эквивалентности (логические тождества).
  3. Дизъюнктивные и конъюнктивные нормальные формы. Совершенные ДНФ и КНФ.
  4. Сокращенные ДНФ и их построение методом Блейка.
  5. Многочлены Жегалкина. Единственность представления многочленом Жегалкина. Построение многочлена Жегалкина методом неопределенных коэффициентов.
  6. Замкнутость и полнота классов булевых функций. Классы функций, сохраняющих ноль, единицу, монотонных, самодвойственных и линейных.
  7. Теорема Поста о полноте.

2. Графы
  1. Определение графов. Ориентированные и неориентированные графы и их пред­ставления: графическое, матрицей смежности, матрицей инцидентности, списками смеж­ности. Нагруженные графы. Примеры использования графов.
  2. Достижимость и связность. Нахождение матрицы достижимости. Нахождение ком­понент сильной связности и базы графа.
  3. Двудольные (бихроматические) графы. Критерий двудольности.
  4. Ориентированные и неориентированные деревья. Эквивалентность разных опре­делений.
  5. Минимальное остовное дерево графа и алгоритм его построения.
  6. Четные графы. Эйлеровы циклы и алгоритм их нахождения.
  7. Задача о кратчайших путях в графе. Алгоритм Дейкстры для нахождения крат­чайших путей из одного источника.
  8. Задача о лабиринте. Алгоритмы обхода графа “в глубину” и “в ширину”.

3. Применение графов для представления булевых функций
  1. Логические схемы (схемы из функциональных элементов). Определение схем и их сложность.
  2. Логические схемы и линейные программы.
  3. Построение схемы двоичного сумматора.
  4. Упорядоченные бинарные диаграммы решений (УБДР): определения и примеры.
  5. Сокращенные УБДР и преобразование произвольной УБДР в сокращенную.

3.6. Построение сокращенной УБДР по формуле.

4. Конечные автоматы и формальные грамматики
  1. Алфавиты, слова, языки. Операции над языками.
  2. Недетерминированные и детерминированные конечные автоматы. Способы зада­ния конечных автоматов: таблицы и диаграммы.
  3. Теорема о детерминизации недетерминированных конечных автоматов.
  4. Регулярные выражения и регулярные языки.
  5. Теорема о распознавании регулярных языков конечными автоматами.
  6. Свойства замкнутости класса автоматных языков.
  7. Алгоритмические проблемы для конечных автоматов.
  8. Теорема о разрастании. Примеры не конечно автоматных языков.

5. Алгоритмы и вычислимые функции
  1. Структурные программы и вычислимые ими функции.
  2. Рекурсивные функции. Операторы суперпозиции, примитивной рекурсии и ми­нимизации. Рекурсивность функций, заданных с помощью ограниченного суммирования, сдвига, склейки и переименования переменных, разбора случаев.
  3. Вычислимость рекурсивных функций программами.
  4. Машины Тьюринга. “Тьюрингово” программирование: простейшие программы, ре­ализация композиции, условного оператора и цикла.

5.5. Вычислимость рекурсивных функций на машинах Тьюринга. Тезис Тьюринга-
Черча.

Литература
  1. Дехтярь М.И. Лекции по дискретной математике. Учебное пособие. – М.: Интернет-Университет Информационных технологий; БИНОМ. Лаборатория знаний, 2007.
  2. Дехтярь М.И.. Дискретная математика. В кн.: Фонд контрольных заданий для ква­лификационной аттестации студентов факультета ПМиК Тверского госуниверситета по основам фундаментальных и компьютерных знаний: Учебн.-метод. Сб. – Тверь: Твер. Гос. Ун-т, 2007, 82-111
  3. Столбоушкин А.П., Тайцлин М.А. Математические основания информатики. Часть 1 (глава 1и п. 2.1). Часть 2. ТвГУ,. Тверь, 1998.
  4. Гаврилов Г.П., Сапоженко А.А. Сборник задач по дискретной математике. М., Наука, 1977.
  5. Карпов Ю.Г. Теория автоматов.- СПб.: Питер, 2002.


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

1.1. Исчисление высказываний

1.1. Исчисление высказываний. Алфавит, формулы, секвенции. Схемы аксиом и правил
вывода. Доказательство. Примеры доказуемых секвенций.

Теорема об эквивалентности линейного доказательства и доказательства в виде дерева.
  1. Эквивалентность формул. Булевы эквивалентности. Теорема о доказуемости буле­вых эквивалентностей.
  2. Теорема о замене.



  1. Нормальные формы. Теорема о существовании эквивалентных днф и кнф для каждой формулы.
  2. Полнота. Теорема о полноте.
  3. Непротиворечивость. Теорема о непротиворечивости.

1.2. Логика предикатов. Базы данных

1.7. Алгебраические системы. Язык логики предикатов. Формулы и термы.
Гомоморфизмы и их различные частные случаи.

Теорема о сохранении значений термов при гомоморфизмах.
  1. Истинность формулы в системе на состоянии. Теорема о сохранении значений фор­мул при изоморфизмах.
  2. Базы данных. Описание свойств баз данных на языке логики предикатов.

1.10. Подсистемы. Теорема о подсистеме, порождённой множеством.

2.1. Сложность алгоритмов
  1. Нумерация машин Тьюринга. Теорема о номере следующего слова Поста.
  2. Теорема о рекурсивности функций, вычислимых на машинах Тьюринга.
  3. Многоленточные машины Тьюринга. Базы данных как входы. Сигнализирующие функции. Классы сложности.

2.4. Теоремы о зависимости сигнализирующих от числа символов алфавита и числа
лент.

2.5. Вычисления в полиномиальное время. Полиномиальная вычислимость запросов,
формулируемых на языке логики предикатов первого порядка.
  1. Полиномиальная сводимость. Теоремы о замкнутости PTIME и NPTIME относи­тельно полиномиальной сводимости.
  2. NP-полные проблемы. Теоремы об NP-полных проблемах.
  3. NP-полнота SAT.
  4. Машины Тьюринга со стеком. Первая теорема Кука о связи временной и емкостной сигнализирующих.

2.10. Машины Тьюринга со стеком. Вторая теорема Кука о связи временной и емкостной сигнализирующих.

2.2. Неразрешимость проблемы равенства в теории полугрупп
  1. Неразрешимость проблемы остановки для машин Тьюринга.
  2. Теорема о существование частично рекурсивной функции с нерекурсивной обла­стью определения.
  3. Полусистемы Туэ. Построение полусистемы Туэ по машине Тьюринга.
  4. Ассоциативные исчисления. Построение ассоциативного исчисления по машине Тьюринга. Теорема о выводимости заключительного слова Поста.
  5. Неразрешимость проблемы равенства в теории полугрупп.
  6. Неразрешимость логики предикатов.

3.1. Неразрешимость логики предикатов на конечных моделях
  1. Существование конечной модели и существование периодической модели в ариф­метике.
  2. Построение формулы по машине Тьюринга.
  3. Теорема о нерекурсивности множества номеров машин, сходящих с ленты, и мно­жества номеров зацикливающихся машин.
  4. Неразрешимость логики предикатов на конечных моделях.

3.2. Представление рекурсивных функций в арифметике

3.5. Функция Гёделя.
Китайская теорема об остатках.
  1. Представление рекурсивных функций в арифметике. Теорема о представимости в арифметике каждой частично рекурсивной функции.
  2. Теорема о неразрешимости арифметики.

3.3. Неполнота логики предикатов для PTIME
  1. Игры Эренфойхта.
  2. Неопределимость связности в логике предикатов.

3.10. Определимость связности в PTIME.

3.4. Метод резолюций
  1. Метод резолюций в логике высказываний.
  1. Самая общая унификация.
  1. Метод резолюций в логике предикатов.
  2. Машинное доказательство теорем.


Литература
  1. А.П.Столбоушкин, М.А.Тайцлин. Математические основания информатики. Части 1, 2 и 3. Тверь, 1998.
  2. М.А.Тайцлин. Теорема Кука.
  3. А.И.Мальцев. Алгоритмы и рекурсивные функции. Москва. "Наука". 1965.
  4. М.А.Тайцлин. Резолюции.
  5. А.П.Столбоушкин, М.А.Тайцлин. Неразрешимость логики предикатов на конечных моделях.
  6. С.Кук. Характеристики машинных автоматов в терминах вычислителей, ограничен­ных во времени. В книге: Сложность вычислений и алгоритмов, Москва, Мир,1974.


Основы программирования
  1. Основные конструкции структурного программирования: присваивание, следование, ветвление, цикл.
  2. Алгоритмы для решения теоретико-числовых и простейших вычислительных задач.
  3. Подпрограммы и функциональное программирование. Рекурсивные алгоритмы.
  4. Сложность вычислений. Время и память вычисления, максимальные и средние оцен­ки.
  5. Спецификация и верификация программ. Предусловия, постусловия, частичная и полная корректность, инвариант и ограничитель цикла.
  6. Системы счисления и представление чисел в ЭВМ. Двоичная система счисления и побитовые операции.
  7. Работа с текстом. Представление текста в ЭВМ. Обработка текста. Поиск текста.
  8. Работа с файлами. Основные действия по обработке текстовых файлов (открытие, закрытие, чтение, запись).

9. Поиск в линейных структурах данных. Линейный поиск. Дихотомические методы поиска. Максимальное и среднее время работы алгоритмов.
  1. Сортировка в линейных структурах данных. Квадратичные алгоритмы сортировки (пузырьком, вставками, выбором максимального элемента) и их модификации. Сор­тировки Шелла. Логарифмические методы сортировки (слияниями, Хоара). Макси­мальное и среднее время работы алгоритмов.
  2. Динамическое распределение памяти. Динамические структуры данных. Списки (односвязные и двусвязные, линейные и кольцевые, многомерные). Деревья. Представ­ления графов. Хеш-таблицы.
  3. Объектно-ориентированное программирование. Построение классов, наследование, перегрузка операторов. Шаблоны.

Литература

Основная литература
  1. Н.Вирт. Алгоритмы и структуры данных. М. Мир, 1984.
  2. С.М.Дудаков. Математическое введение в информатику. Тверь: ТвГУ, 2003.
  3. Д.Кнут. Искусство программирования для ЭВМ (три тома). М. Мир, 1978.
  4. Стандарт языка C++


Дополнительная литература
  1. В.Н.Агафонов. Математические основы обработки информации. Новосибирск, Изд-во НГУ, 1982.
  2. Н.И.Вьюкова, В.А.Галатенко, А.Б.Ходулев. Систематический подход к программи­рованию. М. Наука, 1988.
  3. Д.Грис. Наука программирования. М. Мир, 1984.
  4. Б.Мейер, К.Бодуэн. Методы программирования (два тома). М. Мир, 1982.
  5. В.А.Непомнящий, О.М.Рякин. Прикладные методы верификации программ. М. Ра­дио и связь, 1988.
  6. Требования и спецификации в разработке программ. Сборник статей. М. Мир, 1984.
  7. А.Филд, П.Харрисон. Функциональное программирование. М. Мир, 1993.

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

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

1.1.Машины с произвольным доступом к памяти. Меры сложности вычислений. ПДП-машины и машины Тьюринга.
  1. Линейные программы. Битовые линейные программы. Ветвящиеся программы (де­ревья сравнений).
  2. Модельный алгоритмический язык. Сложность реализации основных конструкций на ПДП-машине.

1.4. Асимптотический анализ верхней и средней оценок сложности алгоритмов; срав­нение наилучших, средних и наихудших оценок; O-, o-, ω- и θ-нотации.

2. Базовые структуры данных и основные методы разработки эффективных алгоритмов
  1. Списки, стеки (магазины), очереди. Алгоритмы выполнения основных операций.
  2. Графы, деревья, бинарные деревья. Способы представления. Алгоритмы обхода деревьев.
  3. Метод разработки алгоритмов "разделяй и властвуй". Алгоритм умножения дво­ичных чисел. Техническая теорема об оценке роста функций, заданных реккурентными соотношениями. Передача сообщений с открытыми ключами (экспоненциация).
  4. Динамическое программирование. Оптимальное умножение последовательности матриц. Алгоритм эффективного распознавания кс-языков. Задача глобального выравни­вания слов.

3. Сортировка
  1. Нижние оценки числа сравнений (в "худшем» и в "среднем").
  2. Алгоритм сортировки обменами (методом "пузырька").
  3. Алгоритм сортировки слиянием.
  4. Алгоритм быстрой сортировки Хоара. Оценка сложности "в среднем".
  5. Алгоритм пирамидальной сортировки (с помощью дерева).
  6. Алгоритм лексикографической сортировки.
  7. Алгоритмы нахождения k-го наименьшего элемента за линейное время.

3.8. Нижняя оценка числа сравнений для нахождения 2-го по величине элемента множества (теорема Кислицына).

4. Задачи поиска. Метод расстановки (хеширование)
  1. Алгоритмы выполнения основных операций при использовании "внешних» и "внутренних» цепей.
  2. Повторное хеширование. Выбор хеш-функции.
  3. Оценки сложности алгоритмов хеширования.

5. Задачи поиска и работа с множествами
  1. Деревья двоичного поиска. Алгоритм построения оптимального дерева двоичного поиска.
  2. 2-3-деревья. Алгоритмы вставки и удаления элементов из 2-3-дерева.
  3. Алгоритмы выполнения операций (ОБЪЕДИНИТЬ, НАЙТИ) с использованием массивов и списков.
  4. Алгоритмы выполнения операций (ОБЪЕДИНИТЬ, НАЙТИ) с использованием древовидных структур (сжатие путей).
  5. Алгоритм проверки эквивалентности конечных автоматов.

5.7 Биномиальные и фиббоначиевы кучи и алгоритмы работы с ними.
  1. В-деревья и алгоритмы работы с ними.
  2. Структуры данных для представления пространственной информации: 2-d дере­вья, квадродеревья, R-деревья порядка k.

6. Алгоритмы на графах
  1. Минимальное остовное дерево.
  2. Поиск в глубину и поиск в ширину в неориентированных и ориентированных гра­фах. Топологическая сортировка.
  3. Алгоритм определения двусвязных компонент графа.

6..4. Алгоритмы построения транзитивного замыкания графа и нахождения кратчай­ших путей.
  1. Задача о кратчайших путях из одного источника (алгоритм Дейкстры).
  2. Задача о максимальном потоке в сетях. Алгоритм Форда - Фалкерсона.
  3. Алгоритм нахождения максимального потока за кубическое время.
  4. Простые сети и задача о максимальном паросочетании для двудольных графов.

Литература Основная:

1. А.Ахо, Дж.Хопкрофт, Дж. Ульман. Построение и анализ вычислительных
алгоритмов.- М.:Мир, 1979.

2. Т.Кормен, Ч.Лейзерсон, Р.Ривест, К. Штайн. Алгоритмы. Построение и анализ. Второе издание. Изд. “Вильямс”, М., 2005.

Дополнительная:
  1. Н.Вирт. Алгоритмы и структуры данных. — М.:Мир, 1989.
  2. Д.Кнут. Искусство программирования для ЭВМ. т.3. Сортировка и поиск. — М.: Мир, 1978.
  3. В.Липский. Комбинаторика для программистов. -М.:Мир,1988

6. Х.Пападимитриу, К.Стайглиц. Комбинаторная оптимизация. Алгоритмы и
сложность.- М.:Мир, 1985.

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

Программа квалификационного экзамена
  1. Проектирование баз данных. Нормализация отношений.
  2. Реляционная алгебра. Основные операции над отношениями (объединение, вычита­ние, декартово произведение, фильтрация, проекция).
  3. Построение SQL-запросов. Оператор select. Внутренние и внешние соединения. Сор­тировка. Группировка и агрегатные функции. Подзапросы.
  4. Изменение данных при помощи SQL-запросов. Операторы insert, delete, update.
  5. Многопользовательский доступ к базам данных. Привилегии. Транзакции, уровни изолированности.
  6. Построение приложений с использованием баз данных. Встроенный SQL для языка C. Статический и динамический SQL.

Литература

Основная литература

1. Документация PostgreSQL,

http://www.postgresql.org/docs/8.3/interactive/index.html
  1. Дж. Дейт, Введение в системы баз данных, Вильямс: Киев, 2000.
  2. СМ. Дудаков, Лекции по базам данных,

http://pmkinfo.tversu.ru/pmk/progr.php?dis=kr

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

1. Документация Microsoft SQL Server,

http://msdn.microsoft.com/en-us/library/aa174556(SQL.80).aspx
  1. Документация MySQL, http://dev.mysql.com/doc/


Программа вступительных испытаний в магистратуру по направлению

080800.68 Прикладная информатика

«Прикладная информатика в аналитической экономике»


Информатика


1. Функции.

Функции, возвращаемые значения, параметры и аргументы. Объявление и определение функций.

Локальные и глобальные переменные.

Дополнительные сведения о функциях. Рекурсия. Стек и рекурсия.