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

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

ОБНИНСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ АТОМНОЙ ЭНЕРГЕТИКИ (ИАТЭ)

ПРОГРАММА ДИСЦИПЛИНЫ

ЕН.Ф2 ДИСКРЕТНАЯ МАТЕМАТИКА

по специальности 230201 — "Информационные системы и технологии".

Форма обучения очная

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



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

Всего часов

Семестр 2

Общая трудоёмкость дисциплины Аудиторные занятия Лекции

Практические занятия Самостоятельная работа

130

68

34

34

62

130

68

34

34

62

Вид итогового контроля




экзамен

Обнинск 2008

^ 1. ЦЕЛИ И ЗАДАЧИ ДИСЦИПЛИНЫ

Курс "Дискретная математика" предназначен для студентов 2 семестра факультета кибернетики, обучающихся по специальности ''Информационные системы и технологии" В курсе излагаются такие разделы дискретной математики, как алгебра логики, множес­тва и отношения, комбинаторика и теория графов.

Целью курса "Дискретная математика" является формирование необходимой матема­тической базы для изучения последующих общепрофессиональных и специальных дисцип­лин таких, как "Алгоритмические языки и программирование", "Информатика", "Логи­ческое и функциональное программирование", "Математическая логика и теория алгорит­мов" и др.

Задачей дисциплины является обучение студентов методам и мышлению, характерным

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

^ 2. ТРЕБОВАНИЯ К УРОВНЮ ОСВОЕНИЯ СОДЕРЖАНИЯ ДИСЦИПЛИНЫ

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

иметь навыки решения основных видов задач указанных разделов дискретной мате­матики.

^ 3. СОДЕРЖАНИЕ ДИСЦИПЛИНЫ

3.1. ЛЕКЦИИ

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

1. Алгебра логики - 40 ч.

Понятие высказывания. Операции дизъюнкции, конъюнкции и отрицания, их свойства. Операции импликации, эквиваленции и суммы по модулю 2, их свойства.

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

Теорема о реализации булевой функции в совершенной дизъюнктивной нормальной форме. Конъюнкты, простые конъюнкты. Теорема о сокращенной ДНФ, следствие о ми­нимальной ДНФ. Приведение пропозициональных формул к ДНФ, их минимизация с по­мощью правил поглощения и образования союзов.

Релейно - контактные схемы. Теорема о построении контактной схемы по заданной функции проводимости.

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

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

Литература. [1], глава 1, с. 3 - 26

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

2. Множества и отношения - 30 ч.

Операции пересечения, объединения, разности и симметрической разности множеств их свойства.

Декартово произведение множеств. Бинарное отношение, обратное отношение, дополнение бинарного отношения. Композиция бинарных отношений, свойства. Отношения эквивалентности, разбиение множества на классы эквивалентности. Час­тично и линейно упорядоченные множества. Функциональные отношения, сюръективные инъективные и биективные функции, их свойства. Теорема об обратной функции. Литература. [1], глава 2, с. 27 - 35.

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

3. Комбинаторика - 30 ч.

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

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

Формула включений и исключений. Задача о беспорядках. Латинские прямоугольники.

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

Литература. [1]. глава 3, с. 36 - 46.

Основные понятия теории графов; маршруты; циклы; связность; планарные графы.

4. Теория графов - 30 ч.

Определение графа и орграфа, простой граф, теорема о "рукопожатиях", матрица смежности и ее свойства, способы представления графов в ЭВМ. Подграф. Частичный, нулевой, полный и дополнительный граф. Соединение графов. Изоморфизм графов, теоре­ма о реализации графов в трехмерном пространстве.

Плоские и планарные графы, теорема о непланарности К3,3 Формулировка теоремы Куратовского-Понтрягина. Цепи, теорема о выделении элементарной цепи, связность гра­фа и ее изменение при удалении ребра. Теорема Эйлера о плоских графах, следствия.

Теорема об эйлеровых графах, задача о кенигсбергских мостах. Деревья и их свойства. Цикломатическое число графа, монотонность и смысл цикломатического числа. Хрома­тическое число графа, примеры. Теорема о четырех красках. Теорема о хроматическом многочлене графа.

Алгоритм обхода графа в глубину и в ширину.

Литература. [1], глава 4, с. 47 - 63.

^ 3.2. ТЕМЫ ПРАКТИЧЕСКИХ И СЕМИНАРСКИХ ЗАНЯТИЙ

Раздел

1.

1.

1.

1.

1.

2. 2. 2.

2.

3. 3. 3. 3.

4.

4.

4.

4.

Тема практического или семинарского занятия

Логические операции

БФ и их реализация многочленами Жегалкина Минимизация ДНФ и контактные схемы Конъюнктивная нормальная форма

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

Предикаты, кванторы

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

Декартово произведение, бинарные отношения

Отношения эквивалентности и порядка, функции

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

Сочетания с повторениями, ф-ла вкл. и искл. Производящие функции

Линейные однородные рекуррентности

Понятие графа, изоморфизм графов

Плоские и планарные графы

Цикломатическое и хроматическое число графа Алгоритмы на графах

Литература

[2], с. 4-6

[2], с. 6 - 7 [2], с. 7 - 8 [2], с. 9

[2], с. 9 - 10

[2], с. 10 - 13 [2], с. 13 - 14 [2], с. 15 - 16 [2], с. 16 - 20

[2], с. 21 - 23 [2], с. 23 - 24 [2], с. 25 - 26 [2], с. 26

[2], с. 27 - 28

[2], с. 28 - 29

[2], с. 29 - 30

[2], с. 30

Часы

2 ч. 2 ч. 2 ч.

ч.

ч.

2 ч. 2 ч. 2 ч. 2 ч.

4 ч. 2 ч. 2 ч. 2 ч.

2 ч. 2 ч. 2 ч. 1 ч.

^ 3.3. ЛАБОРАТОРНЫЙ ПРАКТИКУМ

Не предусмотрен.

3.4. КУРСОВЫЕ ПРОЕКТЫ (РАБОТЫ)

Не предусмотрены.

3.5. ФОРМЫ ТЕКУЩЕГО КОНТРОЛЯ



Раздел

Форма текущего (рубежного) контроля

Неделя

1.

2.

3,4

Аудиторная рейтинговая контрольная работа - 18 баллов Аудиторная рейтинговая контрольная работа - 18 баллов Аудиторная рейтинговая контрольная работа - 19 баллов

7

12

17

^ 3.6. САМОСТОЯТЕЛЬНАЯ РАБОТА

Минимизация ДНФ с помощью карт Карно, [12], с. 16 - 17.

Операции на множествах, [3], с. 37 - 42.

Счетные и континуальные множества, [12], с. 52 - 54.

Хроматический многочлен графа, [12], с. 84 - 85. Контроль проводится путем опроса на семинарских занятиях.

^ 4.1. РЕКОМЕНДУЕМАЯ ЛИТЕРАТУРА

4.1.1. Основная литература

1. Насыров А.З.. Насыров З.Х. Дискретная математика. — Обнинск: ИАТЭ. 2005, 200 экз.

2. Насыров З.Х. Сборник задач по дискретной математике. — Обнинск: ИАТЭ, 2003, 400 экз.

4.1.2. Дополнительная литература

Кузнецов О.П., Адельсон-Вельский Г.М. Дискретная математика для инженера. М.: Энергоатомиздат, 1988.

Гаврилов Г.П.. Сапоженко А.А. Задачи и упражнения по курсу дискретной математики.

М.: Наука. 1992.

Лавров И.А., Максимова Л.Л. Задачи по теории множеств, математический логике и тео­рии алгоритмов. - М.: Наука, 1975.

Холл М. Комбинаторика. - М.: Мир, 1970.

Комбинаторный анализ. Задачи и упражнения./Под ред. К.А. Рыбникова. - М.: Наука. 1982.

Липский В. Комбинаторика для программистов. - М.: Мир, 1988.

Зыков А.А. Основы теории графов. - М.; Наука, 1987.




Сре О. Теория графов. — М.: Наука, 1980.

Харари Ф. Теория графов. - М.: Мир, 1973.

Насыров З.Х. Дискретная математика. - Обнинск: ИАТЭ, 1999.

Дискретная математика. Журнал Российской академии наук.

4.2. СРЕДСТВА ОБЕСПЕЧЕНИЯ ОСВОЕНИЯ ДИСЦИПЛИНЫ

Не предусмотрены.

МАТЕРИАЛЬНО-ТЕХНИЧЕСКОЕ ОБЕСПЕЧЕНИЕ ДИСЦИПЛИНЫ

Не предусмотрено.