Қазақстан Республикасының Министерство
Білім және ғылым образования и науки
министрлігі Республики Казахстан
Д. Серікбаев атындағы ВКГТУ
ШҚМТУ им. Д. Серикбаева
УТВЕРЖДАЮ
Декан ФИТЭ
__________М. К. Кылышканов
____________________2015 г.
ДИСКРЕТТІК МАТЕМАТИКА
Жұмыс модульдік оқу бағдарламасы және силлабус
ДИСКРЕТНАЯ МАТЕМАТИКА
Рабочая модульная учебная программа и силлабус
Специальность: «5В070400 - Вычислительная техника и программное обеспечение»
Количество кредитов дисциплины: 3 кредита
Өскемен
Усть-Каменогорск
2015
Рабочая модульная учебная программа и силлабус разработаны на кафедре «Высшая математика» на основании Рабочего учебного плана, Каталога элективных дисциплин, Типовой учебной программы и Модульной образовательной программы специальности.
Одобрено учебно-методическим советом ФИТиБ
Уазырханова
Протокол №____ от______________________г.
Обсуждено на заседании кафедры «Высшая математика»
Зав. кафедрой С. Тыныбекова
Протокол №____ от ____________________г.
Разработал
Доцент кафедры И. Латкин
Тютюнькова
1 ХАРАКТЕРИСТИКА ДИСЦИПЛИНЫ, ЕЕ МЕСТО В УЧЕБНОМ ПРОЦЕССЕ
1.1 Краткое содержание изучаемой дисциплины
Объектом изучения данной дисциплины является математическая задача (математическая модель) и её логическая характеристика.
Методом изучения данной дисциплины являются теоретические курсы (лекции), практические занятия и самостоятельная работа студентов.
Развитие новых технологий и широкое внедрение математических методов в инженерные исследования, а также рост числа выпускаемой вычислительной техники и повышение ее качества, привели к широкому использованию ПК во многих областях народного хозяйства. В настоящее время успешное решение большинства научно-технических задач в значительной степени зависит от умения оперативно применять ЭВМ. В этой связи курс «Дискретная математика» является фундаментом для почти всех специальных курсов. Его успешное освоение студентами – залог того, чтобы из них сформировались молодые специалисты, обладающие необходимыми компетенциями, которые позволят им быть востребованным на рынке труда, способным осуществлять эффективную профессиональную деятельность.
Данный курс дискретной математики содержит: основные понятия теории множеств, теории графов, алгебры логики, формальных исчислений. Множества. Отношения. Класс эквивалентности. Булевы алгебры. Законы булевой алгебры. Булевы функции. Методы доказательств в логике высказываний. Предикаты и кванторы. Построение доказательств в логике предикатов. Графы. Виды графов. Кратчайшие пути на графе. Деревья.
1.2 Цели и задачи изучения дисциплины
Цель преподавания дисциплины согласуется с целями Ц1, Ц2, Ц3, Ц4 и Ц5 модульной образовательной программы в части подготовки специалистов, которые владеют навыками составления и анализа математических моделей несложных задач прикладного характера, связанных с будущей деятельностью инженера, накопили достаточный практический опыт применения современных математических средств для разработки программного обеспечения при решении различных прикладных задач.
Задачи изучения дисциплины:
- приобретение студентами базовых знаний по теории графов, теории булевых функций, теории множеств, формальных исчислений;
- сформировать у будущих специалистов компетентности в области дискретной математики и её приложений;
- выработать у обучающихся навыки составления и анализа математических моделей несложных задач прикладного характера, связанных с будущей деятельностью инженера.
1.3 Результаты изучения дисциплины
Результаты обучения определяются на основе Дублинских дескрипторов соответствующего уровня образования и выражаются через компетенции.
Знание и понимание:
- определения, понятия и теории графов, используемые при решении некоторых оптимизационных задач;
- алгоритмы построения кратчайших путей;
- определения и понятия теории булевых функций;
- распознавание полных систем булевых функций;
- способы реализации булевых функций формулами;
- методы минимизации булевых функций;
- основные понятия и операции теории множеств;
- важнейшие виды бинарных отношений.
Применение знаний и пониманий:
- применять изученные алгоритмы на практике;
- создавать модели, соответствующие задачам предметных областей.
Формирование суждений:
-иметь представление о математическом моделировании, понимать схемы, задаваемые в виде графов;
- уметь качественно и количественно анализировать численный результат;
- иметь представление о прикладных аспектах дискретной математики.
Коммуникативные способности:
- развить коммуникационные способности, необходимые для работы в команде.
Навыки обучения или способности к учебе:
- научиться преобразовывать словесный материал в математические выражения, а затем в формально-логические, и наоборот;
- уметь строить математические модели реальных явлений и процессов;
- владеть культурой мышления, приобщиться к опыту творческой математической деятельности;
- быть способным поставить цель и сформулировать задачи по дискретной математике.
1.4 Пререквизиты
«Алгебра и геометрия», «Математический анализ», «Информационные технологии».
1.5 Постреквизиты
«Операционные системы», «Системное программирование», «Технология программирования», «Надежность информации».
2 СОДЕРЖАНИЕ ДИСЦИПЛИНЫ
Содержание дисциплины разбито на два модуля «Основы теории множеств и формальных исчислений» и «Булевы функции, их минимизация и элементы теории графов».
2.1 Тематический план
№ модуля, темы | Наименование темы, ее содержание | Ссылка на литературу и другие источники | Трудоемкость в кредитах |
|
1 | 2 | 3 | 4 |
|
1 | Модуль 1 «Основы теории множеств и формальных исчислений» |
| ||
Лекционные занятия |
| |||
1 | Множества. Основные операции над ними и их свойства. | 1,2,9,10 |
| |
2 | Бинарные отношения, их основные свойства. | 1,2,9,10 |
| |
1 | 2 | 3 | 4 |
|
3 | Важнейшие типы бинарных отношений: эквивалентности, частичные порядки, функции. Лемма о разбиении на классы эквивалентности. | 1,9,10,12 |
| |
4 | Булевы алгебры. Законы булевой алгебры. | 1,2,9,10,12 |
| |
5 | Методы доказательств в логике высказываний. Сложные высказывания как булевы функции. Теорема о полноте исчисления высказываний. | 1,2,14,6,7 |
| |
6 | Предикаты и кванторы. Построение доказательств в логике предикатов. Некоторые правила действий с кванторами. | 1,2,9,10,13 |
| |
7 | Применения языка формул для записи сложных утверждений. | 1,2,9,10 |
| |
8 | Эквивалентность формул, основные свойства булевых функций. Совершенные ДНФ и КНФ. Полином Жегалкина для булевой функции. | 1,2,9,10,11,15,17 |
| |
Итого | 0,5 |
| ||
Семинарские (практические) занятия |
| |||
1 | Множества. Основные операции над ними и их свойства. | 1,2,4,5,9,10,12 |
| |
2 | Важнейшие типы бинарных отношений: эквивалентности, частичные порядки, функции. Лемма о разбиении на классы эквивалентности. | 1,2,4,5,9,10 |
| |
3 | Сложные высказывания как булевы функции. Предикаты и кванторы. Применения языка формул для записи сложных утверждений. | 1,2,4,5,9,10 |
| |
4 | Совершенные ДНФ и КНФ. Полином Жегалкина для булевой функции. | 1,2,4,5,9,10,11,17 |
| |
Итого | 1 | |||
Самостоятельная работа обучающегося под руководством преподавателя (СРОП) |
| |||
1 | Множества. Основные операции над ними и их свойства. | 1,2,4,5,9,10 |
| |
2 | Важнейшие типы бинарных отношений: эквивалентности, частичные порядки, функции. Лемма о разбиении на классы эквивалентности. | 1,2,4,5,9,10 |
| |
3 | Сложные высказывания как булевы функции. Предикаты и кванторы. Применения языка формул для записи сложных утверждений. | 1,2,4,5,9,10 |
| |
4 | Совершенные ДНФ и КНФ. Полином Жегалкина для булевой функции. | 1,2,4,5,9,10,11,17 |
| |
Самостоятельная работа обучающегося (СРО) |
| |||
1 | Множества. Основные операции над ними и их свойства. | 1,2,4,5,9,10,12 |
| |
2 | Важнейшие типы бинарных отношений: эквивалентности, частичные порядки, функции. Лемма о разбиении на классы эквивалентности. | 1,2,4,5,9,10 |
| |
1 | 2 | 3 | 4 | |
3 | Совершенные ДНФ и КНФ. Полином Жегалкина для булевой функции. | 1,2,4,5,9,10,17 |
| |
4 | Сложные высказывания как булевы функции. Предикаты и кванторы. Применения языка формул для записи сложных утверждений. | 1,2,4,5,9,10,11,17 |
| |
Итого по модулю 1 | 1,5 |
| ||
2 | Модуль 2 «Булевы функции и графы» |
| ||
Лекционные занятия |
| |||
1 | Двойственные и самодвойственные булевы функции. Принцип двойственности. Монотонные функции. | 1,2,9,10,11,15,17 |
| |
2 | Полнота, примеры полных систем. Критерий полноты. | 1,2,9,10,11,15,17 |
| |
3 | Проблема минимизации булевых функций, индексы простоты. Геометрический подход. | 1,2,9,10,11,15 |
| |
4 | Совершенная, тупиковая, минимальная, сокращенная ДНФ. | 1,2,9,10,11,15,16 |
| |
5 | Определения, начальные понятия теории графов. Примеры. Орграфы, мультиграфы. Подграфы. | 1,2,3,6-11,12,14 |
| |
6 | Взвешенный граф. Кратчайшие пути. Способы задания графов в ЭВМ (матричные и другие). | 1,2,3,6-12,14 |
| |
7 | Изоморфные графы. Деревья. Определения. Эквивалентность различных определений. Остов. | 1,2,3,6-12,14 |
| |
Итого | 0,5 |
| ||
Семинарские (практические) занятия |
| |||
1 | Двойственные и самодвойственные булевы функции. Монотонные функции. Критерий полноты. | 1,2,4,5,9,10,11 |
| |
2 | Совершенная, тупиковая, минимальная, сокращенная ДНФ. | 1,2,4,9,10,11,16 |
| |
3 | Взвешенный граф. Кратчайшие пути. Способы задания графов в ЭВМ (матричные и другие). | 1-4,6-12,14 |
| |
4 | Изоморфные графы. Деревья. Определения. Эквивалентность различных определений. Остов. | 1-4,6-12,14 |
| |
Итого | 1 |
| ||
Самостоятельная работа обучающегося под руководством преподавателя (СРОП) |
| |||
1 | Двойственные и самодвойственные булевы функции. Монотонные функции. Критерий полноты. | 1,2,4,5,9,10,11 |
| |
2 | Совершенная, тупиковая, минимальная, сокращенная ДНФ. | 1,2,4,9,10,11,16 |
| |
3 | Взвешенный граф. Кратчайшие пути. Способы задания графов в ЭВМ (матричные и другие). | 1-4,6-12,14 |
| |
4 | Изоморфные графы. Деревья. Определения. Эквивалентность различных определений. Остов. | 1-4,6-12,14 |
| |
Самостоятельная работа обучающегося (СРО) |
| |||
1 | Двойственные и самодвойственные булевы функции. Монотонные функции. Критерий полноты. | 1,2,4,5,9,10,11,17 |
| |
1 | 2 | 3 | 4 |
|
2 | Тупиковая, минимальная, сокращенная ДНФ. | 1,2,4,9,10,11,16 |
| |
3 | Взвешенный граф. Кратчайшие пути. Способы задания графов в ЭВМ (матричные и другие). | 1-4,6-12,14 |
| |
4 | Изоморфные графы. Деревья. Определения. Эквивалентность различных определений. Остов. | 1-4,6-12,14 |
| |
Итого по модулю 1 | 1,5 |
| ||
Итого по дисциплине, кредит РК | 3 |
|
2.2 Задания для самостоятельной работы (СРОП, СРО)
Тема | Цель и содержание задания | Прод. вып., час. | Форма контроля | Срок сдачи, № уч. недели |
1 | 2 | 4 | 5 | 6 |
1. Множества. | Познакомиться с основными операция-ми над ними и их свойствами. Бинарные отношения, их основные свойства. Свойства отношений эквивалент-ности, частичных поряд-ков, функций. Фактор множества. | 8 | Инд. задание и дополнительные вопросы при его защите. Устный опрос | 3 |
2. Булевы фун-кции. | Элементарные бу-левы функции. За-дание их таблично и формульно. Фиктив-ные переменные. Применения языка формул для записи сложных утверждений. | 8 | Инд. задание и дополнительные вопросы при его защите. Устный опрос | 5 |
3. Свойства бу-левых функции. | ДНФ и КНФ. Поли-ном Жегалкина. Двойственные и самодвойственные булевы функции. Принцип двойстве-нности. Монотон-ные функции. Полнота, задачи на применение кри-терия полноты. | 6 | Инд. задание и дополнительные вопросы при его защите. Тестовые задания | 7 |
4. Методы на-хождения сокращенных ДНФ. | Получить сведения о способах их нахождения. Метод Квайна. Методы Блейка и Нельсона нахожде-ния сокращенных ДНФ. Карты Карно. | 8 | Инд. задание и дополнительные вопросы при его защите. Устный опрос | 10 |
1 | 2 | 4 | 5 | 6 |
5. Триггеры свойств и событий WPF | Познакомиться с механизмом триггеров WPF для создания анимационного эффекта | 7 | Инд. задание и дополнительные вопросы при защите лабораторной работы. Тестовые задания | 12 |
6. Использование API-интерфейса Microsoft Office и первичных сборок. Net Microsoft. Office. Interop | Освоить упрощённый механизм взаимодействия с СОМ с целью расширения практических приёмов организации межпрограммного взаимодействия | 8 | Инд. задание и дополнительные вопросы при защите лабораторной работы. Тестовые задания | 15 |
2.3 График выполнения и сдачи заданий по дисциплине
Вид контроля | Академический период обучения, неделя | ||||||||||||||
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | |
Защита индивидуалных работ | 100 | 100 | 100 | 100 | 100 | 100 | |||||||||
Рубежное тестирование | 100 | 100 | |||||||||||||
Всего | 1 | 1 | 2 | 1 | 1 | 2 |
3 СПИСОК РЕКОМЕНДУЕМОЙ ЛИТЕРАТУРЫ
Основная литература
1 С. Г. Горбатов Основы дискретной математики. М.: Высшая школа, 2007г.
2 С. В. Судоплатов, Е. В. Овчинникова Дискретная математика, Новосибирск, 2007г.
3 Л. Ю. Березина Графы и их применение. М.: Просвещение, 2009.
4 Г. П. Гаврилов, А. А. Сапоженко Задачи и упражнения по курсу дискретной математики.– М.: Наука, 2012.
5 И. А. Лавров, Л. Л. Максимова. Задачи по теории множеств, математической логике и теории множеств. М.: Наука, 2015.
6 В. А. Емеличев и др. Лекции по теории графов.– М.: Наука. 2010.
7 А. А. Зыков Основы теории графов.– М.: Наука. 2007.
8 Н. Кристофидес Теория графов. Алгоритмический подход. – М.: Мир, 2008.
9 И. В. Латкин Конспект лекций по дискретной математике. – Усть-Каменогорск, ВКГТУ, 2010.
10 Ф. А. Новиков Дискретная математика для программистов. – СПб: Питер, 2011.
11 С. В. Яблонский Введение в дискретную математику.– М.: Наука, 2009.
Дополнительная литература
12 М. О. Асанов, В. А. Баранский, В. В. Расин Дискретная математика: графы, матроиды, алгоритмы. – Москва, Ижевск: НИЦ «Регулярная и хаотическая динамика», 2001.
13 С. Г. Горбатов Фундаментальные основы дискретной математики.– М.: Наука, 2000.
14 В. А. Евстигнеев Применение теории графов в программировании. – М.: Наука, 1985.
15 О. П. Кузнецов, Г. М. Адельсон-Вельский Дискретная математика для инженеров.–М., Энергия, 1980.
16 И. В. Латкин Лемма о дополнении граничными точками. //Региональный вестник Востока, №4(8), 2000, С. 48–50.
17 З. Г. Хисамиев Дискретная математика. Часть1. Булевы функции.– Усть-Каменогорск, ВКТУ, 1998.
4 ОЦЕНКА ЗНАНИЙ
4.1 Требования преподавателя
Требования преподавателя:
- посещение лекционных и лабораторных занятий, СРСП по расписанию является обязательным;
- присутствие студентов на занятиях проверяется в начале занятий, в случае опоздания студент должен бесшумно войти в аудиторию и включиться в работу, а в перерыве объяснить преподавателю причину опоздания;
- оцениваемые в баллах лабораторные работы следует сдавать в установленные сроки, к рубежному тестированию допускаются студенты, защитившие не менее одной лабораторной работы текущего рейтинга;
- повторное прохождение студентом рубежного контроля, в случае получения неудовлетворительной оценки, не допускается;
- студенты, получившие средний рейтинг Рср = (Р1 + Р2)/2 менее 50%, к экзамену не допускаются;
- в течение занятий мобильные телефоны должны быть отключены;
- студент обязан приходить на занятия в деловой одежде.
4.2 Критерии оценки
Оценка всех видов заданий осуществляется по 100-балльной системе.
Текущий контроль проводится в соответствии с графиком проведения текущего и рубежного контроля по дисциплине (п.5) и включает контроль посещения лекций, защиту лабораторных работ и индивидуальных заданий по самостоятельной работе.
Рубежный контроль знаний проводится на 7 и 15 неделе семестра в форме тестирования. Рейтинг рассчитывается как среднее значение из следующих видов контроля:
Аттестационный период | Вид текущего контроля | |||||||
Защита индивидуальной 1-работы | Защита индивидуальной 2-работы | Защита индивидуальной 3-работы | Рубежное тестирование | Защита индивидуальной 4-работы | Защита индивидуальной 5-работы | Защита индивидуальной 6-работы | Рубежное тестирование | |
Модуль 1 - рейтинг 1 | 100 | 100 | 100 | 100 | ||||
Модуль 2 - рейтинг 2 | 100 | 100 | 100 | 100 |
Экзамен по дисциплине проходит во время экзаменационной сессии в форме тестирования.
Итоговая оценка знаний студента по дисциплине включает:
- 40% результата, полученного на экзамене;
- 60% результатов текущей успеваемости.
Формула подсчета итоговой оценки:
, (1)
где Р1, Р2 – цифровые эквиваленты оценок первого, второго рейтингов соответственно; Э – цифровой эквивалент оценки на экзамене.
Итоговая буквенная оценка и её цифровой эквивалент в баллах:
Оценка по буквенной системе | Цифровой эквивалент баллов | Процентное содержание, % | Оценка по традиционной системе |
А | 4,0 | 95–100 | отлично |
А– | 3,67 | 90–94 | |
В+ | 3,33 | 85–89 | хорошо |
В | 3,0 | 80–84 | |
В– | 2,67 | 75–79 | |
С+ | 2,33 | 70–74 | удовлетворительно |
С | 2,0 | 65–69 | |
С– | 1,67 | 60–64 | |
D+ | 1,33 | 55–59 | |
D | 1,0 | 50–54 | |
F | 0 | 0–49 | неудовлетворительно |
4.3 Материалы для рубежного и итогового контролей
4.3.1 Материалы для рубежного и итогового контроля модуля 1 «Основы теории множеств и формальных исчислений»
4.3.1.1 Основные понятия и определения. Множества. Основные операции над ними и их свойства.
1) Какие множества называются равными?
2) Операция пересечения.
3) Операция объединения.
4) Операция разности.
5) Дополнение множества.
6) Важнейшие свойства операций.
4.3.1.2 Бинарные отношения.
1) Что такое бинарное отношение?
2) Рефлексивное бинарное отношение.
3) Антирефлексивное бинарное отношение.
4) Симметричное бинарное отношение.
5) Антисимметричное бинарное отношение.
6) Транзитивное бинарное отношение.
7) Отношение эквивалентности.
8) Класс эквивалентности.
9) Фактор множество.
10) Отношение частичного порядка.
11) Наименьший и минимальный элементы.
12) Функция как вид бинарного отношения.
13) Взаимно однозначные функции.
14) Функции «на».
4.3.1.3 Булевы алгебры.
1) Законы булевой алгебры.
2) Алгебра множеств.
4.3.1.4 Формальные исчисления.
1) Аксиомы.
2) Правила вывода.
3) Что такое предикат?
4) Квантор существования.
5) Квантор всеобщности.
4.3.2 Материалы для рубежного и итогового контроля модуля 2 «Булевы функции и их минимизация»
4.3.2.1 Булевы функции.
1) Элементарные (основные) булевы функции, их логический смысл.
2) Табличный способ задания.
3) Фиктивные переменные.
4) Что такое ДНФ?
5) Что такое КНФ?
6) Двойственная функция.
7) Принцип двойственности.
8) Монотонные функции.
9) Линейные функции.
10) Теорема о полноте.
4.3.2.2 Минимизация булевых функций.
1) Основные индексы простоты.
2) Метод Квайна нахождения сокращенных ДНФ.
3) Метод Нельсона нахождения сокращенных ДНФ.
4) Метод Блейка нахождения сокращенных ДНФ.
5) Метод граничных точек.
6) Карты Карно.
4.3.2.3 Теория графов.
1) Степень вершины, вектор степеней.
2) Что такое обыкновенный (простой) граф.
3) Матрица инцидентности.
4) Матрица смежности.
5) Взвешенный граф. Матрица весов.
6) Как избавиться от весов на вершинах?
7) Что такое дерево?
8) Определение остова (каркаса).
5 ОСНОВНЫЕ ФОРМЫ И МЕТОДЫ ОБУЧЕНИЯ
Методы и формы организации обучения, используемые в дисциплине, представлены в таблице.
Методы и формы организации обучения | Лекции | Практические работы | СРОП, СРО |
1 | 2 | 3 | 4 |
Методы проблемного обучения | + | + | + |
Опережающая самостоятельная работа | + | + | |
Устный опрос | + | + | + |
Проектный метод | + | + | |
Поисковый метод | + | + | + |
Исследовательский метод, основанный на использовании элементов НИР преподавателей дисциплины | + | + | |
Реферат | + | + | |
Другие методы |
6. ВРЕМЯ КОНСУЛЬТАЦИЙ
- по графику работы преподавателя
Основные порталы (построено редакторами)