Программа дисциплины «Теория графов»
Скачать 250.75 Kb.
|
6Формы контроля знаний студентов
6.1Критерии оценки знаний, навыков Порядок формирования оценок по дисциплине Текущий контроль – домашняя контрольная работа в первом модуле, домашняя контрольная работа во втором модуле Итоговый контроль – устный экзамен в конце второго модуля. Результирующая оценка за текущий контроль рассчитывается следующим образом: Отекущий = 0,5·Ок/р + 0,5·Од/з Активность работы студентов на практических лабораторных занятиях учитывается в рабочей ведомости и составляет оценку Оаудиторная. Также учитывается оценка Осам. работа самостоятельной работы студентов: в практических домашних задачах на программирование оценивается функциональность и объем созданных программ; в самостоятельных докладах на семинарах – полнота и глубина освещения темы. Итоговая оценка по курсу выставляется по следующей формуле: Оитоговая = 0,4 Оэкзамен + 0,4·Отекущий + 0,2·Оаудиторная где Оэкзамен – оценка за работу непосредственно на экзамене. Таблица соответствия оценок по десятибалльной и пятибалльной системе
7Содержание дисциплиныТема 1. Основы комбинаторики 1.1. Перестановки и сочетания с повторениями и без повторений. Биномиальные коэффициенты. Формула бинома Ньютона. 1.2. Формула включения и исключения. Задача о беспорядках (шляпах). 1.3. Производящие функции. 1.4. Линейные рекуррентные последовательности. Формула для ее n-го числа. Применение к числам Фибоначчи. 1.5. Числа Каталана. Основная литература С. К. Ландо, Комбинаторика, НМУ, М., 1994 С. К.Ландо, Лекции о производящих функциях, МЦНМО, М., 2004 Ю. П. Шевелев, Дискретная математика, Лань, М., 2008 Г. П. Гаврилов, А. А. Сапоженко, Сборник задач по дискретной математике, Наука, М., 1977 Дополнительная литература М. Холл, Комбинаторика, Мир, М., 1970 Тема 2. Основы теории графов 2.1. Основные определения. Изоморфизм графов. Матрица смежности графа. 2.2. Эйлеровы и уникурсальные графы: определения и примеры. Критерии эйлеровости (теорема Эйлера) и уникурсальности графов. 2.3. Гамильтоновы графы. Примеры гамильтоновых и негамильтоновых графов. 2.4. Планарные графы. Теорема Эйлера о связи между числом вершин, ребер и граней связного плоского графа. Приложения к теории трехмерных выпуклых много-гранников. 2.5. Непланарность графов K5 и K3,3. Критерий планарности графа (теорема Понтря-гина—Куратовского. 2.6. Определение замкнутой топологической поверхности (без края и с краем). Ориентируемые и неориентируемые поверхности. Теорема о классификации замкнутых связных топологических поверхностей без края (формулировка). 2.7. Укладка графов на поверхности: теорема Кенига. Род графа. 2.8. Эйлерова характеристика топологической поверхности (определение и дока-зательство его корректности). Явное вычисление эйлеровой характеристики закнутых связных топологических поверхностей без края. 2.9. Теорема о неравенстве, связывающем эйлерову характеристику топологической поверхности с числами вершин, ребер и граней любого уложенного на эту поверхность без самопересечений связного графа. 2.10. Теорема о роде полного графа Kn и роде полного двудольного графа Kn,m (доказательство соответствующего неравенства) 2.11. Задача о раскраске карт. Хроматическое число. Теорема о явном виде хроматического числа замкнутой связной топологической поверхности без края (с доказательством соответствующего неравенства). Теорема о пяти красках. Основная литература Ф. Харари, Теория графов, Мир, М., 1973 И. Г. Болтянский, В. А. Ефремович, Наглядная топология, Наука, М., 1982 Ю. П. Шевелев, Дискретная математика, Лань, М., 2008 Г. П. Гаврилов, А. А. Сапоженко, Сборник задач по дискретной математике, Наука, М., 1977 Дополнительная литература О. Оре, Графы и их применение, Мир, М., 1965 З. Уилсон, Введение в теорию графов, Мир, М., 1977 Г. Рингель, Задача о раскраске карт, Мир, М., 1977 Тема 3. Основы теории сетей 3.1. Определение и примеры сети, ее пропускной способности, потока, его величины, разреза, пропускной способности разреза. 3.2. Алгоритм нахождения максимального потока и минимального разреза: теорема Форда—Фалкерсона (с доказательством). Основная литература Л. Форд, Д. Фалкерсон, Потоки в сетях, Мир, М., 1966 Дополнительная литература Т. Ху, Целочисленное программирование и потоки в сетях, Мир, М., 1974 Тема 4. Применение теории групп к перечислительным задачам теории графов 4.1. Группы преобразований, орбиты, стабилизаторы. Группы многогранников. Основная теорема кристаллографии (формулировка). 4.2. Связь между порядком конечной группы преобразований, числом элементов в ее орбите и порядком стабилизатора точки из этой орбиты. 4.3. Связь между стабилизаторами разных точек одной орбиты. 4.4. Формула Бернсайда и примеры ее применения к задачам о перечислении объектов. 4.5. Цикловой индекс конечной группы перестановок. Теорема Пойя о цикловом индексе. Применение этой теории к подсчету числа неизоморфных графов с n вершинами и m ребрами. Основная литература Ф. Харари, Теория графов, Мир, М., 1973 Дополнительная литература Э. Б. Винберг, Курс алгебры, Факториал Пресс, М., 2002 | ||||||||||||||||||||||||||||||||||||||||||
Похожие:
 | Рабочая учебная программа по дисциплине «Теория графов» для ооп специальности... Дисциплина «Теория графов» является дисциплиной цикла дпп. В. 00 – Дисциплины предметной подготовки (курсы по выбору) | | Теория графов Сейчас почти в любой отрасли науки и техники встречается применение графов. В физике при построении электрических схем, в химии и... |
 | Программа вступительных испытаний по дисциплине Дисциплина «Теория графов» является дисциплиной цикла дпп. В. 00 – Дисциплины предметной подготовки (курсы по выбору) | | Конспект занятия по факультативу Дисциплина «Теория графов» является дисциплиной цикла дпп. В. 00 – Дисциплины предметной подготовки (курсы по выбору) |
| Методические рекомендации по организации математических Дисциплина «Теория графов» является дисциплиной цикла дпп. В. 00 – Дисциплины предметной подготовки (курсы по выбору) | | Блок Основные этапы развития геометрии Дисциплина «Теория графов» является дисциплиной цикла дпп. В. 00 – Дисциплины предметной подготовки (курсы по выбору) |
| Урок геометрии в 7 классе общеобразовательной школы по теме «Основные... Дисциплина «Теория графов» является дисциплиной цикла дпп. В. 00 – Дисциплины предметной подготовки (курсы по выбору) | | Пояснительная записка. За душу каждого математика борются демон абстрактной... Элективный курс «Теория графов» (в рамках предпрофильной подготовки учащихся 9 класса) |
| Реферат по истории математики Научный проф. Верещагин Н. К Теория потоков в сетях – одно из современных направлений развития компьютерных наук в целом, и теории графов в частности. Многие... | | Рабочая программа дисциплины теория государства и права (наименование... ... |
| Рабочая программа учебной дисциплины общая экономическая теория (название... Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования | | Рабочая программа дисциплины Теория менеджмента: организационное поведение Дисциплина «Теория менеджмента: организационное поведение» входит в профессиональный цикл дисциплин ( Б. 3). Преподавание дисциплины... |
| Учебно-методическое пособие дисциплины «Общая теория налогов» Структура и объем дисциплины «Общая теория налогов» для направления 080100. 62 «Экономика», профиль «Налоги и налогообложение» | | Рабочая программа Учебной дисциплины управление персоналом для направления... Изучение дисциплины базируется на таких курсах, как «Экономическая теория», «Теория организации и организационное поведение», «Основы... |
| Программа дисциплины «Политическая теория» для направления 03200. 62 «Политология» «Политология» отделения прикладной политологии факультета менеджмента. Она определяет содержание и структуру учебной дисциплины «Политическая... | | Теория менеджмента 2 (организационное поведение) Изучение данной дисциплины базируется на следующих дисциплинах: «История аграрных отношений», «Экономическая теория» |
