Министерство образования и науки Российской Федерации

Федеральное государственное автономное образовательное учреждение
высшего профессионального образования

«Уральский федеральный университет
имени первого Президента России Б.Н. Ельцина»

Филиал УрФУ в г. Среднеуральске

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

ДИСКРЕТНАЯ МАТЕМАТИКА

для специальностей

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

технического профиля

г. Среднеуральск 2013

РАБОЧАЯ ПРОГРАММА

УЧЕБНОЙ ДИСЦИПЛИНЫ

ДИСКРЕТНАЯ МАТЕМАТИКА

для специальностей среднего профессионального образования

Автор: Перминова Е.В., преподаватель филиала УрФУ в г. Среднеуральске.

Одобрена

ЦМК математических и естественнонаучных дисциплин

Зам. директора филиала по УМР

_____________ Шелгинский А.Е.

«___»__________2012 г.

Рабочая программа учебной дисциплины разработана на основе Федерального государственного образовательного стандарта (далее - ФГОС) по специальности среднего профессионального образования (далее СПО) 230401 Информационные системы (по отраслям)

1. паспорт ПРОГРАММЫ УЧЕБНОЙ ДИСЦИПЛИНЫ

Дискретная математика

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

Программа учебной дисциплины является частью основной профессиональной образовательной программы в соответствии с ФГОС по специальности СПО 230113 Компьютерные системы и комплексы

1.2. Место дисциплины в структуре основной профессиональной образовательной программы:

дисциплина «Дискретная математика» принадлежит к профессиональному циклу, к подциклу общепрофессиональных дисциплин

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2. СТРУКТУРА И ПРИМЕРНОЕ СОДЕРЖАНИЕ УЧЕБНОЙ ДИСЦИПЛИНЫ

2.1. Объем учебной дисциплины и виды учебной работы

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

Объем часов

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

90

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

60

в том числе:

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

24

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

30

в том числе:

Домашняя подготовка

22

Подготовка сообщений

8

Итоговая аттестация в форме экзамена

2.2. Примерный тематический план и содержание учебной дисциплины _ Дискретная математика

__

наименование

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

Содержание учебного материала, лабораторные и практические работы, самостоятельная работа обучающихся, курсовая работ (проект) (если предусмотрены)

Объем часов

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

1

2

3

4

Введение

<Цели ><><предмета, >его основные задачи и связь с другими дисциплинами. Основные разделы дискретной математики

2

1

Раздел 1.

Логические основы ЭВМ

24

2

2

1

2

2

2

2

2

2

2

2

1

1

2

Тема 1.1.

Основные понятия математической логики Логические функции и таблицы истинности. Законы алгебры логики

10

4

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

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

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

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

Доказательство теорем алгебры логики.

Упрощение логических функций с помощью законов алгебры логики.

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

Тема 1.2.

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

4

4

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

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

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

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

Тема 1.3.

Полнота системы логических функций

2

Теорема Поста о полноте системы логических функций.<>

Раздел 2.

Основы теории множеств

14

Тема 2.1.

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

3

2

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

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

Тема 2.2.

Операции над множествами

4

Операции над множествами. Преобразование формул. Выражение свойств множеств через уравнения. Решение уравнений.

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

Решение задач и уравнений с множествами

Тема 2.3.

Отображения и отношения множеств и их виды

3

2

Отношения множеств. Бинарные отношения. Свойства отношений. Рефлексивные, симметричные, транзитивные отношения. Отношения эквивалентности и порядка.

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

Раздел 3

Комбинаторика

18

Тема 3.1.

Комбинаторные задачи

8

4

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

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

Решение упражнений по теме

Самостоятельная работа - решение упражнений

Тема 3.2

Принцип включения и исключения

4

2

Объединение конфигураций. Принцип включения и исключения.

Самостоятельная работа - домашняя подготовка

Раздел 4

Основные элементы теории графов

16

Тема 4.1.

Основные понятия теории графов

4

2

Понятие графа. Рёбра, вершины. Степени вершин. Задачи, формулировка условий которых в терминах графов существенно облегчает их решение.

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

Решение задач методом рассмотрения вершин с максимальными и минимальными степенями.

Самостоятельная работа - домашняя подготовка

Тема 4.2.

Связные и полные графы

4

2

Связный граф, полный граф. Условия полноты и связности. Компоненты связности. Эйлеровы графы. <>

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

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

Решение задач на обходы.<><><>

Самостоятельная работа - домашняя подготовка

Тема 4.3.

Деревья

4

Дерево, висячая вершина, остовное дерево. Число рёбер в дереве. Дерево как связный граф с минимальным числом рёбер.

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

Решение задач на применение данного свойства

Раздел 5.

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

16

Тема 5.1.

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

2

Основные задачи теории автоматов. Дискретное время и такты. Конечные автоматы. Методы задания конечного автомата. Автоматы и графы. Автоматы Мили и Мура.

Тема 5.2

Абстрактная структура автомата.

2

4

Агрегатизация автоматов и последовательностных машин. Одномерный автомат Неймана и его применение для представления глобальных сетей.

Самостоятельная работа - подготовка сообщений

Тема 5.3.

Машины Поста и Тьюринга.

4

4

Описание и примеры машин. Композиция машин Тьюринга. Вычисления на машинах Тьюринга.

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

Составление алгоритмов машины Тьюринга

Самостоятельная работа - Подготовка сообщений

Всего:

90

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

3.1. Требования к минимальному материально-техническому обеспечению

ПК и проектор для демонстрации презентаций

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

Перечень рекомендуемых учебных изданий, Интернет-ресурсов, дополнительной литературы

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

1

Новиков Н.Ф. Дискретная математика для программистов. Учебник для вузов. 2-ое изд. - СПБ.: Питер, 2007.

2

Максимов Н.В., Партыка Т. Л., ПоповИ.И. Архитектура ЭВМ и вычислительных систем: Учебник. - М.: ФОРУМ:ИНФРА-М, 2005

3

Мышляева И.М. Цифровая схемотехника: Учебник для среднего проф образования - М.: Академия, 2005

_________________________________________

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

Результаты обучения

(освоенные умения, усвоенные знания)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Выполнение практических работ

Выполнение практических работ

Выполнение практических работ

Выполнение практических работ

Устный опрос

Выполнение практических работ

Устный опрос

Устный опрос, выполнение практических работ

Устный опрос

Опрос

Выполнение практических работ

Опрос, сообщения

СОДЕРЖАНИЕ

стр.

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

3

2. СТРУКТУРА и ПРИМЕРНОЕ содержание УЧЕБНОЙ ДИСЦИПЛИНЫ

4

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

8

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

9

4