Утверждено

_ подпись

от _ 20 г.

Примерная

основная образовательная программа

высшего профессионального образования

Направление подготовки

010500 Математическое обеспечение и администрирование информационных систем утверждено приказом Минобрнауки России от 17 сентября 2009 г. № 337 (постановлением Правительства РФ от 30.12.2009 г. № 1136).

ФГОС ВПО утвержден приказом Минобрнауки России от 08.12.2009 г.

№ 713.

Квалификация (степень) выпускника бакалавр по направлению Математическое обеспечение и администрирование информационных систем Нормативный срок освоения программы 4 года Форма обучения - очная.

Список профилей по направлению подготовки бакалавров Математическое обеспечение и администрирование информационных систем 1. Математические основы информатики;

2. Информационные системы и базы данных;

3. Параллельное программирование;

4. Системное программирование;

5. Технология программирования;

6. Администрирование информационных систем;

7. Реинжиниринг программного обеспечения.

Требования к результатам освоения основной образовательной программы Выпускник по направлению подготовки 010500 Математическое обеспечение и администрирование информационных систем с квалификацией (степенью) «бакалавр» должен обладать следующими компетенциями:

– общекультурными (ОК):

ОК 1. навыки межличностных отношений;

ОК 2. работа в команде;

ОК 3. приверженность этическим ценностям и здоровому образу жизни;

ОК 4. принятие различий и мультикультурности;

ОК 5. способность применять знания на практике;

ОК 6. исследовательские навыки;

ОК 7. способность учиться;

ОК 8. способность адаптироваться к новым ситуациям;

ОК 9. умение находить, анализировать и контекстно обрабатывать научно-техническую информацию;

ОК 10. фундаментальная подготовка по основам профессиональных знаний;

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

ОК 12. владеет основными методами, способами и средствами получения, хранения, переработки информации, имеет навыки работы с компьютером как средством управления информацией;

ОК 13. базовые знания в различных областях;

ОК 14. способность к анализу и синтезу;

ОК 15. способность к письменной и устной коммуникации на родном языке;

ОК 16. знание второго языка;

профессиональными (ПК):

ПК 1. определение общих форм, закономерностей, инструментальных средств для данной дисциплины;

ПК 2. умение понять поставленную задачу;

ПК 3. умение формулировать результат;

ПК 4. умение строго доказать математическое утверждение;

ПК 5. умение на основе анализа увидеть и корректно сформулировать математически тчныйрезультат;

ПК 6. умение самостоятельно увидеть следствия сформулированного ПК 7. умение грамотно пользоваться языком предметной области;

ПК 8. умение ориентироваться в постановках задач;

ПК 9. знание корректных постановок классических задач;

ПК 10. понимание корректности постановок задач;

ПК 11. самостоятельное построение алгоритма и его анализ;

ПК 12. понимание того, что фундаментальное математическое знание является основой компьютерных наук;

ПК 13. глубокое понимание сути точности фундаментального знания;

ПК 14. контекстная обработка информации;

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

ПК 16. выделение главных смысловых аспектов в доказательствах;

ПК 17. умение извлекать полезную научно-техническую информацию из электронных библиотек, реферативных журналов, сети Internet и т.п.;

ПК 18. умение публично представить собственные и известные научные результаты;

ПК 19 знать математические основы информатики как науки;

ПК 20 знать проблемы современной информатики, ее категории и связи с другими научными дисциплинами;

ПК 21 знать содержание, основные этапы и тенденции развития программирования, математического обеспечения и информационных технологий;

ПК 22 знать принципы обеспечения условий безопасности жизнедеятельности при эксплуатации аппаратуры и систем различного назначения;

ПК 23 знать проблемы и направления развития технологий программирования;

ПК 24 знать основные методы и средства автоматизации проектирования, производства, испытаний и оценки качества программного обеспечения;

ПК 25 знать направления развития компьютеров с традиционной (нетрадиционной) архитектурой; тенденции развития функций и архитектур проблемно-ориентированных программных систем и комплексов;

ПК 26 знать проблемы и тенденции развития рынка программного обеспечения;

ПК 27 знать основные концептуальные положения функционального, логического, объектно-ориентированного и визуального направлений программирования, методы, способы и средства разработки программ в рамках этих направлений;

ПК 28 знать методы проектирования и производства программного продукта, принципы построения, структуры и приемы работы с инструментальными средствами, поддерживающими создание программного обеспечения (ПО);

ПК 29 знать методы организации работы в коллективах разработчиков ПО, направления развития методов и программных средств коллективной разработки ПО;

ПК 30 знать архитектуру, алгоритмы функционирования систем реального времени и методы проектирования их программного обеспечения;

ПК 31 иметь навыки использования современных системных программных средств: операционных систем, операционных и сетевых оболочек, сервисных программ;

ПК 32 иметь навыки использования метода системного моделирования при исследовании и проектировании программных систем;

ПК 33 иметь навыки разработки моделирующих алгоритмов и реализации их на базе языков и пакетов прикладных программ ПК 34 иметь навыки использования основных моделей информационных технологий и способов их применения для решения задач в предметных областях;

ПК 35 иметь навыки выбора архитектуры и комплексирования современных компьютеров, систем, комплексов и сетей системного администрирования;

ПК 36 иметь навыки выбора, проектирования, реализации, оценки качества и анализа эффективности программного обеспечения для решения задач в различных предметных областях.

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

ПРИМЕРНЫЙ УЧЕБНЫЙ ПЛАН

подготовки бакалавра по направлению 010500"Математическое обеспечение и администрирование информационных систем" Наименование дисциплин (в том числе № п/п практик) Б.1 Гуманитарный, социальный и экономический цикл Вариативная часть, в т.ч. дисциплины 4 по выбору (англ., франц., немецк.) Б.2 Математический и естественнонаучный Вариативная часть, в т.ч. дисциплины Методы вычислений II / Методы Экстремальные задачи / Теоретические основы криптографии Уравнение математической физики / Математические основы компьютерной Базовая (общепрофессиональная) часть 50 1 Основы безопасности жизнедеятельности 2 Дифференциальные уравнения 3 Функциональный анализ 4 Теория вероятностей и математическая 5 Дискретная математика 6 Математическая логика 7 Структуры и алгоритмы компьютерной 8 Архитектура вычислительных систем и компьютерных сетей 9 Операционные системы и оболочки 11 Технология разработки программного Теория вычислительных процессов и Вариативная часть, в т.ч. дисциплины Профиль "Теоретическое программирование" программирование Теоретические основы логического Профиль "Информационные системы и базы данных" Основы построения информационных Профиль "Параллельное программирование" Теоретические основы параллельного программирования Языки параллельного программирования Профиль "Системное программирование" Управление программными проектами Трансляция языков программирования Профиль 5 "Технология программирования" Управление программными проектами Визуальное моделирование Профиль 6 "Администрирование информационных систем" Информационные проекты Профиль 7 "Реинжиниринг программного обеспечения" Эволюция систем программирования Реинжиниринг системного Б.5 Учебная и производственная практики обучающегося) Б.6 Итоговая государственная аттестация *)Состав дисциплин определяется вузом на основании его научных традиций, с учетом рекомендаций работодателей и в соответствии с профилем подготовки.

Бюджет времени, в неделях Настоящий учебный план составлен, исходя из следующих данных (в зачетных единицах):

Теоретическое обучение, включая экзаменационные сессии Практики (в том числе научно-исследовательская работа) Б.2.1 Математический анализ

СОДЕРЖАНИЕ КУРСА

I. Введение Основные сведения о множествах. Отображения. Краткие сведения о вещественных числах. Счетные множества. Несчетность отрезка.

II. Последовательности в метрических пространствах Понятия метрического и нормированного пространства. Предел последовательности и его свойства.

Евклидово пространство. Скалярное произведение. Точки и множества в метрическом пространстве.

Компактность. Компактные множества в евклидовом пространстве. Принцип выбора Больцано – Вейерштрасса.

Сходимость и сходимость в себе. Бесконечно большие и бесконечно малые. Границы числовых множеств.

Предел монотонной последовательности. Число e. Верхний и нижний пределы последовательности.

III. Пределы и непрерывность отображений Предел отображения и его свойства. Критерий сходимости Больцано – Коши для отображений. Двойной и повторный пределы. Непрерывные отображения. Теоремы Больцано – Коши о промежуточных значениях.

Теоремы Вейерштрасса. Равномерная непрерывность. Признак непрерывности монотонной функции. Теоремы об обратной функции. Определение и свойства элементарных функций. Замечательные пределы.

Асимптотические разложения.

IV. Дифференциальное исчисление функций одной переменной Определения. Геометрический смысл производной. Правила дифференцирования. Производные высших порядков. Основные теоремы дифференциального исчисления. Формула Тейлора. Разложение некоторых элементарных функций по формуле Тейлора. Раскрытие неопределенностей. Исследование функций с помощью производной. Экстремумы. Выпуклые функции, их свойства. Неравенства Гельдера и Минковского.

V. Интегральное исчисление функций одной переменной Первообразная и неопределенный интеграл. Правила интегрирования. Интегрирование элементарных функций (в основном – на практических занятиях). Интеграл Римана. Интегрируемость непрерывной функции.

Свойства интеграла. Теоремы Барроу и Ньютона – Лейбница. Формула Тейлора с остатком в интегральной форме. Интегральные неравенства. Геометрические приложения интеграла: площади, объемы, длина дуги.

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

VI. Числовые ряды Основные определения. Простейшие признаки сходимости для положительных рядов. Признаки Лейбница и Дирихле. Абсолютная сходимость. Теорема о перестановке членов абсолютно сходящегося ряда. Двойные и повторные ряды. Почленное умножение рядов. Последовательности и ряды с комплексными числами.

VII. Дифференциальное исчисление функций нескольких переменных Линейные операторы в евклидовых пространствах. Норма оператора. Дифференцируемые отображения, их свойства. Формула Лагранжа для вектор-функций. Дифференцируемость и частные производные. Матрица Якоби. Частные производные высших порядков. Многомерная формула Тейлора. Экстремумы. Теоремы об обратное и неявно заданном отображении. Относительные экстремумы.

VIII. Функциональные последовательности и ряды Равномерная сходимость. Непрерывность предельных функций. Предельный переход под знаком интеграла и производной. Степенные ряды: радиус сходимости, равномерная сходимость, почленное дифференцирование и интегрирование. Ряд Тейлора. Экспонента и тригонометрические функции комплексного аргумента.

Формулы Эйлера. Разложения логарифма и арктангенса. Формула Стирлинга. Биномиальный ряд.

IX. Криволинейные интегралы на плоскости Интеграл по пути. Точные и замкнутые дифференциальные формы. Условие независимости интеграла от пути. Свойства интеграла от замкнутой дифференциальной формы. Первообразная вдоль пути.

X. Функции комплексной переменной Комплексная дифференцируемость. Условия Коши – Римана. Интегральная теорема Коши. Представление голоморфной функции с помощью формулы Коши. Разложение голоморфной функции в ряд Тейлора, ее бесконечная дифференцируемость. Теорема Лиувилля. Основная теорема высшей алгебры. Голоморфные и гармонические функции. Теорема единственности. Принцип максимума. Понятие об аналитическом продолжении и полной аналитической функции. Логарифм и степенная функция комплексной переменной.

Ряды Лорана. Особые точки. Теорема Сохоцкого. Вычисление интегралов с помощью вычетов. Лемма Жордана. Понятие о конформном отображении. Дробно-линейные функции. Принцип аргумента. Теорема Руше.

XI. Мера и интеграл Полукольца и сигма-алгебры множеств. Мера. Внешняя мера. Распространение меры с полукольца на сигма-алгебру. Свойства измеримых множеств. Мера Лебега в евклидовом пространстве. Мера Лебега при линейном отображении. Измеримые функции, их свойства. Приближение измеримых функций простыми и ступенчатыми. Эквивалентные функции. Сходимость по мере. Определение интеграла по мере, суммируемые функции. Свойства интеграла. Теоремы Леви, Фату и Лебега о предельном переходе под знаком интеграла.

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

Интеграл Лебега - Стилтьеса. Интегралы от суммируемых функций, зависящие от параметра. Предельный переход под знаком интеграла, непрерывность по параметру. Интегрирование и дифференцирование по параметру. Несобственные интегралы, зависящие от параметра. Гамма-функция.

XII. Интегрирование на многообразиях Гладкие многообразия в евклидовых пространствах: основные понятия. Край и ориентация многообразия.

Мера на многообразии. Интеграл I рода. Дифференциальные формы. Внешнее дифференцирование. Замена переменных в дифференциальных формах. Интегрирование дифференциальных форм. Поверхностные и криволинейные интегралы II рода. Общая формула Стокса. Основные формулы теории поверхностных и криволинейных интегралов: классическая формула Стокса, формула Грина, формула Гаусса-Остроградского.

XIII. Ряды Фурье и приближение функций Пространства Лебега: их полнота, плотные множества в них. Непрерывность сдвига. Ортогональные системы и ряды Фурье в гильбертовом пространстве. Неравенство Бесселя. Теоерма Рисса – Фишера. Теорема о характеристике ортогонального базиса. Тригонометрические ряды Фурье. Модуль непрерывности. Теорема Римана – Лебега. Принцип локализации. Признак Дини сходимости рядов Фурье, следствия. Суммирование рядов. Свойства свертки. Теоерма об аппроксимативной единице. Теорема Фейера. Равенство Парсеваля.

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

Б.2.2. Алгебра и теория чисел Множества. Бинарные отношения, эквивалентность, фактормножество. Отображения. Композиция отображений, обратимые отображения. Бинарные алгебраические действия. Основные алгебраические структуры: группа, кольцо, модуль. Подструктуры. Изоморфные структуры. Разные типы колец. Идеал и факторкольцо.

II. Делимость в кольцах Свойства делимости в коммутативном кольце с 1. Ассоциированность. Наибольший общий делитель в кольце главных идеалов. Евклидовы кольца, алгоритм Евклида. Простые элементы евклидова кольца, основная теорема арифметики.

III. Целые числа и кольца вычетов Простые и составные числа, бесконечность множества простых. Каноническое разложение целого числа.

Идеалы кольца целых чисел. Сравнения и кольца вычетов. Обратимые классы. Теоретико-числовая функция Эйлера. Полная и приведенная системы вычетов. Теорема Лагранжа для конечных абелевых групп и ее теоретико-числовые следствия. Китайская теорема об остатках.

IV. Первоначальные сведения о многочленах Кольцо многочленов от одной переменной над коммутативным кольцом с 1. Степень многочлена и ее свойства. Теорема о делении с остатком для многочленов. Значение многочлена в точке, функциональное равенство многочленов. Теорема Безу. Схема Горнера. Корень многочлена, теорема о числе корней.

Многочлены от нескольких переменных. Теорема о тождестве.

V. Комплексные числа Определение поля комплексных чисел. Действия в компонентах. Комплексное сопряжение. Геометрическая интерпретация. Модуль и аргумент. Тригонометрическая форма записи, связь с действиями. Формула Муавра и ее применение в вещественных вычислениях. Извлечение корня из комплексного числа. Корни из 1. Решение алгебраических уравнений. Формулировка основной теоремы алгебры. Канонические разложения комплексных и вещественных многочленов.

VI. Матрицы и операции над ними: 4 ч. лекций и 2 ч. практических занятий Сложение матриц, умножение матрицы на скаляр. Умножение матриц. Единичная матрица.

Транспонирование. Свойства матричных операций.

VII. Определители Определители второго и третьего порядков. Перестановки и инверсии, четность перестановки.

Определение детерминанта квадратной матрицы произвольного порядка. Определитель транспонированной матрицы. Перестановка строк и свойства линейности. Разложение по строке. Методы вычисления определителей. Определитель Вандермонда. Формулировка теоремы Лапласа. Ранг матрицы в терминах ее миноров. Неизменность ранга при элементарных преобразованиях. Ранг трапециевидной матрицы.

VIII. Системы линейных уравнений Матричная запись линейной системы. Теорема Крамера. Метод Гаусса. Теорема Кронекера-Капелли. Число решений линейной системы. Однородные системы, условия существования нетривиального решения. Связь между решениями неоднородной и соответствующей однородной систем.

Алгебра квадратных матриц Некоммутативность матричного кольца, делители нуля. Многочлен от матрицы. Определитель произведения квадратных матриц. Невырожденные матрицы, полная линейная группа. Взаимная матрица и ее свойства. Обратная матрица, методы ее вычисления. Собственные числа и собственные векторы матрицы, характеристический многочлен. Теорема Гамильтона-Кэли.

IX. Линейные пространства Определение и примеры. Система образующих, конечномерные пространства. Линейная независимость векторов. Базис, размерность. Координаты вектора, их изменение при изменении базиса. Матрица перехода.

Подпространство, его размерность. Ранг матрицы как размерность линейной оболочки ее строк, столбцов.

Эквивалентность разных определений ранга. Факторпространство. Сумма и пересечение подпространств, связь между размерностями. Прямая сумма подпространств, внешняя прямая сумма.

X. Пространства с формами Билинейная и полуторалинейная форма на линейном пространстве. Матрица Грама., ранг формы.

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

Ортонормированные базисы. Унитарная и ортогональная группы. Процесс ортогонализации Грама-Шмидта.

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

Квадратичная форма на пространстве, связь с однородными многочленами. Полярная билинейная форма.

Метод Лагранжа приведения квадратичной формы к диагональному виду. Каноническая матрица комплексной или вещественной квадратичной формы. Закон инерции вещественных квадратичных форм, индексы инерции.

Угловые миноры матрицы, теорема Якоби. Признаки положительной определенности квадратичной формы.

Формулировка теоремы об ортогональном приведении формы.

XI. Дальнейшие сведения о многочленах Производная многочлена и ее свойства. Кратные корни и производная. Освобождение от кратных корней.

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

Редукция целочисленного многочлена, редукционный признак неприводимости. Теорема Гаусса о целочисленных многочленах. Признак Эйзенштейна. Рациональные корни целочисленного многочлена.

Алгоритм разложения целочисленного многочлена на неразложимые множители.

XII. Элементы теории групп Циклические группы, классификация. Подгруппа, примеры. Умножение подмножеств в группе. Смежные классы по подгруппе, разложение Лагранжа, индекс подгруппы. Теорема Лагранжа о группах. Порядок элемента. Нормальная подгруппа. Факторгруппа. Групповой гомоморфизм, его ядро и образ. Первая теорема о гомоморфизме, ее применение к вычислению факторгруппы. Прямое произведение групп и разложение группы в прямое произведение своих подгрупп. Формулировка теоремы о строении конечно порожденной абелевой группы. Подгруппа и нормальная подгруппа, порожденные данным множеством. Центр и коммутант. Критерий абелевости факторгруппы. Автоморфизмы группы. Факторгруппа группы по ее центру. Построение свободной группы, универсальное свойство. Соотношения между образующими, определяющие соотношения. Теорема Дика. Примеры задания группы образующими и определяющими соотношениями.

XIII. Расширения полей Простые поля, классификация. Расширение подполя, получающееся присоединением подмножества большего поля; простое расширение. Алгебраические и трансцендентные элементы. Аннуляторы, минимальный аннулятор. Конечное расширение, степень расширения. Алгебраические расширения, алгебраичность конечного расширения. Простое расширение, порожденное алгебраическим элементом;

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

Существование и единственность поля, содержащего данное число элементов. Подполя конечного поля.

Неприводимые многочлены над конечным полем.

XIV. Линейные отображения Линейное отображение, его ядро и образ. Ранг и дефект. Матрица линейного отображения, каноническая матрица. Пространство линейных отображений, связь с матричным пространством. Композиция линейных отображений. Изоморфность линейного отображения. Двойственное пространство. Свойство рефлексивности для конечномерного пространства. Двойственные базисы. Ковариантность и контравариантность изменения координат. Линейный оператор и его матрица, связь алгебры операторов с матричной алгеброй. Условия обратимости оператора.

XV. Алгебра линейных операторов Инвариантное подпространство. Сужение оператора на инвариантное подпространство; индуцированный оператор на факторпространстве. Матрица оператора при наличии инвариантного подпространства, при разложении пространства в прямую сумму инвариантных подпространств. Собственное число и собственный вектор оператора. Характеристический многочлен оператора, теорема Гамильтона-Кэли. Собственное подпространство и его свойства. Оператор, имеющий диагональную матрицу в некотором базисе; критерий диагонализуемости. Аннулятор вектора, свойства аннуляторов. Циклическое подпространство, клетка Фробениуса. Примарные подпространства и их свойства. Корневой вектор и корневое подпространство.

Нильпотентный оператор, его характеристический многочлен. Построение жордановой матрицы нильпотентного оператора. Жорданова матрица произвольного оператора. Естественные нормальные формы матрицы оператора в пространстве над произвольным полем.

XVI. Операторы в евклидовых и унитарных пространствах Сопряженный оператор. Инвариантные подпространства для сопряженных операторов. Условие ортонормальной диагонализуемости оператора. Нормальный оператор к унитарном и евклидовом пространстве.

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

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

Унитарные и ортогональные операторы. Полярное разложение.

XVII. Алгебры Тело классических кватернионов как вещественная подалгебра алгебры комплексных матриц. Алгебры с 1.

Алгебра с делением. Алгебра Ли, связь с ассоциативной алгеброй. Структурные константы и структурный тензор алгебры. Изоморфные алгебры. Алгебра с инволюцией, процесс удвоения Кэли-Диксона. Алгебра кватернионов как удвоенная алгебра комплексных чисел. Скалярная и векторная часть кватерниона; умножение векторов. Норма кватерниона и ее свойства. Формулировка теоремы Фробениуса. Алгебра Кэли и ее свойства.

Внешняя алгебра, градуирующие подпространства. Свойства внешнего умножения векторов. Определение детерминанта в терминах внешней алгебры. Теорема Лапласа. Формула Бинэ-Коши.

Б.2.3. Геометрия и топология I. Введение Историческое введение. Предмет и роль геометрии в современной математике.

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

Аффинная и декартова системы координат. Переход от одной системы координат к другой. Задание фигур уравнениями и неравенствами.

Уравнение гиперплоскости. Теорема о линейном неравенстве, расстояние от точки до гиперплоскости, нормальное уравнение гиперплоскости. Взаимное расположение гиперплоскостей. Уравнение прямой.

Взаимное расположение прямой и гиперплоскости. Взаимное расположение двух прямых в пространстве.

Классификация кривых второго порядка. Фокальные свойства, директриса, полярное уравнение, касательные и оптические свойства для кривых второго порядка. Асимптоты гиперболы.

Классификация поверхностей второго порядка (п.в.п.). Внешний вид п.в.п. Прямолинейные образующие на п.в.п. Матричные уравнения п.в.п. Взаимное расположение прямой и п.в.п. Центры п.в.п. Диаметральные, касательные и плоскости «границы теней» для п.в.п. Понятие об инвариантах п.в.п. n-мерное евклидово пространство, его гиперплоскости и прямые.

III. Элементы общей топологии Топология в множестве. База. Метрические пространства. Подпространства. Расположение точек относительно множества. Непрерывные отображения и гомеоморфизмы. Связность. Линейная связность.

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

IV. Элементы теории выпуклых множеств (в.м.) Выпуклые множества и выпуклые комбинации точек. Замыкание и внутренность в.м. Лемма о луче, строение границы выпуклого тела. Непустота относительной внутренности. Выпуклая оболочка множества.

Теоремы Радона, Хелли и Каратеодори. Компактность выпуклой оболочки компактного множества. Теоремы отделимости. В.м. как пересечение опорных полупространств. Крайние точки в.м., теорема Крейна-Мильмана.

Радиус Юнга множества. Неравенство Фенхеля для кривизны замкнутой кривой.

V. Дифференциальная геометрия Геометрическая кривая. Касательная. Ориентация. Соприкасающаяся плоскость. Длина кривой.

Натуральная параметризация. Кривизна и кручение. Формулы Френе. Вид кривой вблизи обыкновенной точки.

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

Ориентация. Касательная плоскость. Первая квадратичная форма и внутренняя геометрия поверхности.

Основной оператор поверхности и вторая билинейная форма. Формула Дарбу. Теоремы Эйлера и Менье.

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

Локальная теорема Гаусса о сферическом отображении. Деривационные формулы. Уравнения геодезических.

Основные уравнения теории поверхностей. Теорема ‘egregium’ Гаусса. Теорема об омбилической поверхности. Теорема Бонне (без доказательства).

VI. Фундаментальная группа (ф.г.) топологического пространства (т.п.) Гомотопии. Гомотопические эквивалентности. Определение ф.г. Фундаментальная группа произведения т.п. Изоморфизм переноса начала ф.г. Односвязные т.п. Теорема о накрывающем пути. Ф.г. окружности. Ф.г. S^n при n 2 (лемма Лебега). Ф.г. RP^n.

Поведение ф.г. при непрерывном отображении. Ретракции и деформационные ретракции.

Теоремы Борсука и Брауэра. Основная теорема алгебры.

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

СОДЕРЖАНИЕ КУРСА

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

II. Интегральные кривые на плоскости Дифференциальные уравнения первого порядка, разрешенные относительно производной (основные положения теории и методы решения интегрируемых уравнений). Дифференциальные уравнения в симметричной форме (обыкновенные и особые решения, интегралы). Дифференциальные уравнения, не разрешенные относительно производной (метод введения параметра, уравнения Клеро и Лагранжа), траектории автономных систем на плоскости. Фазовый портрет системы.

III. Линейные дифференциальные уравнения высших порядков Линейные однородные уравнения. Векторное пространство решений. Вронскиан. Общее решение.

Однородное уравнение с постоянными коэффициентами. Линейное неоднородное уравнение. Метод неопределенных коэффициентов и метод Лагранжа. Краевая задача и функция Грина.

IV. Линейные системы дифференциальных уравнений Линейная однородная система. Формула Остроградского-Лиувилля. Общее решение. Метод Эйлера интегрирования однородного уравнения в постоянными коэффициентами. Экспонента матрицы.

Фундаментальная матрица уравнения с постоянными коэффициентами. Неоднородная система. Формула вариации произвольной постоянной. Периодическое решение системы с периодической неоднородностью.

Особые точки типа узел, седло, фокус, центр.

V. Существование, единственность и продолжимость решений Нормальная система дифференциальных уравнений в векторной форме. Условие Липшица. Метод последовательных приближений Пикара. Максимальный интервал существования решения.

VI. Зависимость решений от начальных данных и параметров Непрерывная зависимость решений от начальных данных и параметров. Дифференцируемость решений по начальным данным и параметрам. Система в вариациях. Метод малого параметра. Общее решение и общий интеграл. «Выпрямление» интегральных кривых. Виды траекторий автономных систем. Линейные дифференциальные уравнения с частными производными первого порядка.

VII. Устойчивость решений Понятие устойчивости решения по Ляпунову. Устойчивость линейных систем. Исследование устойчивости решений методом функций Ляпунова. Устойчивость и неустойчивость решения по первому приближению.

Б.3.3 Функциональный анализ I. Общие сведения, связанные с метрическими пространствами Определение и непрерывность метрики. Сходимость в метрических пространствах. Полнота метрического пространства. Открытые, замкнутые и компактные множества. Теоремы Вейерштрасса и Кантора. Теорема о сжимающих отображениях. Теорема Бэра.

II. Общие сведения, связанные с нормированными пространствами Норма и нормированные пространства. Простейшие примеры (пространства с равномерной нормой).

Непрерывность нормы и линейных операций. Понятие полноты. Полунормы. Неравенства Юнга, Гельдера и Минковского. Определение пространств Lp. Полнота пространств Lp. Определение пространств lp(N).

Вложенность пространств Lp.

III. Гильбертово пространство Скалярное произведение, неравенство Коши - Буняковского. Определение гильбертова пространства.

Примеры. Ортогональная проекция. Ортогональные ряды. Ряды Фурье. Полные системы. Примеры классических ортогональных систем. Существование полной системы в сепарабельном гильбертовом пространстве.

IV. Линейные функционалы и операторы Линейные операторы. Непрерывные и ограниченные операторы. Норма оператора. Пространство линейных операторов и его полнота. Ядро и образ линейного оператора. Алгебраическая обратимость и обратимость оператора. Теорема Банаха об обратном операторе. Теорема о замкнутом графике. Линейные функционалы.

Описание линейных непрерывных функционалов в различных пространствах. Теорема Рисса о представлении функционалов в гильбертовом пространстве. Теорема Хана – Банаха и ее приложения. Понятие второго сопряженного пространства. Рефлексивные пространства. Рефлексивность гильбертовых пространств.

Продолжение непрерывных операторов с плотного множества. Пополнение линейных нормированных пространств. Сопряженный оператор. Самосопряженные, унитарные, нормальные операторы. Примеры.

Операторы проектирования. Интегральные операторы. Тест Шура. Примеры.

V. Плотность и полнота в нормированных пространствах Полные множества в Lp. Полнота характеристических функций. Полнота в Lp(Rn) гладких функций с компактным носителем. Теорема Стоуна - Вейерштрасса в вещественном и комплексном вариантах.

VI. Сходимость операторов и функционалов Понятие сильной сходимости операторов. Принцип равномерной ограниченности. Теорема Банаха Штейнгауза. Непрерывность в среднем функций из Lp(Rn). Теорема Римана – Лебега. Сильная аппроксимация тождественного оператора в разных функциональных пространствах. Суммирование рядов Фурье по Фейеру и по Абелю. Связь сильной и равномерной сходимости операторов. Понятие слабой и слабой * сходимости.

Слабая * компактность единичного шара в сопряженном пространстве. Примеры.

VII. Компактные операторы Понятие компактного и относительно компактного множеств. Теорема Хаусдорфа о сетях. Критерий относительной компактности в конечномерном пространстве. Критерий компактности единичного шара в банаховом пространстве. Теорема Арцела - Асколи. Компактные операторы и их свойства. Теорема Шаудера.

Операторы конечного ранга. Теорема о ранге сопряженного оператора. Критерий компактности оператора в гильбертовом пространстве. Лемма о почти перпендикуляре. Теория Фредгольма. Компактность интегральных операторов в пространстве непрерывных функций.

VIII. Элементы спектральной теории Понятие спектрального радиуса оператора. Ряд Неймана. Множество обратимых операторов. Определение и свойства резольвенты и спектра. Спектральный радиус нормального оператора и оператора Вольтерра.

Структура спектра оператора. Свойства спектра нормального, самосопряженного и унитарного операторов.

Спектр компактного оператора. Теорема Гильберта - Шмидта.

Б.3. 4 Теория вероятностей и математическая статистика

ТЕОРИЯ ВЕРОЯТНОСТЕЙ И МАТЕМАТИЧЕСКАЯ

СТАТИСТИКА

СОДЕРЖАНИЕ КУРСА

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

Колмогорова; свойства вероятностей; дискретное вероятностное пространство; классическое определение вероятностей. Условные вероятности, формула полной вероятности, независимость событий. Схема Бернулли, предельные теоремы для схемы Бернулли.

II. Математические основы теории вероятностей Случайные величины и векторы, функции распределения случайных величин и векторов, функции от случайных величин. Дискретные и непрерывные распределения, примеры случайных величин с дискретным и непрерывным распределениями. Независимые случайные величины. Формула свертки для распределений сумм независимых случайных величин. Математическое ожидание случайной величины и его свойства, дисперсия и ее свойства, вычисление математических ожиданий и дисперсий важнейших распределений. Моменты и их свойства, неравенства для моментов. Неравенство Чебышева. Ковариация и коэффициент корреляции.

Условные математические ожидания и их свойства. Дискретные цепи Маркова: определение, примеры, переходные вероятности, простейшие эргодические теоремы.

III. Предельные теоремы Характеристическая функция и ее свойства, формулы обращения для характеристических функций. Виды сходимости случайных величин: по вероятности, с вероятностью 1, по распределению, в среднем порядка r.

Центральная предельная теорема. Закон больших чисел. Лемма Бореля-Кантелли и закон нуля и единицы.

Усиленный закон больших чисел.

IV. Введение в теорию случайных процессов Определение случайного процесса, конечномерные распределения и траектории случайных процессов. Процессы с независимыми приращениями и стационарные процессы. Винеровский процесс и его свойства. Пуассоновский процесс, построение пуассоновского процесса по последовательности независимых экспоненциальных случайных величин. Цепи Маркова с непрерывным временем, уравнение КолмогороваЧепмэна. Процессы гибели и размножения. Дискретные ветвящиеся процессы. Структура и классификация систем массового обслуживания.

V. Cтатистические методы оценивания Случайная выборка. Выборочные характеристики. Вариационный ряд. Эмпирическая функция распределения. Точечное оценивание неизвестных параметров распределений: несмещенность, состоятельность оценок. Оценивание по методу моментов и методу максимального правдоподобия. Эффективные оценки.

Неравенство Рао-Крамера. Достаточные статистики.

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

VI. Проверка статистических гипотез Основные понятия, лемма Неймана-Пирсона, наиболее мощные критерии, проверка гипотез о параметрах нормального распределения, критерий "-квадрат" Б.3. 5 Дискретная математика

СОДЕРЖАНИЕ КУРСА

I. Некоторые понятия теории множеств Напоминание основных понятий. Определение прямого произведения множеств. Разбиения множеств и их свойства. Сравнение разбиений. Произведение разбиений.

II. Комбинаторика Векторы из нулей и единиц, различные их трактовки. Способы перебора и нумерации векторов из нулей и единиц.

Перестановки, размещения, сочетания, способы их перебора и нумерации. Бином Ньютона и треугольник Паскаля.

Числа Фибоначчи, их свойства.

III. Элементарная теория вероятностей Основные определения. Классическое определение вероятности. Условные вероятности. Формула полной вероятности. Формула Байеса и ее использование.

Случайные величины и распределения вероятностей. Математическое ожидание и дисперсия, их свойства.

Энтропия случайной схемы, определение и свойства. Аксиоматическое определение энтропии.

IV. Строки Строковые данные в различных разделах математики и приложениях. Основные операции над строками.

Лексикографическое сравнение строк. Типичные задачи, решаемые со строками. Методы поиска образца в строке. Классификация функций от строк: аддитивные, мультипликативные, марковские.

V. Механизмы хранения информации Массивы, списки, деревья.

Основные методы сортировки. Сортировка во внешней памяти.

Подравнивающиеся (АВЛ) деревья и Б-деревья.

Хеширование, ассоциативные массивы.

Приоритетные очереди, различные механизмы их реализации.

VI. Кодирование Методы сжатия информации.

Защита информации от помех.

Защита информации от несанкционированного доступа.

VII. Отношения Основные определения. Классификация отношений. Эквивалентность. Частичный порядок. Топологическая сортировка.

Использование многоместных отношений в реляционных базах данных.

VIII. Графы Основные определения: граф, частичный граф, подграф. Путь, простой путь, цепь, контур, цикл. Связность, бисвязность, сильная связность. Остовное дерево. Свойства деревьев.

Экстремальные задачи на графах: остовное дерево минимальной длины, дерево кратчайших путей и т.п.

Сетевое планирование и поиск критического пути.

Связь теории графов с линейной алгеброй. Матрица инциденций и ее свойства. Решение линейных систем с матрицей инциденций. Связь с методами решения разреженных линейных систем.

Паросочетания в двудольных графах. Теорема о максимальном паросочетании. Теорема Дилворта. Теорема Биркгофа-фон Неймана. Венгерский метод для задачи о назначениях.

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

Марковская цепь. Основные определения. Граф переходов. Классификация состояний марковской цепи.

Процесс принятия решений. Модель динамического программирования. Уравнение Беллмана.

Процессы в информатике.

X. Связь дискретного и непрерывного анализа Производящие функции.

Асимптотика.

Б.3.6 Математическая логика

СОДЕРЖАНИЕ КУРСА

История возникновения и развития математической логики в широком смысле этого слова.

II. Исчисление высказываний Понятие пропозициональной формулы. Понятие кванторной пропозициональной формулы. Равнозначность пропозициональных формул. Выразимость булевых функций через пропозициональную формулу. Секвенция и ее логическая и числовая интерпретация. Секвенциальное исчисление высказываний.

III. Исчисление предикатов Понятие терма. Атомарная формула. Формула исчисления предикатов. Секвенция и ее числовая интерпретация. Секвенциальное исчисление предикатов.

IV. Аксиоматические теории Исчисление предикатов с равенством (аксиомы равенства и согласованности с равенством).

Формальная арифметика. Аксиомы элементарной теории чисел (формальной арифметики). Первая теорема Геделя о неполноте арифметики. Вторая теорема Геделя о непротиворечивости арифметики. Гиперчисла.

Элементы нестандартного анализа.

Элементы аксиоматической теории множеств. Парадокс Рассела. Аксиомы теории множеств ЦермелоФренкеля.

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

Логики конечнозначных предикатов на основе неравенств. Смешанная логика Поста. Импликация Лукасевича. Нечеткая логика Заде.

V. Элементы теории алгоритмов Данные для алгоритмов. Программы на языке Паскаль как алгоритмы.

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

Различные варианты точного понятия алгоритма: нормальный алгоритм, машина Тьюринга, недетерминированная машина Тьюринга, альтернирующая машина Тьюринга, примитивно рекурсивные программы, элементарные по Кальмару функции.

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

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

VI. Элементы теории сложности алгоритмов Определение иерархии по времени и памяти детерминированных, недетерминированных и альтернирующих машин Тьюринга. Определение и примеры NP-полных и PSPACE-полных задач.

Б.3.7 Структуры и алгоритмы компьютерной обработки данных

СОДЕРЖАНИЕ КУРСА

I. Представление чисел Двоичное кодирование в позиционной системе счисления. Обратный и дополнительный код для отрицательных целых чисел. Арифметические операции над целыми в дополнительном коде. Представление целых произвольной длины и операции над ними. Представления вещественных с фиксированной и плавающей точкой. Арифметические операции сложения и умножения над вещественными. Потеря значащих цифр.

II. Массивы и структуры. Строки Размещение структурных значений. Выравнивание и упаковка. Порядок размещения элементов массива в памяти. Индексация. Массивы с постоянными границами. Массивы с динамическими границами. Косвенная адресация. Базовый адрес и смещение. Паспорт (дескриптор) массива. Массивы с изменяемыми размерами и/или размерностью. Строки с объявленным максимальным размером. Списковое представление строк.

Символьный пул для представления строк в языках обработки строк.

III. Представление процедур Структура стека вызовов процедур. Хранение в стеке параметров и локальных переменных. Структура фрейма процедуры. Связь фреймов в динамическую цепочку (цепочку вызовов) и статическую цепочку (контекст). Хранение и преобразование контекстов при процедурных переходах. Представление процедуры как хранимого объекта. Запоминание контекста.

IV. Представление объектов Поля и методы объектов. Наследование. Таблица виртуальных методов. Динамические свойства объектов.

Проблемы множественного наследования.

V. Представление списковых структур Стек и его представление в виде массива и списка. Стеки, растущие "навстречу" друг другу. Очереди и их реализация. Примеры применения стеков и очередей.

VI. Деревья, их использование и алгоритмы их обработки Представление регулярных деревьев в массиве. Ссылочные представления деревьев. Обходы деревьев.

Упорядоченные деревья: вставка и добавление элементов. Оптимальное и сбалансированное по высоте (АВЛ) дерево. Вставка и удаление элементов в АВЛ-дереве. 2-3-дерево и B-деревья: вставка и удаление элементов.

Применение B-деревьев для хранения индексов в базах данных.

Б.3.8. Архитектура вычислительных систем и компьютерных сетей

СОДЕРЖАНИЕ КУРСА

Микропрограммный уровень II. Архитектура традиционных компьютеров.

III. Способы ускорения традиционных архитектур: Конвейер команд, расслоенная память, регистры, кэш-память.

IV. Нестандартные архитектуры: векторная, матричная, VLIW и т. д.

RISC- и CISC-компьютеры: Исторически эти два направления развивались как противоположные, в настоящее время они практически неразличимы.

VI. Распределение памяти в трансляторах с АЯВУ: Некоторые сведения из техники трансляции, необходимые для понимания аппаратной реализации.

VII. Реализация вызовов в трансляторах с АЯВУ: Некоторые сведения из техники трансляции, необходимые для понимания аппаратной реализации.

VIII. Обзор архитектуры POWER PC IX. Обзор архитектуры Intel, X. Обзор архитектуры SUN SPARC XI. Особенности multimedia extensions (Intel MMX & SSE, PowerPC VMX) XII. Системная архитектура (процессоры, кэш, интегрированная периферия-chipset) XIII. Шинная архитектура (локальные, системные, периферийные шины, "двойная независимая" шинная архитектура) XIV. Архитектура HLL-компьютеров на примере УВК "САМСОН":

Б.3.9. Операционные системы и оболочки

СОДЕРЖАНИЕ КУРСА

I. Принципы построения операционных систем Операционная система. Определение. Поколения операционных систем. Функции операционных систем.

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

Распределенные операционные системы. Аппаратная поддержка распределенных операционных систем.

II. Вычислительный процесс и его реализация с помощью ОС Определение термина "процесс". Процессы и программы. Состояния процесса. Операции над процессами. Потоки (нити) управления. Сравнительный анализ нитей и процессов. Классы нитей. Реализация пользовательских нитей с помощью библиотеки функций.

III. Управление вычислительными процессами Синхронизация параллельных процессов. Проблема критических участков. Анализ подходов к решению проблемы. Алгорифм Деккера. Аппаратная поддержка взаимоисключений: запрещение прерываний, test&set.

Синхронизация памяти: membar. Программная реализация взаимоисключений: блокирование (spin lock).

Cемафоры: определение, назначение, реализация. Задача взаимодействия писателя и читателя и ее решение с помощью блокировок и семафоров. Мониторы: определение, назначение, реализация. Переменная условия.

Решение задачи взаимодействия писателей и читателей. Проблема тупиков. Необходимые условия возникновения тупиков. Алгорифм банкира. Модели для анализа свойств асинхронных процессов. Уровни планирования. Приоритеты. Алгорифмы планирования.

IV. Управление вводом-выводом, реальной памятью Иерархия памяти. Управление памятью. Привязка команд и данных к адресам: времена компиляции, загрузки, исполнения. Именующая функция. Редактор связей. Соглашения о связях. Функция памяти. Способы реализации отображения. Аппаратная поддержка. Управление файловой системой. Управление устройствами ввода/вывода.

V. Управление виртуальной памятью Стратегии размещения, подкачек, вытеснения.

VI. Стандартные сервисные программы Использование стандартных сервисных программ; профилактика устойчивой работы дисков.

VII. Машинно-зависимые свойства ОС Прерывания, планирование процессов, обслуживание ввода-вывода, управление реальной и виртуальной памятью.

VIII. Машинно-независимые свойства ОС Работа с файлами, управление заданиями, распределение ресурсов, защита.

IX. Распределенные системы Синхронизация, распределение процессов, распределенная разделяемая память. Проблемы синхронизации в распределенных системах. Логические часы. Алгорифм Лампорта. Физические часы. Алгорифм Беркли.

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

Организация распределения процессоров. Модели: рабочих станций и процессорного пула. Алгорифмы распределения процессоров и планирования в распределенных системах. Распределенная разделяемая память.

Системы с разделяемой памятью.

X. Способы построения ОС Типы архитектур операционных систем. Ядро операционной системы. Функции ядра. Микроядерные ОС.

Экзоядерные ОС.

XI. Обзор современных ОС и операционных оболочек Доминирование операционных систем Unix и Windows. Распределенная ОС Ameoba.

Операционная система Unix. История Unix. Версии Unix. Многонитевость в некоторых версиях Unix.

Семейства нитей POSIX и Microsoft. Состояния процесса в ОС Unix. Системные функции управления процессами. Взаимодействие между процессами в Unix. Сигналы. Классы сигналов. Работа с сигналами.

Принципы планирования процессов в Unix. Приоритеты. Редактор связей ld в Unix. Типы порождаемых модулей. Модели связывания.

XII. Управления памятью в Unix Свопинг и подкачка по запросу. Система управления вводом-выводом в Unix. Системные функции ввода/вывода. Файловая система в Unix. Оболочки Unix. Программное окружение Unix.

XIII. Сохранность и защита программных систем Безопасность информационных технологий. Три основные задачи по защите информационных технологий.

Иерархия классов безопасных систем. Криптология, криптография, криптоанализ.

XIV. Интерфейсы и основные стандарты в области системного программного обеспечения.

Б.3.10. Базы данных

СОДЕРЖАНИЕ КУРСА

Роль и место СУБД в прикладных системах. Основные функции СУБД. Взаимодействие СУБД с другими компонентами программного обеспечения. История развития СУБД.

II. Модели данных и языки запросов Неформальное определение модели данных и ранние модели данных. Значение высокоуровневых языков запросов. Реляционная модель данных: определение, основные операции реляционной алгебры, эквивалентность языков запросов. Теория нормализации. Пост-реляционные модели данных: объектные модели данных, объектно-реляционные модели. Пространственные, временные, многомерные данные.

Слабоструктурированная модель данных. Язык запросов SQL в реляционных и пост-реляционных системах.

Объектные и дедуктивные языки запросов. Языки запросов для слабоструктурированных данных.

III. Теория транзакций Определение транзакций и их роль в поддержке согласованности и защите от отказов. Критерии согласованности. Теория сериализуемости. Модель управления транзакциями: планировщики и протоколы.

Двухфазный протокол блокирования и его корректность. Обнаружение тупиков. Многоуровневое блокирование и недвухфазные протоколы блокирования. Неблокирующие протоколы управления транзакциями. Теория ведения журналов и восстановления после отказов. Распределенные системы: двухфазный протокол завершения. Раскопированные данные: протоколы голосования.

IV. Архитектуры СУБД и приложений Однопользовательские и многопользовательские архитектуры СУБД. Функции СУБД в архитектуре клиентсервер. Роль и функции СУБД в многоуровневых архитектурах с серверами приложений.

V. Методы реализации ядра СУБД Функции и состав ядра СУБД. Структуры хранения для различных типов и моделей данных. Методы индексирования. Алгоритмы выполнения алгебраических операций в реляционной и пост-реляционных системах. Методы оптимизации запросов. Управление оперативной памятью: буферизация. Методы ведения журналов, алгоритмы откатов транзакций и восстановления после отказов. Параллельные серверы баз данных.

Распределенные системы: выполнение запросов, репликация и фрагментация данных, особенности выполнения транзакций.

VI. Распределенные и неоднородные системы Роль неоднородных систем. Уровни неоднородности: архитектуры вычислительных систем, моделей данных, семантическая неоднородность. Интеграция неоднородных моделей данных. Устранение семантических неоднородностей. Неоднородные автономные системы. Методы поддержки согласованности в неоднородных системах. СУБД в распределенных объектных системах. Мониторы транзакций. Серверы приложений. Доступ к базам данных из Интернет.

VII. Моделирование и проектирование приложений Методологии проектирования прикладных систем, использующих базы данных и жизненный цикл баз данных. Проектирование баз данных с использованием модели “сущность-связь”. Объектные методологии проектирования приложений. Программные средства автоматизации проектирования. Выбор СУБД для реализации прикладной системы.

VIII. Разработка приложений Техника использования языка запросов SQL. Работа с базами данных в обычных языках программирования. Универсальные интерфейсы доступа к базам данных: ODBC, JDBC и другие. Методы создания высокоэффективных приложений.

IX. Администрирование баз данных Планирование емкости и мощности системы. Управление доступом к СУБД: пользователи и полномочия.

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

X. Физическое проектирование и настройка производительности Проектирование физической схемы базы данных. Выбор цели оптимизации системы. Анализ производительности и выявление узких мест. Настройка сервера СУБД. Анализ планов выполнения запросов и их настройка. Управление оптимизатором запросов.

Б.3.11. Технология разработки программного обеспечения

СОДЕРЖАНИЕ КУРСА

I. Понятие технологии программирования Особенности промышленного программирования, "программирование для себя" и "программирование для хозяина".

Жизненный цикл программы II. Постановка задачи, оценка осуществимости Как оценить сложность задачи? Реальность ее решения в заданные сроки при заданных финансовых ограничениях.

III. Планирование Сетевой график, диаграмма Гантта, треугольник – сроки, работы, ресурсы.

Управление Регулярные проверки соответствия графику, меры преодоления отставаний. "Добавлять людей в горящий коллектив – все равно, что заливать пожар керосином" IV. Тестирование, обеспечение качества Оценка качества – существенно более широкая задача, чем тестирование.

V. Оценка качества трансляторов как пример количественно обоснованной Методика Уичмана.

VI. Групповая разработка, управление версиями Единый репозиторий проекта. Системы SourceSafe, PVCS.

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

VII. Документирование ГОСТ ЕСПД и другие стандарты.

Сопровождение: Исправление ошибок, внесение дополнительной функциональности, повышение эффективности.

VIII. Управление качеством Стандарты ISO 9000, CMM, SPICE.

IX. Структурное проектирование Иерархическая декомпозиция, базовые структурные конструкции, неэквивалентность структурного проектирования и программирования без goto.

X. CASE-средства Примеры инструментальных технологических средств.

XI. Реинжиниринг программных систем Перевод устаревших программ на новые языки и платформы, возвратное проектирование – извлечение знаний из текста программы.

Б.3.12. Теория вычислительных процессов и структур

СОДЕРЖАНИЕ КУРСА

I. Теория схем программ Мотивация, историческая справка. Стандартные схемы: базис, операторы, граф.

Интерпретация схемы, программа. Исполнение программы: допустимые цепочки, значение программы.

Эквивалентность, тотальность, пустота, свобода. Корректные отношения эквивалентности.

Свободные интерпретации. Теоремы Лакхэма-Парка-Патерсона.

Двоичный двухголовочный автомат (ДДА): определение и свойства. Неразрешимость проблемы пустоты Моделирование ДДА стандартной схемой. Неразрешимость проблем пустоты и эквивалентности стандартных схем.

Частичная разрешимость проблемы тотальности.

Задача Поста и ее частичнаня разрешимость. Обратная задача Поста и ее неразрешимость.

Сведение проблемы свободы схемы к задаче пустоты системы Поста. Неразрешимость проблемы свободы.

Логико-термальная (ЛТ) эквивалентность стандартных схем: мотивация, определение. Корректность ЛТэквивалентности.

Разрешимость ЛТ-эквивалентности.

Полная система ЛТ-эквивалентных преобразований.

II. Семантическая теория программ Логическая спецификация программ.

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

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

Автоматизация верификации программ.

Доказательство корректности программ в проблемных областях.

Верификация недетерминированных и параллельных программ.

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

Языки, специализированные по области применения (управление, структуры данных, языки и трансляторы, базы данных и знаний, пакеты прикладных программы). Универсальные и расширяемые языки.

Денотационная, операционная и аксиоматическая семантики. Теория неподвижных точек. Семантика состояний. Абстрактные типы данных и сигнатурные графы.

Формальные методы спецификации программ. VDM (венский метод построения программ). Логикоалгебраические спецификации. Машины абстрактных состояний.

III. Модели вычислительных процессов Модел и вычи сли тель ных пр оц ес с ов : Модель графов распределения ресурсов. Сети Петри.

Вычислительные схемы.

Вз а им оде йс тви е пр оце с с ов, а си нх р онн ые пр оце сс ы: Синхронизация параллельных процессов.

Проблема критических участков. Анализ подходов к решению проблемы. Алгорифм Деккера. Программная реализация взаимоисключений: блокирование (spin lock).

Cемафоры и мониторы: определение, назначение, реализация.

Прот ок олы и и нт ерф ей сы : открытость разработки стандартов; уровневые протоколы; драйверы;

средства оконного интерфейса.

Функциональное программирование. Лямбда-исчисление и язык Лисп. Нормальные алгорифмы Маркова и язык Рефал. Комбинаторная логика и язык Миранда.

Логическое программирование. SLD-резолюция и язык Пролог.

IV. Сети Петри Прин ци пы п ос тр оени я: неформальное и формальное определение и способы представления сетей Петри и описание их подклассов.

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

Спос об ы реа лиз а ци и.

Обла ст и прим е н ени я: моделирование систем на основе сетей Петри и расширения сетей Петри.

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

государственный математико-механического Санкт-Петербургский Санкт-Петербургский Санкт-Петербургский Санкт-Петербургский Эксперты:

Санкт-Петербургский Институт Информатики ООО Санкт-Петербургский Директор “Центр разработок ЕМС” по разработке В.М. Нестеров