Скачать 191.62 Kb.
|
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования «Нижегородский государственный университет им. Н.И. Лобачевского» Радиофизический факультет Кафедра математики УТВЕРЖДАЮ Декан радиофизического факультета ____________________Якимов А.В. «18» мая 2011 г. Учебная программа Дисциплины Б3.Б2 «Дискретная математика» по направлению 010300 «Фундаментальная информатика и информационные технологии» Нижний Новгород 2011 г. 1. Цели и задачи дисциплины Дисциплина «Дискретная математика» обеспечивает приобретение знаний и умений в соответствии с государственным образовательным стандартом, содействует формированию мировоззрения и системного мышления. Целью преподавания дисциплины «Дискретная математика» является подготовка специалистов к деятельности в сфере разработки, исследования и эксплуатации информационных систем. 2. Место дисциплины в структуре программы бакалавра Дисциплина «Дискретная математика» относится к дисциплинам базовой части профессионального цикла основной образовательной программы по направлению 010300 «Фундаментальная информатика и информационные технологии», преподается в 1 и 2 семестрах. 3. Требования к уровню освоения содержания дисциплины В результате освоения дисциплины «Дискретная математика» формируются следующие компетенции:
В результате изучения дисциплины студенты должны:
4. Объём дисциплины и виды учебной работы: Общая трудоемкость дисциплины составляет 6 зачетных единиц, 216 часов.
5. Содержание дисциплины 5.1. Разделы дисциплины и виды занятий
5.2. Содержание разделов дисциплины Раздел 1. Введение в дискретную математику. Направления исследований в дискретной математике. Виды теорем и способы их доказательств. Принцип математической индукции. Раздел 2. Основы теории множеств. 2.1. Начальные понятия теории множеств. Понятие множества. Отношения между множествами. Диаграммы Венна-Эйлера. Законы алгебры множеств. Обобщенные тождества алгебры множеств. 2.2. Мощность множеств. Конечные и счетные множества. Множества мощности континуума. Теорема Кантора о несчетности. Подмножества, разбиения и покрытия. Булеан и его мощность. 2.3. Введение в реляционную алгебру. Прямое произведение множеств и его свойства. Мощность прямого произведения n множеств. Бинарные отношения, их виды и свойства. Биективное отображение. Специальные бинарные отношения: отношение эквивалентности и отношение порядка. Диаграмма Хассе. Раздел 3. Комбинаторика. 3.1. Комбинаторные конфигурации. Правила суммы и произведения. Перестановки. Сочетания (с повторениями и без повторений). Размещения (с повторениями и без повторений). 3.2. Разбиения. Включения и исключения. Число разбиений множества. Полиномиальный коэффициент. Формула включений и исключений. 3.3. Биномиальные коэффициенты. Бином Ньютона. Свойства биномиальных коэффициентов. Треугольник Паскаля. Раздел 4. Алгебра логики. 4.1. Функции и формулы алгебры логики. Логические (булевы) функции, их количество. Существенные и фиктивные переменные. Элементарные булевы функции от одной и двух переменных. Законы алгебры логики. Принцип двойственности. Дизъюнктивная и конъюнктивная нормальные формы. Полиномы Жегалкина. 4.2. Полнота и замкнутость. Важнейшие замкнутые классы логических функций. Функционально полная система логических функций. Связь понятий полноты и замкнутости. Критерий Поста полноты системы булевых функций. Понятие базиса и предполного класса в системе булевых функций. Следствия из теоремы Поста. 4.3. Приложения булевых функций. Логические схемы и их реализация с помощью булевых функций. Синтез схем из функциональных элементов. Раздел 5. Введение в математическую логику. Понятие высказывания. Логические связки. Формулы логики высказываний. Равносильность формул. Тождественно-истинные, выполнимые и тождественно-ложные формулы. Правильные рассуждения. Проблема разрешимости в логике высказываний и методы ее решения. Алгоритм редукций определения тождественной истинности формулы логики высказываний. Раздел 6. Начальные понятия теории графов. Определение графа. Области применения графов. Способы задания неориентированных графов. Основная теорема теории графов и ее следствие. Виды неориентированных графов. Дополнение к графу. Подграфы и их виды. Операции над графами. Маршруты, цепи и циклы в графе. Свойства маршрутов и циклов. Связность графов. Матрица связности (достижимости). Число маршрутов в неориентированном графе. Критерий связности графа. Мосты и разделяющие вершины. Признаки моста. Вершинная и реберная связности. N-связные графы. Оценка числа ребер графа через число вершин и число компонент связности. Расстояния в графе. Диаметр, радиус и центр графа. Изоморфизм графов. Алгоритм решения задач на определение изоморфных графов. Теоремы о количестве помеченных графов с р вершинами и с р вершинами и q ребрами. Асимптотическая формула Пойа для числа непомеченных графов. Раздел 7. Неориентированные графы с циклами и без циклов. 7.1. Деревья. Двудольные графы. Теоремы о количестве ребер в связных графах с циклами и без циклов. Неориентированные (свободные) деревья. Кодирование деревьев. Матричная теорема Кирхгофа о деревьях. Количество помеченных деревьев с р вершинами. Основные свойства свободных деревьев. Двудольные графы. Критерий двудольности графа. k-дольные графы. 7.2. Эйлеровы и гамильтоновы графы. Эйлеровы и полуэйлеровы графы. Критерий существования в графе эйлеровой цепи. Теорема Эйлера об эйлеровых графах (критерий эйлеровости графа). Задача о кенигсбергских мостах. Теорема об оценке числа эйлеровых графов. Гамильтоновы графы. Теорема об оценке числа гамильтоновых графов. Задача коммивояжера. Сравнение задач отыскания эйлеровых и гамильтоновых циклов. Достаточные условия гамильтоновости графа (теоремы Дирака, Оре и Хватала), необходимое условие гамильтоновости графа (о разделяющих вершинах графа). 7.3. Планарные графы. Раскраска графов. Планарные графы. Подразбиение и стягивание ребер. Теоремы Понтрягина-Куратовского и Вагнера. Теорема об оценке числа планарных графов. Теорема о количестве граней связного планарного графа и ее следствие. Вершинная и реберная раскраски графов. Хроматическое число и хроматический индекс, их оценки. Проблема четырех красок. История ее возникновения и решения. Теорема о 5 красках. Раздел 8. Ориентированные графы. Ориентированные графы и их виды. Основная теорема теории графов для орграфов. Связь с бинарными отношениями. Способы задания ориентированных графов. Маршруты, пути и контуры в орграфе. Свойства путей и контуров. Количество ориентированных маршрутов в орграфе. Критерий существования контура в орграфе. Связность орграфов и ее виды. Компоненты сильной связности орграфа и их свойства. Конденсация орграфа. Выделение компонент сильной связности в орграфе. Ориентированные, упорядоченные и бинарные деревья. Их сравнительный анализ и области применения. Свойства ориентированных деревьев. Раздел 9. Экстремальные задачи и алгоритмы на графах. 9.1. Экстремальные задачи на графах. Независимое множество вершин. Задача о восьми ферзях. Вершинное число независимости и его оценки. Алгоритм построения независимого множества вершин. Понятие клики графа. Взаимосвязь задач о клике и о независимом множестве вершин. Независимое множество ребер (паросочетание). Реберное число независимости. Построение наибольшего паросочетания методом чередующихся цепей. Покрывающие множества вершин и ребер. Теоремы о связи чисел независимости и покрытий в общем случае и для двудольного графа. Сепараторы и разрезы. Теорема Менгера в вершинной форме и ее модификации. Задача о назначениях и теорема Холла. 9.2. Алгоритмы на графах. Обходы графов. Алгоритмы поиска в ширину и глубину. Алгоритм выделения эйлерова цикла или эйлеровой цепи в связном мультиграфе. Алгоритм поиска минимального маршрута в ненагруженном (ор)графе. Построение остова минимального веса. Алгоритмы Прима и Краскала. Задача о нахождении минимального маршрута в нагруженном орграфе. Алгоритм Дейкстры. Алгоритм Флойда нахождения кратчайших путей между всеми парами вершин в нагруженном орграфе. 5.3. Темы практических занятий.
6. Лабораторный практикум Не предусмотрен. 7. Учебно-методическое обеспечение дисциплины 7.1. Рекомендуемая литература а) основная литература:
б) дополнительная литература:
8. Вопросы для контроля
9. Критерии оценок
10. Примерная тематика курсовых работ и критерии их оценки Не предусмотрены. Программа составлена в соответствии с Федеральным государственным образовательным стандартом высшего профессионального образования по направлению 010300 «Фундаментальная информатика и информационные технологии» Автор программы: _________________ Павлов И.С. Программа рассмотрена на заседании кафедры 18 марта 2011 г. протокол № 10-11-04 Заведующий кафедрой _________________ Дубков А.А. Программа одобрена методической комиссией факультета 11 апреля 2011 года протокол № 05/10 Председатель методической комиссии_________________ Мануилов В.Н. |
Радиофизический факультет Дисциплины 02 «Полупроводниковые лазеры в оптической связи и измерительных системах» | Радиофизический факультет Дисциплины р12 «Взаимодействие электронных потоков с электромагнитными полями» | ||
Радиофизический факультет Данная дисциплина относится к общепрофессиональным дисциплинам федерального компонента, преподается в 9 семестре | Радиофизический факультет Данная дисциплина относится к дисциплинам специализации федерального компонента, преподается в 6 и 7 семестрах | ||
Радиофизический факультет ... | Радиофизический факультет Цель курса – сформировать у студентов представления о квантовомеханических закономерностях, лежащих в основе современной физики и... | ||
Радиофизический факультет Содержание дисциплины направлено на расширение знаний электродинамики плазменных процессов, обусловленных ионизационной нелинейностью... | Радиофизический факультет Цель изучения дисциплины состоит в освоении студентами методологии и технологии моделирования (в первую очередь компьютерного) информационных... | ||
Радиофизический факультет Содержание дисциплины направлено на углубленное изучение методов физики твердого тела, знакомство с некоторыми современными проблемами... | Программа по формированию навыков безопасного поведения на дорогах... Факультет русской филологии и журналистики. Факультет истории и юриспруденции. Факультет татарской и сопоставительной филологии.... | ||
Радиофизический факультет Дисциплина базируется на знаниях студентов, приобретенных в курсах общей физики, полупроводниковой электроники, электродинамики и... | Радиофизический факультет Большое внимание в курсе уделено сопутствующему математическому описанию указанных процессов и их использованию для расчета основных... | ||
Радиофизический факультет Дисциплина «Физическая электроника» относится к дисциплинам базовой части профессионального цикла основной образовательной программы... | Радиофизический факультет Основное внимание при чтении лекций уделяется приближенным методам решения задач распространения и рассеяния скалярных волн в средах... | ||
Радиофизический факультет Содержание дисциплины направлено на изучение разделов аналитической геометрии и высшей алгебры, необходимых для понимания других... | Радиофизический факультет Свч, квч и терагерцовых диапазонов частот. Рассматриваются процессы, происходящие в гетеропереходах, и объясняются основные причины... |