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

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

высшего образования

«Нижегородский государственный университет им. Н.И. Лобачевского»

Арзамасский филиал

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

(Арзамасский политехнический колледж им. В.А. Новикова)

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

учебной дисциплины ЕН.02 Элементы математической логики

специальность 09.02.03 Программирование в компьютерных системах

Арзамас 2015

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

РАССМОТРЕНО И ОДОБРЕНО

Утверждаю

на заседании методической комиссии________________________

________________________________________________________________________________________________.

Директор

Арзамасского филиала ННГУ

«___» _________________ 20____г.

«___» _________________ 20____г.

Председатель методической комиссии__________/____________/

(ф.и.о.)

_________________/С.Н. Пяткин /

Разработчики: Копьёва С.В.

СОДЕРЖАНИЕ

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

стр.

4

2. Результаты усвоения программы.

5

3. Структура и содержание программы учебной дисциплины ЕН.02 Элементы математической логики.

6-26

4. Условия реализации программы учебной дисциплины ЕН.02 Элементы математической логики.

27-28

5. Контроль и оценка результатов усвоения программы учебной дисциплины ЕН.02 Элементы математической логики.

29-33

1. ПАСПОРТ ПРОГРАММЫ

учебной дисциплины ЕН.02 Элементы математической логики

1. 1. Область применения.

Программа учебной дисциплины ЕН.02 Элементы математической логики является элементом основной образовательной программы специальности 09.02.03 Программирование в компьютерных системах цикла ЕН.00.

1. 2. Цели и задачи программы, требования к результатам усвоения:

уметь:

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

знать:

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

• формулы алгебры высказываний;

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

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

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

• максимальной учебной нагрузки обучающегося –144 час.;

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

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

• самостоятельной работы обучающегося – 48часа;

• итоговая аттестация - зачёт.

2.Результаты усвоения программы

ЕН.02 Элементы математической логики

Результатом усвоения программы ЕН.02 Элементы математической логики являются общие (ОК) и профессиональные (ПК) компетенции.

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

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

ОК.3. Принимать решения в стандартных и нестандартных ситуациях и нести за них ответственность.

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

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

ОК.6. Работать в коллективе и команде, эффективно общаться с коллегами, руководством, потребителями.

ОК.7. Брать на себя ответственность за работу членов команды (подчинённых), результат выполнения заданий.

ОК.8. Самостоятельно определять задачи профессионального личностного развития, заниматься самообразованием, осознанно планировать повышение квалификации.

ОК.9. Ориентироваться в условиях частой смены технологий в профессиональной деятельности.

ПК 1.1. Выполнять разработку спецификаций отдельных компонент.

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

ПК 2.4. Реализовывать методы и технологии защиты информации в базах данных.

ПК 3.4. Осуществлять разработку тестовых наборов и тестовых сценариев.

3. СТРУКТУРА и ПРИМЕРНОЕ содержание учебной дисциплины

ЕН.02 Элементы математической логики

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

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

Количество часов

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

144

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

96

в том числе:

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

24

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

48

в том числе:

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

48

Итоговая аттестация в форме зачета

3.2. Тематический план учебной дисциплины

ЕН.02 Элементы математической логики

Коды общих и профессиональ-ных компетенций

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

Всего часов

(макс. учебная нагрузка и практики)

Количество часов, отведенное на освоение учебной дисциплины

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

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

Всего,

часов

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

часов

Всего,

часов

1

2

3

4

5

6

Раздел 1. Формулы логики

27

18

6

9

ОК.3, ПК.1.2

Тема 1.1. Логические операции.

3

2

1

ОК.5, ПК.3.4

Тема 1.2. Формулы логики.

6

4

2

2

ОК.7, ПК.2.4

Тема 1.3. Таблицы истинности.

6

4

2

2

ОК.2, ПК.1.1

Тема 1.4. ДНФ, КНФ.

3

2

1

ОК.8, ПК.1.2

Тема 1.5. Законы логики.

3

2

1

ОК.6, ПК.3.4

Тема 1.6. Равносильные преобразования.

6

4

2

2

Раздел 2. Булевы функции.

30

20

8

10

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

12

8

4

4

ОК.4, ПК.2.4

Тема 2.1.1. СДНФ. Методика представления.

6

2

2

ОК.9, ПК.1.2

Тема 2.1.2. СКНФ. Методика представления.

6

6

4

2

ОК.8, ПК.1.1

Тема 2.2. Операция двоичного сложения. Многочлен Жегалкина.

6

4

2

2

ОК.6, ПК.3.4

Тема 2.3. Полнота множества функций. Важнейшие замкнутые классы.

6

4

2

2

ОК.2, ПК.2.4

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

6

4

2

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

18

12

4

5

ОК.9, ПК.1.1

Тема 3.1. Основные понятия. Теоретико-множественные диаграммы.

3

2

2

1

ОК.3, ПК.2.4

Тема 3.2. Операции над множествами и их свойства.

6

4

2

2

ОК.7, ПК.3.4

Тема 3.3. Соответствие между теоретико-множественными и логическими операциями.

6

4

2

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

15

10

4

5

ОК.4, ПК.1.2

Тема 4.1. Основные понятия. Обычные логические операции над предикатами.

6

4

2

2

ОК.1. ПК.1.1

Тема 4.2. Кванторные операции над предикатами.

6

4

2

2

ОК.5, ПК.3.4

Тема 4.3. Бинарные отношения.

3

2

1

Раздел 5. Теория отображений и алгебра подстановок.

6

4

2

ОК.9, ПК.1.2

Тема 5.1. Отображения. Основные понятия.

3

2

1

ОК.3, ПК.1.1

Тема 5.2. Подстановки. Основные понятия.

3

2

1

Раздел 6. Алгоритмическое перечисление (генерирование) комбинаторных объектов.

18

12

6

ОК.7, ПК.1.2

Тема 6.1. Генерирование двоичных слов заданной длины.

3

2

1

ОК.5, ПК.2.4

Тема 6.2. Генерирование элементов декартова произведения множеств.

3

2

1

ОК.2, ПК.1.1

Тема 6.3. Генерирование перестановок заданной длины.

3

2

1

ОК.6, ПК.2.4

Тема 6.4. Генерирование К-элементных подмножеств данного множества.

3

2

1

ОК.9, ПК.3.5

Тема 6.5. Генерирование всех подмножеств данного множества.

6

4

2

Раздел 7. Основы алгебры вычетов.

6

4

2

ОК.4, ПК.1.1

Тема 7.1. Сравнения и их свойства.

3

2

1

ОК.3, ПК.3.4.

Тема 7.2. Вычеты.

3

2

1

Раздел 8. Простейшие криптографические шифры.

9

6

3

ОК.2, ПК.1.2

Тема 8.1. Шифры замены.

4

2

2

ОК.3, ПК.2.4

Тема 8.2. Коды Хемминга.

6

4

2

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

15

10

2

4

ОК.9, ПК.3.4

Тема 9.1. Вводные понятия.

3

2

1

ОК.7, ПК.2.4

Тема 9.2. Машина Тьюринга.

6

4

2

ОК.4, ПК.1.2

Тема 9.3. Сочетания машин Тьюринга.

3

2

1

ОК.8, ПК.1.1

Тема 9.4. Тьюрингов подход к понятию «алгоритм»

3

2

1

ИТОГО:

144

96

24

48

3.3. Содержание обучения по учебной дисциплине ЕН.02 Элементы математической логики

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

Содержание обучения по дисциплине

Количест-во часов

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

Знать, уметь

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

1

2

3

4

5

Раздел 1. Формулы логики

27

Тема 1.1.Введение. Логические операции.

Студент должен:

иметь представление:

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

знать:

• основные логические операции;

уметь:

• обозначать логические операции.

Предмет математической логики, его основные задачи и области применения. Понятие высказывания. Основные логические операции.

2

2

Самостоятельная работа: Выполнение упражнений записи и оценки основных логических операций.

1

3

Тема 1.2. Формулы логики.

Студент должен:

знать:

• понятие формулы логики;

• понятие тождественно-истинной формулы;

уметь:

• упрощать запись формулы.

Понятие формулы логики. Равносильные формулы. Тождественно-истинные формулы.

4

2

Практическое занятие 1: Упрощение формул логики.

2

Самостоятельная работа: Выполнение упражнений по упрощению записи формул.

2

3

Тема 1.3. Таблицы истинности.

Студент должен:

знать:

• понятие таблицы истинности и методику её построения;

уметь:

• строить таблицы истинности формул логики.

Таблицы истинности и методика её построения.

4

2

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

2

Самостоятельная работа: Выполнение упражнений по оценке формул логики с помощью таблиц истинности.

2

3

Тема 1.4. ДНФ, КНФ.

Студент должен:

знать:

• понятие ДНФ (дизъюнктивной нормальной формы);

• понятие КНФ(конъюнктивной нормальной формы);

уметь:

• строить таблицы истинности для ДНФ упрощённым методом.

Понятие элементарного произведения; понятие ДНФ. Методика построения таблицы истинности для ДНФ упрощённым методом. Понятие элементарной дизъюнкции, понятие КНФ.

2

2

Самостоятельная работа: Выполнение упражнений в представлении формул логики в виде ДНФ, КНФ.

1

3

Тема 1.5. Законы логики.

Студент должен:

знать:

• понятие равносильности формул логики;

• законы логики;

уметь:

• применять законы логики для упрощения формул

Равносильные формулы. Законы логики.

2

2

Самостоятельная работа: Выполнение упражнений по применению законов логики.

1

3

Тема 1.6. Равносильные преобразования.

Студент должен:

знать:

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

уметь:

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

Методика упрощения формул логики с помощью равносильных преобразований.

4

2

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

2

3

Самостоятельная работа: Выполнение равносильных преобразований формул логики.

2

3

Раздел 2. Булевы функции.

30

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

12

Тема 2.1.1. СДНФ. Методика представления.

Студент должен:

знать:

• понятие булевой функции и способы её заданий;

• понятие СДНФ совершенной дизъюнктивной нормальной формы);

• методику представления булевой функции в виде СДНФ;

уметь:

• представлять булеву функцию в виде СДНФ.

Понятие булевой функции. Способы задания булевой функции. Понятие совершенной ДНФ. Методика представления булевой функции в виде СДНФ.

2

2

Самостоятельная работа: Выполнение упражнений в составлении СДНФ.

2

3

Тема 2.1.2. СКНФ. Методика представления.

Студент должен:

знать:

• понятие совершенной КНФ;

• методику представления булевой функции в виде СКНФ (совершенной конъюнктивной нормальной формы);

• понятие ДНФ;

• методику представления булевой функции (N ≤ 3) в виде минимальной ДНФ;

уметь:

• представлять булеву функцию в виде совершенной КНФ;

• представлять булеву функцию (N ≤ 3) в виде минимальной ДНФ.

Понятие совершенной КНФ. Методика представления булевой функции в виде совершенной КНФ. Понятие минимальной ДНФ. Методика представления булевой функции (N ≤ 3) в виде минимальной ДНФ графическим методом.

6

2

Практическое занятие 4: Представление булевой функции в виде СКНФ, СДНФ.

4

3

Самостоятельная работа: Выполнение упражнений в представлении булевой функции в виде СКНФ, СДНФ.

2

3

Тема 2.2. Операция двоичного сложения. Многочлен Жегалкина.

Студент должен:

знать:

• операцию двоичного сложения и её свойства;

• методику представления булевой функции в виде многочлена Жегалкина;

уметь:

• представлять булеву функцию в виде многочлена Жегалкина.

Операция двоичного сложения и её свойства. Многочлен Жегалкина. Методика представления булевой функции в виде многочлена Жегалкина.

4

2

Практическое занятие 5: Представление булевой функции в виде многочлена Жегалкина.

2

3

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

2

3

Тема 2.3. Полнота множества функций. Важнейшие замкнутые классы.

Студент должен:

знать:

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

• понятие полноты множества функций;

• понятие замкнутого класса, важнейшие замкнутые классы;

уметь:

• проверять булеву функцию на принадлежность Т0, Т1, S, L, M.

Проблема возможности выражения одних булевых функций через другие. Полнота множества функций. Понятие замкнутого класса функций. Важнейшие замкнутые классы: Т0, Т1, S, L, M.

4

2

Практическое занятие 6: Проверка булевых функций на принадлежность к классам: Т0, Т1, S, L, M..

2

3

Самостоятельная работа: Выполнение упражнений по проверке булевых функций на принадлежность к важнейшим замкнутым классам.

2

3

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

Студент должен:

знать:

• знать теорему Поста;

• методику проверки множества булевых функций на полноту;

уметь:

• проверять множество булевых функций на полноту;

• проверять, является ли функция шефферовской.

Теорема Поста. Шефферовские функции. Функция Шеффера и функция Пирса как простейшие шефферовские функции.

4

2

Самостоятельная работа: Проверка множества булевых функций на полноту.

2

3

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

18

Тема 3.1. Основные понятия. Теоретико-множественные диаграммы.

Студент должен:

знать:

• понятие множества;

• понятие подмножества; формулу количества подмножеств конечного множества;

уметь:

• применять теоретико-множественные диаграммы.

Понятие множества. Конечные и бесконечные множества, пустое множество. Подмножество; количество подмножеств конечного множества.

Теоретико-множественные диаграммы.

4

2

Самостоятельная работа: Решение задач с помощью теоретико-множественных диаграмм.

2

3

Тема 3.2. Операции над множествами и их свойства.

Студент должен:

знать:

• операции над множествами и их свойства;

• формулу количества элементов в объединении нескольких конечных множеств.

уметь:

• выполнять операции над множествами;

• решать задачи на подсчёт количества элементов с использованием формул.

Операции над множествами и их свойства. Формула количества элементов в объединении конечных множеств. Декартово произведение множеств. Декартова степень множества.

4

2

Практическое занятие 7: Операции над множествами.

2

Самостоятельная работа: Выполнение упражнений на теоретико-множественные операции.

2

3

Тема 3.3. Соответствие между теоретико-множественными и логическими операциями.

Студент должен:

знать:

• соответствие между теоретико-множественными и логическими операциями;

• методику проверки теоретико-множественных соотношений с помощью формул логики;

уметь:

• проверять теоретико-множественные соотношения с помощью формул логики.

Соответствие между теоретико-множественными и логическими операциями. Методика проверки теоретико-множественных соотношений с помощью формул логики.

4

2

Практическое занятие 8: Решение задач с помощью кругов Эйлера.

2

Самостоятельная работа: Выполнение упражнений по проверке теоретико-множественных соотношений с помощью формул логики.

2

3

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

15

Тема 4.1. Основные понятия. Обычные логические операции над предикатами.

Студент должен:

знать:

• понятие предиката, понятия области определения и области истинности предиката;

• логические операции над предикатами;

уметь:

• записывать область истинности предиката;

• выполнять логические операции над предикатами.

Понятие предиката. Область определения и область истинности предиката. Обычные логические операции над предикатами.

4

2

Практическое занятие 9: Логические операции над предикатами.

2

Самостоятельная работа: Выполнение упражнений по записи области истинности предикатов.

2

3

Тема 4.2. Кванторные операции над предикатами.

Студент должен:

знать:

• кванторные операции над предикатами;

• понятие предикатной формулы;

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

уметь:

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

• строить отрицания к предикатам, содержащим кванторные операции;

• формализовывать предложения с помощью логики предикатов.

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

4

2

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

2

3

Самостоятельная работа: Построение отрицаний к предикатам, содержащим кванторные операции.

2

3

Тема 4.3. Бинарные отношения.

Студент должен:

знать:

• понятие бинарного отношений;

• понятие рефлексивного, симметричного, транзитивного бинарного отношения;

• понятие отношения эквивалентности;

уметь:

• строить диаграмму бинарного отношения;

• исследовать бинарные отношения на рефлексивность, симметричность, транзитивность;

• выделять классы эквивалентности.

Понятие бинарного отношения. Диаграммы бинарного отношения. Рефлексивные, симметричные, транзитивные бинарные отношения. Отношение эквивалентности; теорема о разбиении множества на классы эквивалентности.

2

Самостоятельная работа: Построение диаграмм бинарных отношений.

1

3

Раздел 5. Теория отображений и алгебра подстановок.

6

Тема 5.1. Отображения. Основные понятия.

Студент должен:

знать:

• понятие отображения;

• понятие взаимнооднозначного (биективного) отображения;

• операцию композиции отображений и её свойства;

• понятие обратного отображения;

• понятие композиционной степени отображения;

уметь:

• выполнять операции над отображениями;

• строить диаграммы и выделять циклы для внутреннего отображения, заданного на конечном множестве.

Понятие отображения. Виды отображений. Диаграмма внутреннего отображения, заданного на конечном множестве; циклы.

2

2

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

1

3

Тема 5.2. Подстановки. Основные понятия.

Студент должен:

знать:

• понятие подстановки, формулу количества подстановок;

• циклическое разложение подстановки;

• операции над подстановками;

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

уметь:

• записывать циклическое разложение подстановки;

• выполнять операции и решать простейшие уравнения в алгебре подстановок.

Понятие подстановки. Формула количества подстановок. Циклическое разложение подстановки. Произведение подстановок. Обратная подстановка. Степень подстановки. Методика решения простейших уравнений в алгебре подстановок. Чётность подстановок.

2

2

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

1

3

Раздел 6. Алгоритмическое перечисление (генерирование) комбинаторных объектов.

18

Тема 6.1. Генерирование двоичных слов заданной длины.

Студент должен:

знать:

• понятие генерирования элементов конечного множества;

• принцип генерирования двоичных слов заданной длины;

уметь:

• генерировать двоичные слова заданной длины.

Понятие алгоритмического перечисления (генерирования) элементов конечного множества. Генерирование двоичных слов заданной длины.

2

2

Самостоятельная работа: Выполнение упражнений по генерированию двоичных слов данной длины.

1

3

Тема 6.2. Генерирование элементов декартова произведения множеств.

Студент должен:

знать:

• принцип генерирования элементов декартова произведения множеств;

уметь:

• генерировать элементы декартова произведения множеств.

Генерирование элементов декартова произведения множеств.

2

2

Самостоятельная работа: Выполнение упражнений в генерировании элементов декартова произведения множеств.

1

3

Тема 6.3. Генерирование перестановок заданной длины.

Студент должен:

знать:

• принцип генерирования перестановок заданной длины;

уметь:

• генерировать перестановки заданной длины.

Генерирование перестановок заданной длины.

2

2

Самостоятельная работа: Выполнение упражнений в генерировании перестановок заданной длины.

1

3

Тема 6.4. Генерирование

К-элементных подмножеств данного множества.

Студент должен:

знать:

• принцип генерирования К-элементных подмножеств данного множества;

уметь:

• генерировать К-элементные подмножества данного множества.

Генерирование К2-элементных подмножеств данного множества.

2

2

Самостоятельная работа: Выполнение упражнений в генерировании К-элементных подмножеств данного множества.

1

3

Тема 6.5. Генерирование всех подмножеств данного множества.

Студент должен:

знать:

• принцип генерирования всех подмножеств данного множества;

уметь:

• генерировать все подмножества заданного множества.

Генерирование всех подмножеств данного множества.

4

2

Самостоятельная работа: Выполнение упражнений в генерировании комбинаторных объектов заданного типа.

2

3

Раздел 7. Основы алгебры вычетов.

6

Тема 7.1. Сравнения и их свойства.

Студент должен:

знать:

• понятие сравнения по модулю;

• свойства сравнений;

уметь:

• применять свойства сравнений в решении задач.

Сравнение по модулю. Свойства сравнений.

2

2

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

1

3

Тема 7.2. Вычеты.

Студент должен:

знать:

• понятие вычета по модулю;

• числовой и цифровой методы контроля по модулю;

уметь:

• выбирать модуль для контроля;

• использовать вычеты в криптоустойчивых системах.

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

2

2

Самостоятельная работа: Выполнение упражнений в практическом применении алгебры вычетов.

1

3

Раздел 8. Простейшие криптографические шифры.

9

Тема 8.1. Шифры замены.

Студент должен:

знать:

• понятие шифрования;

• принцип шифров замены;

уметь:

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

• осуществлять дешифровку шифротекста в простейших случаях.

Понятие шифрования. Проблема криптографической замены информации. Шифры замены. Шифр Цезаря и шифр Вижнера.

2

2

Самостоятельная работа: Выполнение упражнений в шифровании текста при помощи шифра замены.

1

3

Тема 8.2. Коды Хемминга.

Студент должен:

знать:

• понятие самокорректирующихся кодов;

• понятие кода Хемминга;

• алгоритм построения кода Хемминга;

уметь:

• строить код Хемминга;

• обнаруживать ошибки в кодах Хемминга;

• декодировать (получать исходное сообщение).

Самокорректирующиеся коды. Коды Хемминга. Алгоритм построения кода Хемминга. Алгоритм построения кода Хемминга. Обнаружение ошибки в кодах Хемминга. Декодирование.

4

2

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

2

3

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

15

Тема 9.1. Вводные понятия.

Студент должен:

знать:

• понятие алгоритма;

• свойства алгоритмов;

• понятие алфавита;

• понятие слова;

• понятие длины слова;

• понятие склейки слов;

уметь:

• выполнять простейшие операции над словами.

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

2

2

Самостоятельная работа: Выполнение простейших операций над словами.

1

3

Тема 9.2. Машина Тьюринга.

Студент должен:

знать:

• понятие машины Тьюринга;

• правила работы машины;

уметь:

• задавать программу машины (строить машину Тьюринга).

Структура машины Тьюринга. Задание программы машины таблицей. Правила работы машины. Стандартные машины. Примеры машин.

4

2

Практическое занятие 11: Конструирование машин Тьюринга.

2

Самостоятельная работа: Нахождение результата применения машины к заданному слову по данной машине Тьюринга.

1

3

Тема 9.3. Сочетания машин Тьюринга.

Студент должен:

знать:

• понятие композиции машин;

• понятие машин с полулентами;

• понятие объединения машин;

• понятие разветвления машин;

• понятие итерации машин;

уметь:

• строить машины, работающие по правилу;

• строить машину по её словесному описанию.

Сочетания машин Тьюринга: композиция и объединение. Машины с полулентами, разветвление и итерация машин.

2

2

Самостоятельная работа: Построение программ машин по словесному описанию машин.

1

3

Тема 9.4. Тьюрингов подход к понятию «алгоритм»

Студент должен:

знать:

• понятие Тьюрингова алгоритма решения класса задач Z;

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

• понятие самоприменимой машины;

уметь:

• описывать стандартную кодировку внешних слов и программы машин с помощью таблицы кодирования.

Тьюрингов алгоритм решения класса задач Z. Алгоритмически разрешимые и неразрешимые проблемы по Тьюрингу.

2

2

Самостоятельная работа: Применение алгоритма, заданного машиной Т, к задаче Z.

1

3

Итого:

144

4. условия реализации рабочей программы учебной дисциплины ЕН.02 Элементы математической логики

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

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

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

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

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

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

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

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

Литература.

Основная

1.Ерусалимский Я.М. «Дискретная математика». – М.: «Вузовская книга», 2012г.

2.Журавлёв Ю.И. «Об алгоритмах упрощения ДНФ». – М.: Издательский центр «Академия», 2010г.

3.Мендельсон Э. «Введение в математическую логику». – М.: Наука, 2010г.

4.Спирина М.С., Спирин П.А. «Дискретная математика» - М.: Издательский центр «Академия, 2011г.

5.Яблонский С.В. «Введение в дискретную математику» - М.: «Высшая школа», 2012г.

Дополнительная

1.Тишин В.В. «Дискретная математика в примерах и задачах»-СПб.:БХВ-Петербург,2009г.

2.Шапорев С.Д. «Дискретная математика»-СПб.:БХВ-Петербург,2011г.

3.Канцедал С.А. «Дискретная математика»-М.: ид «Форум»: инфра-М.,2010г.

4.ГалушкинаЮ.И.,Марьямов А.Н. «Конспект лекций по дискретной математике» - М.:

Айрис-пресс,2010г.,высшее образование.

Информационные ресурсы

1.window.edu.ru

2.http ://exponenta.ru

3.http://webmath.ru

4.http://www.allmath.ru

5. Контроль и оценка результатов усвоения учебноЙ дисциплины ЕН.02 Элементы математической логики

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

Текущий контроль проводится преподавателем в процессе обучения. Итоговый контроль проводится экзаменационной комиссией после обучения.

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

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

Для текущего и итогового контроля образовательными учреждениями создаются фонды оценочных средств (ФОС).

ФОС включают в себя педагогические контрольно-измерительные материалы, предназначенные для определения соответствия (или несоответствия) индивидуальных образовательных достижений основным показателям результатов подготовки (таблицы).

Раздел (тема) программы учебной дисциплины Элементы математической логики

Результаты

(освоенные общие и профессиональные компетенции)

Основные показатели результатов
подготовки

Формы и методы контроля

Введение.

ОК.1, ПК.1.1

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

3,4,5

Устное собеседование, рефлексия по модулю.

Раздел 1. Формулы логики

Тема 1.1. Логические операции.

ОК.3, ПК.1.2

Оценка результатов логических операций.

2,3,4,5

Математический диктант.

Тема 1.2. Формулы логики.

ОК.5, ПК.3.4

Упрощение в записи формулы логики.

2,3,4,5

Устное собеседование.

Тема 1.3. Таблицы истинности.

ОК.7, ПК.2.4

Интерпретация формул логики таблицей истинности.

2,3,4,5

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

Тема 1.4. ДНФ, КНФ.

ОК.2, ПК.1.1

Применение упрощённого метода построения таблиц истинности для ДНФ, КНФ.

2,3,4,5

Аудиторная письменная самостоятельная работа.

Тема 1.5. Законы логики.

ОК.8, ПК.1.2

Применение законов логики для упрощения формул.

2,3,4,5

Решение задач.

Тема 1.6. Равносильные преобразования.

ОК.6, ПК.3.4

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

2,3,4,5

Аудиторная письменная самостоятельная работа.

Раздел 2. Булевы функции.

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

Тема 2.1.1. СДНФ. Методика представления.

ОК.4, ПК.2.4

Использование методики представления булевой функции в виде СДНФ.

2,3,4,5

Письменный опрос по индивидуальным заданиям.

Тема 2.1.2. СКНФ. Методика представления.

ОК.9, ПК.1.2

Использование методики представления булевой функции в виде СКНФ.

2,3,4,5

Письменный опрос по индивидуальным заданиям.

Тема 2.2. Операция двоичного сложения. Многочлен Жегалкина.

ОК.8, ПК.1.1

Интерпретация булевой функции в виде многочлена Жегалкина.

2,3,4,5

Устное собеседование, решение задач.

Тема 2.3. Полнота множества функций. Важнейшие замкнутые классы.

ОК.6, ПК.3.4

Определение класса принадлежности данной булевой функции.

2,3,4,5

Фронтальный устный опрос.

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

ОК.2, ПК.2.4

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

2,3,4,5

Индивидуальный письменный опрос.

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

Тема 3.1. Основные понятия. Теоретико-множественные диаграммы.

ОК.9, ПК.1.1

Интерпретация множеств теоретико-множественными диаграммами.

2,3,4,5

Аудиторная письменная самостоятельная работа.

Тема 3.2. Операции над множествами и их свойства.

ОК.3, ПК.2.4

Выполнение операций над множествами; выбор формул подсчёта элементов в объединении множеств.

2,3,4,5

Письменные индивидуальные задания.

Тема 3.3. Соответствие между теоретико-множественными и логическими операциями.

ОК.7, ПК.3.4

Реализация теоретико-множественных соотношений с помощью формул логики.

2,3,4,5

Письменный опрос.

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

Тема 4.1. Основные понятия. Обычные логические операции над предикатами.

ОК.4, ПК.1.2

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

2,3,4,5

Устное собеседование.

Тема 4.2. Кванторные операции над предикатами.

ОК.1. ПК.1.1

Выполнение кванторных операций над предикатами.

2,3,4,5

Аудиторная письменная работа.

Тема 4.3. Бинарные отношения.

ОК.5, ПК.3.4

Исследование бинарных отношений на рефлексивность, симметричность, транзитивность; выделение классов эквивалентности бинарных отношений.

2,3,4,5

Устный опрос, письменные индивидуальные задания.

Раздел 5. Теория отображений и алгебра подстановок.

Тема 5.1. Отображения. Основные понятия.

ОК.9, ПК.1.2

Определение вида отображения; интерпретация внутреннего отображения диаграммой.

2,3,4,5

Устное собеседование.

Тема 5.2. Подстановки. Основные понятия.

ОК.3, ПК.1.1

Реализация методики решения простейших уравнений в алгебре подстановок.

2,3,4,5

Письменный опрос.

Раздел 6. Алгоритмическое перечисление (генерирование) комбинаторных объектов.

Тема 6.1. Генерирование двоичных слов заданной длины.

ОК.7, ПК.1.2

Реализация принципа генерирования двоичных слов заданной длины.

2,3,4,5

Письменный опрос по индивидуальным заданиям.

Тема 6.2. Генерирование элементов декартова произведения множеств.

ОК.5, ПК.2.4

Реализация принципа генерирования элементов декартова произведения множеств.

2,3,4,5

Письменный опрос по индивидуальным заданиям.

Тема 6.3. Генерирование перестановок заданной длины.

ОК.2, ПК.1.1

Реализация принципа генерирования перестановок заданной длины.

2,3,4,5

Письменный опрос по индивидуальным заданиям.

Тема 6.4. Генерирование К-элементных подмножеств данного множества.

ОК.6, ПК.2.4

Реализация принципа генерирования

К-элементных подмножеств данного множества.

2,3,4,5

Письменный опрос по индивидуальным заданиям.

Тема 6.5. Генерирование всех подмножеств данного множества.

ОК.9, ПК.3.5

Реализация принципа генерирования всех подмножеств данного множества.

2,3,4,5

Письменный опрос по индивидуальным заданиям.

Раздел 7. Основы алгебры вычетов.

Тема 7.1. Сравнения и их свойства.

ОК.4, ПК.1.1

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

2,3,4,5

Математический диктант.

Тема 7.2. Вычеты.

ОК.3, ПК.3.4.

Использование алгебры вычетов в криптоустойчивых системах.

2,3,4,5

Решение задач.

Раздел 8. Простейшие криптографические шифры.

Тема 8.1. Шифры замены.

ОК.2, ПК.1.2

Выполнение шифрования и дешифрования при помощи шифров замены.

2,3,4,5

Решение задач.

Тема 8.2. Коды Хемминга.

ОК.3, ПК.2.4

Выполнение кодирования по алгоритму построения кода Хемминга.

2,3,4,5

Выполнение упражнений.

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

Тема 9.1. Вводные понятия.

ОК.9, ПК.3.4

Осуществление операций над словами.

2,3,4,5

Фронтальный опрос.

Тема 9.2. Машина Тьюринга.

ОК.7, ПК.2.4

Решение задач на задание программы машины.

2,3,4,5

Проверочная индивидуальная письменная работа.

Тема 9.3. Сочетания машин Тьюринга.

ОК.4, ПК.1.2

Интерпретировать словесное описание машины её программой.

2,3,4,5

Проверочная самостоятельная письменная работа.

Тема 9.4. Тьюрингов подход к понятию «алгоритм»

ОК.8, ПК.1.1

Реализация алгоритма, заданного машиной Т, к задача Z.

2,3,4,5

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

Оценка индивидуальных образовательных достижений по результатам текущего и итогового контроля производится в соответствии с универсальной шкалой (таблица).

Процент результативности (правильных ответов)

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

балл (отметка)

вербальный аналог

90 ÷ 100

5

отлично

80 ÷ 89

4

хорошо

70 ÷ 79

3

удовлетворительно

менее 70

2

не удовлетворительно

На этапе промежуточной аттестации по медиане качественных оценок индивидуальных образовательных достижений экзаменационной комиссией определяется интегральная оценка освоенных обучающимися профессиональных и общих компетенций как результатов усвоения профессионального модуля.