И I курса магистратуры основные требования к письменной работе изложение
|
Скачать 29.63 Kb.
|
| ТЕМЫ КОЛЛОКВИУМА № DM-12 годового курса "ДИСКРЕТНАЯ МАТЕМАТИКА" для студентов V курса и I курса магистратуры ОСНОВНЫЕ ТРЕБОВАНИЯ К ПИСЬМЕННОЙ РАБОТЕ Изложение темы должно быть разделено на две части. Первая часть представляет собой конспект лекции на заданную тему. Объем этого конспекта должен быть 8–10 страниц печатного текста в формате А4 (шрифт – 12pt). Вторая часть должна быть разработкой практического занятия на заданную тему. Она должна содержать 10 задач четырех уровней сложности вместе с предполагаемыми решениями: (*) 3 простых задачи на освоение материала лекции; (**) 3 чуть более сложных задачи; (***) 2 сложных задачи и (****) 2 трудных задачи в заключение. Нумерация задач – общая. Объем этой второй части должен быть 8–10 страниц печатного текста в формате А4. Форма представления работы – напечатанный текст с титульным листом, оглавлением и полным списком использованной литературы, в том числе интернет-источники. На титульном листе обязательно ФИО студента, группа, номер и название темы, стандартная шапка НГУ и год. Срок представления работы – 15 марта 2011 г. Список тем и ссылки на литературу (1) Системы троек Штейнера. Теоремы существования и методы построения. [4], [12], [13], [15]. (2) Исчисление сумм: Суммы и рекуррентности. Преобразование сумм. Кратные суммы. Общие методы суммирования. [1], [2], [4]-[6], [9]. (3) Числа Эйлера первого и второго порядков. Треугольники Эйлера. Рекуррентные формулы. Связь натуральных степеней и последовательных биномиальных коэффициентов. Дополнительные тождества. [1], [2], [4]-[6], [9], [13]. (4) Вершинная, реберная и циклическая связность. Теоремы Менгера, Коцига и их следствия. Множества сочленения и разрезы. [2], [3], [6]-[8], [10], [11], [13], [14]. (5) Гармонические числа. Гармоническое суммирование. [1], [2], [4], [6], [9], [11]. (6) Числа Бернулли. [1], [2], [4], [6], [9], [13]. (7) Алгоритмы порождения основных комбинаторных объектов: перестановки, подмножества, разбиения чисел, разбиения множеств, произведения пространств. [1], [2], [4], [6], [9], [11]. (8) Теорема Пойа, лемма Бернсайда. [2]-[5], [11]-[15]. (9) Перманенты. [4], [5], [12], [13], [15]. (10) Плоские и планарные графы. Формула Эйлера. Теорема Понтрягина–Куратовского (конструктивное и неконструктивное доказательства). [2], [3], [8], [10], [11], [14]. (11) Частичный порядок и частично упорядоченные множества. Диаграмма Хассе. Структуры. Цепи и антицепи. Примеры частично упорядоченных множеств и их свойства. Теорема Дилворта. [1], [2], [4]-[6], [9], [12], [13], [15]. (12) Блок-схемы и конечные геометрии. [4], [5], [12], [13], [15]. (13) Деревья и ордеревья. Свойства деревьев. Цикломатическое число, каркасы, фундаментальные циклы. Формула Кэли и код Прюфера. [1]–[4], [6], [7]–[11], [13], [14]. (14) Системы ортогональных латинских квадратов. [4], [5], [12], [13], [15]. ЛИТЕРАТУРА 1. Грэхем Р., Кнут Д., Паташник О., Конкретная математика: Основание информатики. М.: Мир, 1998. 2. Евстигнеев В.А., Мельников Л.С., Задачи и упражнения по теории графов и комбинаторике. Новосибирск: НГУ, 1981. 3. Зыков А.А., Теория конечных графов: I. Новосибирск: CО Наука, 1969. 4. Кнут Д., Искусство программирования на ЭВМ. М.: Мир, т. 1: 1976, т. 2:1977, т. 3: 1978. 5. Комбинаторный анализ. Задачи и упражнения: Учебное пособие / Под ред. Рыбникова К.А./ М.: Наука, 1982. 6. Косточка А.В., Соловьева Ф.И., Дискретная математика: Учебное пособие. Часть I. Новосибирск: НГУ, 1997. 7. Кристофидес Н., Теория графов. Алгоритмический подход. М.: Мир, 1978. 8. Лекции по теории графов./Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И./ М.: Наука, 1991. 9. Липский В., Комбинаторика для программистов. М.: Наука, 1988. 10. Оре О., Теория графов. _ М.: Наука, 1968. 11. Рейнгольд Э., Нивергельт Ю., Део Н. Комбинаторные алгоритмы. Теория и практика. М.: Мир, 1980. 12. Рыбников К.А. Введение в комбинаторный анализ. М: МГУ, 1985. 13. Сачков В.Н. Введение в комбинаторные методы дискретной математики. М.: Наука, 1982. 14. Харари Ф., Теория графов. _ М.: Мир, 1973. 15. Холл М. Комбинаторика. М.: Мир, 1970. |
