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

Студенческая жизнь в МФТИ насыщенна и разнообразна. Студенты активно совмещают учебную деятельность с занятиями спортом, участием в культурно-массовых мероприятиях, а также их организации. Администрация института всячески поддерживает инициативу и заботится о благополучии студентов. Так, ведется непрерывная работа по расширению студенческого городка и улучшению быта студентов.

Адрес e-mail:

Дискретный анализ (1 семестр)

МИНИСТЕРСТВО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ

Государственное образовательное учреждение

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

Московский физико-технический институт

(государственный университет)

 

                                                УТВЕРЖДАЮ

                                             Проректор по учебной работе

                                               Ю.А. Самарский

                                                  16 июня 2003 г.

 

ПРОГРАММА

по курсу: ДИСКРЕТНЫЙ АНАЛИЗ

по направлению 511600

факультет        ФУПМ

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

курс I

семестр I

лекции - 32 час.                 Экзамен - нет

семинары - 32 час.                 Зачет с оценкой -1 семестр

лабораторные занятия – нет    Самостоятельная работа -  2 часа в неделю

ВСЕГО ЧАСОВ    64

 Программу и задание составили: академик РАН, проф.Ю.И. Журавлев,

                                                          д.ф.-м.н., проф. Ю.А. Флеров

                                                          к.ф.-м.н., доц. О.С. Федько

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

Заведующий кафедрой                                 С.А. Гуз

 

I . Элементы алгебры логики

1. Функции алгебры логики. Табличное задание функций. Элементарные функции, их свойства, таблица операций, коммутативность, ассоциативность, дистрибутивность элементарных функций.

2. Формулы и функции алгебры логики. Теоремы о разложении функций по одной и нескольким переменным. Завершенная дизьюнктивная нормальная форма.

3. Функциональная полнота систем функций алгебры логики. Замкнутые классы. Пять предполных замкнутых классов Т 0, T 1, L, S, М. Теорема о функции, двойственной к суперпозиции. Критерий функциональной полноты систем функций алгебры логики (теорема Поста). Основная лемма. Лемма о несамодвойственной функции. Лемма о немонотонной функции. Лемма о нелинейной функции. Следствия из критерия полноты.

                  II . Комбинаторные методы дискретной математики

1. Предмет комбинаторики. Комбинаторные задачи о числе функций, слов в алфавите и размещений объектов по ячейкам при различных ограничениях (mn , [m] n , [m] n , [m] n /n!, Pn ).

2. Числа Стирлинга первого рода, рекуррентное соотношение для них.

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

4. Число разбиений n объектов на m классов. Числа Стирлинга второго рода. Рекуррентное соотношение для S(n , k) Разложение степени х n в базисе {[x] k }. Числа Белла разбиений множества на непересекающиеся подмножества, рекуррентное соотношение для чисел Белла.

5. Логические методы комбинаторного анализа. Принцип включений-исключений. Задача о числе беспорядков, задача о числе сюрьективных отображений конечных множеств. Системы представителей множеств. Системы различных представителей (с.р.п.). Необходимое и достаточное условие существования с.р.п. Алгоритм построения с.р.п. для заданной системы множеств. Системы одновременных представителей.

III . Элементы теории графов

1. Определение графа. Неориентированные и ориентированные графы. Изоморфные графы. Полные ориентированные и неориентированные графы. Локальные степени вершин. Число вершин нечетной степени в конечном графе. Машинное представление графов. Матрица инциденций. Матрица смежности (вершин). Список пар, список инцидентности.

2. Пути (маршруты, цепи) в графе, простые пути, циклы. Связность. Теорема о связности двух вершин, имеющих нечетную локальную степень. Максимальное число ребер в графе с n вершинами и k-связными компонентами.

3. Деревья. Связанность любых двух вершин дерева единственным простым путем. Изображение дерева. Концевые (висячие) вершины и концевые (висячие) ребра дерева. Теорема о числе различных деревьев с данными n вершинами.

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

5. Нахождение кратчайших путей в ориентированном графе от фиксированной вершины (случай неотрицательных весов ребер).

Список литературы

1. Журавлев Ю.И., Флеров Ю.А. Дискретный анализ. Ч. 1: Учебное пособие. – М.: МФТИ, 1999.

2. Дискретная математика и математические вопросы кибернетики / Под ред. С.В. Яблонского, О.В. Лупанова. – Т. 1. – М.: Наука, 1974.

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

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

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

6. Липский В. Комбинаторика для программистов. – М.: Мир, 1988.

7. Рыбников К.А. Введение в комбинаторный анализ. – М.: МГУ, 1972.

8. Уилсон Р. Дж. Введение в теорию графов. – М.: Мир, 1977.

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

   10. Холл М. Комбинаторика. – М.: Мир, 1970.

   11. Новиков Ф.А. Дискретная математика для программистов. – СПб.: Питер, 2001.

ЗАДАНИЕ

Номера задач указаны по «Сборнику задач по дискрет­ному анализу. Комбинаторика. Элементы алгебры логики. Теория графов» Ю.И. Журавлев, Ю.А. Флеров, О.С. Федько, Т.М. Дадашев. – М.: МФТИ, 2000.

Глава 1

1.10, 1.18, 2.12(1,4), 2.10, 2.18 (а, б), 2.21, 2.35, 2.46(2,3,5,6,7), 3.5(2), 3.9(6), 3.10(1), 3.11, 3.13(1, 2, 4), 3.16, 4.5, 4.6, 4.7, 4.12, 4.23, 4.24.

Глава 2

1.12, 1.19,1.20, 1.28, 2.4, 2.11, 2.12, 2.18, 2.26, 2.34.

Срок сдачи задания - первая неделя декабря.

 

 

Если вы заметили в тексте ошибку, выделите её и нажмите Ctrl+Enter.

© 2001-2016 Московский физико-технический институт
(государственный университет)

Техподдержка сайта

МФТИ в социальных сетях

soc-vk soc-fb soc-tw soc-li soc-li
Яндекс.Метрика