1. Цели освоения дисциплины
| 1.1. | Развитие логического, алгоритмического и математического мышления. Применение логических операций, формул логики, законов алгебры логики, теории графов. Формулирование задач логического характера и применение средств математической логики для их решения. Применение полученных знаний при решении различных профессиональных задач. Формирование и развитие умения находить информацию из различных источников, анализировать, систематизировать и синтезировать ее. Создание положительной мотивации к обучению, самообучению и саморазвитию. Расширение представлений о математике как части общечеловеческой культуры, универсальном языке науки, позволяющем описывать и изучать реальные процессы и явления. Использование полученных знаний и умений в будущей профессиональной деятельности. |
|---|
2. Место дисциплины в структуре ООП
| Цикл (раздел) ООП: ЕН |
3. Компетенции обучающегося, формируемые в результате освоения дисциплины
| ОК 01. | Выбирать способы решения задач профессиональной деятельности применительно к различным контекстам; |
| ОК 02. | Использовать современные средства поиска, анализа и интерпретации информации и информационные технологии для выполнения задач профессиональной деятельности; |
| ОК 04. | Эффективно взаимодействовать и работать в коллективе и команде; |
| ОК 05. | Осуществлять устную и письменную коммуникацию на государственном языке Российской Федерации с учетом особенностей социального и культурного контекста; |
| ОК 09. | Пользоваться профессиональной документацией на государственном и иностранном языках. |
| В результате освоения дисциплины обучающийся должен | |
| 3.1. | Знать: |
|---|---|
| 3.1.1. | Основные принципы математической логики, теории множеств и теории графов. Формулы алгебры высказываний. Методы алгебраических преобразований. Основы языка и алгебры предикатов. Основные принципы теории множеств. |
| 3.2. | Уметь: |
| 3.2.1. | Применять логические операции, формулы логики, законы алгебры логики, алгоритмы в графах. Формулировать задачи логического характера и применять средства математической логики для их решения. |
| 3.3. | Иметь навыки и (или) опыт деятельности (владеть): |
| 3.3.1. | Не предусмотрено. |
4. Структура и содержание дисциплины
| Код занятия | Наименование разделов и тем | Вид занятия | Семестр | Часов | Компетенции | Литература |
|---|---|---|---|---|---|---|
| Раздел 1. Раздел 1. Введение в теорию множеств. | ||||||
| 1.1. | Основные понятия и определения теории множеств. Основные операции над множествами. | Лекции | 4 | 2 | ОК 01., ОК 02., ОК 09. | Л1.1, Л2.1 |
| 1.2. | Множества. Операции над множествами. Диаграммы Эйлера-Венна. | Практические | 4 | 2 | ОК 01., ОК 05. | Л1.1, Л2.1 |
| 1.3. | Формула включения и исключения.Бинарные отношения. | Лекции | 4 | 2 | ОК 01., ОК 02. | Л1.1, Л2.1 |
| 1.4. | Бинарные отношения. Свойства бинарных отношений. | Практические | 4 | 4 | ОК 01., ОК 02. | Л1.1, Л2.1 |
| 1.5. | Множества. Декартово произведение множеств. Бинарные отношения. | Сам. работа | 4 | 2 | ОК 02., ОК 09. | Л1.1, Л2.1 |
| Раздел 2. Раздел 2. Классическая логика высказываний. | ||||||
| 2.1. | Высказывания. Логические связки высказываний. Исчисление высказываний. | Лекции | 4 | 2 | ОК 01., ОК 02. | Л1.2, Л1.1, Л2.1 |
| 2.2. | Булева алгебра. Принцип подстановки. Законы булевой алгебры. | Лекции | 4 | 2 | ОК 01., ОК 02., ОК 09. | Л1.2, Л1.1, Л2.1 |
| 2.3. | Составление таблиц истинности. Доказательство эквивалентности формул. | Практические | 4 | 4 | ОК 01., ОК 02., ОК 05. | Л1.2, Л2.1 |
| 2.4. | Нормальные формы булевых функций. | Лекции | 4 | 2 | ОК 01., ОК 02., ОК 04. | Л1.2, Л2.1 |
| 2.5. | Представление логических функций в виде СДНФ, СКНФ. | Практические | 4 | 2 | ОК 01., ОК 04., ОК 09. | Л1.2, Л2.1 |
| 2.6. | Законы булевой алгебры. Таблицы истинности. СДНФ,СКНФ. | Сам. работа | 4 | 2 | ОК 01., ОК 02., ОК 09. | Л1.2, Л2.1 |
| Раздел 3. Раздел 3. Логика предикатов. | ||||||
| 3.1. | Приложение логики предикатов в теории множеств. | Лекции | 4 | 2 | ОК 01., ОК 02., ОК 05. | Л1.2, Л1.1, Л2.1 |
| 3.2. | Исчисление одноместных предикатов. | Лекции | 4 | 2 | ОК 02., ОК 05. | Л1.2, Л1.1, Л2.1 |
| 3.3. | Нахождение области определения и истинности предиката. | Практические | 4 | 2 | ОК 01., ОК 02. | Л1.2, Л1.1, Л2.1 |
| 3.4. | Многоместные предикаты. Формулы с кванторами. | Лекции | 4 | 2 | ОК 01., ОК 02. | Л1.2, Л2.1 |
| 3.5. | Построение отрицаний к предикатам, содержащим кванторные операции. | Практические | 4 | 2 | ОК 02. | Л1.2, Л2.1 |
| 3.6. | Утверждения с предикатами. Формулы с кванторами. | Сам. работа | 4 | 2 | ОК 02., ОК 04. | Л1.2, Л2.1 |
| Раздел 4. Раздел 4. Введение в теорию графов. | ||||||
| 4.1. | Основные определения теории графов. Некоторые виды графов. | Лекции | 4 | 2 | ОК 01., ОК 02. | Л1.1, Л2.2 |
| 4.2. | Операции над графами. Графы и матрицы. | Лекции | 4 | 2 | ОК 02., ОК 09. | Л1.1, Л2.2 |
| 4.3. | Деревья. Ориентированные, бинарные деревья. Обход графа по глубине и ширине. Гамильтоновы циклы. Задача комивояжера. Эйлеровы циклы. | Лекции | 4 | 2 | ОК 01., ОК 05. | Л1.1, Л2.2 |
| 4.4. | Восстановление графа по матрице смежности (инцидентности). | Практические | 4 | 2 | ОК 02. | Л1.1, Л2.2 |
| 4.5. | Решение задачи комивояжера методом ветвей и границ. | Практические | 4 | 4 | ОК 04. | Л1.1, Л2.2 |
| 4.6. | Раскраска вершин и ребер графов. | Практические | 4 | 2 | ОК 02., ОК 09. | Л1.1, Л2.2 |
| 4.7. | Графы. Основные понятия и построения. | Сам. работа | 4 | 2 | ОК 02. | Л1.1, Л2.2 |
| Раздел 5. Раздел 5. Элементы теории алгоритмов. | ||||||
| 5.1. | Основные определения теории алгоритмов. Машина Тьюринга. | Лекции | 4 | 2 | ОК 02., ОК 05. | Л1.1, Л2.1 |
5. Фонд оценочных средств
| 5.1. Контрольные вопросы и задания для проведения текущего контроля и промежуточной аттестации по итогам освоения дисциплины |
| Оценочные материалы для текущего контроля (Контрольная работа №1, №2, №3) размещены в онлайн-курсе на образовательном портале https://portal.edu.asu.ru/course/view.php?id=6266 Контрольные вопросы для проведения промежуточной аттестации по итогам освоения дисциплины: Тестовые задания (выбор одного из вариантов) 1) Как называется множество, состоящее из тех и только тех элементов, которые принадлежат хотя бы одному из данных множествам? a) Объединением множеств b) Пересечением множеств c) Дополнением исходного множества до универсального d) Разностью множеств 2) Как называется закон булевой алгебры, задаваемый следующими формулами? a∧b=b∧a a∨b=b∨a a) Дистрибутивность b) Идемпотентность c) Коммутативность d) Ассоциативность 3) Как называется форма K_1 x_1,K_2 x_2,…,K_n x_n (M) содержащая цепочку кванторов K_1 x_1,K_2 x_2,…,K_n x_n (префикс) и следующую за ней приведенную формулу без кванторов M? a) Общезначимая формула b) Приведенная нормальная форма c)Элементарная форма d) Правильно построенная формула 4) Как называется формула с предикатами, истинная на всех интерпретациях? a) Общезначимой b) Замкнутой c) Выполнимой d) Противоречивой 5) Как называется логическая операция, таблица истинности которой изображена на рисунке? A B A∨B 0 0 0 0 1 1 1 0 1 1 1 1 a) Дизъюнкция b) Импликация c) Конъюнкция d) Отрицание 6) Как называется матрица с p строками и (каждая строка соответствует одной из вершин графа) и q столбцами (каждый столбец соответствует одному из ребер графа), элементы которой определяются правилом: b_ij={-1,если ребро e_i входит в вершину v_i, 1,если ребро e_i выходит из вершины v_i, i=1,2,…,p,j=1,2,…,q 2,если ребро e_i петля из вершины v_i, 0,если e_i и v_i не инцидентны.} a) Матрица инцидентности ориентированного графа b) Матрица инцидентности неориентированного графа c) Матрица смежности неориентированного графа d) Матрица смежности ориентированного графа 7) Как называется выражение ∃xP(x) – истинное высказывание, если, по крайней мере, для одного значения аргумента x из W предикат P(x) истинный? a) Формула с квантором существования b) Общезначимая формула c) Формула в приведенной форме d) Формула с квантором всеобщности 8) Какие операции может содержать формула в приведенной форме? a) ∧ b) - c) → d) ∨ 9) Как называется закон булевой алгебры, задаваемый следующими формулами? (a∨b) ̅=a ̅∧b ̅ (a∧b) ̅=a ̅∨b ̅ a) Идемпотентность b) Коммутативность c) Ассоциативность d) Законы двойственности (правила де Моргана) 10) Какими свойствами обладает отношение эквивалентности? a) Рефлексивность, симметричность, транзитивность b) Симметричность, транзитивность, полнота c) Рефлексивность, симметричность, полнота d) Рефлексивность, антисимметричность, транзитивность 11) Как называется множество, не содержащее ни одного элемента? a) Собственным подмножеством b) Подмножеством c) Универсальным множеством d) Пустым множеством 12) Как называется число ребер, входящих в маршрут с учетом повторений? a) Радиусом графа b) Диаметром графа c) Длиной маршрута d) Мостом 13) Как называется множество, состоящее из тех и только тех элементов, которые принадлежат обоим исходным множествам? a) Разностью множеств b) Объединением множеств c) Пересечением множеств d) Дополнением исходного множества до универсального 14) Как называется представление булевой функции в виде дизъюнкции конечного числа попарно различимых конъюнктивных термов? a) Двойственной булевой функцией b) Элементарной конъюнкцией c) Дизъюнктивной нормальной формой d) Совершенной формой 15) Как называется квадратная матрица с p строками и p столбцами (каждый столбец соответствует одному из ребер графа), элементы которой определяются правилом: a_ij={1,если в орграфе есть дуга (v_i,v_j ), i,j=1,2,…,p. 0,в противном случае} a) Матрица смежности ориентированного графа b) Матрица смежности неориентированного графа c) Матрица инцидентности неориентированного графа d) Матрица инцидентности ориентированного графа Правильные ответы: 1) a 2) c 3) b 4) a 5) a 6) a 7) a 8) a, b, d 9) d 10) a 11) d 12) c 13) c 14) c 15) a Критерии оценивания заданий к зачету Каждое задание оценивается 1 баллом. Оценивание теста в целом: «зачтено» – верно выполнено более 60% заданий; «не зачтено» – верно менее 60% заданий. |
| 5.2. Темы письменных работ для проведения текущего контроля (эссе, рефераты, курсовые работы и др.) |
| Не предусмотрено. |
| 5.3. Фонд оценочных средств для проведения промежуточной аттестации |
| Процедура проведения зачета (Может включать несколько блоков оценивания): Оценка успеваемости студентов согласно положению о балльно-рейтинговой системе оценки успеваемости обучающихся по дисциплинам программ подготовки специалистов среднего звена профессионального образования (приказ №1594/п от 03.11.2022г.) осуществляется в ходе текущего и промежуточного контроля. Процедура проведения предполагает два блока оценивания: 1) блок на выявление практических навыков (проводится очно, на занятиях в течении учебного года). Представляет собой текущий рейтинг студента Rтек. 2) блок на проверку общих знаний, связанных с проверкой теоретического материала (итоговый тест). Выполняется студентом который претендует на более высокую отметку по сравнению с рекомендованной ему в качестве «автомата» за текущую успеваемость по дисциплине. Представляет собой экзаменационный рейтинг Rзач. Критерии оценивания: 1) за выполнение первого блока заданий, студент может получить максимум 100 баллов. Оценка за второй блок, представляет собой индивидуальную рейтинговую оценку студента по дисциплине (Rтек). Текущий рейтинг студента Rтек, вычисленное перед началом сессии, называется семестровым рейтингом студента и обозначается в технологической карте по дисциплине Rсем. Зачет «автоматом» выставляется студенту при достижении им Rсем рейтинга 50 баллов и более. 2) за выполнение второго блока, представляющего собой тест множественного выбора, состоящий из 15 вопросов, студент может получить максимум 15 первичных баллов (по 1 баллу за каждый правильный ответ). В тесте встречаются вопросы с выбором одного варианта ответа, выбором нескольких вариантов ответов и вопросы открытого типа. В вопросах с выбором одного ответа, студент либо выбирает правильный ответ и получает 1 балл, либо выбирает не правильный ответ и получает 0 баллов. В вопросах с выбором нескольких вариантов ответов, при выборе всех правильных ответов, студент получает 1 балл. Если выбирает не все правильные ответы, то начисленный балл рассчитывается исходя из процента указанных правильных ответов. Если же при выборе правильных ответов, будут выбраны и не правильный ответ, то за выбор неправильного ответа начисляется штраф 5%. В вопросах открытого типа, необходимо вписать правильный ответ (правильное понятие). В вопросах открытого типа, за правильный ответ студент может набрать 1 балл. За неправильный ответ 0 баллов. Всего в банке тестовых заданий 40 (указывается фактическое количество в банке) тестовых задания. На выполнение теста отводится 20 минут. При прохождении теста, студент может пропустить вопросы в случае возникновения трудностей. И вернуться в оставшееся время. Максимально за тест можно получить 100 баллов, согласно шкале перевода: 50-100 баллов (оценка «зачтено») - 50-100% правильных ответов 0-49 баллов (оценка «не зачтено») - 0-49% правильных ответов |
| Приложения |
|
Приложение 1.
Контроль.docx
Приложение 2.
ФОС_Дискр._мат._ИСиП_2023.docx
|
6. Учебно-методическое и информационное обеспечение дисциплины
| 6.1. Рекомендуемая литература | ||||
| 6.1.1. Основная литература | ||||
| Авторы | Заглавие | Издательство, год | Эл. адрес | |
| Л1.1 | Палий И. А. | Дискретная математика и математическая логика: учебное пособие для среднего профессионального образования | Юрайт, 2021 | urait.ru |
| Л1.2 | В. И. Скорубский, В. И. Поляков, А. Г. Зыков | Математическая логика : учебник и практикум для среднего профессионального образования | Юрайт, 2021 | urait.ru |
| 6.1.2. Дополнительная литература | ||||
| Авторы | Заглавие | Издательство, год | Эл. адрес | |
| Л2.1 | Вечтомов Е. М., Широков Д. В. | Математика: логика, теория множеств и комбинаторика: учебное пособие для среднего профессионального образования | Юрайт, 2021 | urait.ru |
| Л2.2 | Клековкин Г. А., Коннова Л. П., Коннов В. В. | Геометрическая теория графов: учебное пособие для среднего профессионального образования | Юрайт, 2021 | urait.ru |
| 6.2. Перечень ресурсов информационно-телекоммуникационной сети "Интернет" | ||||
| Название | Эл. адрес | |||
| Э1 | Дискретная математика с элементами математической логики (ИСиП, 9 кл., 11 кл., преп. Лапыгин М.К.) | portal.edu.asu.ru | ||
| 6.3. Перечень программного обеспечения | ||||
| Список программного обеспечения Операционная система Windows и/или AstraLinux Специализированное и общее ПО Open Office или Libreoffice 3D Canvas Blender Visual Studio Community Python c расширениями PIL, Py OpenGL FAR XnView 7-Zip AcrobatReader GIMP Inkscape Paint.net VBox Mozila FireFox Chrome Eclipse (PHP,C++, Phortran) VLC QTEPLOT Visual Studio Code https://code.visualstudio.com/License/ Notepad++ https://notepad-plus-plus.org/ | ||||
| 6.4. Перечень информационных справочных систем | ||||
| Информационная справочная система: - СПС КонсультантПлюс (инсталлированный ресурс АлтГУ или http://www.consultant.ru/). Профессиональные базы данных: - Электронная библиотечная система Алтайского государственного университета (http://elibrary.asu.ru/); - Научная электронная библиотека elibrary (http://elibrary.ru); - Образовательная платформа «Юрайт» (https://urait.ru). | ||||
7. Материально-техническое обеспечение дисциплины
| Аудитория | Назначение | Оборудование |
|---|---|---|
| 519М | электронный читальный зал с доступом к ресурсам «ПРЕЗИДЕНТСКОЙ БИБЛИОТЕКИ имени Б.Н. Ельцина» - помещение для самостоятельной работы | Учебная мебель на 46 посадочных мест; 1 Флипчарт; компьютеры; ноутбуки с подключением к информационно-телекоммуникационной сети "Интернет" и доступом в электронную информационно-образовательную среду; стационарный проектор: марка Panasonic, модель PT-ST10E; стационарный экран: марка Projecta, модель 10200123; система видеоконференцсвязи Cisco Telepresence C20; конгресс система Bosch DCN Next Generation; 8 ЖК-панелей |
| 310Н | методический кабинет, помещение для хранения и профилактического обслуживания учебного оборудования | Рабочие места преподавателей; стеллаж; шкафы с бумагами и учебно-методической документацией. |
| 203Н | кабинет математики; кабинет математических дисциплин; кабинет статистики; кабинет математики и информатики; кабинет информационных систем в профессиональной деятельности – учебная аудитория для проведения занятий всех видов (дисциплинарной, междисциплинарной и модульной подготовки), групповых и индивидуальных консультаций, текущего контроля и промежуточной аттестации | Учебная мебель на 54 посадочных места; рабочее место преподавателя; маркерная доска – 1 ед.; компьютер (модель: Aquarius) с доступом в информационно-телекоммуникационную сеть Интернет – 1 ед.; интерактивная доска (марка: Smart) – 1 ед.; проектор (марка: Smart) – 1 ед..; калькуляторы; чертежные принадлежности; модели геометрических тел; раздаточный дидактический материал; учебно-методические издания; таблицы. |
| Учебная аудитория | для проведения занятий лекционного типа, занятий семинарского типа (лабораторных и(или) практических), групповых и индивидуальных консультаций, текущего контроля и промежуточной аттестации, курсового проектирования (выполнения курсовых работ), проведения практик | Стандартное оборудование (учебная мебель для обучающихся, рабочее место преподавателя, доска) |
8. Методические указания для обучающихся по освоению дисциплины
| При реализации учебной дисциплины используются активные и интерактивные формы проведения занятий. При проведении лекционных занятий: лекция–визуализация (презентация), лекция-беседа, проблемная лекция и лекция с запланированными ошибками. При проведении практических занятий: ситуационные методы (решение ситуационных задач, требующих комплексного применения полученных знаний), работа в малых группах. В самостоятельной работе студентов использование интерактивных форм заключается в выполнении индивидуальных заданий. Планирование и организация времени, необходимого для изучения дисциплины. Важным условием успешного освоения дисциплины "Дискретная математика с элементами математической логики" является создание системы правильной организации труда, позволяющей распределить учебную нагрузку равномерно в соответствии с графиком образовательного процесса. Большую помощь в этом может оказать составление плана работы на семестр, месяц, неделю, день. Его наличие позволит подчинить свободное время целям учебы, что позволит сделать обучение более эффективным. Наличие самоконтроля является необходимым условием успешной учебы. Все задания к практическим занятиям, а также задания, вынесенные на самостоятельную работу, рекомендуется выполнять непосредственно после соответствующей темы лекционного курса, что способствует лучшему усвоению материала, позволяет своевременно выявить и устранить "пробелы" в знаниях. Подготовка к лекциям. В ходе лекционных занятий вести конспектирование учебного материала. Обращать внимание на категории, формулировки, раскрывающие содержание тех или иных явлений и процессов, научные выводы и практические рекомендации, положительный опыт в ораторском искусстве. Желательно оставить в рабочих конспектах поля, на которых делать пометки из рекомендованной литературы, дополняющие материал прослушанной лекции, а также подчеркивающие особую важность тех или иных теоретических положений. Целесообразно разработать собственную систему сокращений, аббревиатур и символов. Задавать преподавателю уточняющие вопросы с целью уяснения теоретических положений, разрешения спорных ситуаций. Дорабатывать свой конспект лекции, делая в нем соответствующие записи из литературы, рекомендованной преподавателем и предусмотренной учебной программой - в ходе подготовки к семинарам изучить основную литературу, ознакомиться с дополнительной литературой, новыми публикациями в периодических изданиях: журналах, газетах и т.д. При этом учесть рекомендации преподавателя и требования учебной программы. Конспектирование лекций – сложный вид вузовской аудиторной работы, предполагающий интенсивную умственную деятельность студента. Конспект является полезным тогда, когда записано самое существенное и сделано это самим обучающимся. Не надо стремиться записать дословно всю лекцию. Такое "конспектирование" приносит больше вреда, чем пользы. Целесообразно вначале понять основную мысль, излагаемую лектором, а затем записать ее. Желательно запись осуществлять на одной странице листа или оставляя поля, на которых позднее, при самостоятельной работе с конспектом, можно сделать дополнительные записи, отметить непонятные места. Подготовка к практическим занятиям. Изучив конкретную тему, обучающийся может определить, насколько хорошо он в ней разобрался. Если какие-то моменты остались непонятными, целесообразно составить список вопросов и на занятии задать их преподавателю. Практические занятия предоставляют студенту возможность творчески раскрыться, проявить инициативу и развить навыки публичного ведения дискуссий и общения, сформировать определенные навыки и умения и т.п. Подготовку к каждому практическому занятию студент должен начать с ознакомления с планом практического занятия, который отражает содержание предложенной темы. Тщательное продумывание и изучение вопросов плана основывается на проработке текущего материала лекции, а затем изучения обязательной и дополнительной литературы, рекомендованной к данной теме. В процессе подготовки к практическим занятиям, студентам необходимо обратить особое внимание на самостоятельное изучение рекомендованной литературы. При всей полноте конспектирования лекции в ней невозможно изложить весь материал из-за лимита аудиторных часов. Поэтому самостоятельная работа с учебниками, учебными пособиями, научной, справочной литературой, материалами периодических изданий и Интернета является наиболее эффективным методом получения дополнительных знаний, позволяет значительно активизировать процесс овладения информацией, способствует более глубокому усвоению изучаемого материала, формирует у студентов свое отношение к конкретной проблеме. Рекомендации по работе с литературой. Работу с литературой целесообразно начать с изучения общих работ по теме, а также учебников и учебных пособий. Если для разрешения поставленной задачи требуется изучение некоторых фрагментов текста, то используется метод выборочного чтения. При работе с источниками и литературой важно уметь: • сопоставлять, сравнивать, классифицировать, группировать, систематизировать информацию в соответствии с определенной учебной задачей; • обобщать и оценивать полученную информацию; • фиксировать основное содержание, формулировать, устно и письменно, основную идею, составлять план, выделять основные формулы, уметь выводить их на основе полученных знаний; • работать в разных режимах (индивидуально, в паре, в группе), взаимодействуя друг с другом; • пользоваться справочными материалами; • обращаться за помощью, дополнительными разъяснениями к преподавателю, другим студентам; • повторять или перефразировать реплику собеседника в подтверждении понимания его высказывания или вопроса; • обратиться за помощью к собеседнику (уточнить вопрос, переспросить и др.). Подготовка к промежуточной и итоговой аттестации. При изучении данной дисциплины с учетом использования балльно-рейтинговой системы студент должен сдать контрольные работы. Итоговая аттестация проводится в форме зачета. В целом оценка ставится, как взвешенное среднее оценок полученных во время текущего контроля и оценки, полученных при ответе на вопросы билета, с учетом весовых коэффициентов. При подготовке к промежуточной аттестации целесообразно: • внимательно изучить перечень вопросов и определить, в каких источниках находятся сведения, необходимые для ответа на них; • внимательно прочитать рекомендованную литературу; • составить краткие конспекты ответов (планы ответов); • решать основные типовые задачи. |