МИНИСТЕРСТВО НАУКИ И ВЫСШЕГО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ

ПОЛИТЕХНИЧЕСКИЙ ИНСТИТУТ (ФИЛИАЛ)

ФЕДЕРАЛЬНОГО ГОСУДАРСТВЕННОГО БЮДЖЕТНОГО

ОБРАЗОВАТЕЛЬНОГО УЧРЕЖДЕНИЯ ВЫСШЕГО ОБРАЗОВАНИЯ

«ДОНСКОЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ»

В Г. ТАГАНРОГЕ РОСТОВСКОЙ ОБЛАСТИ

(ПИ (филиал) ДГТУ в г. Таганроге)

ЦМК "Общих гуманитарных, социально-экономических, математических и естественнонаучных дисциплин"

Закреплена за ЦМК

рабочая программа дисциплины (модуля)

Дискретная математика с элементами математической логики

«____»______________ 2023 г.

Директор

УТВЕРЖДАЮ

Учебный план

090207_51-16-2-11-23ИС.plx

Информационные системы и программирование

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

______________

А.Б. Соловьев

личная подпись

инициалы, фамилия

Документ подписан

с использованием

простой электронной

подписи для ЭИОС

самостоятельная работа

0

аудиторные занятия

36

Часов по учебному плану

Форма обучения

очная

Квалификация

специалист по информационным системам

36

в том числе:

Распределение часов дисциплины по семестрам

Семестр

(<Курс>.<Семестр на курсе>)

2 (1.2)

Итого

Недель

18 4/6

Вид занятий

УП

РП

УП

РП

Лекции

18

18

18

18

Практические

18

18

18

18

Итого ауд.

36

36

36

36

Кoнтактная рабoта

36

36

36

36

Итого

36

36

36

36

Документ подписан простой электронной подписью

Информация о владельце:

ФИО: Болдырев Антон Сергеевич

Должность: Директор

Дата подписания: 15.01.2024 11:10:50

Уникальный программный ключ:

9c542731014dd7196f5752b7fa57c524495323a0

УП: 090207_51-16-2-11-23ИС.plx

стр. 2

Рабочая программа составлена:

ФИО

Московченко Н.Н.

_______________________

Дискретная математика с элементами математической логики

Рабочая программа дисциплины

разработана в соответствии с ФГОС СПО:

Федеральный государственный образовательный стандарт среднего профессионального образования по специальности 09.02.07 ИНФОРМАЦИОННЫЕ СИСТЕМЫ И ПРОГРАММИРОВАНИЕ (приказ Минобрнауки России от 09.12.2016 г. № 1547)

Информационные системы и программирование

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

составлена на основании учебного плана:

утвержденного учёным советом вуза от 30.03.2023 протокол № 9.

Протокол от 31.08.2021 г.  № 1   

Срок действия программы: 2021-2025 уч.г.

Председатель ЦМК "Общих гуманитарных, социально-экономических, математических и естественнонаучных дисциплин"

__  _________  2023 г. № ___

ЦМК "Общих гуманитарных, социально-экономических, математических и естественнонаучных дисциплин"

Рабочая программа одобрена на заседании ЦМК

Председатель ЦМК

__________________

Бычкова Мария Владимировна

__________________

Андриян Оксана Вячеславовна

УП: 090207_51-16-2-11-23ИС.plx

стр. 3

Протокол заседания ЦМК «ЦМК "Общих гуманитарных, социально-экономических, математических и естественнонаучных дисциплин"» от __  _________  ____г. № ___

Рабочая программа по дисциплине «Дискретная математика с элементами математической логики» проанализирована и признана актуальной для исполнения в ____ - ____ учебном году.

Визирование РП для исполнения в очередном учебном году

Председатель ЦМК   ___________________

__  _________  ____г. № ___

Бычкова Мария Владимировна

стр. 4

УП: 090207_51-16-2-11-23ИС.plx

1. ЦЕЛИ ОСВОЕНИЯ ДИСЦИПЛИНЫ (МОДУЛЯ)

1.1

Примерная программа учебной дисциплины является частью подготовки математического и общего естественнонаучного цикла в соответствии с ФГОС по специальностям СПО 09.02.07 «Информационные системы и программирование»

2. МЕСТО ДИСЦИПЛИНЫ (МОДУЛЯ) В СТРУКТУРЕ ОБРАЗОВАТЕЛЬНОЙ ПРОГРАММЫ

Цикл (раздел) ОП:

2.1

Требования к предварительной подготовке обучающегося:

2.1.1

Математика

2.1.2

Физика

2.1.3

Теория вероятностей и математическая статистика

2.1.4

Компьютерная графика

2.1.5

Компьютерная графика

2.1.6

Теория вероятностей и математическая статистика

2.2

Дисциплины (модули) и практики, для которых освоение данной дисциплины (модуля) необходимо как предшествующее:

2.2.1

Основы работы Оператора электронно-вычислительных и вычислительных машин

2.2.2

Основы проектирования баз данных

2.2.3

Теория вероятностей и математическая статистика

2.2.4

Информационные технологии и платформы разработки информационных систем

2.2.5

Архитектура аппаратных средств

2.2.6

Технология разработки программного обеспечения

2.2.7

Технические средства информатизации

2.2.8

Основы проектирования баз данных

2.2.9

Теория вероятностей и математическая статистика

2.2.10

Архитектура аппаратных средств

2.2.11

Технические средства информатизации

3. КОМПЕТЕНЦИИ ОБУЧАЮЩЕГОСЯ, ФОРМИРУЕМЫЕ В РЕЗУЛЬТАТЕ ОСВОЕНИЯ ДИСЦИПЛИНЫ (МОДУЛЯ)

ОК 10.: Пользоваться профессиональной документацией на государственном и иностранном языках.

Знать:

Уметь:

Владеть:

ОК 09.: Использовать информационные технологии в профессиональной деятельности.

Знать:

Уметь:

Владеть:

ОК 05.: Осуществлять устную и письменную коммуникацию на государственном языке с учетом особенностей социального и культурного контекста.

Знать:

Уметь:

Владеть:

ОК 04.: Работать в коллективе и команде, эффективно взаимодействовать с коллегами, руководством, клиентами.

Знать:

Уметь:

Владеть:

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

Знать:

Уметь:

Владеть:

ОК 01.: Выбирать способы решения задач профессиональной деятельности, применительно к различным контекстам.

стр. 5

УП: 090207_51-16-2-11-23ИС.plx

Знать:

Уметь:

Владеть:

В результате освоения дисциплины (модуля) обучающийся должен

3.1

Знать:

3.1.1

-основные понятия и приемы дискретной математики;

3.1.2

-логические операции, формулы логики, законы алгебры логики;

3.1.3

-основные классы функций, полнноту множества функций, теорему Поста;

3.1.4

-основные понятия теории множеств, теоретико - множественные операции и их связь с логическими операциями;

3.1.5

-логику предикатов;

3.1.6

элементы теории отображений и алгебры подстановок;

3.1.7

-метод математической индукции;

3.1.8

-алгоритмическое перечисление основных комбинаторных объектов.

3.2

Уметь:

3.2.1

–формулировать задачи логического характера и применять средства математической логики для их решения;

3.2.2

знать:

3.2.3

-основные принципы математической логики, теории множеств и теории алгоритмов;

3.2.4

-формулы алгебры высказываний; методы минимизации алгебраических преобразований;

3.2.5

-основы языка и алгебры предикатов

3.3

Владеть:

Наименование разделов и тем /вид занятия/

Литература

Часов

Компетен-

ции

Семестр / Курс

Код занятия

Примечание

4. СТРУКТУРА И СОДЕРЖАНИЕ ДИСЦИПЛИНЫ (МОДУЛЯ)

Интеракт.

Раздел 1. Высказывания и операции над ними. 

1.1

Высказывания и операции над ними. Таблица истинности /Лек/

1

2

0

1.2

Практическое занятие 1. Составление таблиц истинности

/Пр/

1

2

0

1.3

Булевы функции.. Элементарные конъюнкция и дизъюнкция и их свойства. Эквивалентность и преобразование формул Нормальные формы. Совершенные нормальные формы. Тупиковые формы. Алгоритм построения совершенных нормальных форм Полином Жегалкина. Алгоритм построения полиномов Жегалкина. /Лек/

1

2

0

1.4

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

/Пр/

2

2

0

Раздел 2. Основные положения теории множеств

2.1

Основные положения теории множеств Теоретико-множественные операции и их связь с логическими операциями /Лек/

1

2

0

2.2

Практическое занятие 4. Выполнение операций над множествами Двойственные функции

/Пр/

1

2

0

2.3

Самостоятельная работа 4. Монотонные функции

Теорема Поста

/Пр/

0

2

0

стр. 6

УП: 090207_51-16-2-11-23ИС.plx

Раздел 3. Элементы комбинаторного анализа

3.1

Основные правила комбинаторики. Комбинации элементов с повторениями. Бином Ньютона.

/Лек/

2

2

0

3.2

Практическое занятие 5. Выполнение комбинаторных действий. Использование бинома Ньютона.

/Пр/

1

2

0

3.3

Самостоятельная работа 5. Треугольник Люка. треугольник Фибоначчи, треугольник Каталана, треугольник Эйлера

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

/Пр/

0

2

0

3.4

Отношения. Матрица бинарного отношения. Специальные бинарные отношения.

/Лек/

1

2

0

3.5

Практическое занятие 6. Составление матриц отношений, исследование свойств отношений

/Пр/

1

2

0

3.6

Самостоятельная работа 6. Принцип математической индукции(делимость). Схема Горнера. Предваренная нормальная форма. Стандартная форма Скулема

/Пр/

2

2

0

Раздел 4. Логика предикатов

4.1

Предикаты. Применение предикатов в алгебре. Булева алгебра предикатов. Кванторы.Формулы логики предикатов. Равносильные формулы логики предикатов. /Лек/

1

2

0

4.2

Практическое занятие 7. Преобразование формул логики предикатов /Пр/

1

2

0

4.3

Самостоятельная работа 7.  /Пр/

0

2

0

4.4

Приведенные и нормальные формы в логике предикатов. Исчисление предикатов /Лек/

1

2

0

4.5

Практическое занятие 8. Равносильные преобразования предикатов /Пр/

1

2

0

4.6

решение предикатов /Пр/

0

2

0

Раздел 5. Элементы теории графов

5.1

Понятие графа. Виды и способы задания графов. Изоморфизм графов. Плоские графы. Степень вершин, обходы и основы графов. /Лек/

2

2

0

5.2

Составление основных матриц графа. /Пр/

1

2

0

5.3

Решение примеров /Пр/

0

2

0

5.4

Эйлеров путь, условие существования Эйлерова пути. Изоморфизм графов. Гамильтонов цикл. Условие существования Гамильтонова пути в графе. /Лек/

1

2

0

5.5

Построение графов по их матрицам /Пр/

1

2

0

стр. 7

УП: 090207_51-16-2-11-23ИС.plx

5.6

Построение изоморфных графов по заданным их свойствам /Пр/

0

2

0

5.7

Понятие дерева. Код дерева, построение дерева по его коду. /Лек/

1

2

0

5.8

Проверка деревьев, построение деревьев.  /Пр/

1

2

0

5.9

Решение примеров. Исследование свойств графов, построение графов по данным свойствам. /Пр/

0

2

0

5.10

Методы поиска кратчайших путей в графах. Метод Дейкстеры, матричный метод. Планарные графы. Условие планарности графа. Исследование графа на планарность. Раскраска графа. /Лек/

1

2

0

5.11

Кратчайший путь между двумя пунктами. Определение максимального потока. Метод ветвей и границ. Раскраска графа. /Пр/

1

2

0

5.12

Задача определения максимального потока. Задача единого среднего. Транспортная задача в сетевой постановке. /Пр/

0

2

0

5.13

Кодирование как способ представления информации. Кодирование и декодирование. Коды Хемминга. Алгоритм построения кода Хемминга /Лек/

1

2

0

5.14

Понятие конечного автомата. Опреджеление конечного автомата. Способы задания конечного автомата. Примеры конечного автомата. Каноническое уравнение конечного автомата. /Лек/

2

2

0

5.15

Проверка однозначной декодируемости. Построение кодового слова по методу Хемминга Построение диаграммы Мура по заданной таблице. Построение диаграммы Мура и таблицы автомата по системе булевых функций. /Пр/

1

2

0

5.16

Построение автомата Мура. Задание автомата системой булевых функций. По диаграмме Мура составление таблицы и системы булевых функций. Решение задач. Составление диаграммы Мура по каноническому уравнению автомата. Тезис Черча-Тьюринга /Пр/

1

2

0

Раздел 6. Вычисление теории алгоритмов

6.1

Вычислимые функции и алгоритмы. Теория рекурсивных функций. Нормальный алгоритм Маркова. Машины Тьюринга /Лек/

1

2

0

6.2

Нахождение функций в рекурсивной форме для двухместной функции. Применение операторов примитивной рекурсии к простейшим функциям. Переработка заданных «слов» по алгоритму Маркова

Самостоятельная работа  /Пр/

1

2

0

стр. 8

УП: 090207_51-16-2-11-23ИС.plx

6.3

Выяснение примитивной-рекурсивности функций. Нахождение функций в рекурсивной форме для трехместных функций.Построение нормального алгоритма U над алфавитом А по заданным требованиям.

/Пр/

1

2

0

6.4

Нормальный алгоритм Маркова. /Лек/

1

2

0

5. ОЦЕНОЧНЫЕ МАТЕРИАЛЫ (ОЦЕНОЧНЫЕ СРЕДСТВА)

для текущего контроля успеваемости, промежуточной аттестации по итогам освоения дисциплины

5.1. Контрольные вопросы и задания

1.Что называется множеством? Как его обозначают? Какие способы задания множеств используются? Что называется подмножеством?

2.Перечислите основные операции , выполняются на множествах?

3.Какие основные символы, используемые в теории множеств, вы знаете?

4.Какое множество называется универсальным?

5.Что представляет собой диаграмма Эйлера-Венна?

6.Проиллюстрируйте с помощью диаграммы Эйлера-Венна операции на трех  множествах?

7.Каковы соотношения между множествами и составными высказываниями?

8.Сформулируйте и докажите основные тождества алгебры множеств.

9.Что называется кортежем и какие кортежи называются равными?

10.Что называется декартовым произведением множеств, декартовой степенью множества, бинарным отношением на множестве?

11.Назовите основные свойства бинарных отношений.

12.Дайте определения рефлексивных, транзитивных, симметричных отношений и их подвидов, эквивалентного отношения.

13.Дайте определение отображения множеств, мощности множеств, частных случаев отображения множеств.

14.Дайте определение функции, ее частных случаев.

15.Что называется высказыванием? Какое высказывание называется истинным, а какое ложным?

16.Что называется составным высказыванием?

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

17.Какие основные символы используются в теории высказываний?

Какие связки простейшие? Назовите другие связки.

18.Что называется таблицей истинности высказываний и как она строится? Как еще называется эта таблица?

19.Какие существуют логические отношения между высказываниями?

20.Сформулируйте основные законы алгебры высказываний. Как их доказать?

21.Что такое булева функция? Как строится таблица истинности булевых функций?

22.Что представляют собой ДНФ и КНФ?

23.Приведите правило преобразования формул в СДНФ и СКНФ.

24.Как булевы функции связаны с формулами алгебры высказываний?

25.Дайте определение многочлена Жегалкина и сформулируйте теорему Жегалкина.

26.Сформулируйте первый алгоритм построения многочлена Жегалкина булевой функции.

27.В чем состоит метод неопределенных коэффициентов для построения многочлена Жегалкина?

28.Какой многочлен Жегалкина называется нелинейным?

29.Каков алгоритм определения линейности (нелинейности) булевой функции?

30.Основные понятия теории графов. Вершины, ребра, граф, орграф, дуги, начальная и конечная вершины дуги.  Петля, кратные ребра, изолированная вершина,. Изоморфизм графов. Маршрут, Замкнутый маршрут, цепь, простая цепь, простой цикл. Путь , контур. Матричный способ задания графов. Матрицы смежности и инцидентности для графа и орграфа.

31.Связный граф, дерево. Сеть, узел, дуга. Код дерева. Построение кода дерева. Восстановление дерева по коду.

32.Задача определения кратчайшего пути. Метод присвоения меток. Помеченные и непомеченные узлы. Постоянные и временные метки.

33.Построение коммуникационной сети  минимальной длины.

34. Эйлеров  цикл. Критерий существования эйлерова цикла.  

35. Раскраска графов. Планарные графы. Теорема пяти красок.

36.Что называется комбинаторикой и для чего она используется?

37.Дайте  определение перестановок, размещений и сочетаний из n элементов по k элементов.

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

38.Что называется предикатом? Приведите примеры предикатов.

39.Какой предикат называется тождественно истинным, разрешимым, тождественно ложным?

40.Перечислите операции, которые можно осуществлять над предикатами.

41.Как применяются предикаты в алгебре?

42. Что такое множество истинности предиката?

43. Из чего состоит алфавит логики предикатов?

44. Что такое квантор?

45. Что называется формулой логики предикатов?

стр. 9

УП: 090207_51-16-2-11-23ИС.plx

46. Сформулируйте основные правила построения формул

47.Сформулируйте основные правила перехода к новым равносильным формулам

48.Какая формула называется приведенной и ее смысл

49.Что называется исчислением предикатов?

50.Сформулируйте аксиомы исчисления предикатов

51.Сформулируйте правила вывода исчисления предикатов.

52. Что называется формулой логики предикатов? Сформулируйте основные правила построения формул. В чем состоит смысл термина «интерпретация» в логике предикатов?

53.Сформулируйте основные правила перехода к новым равносильным формулам.

Какая формула называется непротиворечивой, противоречивой, общезначимой?

Какая формула называется приведенной? Что такое приведенная форма?

54.Кодирование и декодирование. Основные понятия  алфавитное кодирование.

5.2. Темы письменных работ

5.3. Оценочные материалы (оценочные средства)

прилагается

5.4. Перечень видов оценочных средств

6. УЧЕБНО-МЕТОДИЧЕСКОЕ И ИНФОРМАЦИОННОЕ ОБЕСПЕЧЕНИЕ ДИСЦИПЛИНЫ (МОДУЛЯ)

6.1. Рекомендуемая литература

6.3.1 Перечень программного обеспечения

6.3.2 Перечень информационных справочных систем

7. МАТЕРИАЛЬНО-ТЕХНИЧЕСКОЕ ОБЕСПЕЧЕНИЕ ДИСЦИПЛИНЫ (МОДУЛЯ)

Специальные помещения представляют собой учебные аудитории для проведения всех занятий по дисциплине, предусмотренных учебным планом и содержанием РПД. Помещения укомплектованы специализированной мебелью и техническими средствами обучения согласно требованиям ФГОС, в т.ч.:

8. МЕТОДИЧЕСКИЕ УКАЗАНИЯ ДЛЯ ОБУЧАЮЩИХСЯ ПО ОСВОЕНИЮ ДИСЦИПЛИНЫ (МОДУЛЯ)