Государственное бюджетное образовательное учреждение

среднего профессионального образования города москвы

«МОСКОВСКИЙ КОЛЛЕДЖ УПРАВЛЕНИЯ И НОВЫХ ТЕХНОЛОГИЙ»

Одобрена

на заседании предметной (цикловой) комиссии «Технические дисциплины»,

протокол №_______

от _____________________ 201__г.

Председатель ___________ /Федосова Т.А./

                                              ^{(подпись)}                    

СОСТАВЛЕНА

на основе Федерального государственного образовательного стандарта по специальности 230113.51 Компьютерные системы и комплексы (базовая подготовка)

Зам. директора по УВР _____________ /Галдина Т.А/

                                                                 ^{(подпись)}                      

Составитель:

Алферова Жанна Олеговна, преподаватель Государственного бюджетного образовательного учреждения среднего профессионального образования города Москвы «Московский колледж управления и новых технологий».

Рецензент:

Коробейников Андрей Владимирович, преподаватель Государственного бюджетного образовательного учреждения среднего профессионального образования города Москвы «Московский колледж управления и новых технологий».

1. Паспорт рабочей программы учебной дисциплины

2. Структура и содержание учебной дисциплины

3. Условия реализации рабочей программы учебной дисциплины

4. Контроль и оценка результатов освоения учебной дисциплины

Вид учебной работы

Объем часов

Максимальная учебная нагрузка (всего)

126

Обязательная аудиторная учебная нагрузка (всего)

84

в том числе:

- лекции

50

- лабораторные работы

0

- практические занятия

34

- контрольные работы

0

- курсовая работа (если предусмотрена)

0

Самостоятельная работа обучающегося (всего)

42

в том числе:

- подготовка к аудиторным занятиям (домашнее задание)

16

- подготовка к практическим занятиям, написание рефератов.

26

- самостоятельная работа над курсовой работой (если предусмотрена)

0

- подготовка к промежуточной аттестации

10

Итоговая аттестация по дисциплине: 1 семестр – экзамен, 2 семестр – дифференцированный зачёт

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

Содержание учебного материала, лабораторные работы, практические занятия,

самостоятельная работа обучающихся

Объем часов

Уровень освоения

1

2

3

4

Введение

Содержание предмета «Дискретная математика», его значение для подготовки специалиста среднего звена, взаимосвязь с другими предметами учебного плана.
Базовые понятия математики, на которые опирается дискретная математика, история развития математики, предпосылки возникновения и истоки развития дискретной математики.

2

1,2,3

Раздел 1. Алгебра логики. Булевы функции

46

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

Содержание учебного материала

8

Суть высказываний. Основные операции над высказываниями.

4

1,2,3

Основные понятия алгебры высказываний. Основные логические операции. Таблицы истинности основных логических операций.

1,2,3

Построение таблиц истинности сложных высказываний.

1,2,3

Практические занятия:

1. Построение таблиц истинности сложных высказываний.

2

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

1. Предмет и задачи дискретной математики
2. История развития дискретной математики
3. Алгебра высказываний
4. Дискретная математика в лицах

2

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

Содержание учебного материала

3

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

2

1,2,3

Понятие тавтологии и противоречия.

1,2,3

Выполнимые и невыполнимые формулы.

1,2,3

Подготовка к самостоятельной работе (тестовому заданию), проработка материалов по лекциям. Примерные темы рефератов:

1. Применение алгебры высказываний при решении логических задач
2. Логика и математика

1

Тема 1.3. Булевы функции. Суперпозиция булевых функций

Содержание учебного материала

3

Основные понятия алгебры логики. Функции алгебры логики.

2

1,2,3

Элементарные функции алгебры логики. Способы задания логической функции.

1,2,3

Суперпозиция булевых функций. Двойственные булевы функции.

1,2,3

Подготовка к самостоятельной работе (тестовому заданию), проработка материалов по лекциям. Примерные темы рефератов:

1. Булевы функции
2. Суперпозиция булевых функций

1

Тема 1.4. Элементарные конъюнкции и дизъюнкции и их свойства

Содержание учебного материала

3

Булева переменная. Булева константа.

2

1,2,3

Понятие элементарной конъюнкции. Свойства элементарной конъюнкции, её ранг.

1,2,3

Понятие элементарной дизъюнкции. Свойства элементарной дизъюнкции.

1,2,3

Подготовка к самостоятельной работе (тестовому заданию), проработка материалов по лекциям. Примерные темы рефератов:

1. Канонические формы логических формул

1

Тема 1.5. Эквивалентность и преобразование формул

Содержание учебного материала

6

Понятие эквивалентности формул. Теоремы эквивалентности.

2

1,2,3

Свойства логических операций.

1,2,3

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

1,2,3

Практические занятия:

1. Эквивалентные преобразования формул.

2

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

1. Алгебра переключательных схем

2

Тема 1.6. Нормальные формы. Совершенные нормальные формы. Тупиковые формы

Содержание учебного материала

5

Дизъюнктивная нормальная форма (ДНФ). Конъюнктивная нормальная форма (КНФ). Теорема о существовании КНФ и ДНФ.

2

1,2,3

Совершенная дизъюнктивная нормальная форма (СДНФ). Совершенная конъюнктивная нормальная форма (СКНФ). Теоремы об СКНФ И СДНФ.

1,2,3

Тупиковые формы.

1,2,3

Практические занятия:

1. Построение СКНФ и СДНФ для заданных формул

2

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

1. Минимизация булевых функций

1

Тема 1.7. Алгоритмы построения совершенных нормальных форм

Содержание учебного материала

5

Алгоритм построения СДНФ с помощью таблицы истинности.

2

1,2,3

Алгоритм построения СКНФ с помощью таблицы истинности.

1,2,3

Построение СДНФ и СКНФ методом эквивалентных преобразований.

1,2,3

Практические занятия:

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

2

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

1. Логические схемы и схемотехника.

1

Тема 1.8. Полином Жегалкина. Алгоритмы построения полиномов Жегалкина

Содержание учебного материала

5

Понятие полинома Жегалкина. Теорема о существовании и единственности полинома Жегалкина. 

2

1,2,3

Алгоритмы построения полинома Жегалкина с помощью таблицы истинности.

1,2,3

Построение полинома Жегалкина методом неопределенных коэффициентов.

1,2,3

Практические занятия:

1. Построение полинома Жегалкина.

2

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

1. Применение полиномов в решении задач.

1

Тема 1.9. Операция замыка-ния. Основные замкнутые классы Т_о, Т₁, S, М, L

Содержание учебного материала

3

Замыкание множества. Свойства операции замыкания. Замкнутые множества. Основные замкнутые классы Т_о, Т₁, S, М, L. Мощность множества.

2

1,2,3

Понятие самодвойственной функции. Понятие монотонной функции. Понятие линейной функции.

1,2,3

Условия принадлежности функции основным замкнутым классам.

1,2,3

Подготовка к самостоятельной работе (тестовому заданию), проработка материалов по лекциям. Примерные темы рефератов:

1. Введение в теорию множеств

1

Тема 1.10. Полные системы операций

Содержание учебного материала

5

Понятие полной системы.

2

1,2,3

Исследование системы булевых функций на полноту.

1,2,3

Необходимое и достаточное условие полноты системы булевых функций (теорема Поста).

1,2,3

Практические занятия:

1. Исследование системы булевых функций на полноту

2

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

1. Системы операций.

1

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

12

Тема 2.1. Основные положения

Содержание учебного материала

6

Множество. Подмножество. Элемент множества. Равные множества. Пустое множество.

5

1,2,3

Конечные, счетные, континуальные множества.

1,2,3

Способы представления множеств.

1,2,3

Подготовка к самостоятельной работе (тестовому заданию), проработка материалов по лекциям. Примерные темы рефератов:

1. Основные понятия теории множеств.

1

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

Содержание учебного материала

6

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

3

1,2,3

Абсолютное дополнение. Диаграммы Эйлера – Венна.

1,2,3

Свойства операций над множествами. Функция принадлежности. Векторы.

1,2,3

Практические занятия.

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

2

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

1. Применение теории множеств в логике.

1

Раздел 3. Основы комбинаторики

14

Тема 3.1. Основные правила комбинаторики

Содержание учебного материала

4

Комбинаторика. Основные правила.

3

1,2,3

Упорядоченные множества.

1,2,3

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

1,2,3

Подготовка к самостоятельной работе (тестовому заданию), проработка материалов по лекциям. Примерные темы рефератов:

1. Этапы жизни великих математиков: Дж. Буль, Пост, Жегалкин, Эйлер, Форд.

1

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

Содержание учебного материала

6

Размещения. Формула для вычисления числа размещений.

3

1,2,3

Перестановки. Формула для вычисления числа перестановок.

1,2,3

Сочетания. Формула для вычисления числа сочетаний и ее основные свойства.

1,2,3

Практические занятия.

1. Вычисление числа размещений, перестановок и сочетаний.

2

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

1. Применение комбинаторики при решении практических задач.

1

Тема 3.3. Метод математической индукции

Содержание учебного материала

4

Дедукция и индукция. Понятие математической (полной) индукции.

3

1,2,3

Доказательства методом математической индукции.

1,2,3

Задачи арифметического характера. Тригонометрические и алгебраические задачи.

1,2,3

Подготовка к самостоятельной работе (тестовому заданию), проработка материалов по лекциям. Примерные темы рефератов:

1. Доказательство теорем методом математической индукции
2. Задачи на доказательства неравенств

1

Раздел 4. Дополнительные главы теории множеств

12

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

Содержание учебного материала

3

Матрица бинарного отношения.

2

1,2,3

Симметричные и антисимметричные отношения.

1,2,3

Рефлексивные отношения.

1,2,3

Подготовка к самостоятельной работе (тестовому заданию), проработка материалов по лекциям.

1

Тема 4.2. Отношения эквивалентности и разбиения. Фактор-множества

Содержание учебного материала

3

Отношения эквивалентности и разбиения.

2

1,2,3

Классы эквивалентности. Вектор.

1,2,3

Фактор-множества.

1,2,3

Подготовка к самостоятельной работе (тестовому заданию), проработка материалов по лекциям.

1

Тема 4.3. Отношения порядка

Содержание учебного материала

3

Предпорядок (квазипорядок). Частичный порядок.

2

1,2,3

Отношение Парето. Максимальный и минимальный элементы множества.

1,2,3

Супремум и инфинум. Алфавит. Изоморфизм.

1,2,3

Подготовка к самостоятельной работе (тестовому заданию), проработка материалов по лекциям.

1

Тема 4.4. Простейшие криптографические шифры

Содержание учебного материала

3

Криптографическое преобразования информации.

2

1,2,3

Области применения криптографического преобразования информации.

1,2,3

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

1,2,3

Подготовка к самостоятельной работе (тестовому заданию), проработка материалов по лекциям.

1

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

40

Тема 5.1. Понятие графа. Виды и способы задания графов

Содержание учебного материала

2

Граф, вершина, дуга. Изображение графа.

1

**

Мультиграф. Орграф. Неорграф.

**

Подграфы и части графа. Полный неорграф.

**

Подготовка к самостоятельной работе (тестовому заданию), проработка материалов по лекциям.

1

Тема 5.2. Операции над графами

Содержание учебного материала

2

Операции добавления и удаление.  отождествление, дополнение, соединение, произведение,

1

**

Операции  отождествления, дополнения, соединения и  произведения.

**

Операции композиции.

**

Подготовка к самостоятельной работе (тестовому заданию), проработка материалов по лекциям.

1

Тема 5.3. Основные матрицы графов. Матрицы смежности, инцидентности и расстояний

Содержание учебного материала

5

Матрицы смежности для орграфа и неорграфа.

2

**

Матрицы инцидентности для орграфа и неорграфа.

**

 Расстояние в графах. Матрица расстояний графов.

**

Практические занятия.

1. Вычисление основных матриц графов.

2

Подготовка к самостоятельной работе (тестовому заданию), проработка материалов по лекциям. Подготовка к практической работе.

1

Тема 5.4. Маршруты. Пути. Достижимость. Связность

Содержание учебного материала

3

Маршрут и его длина. Цепь. Простая цепь. Циклический маршрут. Цикл.

2

**

Обхват неорграфа. Контур. Связный неорграф. Связность графов. Компонента связности.

**

Матрица достижимости. Расстояние в графах.

**

Подготовка к самостоятельной работе (тестовому заданию), проработка материалов по лекциям.

1

Тема 5.5. Степени вершин, обходы и остовы графов

Содержание учебного материала

2

Степень (валентность) вершины графа. Вершины степени 1 и 0. Лемма о рукопожатиях.

1

**

Остов (каркас) графа.

**

Ранг и коранг графа.

**

Подготовка к самостоятельной работе (тестовому заданию), проработка материалов по лекциям.

1

Тема 5.6. Эйлеров путь. Условие существования Эйлерова пути в графе

Содержание учебного материала

2

Задачи, приводящие к понятию Эйлерова пути.

1

**

Эйлеров путь и алгоритм для его построения.

**

Подготовка к самостоятельной работе (тестовому заданию), проработка материалов по лекциям.

1

Тема 5.7. Гамильтонов цикл. Условие существования Гамильтонова цикла в графе

Содержание учебного материала

3

Гамильтонов цикл.

2

**

Задача коммивояжера.

**

Решение задачи коммивояжера.

**

Подготовка к самостоятельной работе (тестовому заданию), проработка материалов по лекциям.

1

Тема 5.8. Методы поиска кратчайших путей в графах: метод Дейкстры, матричный метод

Содержание учебного материала

5

Понятие кратчайшего пути.

2

**

Метод Дейкстры поиска кратчайших путей в орграфах.

**

Матричный метод поиска кратчайших путей в графах, основанный на матрице весов.

**

Практические занятия.

1. Методы поиска кратчайших путей.

2

Подготовка к самостоятельной работе (тестовому заданию), проработка материалов по лекциям. Подготовка к практической работе.

1

Тема 5.9. Понятие дерева. Способы задания деревьев. Упорядоченные и бинарные деревья

Содержание учебного материала

5

Дерево. Лес. Способы задания деревьев.

2

**

Понятие упорядоченного дерева.

**

Бинарное дерево. Левое (правое) поддерево.

**

Практические занятия.

1.     Способы задания деревьев.

2

Подготовка к самостоятельной работе (тестовому заданию), проработка материалов по лекциям. Подготовка к практической работе.

1

Тема 5.10. Фундаментальные циклы. Разрезы

Содержание учебного материала

3

Фундаментальные циклы. Матрица фундаментальных циклов.

2

**

Сеть. Поток. Разрез. Матрица фундаментальных разрезов. Внутреннее произведение векторов.

**

Граница. Векторные пространства, связанные с графами.

**

Размерность подпространства. Ортогональные подпространства.

Подготовка к самостоятельной работе (тестовому заданию), проработка материалов по лекциям.

1

Тема 5.11. Раскраски графов

Содержание учебного материала

3

Раскраска графа. Хроматическое число графа. Реберный мультиграф. Раскраска ребер.

2

**

Бихроматический граф. Двудольный граф.

**

Алгоритм последовательной раскраски.

**

Подготовка к самостоятельной работе (тестовому заданию), проработка материалов по лекциям.

1

Тема 5.12. Планарные графы. Условие планарности графа

Содержание учебного материала

5

Плоское изображение графа. Теорема Понтрягина – Куратовского.

2

**

Теорема о четырех красках.

**

Число планарности графа. Толщина графа.

**

Практические занятия.

1.     Исследование графов на планарность.

2

Подготовка к самостоятельной работе (тестовому заданию), проработка материалов по лекциям. Подготовка к практической работе.

1

Всего:

128

Результаты обучения (освоенные умения, усвоенные знания)

Коды формируемых компетенций

Формы и методы контроля и оценки результатов обучения

Умения:

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

ОК

ПК

Текущий контроль:

- опрос

- тестирование

Рубежный контроль:

- опрос

- тестирование

Итоговый контроль:

дифференцированный зачет, экзамен

применять законы алгебры логики

ОК

ПК

определять типы графов и давать их характеристики

ОК

ПК

строить простейшие автоматы

ОК

ПК

Знания:

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

ОК

ПК

Текущий контроль:

- опрос

- тестирование

Рубежный контроль:

- опрос

- тестирование

Итоговый контроль:

дифференцированный зачет, экзамен

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

ОК

ПК

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

ОК

ПК

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

ОК

ПК

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

ОК

ПК

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

ОК

ПК

основные понятия теории графов, характеристики и виды графов

ОК

ПК

элементы теории автоматов

ОК

ПК