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

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

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


Pages:     | 1 |   ...   | 2 | 3 ||

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

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

В. А. Васенин «Проблемы математического, алгоритмического и программно го обеспечения компьютерной безопасности в Интернет», Математика и безо пасность информационных технологий. Материалы конференции в МГУ 23- октября 2003 г. — М: МЦНМО, 2004, с.111-141;

Критически важные объекты и кибертерроризм. Часть 1. Системный подход к организации противодействия. / О. О. Андреев и др. Под ред. В. А. Васенина.

— М.: МЦНМО, 2008. — 398 с.;

Критически важные объекты и кибертерроризм. Часть 2. Аспекты программ ной реализации средств противодействия. / О. О. Андреев и др. Под ред.

В. А. Васенина. МЦНМО, 2008. — 607 с.

М.:

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

А. В. Галатенко «Математические модели и программные средства защиты распределнных компьютерных систем». — диссертация на соискание степени кандидата физ.-мат. наук;

Bruce Schneier Applied Cryptography — John Wiley & Sons, 1996;

Журнал JetInfo 1996г. — N1-3, N12-13, N19, 1999 г. — N8, 2000 г. — N2.

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

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

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

Целями освоения дисциплины (модуля) «Программирование параллельных ЭВМ»

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

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

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

3. Компетенции обучающегося, формируемые в результате освоения дисципли ны (модуля) Практикум на ЭВМ В результате усвоения данной дисциплины студент должен приобрести следующие компетенции: ОК-1, ОК-6, ОК-8, ОК-9, ОК-10, ОК-11, ОК-12, ОК-13, ОК-14, ПК-2, ПК-3, ПК-8, ПК-9, ПК-11, ПК-12, ПК-17, ПК-19, ПК-20, ПК-21.

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

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

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

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

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

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

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

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

1 Архитектуры параллельных ЭВМ, параллелизм процессора, дисциплина доступа к памяти 2 Объекты синхронизации и взаимного исключения. Использование интерфейса про цессов в параллельных программах 3 Потоки исполнения. Создание, управление, планирование. Объекты взаимной син хронизации и исключения.

4 Интерфейс MPI. Попарные и коллективные обмены. Учет архитектуры ЭВМ.

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

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

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

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

Пример контрольного задания в 5 семестре Написать программу умножения двух матриц на параллельной ЭВМ с распределен ной памятью. Программа должна обеспечивать равномерную загруженность всех процессо ров и давать ускорение на 4-х процессорах не хуже, чем в 3.6 раза по сравнению со временем работы на одном процессоре.

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

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

К.Ю.Богачев. Основы параллельного программирования. М.: Изд-во Бином, 2003.

К.Ю.Богачев. Практикум на ЭВМ. Методы решения линейных систем и нахождения собственных значений. - 2-е изд., перераб. и дополн., Изд-во мех-мат. ф-та МГУ им.

М.В.Ломоносова, 1999.

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

Воеводин В.В., Воеводин Вл. Параллельные вычисления. БХВ-Петербург, 2002.

в) программное обеспечение и Интернет-ресурсы http://parallel.ru/ http://computer.org/parascope/ 8. Материально-техническое обеспечение дисциплины (модуля) При освоении дисциплины для выполнения лабораторных работ необходимы классы персональных компьютеров с набором базового программного обеспечения разработчика системы программирования на языках С/С++, с возможностью многопользовательской рабо ты, централизованного администрирования и доступа к информационным ресурсам. Также необходима параллельная ЭВМ и система очередей для удаленного доступа к ее ресурсам с каждого рабочего места в классе.

Автор(ы) доц К.Ю.Богачев Рецензент(ы) доц. В.Д.Валединский ДЕЙСТВИТЕЛЬНЫЙ АНАЛИЗ 1. Системы множеств (полукольца, кольца, алгебры, алгебры и т.д.). Различные свой ства этих систем.

2. Меры на полукольцах. Классическая мера Лебега на полукольце промежутков в n и ее аддитивность.

3. Продолжение меры с полукольца на минимальное кольцо. Внешние меры Лебега и Жордана. Меры Лебега и Жордана. Их свойства.

4. Полнота и непрерывность мер. Мера Бореля. Меры Лебега-Стилтьеса на прямой и в n. конечные меры. Теоремы о структуре измеримых множеств.

5. Измеримые функции. Их свойства. Измеримые функции и предельный переход.

6. Сходимость по мере и почти всюду. Их свойства.

7. Теоремы Егорова и Лузина.

8. Интеграл Лебега для конечно-простых функций и его свойства.

9. Определение интеграла Лебега в общем случае. Основные свойства интеграла Лебега.

10. Теоремы о предельном переходе под знаком интеграла Лебега.

11. Абсолютная непрерывность интеграла Лебега. Критерий интегрируемости по Лебегу на множестве конечной меры. Неравенство Чебышева.

12. Связь между интегралами Римана и Лебега на отрезке в.

13. Прямое произведение мер. Теорема Фубини.

14. Заряды. Разложения Хана и Жордана.

15. Теорема Радона-Никодима.

16. Неравенства Гельдера и Минковского. Пространства L p.

17. Полнота пространств L p. Плотные множества функций в L p (a, b ).

18. Дифференцирование интеграла Лебега на отрезке по переменному верхнему пре делу.

19. Абсолютно непрерывные функции на отрезке и их связь с интегралами Лебега.

20. Замена переменной и интегрирование по частям в интеграле Лебега по отрезку.

21. Гильбертовы пространства. Неравенство Коши-Буняковского.

22. Теорема о разложении гильбертова пространства в прямую сумму.

23. Ортонормированные системы и базисы в гильбертовых пространствах.

24. Процесс ортогонализации Гильберта-Шмидта.

25. Неравенство Бесселя. Равенство Парсеваля.

26. Теорема Рисса-Фишера.

27. Линейные функционалы в гильбертовых пространствах. Их общий вид.

Литература 1. Колмогоров А.Н., Фомин С.В. Элементы теории функций и функционального анализа.

М., Наука, 1981, 1989.

2. Натансон И.П. Теория функций вещественной переменной. М., Наука,1979.

3. Дьяченко М.И., Ульянов П.Л. Мера и интеграл. М., Факториал, 1998, 2002.

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

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

Задача Коши для квазилинейного уравнения в частных производных первого 1.

порядка. Классические и обобщенные решения. Условия Ранкина-Гюгонио.

Условие допустимости разрыва типа условия возрастания энтропии. Решение задачи Римана о распаде произвольного разрыва.* Физические задачи, приводящие к уравнениям в частных производных второго 2.

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

Линейное уравнение с частными производными второго порядка. Главная часть 3.

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

Понятие характеристики для линейного уравнения второго порядка. Постанов 4.

ка задачи Коши. Теорема Коши-Ковалевской. Доказательство существования решения методом мажорант.* Задача Коши для уравнения струны, формула Даламбера. Гладкость решения в 5.

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

Ограниченная струна. Метод Фурье. Обоснование метода Фурье для уравнения 6.

колебаний закрепленной струны.

Задача Штурма-Лиувилля. Свойства собственных значений и собственных 7.

функций оператора Штурма-Лиувилля. Функция Грина задачи Штурма Лиувилля. Доказательство полноты системы собственных функций сведением к теореме Гильберта-Шмидта.* Задача Коши для волнового уравнения. Энергетическое неравенство. Характе 8.

ристический конус. Теорема единственности и непрерывной зависимости ре шений от начальных данных.

Формула Кирхгофа решения задачи Коши для волнового уравнения в R 3. Рас 9.

пространение колебаний в R 3. Передний и задний фронт волны.

Метод спуска. Формула Пуассона решения задачи Коши для волнового урав 10.

нения в R 2. Распространение волн в R 2 и R 1. Область зависимости решений от начальных данных.

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

11.

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

Постановка задачи Коши для уравнения теплопроводности. Теорема единст 12.

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

Решение задачи Коши для уравнения теплопроводности при помощи преобра 13.

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

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

Формулы Грина. Фундаментальное решение оператора Лапласа. Представление 15.

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

Гармонические функции, их свойства (теорема о потоке, о бесконечной диффе 16.

ренцируемости). Принцип максимума. Лемма о нормальной производной.

Основные краевые задачи для уравнения Лапласа. Единственность решения 17.

задачи Дирихле в ограниченной области, условие существования решения за дачи Неймана.

Постановка внешних краевых задач Дирихле и Неймана. Исследование единст 18.

венности.

Функция Грина задачи Дирихле для уравнения Лапласа, ее симметрия. Функ 19.

ция Грина шара в Rn. Обоснование формулы Пуассона.

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

Харнака. Теорема Лиувилля.

Оценки производных гармонических функций. Теорема Лиувилля. Аналитич 21.

ность гармонических функций.* Обобщенные производные в смысле Соболева. Пространство H 1 (), его пол 22.

нота.

23. 0 (). Неравенство Фридрихса. Нормы и скалярное произве Пространство H 0 ( ).

дение в H 1 () и H Обобщенная задачи Дирихле для уравнения Пуассона с однородными краевы 24.

ми условиями.

Решение задачи Дирихле для уравнения Пуассона вариационными методом.

25.

Обобщенная задача Дирихле для уравнения Лапласа с неоднородными краевы 26.

ми условиями.

Оператор усреднения и его свойства. Теоремы о сходимости последовательно 27.

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

Общее понятие корректной задачи математической физики. Примеры коррект 28.

ных и некорректных задач. Пример Адамара.

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

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

5 семестр Контрольная работа № Контрольная работа № 6 семестр Контрольная работа № Контрольная работа № 7. Учебно-методическое и информационное обеспечение дисциплины.

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

Олейник О.А. «Лекции об уравнениях с частными производными». М.: Изд-во 1.

БИНОМ. Лаборатория знаний, 2005.

Петровский И.Г. «Лекции об уравнениях с частными производными». М.: Физматгиз, 2.

1961.

Тихонов А.Н., Самарский А.А. «Уравнения математической физики». М.: Изд-во 3.

Моск. Ун-та, 1999.

Владимиров В.С. «Сборник задач по уравнениям математической физики», М.: Физ 4.

матлит, Шамаев А. С. (ред). «Cборник задач по уравнениям с частными производными», М.:

5.

Изд-во БИНОМ. Лаборатория знаний, 2008.

Горицкий А.Ю., Кружков С.Н., Чечкин Г.А. «Уравнения с частными производными 6.

первого порядка» (Учебное пособие). М.: Изд-во ЦПИ при мех-мат фак-те МГУ, 1999.

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

Соболев С.Л. Уравнения математической физики. М.: Наука, 1966.

1.

Владимиров В.C. «Уравнения математической физики». М.: Наука, 1988.

2.

Михайлов В.П. «Дифференциальные уравнения в частных производных», М.: Наука, 3.

1983.

Арнольд В. И.. «Лекции об уравнениях с частными производными». М.: Фазис, 1997.

4.

Будак Б.М., Самарский А.А., Тихонов А.Н. «Сборник задач по математической физи 5.

ке». М.: Наука, 1972, 4-е изд. М.: Физматлит, 2003.

6. Смирнов М.М. Задачи по уравнениям математической физики. М.: Наука, 1968.

7. Камке Э. «Справочник по дифференциальным уравнениям в частных производных»

первого порядка. М.: Наука, 1966.

8. Курант Р. «Уравнения с частными производными». Перевод с англ. М.: Мир, 1964.

9. Ладыженская О.А. «Краевые задачи математической физики». М.: Наука, 1973.

10. Ландис Е. М. «Уравнения второго порядка эллиптического и параболического типов».

М.: Наука, 1971.

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

http://mech.math.msu.su/department/diffur/coursesR.htm http://mech.math.msu.su/department/diffur/pde-first.pdf http://mech.math.msu.su/department/diffur/olympR.htm 8. Материально-техническое обеспечение дисциплины.

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

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

1. Цели освоения дисциплины Целями освоения дисциплины (модуля) «Теория чисел» являются:

1. Освоение методов исследования и решения уравнений в целых числах.

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

3. Изучение структуры колец классов вычетов по натуральному модулю и методов решения сравнений.

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

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

2. Место дисциплины в структуре ООП ВПО Данная дисциплина относится к вариативной части цикла профессиональных дисцип лин. Она является логическим продолжением базовых профессиональных курсов алгебры, математического анализа и комплексного анализа. С методической точки зрения она хорошо иллюстрирует общие теоремы и конструкции этих базовых дисциплин на примерах исследо вания свойств конкретных объектов – целых чисел. Знания, полученные после изучения этой дисциплины, позволяют ориентироваться в различных направлениях практической деятель ности, связанных с дискретной математикой, защитой информации, компьютерными наука ми. В качестве входных знаний необходимы основы алгебры, действительного и комплекс ного анализа. Изучение этой дисциплины может сопровождаться практикумом на ЭВМ по теоретико-числовым алгоритмам с использованием пакетов прикладных программ, таких как «Математика», и практикумом по параллельным методам решения теоретико-числовых за дач на кластерах.

3. Компетенции обучающегося, формируемые в результате освоения дисципли ны: ОК 6-14, ПК все, кроме 14, 24, 26, 28.

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

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

2) Уметь: Решать линейные и квадратичные уравнения от нескольких переменных, системы линейных уравнений в целых числах. Устанавливать разрешимость и находить ре шения алгебраических сравнений и систем сравнений, показательных сравнений. Находить системы первообразных корней. Вычислять значения арифметических функций. Строить ра циональные приближения к действительным числам.

3) Владеть: Современными теоретико-числовыми алгоритмами.

4. Структура и содержание дисциплины «Теория чисел».

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

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

1 Свойства простых и составных чисел. Решение линейных уравнениий. Теорема Че бышева об оценках количества простых чисел до заданной границы.

2 Дзета-функция Римана. Асимптотический закон распределения простых чисел.

3 Сравнения. Теорема Эйлера и малая теорема Ферма. Характеры. L-функции Дирихле.

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

4 Алгебраические числа.

5 Диофантовы приближения и трансцендентные числа.

5. Образовательные технологии: Лекции и семинары, возможно использование ЭВМ.

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

4 x 3 y 2 z 8t 36, 1. Решить в целых числах систему уравнений:

3x 4 y 7 z 5t 12.

x 2. Решить сравнение: 5 = 3 (mod 77).

3. Построить полную систему характеров по модулю 22.

4. Найти решения в целых числах уравнения: x2 – 57y2 = 1.

5. Разложить на неприводимые над GF(5) множители многочлен x4 +2x3 – 1.

6. Найти рациональное число, приближающее 23 с точностью меньшей 2 10 6, и имеющее знаменатель, меньший 400.

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

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

1. Виноградов И.М. «Основы теории чисел».

2. Галочкин А.И., Нестеренко Ю.В., Шидловский А.Б. «Введение в теорию чисел».

3. Нестеренко Ю.В. «Теория чисел», изд. Академия, 2008г.

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

1. Боревич З.И., Шафаревич И.Р. «Теория чисел», Любое издание.

2. Бухштаб А.А. «Теория чисел», Василенко О.Н. «Теоретико-числовые алгоритмы».

3. Прахар К. «Распределение простых чисел».

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

Возможно использование персональных компьютеров и пакетов программ Mathe matica, Maple, некоммерческий пакет SAGE (http://sagemath.org ) и др.

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

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

2. Место дисциплины в структуре ООП ВПО Курс входит в цикл профессиональных дисциплин в вариативной части обучения или может входить в базовую часть в качестве дисциплины, продолжающей курс «Теории веро ятности». Для освоения курса необходимы знания и навыки, приобретенные в результате предварительного обучения дисциплинам: математический анализ, функциональный анализ, алгебра, теория вероятностей.

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

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

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

1) ЗНАТЬ: МАТЕМАТИЧЕСКИЕ ОСНОВЫ СТАТИСТИЧЕСКОГО АНАЛИЗА ДАННЫХ:

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

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

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

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

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

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

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

2 Вариационный ряд выборки. Порядковые статистики и их распределения. Эмпириче ская функция распределения, ее свойства как функции распределения и как случайного эле мента. Сходимость эмпирической функции распределения к истинной функции распределе ния. Теорема Гливенко-Кантелли.

3 Теорема Колмогорова. Доказательства независимости статистики Колмогорова от ви да непрерывной функции распределения. Критерий Колмогорова для проверки гипотезы о данном непрерывном распределении.

4 Условное математическое ожидание и условное расп алгебры. Свойства условных математических ожиданий. Аналог формулы полной вероятно сти для условных математических ожиданий. Условная плотность распределения. Формула Байеса для плотностей.

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

6 Эффективные оценки в регулярном случае. Неравенство информации (Крамера-Рао).

Информация Фишера и ее свойства. Экспоненциальное семейство распределений и эффек тивные оценки.

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

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

9 Нормальное распределение в Rn. Эквивалентность различных определений и основ ные свойства. Распределение линейных и квадратичных форм от независимых нормально распределенных случайных величин. Лемма о независимости среднего арифметического и среднего квадратического для независимых нормальных случайных величин. Распределения хи-квадрат, Стьюдента и Фишера-Снедекора как распределения статистик в выборках из нормального распределения. Квантили распределения.

10 Интервальное оценивание параметров, доверительные интервалы. Построение точных и асимптотических доверительных интервалов. Точный и асимптотический доверительные интервалы для параметра биномиального распределения. Доверительные интервалы для па раметров нормального распределения. Доверительный интервал для квантилей.

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

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

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

14 Критерий «хи-квадрат» для гипотезы о полиномиальном распределении. Теорема об асимптотическом хи-квадрат распределении статистики Пирсона. Критерий «хи-квадрат»

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

15 Линейная регрессия. Метод наименьших квадратов для оценки коэффициентов ли нейной регрессии. Доверительный эллипсоид и проверка гипотез о коэффициентах регрессии в нормальной статистической модели.

16 Проверка статистических гипотез. Общие понятия: простые и сложные гипотезы, ста тистический критерий, критическая область, вероятность ошибок I и II рода, размер и мощность критерия, функция мощности критерия. Теорема Неймана-Пирсона: критерий от ношения правдоподобия как наиболее мощный критерий для проверки двух простых гипо тез. Понятие равномерно наиболее мощного критерия. Равномерно наиболее мощный крите рий для семейства распределений с монотонным отношением правдоподобия.

5. Образовательные технологии: Специализированный статистический практикум с применением пакета STATISTICA.

6. Оценочные средства для текущего контроля успеваемости, промежуточной ат тестации по итогам освоения дисциплины и учебно-методическое обеспечение само стоятельной работы студентов Контрольная работа № 1. Пусть X1,..., X n независимы и имеют нормальное распределение N (,1). Исследо вать несмещенность и состоятельность оценки Т ( Х ) X параметра.

2. Пусть X1,..., X n независимы и имеют равномерное распределение на отрезке a, b.

Найти оценку максимального правдоподобия для a и b.

3. Пусть X1,..., X n независимы и имеют гамма распределение,1. Доказать, что 1n T Х X i является эффективной оценкой.

n i 4. Пусть X1,..., X n независимы и имеют биномиальное распределение b(1, ), 0 1.

n Доказать, что T Х X i - полная достаточная статистика.

i 5. Найти количество информации Фишера для модели R(0,) – независимых одинако во равномерно распределенных на (0,) величин.

Контрольная работа № 1. Найти байесовскую оценку параметра нормальной модели N (,1) при условии, что априорным распределение параметра является нормальное распределение N (0,1).

2. Пусть X1,..., X n - независимы и одинаково равномерно распределены на (0,), 0.

Построить доверительный интервал для с помощью статистики Х n max X k.

k 3. Пусть X1,..., X n - независимы и имеют нормальное распределение N (,1). Построить доверительный интервал для с коэффициентом доверия, основанный на центральной статистике n ( X ).

4. Пусть - независимы и имеют плотность распределения X1,..., X n exp x, x, рx,. Построить наиболее мощный критерий размера для про 0, x верки гипотезы Н 0 : 0 при альтернативе Н1 : 1 0. Найти функцию мощности.

5. Пусть X1,..., X n - независимы и имеют распределение Пуассона П ( ). Построить рав номерно наиболее мощный критерий размера для проверки гипотезы Н 0 : 0 при аль тернативе Н1 : 0. Найти функцию мощности.

Задания для подготовки к зачету и экзамену.

1. Пусть X ( X 1,..., X n ) – выборка из генеральной совокупности независимых и n одинаково R(0,), распределенных случайных величин. Для оценки T x, n n x( n ) max xi, параметра найти математическое ожидание ET и дисперсию DT.

1i n Пусть X ( X 1,..., X n ) – выборка из генеральной совокупности независимых и 2.

1n X i 1. Дока одинаково N ( 1, 22 ) распределенных случайных величин и S n i зать, что несмещенной оценкой для функции k 2 при любом целом k 1 являет k n k n 2 Sk.

ся статистика k * 2 n k Найти количество информации Фишера для показательной модели с плотно 3.

e ( x ), x, стью распределения вероятностей p( x) x.

0, Пусть X ( X 1,..., X n ) – выборка из генеральной совокупности независимых и 4.

одинаково N (, 2 ) распределенных случайных величин. Найти достаточную стати стику для неизвестного параметра при условии, что – известно.

Доказать, что для распределения вероятностей N (, 2 ) с неизвестным пара 5.

метром достаточной статистикой для функции k является статисти n ка k k T k, где T 2 X i при любом k 1.

n 2 * nk i 2 2 Пусть X ( X 1,..., X n ) – выборка из генеральной совокупности взаимно неза 6.

висимых и одинаково N (, 2 ) распределенных случайных величин. Найти оценку максимального правдоподобия для функции g P c.

Пусть X ( X 1,..., X n ) – выборка из генеральной совокупности взаимно неза 7.

висимых и одинаково R 0, распределенных случайных величин. Построить по соответствующей выборке X ( X 1,..., X n ) оценку n максимального правдоподо бия. Найти закон ее распределения и убедиться в состоятельности в среднеквадрати ческом смысле.

Построить -доверительный интервал для параметра 0 1 в модели R(0, ) 8.

(равномерное распределение на [0, ]) по выборке X X1,..., X n. Построить крите рий уровня значимости для проверки 2-х гипотез: H0: 0 и H1: 0.

Пусть X X1,..., X n и Y Y1,..., Ym - две независимые выборки из распре 9.

делений 1,1 и 2,1 соответственно. Плотность распределения, опреде x 1e x / ляется следующим образом: f x, x 0, 0 и f ( x) 0, x 0. По строить центральный -доверительный интервал для отношения. Постро ить критерий уровня значимости для проверки гипотез: H0: 1 и H1: 1.

По выборке X X1,..., X n из распределения N, 2 построить двусторон 10.

ний - доверительный интервал для.

Пусть X X1,..., X n - выборка из распределения,1. Построить наиболее 11.

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

12. Пусть для распределения Коши с плотностью f x проверя 1 x ются гипотезы H0: 0 и H1: 1 на уровне значимости. Построить по одному наблюдению (п=1) критерий отношения правдоподобия S X : l X c. Найти в явном виде критическую область S и ошибки первого и второго рода при с= 2.

13. Пусть случайная величина имеет распределение n, причем число степеней свободы n неизвестно. Рассчитать приближенный двусторонний -доверительный интервал для n, соответствующий реализации 157. Воспользоваться нормальной аппроксимацией n распределения при большом n.

14. Пусть n, X, S 2 - соответственно длина, выборочные среднее и дисперсия вы борки из распределения N ( 1, 22 ). Показать, что с вероятностью результат сле дующего n 1 -го испытания находится в интервале X t S 2 (n 1) /(n 1).

15. Пусть X1,..., X n независимы и имеют распределение Пуассона П ( ). Постро ить центральный доверительный интервал с коэффициентом доверия, используя точечную оценку Т ( Х ) X.

16. Пусть X1,..., X n независимы и имеют гамма - распределение,2. Построить доверительный интервал для с коэффициентом доверия, основанный на цен n тральной статистике G Х, X i.

i Пусть X1,..., X n независимы и имеют биномиальное распределение b(1, ), 17.

0 1. Построить равномерно наиболее мощный критерий размера для провер ки гипотезы Н 0 : 0 при альтернативе Н1 : 0. Найти функцию мощности.

18. Пусть X1,..., X n независимы и имеют равномерное распределение на отрезке 0,. Построить равномерно наиболее мощный критерий размера для проверки гипотезы Н 0 : 0 при альтернативе Н1 : 0. Найти функцию мощности.

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

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

1. Боровков А.А., Математическая статистика. Оценка параметров. Проверка гипотез. М.:

Наука, 2. Козлов М.В., Прохоров А.В., Введение в математическую статистику, М.: МГУ, 3. Севастьянов Б.А., Курс теории вероятностей и математической статистики, М.: Наука, 4. Гнеденко Б.В., Курс теории вероятностей, М.: Наука, 5. Ивченко Г.И., МедведевЮ.И., Математическая статистика, М.: Наука, 1984.

6. Крамер Г., Математические методы статистики, изд.2, М.: Мир, 1975.

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

1. Ван дер Варден Б.Л., Математическая статистика, М.: ИЛ, 2. Леман Э., Проверка статистических гипотез, М.: Наука, 3. Леман Э., Теория точечного оценивания, М.: Наука, в) программное обеспечение и Интернет-ресурсы: пакеты программ STATISTIKA 5, 6 и 7 ПК с WIN XP 8. Материально-техническое обеспечение дисциплины.

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

Авторы: профессор кафедры математической статистики и случайных процессов А.М. Зубков, доцент кафедры А.В. Прохоров.

Рецензент: доцент кафедры математической статистики и случайных процессов М.В. Козлов.

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

1. Цели освоения дисциплины «Методы оптимизации».

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

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

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

3. Компетенции обучающегося, формируемые в результате освоения дисципли ны: ОК-6, ОК-7, ОК-11, ПК-2, ПК-3, ПК-4, ПК-5, ПК-6, ПК-7, ПК-8, ПК-9, ПК-10.

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

1) Знать: общую теорию экстремальных задач и методы оптимизации.

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


3) Владеть: методами решения экстремальных математических задач.

4. Структура и содержание дисциплины «Методы оптимизации».

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

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

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

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

3. Приложение принципа Лагранжа к задачам вариационного исчисления.

4. Выпуклые задачи.

5. Условия второго порядка для слабого и сильного минимума в простейшей задаче 6. Принцип максимума Понтрягина 5. Образовательные технологии. Лекции, семинарские занятия, контрольные рабо ты, коллоквиумы, зачет, экзамен.

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

Варианты коллоквиума:

Вариант 1. Теорема об обратном отображении.

2. Лемма о необходимых условиях в задаче Больца.

3. Решить задачу 0 (x’) dt inf, x(0)=0, 0 x sin t dt = 1.

Вариант 1. Теорема о правиле множителей Лагранжа.

2. Лемма о замкнутости образа.

3. Решить задачу 1 0 ((x’’) +48x) dt inf, x(0)=0, x(1)=1.

Варианты контрольных работ:

Контрольная работа 1.

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

Вариант 1.

1. Найти производную отображения t F : C[0,1] C 1[0,1], F ( x)(t ) x(0) sin x( )d 2. Решить задачу Больца:

(x 4 x 2 8 x e 2t )dt 3x 2 (0) 2 x 2 (1) extr 3. Решить задачу Лагранжа:

u dt inf, x u, x(0) 0, x(1) sh1, x(1) ch1 sh x Вариант 2.

1. Найти производную отображения F : C [0,1] C[0,1], F ( x)(t ) x(1) chx(t ) cos x( )d 2. Решить задачу с подвижным концом:

T x dt extr, x(0) 0, T x(T ) 1 3. Решить задачу Лагранжа:

/ u dt x 2 (0) inf, x u, x( / 2) 0, x( / 2) x Контрольная работа 2.

Примечание: В первой задаче варианта 1 требуется найти субдифференциал функций, используя теоремы о субдифференциале гладкой функции, неравенство Коши – Буняковско го, теоремы Моро – Рокафеллара и Дубовицкого – Милютина и утверждение о субдиффе ренциале функции, явно не зависящей от некоторых переменных. Если функция в некоторой точке не является гладкой, то субдифференциал в этой точке нужно изобразить как множест во в пространстве. Во второй задаче варианта 1 нужно рассматривать только те значения па раметров, при которых не выполнены необходимые условия или выполнены достаточные условия слабого (сильного) экстремума;

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

Вариант 1.

1. Найти в каждой точке субдифференциал функции x f ( x, y, z ) y2 z 2. Исследовать на слабый и сильный экстремум допустимые экстремали в задаче x exp( x)dt extr, x(0) 0, x(1) в зависимости от параметра.

3. Решить задачу оптимального управления xdt inf, 2, x(0) x(2) 0, x(2) x Вариант 2.

1. Найти (хотя бы одну) точку минимума в задаче 1 x 2 6 x 9 y 2 y 4 y x min 2 2. Найти допустимую экстремаль и исследовать ее на локальный экстремум с помощью теории поля:

x exp( x)dt extr, x(0) 0, x(1) ln 3. Решить задачу оптимального управления T inf, 2, x(0) x(T ) 0, x(0) 1, x(T ) x 7. Учебно-методическое и информационное обеспечение дисциплины.

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

1. Оптимальное управление. Под редакцией Н.П. Осмоловского и В.М. Тихомирова. М., МЦНМО, 1980.

2. Оптимальное управление. В.М. Алексеев, В.М. Тихомиров, С.В. Фомин. М., Наука, 1979.

3. Оптимальное управление и вариационное исчисление. М.И. Зеликин. М., УРСС, 2004.

4. Сборник задач по оптимизации. В.М. Алексеев, Э.М. Галеев, В.М. Тихомиров. М., Наука, 1984.

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

1. Геометрическая теория управления. А.А. Аграчев, Ю.Л. Сачков. М., Физматлит, 2005.

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

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

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

Целями освоения дисциплины (модуля) "Теория дискретных функций" являются:

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

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

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

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

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

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

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

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

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

4. Структура и содержание дисциплины "Теория дискретных функций".

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

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

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

Формулы. Представление функций формулами. Операция суперпозиции. Операция введения несущественной переменной. Замыкание множества функций. Замкнутые классы. Равенство функций. Эквивалентность формул. Элементарные функции и их свойства. Совершенная дизъюнктивная нормальная форма. Совершенная конъюнктивная нормальная форма.

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


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

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

мощность семейства замкнутых классов булевых функций.

Классы сохранения множеств функций и их свойства. Теорема о представле нии замкнутых классов в терминах сохранения множеств. Описание предполных классов в P2 в терминах сохранения множеств функций. Эквивалентные преобразования формул в P2.

Тождества, классы тождеств, аксиомы, схемы аксиом, эквивалентная подстановка, эквива лентное преобразование, полные системы тождеств. Пример конечной полной системы для класса тождеств над множеством { 0, 1, xy, x + y }. Достаточное условие аксиоматизируемо сти. Теорема Линдона о существовании полных систем тождеств для классов тождеств над конечными множествами булевых функций (без доказательства).

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

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

Алгоритм построения множества [A]x,y. Алгоритм построения предполных классов в Pk. Алгоритм распознавания полноты конечных систем функций в Pk. Сущест венные функции. Лемма о трех наборах. Лемма о существенной функции.

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

единственность представления для случая простых k.

Пример замкнутого класса в P3, не имеющего базиса. Пример замкнутого класса в P3, имеющего счетный базис. Мощность семейства замкнутых классов в Pk.

Эквивалентные преобразования формул в Pk. Основные понятия. Пример Лин дона класса (D) тождеств над конечным множеством D функций в P7, не имеющего конеч ной полной системы тождеств. Система тождеств n = { A{1,2,3}, B1, Bm, Cm, m = 2, …, n } и е свойства. Канонический вид фор мул. Преобразование формул к каноническому виду. Полнота системы n для тождеств спе циального вида. Теорема Линдона (о неаксиоматизируемости класса (D)).

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

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

Лемма о выводимости из литералов (о выводимости формулы A, {0, 1}).

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

Графы. Основные понятия. Ориентированные графы. Лемма о нумерации вер шин в конечном ориентированном графе. Схемы из функциональных элементов в базисе {\/, &, –}. Основные понятия. Реализация функций схемами;

сложность схемы, сложность функ ции, функция Шеннона (функция L(n)). Простейшие методы синтеза. Реализация системы конъюнкций.

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

Минимальные схемы;

свойства минимальных схем. Лемма о числе минималь ных схем сложности h с одним выходом, реализующих функции от переменных x1, …, xn.

Мощностной метод получения нижних оценок сложности. Лемма Шеннона. Нижняя оценка для функции L(n). Асимптотически точная формула для функции L(n).

Конечные автоматы. Способы задания автоматов. Автоматные функции. Лем ма о преобразовании периодических последовательностей автоматными функциями. Приме ры неавтоматных функций. Формулы над множеством автоматных функций. Реализация функций формулами. Замыкание множества автоматных функций относительно операции суперпозиции. Множество PA. Теорема об отсутствии в PA при |A| 2 конечной полной сис темы автоматных функций.

Схемы из функциональных элементов и элементов задержки (схемы с обрат ными связями). Реализация функций схемами. Теорема о реализации автоматных функций из P{0,1} схемами из функциональных элементов и элементов задержки. Эксперименты с авто матами. Эквивалентность состояний. Теорема Мура. Эквивалентность автоматов. Теорема об эквивалентности состояний автоматов. Сокращенный автомат. Построение сокращенного автомата.

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

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

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

Примеры задач повышенной трудности 1. Найти все замкнутые относительно операции суперпозиции множества F P2, ( 2) которые не содержат селекторную функцию e1 ( x1, x2 ).

2. Доказать, что [{m( x, y, z )}] S, где m( x, y, x) x( y z ) yz.

3. Пусть M множество всех монотонных функций алгебры логики. Доказать, что при всех натуральных n выполняются неравенства | M (n) | n C 2;

[ n/ 2] а) n | M (n) | 3C [n/ 2] б).

n 4. Пусть d p ( x1,...,x p ) xi x j, где дизъюнкция берется по всем i, j = 1, 2, …, p, таким, что i j. Доказать, что при всех p 2 выполняется соотношение d p [{x y, d p 1}].

Контрольная работа 6. Найти все минимальные полные подсистемы системы { f1, f 2, f 3, f 4, f 5 } булевых функций, где f1 ( x1, x2, x3, x4, x5 ) x1 ( x2 x2 ( x3 x4 x5 )) x1 x2 x3 ( x4 x5 ), f 2 ( x1, x2, x3, x4 ) 1 x4 ( x1 x2 x3 )(m( x1, x2, x3 ) ( x1 x2 )(x2 x3 )(x3 x1 )), f 3 ( x1, x2, x3 ) m( x1, x2, x3 ) ( x1 x2 ) ( x2 x3 ) ( x3 x1 ), f 4 ( x1, x2 ) x1 ( x1 x2 ) (здесь m( x1, x2, x3 ) x1 ( x2 x3 ) x2 x3 ) ) и определить принадлежность функций этой системы ко всем предполным классам в P2.

(Полная в P2 система A булевых функций называется минимальной, если для любой системы B A выполняется неравенство [ B] P2.) 7. Найти все предполные классы класса L и доказать, что любой базис класса L состо ит либо из двух, либо из трех функций.

(где L множество всех линейных функций алгебры логики.) 8. Пусть F множество всех булевых функций f ( x1,...,xn ), таких, что при некотором i, 1 i n, выполняется равенство f ( x1,...xn ) xi f ( x1,...,xi 1,0, xi 1,...,xn ), n = 1, 2, ….

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

b) Доказать, что F [{x y}].

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

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

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

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

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

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

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

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

Функции алгебры логики 70. Post E. L. Introduction to a general theory of elementary propositions // Amer. J. Math, Vol. XLIII, No. 3, July, 1921. – P. 163–185 (см. также: Post E. L. Introduction to a general theory of elementary propositions. – In the book: Solvability, provability, defi nability: the collected works of Emil L. Post / Martin Davis, editor. – Boston:

Birkhuser, 1994. – P. 21–43.).

71. Яблонский С. В., Гаврилов Г. П., Кудрявцев В. Б. Функции алгебры логики и классы Поста. – М.: Наука, 1966. – 120 с.

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

73. Угольников А. Б. О замкнутых классах Поста // Известия ВУЗов. Математика.

1988, No. 7 (314). – C. 79–88.

Функции k-значной логики 74. Яблонский С. В. Функциональные построения в k-значной логике // Труды матем.

ин-та АН СССР, 1958. Т. 51. – С. 5–142.

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

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

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

Эквивалентные преобразования формул, исчисление тождеств 78. Линдон Р. К. Тождества в конечных алгебрах. – В кн. Кибернетический сб. Вып.

1. – М.: ИЛ, 1959. – С. 246–248.

79. Линдон Р. К. Тождества в двузначных исчислениях. – В кн. Кибернетический сб.

Вып. 1. – М.: ИЛ, 1959. – С. 234–245.

80. Мурский В. Л. Существование в трехзначной логике замкнутого класса с конеч ным базисом, не имеющего конечной полной системы тождеств // Докл. АН СССР. 1965. 163, No. 4. – C. 815– 818.

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

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

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

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

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

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

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

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

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

90. Лавров И. А., Максимова Л. Л. Задачи по теории множеств, математической логи ке и теории алгоритмов. – М.: Наука, 1975. – 240 c.

91. Post E. L. Two-valued iterative systems of mathematical logic // Annals of Math. Stu dies. – Princeton: Princeton Univ. Press, 1941. – 122 p. (см. также: Post E. L. Two valued iterative systems of mathematical logic. – In the book: Solvability, provability, definability: the collected works of Emil L. Post / Martin Davis, editor. – Boston:

Birkhuser, 1994. – P. 249–374.).

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

– 312.

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

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

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

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

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

Рекомендуемые профили подготовки бакалавров:

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

Список разработчиков ПООП, экспертов Разработчики:

Учебно-методический совет по математике и механике УМО по классическому универ ситетскому образованию Волгоградский государственный университет, Факультет математики и информационных технологий Декан, профессор А.Г. Лосев Казанский (приволжский) федеральный университет, Механико-математический факультет, Декан, профессор С.Р. Насыров Кемеровский государственный университет, Математический факультет, Декан, профессор Н.Н. Данилов Кубанский государственный университет, Факультет математики и компьютерных наук И.О. декана, профессор С.П. Грушевский Московский государственный университет, Механико-математический факультет, И.О. декана, профессор В.Н. Чубариков Московский государственный университет, механико-математический факультет, Зам. декана, профессор И.Н. Молодцов Московский государственный университет, механико-математический факультет, Зам. декана, доцент Т.Ю. Семенова Нижегородский государственный университет Механико-математический факультет, Декан, профессор А.К. Любимов Новосибирский государственный университет, Механико-математический факультет, Декан, профессор С.С. Гончаров Самарский государственный аэрокосмический университет, кафедра теоретической механики, зав. кафедрой, профессор В.С. Асланов Саратовский государственный университет Механико-математический факультет, Декан, доцент А.М. Захаров Ставропольский государственный университет, Физико-математический факультет, Декан, профессор И.М. Агибова Удмуртский государственный университет Математический факультет, Декан, доцент Н.Н. Петров Уральский государственный университет, Математико-механический факультет, Декан, доцент М.О. Асанов Эксперты:

Геофизический центр РАН директор А.Д. Гвишиани

Pages:     | 1 |   ...   | 2 | 3 ||
 





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

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