rpd000003781 (210601 (11.05.01).С6 Лазерные информационные системы и комплексы), страница 2

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

Вопросы для подготовки к экзамену/зачету:

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.Внутренне и внешне устойчивые подмножества в графе. Ядро графа. Разбиение графа на уровни.

32.Четыре определения дерева. Их эквивалентность.

33.Понятие остовного дерева. Алгоритм нахождения остовного дерева наименьшей длины.

34.Понятие базиса циклов. Алгоритм нахождение базиса циклов. Вектор-циклы. Цикломатическая матрица.

35.Составление уравнений Кирхгофа для токов и напряжений по графу электрической цепи.

36.Транспортные сети. Нахождение полного и максимального потока в транспортной сети.

37.Эйлеровы и гамильтоновы пути.

38.Понятие кодирования. Расстояние Хэмминга. Теоремы об обнаружении и распознавании ошибок.

39.Матричное кодирование. Групповые коды. Код Хэмминга.

40.Вывести формулы для нахождения числа сочетаний и размещений с повторениями и без.

41.Число разбиений. Полиномиальная формула.

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

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

1. Осипова В.А. Основы дискретной математики. -М.: ФОРУМ ИНФРА-М, 2006

2. Яблонский С.В. Введение в дискретную математику. -М.: Наука, 2006.

3. Лавров И. А. Математическая логика. -М.: Академия, 2006.

4. Новиков Ф.А. Дискретная математика для программистов: учебное пособие для вузов -М.: Питер, 2005.

5. Лавров И.А., Максимова А.Л.. Задачи по теории множеств, математической логики и теории алгоритмов. -М.: ФИЗМАТЛИТ, 2004

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

1. В.Н.Нефедов, В.А.Осипова. Курс дискретной математики. -М.: МАИ, 1993.

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

3. Методические указания к выполнению лабораторных работ по курсу "Дискретная математика". Под ред. Осиповой В.А. -М.: МАИ,1989.

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

1. Лабораторный практикум "Дискретня матемаитка".

2. Обучающая программа "Машина Тьюринга".

3. Дискретная математика. – Электронный учебник. http://www.lvf2004.com/index.html/

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

Дисплейный класс персональных компьютеров.

Лабораторный практикум по курсу «Дискретная математика».

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

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

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

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

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

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

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

Общая трудоемкость освоения дисциплины составляет 2 зачетных единиц, 72 часов. Программой дисциплины предусмотрены лекционные (34 часов), практические (16 часов), лабораторные (0 часов) занятия и (22 часов) самостоятельной работы студента. Основными целями преподавания дисциплины «Дискретная математика» являются:

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

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

• привитие студентам современной математической культуры,

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

Основными задачами преподавания дисциплины "Дискретная математика" являются:

• научить студентов использовать методы следующих разделов математики:

- алгебры множеств;

- логики высказываний;

- логики предикатов;

- теории алгоритмов;

- общей алгебры;

- комбинаторики;

- теории графов;

• применять эти методы к формированию математической модели задач дискретного характера к решению прикладных задач;

• реализовать принцип непрерывного математического образования студентов.

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

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

1. Лекции

1.1.1. Основные понятия алгебры множеств.(АЗ: 2, СРС: 0)

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

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

Описание: Понятие множеств. Основные принципы интуитивной теории множеств. Парадокс Рассела. Основные операции над множествами. Диаграмма Венна. Основные тождества алгебры множеств.

1.2.1. Отношения на множестве(АЗ: 2, СРС: 0)

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

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

Описание: Прямое произведение множеств. Бинарное отношение. Операции с бинарными отношениями. n-арное отношение. Отношение эквивалентности. Разбиение множества. Связь между отношением эквивалентности на множестве и разбиением множества.

Фактор множества.

Отношение порядка. Частный и линейный порядок. Изоформизм частично упорядоченных множеств.

Функции. Инъективные, сюръективные и биективные функции. Композиция и обращение функций. Мощность множества. Счетные множества. Несчетность континуума

1.3.1. Основные понятия логики высказываний(АЗ: 2, СРС: 0)

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

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

1.3.2. Нормальные и совершенные формы. МИнимизация в классе ДНФ(АЗ: 2, СРС: 0)

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

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

1.3.3. Исчисление высказываний(АЗ: 2, СРС: 0)

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

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

1.4.1. Логика и исчисление предикатов.(АЗ: 4, СРС: 0)

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

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

Описание: Предикаты. Кванторы. Язык логики предикатов. Формулы логики предикатов. Понятие интерпретации. Равносильность формул логики предикатов. Истинность и общезначимость формул логики предикатов.

Приведенная нормальная форма формул логики предикатов. Проблема разрешимости. Формулировка теоремы Черча. Исчисление предикатов как аксиоматическая теория. Непротиворечивость исчисления предикатов. Общезначимость выводимых формул. Формулировка Геделя о полноте исчисления предикатов.

1.5.1. Основные понятия теории графов.. Пути в графе.(АЗ: 2, СРС: 0)

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

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

Описание: Ориентированные и неориентированные графы. Основные понятия. Матричное задание графа.

1.5.2. Транспортные сети.(АЗ: 2, СРС: 0)

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

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

Описание: Транспортные сети. Основные определения. Поток по сети.

Задача о наибольшем потоке в сетях.

1.5.3. Деревья и циклы (АЗ: 2, СРС: 0)

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

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

1.5.4. Внутренние и внешние устойчивые подмножества. Ядро. (АЗ: 2, СРС: 0)

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

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

1.6.1. Элементы теории алгоритмов(АЗ: 2, СРС: 0)

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

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

1.7.1. Теория групп(АЗ: 4, СРС: 0)

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

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

Описание: Полугруппы. Моноиды. Группы. Симметрические группы.

1.7.2. Кольца и поля(АЗ: 2, СРС: 0)

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

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

Описание: Понятие кольца. Делители нуля. Поля.

1.7.3. Элементы теории кодирования(АЗ: 2, СРС: 0)

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

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

1.8.1. Комбинаторные схемы (АЗ: 2, СРС: 0)

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

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

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

1.1.1. Основные понятия алгебры множеств.(АЗ: 2, СРС: 0)

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

Описание: Методы доказательства тождеств алгебры множеств. Диаграммы Эйлера-Венна.

Решение систем теоретико-множественных уравнений