авторефераты диссертаций БЕСПЛАТНАЯ БИБЛИОТЕКА РОССИИ

КОНФЕРЕНЦИИ, КНИГИ, ПОСОБИЯ, НАУЧНЫЕ ИЗДАНИЯ

<< ГЛАВНАЯ
АГРОИНЖЕНЕРИЯ
АСТРОНОМИЯ
БЕЗОПАСНОСТЬ
БИОЛОГИЯ
ЗЕМЛЯ
ИНФОРМАТИКА
ИСКУССТВОВЕДЕНИЕ
ИСТОРИЯ
КУЛЬТУРОЛОГИЯ
МАШИНОСТРОЕНИЕ
МЕДИЦИНА
МЕТАЛЛУРГИЯ
МЕХАНИКА
ПЕДАГОГИКА
ПОЛИТИКА
ПРИБОРОСТРОЕНИЕ
ПРОДОВОЛЬСТВИЕ
ПСИХОЛОГИЯ
РАДИОТЕХНИКА
СЕЛЬСКОЕ ХОЗЯЙСТВО
СОЦИОЛОГИЯ
СТРОИТЕЛЬСТВО
ТЕХНИЧЕСКИЕ НАУКИ
ТРАНСПОРТ
ФАРМАЦЕВТИКА
ФИЗИКА
ФИЗИОЛОГИЯ
ФИЛОЛОГИЯ
ФИЛОСОФИЯ
ХИМИЯ
ЭКОНОМИКА
ЭЛЕКТРОТЕХНИКА
ЭНЕРГЕТИКА
ЮРИСПРУДЕНЦИЯ
ЯЗЫКОЗНАНИЕ
РАЗНОЕ
КОНТАКТЫ


Pages:     | 1 | 2 || 4 |

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

-- [ Страница 3 ] --

РАБОЧАЯ ПРОГРАММА ДИСЦИПЛИНЫ (МОДУЛЯ) стохастический аналиЗ Направление подготовки МАТЕМАТИКА И КОМПЬЮТЕРНЫЕ НАУКИ Квалификация (степень) выпускника бакалавр (бакалавр, магистр, дипломированный специалист) Форма обучения Очная (очная, очно-заочная и др.) г. – 200 г.

1. Цели освоения дисциплины Целями освоения дисциплины (модуля) "Стохастический анализ" являются: форми рование стохастической культуры студента, фундаментальная подготовка в области стохас тического анализа, овладение современным математическим аппаратом для дальнейшего ис пользования в приложениях.

2. Место дисциплины в структуре ООП ВПО Стохастический анализ входит в цикл профессиональных дисциплин в базовой части.

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

Освоение первой части стохастического анализа (теории вероятностей) необходимо для дальнейшего изучения математической статистики. Знание стохастического анализа мо жет существенно помочь в научно-исследовательской работе.

3. Компетенции обучающегося, формируемые в результате освоения дисципли ны (модуля): ОК-5, ОК-6, ОК-8, ОК-11, ПК-1, ПК-2, ПК-3, ПК-4, ПК-5, ПК-6, ПК-7, ПК-8, ПК-9, ПК-10, ПК-11, ПК-12, ПК-15, ПК-16, ПК-19, ПК-20, ПК-21, ПК-22, ПК-23, ПК-24, ПК 25, ПК-27, ПК-29.

В результате освоения дисциплины обучающийся должен:

1) Знать: основные понятия стохастического анализа, определения и свойства матема тических объектов в этой области, формулировки утверждений, методы их доказательства, возможные сферы их приложений, основы компьютерного моделирования стохастических объектов и явлений.

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

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

4. Структура и содержание дисциплины (модуля).

Общая трудоемкость дисциплины составляет 7-8 зачетных единиц.

Примерная программа дисциплины (модуля):

1 Понятие случайного события и его вероятности. Классическая вероятностная модель для случая равновозможных исходов. Приложения комбинаторики в теории вероятностей.

2 Геометрическая вероятность. Задача Бюффона*. Понятие о методах Монте-Карло.

3 Операции над событиями. Теорема сложения. Формула включения и исключения. Ак сиоматика Колмогорова. Пример Вители*. Свойства вероятностной меры*.

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

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

6 Предельные теоремы Муавра-Лапласа и Пуассона.

7 Случайная величина и ее распределение. Функция распределения. Дискретные и не прерывные распределения. Сингулярные распределения*. Теорема о разложении*. Плот ность распределения. Основные числовые характеристики случайных величин (математиче ское ожидание, дисперсия, моменты высших порядков, асимметрия*, эксцесс*).

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

9 Основные непрерывные распределения и их свойства (равномерное, показательное, нормальное, логнормальное*, Вейбулла*, Лапласа*, Парето*, Коши*).

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

11 Производящая функция, производящая функция моментов, характеристическая функ ция. Преобразование Лапласа-Стилтьеса*. Тауберовы теоремы*.

12 Многомерные случайные величины. Совместное и частные распределения. Совмест ная функция и плотность распределения. Независимость случайных величин. Меры зависи мости случайных величин и их свойства. Приложения к задаче оптимизации портфеля ак ций*. Многомерное нормальное распределение*.

13 Распределения суммы, разности, произведения и частного независимых случайных величин. Примеры.

14 Условные распределения и условные математические ожидания (одной случайной ве личины по другой). Функции регрессии. Линейная регрессия в случае многомерного нор мального распределения*.

15 Неравенства Маркова и Чебышва, их модификации. Различные виды сходимости случайных последовательностей, их взаимосвязь. Закон больших чисел. Лемма Бореля Кантелли*. Усиленный закон больших чисел*. Центральная предельная теорема. Теорема Берри-Эссеена*.

16 Генераторы псевдослучайных чисел и их свойства. Основные методы построения случайной величины с заданным распределением. Примеры моделирования случайных вели чин в MS Excel. Приложения в методах Монте-Карло. Моделирование многомерных случай ных величин. Приложение к моделированию финансового рынка*.

17 Общее определение случайного процесса. Конечномерные распределения. Теорема Колмогорова о существовании процесса с заданным семейством конечномерных распреде лений*. Условия согласованности. Функциональные характеристики случайных процессов и их преобразования. Примеры.

18 Стационарные случайные процессы (в широком и узком смысле). Автоковариацион ная и автокорреляционная функции, их свойства. Теорема Бохнера-Хинчина. Спектральная функция и спектральная плотность. Спектральное представление (дискретное время).

19 Процессы авторегрессии и скользящего среднего. Условие стационарности. Общая модель АРПСС (ARIMA)*. Моделирование процессов авторегрессии и скользящего средне го.

20 Мартингалы, субмартингалы, супермартингалы. Моменты остановки, их свойства.

Тождества Вальда*. Теоремы о сходимости*. Теорема Дуба о разложении. Мартингальные неравенства*. Функциональные преобразования мартингалов и субмартингалов.

21 Цепи Маркова с дискретным временем и конечным числом состояний. Классифика ция состояний. Предельное распределение. Цепи Маркова с бесконечным числом состоя ний*. Эргодичность и возвратность*. Моделирование цепей Маркова.

22 Случайные блуждания на целочисленной прямой и в пространстве. Возвратность. За дача о разорении для двух игроков*. Приложение мартингалов для вычисления числовых ха рактеристик*. Моделирование случайных блужданий.

23 Ветвящиеся процессы Гальтона-Ватсона. Вероятности вырождения и предельные распределения. Моделирование ветвящихся процессов.

24 Случайные процессы с непрерывным временем. Различные виды непрерывности и дифференцируемости, их критерии. Теорема Колмогорова о непрерывной модификации*.

Примеры.

25 Пуассоновский процесс и поток (на прямой). Эквивалентные определения. Сложный пуассоновский процесс. Моделирование простого и сложного пуассоновских процессов. Пу ассоновское точечное поле*.

26 Цепи Маркова с непрерывным временем. Прямое и обратное уравнения Колмогоро ва*. Критерии эргодичности*. Приложения в теории массового обслуживания. Моделирова ние простейших систем массового обслуживания.

27 Модель Крамера-Лундберга для динамики капитала страховой компании. Оценка ве роятности разорения. Моделирование процесса динамики капитала.

28 Броуновское движение. Винеровский процесс, его построение и свойства. Моделиро вание винеровского процесса. Модель Блэка-Шоулса для динамики цен акций*.

29 Общие гауссовские процессы. Условия существования. Свойства траекторий. Фрак тальное броуновское движение, свойства и приложения*. Моделирование гауссовских про цессов.

30 Стохастический интеграл. Стохастический дифференциал. Формула Ито.

31 Спектральное представление стационарного процесса (непрерывное время).

32 Стохастические дифференциальные уравнения. Сильные и слабые решения*. Уравне ние Ланжевена. Процесс Орнштейна-Уленбека, его моделирование.

5. Образовательные технологии: активные и интерактивные формы, компьютерная симуляция.

6. Оценочные средства для текущего контроля успеваемости, промежуточной ат тестации по итогам освоения дисциплины и учебно-методическое обеспечение само стоятельной работы студентов В течение семестра студенты решают задачи, указанные преподавателем, к каждому семинару. В каждом семестре проводятся по 2 контрольные работы (на семинарах) и по од ной самостоятельной работе (на компьютере, по индивидуальному домашнему заданию). За чет выставляется после решения всех задач контрольных работ и выполнения самостоятель ной работы.

4 семестр Контрольная работа № 1. Группа из 27 студентов пишет контрольную из 3 вариантов (по 9 человек в каж дом). Найти вероятность, что среди случайно выбранных 5 студентов есть писавшие каждый вариант.

2. Студент может добраться до факультета либо на автобусе, интервал движения ко торого составляет 7 минут, либо на троллейбусе, интервал движения которого составляет минут. Найти вероятность того, что студенту, пришедшему на остановку в случайный мо мент времени, придется ждать не более 3 минут. Предполагается, что автобус и троллейбус ходят независимо.

3. Из продукции птицефабрики 75% яиц стандартные, 20% большего объема и 5% двухжелтковых. С какой вероятностью среди 3 случайно выбранных яиц окажутся хотя бы одно большего объема и хотя бы одно двухжелтковое (вместе)?

4. К системному администратору обращаются за помощью пользователи. Среди них начинающих – 60%, опытных – 40%. Вероятность обращения начинающего пользователя – 85%, опытного – 15%. Найти вероятность, что очередной пользователь, обратившийся за по мощью, окажется начинающим.

5. Страховая фирма заключила 2500 договоров. Вероятность страхового случая по ка ждому в течение года составляет 2%. Найти вероятность того, что число таких случаев в те кущем году составит не более 60.

Контрольная работа № 1. В телеигре игроку задают вопросы. Если игрок правильно отвечает на вопрос, ему задают следующий;

если неправильно, то игрок выбывает из игры. Всего задается не более трех вопросов. Вероятность ответить на первый вопрос равна 0,9;

на второй – 0,3;

на третий – 0,1. Найти распределение числа правильных ответов;

математическое ожидание выигрыша, если за один правильный ответ платят 100 руб., за два – 400 руб. и за три – 1000 руб.

2. Вес арбуза имеет математическое ожидание 10 кг и среднее квадратическое откло нение 2 кг. Найти вероятность того, что в 1 тонне окажется не более 105 арбузов.

3. Совместное распределение двумерной случайной величины () задано таблицей:

-1 0 1 1 1 12 4 1 1 4 12 Найти закон распределения случайной величины + и вычислить cov(23,+2).

Найти условное распределение по.

4. Плотность распределения случайной величины имеет вид C ( x 1) 2, x [1,2], f ( x ) x [1,2].

0, Найти С, функцию распределения F(x), Р( 1), М, плотность распределения случай ной величины =ln(3+1).

5. Пара случайных величин и равномерно распределена в треугольнике с верши нами в точках (0;

0), (1;

1), (1;

–2). Найти плотности распределения и ;

функции регрессии по и по.

Самостоятельная работа 1. Построить алгоритм моделирования случайной величины с функцией распределе ния: а) F(x)=0,7x+0,2x2+0,1x3, 0x1;

б) F(x)=(1–e–3x)(1–e–x)2, x0. Провести моделирование 1000 независимых случайных величин, вычислить их среднее арифметическое и сравнить с теоретическим значением.

2. Методом Монте-Карло оценить площадь фигуры, ограниченной кривой x 3+y3– 3xy=0 в квадрате [0, 2]2. Провести моделирование 1000 точек и построить график. Результат сравнить с теоретическим значением.

3. Построить алгоритм моделирования двумерной нормальной случайной величины с вектором средних a=(-1,5;

2) и матрицей ковариаций 0,64 0, В= 0,48 0,25.

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

6 семестр Контрольная работа № 1. Рассмотреть процесс авторегрессии и скользящего среднего, заданный уравнением n 0,3n 1 0,4n 2 n 0,7 n 1, где n, n1, независимы и имеют стандартное нормальное распределение. Проверить условие стационарности. Найти спектральную плотность.

2. Пусть Sn 1... n, где k, k0, независимы и принимают значения –1, 0 и + равновероятно. Доказать, что X n Sn 3Sn – субмартингал, построить его разложение Дуба.

4 3. Рассмотреть ветвящийся процесс Zn с распределением числа потомков, заданным вероятностями: p0=0,3;

p1=0,2;

p2=0,4;

p3=0,1. Найти среднее число потомков, вероятность вырождения и дисперсию предельного распределения.

4. Торговец из города Олино ездит продавать товар в города Анино и Ванино. Выехав из Олино, он направляется в Анино с вероятностью 40%, в Ванино – с вероятностью 60%.

Посетив Анино или Ванино, торговец возвращается в Олино с вероятностью 80% либо едет в другой из двух городов с вероятностью 20%. Найти стационарное распределение вероятно стей застать предпринимателя в каждом из городов.

Контрольная работа № 1. Для некоторого пуассоновского потока вероятность того, что на отрезке [0, 2] име ются 3 точки, вдвое больше вероятности того, что на отрезке [3, 5] имеются 5 точек. Найти вероятность того, что на отрезке [0, 3] имеется 4 точки.

2. Рассмотреть интеграл w(t ) t dt, где w(t) – винеровский процесс. Доказать сходимость интеграла почти наверное. Най ти его дисперсию.

3. Рассмотреть систему массового обслуживания с очередью, двумя приборами с ин тенсивностью обслуживания =3 и пуассоновским входным потоком интенсивности =5.

Найти вероятность того, что приборы свободны, и среднюю длину очереди в стационарном режиме.

4. Показать, что функция R(t ) e|t | (1 | t |) является автоковариационной функцией некоторого стационарного гауссовского случайного процесса. Найти спектральную плот ность. Проверить, является ли процесс дифференцируемым в среднем квадратическом и сколько раз.

Самостоятельная работа 1. Провести моделирование процесса авторегрессии и скользящего среднего, заданно го уравнением n 0,9n 1 0,2n 2 n 0,3 n 1, где n, n1, независимы и имеют стандарт ное нормальное распределение. Построить графики трех траекторий процесса за период в 100 единиц времени.

2. Построить алгоритм моделирования ветвящегося процесса с распределением числа потомков, заданным вероятностями: p0=0,3;

p1=0,2;

p2=0,4;

p3=0,1. Построить графики траекторий процесса за период в 10 единиц времени.

3. Построить алгоритм моделирования цепи Маркова с дискретным временем, тремя состояниями и матрицей переходных вероятностей 0,7 0,2 0, 0,3 0,6 0,1, 0,1 0,7 0, в предположении, что начальное распределение стационарно. Провести моделирова ние 100 траекторий цепи за период в 100 единиц времени. Вычислить средние доли времени пребывания в каждом состоянии и сравнить их со стационарными вероятностями.

4. Построить алгоритм моделирования системы массового обслуживания с очередью, двумя приборами с интенсивностью обслуживания =3 и пуассоновским входным потоком интенсивности =5. Провести моделирование системы за период времени в 100 единиц в предположении, что сначала она пуста. Вычислить среднюю длину очереди (по времени), сравнить ее с теоретическим значением.

5. Провести моделирование винеровского процесса на отрезке [0, 1] с шагом h=0,01.

Построить 100 траекторий. Вычислить долю тех из них, которые превышают уровень A=1, и сравнить ее с теоретической вероятностью. Построить графики двух траекторий: где превы шение уровня происходит и где не происходит.

7. Учебно-методическое и информационное обеспечение дисциплины (модуля) а) основная литература:

1. Ширяев А.Н. Вероятность. Т. 1, 2. М.: МЦНМО, 2004.

2. Ширяев А.Н. Задачи по теории вероятностей. М.: МЦНМО, 2004.

3. Булинский А.В., Ширяев А.Н. Теория случайных процессов. М.: Физматлит, 2005.

4. Севастьянов Б.А. Курс теории вероятностей и математической статистики. М.: Наука, 1982.

5. Зубков А.М., Севастьянов Б.А., Чистяков В.П. Сборник задач по теории вероятностей. М.:

Наука, 1989.

6. Мешалкин Л.Д. Сборник задач по теории вероятностей. М.: Наука. 1963.

7. Прохоров А. В., Ушаков В.Г., Ушаков Н.Г. Задачи по теории вероятностей. М.: Наука, 1986.

8. Миллер Б.М., Панков А.Р. Случайные процессы в примерах и задачах. М.: Изд-во МАИ, 2001.

9. Михайлов Г.А., Войтишек А.В. Численное статистическое моделирование. Методы Мон те-Карло. М.: Академия, 2006.

б) дополнительная литература:

1. Виленкин Н.Я., Виленкин А.Н., Виленкин П.А. Комбинаторика. М.: МЦНМО, 2006.

2. Тутубалин В.Н. Теория вероятностей. М.: Академия, 2008.

3. Ширяев А.Н. Основы стохастической финансовой математики. Т.1. М.: Фазис, 1998.

4. Феллер В. Введение в теорию вероятностей и ее приложения. Т. 1, 2. М.: Мир, 1984.

5. Секей Г. Парадоксы в теории вероятностей и математической статистике. М.: Институт компьютерных исследований, 2003.

6. Харрис Т. Теория ветвящихся случайных процессов. М.: Мир, 1966.

7. Гнеденко Б.В., Коваленко И.Н. Введение в теорию массового обслуживания. М.: Наука, 1987.

8. Соколов Г.А., Чистякова Н.А. Теория вероятностей. Управляемые цепи Маркова в эконо мике. М.: Физматлит, 2005.

9. Гихман И.И., Скороход А.В. Введение в теорию случайных процессов. М.: Наука, 1972.

10. Оксендаль Б. Стохастические дифференциальные уравнения. Введение в теорию и при ложения. М.: Мир, 2003.

11. Кузнецов Д.Ф. Численное моделирование стохастических дифференциальных уравнений и стохастических интегралов. СПб.: Наука, 1999.

12. Соболь И.М. Численные методы Монте-Карло. М.: Наука, 1973.

13. Калугина О.Б., Люцарев В.С. Работа с электронными таблицами. Microsoft Office Excel 2003. М.: Интернет-университет информационных технологий, 2006.

14. Эйткен П. Интенсивный курс программирования в Excel за выходные. М.: Вильямс, 2006.

15. Бокс Дж., Дженкинс Г. Анализ временных рядов. Прогноз и управление. Т. 1. М.: Мир, 1974.

в) программное обеспечение и Интернет-ресурсы: MS Excel.

8. Материально-техническое обеспечение дисциплины (модуля) Учебные аудитории для проведения лекционных и семинарских занятий, доступ сту дентов к компьютеру с Microsoft Office.

Автор: доцент кафедры теории вероятностей А.В.Лебедев Рецензенты: проф. кафедры теории вероятностей А.В.Булинский, проф. кафедры тео рии вероятностей В.В.Сенатов.

РАБОЧАЯ ПРОГРАММА ДИСЦИПЛИНЫ (МОДУЛЯ) ДИСКРЕТНАЯ МАТЕМАТИКА, математическая логика и их приложения в информатике и компьютерных науках Направление подготовки МАТЕМАТИКА И КОМПЬЮТЕРНЫЕ НАУКИ Квалификация (степень) выпускника бакалавр (бакалавр, магистр, дипломированный специалист) Форма обучения Очная (очная, очно-заочная и др.) г. – 200 г.

1. Цели освоения дисциплины.

Целями освоения дисциплины (модуля) "Дискретная математика, математическая ло гика и их приложения в информатике и компьютерных науках" являются:

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

2. Место дисциплины в структуре ООП ВПО.

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

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

3. Компетенции обучающегося, формируемые в результате освоения дисципли ны (модуля): ОК-6, ОК-10, ОК-11, ОК-14, ПК-1, ПК-2, ПК-3, ПК-4, ПК-5, ПК-6, ПК-7, ПК-8, ПК-9, ПК-10, ПК-11, ПК-12, ПК-15, ПК-16, ПК-17, ПК-19, ПК-20, ПК-21, ПК-23, ПК-24, ПК 27, ПК-29.

В результате освоения дисциплины обучающийся должен:

1. Знать: основные понятия дискретной математики и математической логики, опре деления и свойства математических объектов, используемых в этих областях, формулировки утверждений, методы их доказательства, возможные сферы их приложений, основы построе ния компьютерных дискретно-математических моделей.

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

3. Владеть: математическим аппаратом дискретной математики и математической ло гики, методами доказательства утверждений в этих областях, навыками алгоритмизации ос новных задач.

4. Структура и содержание дисциплины (модуля) "Дискретная математика, мате матическая логика и их приложения в информатике и компьютерных науках".

Общая трудоемкость дисциплины составляет 7-8 зачетных единиц.

Примерная программа дисциплины (модуля):

1 Функции алгебры логики. Существенные и несущественные переменные. Формулы.

Представление функций формулами. Операция суперпозиции. Операция введения несущест венной переменной. Замыкание множества функций. Замкнутые классы. Равенство функций.

Эквивалентность формул. Элементарные функции и их свойства. Совершенная дизъюнктив ная нормальная форма. Совершенная конъюнктивная нормальная форма.

2 Полные системы функций. Достаточное условие полноты. Примеры полных систем.

Полиномы Жегалкина. Представление булевых функций полиномами. Линейные функции и их свойства. Функции, сохраняющие константы. Самодвойственные функции и их свойства.

Монотонные функции и их свойства.

3 Теорема Поста о полноте системы булевых функций. Возможность выделить из каж дой полной системы полную подсистему, состоящую не более чем из 4-х функций. Базисы замкнутых классов. Примеры базисов в P2. Предполные классы. Свойства предполных клас сов в P2. Теорема Поста о конечной порожденности замкнутых классов булевых функций (без доказательства).

4 Функции k-значной логики. Основные понятия. Элементарные функции и их свойст ва. Полные системы. Полнота системы {0, …, k-1, I0, …, Ik-1, max (x,y), min(x, y)}.

Полнота систем {max(x,y), x+1} и {max(x,y)+1}. Алгоритм распознавания полноты ко нечных систем функций. Классы сохранения множеств функций и их свойства. Теорема Куз нецова (о функциональной полноте). Алгоритм построения предполных классов в Pk (**).

5 Особенности множества функций k-значной логики, k 3. Теорема о полноте системы {0,1, …, k-1, x+y, xy} в Pk. Представление функций из Pk полиномами. Пример замкну того класса в P3, не имеющего базиса. Пример замкнутого класса в P3, имеющего счетный базис. Мощность семейства замкнутых классов в Pk.

6 Графы. Основные понятия. Способы представления графов. Реализация графов в трехмерном пространстве. Формула Эйлера для плоских графов. Графы правильных много гранников (*). Теорема Понтрягина-Куратовского (без доказательства). Перечисление графов на нумерованных вершинах. Верхняя оценка для числа неизоморфных графов с q ребрами.

Ориентированные графы. Лемма о нумерации вершин в конечном ориентированном графе.

7 Схемы из функциональных элементов. Контактные схемы. Основные понятия. Реали зация функций схемами. Простейшие методы синтеза. Метод каскадов. Верхняя оценка сложности схем, построенных по методу каскадов. Реализация симметрических функций.

Двоичный сумматор. Схема Карацубы для умножения чисел (*). Алгоритм Тоома для умно жения чисел (**).

8 Функция Шеннона. Верхняя оценка для функции Шеннона. Лемма Шеннона. Порядок роста функции Шеннона. Асимптотически наилучший метод синтеза схем из функциональ ных элементов в базисе {\/, &, –} (**). Теорема Лупанова (**). Минимальные схемы и их свойства;

лемма о верхней оценке числа минимальных схем (**). Асимптотически точная формула для функции Шеннона (**).

9 Детерминированные функции, ограниченно-детерминированные функции (о. д. функции). Способы задания о. д.-функций. Конечные автоматы. Способы задания ав томатов. Автоматные функции. Преобразование периодических последовательностей авто матными функциями. Примеры неавтоматных функций. Отсутствие конечных полных сис тем автоматных функций в случае схем без обратных связей (**).

10 Схемы из функциональных элементов и элементов задержки (схемы с обратными свя зями). Реализация функций схемами. Реализуемость автоматных функций схемами из функ циональных элементов и элементов задержки. Эксперименты с автоматами. Эквивалентность состояний.

Теорема Мура об эквивалентных состояниях автомата. Эквивалентность автоматов (*).

Теорема об эквивалентности состояний автоматов (*). Сокращенный автомат (*). Алгоритм построения сокращенного автомата (**).

11 Высказывания и операции над ними. Аксиомы классического исчисления высказыва ний. Схемы аксиом. Правила вывода. Вывод. Выводимые формулы. Вывод из системы гипо тез. Простые свойства выводимости. Примеры вывода. Вывод формулы A A. Теорема о дедукции.

12 Тождественная истинность выводимых формул. Непротиворечивость классического исчисления высказываний. Теорема о полноте. Независимость схем аксиом исчисления вы сказываний (*). Теорема о независимости схем аксиом исчисления высказываний (**).

13 Понятие предиката. Примеры. Логические операции над предикатами;

кванторы. Тео ретико-множественный смысл операций над предикатами. Условия полноты системы преди катов на конечном множестве. Формулы;

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

14 Истинность формул в модели, на множестве;

тождественно истинные формулы. Зада ча установления тождественной истинности формул, содержащих только одноместные пре дикаты. Гомоморфизм моделей (*). Существование модели гомоморфной заданной (**). Не обходимые и достаточные условия тождественной истинности формул (**). Алгоритм про верки тождественной истинности формул (содержащих только одноместные предикаты) (**).

15 Аксиомы классического исчисления предикатов. Правила вывода. Выводимые фор мулы. Примеры вывода. Специальный вывод из системы гипотез, теорема о дедукции (ос лабленный вариант) (*). Тождественная истинность выводимых формул. Непротиворечи вость классического исчисления предикатов. Теорема Гделя о полноте (без доказательства).

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

17 Частичные числовые функции. Простейшие функции. Операции суперпозиции и при митивной рекурсии. Примитивно рекурсивные функции. Операция минимизации. Частично рекурсивные функции, общерекурсивные функции. Тезис Чрча. Теорема о совпадении клас са частично рекурсивных функций и класса частичных числовых функций, вычислимых по Тьюрингу (без доказательства). Рекурсивные множества, разрешимые предикаты, рекурсив но перечислимые множества, частично разрешимые предикаты (*). Теорема Райса (**). Нор мальные алгорифмы Маркова (*). Принцип нормализации (*).

18 Выборки. Перестановки, сочетания, перестановки с повторениями, сочетания с повто рениями. Биномиальные коэффициенты. Свойства биномиальных коэффициентов, биноми альная теорема. Полиномиальные коэффициенты, полиномиальная теорема. Числа Стирлин га 1-го и 2-го рода;

свойства чисел Стирлинга;

обращение Стирлинга (*). Числа Белла (*).

19 Формулы обращения. Метод включений и исключений. Оценки для числа элементов, не обладающих ни одним из n свойств. Формула для числа элементов, обладающих в точ ности m свойствами, 0 m n. Неравенства Бонферрони (*). Арифметическая функция М биуса. Формула обращения Мбиуса. Перечисление p-ичных циклических последовательно стей длины n. Функция Эйлера (n), вычисление функции (n). Формула Гаусса (n = (d), суммирование по всем d | n) (**).

20 Формальные степенные ряды, операции над рядами. Кольцо формальных степенных рядов и его свойства. Формальная производная. Производящие функции. Примеры приме нения метода производящих функций для решения комбинаторных задач. Линейные ре куррентные соотношения с постоянными коэффициентами. Теорема о решении линейных рекуррентных соотношений. Числа Фибоначчи.

21 Элементы теории графов. Эйлеровы циклы. Теорема Эйлера. Теорема Эйлера для ориентированных графов. Последовательности де Брейна (**). Алгоритм построения Эйле рова цикла специального вида ("обход выставки").

22 Деревья и их свойства. Оценка числа неизоморфных корневых деревьев с q ребра ми. Теорема Кэли о числе деревьев на нумерованных вершинах. Алгоритм нахождения ми нимального остовного дерева.

23 Потоки в сетях. Максимальный поток. Минимальный разрез. Лемма о существовании максимального потока (*). Теорема Форда-Фалкерсона о максимальном потоке и минималь ном разрезе. Алгоритм нахождения максимального потока. Теорема о целочисленности.

24 Двудольные графы. Паросочетания в двудольных графах. Теорема Холла о паросоче таниях в двудольном графе. Рассекающие множества. Теорема Книга–Эгервари о рассе кающих множествах в двудольном графе. Частично упорядоченные множества (*). Теорема Дилуорса о представлении частично упорядоченных множеств (**). Разбиение Анселя мно жества всех двоичных наборов длины n на непересекающиеся цепи (**).

25 Побуквенное (алфавитное) кодирование. Разделимые коды. Неравенство Крафта Макмиллана. Условие существования разделимого p-ичного кода с заданным набором длин кодовых слов. Критерий взаимной однозначности алфавитного кодирования. Алгоритм рас познавания однозначности декодирования в терминах теории графов (**). Полные коды, критерий полноты для разделимых кодов (*). Построение полного (двоичного) кода по за данному префиксному коду (*).

26 Оптимальные коды. Свойства оптимальных p-ичных кодов. Верхняя и нижняя оценки стоимости оптимального кода. Методы построения оптимальных кодов. Метод Шеннона.

Теорема Шеннона. Свойства двоичных оптимальных кодов. Полнота префиксного опти мального двоичного кода (*). Теорема редукции. Алгоритм Хаффмена построения оптималь ного двоичного кода.

27 Коды, исправляющие ошибки над полем GF(p). Расстояние Хэмминга. Граница сфе рической упаковки (граница Хэмминга). Метод построения кода, исправляющего t ошибок.

Верхняя и нижняя оценки мощности максимального кода. Совершенные коды. Примеры со вершенных кодов.

28 Линейные коды над полем GF(p). Проверочные и порождающие матрицы линейных кодов. Двойственные коды. Параметры линейных кодов. Необходимые и достаточные усло вия существования линейных кодов с заданным минимальным расстоянием. Граница Сингл тона. Граница Варшамова–Гилберта (**). Декодирование линейных кодов. Смежные классы, лидеры смежных классов, синдром, стандартное расположение. Алгоритм декодирования по максимуму правдоподобия.

29 Коды Хэмминга, параметры кодов Хэмминга. Алгоритм декодирования кодов Хэм минга. Обобщенные коды Хэмминга, параметры обобщенных кодов Хэмминга (*). Алгоритм декодирования обобщенных кодов Хэмминга (*).

30 Языки. Операции над языками. Регулярные языки. Диаграммы. Представление языков диаграммами. Теорема о совпадении класса регулярных языков с классом языков, предста вимых диаграммами.

31 Представимые языки. Теорема Клини. Замкнутость семейства регулярных языков от носительно теоретико-множест-венных операций. Равенство регулярных языков. Примеры нерегулярных языков. Языки в однобуквенном алфавите (*). Периодические множества (*).

Необходимые и достаточные условия регулярности языков в однобуквенном алфавите (*).

32 Порождающие грамматики. Вывод слов. Порождение языков грамматиками. Эквива лентность грамматик. Контекстно-свободные грамматики;

контекстно-свободные языки. Ли нейные грамматики;

линейные языки. Праволинейные (леволинейные) грамматики;

право линейные (лнволинейные) языки. Теорема о праволинейных языках (*).

33 Дискретные экстремальные задачи в форме распознавания. Классы P и NP. Полино миальные сведения. NP-полные задачи. Примеры NP-полных задач. Теорема Кука (**).

34 Подходы к решению NP-полных задач. Приближенные методы решения дискретных экстремальных задач. Задача коммивояжера. Приближенный алгоритм для задачи комми вояжера с неравенством треугольника. Метод ветвей и границ;

метод ветвей и границ для задачи коммивояжера (**).

Примечания:

Символом «*» отмечены разделы дисциплины, которые могут быть прочитаны или выпущены по усмотрению лектора (и читаются в университетах с высоким рейтингом).

Символом «**» отмечены разделы дисциплины, которые читаются в университетах с высоким рейтингом.

5. Образовательные технологии: активные и интерактивные формы проведения за нятий.

6. Оценочные средства для текущего контроля успеваемости, промежуточной ат тестации по итогам освоения дисциплины и учебно-методическое обеспечение само стоятельной работы студентов В течение семестра студенты решают задачи, указанные преподавателем, к каждому семинару. В каждом семестре проводятся по 2 контрольные работы (на семинарах).

2-й семестр Контрольная работа № 1. Найти все полные подсистемы системы { f1, f 2, f 3, f 4, f 5 } булевых функций, где f1 xyz xyz yxz xzy, f 2 x( y zv ) xy( z v), f 3 ( x y)( y z )(z x) 1, f 4 x ( y z ) yxz, f 5 1.

2. Найти число функций f ( x, y, z ) из множества (T0 S ) \ L, существенно завися щих от всех переменных.

3. При каких натуральных k и m система {min( x, y), x m(mod k )} полна в Pk ?

4. Пусть f ( x1, x2, x3, x4, x5 ) – функция алгебры логики, такая, что равенство f (1, 2, 3, 4, 5 ) 1 выполняется тогда и только тогда, когда число r единиц в наборе (1, 2, 3, 4, 5 ) удовлетворяет неравенствам 2 r 3.

Построить методом каскадов контактную схему, реализующую функцию f.

5. Найти все булевы функции f ( x1, x2 ), такие, что а) L( f ) L(1);

б) L( f ) L(2).

(Здесь L( f ) – сложность функции f, а L(1) и L(2) – функции Шеннона при реализации схемами из функциональных элементов булевых функций от одной и от двух переменных соответственно).

Контрольная работа № 1. Построить диаграмму переходов, канонические уравнения и схему из функциональ ных элементов и элементов единичной задержки для функции f ( x(1) x(2)...x(t )...) y(1) y(2)...y(t )..., преобразующей бесконечные двоичные последовательности в бесконечные двоичные последовательности следующим образом: y(t ) 1 тогда и только тогда, когда слово x(1) x(2)...x(t ) содержит по крайней мере 4 единицы.

2. Пусть C исчисление высказываний со следующими схемами аксиом (Я. Лукасеви ча):

( A1 ) A ( B A), ( A ( B C )) (( A B) ( A C )), ( A2 ) ( A B ) ( B A) ( A3 ) и (единственным) правилом вывода modus ponens. Построить в исчислении C (без использования теоремы о дедукции) вывод формулы B ( B A).

3. Формулы A1 и A2 называются эквивалентными, если формулы A1 A2 и A2 A являются теоремами (выводимы в исчислении C ). Пусть B(A) формула над {,}, A подформула формулы B. Доказать, что для любых двух эквивалент ных формул A1 и A2 над {,} формулы B( A1 ) B( A2 ) и B( A2 ) B( A1 ) являются теоремами, где B( A1 ) и B( A2 ) формулы, полученные из B(A) заменой формулы A на A1 и A2 соответственно (имеется ввиду фиксированное вхождение подформулы в формулу).

A A, A A, 4. Можно ли в исчислении со схемами аксиом ( A2 ), ( A B) ( B A ) и правилом вывода modus ponens вывести формулу (A (A B)?

5. Построить формулу логики предикатов, которая является истинной на множествах, имеющих ровно 2 элемента, и не являющейся истинной на одноэлементных множест ва, а также на множествах из трх и более элементов.

6. Пусть A {a0, a1,...ak }, a0 0. Построить машину Тьюринга, которая утраивает слова в алфавите A и помещает между экземплярами слов символ A :

ai ai...ai ai ai...ai ai ai...ai ai ai...ai, 1 2 m 1 2 m 1 2 m 1 2 m где ai1, ai2,...,aim 0, m 1.

7-й семестр Контрольная работа № 1. Найти число различных слов, которые можно получить перестановкой букв из слова БАРБАРАБРА, и которые при этом не содержат подслов вида «ААА».

2. Найти число булевых функций f ( x, y, z, v) T0 T1, у которых число m сущест венных переменных удовлетворяет неравенствам 2m (где T0 и T1 множества всех булевых функций, сохраняющих константы 0 и 1 соот ветственно).

3. Найти число слов из нулей и единиц длины 30, которые не содержат подслов вида «00» и, кроме того, не содержат единичных массивов, состоящих из чтного числа единиц.

(Здесь единичный массив – подслово, состоящее только из единиц и ограниченное с каждой из сторон либо нулем, либо концом или началом исходного слова.) 4. Пусть G конечный граф без петель и кратных рбер, имеющий p вершин, q р бер и k компонент связности. Доказать, что p k q ( p k )( p k 1) / 2.

5. Пусть A матрица, состоящая из нулей и единиц. Доказать, что максимальное число единиц, попарно не лежащих на одной линии, равно минимальному числу линий, ко торые содержат все единицы матрицы A.

(Здесь линия – строка или столбец матрицы A ).

6. Из какого числа вершин может состоять центр конечного дерева?

(Центром конечного графа G (V, E ) называется множество всех вершин v V, таких, что выполняется равенство e(v) min e(u), где минимум берется по всем вершинам u из множества V, e(u) max d ( w, u) (максимум берется по всем wV ), а d ( w, u ) расстояние между вершинами u и w. ) Контрольная работа № 1. Пусть B {0,1}, V1 и V2 линейные двоичные [n, k1, d1 ] – и [n, k1, d 2 ] – коды соот ветственно, а V {v B n | v (u1, u1 u2 ), u1 V1, u2 V2 }.

Найти параметры кода V.

2. Пусть B {0,1} Говорят, что код V {v1,...vm } B обнаруживает t ошибок, если n B n, которое можно получить из vi, 1 i m, в результате не для любого слова более t ошибок выполняется условие B \ {vi }. Верно ли, что из всякого непус n того подмножества C B можно получить код, обнаруживающий одну ошибку, n удалив из C не более половины вершин?

3. Пусть G ({0,1},{, x}, P, ), где P { 00, 1x, x 0 x, x 11} Представить язык L(G ) (порожденный грамматикой G ) в виде выражения над множеством операций {,,}.

4. Пусть V ({0,1},{q0, q1}, G, q0,{q1}) конечный автомат с каноническими урав нениями следующего вида:

q(t 1) q(t ) x(t ), q(1) q0.

Построить порождающую грамматику G, такую, что L(G) T (V ) (где T (V ) язык, представимый автоматом V ).

5. Пусть E { n, где n – натуральное}. Является ли множество E праволинейным языком?

7. Учебно-методическое и информационное обеспечение дисциплины (модуля) а) основная литература:

1. Конспект лекций О. Б. Лупанова по курсу «Введение в математическую логику» / Отв.

ред. А. Б. Угольников. – М.: Изд-во ЦПИ при механико-математическом факультете МГУ им. М.В. Ломоносова, 2007. – 192 c.

2. Яблонский С. В. Введение в дискретную математику. – М.: Наука, 1986. – 384 c.

3. Лавров И. А. Математическая логика. – М.: Издательский центр «Академия», 2006. – 240 с.

4. Лупанов О. Б. Асимптотические оценки сложности управляющих систем. – М.: Изд-во Моск. ун-та, 1984. – 138 c.

5. Яблонский С. В. Элементы математической кибернетики. – М.: Высшая школа, 2007. – 188 c.

Редькин Н. П. Дискретная математика. – М.: Изд-во ЦПИ при механико 6.

математическом факультете МГУ им. М. В. Ломоносова, 2007. – 174 c.

Левенштейн В. И. Элементы теории кодирования. – В. сб. Дискретная математика и ма 7.

тематическая кибернетика. Т. 1. / Под общей редакцией С. В. Яблонского и О. Б. Лупа нова. – М.: Наука, 1974. – С. 207-305.

Гаврилов Г. П., Сапоженко А. А. Задачи и упражнения по дискретной математике. –М.:

8.

Физматлит, 2004. – 424 c.

Лавров И. А., Максимова Л. Л. Задачи по теории множеств, математической логике и 9.

теории алгоритмов. – М.: Наука, 1975. – 240 c.

б) дополнительная литература (с условной разбивкой по разделам):

Функции алгебры логики 10. Яблонский С. В. Введение в теорию функций k-значной логики. – В. сб. Дискретная ма тематика и математическая кибернетика. Т. 1. / Под общей редакцией С. В. Яблонского и О. Б. Лупанова. – М.: Наука, 1974. – С. 9-66.

11. Яблонский С. В., Гаврилов Г. П., Кудрявцев В. Б. Функции алгебры логики и классы Поста.

– М.: Наука, 1966. – 120 с.

12. Угольников А. Б. Классы Поста. – М.: Изд.-во ЦПИ при механико-математическом фа культете МГУ им. М. В. Ломоносова, 2008. – 64 с.

Функции k-значной логики 13. Яблонский С. В. Функциональные построения в k-значной логике // Труды матем. ин-та АН СССР, 1958. Т. 51. – С. 5–142.

14. Яблонский С. В., Гаврилов Г. П., Набебин А. А. Предполные классы в многозначных логиках. – М.: Изд-во МЭИ, 1987. – 142 с.

15. Lau D. Function Algebras on Finite Sets. – Berlin, Heidelberg: Springer, 2006. – 668 p.

16. Pschel R., Kaluznin L. A. Funktionen und Relationenalgebren. – Berlin. 1979. – 260 p.

Синтез и сложность управляющих систем 17. Лупанов О. Б. О синтезе некоторых классов управляющих систем. – В кн.: Проблемы ки бернетики. Вып. 10. – М.: Наука, 1963. – С. 63–97.

18. Нигматулин Р. Г. Сложность булевых функций. – М.: Наука, 1991. – 240 с.

19. Сэвидж Дж. Сложность вычислений. – М.: Факториал, 1998. – 368 с.

Исчисление высказываний, логика и исчисление предикатов, алгоритмы и вычислимые функции 20. Лупанов О. Б. Лекции по математической логике. Часть. 1. – М.: Факультет ВМиК МГУ им. М. В. Ломоносова, 1970. – 80 с.

21. Лупанов О. Б. Лекции по математической логике. Часть 2. – М.: Факультет ВМиК МГУ им. М. В. Ломоносова, 1970. – 28 с.

22. Гильберт Д., Бернайс П. Основания математики. Логические исчисления и формал и зации арифметики. – М.: Наука, 1979. – 560 с.

23. Гильберт Д., Бернайс П. Основания математики. Теория доказательств. – М.: Наука, 1979. – 656 с.

24. Мальцев А. И. Алгоритмы и рекурсивные функции. – М.: Наука, 1965. – 392 с.

25. Марков А. А., Нагорный Н. М. Теория алгорифмов. – М.: Наука, 1984. – 432 с.

26. Мендельсон Э. Введение в математическую логику. – М.: Наука, 1976. – 320 с.

27. Новиков П. С. Элементы математической логики. – М.: Наука, 1973. – 400 с.

28. Чрч А. Введение в математическую логику. Т. 1. – М.: Ил, 1960. – 486 с.

29. Гиндикин С. Г. Алгебра логики в задачах. – М.: Наука, 1972.

Комбинаторный анализ 30. Холл М. Комбинаторика. – М.: Мир, 1970. – 424 c.

31. Сачков В. Н. Введение в комбинаторные методы дискретной математики. – М.: МЦНМО, 2004. – 424 с.

32. Кнут Д., Грехем Р. Паташник О. Конкретная математика. Основание информатики. – М.:

Мир, 1998. – 703 с.

33. Райзер Г. Дж. Комбинаторная математика. – М.: Мир, 1966. – 154 с.

34. Риордан Дж. Введение в комбинаторный анализ. – М.: ИЛ, 1963. – 288 с.

35. Риордан Дж. Комбинаторные тождества, М. Наука, 1982. – 256 с.

36. Рыбников К. А. Введение в комбинаторный анализ. – М.: Изд.-во МГУ им. М.В. Ломо носова, 1985. – 308 с.

37. Стенли Р. Перечислительная комбинаторика. – М.: Мир, 1990. – 440 с.

38. Комбинаторный анализ. Задачи и упражнения / Под ред. К. А. Рыбникова. – М.: Нау ка, 1982.

Теория графов 39. Оре О. Теория графов. – М.: Наука, 1968. – 352.

40. Харари Ф. Теория графов. – М.: Мир, 1973. – 300 с.

41. Уилсон Р. Введение в теорию графов. – М.: Мир., 1977. – 207 c.

42. Форд Л., Фалкерсон Д. Потоки в сетях. – М.: Мир, 1966. – 276 с.

43. Ветухновский Ф. Я. Графы и сети. – В. сб. Дискретная математика и математическая кибернетика. Т. 1. / Под общей редакцией С. В. Яблонского и О. Б. Лупанова. – М.:

Наука, 1974. – С. 149-206.

44. Зыков А. А. Теория конечных графов. – Новосибирск: Наука, 1969. – 543 с.

45. Кристофидес Н. Теория графов. Алгоритмический подход. М. Мир, 1978.

46. Ансель Ж. О числе монотонных булевызх функций n переменных. – В кн. Кибернетиче ский сб. Новая серия. Вып. 5. – М.: Мир, 1968. – С. 53–57.

Конечные автоматы, формальные языки и грамматики 47. Кудрявцев В. Б., Алешин С. В., Подколзин А. С. Теория автоматов. – М.: Наука, 1986. – 312 с.

48. Кук Д. Дж., Бейз Г. Компьютерная математика. – М.: Наука, 1990. – 384 с.

49. Гладкий А. В. Формальные грамматики и языки. – М.: Наука, 1973. – 368 с.

50. Гинзбург С. Математическая теория контекстно-свободных языков. – М.: Мир, 1970. – с.

51. Трахтенброт Б. А., Барздинь Я. М. Конечные автоматы (поведение и синтез). – М.: Наука, 1970. – 400 с.

52. Шоломов Л. А. Основы теории дискретных логических и вычислительных устройств. – М.: М. Наука, 1980.

Теория кодирования 53. Блейхут Р. Теория и практика кодов, контролирующих ошибки. – М.: Мир, 1986. – 576 с.

54. МакВильямс Ф. Дж., Слоэн Н. Д. А. Теория кодов, исправляющих ошибки. – М.: Связь, 1979. – 744 с.

55. Марков Ал. А. Введение в теорию кодирования. – М.: Наука, 1982. – 192 с.

56. Питерсон У. Коды, исправляющие ошибки. – М.: Мир, 1964. – 338 с.

57. Питерсон У., Уэлдон Э. Коды, исправляющие ошибки. – М.: Мир, 1976. – 596 с.

Сложность алгоритмов и вычислений 58. Алексеев В. Б. Введение в теорию сложности алгоритмов. – М.: Издательский отдел ф-та ВМиК МГУ им. М. В. Ломоносова, 2002. – 82 с.

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

60. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. – М. Мир, 1982. – 416 с.

61. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. – М.: МЦНМО, 1999. – 960 с.

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

63. Рейнгольд Э., Нивергельт Ю., Део Н. Комбинаторные алгоритмы. – М.: Мир, 1980.

64. Тоом А. Л. О сложности схемы из функциональных элементов, реализующих умножение целых чисел // ДАН СССР. – 1963. Т. 150. – С. 496-498.

8. Материально-техническое обеспечение дисциплины (модуля):

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

Автор: профессор кафедры дискретной математики механико-математического фа культета МГУ имени М. В. Ломоносова д.ф.–м.н. А. Б. Угольников.

РАБОЧАЯ ПРОГРАММА ДИСЦИПЛИНЫ (МОДУЛЯ) ДИФФЕРЕНЦИАЛЬНЫЕ урАВНЕНИЯ Направление подготовки МАТЕМАТИКА И КОМПЬЮТЕРНЫЕ НАУКИ Квалификация (степень) выпускника бакалавр (бакалавр, магистр, дипломированный специалист) Форма обучения Очная (очная, очно-заочная и др.) г. – 200 г.

1. Цели освоения дисциплины.

Целями освоения дисциплины (модуля) "Дифференциальные уравнения" являются:

1) фундаментальная подготовка в области дифференциальных уравнений;

2) овладение методами решения основных типов дифференциальных уравнений и их систем;

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

2. Место дисциплины в структуре ООП ВПО.

Дисциплина «Дифференциальные уравнения» входит в цикл профессиональных дис циплин в базовой части.

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

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

3. Компетенции обучающегося, формируемые в результате освоения дисципли ны (модуля): ОК-5, ОК-6, ОК-8, ОК-11, ПК-1, ПК-2, ПК-3, ПК-4, ПК-5, ПК-6, ПК-7, ПК-8, ПК-9, ПК-10, ПК-11, ПК-12, ПК-15, ПК-16, ПК-19, ПК-20, ПК-21, ПК-22, ПК-23, ПК-24, ПК 25, ПК-27, ПК-29.

В результате освоения дисциплины обучающийся должен:

1) знать: основные понятия теории дифференциальных уравнений, определения и свойства математических объектов в этой области, формулировки утверждений, методы их доказательства, возможные сферы их приложений;

2) уметь: решать задачи вычислительного и теоретического характера в области диф ференциальных уравнений;

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

4. Структура и содержание дисциплины (модуля).

ОБЩАЯ ТРУДОЕМКОСТЬ ДИСЦИПЛИНЫ СОСТАВЛЯЕТ 7-8 ЗАЧЕТНЫХ ЕДИНИЦ.


ПРИМЕРНАЯ ПРОГРАММА ДИСЦИПЛИНЫ:

ПОНЯТИЕ ГЕОМЕТРИЧЕСКАЯ ДИФФЕРЕНЦИАЛЬНОГО УРАВНЕНИЯ.

ИНТЕРПРЕТАЦИЯ: РАСШИРЕННОЕ ФАЗОВОЕ ПРОСТРАНСТВО, ПОЛЕ НАПРАВЛЕНИЙ, ИНТЕГРАЛЬНЫЕ КРИВЫЕ, ИЗОКЛИНЫ. ЭЛЕМЕНТАРНЫЕ МЕТОДЫ ИНТЕГРИРОВАНИЯ.

ТЕОРЕМА СУЩЕСТВОВАНИЯ И ЕДИНСТВЕННОСТИ РЕШЕНИЯ ЗАДАЧИ КОШИ ДЛЯ СИСТЕМ И УРАВНЕНИЙ ПРОИЗВОЛЬНОГО ПОРЯДКА. ТЕОРЕМА О ПРОДОЛЖЕНИИ РЕШЕНИЙ.

НЕПРЕРЫВНАЯ ЗАВИСИМОСТЬ РЕШЕНИЙ ОТ НАЧАЛЬНЫХ ЗНАЧЕНИЙ.

ОБЩАЯ ТЕОРИЯ ЛИНЕЙНЫХ СИСТЕМ И УРАВНЕНИЙ. ОПРЕДЕЛИТЕЛЬ ВРОНСКОГО, ФОРМУЛА ЛИУВИЛЛЯ – ОСТРОГРАДСКОГО. МЕТОД ВАРИАЦИИ ПОСТОЯННЫХ.

ЛИНЕЙНЫЕ УРАВНЕНИЯ И СИСТЕМЫ С ПОСТОЯННЫМИ КОЭФФИЦИЕНТАМИ. УРАВНЕНИЯ И СИСТЕМЫ СО СПЕЦИАЛЬНОЙ ПРАВОЙ ЧАСТЬЮ. ЭКСПОНЕНТА МАТРИЦЫ.

ФАЗОВОЕ ПРОСТРАНСТВО, ВЕКТОРНОЕ ПОЛЕ, ФАЗОВЫЕ КРИВЫЕ. ФАЗОВЫЙ ПОРТРЕТ ПРЯМОГО ПРОИЗВЕДЕНИЯ*. УРАВНЕНИЕ НЬЮТОНА: ИНТЕГРАЛ ЭНЕРГИИ, ПЕРИОД МАЛЫХ КОЛЕБАНИЙ*. УРАВНЕНИЕ НЬЮТОНА С ТРЕНИЕМ*.

НУЛИ РЕШЕНИЙ, ТЕОРЕМЫ СРАВНЕНИЯ (ШТУРМА)*. КРАЕВЫЕ ЗАДАЧИ:

ТЕОРЕМА ОБ АЛЬТЕРНАТИВЕ, ФУНКЦИЯ ГРИНА, ЗАДАЧА ШТУРМА – ЛИУВИЛЛЯ*.

УСТОЙЧИВОСТЬ ПО ЛЯПУНОВУ И АСИМПТОТИЧЕСКАЯ УСТОЙЧИВОСТЬ.

КРИТЕРИЙ УСТОЙЧИВОСТИ ЛИНЕЙНОЙ СИСТЕМЫ С ПОСТОЯННЫМИ КОЭФФИЦИЕНТАМИ.

ТЕОРЕМА ЛЯПУНОВА ОБ УСТОЙЧИВОСТИ ПО ПЕРВОМУ ПРИБЛИЖЕНИЮ. ФУНКЦИЯ ЛЯПУНОВА: ЛЕММЫ ЛЯПУНОВА ОБ УСТОЙЧИВОСТИ И АСИМПТОТИЧЕСКОЙ УСТОЙЧИВОСТИ, ТЕОРЕМА ЧЕТАЕВА О НЕУСТОЙЧИВОСТИ*.

ФАЗОВАЯ ПЛОСКОСТЬ. ТОПОЛОГИЯ ФАЗОВЫХ КРИВЫХ. КЛАССИФИКАЦИЯ ЛИНЕЙНЫХ ОСОБЫХ ТОЧЕК НА ПЛОСКОСТИ: УЗЕЛ, СЕДЛО, ФОКУС, ЦЕНТР.

СЕПАРАТРИСЫ*. ПРЕДЕЛЬНЫЙ ЦИКЛ: ОТОБРАЖЕНИЕ ПУАНКАРЕ, УСТОЙЧИВОСТЬ ПРЕДЕЛЬНОГО ЦИКЛА, МУЛЬТИПЛИКАТОР, ТЕОРЕМА ФЛОКЕ*.

ДИФФЕРЕНЦИРУЕМОСТЬ РЕШЕНИЯ ПО ПАРАМЕТРУ И НАЧАЛЬНЫМ ЗНАЧЕНИЯМ.

УРАВНЕНИЕ В ВАРИАЦИЯХ. ОДНОПАРАМЕТРИЧЕСКАЯ ГРУППА ДИФФЕОМОРФИЗМОВ*.

ТЕОРЕМА О ВЫПРЯМЛЕНИИ ВЕКТОРНОГО ПОЛЯ В ОКРЕСТНОСТИ НЕОСОБОЙ ТОЧКИ*.

ИРРАЦИОНАЛЬНЫЙ ПОВОРОТ ОКРУЖНОСТИ*. РАЦИОНАЛЬНАЯ И ИРРАЦИОНАЛЬНАЯ ОБМОТКИ ТОРА*.

ПЕРВЫЕ СУЩЕСТВОВАНИЕ ИНТЕГРАЛЫ АВТОНОМНОЙ СИСТЕМЫ. ПОЛНОЙ СИСТЕМЫ ПЕРВЫХ ИНТЕГРАЛОВ.

ЛИНЕЙНЫЕ И КВАЗИЛИНЕЙНЫЕ УРАВНЕНИЯ С ЧАСТНЫМИ ПРОИЗВОДНЫМИ ПЕРВОГО ПОРЯДКА. ХАРАКТЕРИСТИКИ. ЗАДАЧА КОШИ. ТЕОРЕМА СУЩЕСТВОВАНИЯ И ЕДИНСТВЕННОСТИ РЕШЕНИЯ ЗАДАЧИ КОШИ.

5. Образовательные технологии: активные и интерактивные формы.

6. Оценочные средства для текущего контроля успеваемости, промежуточной ат тестации по итогам освоения дисциплины и учебно-методическое обеспечение само стоятельной работы студентов В течение семестра студенты решают задачи, указанные преподавателем, к каждому семинару. В каждом семестре проводятся по 2 контрольные работы (на семинарах). Зачет выставляется после решения всех задач контрольных работ.

3 семестр Контрольная работа № 1. Решить задачу Коши:

y' 3 2 x y y (1) 2. Найти все периодические решения уравнения y' y cos x 1.

y' y 2 x.

3. Решить уравнение 4. Найти ортогональные траектории семейства: y Ce x 1.

2 x ( n 1) 5. Для каких n уравнение y F ( x, y, y',..., y (n) ) с гладкой правой частью может иметь решения x 2 x и -1?

Контрольная работа № 1. Решить уравнение: ( x 2 y 2 y )dx x(1 2 y )dy.

2. Решить уравнение: y ln(1 y 2 ).

3. Решить уравнение: y y 2 y 2.

4. Решить уравнение: y y 4 x sin x.

5. Решить уравнение: x( x 2) y ( x 4) y y 0.

4 семестр Контрольная работа № 1. При каких R уравнение 2 x cos 2 x 1 имеет хотя бы одно периодическое x решение?

2. Найти общее решение системы:

x 5 x 2 y 7e 3t.

y 4 x 4 y 3 0 3. Вычислить экспоненту матрицы: 0 6 9.

0 1 x Ax, x R 2 :

4. Дана фундаментальная система решений системы 9te e 6te t t t t e 6te t, 4te t. Найти det A и a11.

Контрольная работа № 1. Исследовать нулевое решение на устойчивость (асимптотическую устойчивость):

x.

y sin( y y / 2) e 2 y 2. Найти особые точки, указать их тип, исследовать их на устойчивость, изобразить особые точки типа фокус:

x 2 y 2.

y 3e x e y x при 0 : x sin x 0, x(0) 0, x(0) 2.

3. Найти x z z 4. Решить задачу Коши: 2 x ( xz 2 y ) 2 z, z x 2, y 0.

x y 7. Учебно-методическое и информационное обеспечение дисциплины (модуля) Дифференциальные уравнения а) основная литература:

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

2. Бибиков Ю.Н. Курс обыкновенных дифференциальных уравнений. М.: Высшая школа, 1991.

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

Изд-во МГУ, 1984.

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

5. Сергеев И.Н. Лекции по дифференциальным уравнениям. М.: Изд-во ЦПИ при мех.-мат.

ф-те МГУ. 6. Филиппов А.Ф. Введение в теорию дифференциальных уравнений. М.: Едиториал УРСС, 2004.

7. Филиппов А.Ф. Сборник задач по дифференциальным уравнениям. М.;

Ижевск: Изд-во РХД, 2000.

б) дополнительная литература:

1. Андреев А.Ф. Особые точки дифференциальных уравнений. Минск: Выш. школа, 1979.

2. Андронов А.А., Витт А.А., Хайкин С.Э. Теория колебаний. М.: Физматгиз, 1959.

3. Андронов А.А., Леонтович Е.А., Гордон И.И., Майер А.Г. Качественная теория динамиче ских систем на плоскости. М.: Наука, 1966.

4. Арнольд В.И. Дополнительные главы теории обыкновенных дифференциальных уравне ний. М.: Наука, 1978.

5. Арнольд В.И., Ильяшенко Ю.С. Обыкновенные дифференциальные уравнения. //Итоги науки и техники. Сер. «Современные проблемы математики. Фундаментальные направле ния», Том 1. М.: ВИНИТИ, 1985.

6. Боголюбов Н.Н., Митропольский Ю.А. Асимптотические методы в теории нелинейных колебаний. М.: Наука, 1974.

7. Демидович Б. П. Лекции по математической теории устойчивости. М.: Наука, 1967.

8. Камке Э. Справочник по обыкновенным дифференциальным уравнениям. М.: Наука, 1971.

9. Коддингтон Э.А., Левинсон Н. Теория обыкновенных дифференциальных уравнений. М.:

Изд-во иностр. лит., 1958.

10. Немыцкий В.В., Степанов В.В. Качественная теория дифференциальных уравнений.

М.;

Л.: Гостехиздат, 1949.

11. Сансоне Дж. Обыкновенные дифференциальные уравнения. М.: Изд-во иностр. лит. Т.1.

1953;

Т.2. 1954.

12. Хартман. Обыкновенные дифференциальные уравнения. М.: Мир, 1970.

в) программное обеспечение и Интернет-ресурсы: не требуются.

8. Материально-техническое обеспечение дисциплины (модуля): учебные аудито рии для проведения лекционных и семинарских занятий.

Авторы: доцент кафедры дифференциальных уравнений А.Н. Ветохин, доцент кафедры дифференциальных уравнений А.Ю. Горицкий.

Рецензент: профессор кафедры дифференциальных уравнений И.Н. Сергеев.

РАБОЧАЯ ПРОГРАММА ДИСЦИПЛИНЫ (МОДУЛЯ) Базы данных Направление подготовки МАТЕМАТИКА И КОМПЬЮТЕРНЫЕ НАУКИ Квалификация (степень) выпускника бакалавр (бакалавр, магистр, дипломированный специалист) Форма обучения Очная (очная, очно-заочная и др.) г. – 200 г.

1. Цели освоения дисциплины.

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

2. Место дисциплины в структуре ООП ВПО Для изучения и освоения дисциплины нужны первоначальные знания из курсов мате матического анализа, алгебры, аналитической геометрии. Знания и умения, приобретенные студентами в результате изучения дисциплины, будут использоваться при изучении курсов вычислительного практикума, при выполнении курсовых и дипломных работ, связанных с математическим моделированием и обработкой наборов данных.

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

В результате усвоения данной дисциплины студент должен приобрести следующие компетенции: ОК-1, ОК-6;

ОК-8;

ОК-9;

ОК-10;

ОК-12, ОК-13, ОК-14;

ПК-2, ПК-3;

ПК-8, ПК 11, ПК-12, ПК-17, ПК-19, ПК-20, ПК-21.

В результате освоения дисциплины обучающийся должен:

1) Знать: методы и технологии создания баз данных, абстракции основных структур данных и методы их обработки и реализации, базовые алгоритмы обработки данных, визу альные нотации.

2) Уметь: разрабатывать строить модель сущность связь, модели сценариев использо вания и запросы к БД на языке SQL;

3) Владеть методами и технологиями создания баз данных, описания структур данных и других базовых представлений данных.

4. Структура и содержание дисциплины.

Общая трудоемкость дисциплины составляет 2-3 зачетных единиц.

Примерное содержание дисциплины:

1 Информационные системы (ИС) и БД. Сервера и Архитектура ИС. Основные функции системы управления БД (СУБД). Транзакция. Корпоративные и настольные БД.

2 Понятие Базы данных (БД). Модели данных - иерархическая, сетевая, реляционная;

их особенности. Логическая и физическая структура БД.

3 ER-модель, е состав, способ построения. UML-диаграмма классов, отношения. Пря мое и обратное проектирование БД. CASE средство IBM Rational Rose.

4 Реляционные БД. Понятие отношения. Основные операции реляционной алгебры.

Операция соединения. Нормальные формы и их связь с ER-моделью.

5 Коллоквиум «ER-Модель»

6 Язык SQL. Поддержка в SQL операций реляционной алгебры. Типы операторов – DDL, DML, DCL - и их назначение. Структура оператора SELECT. Примеры.

7 Язык SQL. Оператор SELECT и соединения таблиц. Примеры.

8 Язык SQL. Оператор SELECT с агрегирующими функциями. Примеры.

9 Коллоквиум «SQL»

10 Жизненный цикл ИС (ГОСТ 12207). Основные, вспомогательные и управляющие процессы. Состав работ процессов и их назначение по ГОСТ 11 Процесс создания ИС/БД: Методология RUP - IBM Rational Unified Process. Лучшие практики. Фазы, итерации, риски.


12 Дисциплина RUP Управление требованиями, ее роли и артефакты. Модель сценари ев использования (Use Case Model). Use Case диаграмма на UML.

13 Коллоквиум «Use Case Model»

14 БД в средствах поддержки процессов создания ИС - назначение и основные возмож ности CASE систем: IBM Rational Requisite Pro, IBM Rational ClearQuest, IBM Rational ClearCase.

15 Аналитические БД, сравнение OLAP и OLTP. Хранилища данных. OLAP-куб, его на значение и построение.

16 Восстановление пропущенных значений - линейная модель, коэффициент R2. Сколь зящий контроль, коэффициент R2cv (cross validation).

17 Восстановление пропущенных значений - дерево решений. Алгоритмы кластерного анализа и их сравнение.

18 Восстановление пропущенных значений - эволюционные алгоритмы: генетический алгоритм, метод группового учета аргументов (МГУА).

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

6. Оценочные средства для текущего контроля успеваемости, промежуточной ат тестации по итогам освоения дисциплины и учебно-методическое обеспечение само стоятельной работы студентов Контроль качества подготовки осуществляется путем проверки теоретических знаний и практических навыком посредством 1) промежуточных контрольных работ 2) экзамена в конце семестра.

Пример контрольного задания – «найти сценарии использования и действующих лиц»:

Как руководителю ИТ в фирме Acme Inc, Вам поручено построение новой системы расчета зарплаты, которая за менит существующую систему. Фирма нуждается в новой системе, которая позволит служащим записывать отработанные часы в свой электронный табель (timecard) и будет автоматически производить расчет зарплаты на основе отработанных часов и общей сумме продаж (для уполномоченных служащих).

Новая система будет заказной. Она должна использовать интерфейс Windows, чтобы служащие могли вводить электронный табель (timecard) информацию, вводить данные о выполненных заказах, могли изменять предпочтение служа щего (по методу оплаты), а также создавать различные отчеты. Система будет работать на ПК служащих повсюду в компа нии. По соображениям безопасности служащие могут иметь доступ и редактировать только свои собственные табели и дан ные о заказах.

Система должна сохранить информацию обо всех служащих в компании (Acme в настоящее время имеет около 5,000 служащих по всему миру). Система должна платить каждому служащему «правильное» количество денег, вовремя, и тем методом, который он себе определил (возможные методы оплаты описаны ниже). Acme, по причинам экономии затрат, не будет заменять одну из унаследованных БД, Project Management Database, которая содержит всю информацию относи тельно номеров проектов (открытых для выплаты зарплаты). Новая система должна работать с Project Management Database, которая основана на СУБД DB2 на универсальной ЭВМ IBM. Payroll System будет иметь доступ, но не должна изменять информацию, хранимую в Project Management Database.

Часть служащих работают на почасовой ставке, и их работа оплачивается по норме за отработанные часы. Они представляют timecards, в которых записаны даты, число часов, отработанных по конкретному проекту, и номер проекта.

Если кто-то работает больше чем 8 часов, то фирма Acme платит им в 1.5 раза больше их нормы за дополнительные часы.

Почасовые рабочие получают зарплату каждую пятницу. Часть служащих зачислены в штат и получают фиксированный заработок. Они также представляют timecards, где записаны даты, часы и номер проекта. Они получают зарплату в послед ний рабочий день месяца. Некоторые из штатных служащих, кроме того, получают комиссионные, основанные на их про дажах (оформленных заказах). Они вносят в систему данные о заказах, которые включают дату и размер продажи. Процент комиссии определен индивидуально для каждого служащего, и – составляет 10 %, 15 %, 25 %, или 35 %. Одно из наиболее важных свойства новой системы – генерация отчетов служащего. Служащие смогут запросить систему по числу отработан ных часов по проекту, общему количеству всех часов, по полной сумме выплат за год и т.д.

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

Администратор системы должен поддерживать информацию обо всех служащих. Он ответствен за добавление но вых служащих, удаление служащих и за изменение информации о служащем: имя, адрес, классификации оплаты (почасо вый, штатник, комиссионный). Сисадмин может формировать различные административные отчеты. Систем будет автома тически запускаться каждую пятницу и/или в последний рабочий день месяца, и рассчитывать зарплату соответствующим служащим. Новая система должна быть разработана так, чтобы расчет платежей всегда производился автоматически, и не было бы необходимости в ручном вмешательстве в ее работу.

Пример контрольного задания «Построить модель «сущность-связь» (ER-модель) Как руководителю отдела информационных систем Колледжа Wylie вам поручено развитием новой системы реги страции студентов. Колледж хотел бы, чтобы новая система типа «клиент-сервер» заменила старую систему, разработанную на универсальной ЭВМ. Новая система позволит слушателям регистрироваться на курсы и просматривать свои зачетные ведомости на персональных компьютерах, присоединенных к локальной сети (LAN) университетского городка. Профессора будут иметь доступ к системе, чтобы подтвердить преподавание курсов, а также записывать отметки (экзаменационные оценки) студентов. Из-за уменьшения в федеральном финансировании колледж не может позволить себе заменять всю ста рую систему одновременно. Колледж будет поддерживать существующую базу данных каталога курса, где собрана вся ин формация о курсах. Эта база данных - Ingress реляционная база данных выполняющаяся на DEC VAX. Колледж вложил капитал в открытый интерфейс SQL, который позволяет иметь доступ этой базе данных от серверов Unix колледжа. Произ водительность унаследованной системы довольно бедна, так что новая система должна обеспечить быстрый доступ к дан ным унаследованной системы. Новая система будет читать информацию о курсах из унаследованной базы данных, но не будет модернизировать ее. Офис колледжа продолжит поддержку информации о курсах через другую систему.

В начале каждого семестра слушатели могут запрашивать каталог курсов, содержащий список семинарских заня тий в течение семестра. Информация о каждом курсе, такая как профессор, кафедра, и пререквизиты курса будет включена в каталог, чтобы помочь слушателям принять информированное решение. Новая система позволит слушателям выбирать четыре семинарских занятия в течение текущего семестра. Кроме того, каждый слушатель должен указать два альтернатив ных выбора в случае, если слушатель не может быть назначен на первичный курс. Семинарские занятия будут иметь мак симум 10 слушателей и минимума 3 слушателя. Семинарское занятие с меньшим, чем три числом слушателей будет отме нено. В течение каждого семестра, есть период времени, что слушатели могут изменять свой график занятий. Слушатели должны имеют доступ система, чтобы добавлять или удалять курсы из своего расписания (графика занятий). Как только процесс регистрации закончен, система регистрации посылает информацию в систему выписки счетов, так что слушатель мог оплатить свое обучение в данном семестре. Если курс заполняется в течение фактического процесса регистрации, слу шатель должен быть уведомлен об этом перед передачей в систему своего графика занятий для обработки.

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

Пример контрольного задания «SQL-запросы»

Используя таблицы Таблица 1.1: Продавцы SNUM SNAME CITY COMM • snum – уникальный номер, назначенный каждому продавцу("номер служащего") – первичный ключ;

• sname – имя продавца;

• city – расположение продавца(город);

• comm – комиссионные продавца в десятичной форме.

Таблица 1.2: Заказчики CNUM CNAME CITY RATING SNUM • cnum - уникальный номер Заказчика – первичный ключ;

• cname - имя заказчика;

• city – место расположения заказчика (город);

• rating - код рейтинга, т.е. уровень предпочтения данного заказчика перед другими. Более высокий номер указы вают на большее предпочтение (рейтинг);

• SNUM - номер продавца, назначенного заказчику (из таблицы Продавцов) – внешний ключ.

Таблица 1.3: Заказы ONUM AMT ODATE CNUM SNUM • onum - уникальный номер покупки (заказа) – первичный ключ;

• amt – величина покупки (заказа) в условной денежной единице;

• odate - дата покупки (заказа);

• cnum - номер заказчика, сделавшего покупку (из таблицы Заказчиков) – внешний ключ;

• snum - номер продавца, оформившего продажу (заказ) (из таблицы Продавцов) – внешний ключ.

Напишите запрос, который бы вывел список номеров Заказов, сопровождающихся именем заказчика, который соз давал эти Заказы.

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

Напишите запрос, который бы выводил всех заказчиков, обслуживаемых продавцом с комиссионными выше 12%.

Выведите имя заказчика, имя продавца и ставку комиссионных продавца.

Примеры вопросов экзаменационных билетов 1. Можно ли создавать ИС без использования СУБД? Опишите преимущества и недостатки такого про ектного решения.

2. Что такое и чем различаются логическое и физическое представление данных? Какова роль БД в их «различении»?

3. Что такое концептуальная модель БД?

4. Что такое метаданные, и для чего они используются в СУБД?

5. Опишите основные этапы развития БД и информационных систем.

6. Чем иерархическая модель данных отличается от сетевой?

7. Что такое сервер? Чем клиент-серверные СУБД отличаются от файл-серверных систем?

8. Что такое транзакции. Для чего они используются в БД?

9. Опишите ACID свойства транзакции.

10. Дайте определения, что такое ключ? Какие бывают ключи?

11. Что такое сервер приложений? Для чего он используется в ИС? Возможно ли построение информа ционной системы без сервера приложений?

12. Что такое многозвенная архитектура ИС?

7. Учебно-методическое и информационное обеспечение дисциплины.

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

Дейт К. Введение в системы баз данных: пер с англ. – М.: Издательский дом «Вильямс», 2000.

Хансен Г., Хансен Дж. Базы данных: разработка и управление: Пер с англ. – М.: Издательский дом БИНОМ, 1999.

Васкевич Д. Стратегии клиент/сервер. Руководство по выживанию для специалистов по реор ганизации бизнеса. – К.: Диалектика, 1996.

Буч Г., Рамбо Дж., Джекобсон А. Язык UML. Руководство пользователя.: Пер. с англ. – М.:

ДМК, 2000.

Грабер М. Введение в SQL: Пер. с англ. – М., ЛОРИ, 1996.

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

б) дополнительная литература:

В.Д.Валединский, Ю.Н.Пронкин, Вычислительные системы и программирование, Схемы хра нения данных, М.Изд-во ЦПИ мех-мат.ф-та МГУ, 2006.

В.Д.Валединский, А.А.Корнев, Методы программирования в примерах и задачах, М.Изд-во ЦПИ мех-мат.ф-та МГУ, Г.Буч. Объектно-ориентированный анализ и проектирование с примерами приложений на C++. М.: "Бином", А. Пол. Объектно-ориентированное программирование на C++ М.: "Бином", 1999. в) программное обеспечение и Интернет-ресурсы http://citforum.ru/ www.citforum.ru www.rational.com www.it.ru 8. Материально-техническое обеспечение дисциплины (модуля) Учебный класс должен быть снабжен персональным компьютером преподавателя, проектором и экраном.

Автор(ы) проф. М.И.Кумсков Рецензент(ы) доц. К.Ю.Богачев РАБОЧАЯ ПРОГРАММА ДИСЦИПЛИНЫ (МОДУЛЯ) Математическое и программное обеспечение БЕЗОПАСНОСТИ информационных систем Направление подготовки МАТЕМАТИКА И КОМПЬЮТЕРНЫЕ НАУКИ Квалификация (степень) выпускника бакалавр (бакалавр, магистр, дипломированный специалист) Форма обучения Очная (очная, очно-заочная и др.) г. Москва, 2009 – 2010 г.

1. Цели освоения дисциплины Цели освоения дисциплины «Математическое и программное обеспечение информа ционной безопасности» заключаются в получении представления о современной методоло гии обеспечения информационной безопасности и о роли математических методов и про граммно-технических средств в обеспечении информационной безопасности, в подготовке к применению методов обеспечения информационной безопасности на этапах проектирования, разработки и эксплуатации сложно организованных компьютерных систем.

2. Место дисциплины в структуре ООП ВПО Курс входит в модуль «Основы компьютерных наук» в блок общепрофессиональных дисциплин.

При освоении материалов курса от обучающегося требуется подготовка по следую щим дисциплинам: дискретная математика и математическая логика, теория вероятностей, операционные системы, технология программирования.

3. Компетенции обучающегося, формируемые в результате освоения дисципли ны (модуля) В результате освоения дисциплины «Математическое и программное обеспечение информационной безопасности» у обучающегося формируются компетенции ОК-9, ОК-11, ОК-13, ПК-1, ПК-9, ПК-10, ПК-12, ПК-20, ПК-22, ПК-23.

В результате освоения дисциплины обучающийся должен:

1) знать:

основные положения методологии комплексного подхода к обеспечению ин формационной безопасности;

общие положения формирования политики безопасности компьютерной сис темы;

типовые математические модели информационно безопасных систем;

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

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

типовые подходы к программной реализации базовых сервисов безопасности в компьютерных системах;

основные принципы обеспечения информационной безопасности с позиции технологии программирования;

типовые ошибки программирования, приводящие к уязвимостям компьютер ным систем;

2) владеть:

понятийным аппаратом информационной безопасности;

навыками применения положений современных нормативных документов и стандартов в области информационной безопасности;

навыками проектирования программных систем защиты и «безопасного» про граммирования;

навыками проведения аудита программного обеспечения на предмет наличия типовых ошибок программирования;

3) уметь:

строить на основе типовых математических моделей информационно безопас ных систем модели безопасности компьютерных комплексов;

применять математические методы в обеспечении информационной безопас ности.

4. Структура и содержание дисциплины (модуля) Общая трудоемкость дисциплины составляет 3-4 зачетные единицы.

Примерная программа дисциплины:

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

Элементы теории информации.

Понятие ценности информации. Учет ресурсов противника и выбор оптималь ной по стоимости системы защиты. Стратегия злоумышленника при атаке системы. Наибо лее распространенные угрозы и атаки.

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

Административные меры обеспечения информационной безопасности. Опера ционные меры обеспечения информационной безопасности Программно-технические меры обеспечения информационной безопасности:

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

Программно-технические меры обеспечения информационной безопасности:

протоколирование и аудит. Идеология построения систем протоколирования и аудита. Ма тематические модели и задачи.

Программно-технические меры обеспечения информационной безопасности:

криптография. Решаемые задачи, обзор основных методов. Криптография с симметричным ключом. Криптография с открытым ключом. Эллиптические кривые. Квантовая криптогра фия. Математические задачи. Некоторые примеры криптографических систем и протоколов.

Программно-технические меры обеспечения информационной безопасности:

построение сетей и экранирование. Особенности обеспечения информационной безопасно сти в Internet.

Программно-технические меры обеспечения информационной безопасности:

разграничение доступа.

Программно-технические меры обеспечения информационной безопасности:

обеспечение высокой доступности.

Информационная безопасность с точки зрения технологии программирования.

Безопасное программирование и построение систем защиты. Основные принципы и наибо лее распространенные ошибки. Анализ некоторых существующих программных реализаций сервисов безопасности.

5. Образовательные технологии.

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

6. Оценочные средства для текущего контроля успеваемости, промежуточной аттестации по итогам освоения дисциплины и учебно-методическое обеспечение самостоятельной работы студентов Примерные контрольные (экзаменационные) вопросы.

Уровни комплексного подхода к обеспечению информационной безопасности.

Современные стандарты в области обеспечения информационной безопасности.

Общие положения формирования политики безопасности.

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

Модель Белла-Лападула и модель Биба.

Модели дискреционного разграничения доступа.

Модель «take-grant».

Информационные потоки и скрытые каналы.

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

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

Архитектура систем протоколирования и аудита.

Криптографические схемы с симметричным ключом.

Криптографические схемы с открытым ключом.

Типовые криптографические системы и протоколы.

Основные методы обеспечения информационной безопасности в компьютерных сетях.

Подходы к обеспечению высокой доступности.

Основные положения безопасного программирования и построения систем защи ты.

Типовые ошибки программирования, приводящие к уязвимостям программного обеспечения.

7. Учебно-методическое и информационное обеспечение дисциплины (модуля) а) Основная литература:

В. А. Галатенко «Основы информационной безопасности» М.: ИНТУИТ.РУ»

Интернет университет информационных технологий», 2003. – 280 с.;

А. А. Грушо, Е. Е. Тимонина «Теоретические основы защиты информации» — М., Яхтсмен, 1996;



Pages:     | 1 | 2 || 4 |
 





 
© 2013 www.libed.ru - «Бесплатная библиотека научно-практических конференций»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.