страница 1
Учреждение образования
“Гродненский государственный университет имени Янки Купалы”
-
УТВЕРЖДАЮ
Декан факультета математики
и информатики
___________________ ____________
«___» _______ _____ г.
Регистрационный № УД- _____/р.
|
Дискретная математика
Учебная программа для специальности:
(рабочий вариант)
1-310301-02 Математика (научно-педагогическая деятельность)
(код специальности) (наименование специальности)
Факультет математики и информатики
Кафедра алгебры, геометрии и методики преподавания математики
Курс 1
Семестр 2
Лекции ____26_____ Экзамен _________
(количество часов) (семестр)
Практические (семинарские)
занятия ____24___ Зачёт ____2__________
(количество часов) (семестр)
Всего аудиторных часов Форма получения
по дисциплине ____50___ высшего образования дневная
(количество часов)
Составила М.Н.Гончарова, кандидат физико-математических наук, доцент
2010 г.
Рабочая программа составлена на основе учебной программы по дисциплине “Дискретная математика”, утверждённой 05.09.2008
Регистрационный № УД - 08/МИ-003/уч.
(дата утверждения, регистрационный номер)
Рассмотрена и рекомендована к утверждению в качестве рабочего варианта на заседании кафедры алгебры, геометрии и методики преподавания математики
26.06.2010 г., протокол N°10
Заведующий кафедрой
____________________ А.А. Гринь
Одобрена и рекомендована к утверждению на заседании Методической комиссии факультета математики и информатики
29.06.2010 г., протокол № 6
Председатель
________________ Ю.Я. Романовский
Одобрена и рекомендована к утверждению на заседании Совета факультета
математики и информатики
30.06.2010 г., протокол № 6
Учёный секретарь
-
ПОЯСНИТЕЛЬНАЯ ЗАПИСКА
-
Цель преподавания дисциплины
Изучение математических задач, в которых основной спецификой является дискретность, с целью применения результатов при исследовании сложных технических систем
-
Задачи изучения дисциплины
В результате изучения дисциплины студенты должны:
-
знать функции алгебры логики, способы из задания, замкнутые классы функций алгебры логики, полные системы булевых функций, способы выяснения полноты конкретных систем булевых функций, способы минимизации дизъюнктивных нормальных форм, проблемы теории алгоритмов, определение машины Тьюринга;
-
владеть навыками работы с дискретными множествами, определять полноту конкретных систем функций алгебры логики, строить тупиковые, сокращенные дизъюнктивные нормальные формы, строить машины Тьюринга, вычисляющие конкретные функции.
-
СОДЕРЖАНИЕ УЧЕБНОГО МАТЕРИАЛА
№
п/п
|
Наименование
раздела, темы дисциплины
|
Содержание в соответствии с
типовой учебной программой (учебной программой)
|
1
| Алгебра логики
|
Булевы функции. Табличный способ задания. Существенные и несущественные переменные. Формулы. Эквивалентность формул. Элементарные функции и их свойства. Разложение функции по переменным. Совершенная дизъюнктивная нормальная форма. Полные системы функций. Полиномы Жегалкина. Представление булевых функций полиномами. Замыкание. Свойства операции замыкания. Замкнутые классы Т0 и Т1. Линейные функции. Лемма о нелинейной функции. Самодвойственные функции. Принцип двойственности. Лемма о несамодвойственной функции. Монотонные функции. Лемма о немонотонной функции. Критерий полноты системы функций алгебры логики (теорема Поста).
|
2
|
Дизъюнктивные нормальные формы
|
Проблема минимизации дизъюнктивных форм. Сложность ДНФ. Тупиковая, минимальная и сокращенная ДНФ. Геометрическая интерпретация. Задача о покрытии. Алгоритм нахождения всех тупиковых ДНФ, минимальных ДНФ, сокращенной ДНФ. Методы построения сокращенной ДНФ.
|
3
|
Элементы теории алгоритмов
|
Определение машины Тьюринга. Типы композиции и принцип двойственности для машин Тьюринга. Машинные коды. Определение вычислимой функции. Операции суперпозиции, минимизации, примитивной рекурсии на множестве вычислимых функций.
|
3. УЧЕБНО-МЕТОДИЧЕСКАЯ КАРТА
Номер раздела, темы, занятия
|
Название раздела,темы, занятия;
перечень изучаемых вопросов
|
Количество аудиторных часов
|
Материальное обеспечение занятия (наглядные, методические пособия и др.)
|
Литература
|
Формы контроля знаний
|
лекции
|
практические (семинарские) занятия
|
лабораторные занятия
|
управляемая самостоятельная работа студентов
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
9
|
1
|
Алгебра логики
|
16
|
14
|
|
2
|
|
|
|
1.1
|
Высказывания и операции над ними.
|
2
|
2
|
|
|
|
[1]-[4]
|
|
1.2
|
Логические формулы. Функции алгебры логики. Эквивалентность формул. Логически правильные выводы.
|
2
|
2
|
|
|
|
[1]-[5]
|
|
1.3
|
Существенные и несущественные переменные. Элементарные функции и их свойства.
|
2
|
2
|
|
|
|
[1]-[5]
|
тест
|
1.4
|
Разложение функции по переменным. Совершенная дизъюнктивная нормальная форма.
|
2
|
|
|
2
|
Тестовые задания
|
[1]-[5]
|
|
1.5
|
Полные системы функций. Полиномы Жегалкина. Представление булевых функций полиномами. Замыкание. Свойства операции замыкания.
|
2
|
2
|
|
|
|
[1]-[5]
|
|
1.6
|
Замкнутые классы Т0 и Т1. Самодвойственные функции. Принцип двойственности. Лемма о несамодвойственной функции.
|
2
|
2
|
|
|
|
[1]-[5]
|
|
1.7
|
Линейные функции. Лемма о нелинейной функции. Монотонные функции. Лемма о немонотонной функции.
|
2
|
2
|
|
|
|
[1]-[5]
|
|
1.8
|
Критерий полноты системы функций алгебры логики (теорема Поста).
|
2
|
2
|
|
|
|
[1]-[5]
|
|
2
|
Дизъюнктивные нормальные формы
|
6
|
4
|
|
|
|
|
|
2.1
|
Проблема минимизации дизъюнктивных форм. Сложность ДНФ. Тупиковая, минимальная и сокращенная ДНФ.
|
2
|
|
|
|
|
[1],[5]
|
|
2.2
|
Геометрическая интерпретация. Задача о покрытии.
|
2
|
2
|
|
|
|
[1],[5]
|
|
2.3
|
Алгоритм нахождения тупиковых ДНФ, минимальных ДНФ, сокращенной ДНФ. Методы построения сокращенной ДНФ.
|
2
|
2
|
|
|
|
[1],[5]
|
|
3
|
Машины Тьюринга
|
4
|
4
|
|
|
|
|
|
3.1
|
Определение машины Тьюринга.
|
2
|
2
|
|
|
|
[1],[2],[5]
|
|
3.2
|
Типы композиции машин Тьюринга. Вычислимые функции
|
2
|
2
|
|
|
|
[1],[2],[5]
|
|
4. ИНФОРМАЦИОННО-МЕТОДИЧЕСКИЕ МАТЕРИАЛЫ ПО ДИСЦИПЛИНЕ
| Литература основная |
1
|
Гаврилов Г.П., Сапоженко А.А. Сборник задач по дискретной математике. М.: Наука, 1977, 368с.
|
2
|
Гончарова М.Н.. Дискретная математика: Уч. пособие. Гродно: ГрГУ. – 1999
|
3
|
Дискретная математика и математическая логика. – Брест: Изд-во Брестского гос. ун-та им. А.С.Пушкина, 2003
|
4
|
Капылова Т.I. Матэматычная логiка, Гродно, ГрГУ, 1997.
|
5
|
Яблонский С.В. Введение в дискретную математику. М.: Наука, 1979, 272с.
|
|
Литература дополнительная
|
6
|
Игошин В.И. Задачник-практикум по математической логике. – М.: Просвещение, 1986. – 160с.
|
7
|
Игошин В.И. Математическая логика и теория алгоритмов. Из-во Саратовского университета. 1991, 258с.
|
8
|
Карпов В.Г., Мощенский В.А. Математическая логика и дискретная математика, Воронеж: Машиностроение, 1977
|
9
|
Карпов В.Г., Мощенский В.А. Математическая логика и дискретная математика (учебное пособие для ун-тов по спец. «прикладная математика») – М.: Лайда, 1977
|
10
|
Кожух I.Р. Матэматыка. Минск, 1993, 258с.
|
11
|
Колмогоров А.Н., Драгалин А.Г. Ввведение в математическую логику. – М. МГУ, 1982. – 120с.
|
12
|
Корлюков А.В., Мищенко С.П. Методические указания к практическим занятиям по курсу "Математическая логика", Гродно,ГрГУ, 1983.
|
13
|
Марков А.А. Элементы математической логики. – М. МГУ, 1984. – 50с.
|
14
|
Мендельсон Э. Введение в математическую логику. – М. Наука, 1976. – 288с.
|
5. ПРОТОКОЛ СОГЛАСОВАНИЯ УЧЕБНОЙ ПРОГРАММЫ
ПО ИЗУЧАЕМОЙ УЧЕБНОЙ ДИСЦИПЛИНЕ
С ДРУГИМИ ДИСЦИПЛИНАМИ СПЕЦИАЛЬНОСТИ
Название дисциплины, с которой требуется согласование
|
Название кафедры
|
Предложения об изменениях в содержании учебной программы по изучаемой учебной дисциплине
|
Решение, принятое кафедрой, разработавшей учебную программу
(с указанием даты и номера протокола) 1
|
|
|
|
|
6. ДОПОЛНЕНИЯ И ИЗМЕНЕНИЯ К УЧЕБНОЙ ПРОГРАММЕ
ПО ИЗУЧАЕМОЙ УЧЕБНОЙ ДИСЦИПЛИНЕ
на ____ / _____ учебный год
№
п/п
|
Дополнения и изменения
|
Основание
|
|
|
|
Учебная программа пересмотрена и одобрена на заседании кафедры
(протокол № __ от _______ 200__ г.)
Заведующий кафедрой __________________________ ______________ _______________________
(степень, звание) (И.О.Фамилия)
страница 1
|