Реферат: Российской Федерации Федеральное агентство по образованию обнинский государственный технический университет атомной энергетики (иатэ) программа дисциплины
Министерство образования и науки Российской Федерации Федеральное агентство по образованию
ОБНИНСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ АТОМНОЙ ЭНЕРГЕТИКИ (ИАТЭ)
ПРОГРАММА ДИСЦИПЛИНЫ
ЕН. ФЗ ДИСКРЕТНАЯ МАТЕМАТИКА
направление подготовки:
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. МАТЕРИАЛЬНО-ТЕХНИЧЕСКОЕ ОБЕСПЕЧЕНИЕ ДИСЦИПЛИНЫ
Не предусмотрено.
еще рефераты
Еще работы по разное
Реферат по разное
Программа дисциплины «Политическая культура в странах Африки» Автор: Исаев Леонид Маркович
17 Сентября 2013
Реферат по разное
Программа дисциплины высшая математика для студентов специальности 080507 «Менеджмент организаций» -бакалавры
17 Сентября 2013
Реферат по разное
Программа дисциплины дпп. Дс. 01 Компьютерное моделирование в химии цели и задачи дисциплины
17 Сентября 2013
Реферат по разное
Программа дисциплины Психология для направления: 521600 экономика (2-я ступень высшего профессионального образования)
17 Сентября 2013