rpd000007009 (230700 (09.03.03).Б9 Компьютерный дизайн), страница 2

Прикрепленные файлы: Экзамен (4 семестр).doc

1. УЧЕБНО-МЕТОДИЧЕСКОЕ И ИНФОРМАЦИОННОЕ ОБЕСПЕЧЕНИЕ ДИСЦИПЛИНЫ

а)основная литература:

1. Осипова В.А., Нефедов В.Н. Дискретная математика. М., МАИ, 1992.

2. Яблонский С.В. Дискретная математика. М.: Наука, 2001.

3. Аржененко А.Ю., Григоревский Н.В. Учебное пособие по дискретной математике (для технических и экономических специальностей).(в печати).

б)дополнительная литература:

1. Кофман А. Введение в прикладную комбинаторику. М.: Наука, 1975.

2. Виленкин Д.С. Введение в комбинаторику. М.: Наука, 2000.

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

4. Берж К. Теория графов и ее применения. М.: ИЛ, 1962.

в)программное обеспечение, Интернет-ресурсы, электронные библиотечные системы:

http://www.exponenta.ru/educat/class/courses/student/la/examples.asp

http://www.ctve.ru

Интернет-тест по математике: http://www.mathtest.ru

www.mon.gov.ru – Министерство образования РФ.

www.expert.ru (Эксперт).

www.nns.ru (Национальная электронная библиотека).

www.rsl.ru (Российская государственная библиотека).

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

1. Компьютерный класс с ПК для проведения практических занятий.

2. Класс видеопрезентаций для проведения практических занятий.

3. Поточная аудитория с информационным проектором TDP-S8.

4. Локальная вычислительная сеть кафедры с выходом в Internet/

Приложение 1
к рабочей программе дисциплины
«Дискретная математика »

Аннотация рабочей программы

Дисциплина Дискретная математика является частью Математического и естественно-научный цикл дисциплин подготовки студентов по направлению подготовки Прикладная информатика. Дисциплина реализуется на 3 факультете «Московского авиационного института (национального исследовательского университета)» кафедрой (кафедрами) 311.

Дисциплина нацелена на формирование следующих компетенций: ОК-7.

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

Преподавание дисциплины предусматривает следующие формы организации учебного процесса: Лекция, мастер-класс, Практическое занятие.

Программой дисциплины предусмотрены следующие виды контроля: промежуточная аттестация в форме Экзамен (4 семестр).

Общая трудоемкость освоения дисциплины составляет 4 зачетных единиц, 144 часов. Программой дисциплины предусмотрены лекционные (36 часов), практические (18 часов), лабораторные (0 часов) занятия и (63 часов) самостоятельной работы студента. В курсе "Дискретная математика" рассматриваются такие разделы,как:математическая логика и комбинаторика,элементы теории множеств,теория графов

Приложение 2
к рабочей программе дисциплины
«Дискретная математика »

Cодержание учебных занятий

1. Лекции

1.1.1. Высказывания, отрицание, дизъюнкция, конъюнкция, эквиваленция, импликация. Формула. Виды формул (АЗ: 4, СРС: 3)

Тип лекции: Информационная лекция

Форма организации: Лекция, мастер-класс

1.1.2. Булевы функции одной и двух переменных. Основные соотношения (АЗ: 2, СРС: 3)

Тип лекции: Информационная лекция

Форма организации: Лекция, мастер-класс

1.1.3. Базисы. Замкнутые классы. Теорема Поста (АЗ: 2, СРС: 3)

Тип лекции: Информационная лекция

Форма организации: Лекция, мастер-класс

1.1.4. Совершенные нормальные формы. Приведение к с.д.н.ф. и с.к.н.ф. двумя способами (АЗ: 2, СРС: 3)

Тип лекции: Информационная лекция

Форма организации: Лекция, мастер-класс

1.1.5. Проблема минимизации. Алгоритм Мак-Класски. (АЗ: 2, СРС: 3)

Тип лекции: Информационная лекция

Форма организации: Лекция, мастер-класс

1.1.6. Предикаты. Кванторы общности и существования (АЗ: 2, СРС: 3)

Тип лекции: Информационная лекция

Форма организации: Лекция, мастер-класс

1.1.7. Правило суммы и произведения. Размещения, перестановки, сочетания. Разбиения. Формула включения (АЗ: 2, СРС: 3)

Тип лекции: Информационная лекция

Форма организации: Лекция, мастер-класс

1.2.1. Множества. Дополнение, объединение, пересечение, симметрическая разность, включение. Связь алгебры множеств и булевой алгебры (АЗ: 2, СРС: 3)

Тип лекции: Информационная лекция

Форма организации: Лекция, мастер-класс

1.2.2. Прямое произведение. Разбиение, покрытие. Отношения на множествах. Отношение эквивалентности. Отношения частичного, линейного, полного порядков (АЗ: 2, СРС: 3)

Тип лекции: Информационная лекция

Форма организации: Лекция, мастер-класс

1.2.3. Равномощность множеств. Кардинальное число. Счетное множество. Континуум. Теорема Кантора (АЗ: 2, СРС: 3)

Тип лекции: Информационная лекция

Форма организации: Лекция, мастер-класс

1.3.1. Графы. Смежность и инцидентность. Степень вершины. Матричные описания графов (АЗ: 2, СРС: 1)

Тип лекции: Информационная лекция

Форма организации: Лекция, мастер-класс

1.3.2. Маршруты и связность.Метод латинской композ. Алгоритм фронта волны.Нагруженные графы.Экстремальные пути.Алгоритм Форда.Эйлеровы и гамильтоновы графы (АЗ: 4, СРС: 1)

Тип лекции: Информационная лекция

Форма организации: Лекция, мастер-класс

1.3.3. Деревья,их свойства.Полные графы.Циклы.Цикломатическое число.Векторное пространство циклов.Остовное дерево и кодерево.Построение базисной с-мы циклов (АЗ: 4, СРС: 1)

Тип лекции: Информационная лекция

Форма организации: Лекция, мастер-класс

1.3.4. Внутренняя устойчивость.Хроматическое число.Теорема Кенига и Куратовского.Проблема четырех красок.Внешняя устойчивость.Ядро.Метод Магу.Функция Гранди (АЗ: 2, СРС: 1)

Тип лекции: Информационная лекция

Форма организации: Лекция, мастер-класс

1.3.5. Определение транспортной сети. Насыщенная транспортная сеть. Алгоритм Форда-Фалкерсена (АЗ: 2, СРС: 1)

Тип лекции: Информационная лекция

Форма организации: Лекция, мастер-класс

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

1.1.1. Построение таблиц истинности. Определение типа формул. Исследование равносильностей и тавтологий (АЗ: 2, СРС: 3)

Форма организации: Практическое занятие

1.1.2. Приведение к с.д.н.ф. и с.к.н.ф (АЗ: 2, СРС: 3)

Форма организации: Практическое занятие

1.1.3. Минимизация булевых функций. Отрицание предикатов (АЗ: 2, СРС: 3)

Форма организации: Практическое занятие

1.1.4. Решение элементарных комбинаторных задач. Контрольная работа (АЗ: 2, СРС: 3)

Форма организации: Практическое занятие

1.2.1. Определение типа бинарного отношения. Нахождение равномощных множеств (АЗ: 2, СРС: 4)

Форма организации: Практическое занятие

1.3.1. Построение графов по матрицам и матриц по диаграммам. Исследование ребер и вершин (АЗ: 2, СРС: 3)

Форма организации: Практическое занятие

1.3.2. Метод латинской композиции. Поиск кратчайшего и максимального пути (АЗ: 2, СРС: 3)

Форма организации: Практическое занятие

1.3.3. Построение методом Магу максимально внутренне устойчивых и минимально внешне устойчивых подмножеств. Отыскание ядра и хроматического числа (АЗ: 2, СРС: 3)

Форма организации: Практическое занятие

1.3.4. Построение максимального потока (АЗ: 2, СРС: 3)

Форма организации: Практическое занятие

1. Лабораторные работы

1. Типовые задания

Приложение 3
к рабочей программе дисциплины
«Дискретная математика »

Прикрепленные файлы

Экзамен (4 семестр).doc

Промежуточная аттестация №1

Экзамен (4 семестр)

Семестр: 4

Вид контроля: Э

Вопросы:

1. Множества и операции над ними

2. Основные тождества алгебры множеств.

3. Доказательство тождеств с множествами с помощью диаграмм Венна , рассуждений и преобразований.

4. Прямое произведение множеств.

5. Бинарные отношения между элементами двух множеств и действия над ними

6. Свойства бинарного отношения на множестве.

7. Типы бинарных отношений: отношения эквивалентности и частичного порядка.

8. Задачи и принципы комбинаторики.

9. Вычисление количества размещений, сочетаний и разбиений.

10. Высказывания и операции над ними.

11. Формулы, таблицы истинности , равносильность формул логики высказываний.

12. Основные равносильности логики высказываний.

13. Нормальные формы формул логики высказываний.

14. Тождественно истинные формулы.

15. Проверка правильности рассуждений

16. Логика предикатов.

17. Булевы функции. Способы задания.

18. Табличный способ приведения булевой функции к совершенной дизъюнктивной нормальной форме.

19. Минимизация булевых функций в классе ДНФ.

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

21. Представление булевых функций в арифметической полной системе. Многочлены Жегалкина.

22. Графы ориентированные и неориентированные. Матричные способы задания графов.

23. Нахождение путей минимальной длины в орграфе ( простой и нагруженный случаи).

24. Связность вершин графа. Компоненты связности.

25. Цикломатическое число. Базис в множестве циклов

26. Деревья и циклы в графе.

27. Поиск остовного дерева наименьшей длины

28. Нахождение устойчивых множеств вершин в графах. Алгоритм Магу.

29. Функция Гранди. Ядро графа.

30. Специальные пути в графах.

31. Потоки в транспортных сетях. Алгоритм Форда- Фалкерсона нахождения максимального потока.

Версия: AAAAAAS+V3o Код: 000007009