МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ
Государственное образовательное учреждение
высшего профессионального образования
«Алтайская государственная академия образования имени »
(ГОУВПО «АГАО»)
Физико-математический факультет
Кафедра математики и методики обучения математике
ПРИНЯТО Ученым советом Протокол № 7 от «29» июня 2010 г. | УТВЕРЖДАЮ Первый проректор ______________ «29» июня 2010 г. |
ПРОГРАММА УЧЕБНОЙ ДИСЦИПЛИНЫ
ОПД. Ф.10 ОСНОВЫ ДИСКРЕТНОЙ МАТЕМАТИКИ
Направление подготовки 050200.62 Физико-математическое образование
Профиль подготовки Математика
Степень (квалификация) бакалавр физико-математического образования
Форма обучения заочная
Составитель:
к. физ-мат. н., доцент кафедры математики и методики обучения математике
_________________
Бийск 2010
Программа составлена в соответствии с требованиями ГОС направлений и специальностей высшего профессионального образования, утвержденного Министерством образования и науки РФ от 01.01.2001 года и учебного плана по направлению подготовки 050200.62 Физико-математическое образование, утвержденного Ученым советом ГОУВПО «АГАО» (от 29 июня 2010 г., протокол № 8).
Распределение по семестрам
Номер семестра | Учебные занятия | Форма промежуточной - аттестации (зачет, экзамен) | ||||||
Общий объем | В том числе | |||||||
Аудиторные | Самостоятельная работа | Число курсовых проектов (работ), расчетных заданий | ||||||
Всего | Из них | |||||||
Лекции | Практ. | Лабор. | ||||||
Уст. | - | 12 | 8 | 4 | - | - | - | - |
1 | 150 | - | - | - | - | 138 | 1 | экзамен |
Всего | 150 | 12 | 8 | 4 | - | 138 | 1 к. р. | экзамен |
Основы дискретной математики
Множества и отношения. Операции над множествами. Функции. Основы математической логики. Математический язык. Булева алгебра. Элементы комбинаторики. Основные задачи комбинаторики и методы комбинаторных рассуждений. Элементы теории графов.
Программа обсуждена на заседании кафедры математики и методики обучения математике
Протокол № 1 от «29» августа 2010 г.
Заведующий кафедрой _____________________
1.1 ЦЕЛЬ И ЗАДАЧИ ДИСЦИПЛИНЫ
Цель дисциплины – формирование систематизированных знаний в области дискретной математики.
Задачи дисциплины:
─ изучение основных разделов дискретной математики: множества и отношения, элементы комбинаторики, основы математической логики, элементы теории графов;
─ овладение методами дискретной математики, наиболее употребительными при решении практических задач.
1.2 Место дисциплины в структуре ООП
Дисциплина «Основы дискретной математики» относится к циклу дисциплин общепрофессионального направления (ОПД. Ф.10).
Для освоения дисциплины студенты используют знания, умения и виды деятельности, сформированные в процессе изучения предмета «Математика» на предыдущем уровне образования и изучение смежных с курсом дисциплин таких как «Математика», «Математические модели, методы и теории».
Изучение данной дисциплины даст студенту базовые знания для дальнейшего изучения общеобразовательных дисциплин и дисциплин цикла предметной подготовки, таких как «Алгебра и теория чисел», «Числовые системы в школьном курсе математики».
1.3 Требования к результатам освоения дисциплины
В результате изучения дисциплины студент должен
знать:
· основы теории множеств: определения операций над множествами и их свойства;
· основные понятия теории отношений (бинарные отношения, эквивалентность, порядок, функция);
· основные правила комбинаторики, основные комбинаторные конфигурации (размещения, перестановки, сочетания без повторений и с повторениями) и формулы для подсчета их числа;
· основные понятия и законы алгебры логики и их применение к решению задач;
· основные понятия и факты теории графов.
уметь:
· находить результаты операций над множествами, иллюстрировать их и отношение включения между множествами на диаграммах Эйлера-Венна, доказывать равенства для множеств;
· определять свойства отношений между элементами множества; выделять отношение порядка и эквивалентности; строить фактор-множество по отношению эквивалентности;
· узнавать среди соответствий функции и определять их вид (сюръективные, инъективные, биекции);
· решать комбинаторные задачи с применением правил суммы и произведения, формулы включений и исключений, формул для подсчета числа размещений, перестановок, сочетаний;
· строить таблицы истинности для формул логики высказываний и с помощью них определять равносильность или неравносильность данных формул;
· определять и анализировать логическую структуру математических предложений;
· применять простейшие законы алгебры логики (контрапозиции, исключенного третьего и др.) к равносильным преобразованиям тех или иных утверждений;
· строить матрицы смежностей и инциденций для графа;
· применять на практике изученные алгоритмы теории графов;
владеть:
· представлениями о значении и областях применения дискретной математики;
· навыками практической работы с дискретными объектами, в том числе в профессиональной деятельности.
2. СОДЕРЖАНИЕ ДИСЦИПЛИНЫ
2.1. СОДЕРЖАНИЕ ДИСЦИПЛИНЫ ПО ГОС ВПО
ОПД. Ф.10 Основы дискретной математики
Множества и отношения. Операции над множествами. Функции.
Основы математической логики. Математический язык. Булева алгебра.
Элементы комбинаторики. Основные задачи комбинаторики и методы комбинаторных рассуждений.
Элементы теории графов.
2.2. МОДУЛИ И РАЗДЕЛЫ ДИСЦИПЛИНЫ
Модуль 1. Множества и отношения
Раздел I. Введение в теорию множеств
Понятие множества. Способы задания множеств. Подмножество. Универсальное множество. Булеан множества. Равенство множеств. Диаграммы Эйлера-Венна. Операции над множествами: объединение, пересечение, разность, декартово произведение. Теоремы об основных свойствах операций.
Раздел II. Отношения. Отображения
Определение бинарного отношения на паре множеств. Область определения, область значений б. о. Способы задания бинарных отношений; граф и график б. о. Отношение, обратное данному. Отношения на множестве и их свойства.
Отношение эквивалентности. Классы эквивалентности и фактор - множество. Понятие разбиения. Связь отношения эквивалентности, заданного на множестве, с разбиением этого множества. Отношение порядка. Упорядоченные (строго, нестрого, частично, линейно) множества.
Частичное отображение. Отображение (функция). Виды отображений: инъективное, сюръективное и биективное отображения. Обратное отображение. Необходимое и достаточное условие обратимости отображений. Взаимно однозначные отображения и мощности множеств. Счетные множества. Композиция отображений.
Модуль 2. Элементы комбинаторики
Раздел I. Элементы комбинаторики
Общие правила комбинаторики: правило суммы и произведения. Теорема о включениях и исключениях. Размещения с повторениями и без повторений. Перестановки с повторениями и без повторений. Сочетания. Свойства биномиальных коэффициентов. Бином Ньютона и полиномиальная формула. Комбинаторика разбиений.
Модуль 3. Основы математической логики
Раздел I. Алгебра высказываний
Понятие высказывания; элементарные и составные высказывания; логические операции над высказываниями. Формулы логики высказываний; таблицы истинности. Равносильность формул; основные равносильности алгебры высказываний; тождественно истинные, тождественно ложные и выполнимые формулы; закон двойственности.
Конъюнктивные и дизъюнктивные нормальные формы, совершенные к. н.ф. и д. н.ф. для формул логики высказываний.
Раздел II. Булевы функции (функции алгебры логики)
Понятие булевой функции; число различных п‑ местных булевых функций; равносильные булевы функции. Существенные и несущественные переменные; суперпозиция булевых функций; закон двойственности. теорема о разложении функции по аргументам.
Нормальные формы булевых функций и алгоритмы приведения булевых функций к нормальным формам. Полные системы функций. Применение булевых функций к анализу и синтезу релейно-контактных схем.
Модуль 4. Элементы теории графов
Раздел I. Введение в теорию графов. Маршруты, цепи и циклы в графе
Определение графа (неориентированного). Вершины и ребра. Графическая интерпретация графа. Смежность и инцидентность. Матричная форма представления графов: матрица смежности, матрица инцидентности. Подграфы и части графа. Степени вершин. Ориентированный граф; дуга орграфа, полустепень захода и исхода вершины.
Маршруты в графе. Цепи, простые цепи, циклы, простые циклы; путь и контур в орграфе. Связность и достижимость. Кратчайший маршрут во взвешенном связном графе; алгоритм Дейкстры.
Эйлеровы графы. Алгоритм построения эйлерова цикла. Алгоритм построения эйлеровой цепи. Гамильтоновы графы. Условия Дирака и Орэ, гарантирующие существование в графе гамильтонова цикла.
Раздел II. Планарные и плоские графы. Раскраска вершин графа
Планарные и плоские графы. Условия планарности. Грани плоского графа. Теорема Эйлера о соотношении чисел граней, ребер и вершин плоского графа.
|
Из за большого объема этот материал размещен на нескольких страницах:
1 2 3 4 5 |
