Рабочая программа спецкурса
| Вид материала | Рабочая программа |
- Программа спецкурса для студентов заочного факультета Составители, 132.28kb.
- М. К. Аммосова биолого-географический факультет кафедра общей биологии рабочая программа, 55.7kb.
- Рабочая программа спецкурса «Синергетика» специальность 020600 «Культурология»; специальность, 163.8kb.
- Рабочая программа спецкурса «Методы органического синтеза» для специальности 020101, 103.25kb.
- О. Г. Лекаренко Вступительные замечания: Программа спецкурса, 149.36kb.
- Рабочая программа спецкурса "Педагогический процесс в национальной школе", 99.1kb.
- М. К. Аммосова мифология народов евразии программа спецкурса, 97.24kb.
- Рабочая программа спецкурса направление 020701 «Отечественная история» Специальность, 128.98kb.
- Рабочая программа спецкурса "Процессы образования и превращения органических молекул, 252.89kb.
- Учебная программа для специальности рабочий вариант: 1-310306, 148.59kb.
Приложение 3
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ
Национальный исследовательский университет
Новосибирский государственный университет
Механико-математический факультет
УТВЕРЖДАЮ
_______________________
«_____»__________________201__ г.
Рабочая программа спецкурса
Дискретный анализ и комбинаторика
Направление подготовки
Дискретная математика и математическая кибернетика, 01-01-09
Профиль подготовки
????
Квалификация (степень) выпускника
Магистр
Форма обучения
Очная
Новосибирск 2010
Аннотация рабочей программы
Курс читается на кафедре «Теоретическая кибернетика» ММФ НИУ НГУ и предназначен для изучения математических дисциплин комбинаторики и дискретного анализа, которые составляют значительную часть базового образования в области дискретной математики, математической кибернетики и теоретической информатики.
Преподавание дисциплины предусматривает следующие формы организации учебного процесса: лекции и самостоятельная работа студента.
Программой годового курса предусмотрена сдача в конце семестров зачётных заданий и решений предлагаемых на лекциях задач. Курс годовой 68 часов лекционных и 10 часов - приём экзаменов и заданий.
- Цели освоения курса
Курс предназначен для изучения математических дисциплин - комбинаторики и дискретного анализа, которые составляют значительную часть базового образования в области дискретной математики, математической кибернетики и теоретической информатики.
Основной целью освоения курса является ознакомление с базовыми понятиями и теоретическими методами указанных разделов дискретной математики, а также с современными исследованиями в этих областях и новыми задачами.
В первой части данного курса делается упор на задачи и методы комбинаторики. Во второй части читается в основном дискретный анализ.
2. Место курса в образовании по дискретной математике
В настоящем курсе объединены разделы дискретной математики, которые автор читал на ММФ на протежении многих лет отдельными годовыми курсами. Новизна и актуальность состоит в рассмотрении новых задач и знакомстве с современными исследованиями в области комбинаторики символьных последовательностей и языков с запретами (по разделу “Комбинаторика”) и дискретных метрических пространств, вопросов кодирования структурированной информации и дискретным моделям функционирования генных сетей (по разделу “Дискретный анализ”).
Изложение этих разделов оригинально, даются постановки новых задач.
Разделы дискретной математики, связанные с материалом курса.
Общая алгебра. Теория булевых функций. Математическая кибернетика. Теория графов. Теория автоматов. Теория функциональных систем.
3. Компетенции обучающегося, формируемые в результате освоения дисциплины
В результате освоения курса обучающийся должен знать основы и овладеть методами комбинаторики и дискретного анализа а также иметь представление о современных исследованиях в этих областях.
4. Структура и содержание дисциплины
- Комбинаторика перечисления и кодирование.
Системы счисления и кодирование натуральных чисел. Задачи о нумерациях подмножеств конечного множества. Коды Грея. Нумерации объектов в порядке минимального изменения. Алгоритмы построения нумерующих отображений. Отображения конечных множеств, их кодирование и подсчет числа. Кодирование деревьев. Число деревьев. Методы перечисления с помощью рекуррентных уравнений и производящих функций.
- Комбинаторика слов.
Некоторые классические символьные последовательности и способы их задания.
Универсальные слова. Задачи восстановления символьных последовательностей по их фрагментам. Коды без перекрытий. Комбинаторная сложность слов. Псевдослучайные последовательности. Символьные последовательности де Брейна и их число. Графы перекрытия подслов. Задачи быстрой сборки слов. Алгоритмы сборки. Аддитивная сложность символьных последовательностей и ее связь с задачами быстрого умножения и вычисления полиномов. Оценки аддитивной сложности индивидуальных последовательностей.
- Кодирование структурированной информации и вложения дискретных пространств.
Понятия близости, расстояния, метрики. Метрические пространства на множестве подмножеств, словах, символьных последовательностях. Реализация метрик графами.
Графы гиперкубов. Гиперкубовая архитектура вычислительных систем. Кодирования и вложения дискретных объектов в гиперкубы. Изоморфные и изометрические вложения. Дискретный аналог гомеоморфного вложения. Алгоритмы построения вложений графов в гиперкубы.
Применение методов вложения. Обобщённые коды Грея. Локально изометрическое кодирование табло. Сеточные графы вычислительных структур. Систолические вычисления. Суффиксные деревья. Префиксные коды. Вложения деревьев в гиперкубы.
4. Булевы функции и дискретные модели функционирования генных сетей.
Булевы функции, их число, способы задания. Представление формулами. Нормальные формы. Единственность совершенной и сокращённой форм. Представления многочленами Жегалкина. Полнота систем булевых функций. Теорема Поста. K-значные логические функции. Пороговые булевы функции. Способы задания. Сложность вычисления. Решения систем булевых уравнений. Схемы из функциональных элементов. Конечно-автоматные модели вычисления.
Ориентированные графы и сети. Достижимость вершин. Алгоритмы нахождения внутренне и внешне устойчивых множеств. Базы и ядра. Булевы методы в задачах теории графов. Алгоритм построения разрезов циклов. Логические производящие функции. Диаметр, радиус и центр в орграфах и алгоритмы их нахождения. Дискретные модели генных сетей. Анализ функционирования регуляторного контура генной сети.
6. Учебно-методическое обеспечение самостоятельной работы студентов. Оценочные средства для текущего контроля успеваемости, промежуточной аттестации по итогам освоения дисциплины
7. Учебно-методическое и информационное обеспечение дисциплины
а) основная литература:
1. Гаврилов Г.П. Сапоженко А.А. Сборник задач по дискретной математике. Третье издание. М. Наука, 2004.
2. Марченков С.С. Булевы функции. М. Физматлит. 2008.
3. Новиков Ф.А. Дискретная математика для программистов. 2000-2001
Рейнгольд Э., НивергельтЮ., ДеоН. Комбинаторные алгоритмы. М.:Мир,1980. (переиздана позже. ?)
4. Холл М. Комбинаторика. М.: Мир. 1970.
5. Яблонский С.В. Введение в дискретную математику. М.: Наука, 1979.
б) дополнительная литература:
1. Евдокимов А.А. Вложения графов в n-мерный булев куб и интервальное кодирование табло // Вестник Томского государственного университета. Приложение. 2006. № 17. С. 15-19.
2. Гоппа В.Д. Введение в алгебраическую теорию информации. М: Наука, 1995.
3. Емеличев В.А. и др. Лекции по теории графов. М.: Наука, ? издание. 200?.
4. Марков А.А. Введение в теорию кодирования. М.: Наука, 1982.
5. Нигматуллин Р.Г. Сложность булевых функций. Изд-во Казанского ун-та. 1983.
6. Рыбников К.А. Введение в комбинаторный анализ. М.: Изд-во МГУ, 1985.
8. Материально-техническое обеспечение курса
Ноутбук, медиа-проектор, экран.
Программное обеспечение для демонстрации слайд-презентаций.
Автор: Евдокимов Александр Андреевич
к.ф.-м.н., профессор ММФ НГУ
зав.лаб.ИМ СОРАН м.С.Л.Соболева.
Рецензент (ы)
Программа одобрена на заседании
(Наименование уполномоченного органа вуза (УМК, НМС, Ученый совет)
от ___________ года, протокол № ________