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

Вид материалаПрограмма дисциплины

Содержание


1. Цели и задачи дисциплины
2. Требования к уровню освоения содержания дисциплины
3. Содержание дисциплины
3.2. Темы практических и семинарских занятий
3.3. Лабораторный практикум
3.6. Самостоятельная работа
4.1. Рекомендуемая литература
Подобный материал:
Министерство образования и науки Российской Федерации Федеральное агентство по образованию

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

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

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

направление подготовки:

230100 "Информатика и вычислительная техника"

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

230101"Вычислительные машины, комплексы, системы и сети",

230102 "Автоматизированные системы обработки информации и управления".

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

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



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

Всего часов

Семестр 2

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

140

140

Аудиторные занятия

85

85

Лекции

34

34

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

51

51

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

55

55

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




экзамен

Обнинск 2008

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

к

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

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

мов" и др.

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

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

В результате изучения дисциплины студент должен

знать основные факты теории множеств и отношений, алгебры логики, комбинаторики | теории графов.

уметь выводить формулы и доказывать теоремы,

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

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

3.1. ЛЕКЦИИ

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

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

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

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

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

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

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

Свободные и связанные переменные. Кванторы существования и всеобщности, их свой­ства. Свойства кванторов. Предваренная и сколемовская форма предиката. Литература. [1], глава 1, с. 3 - 26.

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

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

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

Декартово произведение множеств. Бинарное отношение, обратное отношение, допол­нение бинарного отношения. Композиция бинарных отношений, свойства.

Отношения эквивалентности, разбиение множества на классы эквивалентности. Час­тично и линейно упорядоченные множества. Функциональные отношения, сюръективные, инъективные и биективные функции, их свойства. Теорема об обратной функции.

Мощность множества; счетные и континуальные множества.

Литература. [1], глава 2, с. 27 - 35.

Операции

3. Алгебры - 35 ч.

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

Понятие кольца и поля, примеры. Делители нуля, обратимые и необратимые элемен­ты. Кольцо многочленов. Идеалы, главные идеалы. Факторкольцо. Кольцо вычетов Zu. Конечные поля.

Литература. [4], с. 71 - 81.

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

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

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

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

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

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

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


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



Раздел

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

Литература | Часы

1. 1.

1. 1. 1.

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

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

[2], с. 4 - 6

[2], с. 6 - 7

[2], с. 7 - 8

[2], с. 9

[2], с. 9 - 10

4 ч.

2 ч.

4 ч.

2 ч.

2 ч.

2. 2. 2. 2.

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

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

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

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

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

4 ч.

2 ч.

2 ч.

4 ч.

3. 3. 3. 3.

Понятие группы, подгруппа, порядок элемента Факторгруппа, прямое произведение групп. Кольцо, поле, идеалы, факторкольцо Конечные поля

[3], с. 12 - 15

[3], с. 17 -- 20

[3], с. 22 - 26, 30 [3], с. 30 -32

4 ч.

2 ч.

4 ч.

2 ч.

4. 4. 4. 4.

Понятие графа, изоморфизм графов Плоские и планарные графы Цикломатическое и хроматическое число графа Алгоритмы на графах

[2], с. 27 - 28 [2], с. 28 - 29 [2], с. 29 - 30 [2], с. 30

2 ч.

2 ч.

2 ч. 1ч.

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

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

3.4. КУРСОВЫЕ ПРОЕКТЫ (РАБОТЫ) Не предусмотрены.

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



Раздел

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

Неделя

1. 2.

3,4.

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

7 12 17

3.6. САМОСТОЯТЕЛЬНАЯ РАБОТА
  1. Минимизация ДНФ с помощью карт Карно, [13], с. 16 - 17.
  2. Операции на множествах, [4], с. 37 - 42.
  3. Счетные и континуальные множества, [13], с. 52 - 54.
  4. Хроматический многочлен графа, [13], с. 84 - 85. Контроль проводится путем опроса на семинарских занятиях.

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

4.1.1. Основная литература
  1. Насыров А.З.. Насыров З.Х. Дискретная математика. — Обнинск: ИАТЭ, 2005, 200 экз.
  2. Насыров З.Х. Сборник задач по дискретной математике. — Обнинск: ИАТЭ, 2003. 400 эк:
  3. Насыров З.Х. Сборник задач по высшей алгебре. - Обнинск: ИАТЭ. 2004, 200 экз.

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

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

5. О. Соболева Т.С.. Чечкин А.В. Дискретная математика. М.: "Академия". 2005.

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

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

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

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

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

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

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

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

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

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

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

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

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