Программа
вступительных испытаний в магистратуру
по направлению 010200.68 – Математика. Прикладная математика
«Математический анализ»
Математический анализ
-
Предел числовой последовательности. Основные свойства: единственность предела; ограниченность сходящейся последовательности; сходимость подпоследовательности сходящейся последовательности. Предел и арифметические операции. Принцип Больцано Вейерштрасса. Критерий Коши сходимости числовой последовательности.
-
Предел и непрерывность функции. Эквивалентные определения (по Коши и по Гейне). Основные свойства непрерывных функций. Связь с арифметическими операциями. Непрерывность композиции. Односторонние пределы и односторонняя непрерывность.
-
Теорема Вейерштрасса об ограниченности и о достижении экстремальных значений функции непрерывной на отрезке. Теорема Коши о промежуточных значениях непрерывной функции. Непрерывность обратной функции.
-
Дифференцируемость числовой функции. Производная и дифференциал. Непрерывность дифференцируемой функции. Геометрический смысл производной. Дифференцируемость и арифметические операции. Дифференцируемость композиции и обратной функции.
-
Теоремы Ферма, Ролля, Коши и Лагранжа о дифференцируемых функциях. Необходимые и достаточные условия экстремума функции в терминах производной.
-
Интеграл Римана. Основные свойства интеграла: линейность, монотонность, аддитивность. Классы функций интегрируемых по Риману.
-
Числовые ряды. Понятие сходимости числового ряда Необходимое условие сходимости. Признаки сравнения, Коши и Даламбера сходимости положительных рядов. Признак Лейбница сходимости знакопеременного ряда.
-
Степенные ряды. Теорема Коши Адамара о структуре области сходимости степенного ряда. Радиус и интервал сходимости. Равномерная сходимость степенных рядов. Теорема Абеля о равномерной сходимости степенного ряда на отрезке, содержащемся в интервале сходимости. Непрерывность суммы степенного ряда. Почленное дифференцирование и интегрирование степенных рядов.
Дифференциальные уравнения
-
Линейное уравнение n-ого порядка с постоянными коэффициентами. Методы нахождения общего решения.
Теория функций комплексного переменного
-
Моногенные и голоморфные функции. Критерии моногенности и голоморфности. Изолированные особые точки и вычеты.
Литература к разделу
Математический анализ
-
Ильин В.А., Садовничий В.А., Сендов Б. Х. Математический анализ. М., 1981;
-
Кудрявцев Л.Д. Курс математического анализа. М. 1981;
-
Гусев А.И. Обзорные лекции по математическому анализу. Сервер локальной сети ТвГУ М:\Для студентов А.И. Гусева\ 5 курс.
Литература к разделу
Дифференциальные уравнения
1. Петровский И.Г. Лекции по теории обыкновенных дифференциальных уравнений. М.: Наука, 1970.
2. Понтрягин Л.С. Обыкновенные дифференциальные уравнения. М.: Наука, 1976.
3. Арнольд В.И. Обыкновенные дифференциальные уравнения. М.: Наука, 1976.
4. Федорюк М.В. Обыкновенные дифференциальные уравнения. М.: Наука, 1985.
6. Филлипов А.В. Сборник задач по дифференциальным уравнениям. М., Наука, 1975.
Литература к разделу
Теория функций комплексного переменного
-
Шабат Б.В. Введение в комплексный анализ. Т.1. М., 1969 и другие издания.
-
Привалов И.И. Введение в теорию функций комплексного переменного. М, 1984 и другие издания.
-
Сидоров Ю.В., Федорюк М.В., Шабунин М.И. Лекции по теории функций комплексного переменного. М., 1982 и другие издания.
-
Голубев А.А., Граф С.Ю., Шеретов В.Г. Практический курс комплексного анализа Тверь, 2003.
-
Маркушевич А.Н. Краткий курс теории аналитических функций. М., 1978 и другие издания.
-
Евграфов М.А. Аналитические функции. М, 1991 и другие издания.
-
Волковыский Л.И., Лунц Г.Л., Араманович И.Г. Сборник задач по теории функций комплексного переменного. М., 1975.
Программа
вступительных испытаний в магистратуру
по направлению 010200.68– Математика. Прикладная математика
«Методы оптимизации и оптимального управления»
Математический анализ
-
Предел числовой последовательности. Основные свойства: единственность предела; ограниченность сходящейся последовательности; сходимость подпоследовательности сходящейся последовательности. Предел и арифметические операции. Принцип Больцано Вейерштрасса. Критерий Коши сходимости числовой последовательности.
-
Предел и непрерывность функции. Эквивалентные определения (по Коши и по Гейне). Основные свойства непрерывных функций. Связь с арифметическими операциями. Непрерывность композиции. Односторонние пределы и односторонняя непрерывность.
-
Теорема Вейерштрасса об ограниченности и о достижении экстремальных значений функции непрерывной на отрезке. Теорема Коши о промежуточных значениях непрерывной функции. Непрерывность обратной функции.
-
Дифференцируемость числовой функции. Производная и дифференциал. Непрерывность дифференцируемой функции. Геометрический смысл производной. Дифференцируемость и арифметические операции. Дифференцируемость композиции и обратной функции.
-
Теоремы Ферма, Ролля, Коши и Лагранжа о дифференцируемых функциях. Необходимые и достаточные условия экстремума функции в терминах производной.
-
Интеграл Римана. Основные свойства интеграла: линейность, монотонность, аддитивность. Классы функций интегрируемых по Риману.
-
Числовые ряды. Понятие сходимости числового ряда Необходимое условие сходимости. Признаки сравнения, Коши и Даламбера сходимости положительных рядов. Признак Лейбница сходимости знакопеременного ряда.
-
Степенные ряды. Теорема Коши Адамара о структуре области сходимости степенного ряда. Радиус и интервал сходимости. Равномерная сходимость степенных рядов. Теорема Абеля о равномерной сходимости степенного ряда на отрезке, содержащемся в интервале сходимости. Непрерывность суммы степенного ряда. Почленное дифференцирование и интегрирование степенных рядов.
Дифференциальные уравнения
1. Линейное уравнение n-ого порядка с постоянными коэффициентами. Методы нахождения общего решения.
Вариационное исчисление и методы оптимизации
-
Конечномерные задачи минимизации.
-
Выпуклые множества. Теорема Куна – Таккера. Понятие седловой точки, ее свойства.
-
Задача оптимального управления. Понятие допустимого процесса, локально оптимального процесса. Классификация задач оптимального управления.
-
Принцип максимума Понтрягина.
-
Двойственный метод. Теорема Гамильтона-Якоби.
-
Двойственная задача оптимального управления. Метод построения решения двойственной задачи.
-
Уравнение Беллмана. Принцип оптимальности Беллмана. Связь метода Беллмана с методом Гамильтона-Якоби.
-
Связь метода Беллмана с принципом максимума Понтрягина.
-
Дискретная задача оптимального управления. Необходимое условие оптимальности в дискретной задаче оптимального управления.
-
Необходимые условия оптимальности (Теорема Лагранжа). Предельный переход.
-
Численные методы решения задач оптимального управления. Метод функции штрафа.
Литература к разделу
Математический анализ
-
Ильин В.А., Садовничий В.А., Сендов Б. Х. Математический анализ. М., 1981;
-
Кудрявцев Л.Д. Курс математического анализа. М. 1981;
-
Гусев А.И. Обзорные лекции по математическому анализу. Сервер локальной сети ТвГУ М:\Для студентов А.И. Гусева\ 5 курс.
Литература к разделу
Дифференциальные уравнения
1. Петровский И.Г. Лекции по теории обыкновенных дифференциальных уравнений. М.: Наука, 1970.
2. Понтрягин Л.С. Обыкновенные дифференциальные уравнения. М.: Наука, 1976.
3. Арнольд В.И. Обыкновенные дифференциальные уравнения. М.: Наука, 1976.
4. Федорюк М.В. Обыкновенные дифференциальные уравнения. М.: Наука, 1985.
6. Филлипов А.В. Сборник задач по дифференциальным уравнениям. М., Наука, 1975.
Литература к разделу
Вариационное исчисление и методы оптимизации
-
Андреева Е.А., Цирулева В.М. Вариационное исчисление и методы оптимизации. М.: Высшая школа, 2006.
-
Андреева Е.А., Цирулева В.М. Численные методы решения задач оптимального управления. Тверь: МЭСИ, 2004.
-
Васильев Ф.П. Численные методы решения экстремальных задач. М.: Наука, 1989.
Программа
вступительных испытаний в магистратуру
по направлению 010400.68 Информационные технологии
Алгебра и геометрия
-
Системы линейных уравнений. Метод Гаусса решения систем линейных уравнений. Определитель матрицы. Свойства определителя. Метод Крамера решения систем линейных уравнений.
-
Линейные пространства. Линейная зависимость и линейная независимость систем векторов. Базис и ранг системы векторов. Матрица перехода от одного базиса к другому. Координаты вектора в базисе. Изменение координат вектора при изменении базиса.
-
Кольцо многочленов. Делимость многочленов. Наибольший общий делитель двух многочленов. Алгоритм Евклида нахождения наибольшего общего делителя.
-
Линейные преобразования линейных пространств. Матрица линейного преобразования в базисе. Изменение матрицы линейного преобразования при изменении базиса.
-
Собственные числа и собственные векторы линейного преобразования. Характеристический многочлен линейного преобразования. Нахождение собственных чисел и собственных векторов линейного преобразования.
-
Евклидовы пространства. Симметрические преобразования. Нахождение ортонормированного базиса, состоящего из собственных векторов симметрического преобразования.
-
Квадратичные формы. Приведение квадратичной формы к каноническому и нормальному виду. Метод Лагранжа и метод Якоби. Положительно определённые квадратичные формы. Критерий Сильвестра.
-
Гиперповерхности второго порядка в евклидовом пространстве. Классификация гиперповерхностей второго порядка.
Задачи
-
Вычислите определитель матрицы размера п х п.
-
Для данной системы векторов арифметического пространства найдите базис и ранг этой системы.
-
Даны два многочлена из R[x]. Найдите наибольший общий делитель этих многочленов.
-
Даны два базиса линейного пространства. Найдите матрицу перехода от первого базиса ко второму.
-
Даны координаты вектора x в базисе E и матрица перехода от базиса A к базису E. Найдите координаты вектора x в базисе A.
-
Дана матрица линейного преобразования ϕ линейного пространства Rn в базисе E и матрица перехода от базиса E к базису A. Найдите матрицу преобразования ϕ в базисе A.
-
Дана матрица линейного преобразования ϕ линейного пространства Rn в некотором базисе E. Найдите собственные числа и собственные векторы преобразования ϕ.
-
Дана квадратичная форма. Приведите её к каноническому виду.
-
Дана квадратичная форма. Выясните, является ли она положительно определённой.
-
Дано уравнение поверхности второго порядка в R3. Определите тип этой поверхности.
Литература
-
Курош А.Г. Курс высшей алгебры. М.: Наука, 1975.
-
Глухов М.М., Елизаров В.П., Нечаев А.А. Алгебра: Учебник. В 2-х т.-М.: Гелиос АРВ, 2003.
-
Кострикин А.И. Введение в алгебру. М.: Наука, учебник, 1977.
-
Фаддеев Д.К., Соминский И.С. Сборник задач по высшей алгебре. М.: Наука, 1977.
-
Сборник задач по алгебре. Под ред. А.И.Кострикина, М.: Наука, 1995.
-
Мальцев А.И. Основы линейной алгебры. М.: Наука, 1970.
-
Калужнин А.Г. Введение в общую алгебру. М.: Наука, 1973
-
Скорняков Л.А. Элементы общей алгебры. М.: Наука, 1983.
-
Фаддеев Д.К. Лекции по алгебре. М.: Наука, 1984.
-
Куликов Л.Я. Алгебра и теория чисел. М.: Высшая школа, 1979.
-
Проскуряков И.В. Сборник задач по линейной алгебре. М.: Юнимедиастайл, 2002.
Математический анализ
1. Введение в анализ.
-
Вещественные числа. Десятичная запись вещественного числа. Свойства вещественных чисел. Аксиома Архимеда. Свойство непрерывности.
-
Верхняя и нижняя грани числового множества, их характеристические свойства. Теорема о существовании верхней (нижней) грани у ограниченного сверху (снизу) числового множества.
-
Ограниченные отображения, верхняя и нижняя грани отображения.
2. Предел последовательности.
2.1. Предел числовой последовательности, теорема о единственности предела числовой последовательности.
-
Бесконечно малые, бесконечно большие последовательности, их свойства. Арифметические свойства сходящихся последовательностей.
-
Предельный переход в неравенствах. Теорема о существовании предела у ограниченной монотонной последовательности. Число “е”.
-
Теорема Больцано–Вейерштрасса о существовании частичного предела у ограниченной числовой последовательности. Верхний и нижний пределы последовательности.
-
Критерий Коши сходимости последовательности.
3. Предел функции.
-
Предел функции в точке по Гейне и по Коши; эквивалентность этих определений. Односторонние пределы в точке. Арифметические операции над функциями, имеющими предел.
-
Критерий Коши существования предела функции в точке.
-
Замечательные пределы.
-
Бесконечно малые и бесконечно большие функции, теоремы о них. Сравнение бесконечно малых функций. Эквивалентные бесконечно малые функции.
-
Теорема о пределе сложной функции.
4. Непрерывность функции.
-
Непрерывность функции в точке. Односторонняя непрерывность. Арифметические операции над непрерывными функциями.
-
Свойство устойчивости знака непрерывной в точке функции.
-
Свойство локальной ограниченности непрерывной в точке функции.
-
Непрерывность элементарных функций.
-
Точки разрыва функции и их классификация. Теорема о точках разрыва монотонной на отрезке функции.
-
Первая теорема Коши (о прохождении непрерывной функции через нуль при смене знаков).
-
Вторая теорема Коши (о промежуточных значениях непрерывной на отрезке функции).
-
Первая теорема Вейерштрасса (об ограниченности непрерывной на отрезке функции).
-
Вторая теорема Вейерштрасса (о достижении верхней и нижней граней непрерывной на отрезке функцией).
-
Равномерная непрерывность. Теорема Кантора о равномерной непрерывности функции, непрерывной на отрезке.
-
Свойства открытых и замкнутых множеств. Компакт.
-
Теорема о равномерной непрерывности функции, непрерывной на компакте.
5. Производная и дифференциал.
-
Производная, ее геометрический смысл. Односторонние производные.
-
Непрерывность функции, дифференцируемой в точке.
-
Производная суммы, произведения и частного двух функций.
-
Производная сложной и обратной функций. Дифференцирование функции, заданной параметрически.
-
Производные элементарных функций.
-
Производные высших порядков. Формула Лейбница.
-
Дифференциал функции, геометрический смысл дифференциала. Правила вычисления дифференциала. Инвариантность формы первого дифференциала.
-
Дифференциалы высших порядков.
-
Лемма Дарбу о возрастании или убывании функции в точке.
-
Теорема Ферма о локальном экстремуме функции.
-
Теорема Ролля о нуле производной.
-
Теорема Лагранжа (формула конечных приращений).
-
Теорема Коши (обобщенная формула конечных приращений).
-
Первое и второе правило Лопиталя.
-
Формулы Тейлора и Маклорена с остаточным членом в форме Пеано.
-
Формула Тейлора с остаточным членом в форме Лагранжа.
-
Разложение элементарных функций по формуле Маклорена.
-
Необходимое и достаточное условия локального экстремума.
-
Выпуклость графика функции. Достаточное условие выпуклости графика функции.
-
Необходимое и достаточное условия точки перегиба.
-
Асимптоты графика функции. Необходимое и достаточное условие существования наклонной асимптоты.
6. Неопределенный интеграл.
-
Первообразная и неопределенный интеграл. Основные свойства неопределенного интеграла. Таблица интегралов.
-
Замена переменной в неопределенном интеграле. Формула интегрирования по частям.
-
Интегрирование рациональных дробей.
-
Интегрирование тригонометрических выражений, универсальная тригонометрическая подстановка.
-
Интегрирование простейших иррациональных функций.
7. Определенный интеграл.
-
Определенный интеграл Римана. Неинтегрируемость по Риману неограниченной на [а,в] функции.
-
Верхняя и нижняя интегральные суммы Дарбу, их основные свойства. Верхний и нижний интегралы Дарбу, их свойства. Основная лемма Дарбу.
-
Необходимые и достаточные условия интегрируемости функции по Риману. Теорема об интегрируемости непрерывной функции. Теорема об интегрируемости монотонной функции.
-
Свойства определенного интеграла.
-
Оценка определенных интегралов. Интегрирование неравенств. Первая теорема среднего значения.
-
Интеграл с переменным верхним пределом. Производная интеграла по переменному верхнему пределу. Формула Ньютона – Лейбница.
-
Замена переменной под знаком определенного интеграла. Правило интегрирования по частям для определенного интеграла.
-
Приложения определенного интеграла: вычисление площадей; вычисление длины дуги кривой.
8. Несобственные интегралы.
-
Несобственные интегралы первого и второго рода. Критерий Коши сходимости несобственных интегралов.
-
Абсолютная и условная сходимость несобственных интегралов.
-
Признаки сходимости несобственных интегралов (общий и частный признаки сравнения).
9. Числовые ряды.
-
Числовой ряд, сходимость и расходимость. Гармонический ряд. Необходимое условие сходимости ряда. Арифметические действия со сходящимися рядами. Критерий Коши сходимости числового ряда.
-
Признаки сравнения числовых рядов. Признаки Даламбера и Коши сходимости ряда.
-
Абсолютная и условная сходимость ряда. Переместительный закон для абсолютно сходящегося ряда.
9.4. Признак Лейбница сходимости знакочередующегося ряда.
10. Функциональные последовательности и ряды.
-
Функциональные последовательности и ряды. Поточечная и равномерная сходимость последовательностей и рядов.
-
Критерий Коши равномерной сходимости последовательности и ряда. Необходимое условие равномерной сходимости ряда. Признак Вейерштрасса равномерной сходимости функционального ряда.
-
Теорема о непрерывности суммы (предельной функции) равномерно сходящегося ряда (функциональной последовательности).
-
Теорема об интегрируемости суммы (предельной функции) равномерно сходящегося на [а,в] ряда (функциональной последовательности).
-
Теорема о дифференцируемости суммы (предельной функции) сходящегося на [а,в] ряда (функциональной последовательности).
-
Степенные ряды. Первая теорема Абеля. Радиус и интервал сходимости степенного ряда. Теорема о радиусе сходимости степенного ряда. Формулы для вычисления радиуса сходимости степенного ряда.
-
Функция, аналитическая в точке. Единственность представления аналитической в точке функции степенным рядом. Теорема о почленном дифференцировании интегрировании степенного ряда.
-
Ряды Тейлора и Маклорена. Необходимое и достаточное условие разложимости функции в степенной ряд. Пример бесконечно дифференцируемой функции, не являющейся аналитической. Разложение в ряд Маклорена некоторых элементарных функций.
11. Функции нескольких переменных.
-
Предел последовательности точек пространства Rn. Лемма о сходимости последовательности точек в пространстве Rn. Лемма о фундаментальной последовательности; критерий Коши сходимости последовательности точек пространства Rn. Теорема Больцано – Вейерштрасса.
-
Предел функции n переменных в точке по Гейне и по Коши; эквивалентность этих определений. Арифметические операции над функциями, имеющими предел. Бесконечно малые функции n переменных.
-
Критерий Коши существования предела функции n переменных в точке.
-
Повторные пределы.
-
Непрерывность функции нескольких переменных в точке. Арифметические операции над непрерывными функциями. Непрерывность сложной функции.
-
Теорема об устойчивости знака непрерывной в точке функции. Теорема о прохождении непрерывной функцией через любое промежуточное значение.
-
Первая теорема Вейерштрасса (об ограниченности функции, непрерывной на компакте).
-
Вторая теорема Вейерштрасса (о достижении непрерывной на компакте функцией своих точных граней).
-
Равномерная непрерывность функции нескольких переменных. Теорема Кантора о равномерной непрерывности функции, непрерывной на компакте.
-
Частные производные. Дифференцируемость функции нескольких переменных. Теорема о существовании частных производных дифференцируемой в точке функции.
-
Непрерывность дифференцируемой в точке функции. Достаточное условие дифференцируемости функции в точке. Дифференциал функции нескольких переменных.
-
Дифференцирование сложной функции. Однородные функции степени p. Теорема Эйлера об однородных функциях. Инвариантность формы первого дифференциала.
-
Производная по направлению. Градиент. Теорема о производной функции по направлению градиента.
-
Частные производные высших порядков. Достаточное условие равенства смешанных производных (случай функции двух переменных и случай функции n переменных). Дифференциалы высших порядков.
-
Формула Тейлора с остаточным членом в форме Лагранжа. Формула Тейлора с остаточным членом в форме Пеано (без доказательства).
-
Понятие локального экстремума. Необходимое условие локального экстремума.
-
Достаточное условие локального экстремума.
-
Условный экстремум. Метод множителей Лагранжа, необходимое условие локального экстремума.
-
Достаточные условия локального экстремума.
-
Касательная плоскость; нормальный вектор.
-
Понятие функции, заданной неявно. Теорема о неявной функции для случая а) одного уравнения с двумя переменными; в) одного уравнения с (n+1) переменной.
-
Неявные функции, определяемые системой функциональных уравнений. Теорема о существовании неявных функций, определяемых системой уравнений (без доказательства). Вычисление частных производных функций, заданных неявно системой уравнений.
-
Замена переменных для неявно заданных функций.
12. Кратные интегралы.
-
Собственные интегралы, зависящие от параметра. Теорема о непрерывности интеграла по параметру. Теорема о дифференцируемости интеграла по параметру (правило Лейбница).
-
Двойной интеграл. Теорема об интегрируемости непрерывной функции двух переменных (без доказательства). Свойства двойного интеграла. Теорема о среднем.
-
Приведение двойного интеграла к повторному а) случай прямоугольной области б) случай произвольной области.
-
Двойной интеграл в полярных координатах
-
Замена переменных в двойном интеграле
-
Геометрические приложения двойных интегралов: а) вычисление площадей б) вычисление объемов в) вычисление площадей поверхностей.
-
Тройной интеграл. Переход к повторному интегралу (без доказательства). Замена переменных (без доказательства); цилиндрическая и сферическая системы координат.
-
Криволинейный интеграл 1-го рода; его свойства.
-
Криволинейный интеграл 2-го рода; его свойства.
-
Формула Грина. Вычисление площадей с помощью криволинейных интегралов.
-
Независимость криволинейного интеграла от пути интегрирования.
-
Поверхностные интегралы 1-го и 2-го рода. Теорема Гаусса–Остроградского (без доказательства).
13. Ряды Фурье.
-
Ортогональная тригонометрическая система. Ряд Фурье для абсолютно интегрируемой на [a,b] функции; ряд Фурье для четной и нечетной функции. Ряд Фурье в случае произвольного интервала.
-
Сходимость ряда Фурье для кусочно-гладкой функции.
-
Неравенство Бесселя.
-
Признак Дини (без доказательства).
-
Сходимость рядов Фурье для функций, удовлетворяющих условию Гельдера.
-
Приближение непрерывных функций тригонометрическими и алгебраическими многочленами.
-
Минимальное свойство коэффициентов Фурье. Равенство Парсеваля. Почленное дифференцирование и интегрирование рядов Фурье.
Литература
Основная литература
-
Рудин Основы математического анализа. М.: Мир. 1976.
-
Фихтенгольц Г.М. Курс дифференциального и интегрального исчисления. Т. 1–3. М.: Наука.
-
Кудрявцев Л.Д. Математический анализ. Т.1,2. М.: Высшая школа. 1970.
-
Ляшко И.И. Основы классического и современного математического анализа. - Киев, Высшая школа. 1988.
Дополнительная литература
-
Дьедоне. Основы современного анализа. М.: Мир, 1964.
-
Шварц, Лоран. Анализ т.1,2. М.:, 1972.
Задачники
-
Берман Г.Н. Сборник задач по курсу математического анализа. М.: Наука, 1985.
-
Демидович Б.П. Сборник задач и упражнений по математическому анализу. М.: Наука, 1977.
-
Кузнецов Л.А. Сборник заданий по высшей математике. Типовые расчеты. “Высшая школа”, М., 1994.
Прикладные задачи теории вероятностей. Дискретное вероятностное пространство.
-
Дискретное вероятностное пространство.
-
Классическое определение вероятности. Гипергеометрическое распределение.
-
Теорема сложения. Условная вероятность. Теорема умножения. Независимость событий. Формула полной вероятности. Формулы Байеса.
-
Последовательность испытаний Бернулли. Наиболее вероятное число успехов в испытаниях Бернулли. Теорема Пуассона.
-
Математическое ожидание случайной величины.
-
Дисперсия случайной величины.
-
Независимость случайных величин. Математическое ожидание произведения случайных величин.
-
Ковариация. Дисперсия суммы n случайных величин.
-
Коэффициент корреляции и его свойства.
10. Неравенство Чебышева. Закон больших чисел. Теорема Бернулли.
II. Общее вероятностное пространство.
-
Аксиоматика теории вероятностей в общем случае.
-
Непрерывность вероятностной меры.
-
Измеримые функции. Определение случайной величины.
-
Функция распределения случайной величины и ее свойства.
-
Плотность распределения случайной величины и ее свойства.
-
Примеры непрерывных распределений.
-
Плотность распределения функции от случайной величины.
-
Многомерная функция распределения и ее свойства.
-
Многомерная плотность распределения и ее свойства.
-
Свертка распределений.
-
Характеристические функции и их свойства.
-
Центральная предельная теорема.
-
Интегральная теорема Муавра -Лапласа.
-
Цепи Маркова. Матрица вероятностей перехода. Вычисление переходных вероятностей.
III. Математическая статистика.
-
Предмет и задачи математической статистики. Простой случайный выбор.
-
Точечное оценивание. Статистика. Несмещенность, состоятельность, эффективность.
-
Выборочное среднее. Его несмещенность и состоятельность.
-
Выборочная дисперсия. Смещеность, состоятельность.
-
Эмпирическая функция распределения.
-
Достаточные условия состоятельности оценок.
-
Метод моментов. Условия состоятельности оценок, полученных методом моментов. Примеры.
-
Метод максимального правдоподобия.
9. Получение оценок параметров распределения методом минимума χ2.
10. Распределения Пирсона и Стьюдента.
-
Интервальное оценивание. Доверительный интервал для математического ожидания случайной величины с известной дисперсией.
-
Доверительный интервал для вероятности события.
-
Интервальные оценки параметров нормального распределения.
-
Понятие статистической гипотезы. Простая гипотеза. Статистические критерии. Критерий согласия, общая схема. Уровень значимости критерия. Ошибки первого и второго рода. Критическая область.
-
Критерий согласия Пирсона (критерий согласия χ2) проверки простой гипотезы.
-
Модель линейной регрессии и метод наименьших квадратов.
-
Критерий χ2 проверки гипотезы независимости случайных величин. "Проверка сопряжённости признаков".
-
Критерий χ2 проверки гипотезы об однородности наблюдений.
-
Модель линейной регрессии. Коэффициент линейной регрессии. Остаточная дисперсия. Метод наименьших квадратов.
Литература
-
Севастьянов Б. А. Курс теории вероятностей и математической статистики.
-
Боровков А.А. Курс теории вероятностей.
-
Чистяков В.П. Курс теории вероятностей.
-
Ивченко Г. И., Медведев Ю.И. Математическая статистика
-
Гнеденко Б.В. Курс теории вероятностей.
-
Тутубалин Б.Н. Теория вероятностей.
-
Солодовников А.С. Теория вероятностей.
-
Ширяев А.Н. Вероятность.
Архитектура вычислительных систем
1. Введение
-
Первый взгляд на архитектуру ЭВМ. Виртуальная машина, трансляция, интерпретация.
-
Современная многоуровневая машина
-
Архитектура фон-Неймана. Основные принципы, устройство. Примеры фон-Неймановской и не фон-Неймановской архитектур.
-
Основные компоненты компьютера: центральный процессор, память, устройства ввода-вывода, шина.
-
Эволюция вычислительных систем, основные периоды.
2. Базовое устройство виртуальной машины
-
Устройство центрального процессора. Блок управления, АЛУ.
-
Регистры
-
Трак данных
-
Цикл работы центрального процессора
-
Память. Иерархическая структура памяти. Типы памяти.
-
Кэш-память, принцип локальности
-
Устройства ввода-вывода. Порты ввода-вывода.
-
Базовое устройство языка ассемблера виртуальной машины. Типы команд, пример программы.
3. Цифровой логический уровень
-
Устройство транзистора, транзисторный инвертор
-
Вентиль. Простейшие булевы вентили. Выражение любой булевой формулы с помощью цифровой логической микросхемы. Интегральная схема.
-
Устройство мультиплексора.
-
Устройство декодера.
-
Устройство компаратора.
-
Устройство полусумматора.
-
Устройство полного сумматора.
-
Устройство одноразрядного арифметико-логического устройства. Принцип построения 8-битного АЛУ
-
Устройство защелки.
-
Устройство синхронной SR-защелки, синхронной D-защелки
-
Устройство 8-ми битной схемы памяти. 12-ти битная схема памяти с 3-мя выходами.
4. Уровень архитектуры команд
-
Четыре основных блока уровня архитектуры команд: модель памяти, регистры, типы данных, команды.
-
Модель памяти: ячейка памяти, слово памяти, выравнивание, адресное пространство.
-
Адресное пространство, регистры.
-
Команды, формат команд, типы команд.
5. Уровень операционной системы
-
Определение операционной системы как расширенной виртуальной машины
-
Определение операционной системы как менеджера ресурсов
-
Принцип работы ОС. Один цикл жизнедеятельности ОС.
-
Когда начинает работать ОС.
-
Прерывания. Прерывания по таймеру, программное прерывание.
6. Ввод-вывод
-
Устройство ввода-вывода. Контроллер устройства. Регистры контроллера, назначение, принцип работы.
-
Общение контроллера с процессором: при помощи портов, при помощи адресного пространства ввода-вывода.
-
Общее описание способов ввода-вывода: программный, при помощи прерываний, DMA.
-
Принцип работы ввода-вывода при помощи прерываний. Достоинства и недостатки.
-
Принцип работы ввода-вывода при помощи прямого доступа в память (DMA). Достоинства и недостатки.
7. Уровень языка ассемблера
-
Уровни языков. Компиляторы, трансляторы, ассемблеры.
-
Специфика языков ассемблера. Зачем нужны ассемблерные языки сегодня?
-
Пример формата языка ассемблера.
-
Процесс ассемблирования.
-
Компоновщик, описание процесса компоновки. Структура объектного модуля.
-
Связывание: раннее связывание, позднее связывание. Где, как и когда используется. Преимущества и недостатки.
Литература
-
Буза М.К. Архитектура ЭВМ. Минск: Новое знание, 2007. 560 стр.
-
Э. Таненбаум. Архитектура компьютера. 5-изд. СПБ.: Издательство “Питер”, 2007. 848 стр.
-
Полунов Ю.Л. От абака до компьютера: судьбы людей и машин. Книга для чтения по истории вычислительной техники в двух томах. Издательство “Русская редакция”, 2004.
Операционные системы
-
Понятие вытесняющей и невытяснющей многозадачности.
-
Различия между процессами и потоками.
-
Состояния процессов в многозадачной ОС.
-
Критерии планирования процессов и требования к алгоритмам планирования.
-
Алгоритм планирования First Come First Served (FCFS).
-
Алгоритм планирования Round Robin (RR).
-
Оптимальный алгоритм планирования и практические приближения к нему.
-
Механизмы синхронизации процессов.
-
Принцип локальности и организация памяти компьютера.
-
Связывание адресов.
-
Страничная и сегментно-страничная организация памяти.
-
Архитектурные средства поддержки страничной памяти. Многоуровневые таблицы страниц и ассоциативная память (TLB).
-
Алгоритмы First In First Out (FIFO) и Second Chance замещения страниц.
-
Алгоритм выталкивания не часто используемой страницы (NFU).
-
Рабочее множество страниц процесса и тренинг.
-
Модель взаимодействия открытых систем OSI.
-
Объединение сетей. Ретрансляторы, коммутаторы и маршрутизаторы.
-
Основные протоколы уровня Интернет стека сетевых протоколов TCP/IP.
-
IP-адреса и маршрутизация в Интернет.
-
Основные протоколы уровня узлов стека сетевых протоколов TCP/IP.
-
Служба доменных имен DNS.
Литература
-
Танненбаум Э. Современные операционные системы. 2-е издание.
-
Танненбаум Э. Вудхалл А. Операционные системы. Разработка и реализация. Классика CS.
-
Дейтел Х., Дейтел П., Чорнес Д. Операционные системы. Основы и принципы. Книга 1.
-
М. Руссинович. Внутреннее устройство Microsoft Windows: Windows Server 2003, Windows XP и Windows 2000.
-
Кабелова А., Досталек Л. TCP/IP и DNS в теории и на практике. Полное руководство.
-
Фейт С. TCP/IP. Архитектура, протоколы и реализация (включая IP версии 6 и IP Security).
Компьютерные сети
-
Требования, предъявляемые к XML документу. Правильные и состоятельные документы.
-
DTD. Назначение схем. Правила подключения DTD к XML документам. Внутренние и внешние DTD.
-
DTD. Правила и синтаксис описания элементов. Модель содержания.
-
DTD. Правила описания атрибутов.
-
DOM. Представление XML документа в DOM.
-
Пространство имен NameSpace. Назначение, связь с XML документом.
-
Область действия объявлений пространства имен в XML документе.
-
XML Schema. Синтаксис объявления элементов и атрибутов. Простые и сложные элементы.
-
XML Schema. Зачем и как объединяются элементы в группы. Элементы group, choice и all.
-
XML Schema. Задание правил вхождения элементов и атрибутов в XML документе с использованием атрибутов manicures и maxOccurs.
-
XML Schema. Задание правил вхождения элементов и атрибутов в XML документе с использованием атрибутов default, fixed и use.
-
XML Schema. Содержание элементов. Образование сложных элементов от простых.
-
XML Schema. Содержание элементов. Смешанное содержание.
-
XML Schema. Содержание элементов. Пустое содержание.
-
XML Schema. Ограничения. Задание ограничений на диапазон значений и на основе перечислений.
-
Ограничения. Задание ограничений на длину и с помощью шаблона.
Литература
-
Д. Мартин и др. XML для профессионалов. М.: Лори, 2001.
-
Ф. Бумфлей и др. XML: новые перспективы WWW. М.: ДМК, 2000.
-
Г.Е. Берман. Введение в XML Schema. Тверь. 2005.
Компьютерная графика
-
Растровые и векторные изображения. Рисование прямых линий на растровых устройствах.
-
Рисование простых графических примитивов.
-
Заполнение областей на растровых устройствах.
-
Аффинные преобразования на плоскости (сдвиг, масштабирование, вращение).
-
Определение принадлежности точки треугольнику.
-
Представление кривых сплайнами Безье. Свойства кривых Безье.
-
Алгоритмы обрисовки параметрических кривых.
-
Однородные координаты, аффинные и проективные преобразования в пространстве.
-
Удаление невидимых линий. Синтез трехмерной сцены.
10. Моделирование освещенности. Закрашивание грани (плоское, по Гуро, по Фонгу).
Литература
-
Роджерс Д., Адамс Дж. Математические основы машинной графики. М.,Мир, 2001.
-
Роджерс Д. Алгоритмические основы машинной графики. М.,Мир, 1989.
-
Шикин Е.В., Плис А.И. Кривые и поверхности на экране компьютера. М., Диалог-МИФИ, 1996.
-
Ньюмен У., Спрулл Р. Основы машинной графики. М., Мир, 1976.
-
Фоли Д., вэн Дэм А. Основы интерактивной машинной графики: В 2 кн. М, Мир, 1985.
-
Энджел И. Практическое введение в машинную графику. М., Радио и связь, 1984.
-
Препарата Ф., Шеймос М. Вычислительная геометрия: введение. М., Мир, 1989.
-
Шикин Е.В., Боресков А.В. Компьютерная графика. Полигональные модели. М., Диалог-МИФИ, 2000
-
Иванов В.П., Батраков А.С. Трехмерная компьютерная графика. М., Радио и связь, 1995.
-
Никулин Е.А. Компьютерная геометрия и алгоритмы машинной графики. BHV-Санкт-Петербург, 2003.
-
Математика и САПР, книга 2. М., Мир, 1989.
Основы дискретной математики
1. Булевы функции
-
Булевы функции. Табличное и геометрическое представления булевых функций. Формулы. Реализация булевых функций формулами. Булевы функции и логика высказываний.
-
Эквивалентность формул. Основные элементарные эквивалентности (логические тождества).
-
Дизъюнктивные и конъюнктивные нормальные формы. Совершенные ДНФ и КНФ.
-
Сокращенные ДНФ и их построение методом Блейка.
-
Многочлены Жегалкина. Единственность представления многочленом Жегалкина. Построение многочлена Жегалкина методом неопределенных коэффициентов.
-
Замкнутость и полнота классов булевых функций. Классы функций, сохраняющих ноль, единицу, монотонных, самодвойственных и линейных.
-
Теорема Поста о полноте.
2. Графы
-
Определение графов. Ориентированные и неориентированные графы и их представления: графическое, матрицей смежности, матрицей инцидентности, списками смежности. Нагруженные графы. Примеры использования графов.
-
Достижимость и связность. Нахождение матрицы достижимости. Нахождение компонент сильной связности и базы графа.
-
Двудольные (бихроматические) графы. Критерий двудольности.
-
Ориентированные и неориентированные деревья. Эквивалентность разных определений.
-
Минимальное остовное дерево графа и алгоритм его построения.
-
Четные графы. Эйлеровы циклы и алгоритм их нахождения.
-
Задача о кратчайших путях в графе. Алгоритм Дейкстры для нахождения кратчайших путей из одного источника.
-
Задача о лабиринте. Алгоритмы обхода графа “в глубину” и “в ширину”.
3. Применение графов для представления булевых функций
-
Логические схемы (схемы из функциональных элементов). Определение схем и их сложность.
-
Логические схемы и линейные программы.
-
Построение схемы двоичного сумматора.
-
Упорядоченные бинарные диаграммы решений (УБДР): определения и примеры.
-
Сокращенные УБДР и преобразование произвольной УБДР в сокращенную.
3.6. Построение сокращенной УБДР по формуле.
4. Конечные автоматы и формальные грамматики
-
Алфавиты, слова, языки. Операции над языками.
-
Недетерминированные и детерминированные конечные автоматы. Способы задания конечных автоматов: таблицы и диаграммы.
-
Теорема о детерминизации недетерминированных конечных автоматов.
-
Регулярные выражения и регулярные языки.
-
Теорема о распознавании регулярных языков конечными автоматами.
-
Свойства замкнутости класса автоматных языков.
-
Алгоритмические проблемы для конечных автоматов.
-
Теорема о разрастании. Примеры не конечно автоматных языков.
5. Алгоритмы и вычислимые функции
-
Структурные программы и вычислимые ими функции.
-
Рекурсивные функции. Операторы суперпозиции, примитивной рекурсии и минимизации. Рекурсивность функций, заданных с помощью ограниченного суммирования, сдвига, склейки и переименования переменных, разбора случаев.
-
Вычислимость рекурсивных функций программами.
-
Машины Тьюринга. “Тьюрингово” программирование: простейшие программы, реализация композиции, условного оператора и цикла.
5.5. Вычислимость рекурсивных функций на машинах Тьюринга. Тезис Тьюринга-
Черча.
Литература
-
Дехтярь М.И. Лекции по дискретной математике. Учебное пособие. – М.: Интернет-Университет Информационных технологий; БИНОМ. Лаборатория знаний, 2007.
-
Дехтярь М.И.. Дискретная математика. В кн.: Фонд контрольных заданий для квалификационной аттестации студентов факультета ПМиК Тверского госуниверситета по основам фундаментальных и компьютерных знаний: Учебн.-метод. Сб. – Тверь: Твер. Гос. Ун-т, 2007, 82-111
-
Столбоушкин А.П., Тайцлин М.А. Математические основания информатики. Часть 1 (глава 1и п. 2.1). Часть 2. ТвГУ,. Тверь, 1998.
-
Гаврилов Г.П., Сапоженко А.А. Сборник задач по дискретной математике. М., Наука, 1977.
-
Карпов Ю.Г. Теория автоматов.- СПб.: Питер, 2002.
Математическая логика и теория алгоритмов
1.1. Исчисление высказываний
1.1. Исчисление высказываний. Алфавит, формулы, секвенции. Схемы аксиом и правил
вывода. Доказательство. Примеры доказуемых секвенций.
Теорема об эквивалентности линейного доказательства и доказательства в виде дерева.
-
Эквивалентность формул. Булевы эквивалентности. Теорема о доказуемости булевых эквивалентностей.
-
Теорема о замене.
-
Нормальные формы. Теорема о существовании эквивалентных днф и кнф для каждой формулы.
-
Полнота. Теорема о полноте.
-
Непротиворечивость. Теорема о непротиворечивости.
1.2. Логика предикатов. Базы данных
1.7. Алгебраические системы. Язык логики предикатов. Формулы и термы.
Гомоморфизмы и их различные частные случаи.
Теорема о сохранении значений термов при гомоморфизмах.
-
Истинность формулы в системе на состоянии. Теорема о сохранении значений формул при изоморфизмах.
-
Базы данных. Описание свойств баз данных на языке логики предикатов.
1.10. Подсистемы. Теорема о подсистеме, порождённой множеством.
2.1. Сложность алгоритмов
-
Нумерация машин Тьюринга. Теорема о номере следующего слова Поста.
-
Теорема о рекурсивности функций, вычислимых на машинах Тьюринга.
-
Многоленточные машины Тьюринга. Базы данных как входы. Сигнализирующие функции. Классы сложности.
2.4. Теоремы о зависимости сигнализирующих от числа символов алфавита и числа
лент.
2.5. Вычисления в полиномиальное время. Полиномиальная вычислимость запросов,
формулируемых на языке логики предикатов первого порядка.
-
Полиномиальная сводимость. Теоремы о замкнутости PTIME и NPTIME относительно полиномиальной сводимости.
-
NP-полные проблемы. Теоремы об NP-полных проблемах.
-
NP-полнота SAT.
-
Машины Тьюринга со стеком. Первая теорема Кука о связи временной и емкостной сигнализирующих.
2.10. Машины Тьюринга со стеком. Вторая теорема Кука о связи временной и емкостной сигнализирующих.
2.2. Неразрешимость проблемы равенства в теории полугрупп
-
Неразрешимость проблемы остановки для машин Тьюринга.
-
Теорема о существование частично рекурсивной функции с нерекурсивной областью определения.
-
Полусистемы Туэ. Построение полусистемы Туэ по машине Тьюринга.
-
Ассоциативные исчисления. Построение ассоциативного исчисления по машине Тьюринга. Теорема о выводимости заключительного слова Поста.
-
Неразрешимость проблемы равенства в теории полугрупп.
-
Неразрешимость логики предикатов.
3.1. Неразрешимость логики предикатов на конечных моделях
-
Существование конечной модели и существование периодической модели в арифметике.
-
Построение формулы по машине Тьюринга.
-
Теорема о нерекурсивности множества номеров машин, сходящих с ленты, и множества номеров зацикливающихся машин.
-
Неразрешимость логики предикатов на конечных моделях.
3.2. Представление рекурсивных функций в арифметике
3.5. Функция Гёделя.
Китайская теорема об остатках.
-
Представление рекурсивных функций в арифметике. Теорема о представимости в арифметике каждой частично рекурсивной функции.
-
Теорема о неразрешимости арифметики.
3.3. Неполнота логики предикатов для PTIME
-
Игры Эренфойхта.
-
Неопределимость связности в логике предикатов.
3.10. Определимость связности в PTIME.
3.4. Метод резолюций
-
Метод резолюций в логике высказываний.
-
Самая общая унификация.
-
Метод резолюций в логике предикатов.
-
Машинное доказательство теорем.
Литература
-
А.П.Столбоушкин, М.А.Тайцлин. Математические основания информатики. Части 1, 2 и 3. Тверь, 1998.
-
М.А.Тайцлин. Теорема Кука.
-
А.И.Мальцев. Алгоритмы и рекурсивные функции. Москва. "Наука". 1965.
-
М.А.Тайцлин. Резолюции.
-
А.П.Столбоушкин, М.А.Тайцлин. Неразрешимость логики предикатов на конечных моделях.
-
С.Кук. Характеристики машинных автоматов в терминах вычислителей, ограниченных во времени. В книге: Сложность вычислений и алгоритмов, Москва, Мир,1974.
Основы программирования
-
Основные конструкции структурного программирования: присваивание, следование, ветвление, цикл.
-
Алгоритмы для решения теоретико-числовых и простейших вычислительных задач.
-
Подпрограммы и функциональное программирование. Рекурсивные алгоритмы.
-
Сложность вычислений. Время и память вычисления, максимальные и средние оценки.
-
Спецификация и верификация программ. Предусловия, постусловия, частичная и полная корректность, инвариант и ограничитель цикла.
-
Системы счисления и представление чисел в ЭВМ. Двоичная система счисления и побитовые операции.
-
Работа с текстом. Представление текста в ЭВМ. Обработка текста. Поиск текста.
-
Работа с файлами. Основные действия по обработке текстовых файлов (открытие, закрытие, чтение, запись).
9. Поиск в линейных структурах данных. Линейный поиск. Дихотомические методы поиска. Максимальное и среднее время работы алгоритмов.
-
Сортировка в линейных структурах данных. Квадратичные алгоритмы сортировки (пузырьком, вставками, выбором максимального элемента) и их модификации. Сортировки Шелла. Логарифмические методы сортировки (слияниями, Хоара). Максимальное и среднее время работы алгоритмов.
-
Динамическое распределение памяти. Динамические структуры данных. Списки (односвязные и двусвязные, линейные и кольцевые, многомерные). Деревья. Представления графов. Хеш-таблицы.
-
Объектно-ориентированное программирование. Построение классов, наследование, перегрузка операторов. Шаблоны.
Литература
Основная литература
-
Н.Вирт. Алгоритмы и структуры данных. М. Мир, 1984.
-
С.М.Дудаков. Математическое введение в информатику. Тверь: ТвГУ, 2003.
-
Д.Кнут. Искусство программирования для ЭВМ (три тома). М. Мир, 1978.
-
Стандарт языка C++
Дополнительная литература
-
В.Н.Агафонов. Математические основы обработки информации. Новосибирск, Изд-во НГУ, 1982.
-
Н.И.Вьюкова, В.А.Галатенко, А.Б.Ходулев. Систематический подход к программированию. М. Наука, 1988.
-
Д.Грис. Наука программирования. М. Мир, 1984.
-
Б.Мейер, К.Бодуэн. Методы программирования (два тома). М. Мир, 1982.
-
В.А.Непомнящий, О.М.Рякин. Прикладные методы верификации программ. М. Радио и связь, 1988.
-
Требования и спецификации в разработке программ. Сборник статей. М. Мир, 1984.
-
А.Филд, П.Харрисон. Функциональное программирование. М. Мир, 1993.
Алгоритмы и анализ сложности
1. Модели вычислений
1.1.Машины с произвольным доступом к памяти. Меры сложности вычислений. ПДП-машины и машины Тьюринга.
-
Линейные программы. Битовые линейные программы. Ветвящиеся программы (деревья сравнений).
-
Модельный алгоритмический язык. Сложность реализации основных конструкций на ПДП-машине.
1.4. Асимптотический анализ верхней и средней оценок сложности алгоритмов; сравнение наилучших, средних и наихудших оценок; O-, o-, ω- и θ-нотации.
2. Базовые структуры данных и основные методы разработки эффективных алгоритмов
-
Списки, стеки (магазины), очереди. Алгоритмы выполнения основных операций.
-
Графы, деревья, бинарные деревья. Способы представления. Алгоритмы обхода деревьев.
-
Метод разработки алгоритмов "разделяй и властвуй". Алгоритм умножения двоичных чисел. Техническая теорема об оценке роста функций, заданных реккурентными соотношениями. Передача сообщений с открытыми ключами (экспоненциация).
-
Динамическое программирование. Оптимальное умножение последовательности матриц. Алгоритм эффективного распознавания кс-языков. Задача глобального выравнивания слов.
3. Сортировка
-
Нижние оценки числа сравнений (в "худшем» и в "среднем").
-
Алгоритм сортировки обменами (методом "пузырька").
-
Алгоритм сортировки слиянием.
-
Алгоритм быстрой сортировки Хоара. Оценка сложности "в среднем".
-
Алгоритм пирамидальной сортировки (с помощью дерева).
-
Алгоритм лексикографической сортировки.
-
Алгоритмы нахождения k-го наименьшего элемента за линейное время.
3.8. Нижняя оценка числа сравнений для нахождения 2-го по величине элемента множества (теорема Кислицына).
4. Задачи поиска. Метод расстановки (хеширование)
-
Алгоритмы выполнения основных операций при использовании "внешних» и "внутренних» цепей.
-
Повторное хеширование. Выбор хеш-функции.
-
Оценки сложности алгоритмов хеширования.
5. Задачи поиска и работа с множествами
-
Деревья двоичного поиска. Алгоритм построения оптимального дерева двоичного поиска.
-
2-3-деревья. Алгоритмы вставки и удаления элементов из 2-3-дерева.
-
Алгоритмы выполнения операций (ОБЪЕДИНИТЬ, НАЙТИ) с использованием массивов и списков.
-
Алгоритмы выполнения операций (ОБЪЕДИНИТЬ, НАЙТИ) с использованием древовидных структур (сжатие путей).
-
Алгоритм проверки эквивалентности конечных автоматов.
5.7 Биномиальные и фиббоначиевы кучи и алгоритмы работы с ними.
-
В-деревья и алгоритмы работы с ними.
-
Структуры данных для представления пространственной информации: 2-d деревья, квадродеревья, R-деревья порядка k.
6. Алгоритмы на графах
-
Минимальное остовное дерево.
-
Поиск в глубину и поиск в ширину в неориентированных и ориентированных графах. Топологическая сортировка.
-
Алгоритм определения двусвязных компонент графа.
6..4. Алгоритмы построения транзитивного замыкания графа и нахождения кратчайших путей.
-
Задача о кратчайших путях из одного источника (алгоритм Дейкстры).
-
Задача о максимальном потоке в сетях. Алгоритм Форда - Фалкерсона.
-
Алгоритм нахождения максимального потока за кубическое время.
-
Простые сети и задача о максимальном паросочетании для двудольных графов.
Литература Основная:
1. А.Ахо, Дж.Хопкрофт, Дж. Ульман. Построение и анализ вычислительных
алгоритмов.- М.:Мир, 1979.
2. Т.Кормен, Ч.Лейзерсон, Р.Ривест, К. Штайн. Алгоритмы. Построение и анализ. Второе издание. Изд. “Вильямс”, М., 2005.
Дополнительная:
-
Н.Вирт. Алгоритмы и структуры данных. — М.:Мир, 1989.
-
Д.Кнут. Искусство программирования для ЭВМ. т.3. Сортировка и поиск. — М.: Мир, 1978.
-
В.Липский. Комбинаторика для программистов. -М.:Мир,1988
6. Х.Пападимитриу, К.Стайглиц. Комбинаторная оптимизация. Алгоритмы и
сложность.- М.:Мир, 1985.
Технологии баз данных
Программа квалификационного экзамена
-
Проектирование баз данных. Нормализация отношений.
-
Реляционная алгебра. Основные операции над отношениями (объединение, вычитание, декартово произведение, фильтрация, проекция).
-
Построение SQL-запросов. Оператор select. Внутренние и внешние соединения. Сортировка. Группировка и агрегатные функции. Подзапросы.
-
Изменение данных при помощи SQL-запросов. Операторы insert, delete, update.
-
Многопользовательский доступ к базам данных. Привилегии. Транзакции, уровни изолированности.
-
Построение приложений с использованием баз данных. Встроенный SQL для языка C. Статический и динамический SQL.
Литература
Основная литература
1. Документация PostgreSQL,
http://www.postgresql.org/docs/8.3/interactive/index.html
-
Дж. Дейт, Введение в системы баз данных, Вильямс: Киев, 2000.
-
СМ. Дудаков, Лекции по базам данных,
http://pmkinfo.tversu.ru/pmk/progr.php?dis=kr
Дополнительная литература
1. Документация Microsoft SQL Server,
http://msdn.microsoft.com/en-us/library/aa174556(SQL.80).aspx
-
Документация MySQL, http://dev.mysql.com/doc/
Программа вступительных испытаний в магистратуру по направлению
080800.68 Прикладная информатика
«Прикладная информатика в аналитической экономике»
Информатика
1. Функции.
Функции, возвращаемые значения, параметры и аргументы. Объявление и определение функций.
Локальные и глобальные переменные.
Дополнительные сведения о функциях. Рекурсия. Стек и рекурсия.
Достарыңызбен бөлісу: |