Дискретная математика (стр. 2 )

Дидактические единицы (ДЕ)	Наименование тем	Максимальная нагрузка студентов, час.	Количество аудиторных часов при заочной форме обучения	Самостоятельная работа студентов, час.
Лекции	Семинары	Лабораторные работы
1	2	3	4	5	6	7
ДЕ 12 Множества. Комбинаторика	14.  Множества	12	1	1		10
15.  Отношения	12	1	1		10
16.  Элементы теории нечетких множеств Нечеткие алгоритмы. Теория неопределенности	16	0,5	0,5		15
17.  Комбинаторика	17	0,5	1,5		15
Промежуточный контроль	Контрольная работа
ДЕ 13 Логические исчисления	18.  Формулы и функции алгебры логики	12	1	1		10
19.  Дизъюнктивные и конъюнктивные нормальные формы алгебры логики	16,5	0,5	1		15
20.  Совершенные дизъюнктивные и совершенные конъюнктивные нормальные формы	16,5	0,5	1		15
21.  Полные системы булевых функций	21,5	0,5	1		20
22.  Логика предикатов	21,5	1,5			20
Промежуточный контроль	Контрольная работа
ДЕ 14 Графы	23.  Основные понятия теории графов	11	0,5	0,5		10
24.  Связные графы	11	0,5	0,5		10
25.  Планарные и плоские графы	21,5	1	0,5		20
26.  Ориентированные графы	11,5	1	0,5		10
Промежуточный контроль	Контрольная работа
Итого часов	200	10	10		180
Итоговый контроль	Экзамен
Итого за весь курс часов	600	30	30		540

3. СОДЕРЖАНИЕ ДИСЦИПЛИНЫ

(дидактические единицы)

3.1 Обязательный минимум содержания образовательной программы : Логические исчисления. Графы. Комбинаторика. Элементы теории нечетких множеств. Нечеткие алгоритмы. Теория неопределенности.

3.2 Содержание разделов учебной дисциплины

ДЕ 1 Множества. Комбинаторика.

Тема 1. Множества

Аудиторное изучение: Понятие множества, подмножества. Задание множеств. Сравнение множеств. Операции над множествами (объединение, пересечение, дополнение, разность). Диаграммы Венна. Универсальное множество. Разбиения и покрытия. Булеан.

Самостоятельное изучение: Свойства операций над множествами.

Тема 2. Отношения

Аудиторное изучение: Прямое произведение. Бинарное отношение. Способы задания бинарных отношений. Операции над бинарными отношениями. Обратные отношения. Композиция бинарных отношений. Свойства бинарных отношений и их распознавание. Свойства матриц бинарных отношений. Рефлексивные, симметричные, транзитивные бинарные отношения. Отношение эквивалентности и классы эквивалентности.

Самостоятельное изучение: Отношение порядка. Линейный порядок и частичный порядок. Диаграммы Хассе.

Тема 3. Элементы теории нечетких множеств

Аудиторное изучение: Нечеткие множества. Объединение, пересечение, дополнение, разность и симметрическая разность нечетких множеств. Основные свойства операций над нечеткими множествами. Мощность нечёткого конечного множества. Нечёткое равенство нечётких множеств. Нечеткие алгоритмы. Теория неопределенности.

Самостоятельное изучение: Прямое произведение нечётких множеств. Композиция нечетких отображений. Композиция нечетких отношений. Теория неопределенности

Тема 4. Комбинаторика

Аудиторное изучение: Комбинаторные конфигурации и их общая характеристика. Правила суммы и произведения. Размещения, перестановки, сочетания с повторениями и без повторений. Основные тождества для сочетаний. Решение комбинаторных уравнений. Метод включений и исключений. Бином Ньютона, треугольник Паскаля.

Самостоятельное изучение: Рекуррентные соотношения. Возвратные последовательности.

ДЕ 2. Логические исчисления.

Тема 5. Формулы и функции алгебры логики

Аудиторное изучение: Логические переменные. Логические связки. Таблицы истинности. Правила расстановки скобок в формулах. Булева функция. Вектор значений булевой функции. Эквивалентность формул. Основные эквивалентности.

Самостоятельное изучение: Выполнимая и опровержимая формула. Тождественно-истинная формула. Тождественно-ложная формула.

Тема 6. Дизъюнктивные и конъюнктивные нормальные формы алгебры логики

Аудиторное изучение: Понятие литеры. Дизъюнкт. Конъюнкт. Дизъюнктивная и конъюнктивная нормальные формы. Алгоритм приведения формулы к дизъюнктивной и конъюнктивной нормальным формам.

Самостоятельное изучение: Конституента единицы. Конституента нуля.

Тема 7. Совершенные дизъюнктивные и совершенные конъюнктивные нормальные формы

Аудиторное изучение: Совершенная дизъюнктивная и конъюнктивная нормальные формы. Алгоритмы нахождения совершенной дизъюнктивной и совершенной конъюнктивной нормальных форм.

Самостоятельное изучение: Минимизация булевых функций в классе ДНФ.

Тема 8. Полные системы булевых функций

Аудиторное изучение: Многочлены Жегалкина. Теорема Жегалкина.

Замыкание множества функций. Понятие замкнутого класса функций. Важнейшие замкнутые классы: Т0 (класс функций, сохраняющих константу 0), Т1 (класс функций, сохраняющих константу 1), S (класс самодвойственных функций), L (класс линейных функций), M (класс монотонных функций). Полные системы булевых функций. Теорема Поста.

Самостоятельное изучение: Методики представления булевой функции в виде многочлена Жегалкина. Метод неопределенных квадратов.

Тема 9. Логика предикатов

Аудиторное изучение: Предикаты. Кванторы. Формулы логики предикатов. Равносильные формулы логики предикатов. Приведенные и нормальные формы в логике предикатов.

Самостоятельное изучение: Исчисление предикатов.

ДЕ 3 Графы.

Тема 10. Основные понятия теории графов

Аудиторное изучение: Понятие графа, простого графа, полного графа, однородного графа, мультиграфа, псевдографа. Подграф, надграф, частичный граф. Степень вершины. Операции над графами: дополнение, объединение, пересечение, сумма по модулю два, произведение. Способы задания графов: аналитический, графический, матричный. Матрица смежности. Матрица инцидентности..

Самостоятельное изучение: Изоморфизм.

Тема 11. Связные графы

Аудиторное изучение: Понятия маршрута, цепи, простой цепи, цикла, простого цикла. Связный граф. Степень связности. Матрица расстояний, эксцентриситеты вершин, радиус, диаметр, центр графа. Переферийные и центральные вершины. Обходы графов. Эйлеров цикл. Критерий Эйлера. Алгоритм построения эйлерова цикла.

Самостоятельное изучение: Гамильтонов цикл. Двудольные графы

Тема 12. Планарные и плоские графы

Аудиторное изучение: Плоский граф. Изоморфизм. Внутренняя и внешняя грани в двудольном графе. Теорема Эйлера о плоских графах. Гомеоморфизм. Подразбиение и надразбиение ребра. Теорема о том, что К5 и К3,3 не планарны. Критерий Понтрягина-Куратовского. Двойственные графы. Дерево и лес. Теорема о характеризации деревьев. Остовы графа. Цикломатическое число. Мост. Разделяющее множество. Разрез.

Самостоятельное изучение: Раскраска графа. Хроматическое число графа.

Тема 13. Ориентированные графы

Аудиторное изучение: Понятие орграфа. Матрица смежности вершин и дуг. Матрица инциденций. Степень вершин орграфа. Изоморфизм. Маршруты, цепи, циклы в орграфах. Связность орграфа: сильно связный, слабосвязный и несвязный орграф. Эйлеровы цепи и циклы в орграфе. Полный орграф. Операции в орграфе. Взвешенный граф. Нахождение кратчайщих маршрутов.

Самостоятельное изучение: Орграфы и бинарные отношения.

3.3 Содержание практических занятий

Тема 1. Множества

План.

1. Операции над множествами. Диаграммы Эйлера-Венна.

2. Упрощение выражений над множествами с использованием основных тождеств алгебры множеств.

3. Решение задач на подсчет количества элементов с использованием формулы количества элементов в объединении нескольких конечных множеств.

Тема 2. Отношения

План.

1. Прямое произведение.

2. Бинарное отношение. Способы задания бинарных отношений.

3. Матрицы бинарных отношений.

4. Рефлексивные, симметричные, транзитивные бинарные отношения.

5. Отношения порядка.

Тема 3. Элементы теории нечетких множеств

План.

1. Объединение, пересечение, дополнение, разность и симметрическая разность нечетких множеств.

2. Мощность нечёткого конечного множества. Нечёткое равенство нечётких множеств.

3. Прямое произведение нечётких множеств. Композиция нечетких отображений. Композиция нечетких отношений.

4. Нечеткие алгоритмы.

5. Теория неопределенности.

Тема 4. Комбинаторные конфигурации

План.

1. Правила суммы и произведения.

2. Размещения, перестановки, сочетания с повторениями.

3. Размещения, перестановки, сочетания без повторений.

4. Решение комбинаторных уравнений.

5. Метод включений и исключений.

6. Рекуррентные соотношения. Возвратные последовательности.

Тема 5. Формулы и функции алгебры логики

План.

1. Логические переменные.

2. Логические связки.

3. Таблицы истинности. Правила расстановки скобок в формулах.

4. Символическая форма для высказываний.

5. Булева функция. Вектор значений булевой функции.

6. Эквивалентность формул.

7. Выполнимая и опровержимая формула. Тождественно-истинная формула. Тождественно-ложная формула.

Тема 6. Дизъюнктивные и конъюнктивные нормальные формы алгебры логики

План.

1. Понятие литеры. Дизъюнкт. Конъюнкт.

2. Построение дизъюнктивной и совершенной конъюнктивной нормальных форм.

Тема 7. Совершенные дизъюнктивные и совершенные конъюнктивные нормальные формы.

План.

1. Представление булевой функции в виде совершенной дизъюнктивной и совершенной конъюнктивной нормальных форм.

2. Представление булевой функции в виде минимальной дизъюнктивной нормальной формы.

Тема 8. Полные системы булевых функций

План.

1. Представления булевой функции в виде многочлена Жегалкина двумя способами.

2. Проверка булевой функции на линейность.

3. Важнейшие замкнутые классы: Т0 (класс функций, сохраняющих константу 0), Т1 (класс функций, сохраняющих константу 1), S (класс самодвойственных функций), L (класс линейных функций), M (класс монотонных функций).

4. Полные системы булевых функций. Теорема Поста.

Тема 9. Логика предикатов

План.

1. Предикаты. Область истинности предиката

2. Кванторы.

3. Формулы логики предикатов.

4. Равносильные формулы логики предикатов.

5. Приведенные и нормальные формы в логике предикатов.

Тема 10. Основные понятия теории графов

План.

1. Виды и способы задания графов.

2. Матрица смежности. Матрица инцидентности. Степень вершины.

3. Однородный граф. Полный граф. Дополнение графа.

4. Операции над графами: дополнение, объединение, пересечение, сумма по модулю два, произведение.

Тема 11. Связные графы

План.

1. Маршруты, цепи, простые цепи, циклы, простые циклы. Длина цепи.

2. Связность графа.

3. Нахождение простых цепей.

4. Матрица расстояний, эксцентриситеты вершин, радиус, диаметр, центр графа. Переферийные и центральные вершины.

5. Взвешенный граф. Нахождение кратчайщих маршрутов.

6. Эйлеров цикл. Критерий Эйлера. Алгоритм построения эйлерова цикла.

7. Гамильтоновы графы. Задача о коммивояжере.

8. Двудольные графы.

Тема 12. Планарные и плоские графы

План.

1. Гомеоморфизм.

2. Теорема Эйлера о плоских графах.

3. Критерий планарности Понтрягина-Куратовского.

4. Двойственные графы.

5. Деревья и лес.

6. Раскраска графа. Хроматическое число графа.

Тема 13. Ориентированные графы

План.

1. Орграф. Матрица смежности. Изоморфизм.

2. Степень вершины орграфа.

3. Маршруты, цепи, циклы в орграфах.

4. Связность орграфа.

5. Эйлеровы цепи и циклы в орграфе.

6. Полный орграф.

7. Нахождение кратчайщих маршрутов

4. МЕТОДИЧЕСКИЕ РЕКОМЕНДАЦИИ ПО ОСВОЕНИЮ УЧЕБНОЙ ДИСЦИПЛИНЫ

4.1 Самостоятельная работа студента

Основной составной частью учебного процесса в преподавании дисциплины «Дискретная математика» студентам дневной формы обучения являются лекции и практические занятия. Очевидно, что студенты, активно участвующие в этих занятиях, способны успешнее освоить предмет.

Все лекции студентам необходимо конспектировать. В конспект рекомендуется выписывать определения, формулировки и доказательства теорем, формулы и т. п. На полях конспекта следует помечать вопросы, выделенные студентом для консультации с преподавателем. Выводы, полученные в виде формул, а также алгоритмы решения тех или иных классов задач дискретной математики рекомендуется в конспекте подчеркивать или обводить рамкой, чтобы при перечитывании конспекта они выделялись и лучше запоминались. Полезно составить краткий справочник, содержащий определения важнейших понятий и наиболее часто употребляемые формулы дисциплины. К каждой лекции следует разобрать материал предыдущей лекции. Ряд вопросов дискретной математики вынесен на самостоятельное изучение. Такое задание требует оперативного выполнения. В конспекте лекций необходимо оставить место для освещения упомянутых вопросов.

На практических занятиях подробно рассматриваются основные вопросы дисциплины, разбираются основные типы задач. К каждому практическому занятию следует заранее самостоятельно выполнить домашнее задание и выучить лекционный материал к следующей теме. Систематическое выполнение домашних заданий обязательно и является важным фактором, способствующим успешному усвоению дисциплины.

Промежуточный контроль проводится в виде контрольных работ.

Основной формой обучения студента-заочника является самостоятельная работа над учебным материалом, которая состоит из следующих элементов: изучение материала по учебникам, решение задач, самопроверка, выполнение контрольных работ. В помощь заочникам институт организует чтение лекций, практические занятия. Кроме того, студент может обращаться к преподавателю с вопросами для получения письменной или устной консультации.

Чтение учебника

1. Изучая материал по учебнику, следует переходить к следующему вопросу только после правильного понимания предыдущего, производя на бумаге все вычисления (в том числе и те, которые ради краткости опущены в учебнике) и выполняя имеющиеся в учебнике чертежи.

2. Особое внимание следует обращать на определение основных понятий. Студент должен подробно разбирать примеры, которые поясняют такие определения, и уметь строить аналогичные примеры самостоятельно.

3. При изучении материала по учебнику полезно вести конспект, в который рекомендуется вписывать определения, формулировки теорем, формулы, уравнения и т. д. На полях конспекта следует отмечать вопросы, выделенные студентом для получения письменной или устной консультации преподавателя.

4. Письменное оформление работы студента имеет исключительно важное значение. Записи в конспекте должны быть сделаны чисто, аккуратно и расположены в определенном порядке. Хорошее внешнее оформление конспекта по изученному материалу не только приучит студента к необходимому в работе порядку, но и позволит ему избежать многочисленных ошибок, которые происходят из-за небрежных, беспорядочных записей.

5. Выводы, полученные в виде формул, рекомендуется в конспекте подчеркивать или обводить рамкой, чтобы при перечитывании конспекта они выделялись и лучше запоминались. Опыт показывает, что многим студентам помогает в работе составление листа, содержащего важнейшие и наиболее часто употребляемые формулы курса. Такой лист не только помогает запомнить формулы, но и может служить постоянным справочником для студента.

Решение задач

1.Чтение учебника должно сопровождаться решением задач, для чего рекомендуется завести специальную тетрадь.

2.При решении задач нужно обосновать каждый этап решения исходя из теоретических положений курса. Если студент видит несколько путей решения, то он должен сравнить их и выбрать из них самый лучший. Полезно до начала вычислений составить краткий план решения.

3.Решения задач и примеров следует излагать подробно, вычисления располагать в строгом порядке, отделяя вспомогательные вычисления от основных.

5.Полученный ответ следует проверять способами, вытекающими из существа данной задачи. Полезно также, если возможно, решить задачу несколькими способами и сравнить полученные результаты.

6. Решение задач определенного типа нужно продолжать до приобретения твердых навыков в их решении.

Самопроверка

1.После изучения определенной темы по учебнику и решения достаточного количества соответствующих задач студенту рекомендуется воспроизвести по памяти определения, выводы формул, формулировки и теорем. В случае необходимости надо еще раз внимательно разобраться в материале учебника, решить ряд задач.

2.Иногда недостаточность усвоения того или иного вопроса выясняется только при изучении дальнейшего материала. В этом случае надо вернуться назад и повторить плохо усвоенный раздел.

Консультации

1.Если в процессе работы над изучением теоретического материала или при решении задач у студента возникают вопросы, разрешить которые самостоятельно не удается (неясность терминов, формулировок теорем, отдельных задач и др.), то он может обратиться к преподавателю для получения от него письменной или устной консультации.

2. В своих запросах студент должен точно указать, в чем он испытывает затруднение. Если он не разобрался в теоретических объяснениях, или в доказательстве теоремы, или в выводе формулы по учебнику, то нужно указать, какой это учебник, год его издания и страницу, где рассмотрен затрудняющий его вопрос, и что именно его затрудняет. Если студент испытывает затруднение при решении задачи, то следует указать характер этого затруднения, привести предполагаемый план решения.

3. За консультацией следует обращаться и при сомнении в правильности ответов на вопросы для самопроверки.

Контрольные работы

1.В процессе изучения курса математики студент должен выполнить ряд контрольных работ, главная цель которых — оказать студенту помощь в его работе. Рецензии на эти работы позволяют студенту судить о степени усвоения им соответствующего раздела курса; указывают на имеющиеся у него пробелы, на желательное направление дальнейшей работы; помогают сформулировать вопросы для постановки их перед преподавателем.

2. Не следует приступать к выполнению контрольного задания, не решив достаточного количества задач по материалу, соответствующему этому заданию. Опыт показывает, что чаще всего неумение решить ту или иную задачу контрольного задания вызывается тем, что студент не выполнил это требование.

3. Контрольные работы должны выполняться самостоятельно. Несамостоятельно выполненная работа не дает возможности преподавателю-рецензенту указать студенту на недостатки в его работе, в усвоении им учебного материала, в результате чего студент не приобретает необходимых знаний и может оказаться неподготовленным к устному зачету и экзамену.

Во время сессий для студентов-заочников организуются лекции и практические занятия. Они носят по преимуществу обзорный характер. Их цель — обратить внимание на общую схему построения соответствующего раздела курса, подчеркнуть важнейшие места, указать главные практические приложения теоретического материала.

Завершающим этапом изучения курса является

4.2 Оценочные средства для контроля успеваемости и результатов освоения учебной дисциплины

При оценивании знаний студентов по дисциплине используются Балльно-рейтинговые технологии, которые полностью описаны в «Положении о балльно-рейтинговых технологиях в РИ (филиале) АлтГУ».

Максимум 100 баллов студент может набрать в ходе семестра на аудиторных занятиях, промежуточном контроле и за решения контрольных работ и типовых расчетов. Баллы присуждаются по результатам работы на семинарских занятиях, за посещение в ходе семестра лекций. Максимальное количество баллов за работу на семинаре, можно получить, демонстрируя хорошее знание теоретического материала и умение применять их при решении практических задач. Ответ на экзамене дает студенту от 0 до 40 баллов.

Студент, набравший менее 60 баллов, получает итоговую оценку – неудовлетворительно, от 61 до 75 – удовлетворительно, от 76 до 90 – хорошо, 91 и выше баллов – отлично.

На экзамене оценка «отлично» ставится, если студент строит ответ логично в соответствии с планом, показывает максимально глубокие знания математических терминов, понятий, категорий, концепций и теорий. Практические задания выполнены полностью, осознанно. Устанавливает содержательные межпредметные связи. Демонстрирует знание специальной литературы в рамках учебного методического комплекса и дополнительных источников информации.

Оценка «хорошо» ставится, если студент строит свой ответ в соответствии с планом. Есть небольшие неточности в изложении теоретического материала или в выполнении практических заданий. Устанавливает содержательные межпредметные связи. Речь грамотна, используется профессиональная лексика. Демонстрирует знание специальной литературы в рамках учебного методического комплекса и дополнительных источников информации. Имеет место средний уровень выполнения контрольных и самостоятельных работ в течение учебного процесса

Оценка «удовлетворительно» ставится, если ответ недостаточно логически выстроен, план ответа соблюдается непоследовательно. Практические задания выполнены все, есть небольшие неточности.

Оценка «неудовлетворительно» ставится при условии недостаточного раскрытия понятий. Ответ содержит ряд серьезных неточностей. Выводы поверхностны. Имеет место очень низкий уровень выполнения контрольных и самостоятельных работ в течение учебного процесса

5. МАТЕРИАЛЬНО-ТЕХНИЧЕСКОЕ ОБЕСПЕЧЕНИЕ ДИСЦИПЛИНЫ

Аудитория для проведения лекционных занятий, имеющая необходимое количество посадочных мест и оснащенная оборудованием для проведения презентаций (ноутбук, проектор).

6. МАТЕРИАЛЫ К ПРОМЕЖУТОЧНОМУ И ИТОГОВОМУ КОНТРОЛЮ

Вариант аудиторной контрольной работы №1.

1.  В студенческой группе 25 человек. Чтобы получить допуск на экзамен по данному курсу необходимо защитить курсовую работу, выполнить лабораторную работу и сдать зачет. 15 студентов защитили курсовую работу, 20 — выполнили лабораторную работу, 17 — сдали зачет. Защитили курсовую работу и выполнили лабораторную работу 12 человек. Защитили курсовую работу и сдали зачет 13 человек. Выполнили лабораторную работу и сдали зачет 16 человек. Сколько студентов допущено к экзамену?

2.  Изобразить с помощью диаграмм Венна:

a. 

b. 

3.  Даны множества: A = {1, 2, 3}; B = {2, 3, 4}; С = {1, 2, 3, 4, 5, 6}. Найдите элементы множеств:; ; ; ;

; ; ; .

4.  . Изобразите Р1 и Р2 графически. Найдите . Проверьте с помощью матрицы , является ли отношение Р2 рефлексивным, симметричным, антисимметричным, транзитивным?

5.  Номер автомашины состоит из трех букв русского алфавита (30 букв) и трех цифр. Сколько существует различных номеров автомашин?

6.  Из колоды в 36 карт наудачу берутся 6 карт. Найти число различных способов выбора 6 карт, содержащих 3 туза.

7.  Местком состоит из 7 человек. Из своей среды он выбирает президиум в составе трех человек: председателя месткома, заместителя председателя месткома, секретаря месткома. Сколько существует различных способов образования президиума месткома?

8.  Семнадцать девушек водят хоровод. Сколькими различными способами они могут встать в круг?

9.  На 10-ти карточках написаны буквы так, что из этих карточек можно составить слово МАТЕМАТИКА. Сколько существует различных 10-

буквенных слов, которые можно образовать при помощи этих десяти карточек?

10.  Сколькими способами можно выбрать 4 краски из имеющихся 7 различных?

Вариант аудиторной контрольной работы № 2

1.  Для заданной булевой функции трех переменных:

а) построить таблицу истинности, найти двоичную форму булевой функции и привести функцию к СДНФ и СКНФ;

б) найти двумя способами многочлен Жегалкина и ответить на вопрос, является ли данная функция линейной;

с) с помощью эквивалентных преобразований приведите функцию к ДНФ, КНФ, СДНФ и СКНФ.

a 

2.  Выяснить, является ли система функций A функционально полной.

Вариант аудиторной контрольной работы № 3.

1.  Даны графы G1 и G2. Найдите . Для графа найдите матрицы смежности, инцидентности, сильных компонент, маршрутов длины 2 и все маршруты длины 2, исходящие из вершины 1.

2.  Найдите матрицы фундаментальных циклов, фундаментальных разрезов, радиус и диаметр, минимальное множество покрывающих цепей графа G. Является ли изображенный граф эйлеровым? Является ли изображенный граф планарным?

3.  Для графа представленного следующей матрицей смежности, определить матрицу инцидентности и изобразить его графически.

4.  Для графа представленного следующей матрицей инцидентности, определить матрицу смежности и изобразить его графически.

Вопросы к экзамену:

1.  Множество. Задание множеств. Сравнение множеств.

2.  Операции над множествами (объединение, пересечение, дополнение, разность).

3.  Универсальное множество. Разбиения и покрытия. Булеан.

4.  Свойства операций над множествами.

5.  Прямое произведение. Бинарное отношение.

6.  Способы задания бинарных отношений. Композиция бинарных отношений.

7.  Свойства бинарных отношений и их распознавание.

8.  Свойства матриц бинарных отношений.

9.  Рефлексивные, симметричные, транзитивные бинарные отношения.

10.  Отношение эквивалентности.

11.  Отношения порядка. Упорядоченные пары.

12.  Простейшие комбинаторные конфигурации и их свойства.

Логические переменные. Логические связки. Таблицы истинности. Булева функция. Вектор значений булевой функции. Эквивалентность формул. Основные эквивалентности. Выполнимая и опровержимая формула. Тождественно-истинная формула. Тождественно-ложная формула. Понятие литеры. Дизъюнкт. Конъюнкт. ДНФ. КНФ. Конституента единицы. Конституента нуля. Алгоритм приведения формулы к ДНФ и КНФ. Совершенная дизъюнктивная и конъюнктивная нормальные формы. Алгоритмы нахождения СДНФ и СКНФ. Минимизация булевых функций в классе ДНФ. Матрица Квайна. Замкнутые классы. Классы T0 , T1 , S, M, L. Полные системы булевых функций. Теорема Поста. Свойства суммы по модулю 2. Теорема Жегалкина. Алгоритмы построения полинома Жегалкина. Предикаты. Кванторы. Формулы логики предикатов Понятие графа, простого графа, полного графа, однородного графа, мультиграфа, псевдографа. Подграф, надграф, частичный граф. Степень вершины. Операции над графами: дополнение, объединение, пересечение, сумма по модулю два, произведение. Способы задания графов: аналитический, графический, матричный. Матрица смежности. Матрица инцидентности. Понятия маршрута, цепи, простой цепи, цикла, простого цикла. Связный граф. Степень связности. Матрица расстояний, эксцентриситеты вершин, радиус, диаметр, центр графа. Переферийные и центральные вершины. Эйлеров цикл. Критерий Эйлера. Алгоритм построения эйлерова цикла. Гамильтонов цикл. Двудольные графы. Плоский граф. Изоморфизм. Внутрення и внешняя грани в двудольном графе. Теорема Эйлера о плоских графах. Гомеоморфизм. Подразбиение и надразбиение ребра Критерий Понтрягина-Куратовского. Дерево и лес. Цикломатическое число. Мост. Разделяющее множество. Разрез. Понятие орграфа. Матрица смежности вершин и дуг. Матрица инциденций. Степень вершин орграфа. Изоморфизм. Маршруты, цепи, циклы в орграфах. Связность орграфа: сильно связный, слабосвязный и несвяхный орграф. Эйлеровы цепи и циклы в орграфе. Полный орграф.

7. СПИСОК ОСНОВНОЙ И ДОПОЛНИТЕЛЬНОЙ ЛИТЕРАТУРЫ, ДРУГИЕ ИНФОРМАЦИОННЫЕ ИСТОЧНИКИ

Основная литература

1.  , Шишков логика. Дискретные функции. Теория алгоритмов / , – СПб.: «Лань», 2012 – 409.

2.  , , Шевелев задач по дискретной математике (для практических занятий в группах)/ , , - СПб.: «Лань», 2013 – 523.

3.  Шевелев математика / . - СПб.: «Лань», 2008 – 592.

Дополнительная литература

1.  Виленкин ./ , А. Н Виленкин., - М.: ФИМА, МЦНМО, 20с.

2.  Галкина математика: комбинаторная оптимизация на графах: Учеб. Пособие/ - М.: Гелиос АРВ, 20c.

3.  Гончарова, дискретной математики: Учебное пособие для среднего профессионального образования по специальностям информатики и вычислительной техники / , - М, 2003, 128 с.

Горбатов основы дискретной математики. Информационная математика. /, , - Наука, 2000.- С.- 544c.

5.  Москинова, математика: Математика для менеджера в примерах и упражнениях / . - М.: Логос, 2c.

6.  Овчинникова логика и теория алгоритмов: учебник / , . - Новосибирск: НГТУ, 20c.

7.  Овчинникова дискретной математики: учебник / , -М. 2002, 280 с.

Плотников математика: учеб. пособие /. — М.: Новое знание, 2005. — 288 с. Соболева математика: учебник для студ. вузов / , ; под ред. . — М.: Издательский центр «Академия», 2006. — 256 с. Спирина математика: Учебник для студ. учреждений сред. проф. образования / , . — М.: Издательский центр «Академия», 2004. — 368 с. Яблонский в дискретную математику: Учеб. пособие / - М.: Высшая школа, 20c.

Базы данных, Интернет-ресурсы,

информационно-справочные и поисковые системы

1.  Единое окно доступа к образовательным ресурсам. Электронная библиотека [Электронный ресурс]: инф. система. – М.: ФГАУ ГНИИ ИТТ "Информика", . – Режим доступа: //www. http://window. *****, свободный. – Загл. с экрана (дата обращения 11.04.2012)

2.  Образовательный математический сайт http://www. *****/

3.  Поисковые системы: Яндекс, Rambler, Google

4.  Свободная энциклопедия Википедия (http://ru. wikipedia. org)