Утверждаю

Декан факультета ПМиК

А.В.Язенин

2008 г.

ПРОГРАММА

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

по направлению 010400 Информационные технологии Алгебра и геометрия 1. Системы линейных уравнений. Метод Гаусса решения систем линейных уравнений.

Определитель матрицы. Свойства определителя. Метод Крамера решения систем линейных уравнений.

2. Линейные пространства. Линейная зависимость и линейная независимость систем векторов. Базис и ранг системы векторов. Матрица перехода от одного базиса к другому. Координаты вектора в базисе. Изменение координат вектора при изменении базиса.

3. Кольцо многочленов. Делимость многочленов. Наибольший общий делитель двух многочленов. Алгоритм Евклида нахождения наибольшего общего делителя.

4. Линейные преобразования линейных пространств. Матрица линейного преобразования в базисе. Изменение матрицы линейного преобразования при изменении базиса.

5. Собственные числа и собственные векторы линейного преобразования.

Характеристический многочлен линейного преобразования. Нахождение собственных чисел и собственных векторов линейного преобразования.

6. Евклидовы пространства. Симметрические преобразования. Нахождение ортонормированного базиса, состоящего из собственных векторов симметрического преобразования.

7. Квадратичные формы. Приведение квадратичной формы к каноническому и нормальному виду. Метод Лагранжа и метод Якоби. Положительно определённые квадратичные формы. Критерий Сильвестра.

8. Гиперповерхности второго порядка в евклидовом пространстве. Классификация гиперповерхностей второго порядка.

Задачи 1. Вычислите определитель матрицы размера n n.

2. Для данной системы векторов арифметического пространства найдите базис и ранг этой системы.

3. Даны два многочлена из R[x ]. Найдите наибольший общий делитель этих многочленов.

4. Даны два базиса линейного пространства. Найдите матрицу перехода от первого базиса ко второму.

5. Даны координаты вектора x в базисе E и матрица перехода от базиса A к базису E.

Найдите координаты вектора x в базисе A.

6. Дана матрица линейного преобразования линейного пространства Rn в базисе E и матрица перехода от базиса E к базису A. Найдите матрицу преобразования в базисе A.

7. Дана матрица линейного преобразования линейного пространства Rn в некотором базисе E. Найдите собственные числа и собственные векторы преобразования.

8. Дана квадратичная форма. Приведите её к каноническому виду.

9. Дана квадратичная форма. Выясните, является ли она положительно определённой.

10. Дано уравнение поверхности второго порядка в R3. Определите тип этой поверхности.

Литература 1. Курош А.Г. Курс высшей алгебры. М.: Наука, 1975.

2. Глухов М.М., Елизаров В.П., Нечаев А.А. Алгебра: Учебник. В 2-х т.-М.: Гелиос АРВ, 2003.

3. Кострикин А.И. Введение в алгебру. М.: Наука, учебник, 1977.

4. Фаддеев Д.К., Соминский И.С. Сборник задач по высшей алгебре. М.: Наука, 1977.

5. Сборник задач по алгебре. Под ред. А.И.Кострикина, М.: Наука, 1995.

6. Мальцев А.И. Основы линейной алгебры. М.: Наука, 1970.

7. Калужнин А.Г. Введение в общую алгебру. М.: Наука, 8. Скорняков Л.А. Элементы общей алгебры. М.: Наука, 1983.

9. Фаддеев Д.К. Лекции по алгебре. М.: Наука, 1984.

10. Куликов Л.Я. Алгебра и теория чисел. М.: Высшая школа, 1979.

11. Проскуряков И.В. Сборник задач по линейной алгебре. М.: Юнимедиастайл, 2002.

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

1.1. Вещественные числа. Десятичная запись вещественного числа. Свойства вещественных чисел. Аксиома Архимеда. Свойство непрерывности.

1.2. Верхняя и нижняя грани числового множества, их характеристические свойства. Теорема о существовании верхней (нижней) грани у ограниченного сверху (снизу) числового множества.

1.3. Ограниченные отображения, верхняя и нижняя грани отображения.

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

2.1. Предел числовой последовательности, теорема о единственности предела числовой последовательности.

2.2. Бесконечно малые, бесконечно большие последовательности, их свойства.

Арифметические свойства сходящихся последовательностей.

2.3. Предельный переход в неравенствах. Теорема о существовании предела у ограниченной монотонной последовательности. Число “е”.

2.4. Теорема Больцано–Вейерштрасса о существовании частичного предела у ограниченной числовой последовательности. Верхний и нижний пределы последовательности.

2.5. Критерий Коши сходимости последовательности.

3. Предел функции.

3.1. Предел функции в точке по Гейне и по Коши; эквивалентность этих определений. Односторонние пределы в точке. Арифметические операции над функциями, имеющими предел.

';

3.2. Критерий Коши существования предела функции в точке.

3.3. Замечательные пределы.

3.4. Бесконечно малые и бесконечно большие функции, теоремы о них. Сравнение бесконечно малых функций. Эквивалентные бесконечно малые функции.

3.5. Теорема о пределе сложной функции.

4. Непрерывность функции.

4.1. Непрерывность функции в точке. Односторонняя непрерывность.

Арифметические операции над непрерывными функциями.

4.2. Свойство устойчивости знака непрерывной в точке функции.

4.3. Свойство локальной ограниченности непрерывной в точке функции.

4.4. Непрерывность элементарных функций.

4.5. Точки разрыва функции и их классификация. Теорема о точках разрыва монотонной на отрезке функции.

4.6. Первая теорема Коши (о прохождении непрерывной функции через нуль при 4.7. Вторая теорема Коши (о промежуточных значениях непрерывной на отрезке 4.8. Первая теорема Вейерштрасса (об ограниченности непрерывной на отрезке 4.9. Вторая теорема Вейерштрасса (о достижении верхней и нижней граней непрерывной на отрезке функцией).

4.10. Равномерная непрерывность. Теорема Кантора о равномерной непрерывности функции, непрерывной на отрезке.

4.11. Свойства открытых и замкнутых множеств. Компакт.

4.12. Теорема о равномерной непрерывности функции, непрерывной на компакте.

5. Производная и дифференциал.

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

5.2. Непрерывность функции, дифференцируемой в точке.

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

5.4. Производная сложной и обратной функций. Дифференцирование функции, заданной параметрически.

5.5. Производные элементарных функций.

5.6. Производные высших порядков. Формула Лейбница.

5.7. Дифференциал функции, геометрический смысл дифференциала. Правила вычисления дифференциала. Инвариантность формы первого дифференциала.

5.8. Дифференциалы высших порядков.

5.9. Лемма Дарбу о возрастании или убывании функции в точке.

5.10. Теорема Ферма о локальном экстремуме функции.

5.11. Теорема Ролля о нуле производной.

5.12. Теорема Лагранжа (формула конечных приращений).

5.13. Теорема Коши (обобщенная формула конечных приращений).

5.14. Первое и второе правило Лопиталя.

5.15. Формулы Тейлора и Маклорена с остаточным членом в форме Пеано.

5.16. Формула Тейлора с остаточным членом в форме Лагранжа.

5.17. Разложение элементарных функций по формуле Маклорена.

5.18. Необходимое и достаточное условия локального экстремума.

5.19. Выпуклость графика функции. Достаточное условие выпуклости графика 5.20. Необходимое и достаточное условия точки перегиба.

5.21. Асимптоты графика функции. Необходимое и достаточное условие существования наклонной асимптоты.

6. Неопределенный интеграл.

6.1. Первообразная и неопределенный интеграл. Основные свойства неопределенного интеграла. Таблица интегралов.

6.2. Замена переменной в неопределенном интеграле. Формула интегрирования по 6.3. Интегрирование рациональных дробей.

6.4. Интегрирование тригонометрических выражений, универсальная тригонометрическая подстановка.

6.5. Интегрирование простейших иррациональных функций.

7. Определенный интеграл.

7.1. Определенный интеграл Римана. Неинтегрируемость по Риману неограниченной на [а,в] функции.

7.2. Верхняя и нижняя интегральные суммы Дарбу, их основные свойства. Верхний и нижний интегралы Дарбу, их свойства. Основная лемма Дарбу.

7.3. Необходимые и достаточные условия интегрируемости функции по Риману. Теорема об интегрируемости непрерывной функции. Теорема об интегрируемости монотонной функции.

7.4. Свойства определенного интеграла.

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

7.6. Интеграл с переменным верхним пределом. Производная интеграла по переменному верхнему пределу. Формула Ньютона – Лейбница.

7.7. Замена переменной под знаком определенного интеграла. Правило интегрирования по частям для определенного интеграла.

7.8. Приложения определенного интеграла: вычисление площадей; вычисление 8. Несобственные интегралы.

8.1. Несобственные интегралы первого и второго рода. Критерий Коши сходимости несобственных интегралов.

8.2. Абсолютная и условная сходимость несобственных интегралов.

8.3. Признаки сходимости несобственных интегралов (общий и частный признаки 9. Числовые ряды.

9.1. Числовой ряд, сходимость и расходимость. Гармонический ряд. Необходимое условие сходимости ряда. Арифметические действия со сходящимися рядами.

Критерий Коши сходимости числового ряда.

9.2. Признаки сравнения числовых рядов. Признаки Даламбера и Коши сходимости 9.3. Абсолютная и условная сходимость ряда. Переместительный закон для абсолютно сходящегося ряда.

9.4. Признак Лейбница сходимости знакочередующегося ряда.

10. Функциональные последовательности и ряды.

10.1. Функциональные последовательности и ряды. Поточечная и равномерная сходимость последовательностей и рядов.

10.2. Критерий Коши равномерной сходимости последовательности и ряда.

Необходимое условие равномерной сходимости ряда. Признак Вейерштрасса равномерной сходимости функционального ряда.

10.3. Теорема о непрерывности суммы (предельной функции) равномерно сходящегося ряда (функциональной последовательности).

10.4. Теорема об интегрируемости суммы (предельной функции) равномерно сходящегося на [а,в] ряда (функциональной последовательности).

10.5. Теорема о дифференцируемости суммы (предельной функции) сходящегося на [а,в] ряда (функциональной последовательности).

10.6. Степенные ряды. Первая теорема Абеля. Радиус и интервал сходимости степенного ряда. Теорема о радиусе сходимости степенного ряда. Формулы для вычисления радиуса сходимости степенного ряда.

10.7. Функция, аналитическая в точке. Единственность представления аналитической в точке функции степенным рядом. Теорема о почленном дифференцированиии интегрировании степенного ряда.

10.8. Ряды Тейлора и Маклорена. Необходимое и достаточное условие разложимости функции в степенной ряд. Пример бесконечно дифференцируемой функции, не являющейся аналитической. Разложение в ряд Маклорена некоторых элементарных функций.

11. Функции нескольких переменных.

11.1. Предел последовательности точек пространства Rn. Лемма о сходимости последовательности точек в пространстве Rn. Лемма о фундаментальной последовательности; критерий Коши сходимости последовательности точек пространства Rn. Теорема Больцано – Вейерштрасса.

11.2. Предел функции n переменных в точке по Гейне и по Коши; эквивалентность этих определений. Арифметические операции над функциями, имеющими предел. Бесконечно малые функции n переменных.

11.3. Критерий Коши существования предела функции n переменных в точке.

11.4. Повторные пределы.

11.5. Непрерывность функции нескольких переменных в точке. Арифметические операции над непрерывными функциями. Непрерывность сложной функции.

11.6. Теорема об устойчивости знака непрерывной в точке функции. Теорема о прохождении непрерывной функцией через любое промежуточное значение.

11.7. Первая теорема Вейерштрасса (об ограниченности функции, непрерывной на 11.8. Вторая теорема Вейерштрасса (о достижении непрерывной на компакте функцией своих точных граней).

11.9. Равномерная непрерывность функции нескольких переменных. Теорема Кантора о равномерной непрерывности функции, непрерывной на компакте.

11.10. Частные производные. Дифференцируемость функции нескольких переменных.

Теорема о существовании частных производных дифференцируемой в точке 11.11. Непрерывность дифференцируемой в точке функции. Достаточное условие дифференцируемости функции в точке. Дифференциал функции нескольких 11.12. Дифференцирование сложной функции. Однородные функции степени p.

Теорема Эйлера об однородных функциях. Инваринтность формы первого дифференциала.

11.13. Производная по направлению. Градиент. Теорема о производной функции по направлению градиента.

11.14. Частные производные высших порядков. Достаточное условие равенства смешанных производных (случай функции двух переменных и случай функции n переменных). Дифференциалы высших порядков.

11.15. Формула Тейлора с остаточным членом в форме Лагранжа. Формула Тейлора с остаточным членом в форме Пеано (без доказательства).

11.16. Понятие локального экстремума. Необходимое условие локального экстремума.

11.17. Достаточное условие локального экстремума.

11.18. Условный экстремум. Метод множителей Лагранжа, необходимое условие локального экстремума.

11.19. Достаточные условия локального экстремума.

11.20. Касательная плоскость; нормальный вектор.

11.21. Понятие функции, заданной неявно. Теорема о неявной функции для случая а) одного уравнения с двумя переменными; в) одного уравнения с (n+1) 11.22. Неявные функции, определяемые системой функциональных уравнений.

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

11.23. Замена переменных для неявно заданных функций.

12. Кратные интегралы.

12.1. Собственные интегралы, зависящие от параметра. Теорема о непрерывности интеграла по параметру. Теорема о дифференцируемости интеграла по параметру (правило Лейбница).

12.2. Двойной интеграл. Теорема об интегрируемости непрерывной функции двух переменных (без доказательства). Свойства двойного интеграла. Теорема о 12.3. Приведение двойного интеграла к повторному а) случай прямоугольной области б) случай произвольной области.

12.4. Двойной интеграл в полярных координатах 12.5. Замена переменных в двойном интеграле 12.6. Геометрические приложения двойных интегралов: а) вычисление площадей б) вычисление объемов в) вычисление площадей поверхностей.

12.7. Тройной интеграл. Переход к повторному интегралу (без доказательства).

Замена переменных (без доказательства); цилиндрическая и сферическая системы координат.

12.8. Криволинейный интеграл 1-го рода; его свойства.

12.9. Криволинейный интеграл 2-го рода; его свойства.

12.10. Формула Грина. Вычисление площадей с помощью криволинейных интегралов.

12.11. Независимость криволинейного интеграла от пути интегрирования.

12.12. Поверхностные интегралы 1-го и 2-го рода. Теорема Гаусса–Остроградского (без доказательства).

13. Ряды Фурье.

13.1. Ортогональная тригонометрическая система. Ряд Фурье для абсолютно интегрируемой на [a,b] функции; ряд Фурье для четной и нечетной функции.

Ряд Фурье в случае произвольного интервала.

13.2. Сходимость ряда Фурье для кусочно-гладкой функции.

13.3. Неравенство Бесселя.

13.4. Признак Дини (без доказательства).

13.5. Сходимость рядов Фурье для функций, удовлетворяющих условию Гельдера.

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

13.7. Минимальное свойство коэффициентов Фурье. Равенство Парсеваля.

Почленное дифференцирование и интегрирование рядов Фурье.

1. Рудин Основы математического анализа. М.: Мир. 1976.

2. Фихтенгольц Г.М. Курс дифференциального и интегрального исчисления. Т. 1–3. М.:

Наука.

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

4. Ляшко И.И. Основы классического и современного математического анализа. - Киев, Выща школа. 1988.

1. Дьедонне. Основы современного анализа. М.: Мир, 1964.

2. Шварц, Лоран. Анализ т.1,2. М.:, 1972.

1. Берман Г.Н. Сборник задач по курсу математического анализа. М.: Наука, 1985.

2. Демидович Б.П. Сборник задач и упражнений по математическому анализу. М.:

Наука, 1977.

3. Кузнецов Л.А. Сборник заданий по высшей математике. Типовые расчеты. “Высшая школа”, М., 1994.

Прикладные задачи теории вероятностей I. Дискретное вероятностное пространство.

1. Дискретное вероятностное пространство.

2. Классическое определение вероятности. Гипергеометрическое распределение.

3. Теорема сложения. Условная вероятность. Теорема умножения. Независимость событий. Формула полной вероятности. Формулы Байеса.

4. Последовательность испытаний Бернулли. Наиболее вероятное число успехов в испытаниях Бернулли. Теорема Пуассона.

5. Математическое ожидание случайной величины.

6. Дисперсия случайной величины.

7. Независимость случайных величин. Математическое ожидание произведения случайных величин.

8. Ковариация. Дисперсия суммы n случайных величин.

9. Коэффициент корреляции и его свойства.

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

1. Аксиоматика теории вероятностей в общем случае.

2. Непрерывность вероятностной меры.

3. Измеримые функции. Определение случайной величины.

4. Функция распределения случайной величины и ее свойства.

5. Плотность распределения случайной величины и ее свойства.

6. Примеры непрерывных распределений.

7. Плотность распределения функции от случайной величины.

8. Многомерная функция распределения и ее свойства.

9. Многомерная плотность распределения и ее свойства.

10. Свертка распределений.

11. Характеристические функции и их свойства.

12. Центральная предельная теорема.

13. Интегральная теорема Муавра -Лапласа.

14. Цепи Маркова. Матрица вероятностей перехода. Вычисление переходных вероятностей.

1. Предмет и задачи математической статистики. Простой случайный выбор.

2. Точечное оценивание. Статистика. Несмещенность, состоятельность, эффективность.

3. Выборочное среднее. Его несмещенность и состоятельность.

4. Выборочная дисперсия. Смещеность, состоятельность.

5. Эмпирическая функция распределения.

6. Достаточные условия состоятельности оценок.

7. Метод моментов. Условия состоятельности оценок, полученных методом моментов.

Примеры.

8. Метод максимального правдоподобия.

9. Получение оценок параметров распределения методом минимума 2.

10. Распределения Пирсона и Стъюдента.

11. Интервальное оценивание. Доверительный интервал для математического ожидания случайной величины с известной дисперсией.

12. Доверительный интервал для вероятности события.

13. Интервальные оценки параметров нормального распределения.

14. Понятие статистической гипотезы. Простая гипотеза. Статистические критерии.

Критерий согласия, общая схема. Уровень значимости критерия. Ошибки первого и второго рода. Критическая область.

15. Критерий согласия Пирсона (критерий согласия 2 ) проверки простой гипотезы.

16. Модель линейной регрессии и метод наименьших квадратов.

17. Критерий 2 проверки гипотезы независимости случайных величин. "Проверка сопряжённости признаков".

18. Критерий 2 проверки гипотезы об однородности наблюдений.

19. Модель линейной регрессии. Коэффициент линейной регрессии. Остаточная дисперсия. Метод наименьших квадратов.

1. Севастьянов Б. А. Курс теории вероятностей и математической статистики.

2. Боровков А.А. Курс теории вероятностей.

3. Чистяков В.П. Курс теории вероятностей.

4. Ивченко Г. И., Медведев Ю.И. Математическая статистика 5. Гнеденко Б.В. Курс теории вероятностей.

6. Тутубалин Б.Н. Теория вероятностей.

7. Солодовников А.С. Теория вероятностей.

8. Ширяев А.Н. Вероятность.

1. Введение 1.1. Первый взгляд на архитектуру ЭВМ. Виртуальная машина, трансляция, интерпретация.

1.2. Современная многоуровневая машина 1.3. Архитектура фон-Неймана. Основные принципы, устройство. Примеры фонНеймановской и не фон-Неймановской архитектур.

1.4. Основные компоненты компьютера: центральный процессор, память, устройства ввода-вывода, шина.

1.5. Эволюция вычислительных систем, основные периоды.

2. Базовое устройство виртуальной машины 2.1. Устройство центрального процессора. Блок управления, АЛУ.

2.2. Регистры 2.3. Трак данных 2.4. Цикл работы центрального процессора 2.5. Память. Иерархическая структура памяти. Типы памяти.

2.6. Кэш-память, принцип локальности 2.7. Устройства ввода-вывода. Порты ввода-вывода.

2.8. Базовое устройство языка ассемблера виртуальной машины. Типы команд, пример программы.

3. Цифровой логический уровень 3.1. Устройство транзистора, транзисторный инвертор 3.2. Вентиль. Простейшие булевы вентили. Выражение любой булевой формулы с помощью цифровой логической микросхемы. Интегральная схема.

3.3. Устройство мультиплексора.

3.4. Устройство декодера.

3.5. Устройство компаратора.

3.6. Устройство полусумматора.

3.7. Устройство полного сумматора.

3.8. Устройство одноразрядного арифметико-логического устройства. Принцип построения 8-битного АЛУ 3.9. Устройство защелки.

3.10. Устройство синхронной SR-защелки, синхронной D-защелки 3.11. Устройство 8-ми битной схемы памяти. 12-ти битная схема памяти с 3-мя 4. Уровень архитектуры команд 4.1. Четыре основных блока уровня архитектуры команд: модель памяти, регистры, типы данных, команды.

4.2. Модель памяти: ячейка памяти, слово памяти, выравнивание, адресное пространство.

4.3. Адресное пространство, регистры.

4.4. Команды, формат команд, типы команд.

5. Уровень операционной системы 5.1. Определение операционной системы как расширенной виртуальной машины 5.2. Определение операционной системы как менеджера ресурсов 5.3. Принцип работы ОС. Один цикл жизнедеятельности ОС.

5.4. Когда начинает работать ОС.

5.5. Прерывания. Прерывания по таймеру, программное прерывание.

6. Ввод-вывод 6.1. Устройство ввода-вывода. Контроллер устройства. Регистры контроллера, назначение, принцип работы.

6.2. Общение контроллера с процессором: при помощи портов, при помощи адресного пространства ввода-вывода.

6.3. Общее описание способов ввода-вывода: программный, при помощи 6.4. Принцип работы ввода-вывода при помощи прерываний. Достоинства и 6.5. Принцип работы ввода-вывода при помощи прямого доступа в память (DMA).

Достоинства и недостатки.

7. Уровень языка ассемблера 7.1. Уровни языков. Компиляторы, трансляторы, ассемблеры.

7.2. Специфика языков ассемблера. Зачем нужны ассемблерные языки сегодня?

7.3. Пример формата языка ассемблера.

7.4. Процесс ассемблирования.

7.5. Компоновщик, описание процесса компоновки. Структура объектного модуля.

7.6. Связывание: раннее связывание, позднее связывание. Где, как и когда используется. Преимущества и недостатки.

1. Буза М.К. Архитектура ЭВМ. Минск: Новое знание, 2007. 560 стр.

2. Э. Таненбаум. Архитектура компьютера. 5-изд. СПБ.: Издательство “Питер”, 2007.

3. Полунов Ю.Л. От абака до компьютера: судьбы людей и машин. Книга для чтения по истории вычислительной техники в двух томах. Издательство “Русская редакция”, 1. Понятие вытесняющей и невытяснющей многозадачности.

2. Различия между процессами и потоками.

3. Состояния процессов в многозадачной ОС.

4. Критерии планирования процессов и требования к алгоритмам планирования.

5. Алгоритм планирования First Come First Served (FCFS).

6. Алгоритм планирования Round Robin (RR).

7. Оптимальный алгоритм планирования и практические приближения к нему.

8. Механизмы синхронизации процессов.

9. Принцип локальности и организация памяти компьютера.

10. Связывание адресов.

11. Страничная и сегментно-страничная организация памяти.

12. Архитектурные средства поддержки страничной памяти. Многоуровневые таблицы страниц и ассоциативная память (TLB).

13. Алгоритмы First In First Out (FIFO) и Second Chance замещения страниц.

14. Алгоритм выталкивания не часто используемой страницы (NFU).

15. Рабочее множество страниц процесса и трешинг.

16. Модель взаимодействия открытых систем OSI.

17. Объединение сетей. Ретрансляторы, коммутаторы и маршрутизаторы.

18. Основные протоколы уровня интернет стека сетевых протоколов TCP/IP.

19. IP-адреса и маршрутизация в Интернет.

20. Основные протоколы уровня узлов стека сетевых протоколов TCP/IP.

21. Служба доменных имен DNS.

1. Танненбаум Э. Современные операционные системы. 2-е издание.

2. Танненбаум Э. Вудхалл А. Операционные системы. Разработка и реализация.

Классика CS.

3. Дейтел Х., Дейтел П., Чорнес Д. Операционные системы. Основы и принципы. Книга 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 10. XML Schema. Задание правил вхождения элементов и атрибутов в XML документе с использованием атрибутов minOccurs и maxOccurs.

11. XML Schema. Задание правил вхождения элементов и атрибутов в XML документе с использованием атрибутов default, xed и use.

12. XML Schema. Содержание элементов. Образование сложных элементов от простых.

13. XML Schema. Содержание элементов. Смешанное содержание.

14. XML Schema. Содержание элементов. Пустое содержание.

15. XML Schema. Ограничения. Задание ограничений на диапазон значений и на основе перечислений.

16. Ограничения. Задание ограничений на длину и с помощью шаблона.

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 кн. М, Мир, 6. Энджел И. Практическое введение в машинную графику. М., Радио и связь, 1984.

7. Препарата Ф., Шеймос М. Вычислительная геометрия: введение. М., Мир, 1989.

8. Шикин Е.В., Боресков А.В. Компьютерная графика. Полигональные модели. М., Диалог-МИФИ, 9. Иванов В.П., Батраков А.С. Трехмерная компьютерная графика. М., Радио и связь, 10. Никулин Е.А. Компьютерная геометрия и алгоритмы машинной графики. BHVСанкт-Петербург, 2003.

11. Математика и САПР, книга 2. М., Мир, 1989.

1. Булевы функции 1.1. Булевы функции. Табличное и геометрическое представления булевых функций.

Формулы. Реализация булевых функций формулами. Булевы функции и логика высказываний.

1.2. Эквивалентность формул. Основные элементарные эквивалентности (логические тождества).

1.3. Дизъюнктивные и конъюнктивные нормальные формы. Совершенные ДНФ и КНФ.

1.4. Сокращенные ДНФ и их построение методом Блейка.

1.5. Многочлены Жегалкина. Единственность представления многочленом Жегалкина.

Построение многочлена Жегалкина методом неопределенных коэффициентов.

1.6. Замкнутость и полнота классов булевых функций. Классы функций, сохраняющих ноль, единицу, монотонных, самодвойственных и линейных.

1.7. Теорема Поста о полноте.

2. Графы 2.1. Определение графов. Ориентированные и неориентированные графы и их представления: графическое, матрицей смежности, матрицей инцидентности, списками смежности. Нагруженные графы. Примеры использования графов.

2.2. Достижимость и связность. Нахождение матрицы достижимости. Нахождение компонент сильной связности и базы графа.

2.3. Двудольные (бихроматические) графы. Критерий двудольности.

2.4. Ориентированные и неориентированные деревья. Эквивалентность разных определений.

2.5. Минимальное остовное дерево графа и алгоритм его построения.

2.6. Четные графы. Эйлеровы циклы и алгоритм их нахождения.

2.7. Задача о кратчайших путях в графе. Алгоритм Дейкстры для нахождения кратчайших путей из одного источника.

2.8. Задача о лабиринте. Алгоритмы обхода графа “в глубину” и “в ширину”.

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

3.2. Логические схемы и линейные программы.

3.3. Построение схемы двоичного сумматора.

3.4. Упорядоченные бинарные диаграммы решений (УБДР): определения и примеры.

3.5. Сокращенные УБДР и преобразование произвольной УБДР в сокращенную.

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

4. Конечные автоматы и формальные грамматики 4.1. Алфавиты, слова, языки. Операции над языками.

4.2. Недетерминированные и детерминированные конечные автоматы. Способы задания конечных автоматов: таблицы и диаграммы.

4.3. Теорема о детерминизации недетерминированных конечных автоматов.

4.4. Регулярные выражения и регулярные языки.

4.5. Теорема о распознавании регулярных языков конечными автоматами.

4.6. Свойства замкнутости класса автоматных языков.

4.7. Алгоритмические проблемы для конечных автоматов.

4.8. Теорема о разрастании. Примеры не конечно автоматных языков.

5. Алгоритмы и вычислимые функции 5.1. Структурные программы и вычислимые ими функции.

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

5.3. Вычислимость рекурсивных функций программами.

5.4. Машины Тьюринга. “Тьюрингово” программирование: простейшие программы, реализация композиции, условного оператора и цикла.

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

1. Дехтярь М.И. Лекции по дискретной математике. Учебное пособие. – М.: ИнтернетУниверситет Информационных технологий; БИНОМ. Лаборатория знаний, 2007.

2. Дехтярь М.И.. Дискретная математика. В кн.: Фонд контрольных заданий для квалификационной аттестации студентов факультета ПМиК Тверского госуниверситета по основам фундаментальных и компьютерных знаний: Учебн.-метод. Сб. – Тверь: Твер.

Гос. Ун-т, 2007, 82- 3. Столбоушкин А.П., Тайцлин М.А. Математические основания информатики. Часть 1 (глава 1и п. 2.1). Часть 2. ТвГУ,. Тверь, 1998.

4. Гаврилов Г.П., Сапоженко А.А. Сборник задач по дискретной математике. М., Наука, 1977.

5. Карпов Ю.Г. Теория автоматов.- СПб.: Питер, 2002.

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

Теорема об эквивалентности линейного доказательства и доказательства в виде дерева.

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

1.3. Теорема о замене.

1.4. Нормальные формы. Теорема о существовании эквивалентных днф и кнф для каждой формулы.

1.5. Полнота. Теорема о полноте.

1.6. Непротиворечивость. Теорема о непротиворечивости.

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

Гомоморфизмы и их различные частные случаи.

Теорема о сохранении значений термов при гомоморфизмах.

1.8. Истинность формулы в системе на состоянии. Теорема о сохранении значений формул при изоморфизмах.

1.9. Базы данных. Описание свойств баз данных на языке логики предикатов.

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

2.1. Сложность алгоритмов 2.1. Нумерация машин Тьюринга. Теорема о номере следующего слова Поста.

2.2. Теорема о рекурсивности функций, вычислимых на машинах Тьюринга.

2.3. Многоленточные машины Тьюринга. Базы данных как входы.

Сигнализирующие функции. Классы сложности.

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

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

2.6. Полиномиальная сводимость. Теоремы о замкнутости PTIME и NPTIME относительно полиномиальной сводимости.

2.7. NP-полные проблемы. Теоремы об NP-полных проблемах.

2.8. NP-полнота SAT.

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

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

2.2. Неразрешимость проблемы равенства в теории полугрупп 2.11. Неразрешимость проблемы остановки для машин Тьюринга.

2.12. Теорема о существование частично рекурсивной функции с нерекурсивной областью определения.

2.13. Полусистемы Туэ. Построение полусистемы Туэ по машине Тьюринга.

2.14. Ассоциативные исчисления. Построение ассоциативного исчисления по машине Тьюринга. Теорема о выводимости заключительного слова Поста.

2.15. Неразрешимость проблемы равенства в теории полугрупп.

2.16. Неразрешимость логики предикатов.

3.1. Неразрешимость логики предикатов на конечных моделях 3.1. Существование конечной модели и существование периодической модели в арифметике.

3.2. Построение формулы по машине Тьюринга.

3.3. Теорема о нерекурсивности множества номеров машин, сходящих с ленты, и множества номеров зацикливающихся машин.

3.4. Неразрешимость логики предикатов на конечных моделях.

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

Китайская теорема об остатках.

3.6. Представление рекурсивных функций в арифметике. Теорема о представимости в арифметике каждой частично рекурсивной функции.

3.7. Теорема о неразрешимости арифметики.

3.3. Неполнота логики предикатов для PTIME 3.8. Игры Эренфойхта.

3.9. Неопределимость связности в логике предикатов.

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

3.4. Метод резолюций 3.11. Метод резолюций в логике высказываний.

2.12. Самая общая унификация.

3.13. Метод резолюций в логике предикатов.

3.14. Машинное доказательство теорем.

1. А.П.Столбоушкин, М.А.Тайцлин. Математические основания информатики. Части 1, 2 и 3. Тверь, 1998.

2. М.А.Тайцлин. Теорема Кука.

3. А.И.Мальцев. Алгоритмы и рекурсивные функции. Москва. "Наука". 1965.

4. М.А.Тайцлин. Резолюции.

5. А.П.Столбоушкин, М.А.Тайцлин. Неразрешимость логики предикатов на конечных моделях.

6. С.Кук. Характеристики машинных автоматов в терминах вычислителей, ограниченных во времени. В книге: Сложность вычислений и алгоритмов, Москва, Мир,1974.

1. Основные конструкции структурного программирования: присваивание, следование, ветвление, цикл.

2. Алгоритмы для решения теоретико-числовых и простейших вычислительных задач.

3. Подпрограммы и функциональное программирование. Рекурсивные алгоритмы.

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

6. Системы счисления и представление чисел в ЭВМ. Двоичная система счисления и побитовые операции.

7. Работа с текстом. Представление текста в ЭВМ. Обработка текста. Поиск текста.

8. Работа с файлами. Основные действия по обработке текстовых файлов (открытие, закрытие, чтение, запись).

9. Поиск в линейных структурах данных. Линейный поиск. Дихотомические методы поиска. Максимальное и среднее время работы алгоритмов.

10. Сортировка в линейных структурах данных. Квадратичные алгоритмы сортировки (пузырьком, вставками, выбором максимального элемента) и их модификации.

Сортировки Шелла. Логарифмические методы сортировки (слияниями, Хоара).

Максимальное и среднее время работы алгоритмов.

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

Представления графов. Хеш-таблицы.

12. Объектно-ориентированное программирование. Построение классов, наследование, перегрузка операторов. Шаблоны.

Основная литература 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.2. Линейные программы. Битовые линейные программы. Ветвящиеся программы (деревья сравнений).

1.3. Модельный алгоритмический язык. Сложность реализации основных конструкций на ПДП-машине.

1.4. Асимптотический анализ верхней и средней оценок сложности алгоритмов;

сравнение наилучших, средних и наихудших оценок; O-, o-, - и -нотации.

2.1. Списки, стеки (магазины), очереди. Алгоритмы выполнения основных операций.

2.2. Графы, деревья, бинарные деревья. Способы представления. Алгоритмы обхода деревьев.

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

2.4. Динамическое программирование. Оптимальное умножение последовательности матриц. Алгоритм эффективного распознавания кс-языков. Задача глобального выравнивания слов.

3.1. Нижние оценки числа сравнений (в "худшем"и в "среднем").

3.2. Алгоритм сортировки обменами (методом "пузырька").

3.3. Алгоритм сортировки слиянием.

3.4. Алгоритм быстрой сортировки Хоара. Оценка сложности "в среднем".

3.5. Алгоритм пирамидальной сортировки (с помощью дерева).

3.6. Алгоритм лексикографической сортировки.

3.7. Алгоритмы нахождения k-го наименьшего элемента за линейное время.

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

4.1. Алгоритмы выполнения основных операций при использовании "внешних"и "внутренних"цепей.

4.2. Повторное хеширование. Выбор хеш-функции.

4.3. Оценки сложности алгоритмов хеширования.

5.1. Деревья двоичного поиска. Алгоритм построения оптимального дерева двоичного поиска.

5.2. 2-3-деревья. Алгоритмы вставки и удаления элементов из 2-3-дерева.

5.3. Алгоритмы выполнения операций (ОБЪЕДИНИТЬ, НАЙТИ) с использованием массивов и списков.

5.4. Алгоритмы выполнения операций (ОБЪЕДИНИТЬ, НАЙТИ) с использованием древовидных структур (сжатие путей).

5.5. Алгоритм проверки эквивалентности конечных автоматов.

5.7 Биномиальные и фиббоначиевы кучи и алгоритмы работы с ними.

5.8. В-деревья и алгоритмы работы с ними.

5.9. Структуры данных для представления пространственной информации: 2-d деревья, квадродеревья, R-деревья порядка k.

6.1. Минимальное остовное дерево.

6.2. Поиск в глубину и поиск в ширину в неориентированных и ориентированных графах. Топологическая сортировка.

6.3. Алгоритм определения двусвязных компонент графа.

6..4. Алгоритмы построения транзитивного замыкания графа и нахождения кратчайших путей.

6.5. Задача о кратчайших путях из одного источника (алгоритм Дейкстры)..

6.6. Задача о максимальном потоке в сетях. Алгоритм Форда- Фалкерсона.

6.7. Алгоритм нахождения максимального потока за кубическое время.

6.8. Простые сети и задача о максимальном паросочетании для двудольных графов.

Основная:

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

2. Т.Кормен, Ч.Лейзерсон, Р.Ривест, К. Штайн. Алгоритмы. Построение и анализ.

Второе издание. Изд. “Вильямс”, М., 2005.

Дополнительная:

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

4. Д.Кнут. Искусство программирования для ЭВМ. т.3. Сортировка и поиск. М.:

Мир, 1978.

5. В.Липский. Комбинаторика для программистов.-М.:Мир, 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 2. Дж.Дейт, Введение в системы баз данных, Вильямс: Киев, 2000.

3. С.М.Дудаков, Лекции по базам данных, http://pmkinfo.tversu.ru/pmk/progr.php?dis=kr Дополнительная литература 1. Документация Microsoft SQL Server, http://msdn.microsoft.com/en-us/library/aa174556(SQL.80).aspx 2. Документация MySQL, http://dev.mysql.com/doc/