Российской Федерации Федеральное агентство по образованию обнинский государственный технический университет атомной энергетики (иатэ) программа дисциплины
| Вид материала | Программа дисциплины |
- Российской Федерации Федеральное агентство по образованию обнинский государственный, 90.77kb.
- Российской Федерации Федеральное агентство по образованию обнинский государственный, 130.31kb.
- Российской Федерации Федеральное агентство по образованию обнинский государственный, 77.01kb.
- Российской Федерации Федеральное агентство по образованию обнинский государственный, 81.87kb.
- Федеральная целевая программа "Развитие электронной компонентной базы и радиоэлектроники", 3538.74kb.
- Я модели программно-аппарат-ного комплекса для обработки и оценки спектров сигналов, 10.18kb.
- Роль институциональных преобразований в лесном комплексе России, 43.15kb.
- Рабочей программы учебной дисциплины: код года утверждения, 303.46kb.
- Министерство образования и науки российской федерации федеральное агентство по образованию, 32.48kb.
- Федеральное агентство по образованию Пермский государственный технический университет, 171.98kb.
Министерство образования и науки Российской Федерации Федеральное агентство по образованию
ОБНИНСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ АТОМНОЙ ЭНЕРГЕТИКИ (ИАТЭ)
ПРОГРАММА ДИСЦИПЛИНЫ
ЕН. ФЗ ДИСКРЕТНАЯ МАТЕМАТИКА
направление подготовки:
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. САМОСТОЯТЕЛЬНАЯ РАБОТА
- Минимизация ДНФ с помощью карт Карно, [13], с. 16 - 17.
- Операции на множествах, [4], с. 37 - 42.
- Счетные и континуальные множества, [13], с. 52 - 54.
- Хроматический многочлен графа, [13], с. 84 - 85. Контроль проводится путем опроса на семинарских занятиях.
4.1. РЕКОМЕНДУЕМАЯ ЛИТЕРАТУРА
4.1.1. Основная литература
- Насыров А.З.. Насыров З.Х. Дискретная математика. — Обнинск: ИАТЭ, 2005, 200 экз.
- Насыров З.Х. Сборник задач по дискретной математике. — Обнинск: ИАТЭ, 2003. 400 эк:
- Насыров З.Х. Сборник задач по высшей алгебре. - Обнинск: ИАТЭ. 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. МАТЕРИАЛЬНО-ТЕХНИЧЕСКОЕ ОБЕСПЕЧЕНИЕ ДИСЦИПЛИНЫ
Не предусмотрено.