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

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)

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

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

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

1.2.1. Прямое произведение множеств. Бинарные отношения (АЗ: 2, СРС: 0)

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

Описание: Доказательство тождеств с операцией прямого произведения. Операции с бинарными отношениями.

Нахождение Области определении, множества значений бинарного отношения, обратного отношения, композиции бинарных отношений

1.2.2. Отношения порядка и эквивалентности.(АЗ: 2, СРС: 0)

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

Описание: Проверка свойств отношения.

Нахождение наибольшего, наименьшего максимальных, минимальных элементов частично упорядоченного множества. Построение линейного порядка.

Нахождение классов эквивалентности.

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

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

Описание: Высказывания. Формулы логики высказываний. Таблицы истинности. Тождественно истинные формулы. Правильные рассуждения.

1.3.2. СДНФ, СКНФ(АЗ: 2, СРС: 0)

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

Описание: Нахождение СДНФ и СКНФ заданной формулы. Многочлен Жегалкина.

1.4.1. Логика предикатов(АЗ: 2, СРС: 0)

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

Описание: Составление формул логики предикатов в заданной интерпретации. Проверка общезначимости формул. Доказательство раносильности формул.

1.5.1. Матричное задание графа(АЗ: 2, СРС: 0)

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

Описание: Нахождение матриц смежности, инцидентности, связности по изображению графа. Построение изображение графа по матрицам инцидентности и связности. Нахождение матриц связности по матрице смежности.

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

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

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

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

1.1.1. Доказательство тождеств алгебры множеств(СРС: 1)

Тип: Домашнее задание

Типовые варианты:

-Доказать тождество алгебры множеств

1.2.1. Проверка свойств бинарных отношений, нахождение области определения и значений(СРС: 1)

Тип: Домашнее задание

1.3.1. СДНФ, СКНФ(СРС: 2)

Тип: Домашнее задание

Типовые варианты:

-Для заданной формулы найти СДНФ, СКНФ

1.4.1. Привести равносильными преобразованиями к приведенной нормальной форме данную формулу логики предикатов.(СРС: 1)

Тип: Домашнее задание

1.4.2. Проверить правильность рассуждения в логике предикатов.(СРС: 2)

Тип: Домашнее задание

1.5.1. Определить для орграфа, заданного матрицей смежности: имеются ли контуры; матрицу односторонней связности; матрицу сильной связности.(СРС: 1)

Тип: Домашнее задание