Обмен опытом

См. также:

Уважаемые коллеги. Размещение авторского материала на страницах электронного справочника "Информио" является бесплатным. Для получения бесплатного свидетельства необходимо оформить заявку

Положение о размещении авторского материала

Размещение информации

Рабочая программа учебной дисциплины «Дискретная математика» по специальности 230701 «Прикладная информатика»

21.05.2015 405 621
Стратьева Алла Васильевна
Стратьева Алла Васильевна, Преподаватель

Томский экономико-промышленный колледж

1. ПАСПОРТ РАБОЧЕЙ ПРОГРАММЫ УЧЕБНОЙ ДИСЦИПЛИНЫ

1.1. Область применения программы

Рабочая программа учебной дисциплины «Дискретная математика» является частью основной профессиональной образовательной программы специальности 230701 Прикладная информатика (по отраслям), разработана в соответствии с ФГОС специальности СПО 230701 Прикладная информатика (по отраслям), укрупненной группы подготовки 230000 Информатика и вычислительная техника, направление подготовки 230100 Информатика и вычислительная техника.

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

1.3. Цели и задачи дисциплины – требования к результатам освоения дисциплины:

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

уметь:

  • применять методы дискретной математики;
  • строить таблицы истинности для формул логики;
  • представлять булевы функции в виде формул заданного типа;
  • выполнять операции над множествами, применять аппарат теории множеств для решения задач;
  • выполнять операции над предикатами;
  • исследовать бинарные отношения на заданные свойства;
  • выполнять операции над отображениями и подстановками;                            
  • выполнять операции в алгебре вычетов;  
  • применять простейшие криптографические шифры для шифрования текстов;
  • генерировать основные комбинаторные объекты;                                  
  • находить характеристики графов;        

знать:

  • логические операции, формулы логики, законы алгебры логики;
  • основные классы функций, полноту множеств функций, теорему Поста;
  • основные понятия теории множеств, теоретико-множественные операции и их связь с логическими операциями;
  • логику предикатов, бинарные отношения и их виды;                                                        
  • элементы теории отображений и алгебры подстановок;
  • основы алгебры вычетов и их приложение к простейшим криптографическим шифрам;
  • метод математической индукции;                    
  • алгоритмическое перечисление основных комбинаторных объектов;                  
  • основы теории графов;                  
  • элементы теории автоматов.            

1.4. Рекомендуемое количество часов на освоение программы дисциплины:

максимальной учебной нагрузки обучающегося 92 часа, в том числе:

обязательной аудиторной учебной нагрузки обучающегося 62 часа;

самостоятельной работы обучающегося 30 часов.

2.1 Тематический план и содержание учебной дисциплины

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

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

Количество аудиторных часов

Внеаудиторная самостоятельная работа студентов

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

всего

практических

Раздел 1 Множества. Операции над множествами

14

10

4

4

 

Тема 1.1 Понятие множества. Примеры множеств. Элемент множества. Подмножество. Мощность конечного множества. Пустое множество.

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

Алгебра (под) множеств и ее законы. Изменение мощности множеств при операциях над множествами.

Векторы (кортежи), прямое произведение, проекция.

2

2

2

 

2

 

 

2

 

 

2

 

2

Практическая работа № 1

Прямое произведение множеств.

Построение диаграмм Эйлера - Венна

 

 

 

 

 

Тема 1.2 Понятие соответствия. Образ и прообраз. Область определения и область значения соответствия. Всюду определенное соответствие. Сюръективное соответствие. Однозначное (функциональное) соответствие.

2

2

 

 

2

Тема 1.3 Обратное соответствие. Обратимое соответствие. Взаимно однозначное соответствие (1-1-соответствие, биекция). Мощность бесконечного множества. Равномощность бесконечного множества своему подмножеству. Счетные множества. Несчетные множества (континуум).

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

6

2

 

 

4

2

 

 

 

 

2

Самостоятельная работа № 1 Реферат по темам: (1 по выбору студента) Обратное соответствие. Обратимое соответствие. Взаимно однозначное соответствие (1-1-соответствие, биекция). Мощность бесконечного множества. Равномощность бесконечного множества своему подмножеству. Счетные множества. Несчетные множества (континуум).

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

 

 

 

 

 

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

2

2

2

 

3

Практическая работа № 2

Задание числового ряда с помощью порождающей процедуры.

 

 

 

 

 

Тема 1.5 Понятие отношения. Бинарные отношения. Свойства отношений: рефлексивность, антирефлексивность, симметричность, антисимметричность, транзитивность. Транзитивное замыкание отношения. Обратное отношение.

Отношение эквивалентности. Класс эквивалентности. Отношение строгого и нестрогого порядка. Отношение линейного и частичного порядка.

Лексикографический порядок векторов.

2

2

 

 

 

2

 

 

2

 

2

Раздел 2 Комбинаторика.

14

8

6

6

 

Тема 2.1. Основные объекты комбинаторики. Типы комбинаторных задач. Правило суммы и правило произведения.

Формула включения и исключения. Размещения с повторениями. Размещения без повторений.

2

2

 

2

 

2

 

2

Практическая работа № 3

Решение комбинаторных задач

Практическая работа № 4

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

Размещения без повторений.

Бином Ньютона

 

 

 

 

 

Тема 2.2 Перестановки. Сочетания без повторений.

Бином Ньютона, свойства биномиальных коэффициентов, треугольник Паскаля.

6

2

2

4

2

 

2

Практическая работа № 5

Решение комбинаторных задач

Вычисление сочетаний без повторений

Самостоятельная работа № 2 Решение задач.

 

 

 

 

 

Тема 2.3 Сочетания с повторениями. Задача перечисления.

2

2

2

 

2

Практическая работа № 6

Перестановки. Сочетания без повторений.

 

 

 

 

 

Тема 2.4 Лексикографический порядок. Двумерные выборки.

4

2

 

2

2

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

Решение задач. Двумерные выборки.

 

 

 

 

 

Раздел 3 Основы общей алгебры

26

18

2

8

 

Тема 3.1 Понятие алгебры. Замкнутые операции. N-арные операции, бинарные операции, арность операции.

Тип алгебры, сигнатура. Свойства бинарных операций: ассоциативность, коммутативность, дистрибутивность слева, дистрибутивность справа.

Два вида процедур в алгебре: вычисление формул и преобразование формул.

2

2

 

 

3

 

3

 

3

Тема 3.2 Изоморфизм алгебр. Гомоморфизм алгебр. Полугруппа. Единица полугруппы. Моноид. Группа. Обратный элемент.

Способ задания (полу)групп: с помощью бинарной таблицы и с помощью образующих.

Решетка. Наименьшая верхняя грань, наибольшая нижняя грань. Единственность максимального и единственность минимального элемента. Единица решетки и нуль решетки. Решетка подмножеств любого множества.

6

2

 

 

4

2

 

 

2

 

2

Самостоятельная работа № 4 Задание (полу) групп: с помощью бинарной таблицы и с помощью образующих.

Индивидуальные задания

 

 

 

 

 

Тема 3.3 Высказывание. Логические связки: конъюнкция, дизъюнкция, отрицание, импликация, разделительное "или", эквивалентность.

Таблицы истинности для логических функций.

4

2

 

2

3

 

3

Самостоятельная работа № 5 Таблицы истинности для логических функций. Индивидуальные задания

 

 

 

 

 

Тема 3.4 Логические функции от нуля переменных (константы), от одной переменной, от двух переменных.

Применение к переключательным схемам. Алгебра логических функций. Вычисление логических функций.

2

2

 

 

 

3

 

3

Тема 3.5 Проблема полноты. Функционально полная система функций (в сильном смысле и в слабом смысле). Эквивалентности формул.

2

2

 

 

3

Тема 3.6 Алгоритм перехода от таблицы функции к формуле (построение СДНФ).

2

2

2

 

3

Практическая работа № 7

Построение СДНФ

 

 

 

 

 

Тема 3.7 Булева алгебра и ее законы. Изоморфизм булевых алгебр (алгебры множеств и алгебры логических функций).

2

2

 

 

3

Тема 3.8 Функциональная полнота некоторых систем функций. Алгебра Жегалкина.

Функциональная полнота алгебры Жегалкина. Ортогональные функции. Монотонные функции.

2

2

 

 

3

 

3

Тема 3.9 Классы логических функций. Монотонные функции. Линейные функции. Отношение двойственности функций.

Функции, двойственные самим себе (самодвойственные функции).

Функции, сохраняющие нуль. Функции, сохраняющие единицу.

4

2

 

 

2

3

 

 

 

3

Самостоятельная работа № 6 Реферат на тему: Классы логических функций. Монотонные функции. Линейные функции. Отношение двойственности функций. Функции, двойственные самим себе (самодвойственные функции). Функции, сохраняющие нуль. Функции, сохраняющие единицу.

 

 

 

 

 

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

4

4

4

 

 

Тема 4.1 Понятие предиката. Кванторы

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

2

2

 

 

3

Тема 4.2 Эквивалентные соотношения в логике предикатов.

Чистая логика предикатов и прикладные логики предикатов.

2

2

 

4

 

3

 

3

Практическая работа № 8

Выполнение обычных логических операций над предикатами.

Практическая работа № 9

Формализация предложений с помощью логики предикатов.

 

 

 

 

 

Раздел 5. Графы

20

16

8

4

 

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

Отношение смежности между вершинами, матрица смежности. Отношение инцидентности между вершинами и ребрами. Степень вершины. Изолированные вершины, висячие вершины.

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

2

2

 

 

 

2

 

 

2

 

 

2

Тема 5.2 Максимальный и минимальный (относительно некоторого свойства) подграф. Изоморфизм графов. Неориентированные графы. Путь, цепь, простая цепь, цикл.

Связанные вершины. Связный граф. Компоненты связности

Длина пути. Расстояние между вершинами в связном графе. Аксиомы метрики (расстояния).

2

2

 

2

 

3

 

3

 

3

Практическая работа № 10

Построить граф и указать на нем путь, цепь, простую цепь, цикл

 

 

 

 

 

Тема 5.3 Радиус графа, центры графа. Эйлеров обход. Задача о кенигсбергских мостах. Алгоритм построения Эйлерова цикла. Задача о гамильтоновом обходе (задача коммивояжера).

Ориентированные графы (орграфы). Ориентированный путь, ориентированный цикл. Достижимость.

2

2

4

 

2

 

 

2

Практическая работа № 11

Нахождение центра графа

Практическая работа № 12

Определение радиуса графа

 

 

 

 

 

Тема 5.4 Виды связности: сильная связность, односторонняя связность, слабая связность. Компонента сильной связности.

Конденсация, граф конденсации. Ациклический граф.

Топологическая сортировка.

2

2

 

 

 

3

 

3

Тема 5.5 Деревья. Оптимизационные задачи на графах. Задача о кратчайшем пути

Неориентированные деревья. Ориентированные деревья. Применение деревьев: классификация, представление формул, бинарное дерево поиска.

Оптимизационные задачи на графах Взвешенные (нагруженные) графы. Задача о кратчайшем пути в неориентированном графе без весов.

Ранжирование вершин. Задача о кратчайшем пути во взвешенном графе. Алгоритм Дейкстры

2

2

 

 

 

3

 

 

3

 

 

3

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

Оптимизационные задачи на графах.

2

2

 

 

 

3

Тема 5. 7 Алгоритм поиска увеличивающей цепи. Разрезы. Пропускная способность разреза.

2

2

 

 

3

Тема 5.8 Матричные методы анализа графов. Степень матрицы смежности графа. Сумма степеней матрицы смежности, достижимость и связность. Транзитивное замыкание. Графы и бинарные отношения.

Отношения эквивалентности и отношения порядка в терминах графов. Матричные методы анализа мульти графов. Двудольные графы. Задача о раскраске графа.

6

2

2

4

3

 

 

3

Практическая работа № 13

Раскраска графа

Самостоятельная работа № 7. Задача о раскраске графа.

 

 

 

 

 

Раздел 6 Элементы теории автоматов

14

6

6

8

 

6.1 Базовые множества для автомата: входной алфавит, выходной алфавит, множество состояний. Таблица автомата. Принцип работы автомата. Диаграмма автомата.

8

4

4

4

2

Самостоятельная работа № 8 Принцип работы автомата.

Практическая работа № 14

Диаграмма автомата

 

 

 

 

 

6.2 Словарная функция автомата. Финальная функция автомата. Правильный автомат (автомат Мура). Упрощённый вид диаграммы для правильных автоматов. Автомат, распознающий свойство слова, и его построение.

6

2

2

4

2

Практическая работа №15

Построение автомата

Самостоятельная работа №9 Диаграмма автомата. Индивидуальные задания

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

Упрощённый вид диаграммы для

автоматов. Индивидуальные задания.

Подготовка к экзамену

 

 

 

 

 

Всего часов

92

62

30

30

 

 3.2. Информационное обеспечение обучения

Основные источники:

  1. Алексеев В.Б. Лекции по дискретной математике. - М.: 2008.
  2. Богомолов Н. В. Сборник дидактических заданий по математике: учебное пособие для студентов средних специальных учебных заведений / Н. В. Богомолов, Л. Ю. Сергиенко. - 3-е изд., стер. - М.: Дрофа, 2009.
  1. Гиндинкин С.Г. Алгебра логики. – М.: 2006.
  2. Григорьев С. Г. Математика: учебник для студентов средних профессиональных учебных заведений / С. Г. Григорьев, С. В. Задулина; под ред. В. А. Гусева. - 3-е изд., стер. - М.: Академия, 2008.



Назад к списку


Добавить комментарий
Прежде чем добавлять комментарий, ознакомьтесь с правилами публикации
Имя:*
E-mail:
Должность:
Организация:
Комментарий:*
Введите код, который видите на картинке:*