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

Вид материала

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

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

Подобный материал:

• Российской Федерации Федеральное агентство по образованию обнинский государственный, 84.76kb.
• Российской Федерации Федеральное агентство по образованию обнинский государственный, 90.77kb.
• Российской Федерации Федеральное агентство по образованию обнинский государственный, 130.31kb.
• Российской Федерации Федеральное агентство по образованию обнинский государственный, 81.87kb.
• Федеральная целевая программа "Развитие электронной компонентной базы и радиоэлектроники", 3538.74kb.
• Я модели программно-аппарат-ного комплекса для обработки и оценки спектров сигналов, 10.18kb.
• Роль институциональных преобразований в лесном комплексе России, 43.15kb.
• Рабочей программы учебной дисциплины: код года утверждения, 303.46kb.
• Министерство образования и науки российской федерации федеральное агентство по образованию, 32.48kb.
• Федеральное агентство по образованию Пермский государственный технический университет, 171.98kb.

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

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

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

ЕН.Ф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 ч.

1. ч.
   
2. ч.
   

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

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

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