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

Стр 1 из 2Следующая ⇒

Методические указания

по изучению дисциплины «Дискретная математика»

для студентов заочной формы обучения

Направление подготовки

11.03.02 - Инфокоммуникационные технологии

и системы связи

Квалификация выпускника - бакалавр

Воронеж 2014

ВВЕДЕНИЕ

Дискретная математика изучает свойства объектов конечного характера (конечные множества‚ графы‚ ряд математических моделей преобразователей информации и т.д.). Основной ее особенностью является отсутствие предельного перехода к непрерывности‚ характерного для классической математики.

В качестве учебной дисциплины «Дискретная математика» играет важнейшую роль в подготовке бакалавров в рамках направления 11.03.02 - Инфокоммуникационные технологии и системы связи. Ее теоретическое и методическое значение обусловлено возрастающими требованиями к профессиональным знаниям специалиста и формированию научного понимания структуры основных законов и принципов построения современных сложных технических систем.

Задачами дисциплины являются:

- разработка навыков правильного логического рассуждения‚ выработки отчетливых формулировок‚ кратких и корректных математических предложений;

- изучение приемов и методов исследования и решения формализованных математических задач;

- моделирование объектов и процессов с целью анализа и оптимизации их параметров с использованием имеющихся средств исследований;

- выработать умения анализировать полученные результаты, обобщать и систематизировать их, проводить необходимые расчеты, используя современные технические средства.

Дисциплина относится к базовой части математического и естественнонаучного цикла.

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

- математический анализ;

- информатика.

Дисциплина обеспечивает изучение дисциплин:

- теория электрических цепей;

- электроника;

- схемотехника коммуникационных устройств;

- цифровая обработка сигналов;

- вычислительная техника и информационные технологии;

- основы построения инфокоммуникационных систем и сетей;

- устройства преобразования и обработки информации;

-цифровые устройства и микропроцессоры.

Теоретический материал должен сочетаться с его практическим применением, что более эффективно достигается при проведении практических работ с применением средств математического моделирования.

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

- использовать основные законы естественнонаучных дисциплин в профессиональной деятельности, применять методы математического анализа и моделирования, теоретического и экспериментального исследования (ОК-9);

- способностью понимать сущность и значение информации в развитии современного информационного общества, осознавать опасности и угрозы, возникающие в этом процессе, соблюдать основные требования информационной безопасности, в том числе, защиты государственной тайны; владеть основными методами, способами и средствами получения, хранения, переработки информации (ПК-1);

- иметь навыки самостоятельной работы на компьютере и в компьютерных сетях; осуществлять компьютерное моделирование устройств, систем и процессов с использованием универсальных пакетов прикладных компьютерных программ (ПК-2).

В результате изучения дисциплины обучающийся должен:

знать:

- основные понятия и методы дискретной математики (ОК-9);

- основы математического аппарата, применяемого для решения задач управления и алгоритмизации процессов обработки информации (ОК-9);

- элементы теории множеств, логические функции, графы и конечные автоматы (ОК-9, ПК-2);

- законы и методы накопления, передачи и обработки информации с помощью компьютера (ПК-1, ПК-2);

уметь:

- использовать математические методы в технических приложениях (ПК-2);

- использовать возможности вычислительной техники и программного обеспечения (ПК-1, ПК-2);

владеть:

- методами математического анализа и теории вероятностей (ОК-9);

- основными методами работы на компьютере с использованием универсальных прикладных программ (ПК-1 ПК-2);

- навыками использования основных приемов обработки экспериментальных данных, в том числе с использованием стандартного программного обеспечения (ОК-9, ПК-1, ПК-2).

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

Структурно содержание курса “Дискретная математика” делится на следующие логически взаимосвязанные разделы: математическая логика, теория множеств, комбинаторный анализ, элементы теория графов, алгоритмы и конечные автоматы.

В соответствии с программой дисциплины осуществляются следующие три вида занятий с курсантами: лекции, семинарские занятия и практические занятия.

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

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

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

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

СОДЕРЖАНИЕ УЧЕБНОЙ ДИСЦИПЛИНЫ

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

Понятие множества и элемента множества. Принадлежность. Понятие подмножества. Отношение включения. Равенство множеств. Операции над множествами: пересечение‚ объединение‚ дополнение. Классификация множеств. Мощность множества.

Используемая литература: [1, 2].

Тема 2. Отношения, отображения, функции.

Соответствия между множествами. Отображения. Виды отображений. Отношения и функции. Композиции функций. Кортежи. Декартовы произведения. Бинарные отношения и их свойства.

Используемая литература: [1, 2].

Раздел 2. Математическая логика

Тема 3. Суждения. Высказывания. Булевы функции. Формулы алгебры логики.

Элементы математической логики. Высказывания и логические операции над ними. Таблицы истинности. Формулы логики. Законы алгебры логики.

Используемая литература: [1, 2].

Тема 4. Нормальные формы. Минимизация булевых функций. Полные системы булевых функций.

Булевы функции и их канонические представления (СДНФ, СКНФ, многочлен Жегалкина). Логические схемы и Карты Карно. Основные классы булевых функций. Полнота системы булевых функций. Теорема Поста.

Используемая литература: [1, 2].

Раздел 3. Комбинаторный анализ

Тема 5. Элементы комбинаторики

Комбинаторные объекты и комбинаторные числа. Свойства комбинаторных объектов и чисел. Размещения, перестановки и сочетания. Свойства биноминальных коэффициентов.

Используемая литература: [1, 2].

Раздел 4. Элементы теории графов

Тема 6. Неориентированные и ориентированные графы

Основные понятия и определения теории графов. Смежность, инцидентность, степени. Изоморфизм, гомеоморфизм. Маршруты, пути. Плоские и планарные графы. Эйлеровы и гамильтоновы графы. Матричное задание графов. Матрицы смежности, инцидентности. Объединение и пересечение графов. Подграфы. Связность. Компоненты связности и их определение. Матрица связности. Деревья и циклы. Фундаментальные циклы и разрезы. Цикломатическое число графа. Хроматическое число графа.

Используемая литература: [1, 2].

РЕКОМЕНДУЕМАЯ ЛИТЕРАТУРА

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

1. Гончарова Г.А., Мочалин А.А. Элементы дискретной математики: Учебное пособие. - Москва: Форум-Инфра-М, 2003- 128с.

2. Спирина М.С., Спирин П.А. Дискретная математика: Учебник - Москва: Издательский центр " Академия", 2009 – 368с.

3. Яблонский С.А. Введение в дискретную математику: учебное пособие. – М., Высшая школа, 2003 – 384с.

Дополнительная литература:

4. Акимов О.Е. Дискретная математика: Логика, группы, графы - М.: Лаборатория Базовых Знаний, 2001. - 376c.

5. Гаврилов Г.П., Сапоженко А.А. Сборник задач по дискретной математике, Москва, Физматлит, 2004 - 424c.

6. Галкина В.А. Дискретная математика: комбинаторная оптимизация на графах: Учеб. пособие - М.: Гелиос АРВ, 2003. 232c.

7. Горбатов В.А., Горбатов А.В., Горбатова М.В. Дискретная математика: учеб. для вузов. - М.: АСТ: Астрель, 2006. -448с.

8. Новиков Ф.А. Дискретная математика для программистов: Учебник - СПб: Питер, 2002. 304c.

9. Редькин Н.П. Дискретная математика: Курс лекций для студентов-механиков: Учеб. пособие - СПб: Лань, 2003. - 96c.

10. Судоплатов С.В., Овчинникова Е.В. Дискретная математика: учеб. для вузов. - М.; Новосибирск: ИНФРА-М: НГТУ, 2005. – 280с. Гриф МО

11. Фомичев В.М. Дискретная математика и криптология: Курс лекций. - М. ДИАЛОГ-МИФИ, 2003. - 400c.

Способы выполнения текста

Текст документа выполняется с высотой букв не менее 2, 5 мм одним из следующих способов:

- с применением печатающих и графических устройств вывода персональных компьютеров (ПК), что предпочтительнее;

- рукописным по ГОСТ 2.304.

Форматы

Страницы документа и включенные в него иллюстрации, таблицы и распечатки с ПК должны соответствовать формату А4 по ГОСТ 9327. Допускается представлять иллюстрации, таблицы и распечатки с ПК на листах формата А3, которые должны быть сложены по размеру формата А4.

Шрифты

При использовании ПК весь текст документа должен быть набран в редакторе Word (любая версия) одинаковым шрифтом – Times New Roman. Размер шрифта в тексте 14 пунктов.

Для более наглядного восприятия элементов текста допускается использование выделения жирным и курсивом (примером этого может служить настоящий стандарт).

В рукописном варианте цифры и буквы необходимо писать четким почерком чернилами или пастой только одного цвета (черного, синего или фиолетового).

Поля

Текст следует печатать (писать), соблюдая следующие размеры полей: левое – 30 мм, правое – 10 мм, верхнее –20 мм, а нижнее – 20 мм.

Интервалы

Количество строк текста на листе должно быть не более 30, что соответствует в редакторе Word интервалу 1, 5.

Абзацы

Абзацы в тексте начинаются отступом 12, 5 мм.

Перечисления

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

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

Пример

а) ______________

б) ______________

1) ______________

2) ______________

в) ______________

Каждый пункт, подпункт и перечисление записывают с абзацного отступа.

Заголовки

Разделы, подразделы должны иметь заголовки. Пункты, как правило, заголовков не имеют.

Заголовки должны четко и кратко отражать содержание разделов, подразделов.

Заголовки следует печатать (писать) с прописной буквы без точки в конце, не подчеркивая. Переносы слов в заголовках не допускаются. Если заголовок состоит из двух предложений, их разделяют точкой. Допускается заголовки разделов писать прописными буквами.

Расстояние между заголовком и текстом должно быть 15 мм. Расстояние между заголовками раздела и подраздела – 8 мм.

Каждый раздел текстового документа рекомендуется начинать с нового листа (страницы).

Нумерация страниц

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

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

Иллюстрации и таблицы, расположенные на отдельных листах, распечатки с ПК, а также содержание, введение и заключение включают в общую нумерацию страниц.

5.11 Содержание (оглавление)

В документе большого объема (РПЗ) на первом (заглавном) листе и, при необходимости, на последующих листах помещают содержание, включающее номера и наименования разделов и подразделов с указанием номеров листов (страниц).

Слово «Содержание» записывают в виде заголовка (симметрично тексту) с прописной буквы. Наименования, включенные в содержание, записывают строчными буквами, начиная с прописной буквы. Для удобства пользования содержанием допускается проставлять на строке точки (см. содержание настоящего стандарта).

Иллюстрации

Количество иллюстраций должно быть достаточным для пояснения излагаемого текста. Иллюстрации могут быть расположены как по тексту документа (возможно ближе к соответствующим частям текста), так и в конце его. Иллюстрации должны быть выполнены в соответствии с требованиями стандартов ЕСКД и СПДС.

Иллюстрации, за исключением иллюстраций приложений, следует нумеровать арабскими цифрами сквозной нумерацией. Если рисунок один, то он обозначается «Рисунок 1».

Иллюстрации каждого приложения обозначают отдельной нумерацией арабскими цифрами с добавлением перед цифрой обозначения приложения. Например: Рисунок А.3.

Допускается нумеровать иллюстрации в пределах раздела. В этом случае номер иллюстрации состоит из номера раздела и порядкового номера иллюстрации, разделенных точкой. Например: Рисунок 1.1.

При ссылках на иллюстрации следует писать «... в соответствии с рисунком 2» при сквозной нумерации и «... в соответствии с рисунком 1.2» при нумерации в пределах раздела.

Иллюстрации, при необходимости, могут иметь наименование и пояснительные данные (подрисуночный текст). Слово «Рисунок» и наименование помещают после пояснительных данных и располагают следующим образом: Рисунок 1 – Детали прибора.

На приводимых в документе электрических схемах около каждого элемента указывают его позиционное обозначение, установленное соответствующими стандартами, и при, необходимости, номинальное значение величины.

Ссылки на литературу. Список литературы

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

Описание источников осуществляется по правилам, определяемым ГОСТ 7.1. Количество используемых источников - от 5, не старше 10 лет.

6. Контрольные вопросы к зачету

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. Метод рекурсии

Методические указания

по изучению дисциплины «Дискретная математика»

для студентов заочной формы обучения

Направление подготовки

11.03.02 - Инфокоммуникационные технологии

и системы связи

Квалификация выпускника - бакалавр

Воронеж 2014

ВВЕДЕНИЕ

Задачами дисциплины являются:

- изучение приемов и методов исследования и решения формализованных математических задач;

Дисциплина относится к базовой части математического и естественнонаучного цикла.

- математический анализ;

- информатика.

Дисциплина обеспечивает изучение дисциплин:

- теория электрических цепей;

- электроника;

- схемотехника коммуникационных устройств;

- цифровая обработка сигналов;

- вычислительная техника и информационные технологии;

- основы построения инфокоммуникационных систем и сетей;

- устройства преобразования и обработки информации;

-цифровые устройства и микропроцессоры.

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

В результате изучения дисциплины обучающийся должен:

знать:

- основные понятия и методы дискретной математики (ОК-9);

- элементы теории множеств, логические функции, графы и конечные автоматы (ОК-9, ПК-2);

- законы и методы накопления, передачи и обработки информации с помощью компьютера (ПК-1, ПК-2);

уметь:

- использовать математические методы в технических приложениях (ПК-2);

- использовать возможности вычислительной техники и программного обеспечения (ПК-1, ПК-2);

владеть:

- методами математического анализа и теории вероятностей (ОК-9);

- основными методами работы на компьютере с использованием универсальных прикладных программ (ПК-1 ПК-2);

СОДЕРЖАНИЕ УЧЕБНОЙ ДИСЦИПЛИНЫ

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

Используемая литература: [1, 2].

12 Следующая ⇒