В. П. Некрасов дискретная математика




НазваниеВ. П. Некрасов дискретная математика
страница1/12
Дата публикации03.03.2013
Размер1.02 Mb.
ТипМетодические указания
skachate.ru > Информатика > Методические указания
  1   2   3   4   5   6   7   8   9   ...   12
Федеральное агентство связи

ФГОБУ ВПО «Сибирский государственный университет

телекоммуникаций и информатики»

Уральский технический институт связи и информатики (филиал)



В.П. Некрасов


ДИСКРЕТНАЯ МАТЕМАТИКА
Методические указания по выполнению домашней контрольной работы

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

на базе среднего (полного) общего образования для направления

210700 «Инфокоммуникационные технологии и системы связи»

профили «Оптические системы и сети связи»,

«Цифровое телерадиовещание», «Сети связи и системы коммутации»,

«Многоканальные телекоммуникационные системы»,

«Инфокоммуникационные технологии в сервисах и услугах связи».

в соответствии с требованиями ФГОС ВПО 3 поколения


Квалификация (степень) выпускника «бакалавр»

Екатеринбург

2011




УДК 519.1

ББК 22.17я73
Рецензент: к.т.н., доцент кафедры информатики ГОУ ВПО «УГГУ»

Ю. С. Петров
Некрасов В. П.

Дискретная математика: Методические указания по выполнению домашней контрольной работы / В.П. Некрасов. — Екатеринбург: УрТИСИ ФГОБУ ВПО «СибГУТИ», 2011. — 50 с.
Методические указания предназначены для выполнения домашней контрольной работы (ДКР) по дисциплине «Дискретная математика».

Методические указания содержат задания по темам:

  • основы теории множеств;

  • отношения;

  • основы алгебры логики;

  • основы теории алгоритмов;

  • основы теории конечных автоматов.



Рекомендовано НМС УрТИСИ ФГОБУ ВПО СибГУТИ в качестве методических указаний по выполнению домашней контрольной работы (ДКР) студентами заочной формы обучения направления подготовки 210700 «Инфокоммуникационные технологии и системы связи, профили: «Оптические системы и сети связи», «Цифровое телерадиовещание», «Сети связи и системы коммутации», «Многоканальные телекоммуникационные системы», «Инфокоммуникационные технологии в сервисах и услугах связи».

УДК 519.1

ББК 22.17я73

Кафедра информационных систем и технологий

 УрТИСИ ФГОБУ ВПО «СибГУТИ», 2011
СОДЕРЖАНИЕ



ВВЕДЕНИЕ 5

Содержание дисциплины 6

Задание № 1 12

Задание № 2 19

Задание № 3 21

Задание № 4 24

Задание № 5 45

ВВЕДЕНИЕ



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

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

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

^

Содержание дисциплины



1. Цели и задачи дисциплины:

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

Изучение основных понятий дискретной математики, их взаимосвязей и областей практического применения формирует общий технический уровень студента, позволяющий ему эффективно решать инженерные и научно технические задачи.
^ 2. Место дисциплины в структуре ООП:

Дисциплина «Дискретная математика» относится к числу дисциплин вариативной части ООП и является дисциплиной по выбору студента для подготовки бакалавров по направлению 210700 «Инфокоммуникационные технологии и системы связи».

Дисциплина «Дискретная математика» опирается на такие дисциплины как «Математика» и «Информатика» и имеет непосредственную связь с такими дисциплинами, входящими в учебный план, как «Базы данных», «Основы построения инфокоммуникационных систем и сетей», «Программное обеспечение средств распределения сообщений», «Сети связи и системы коммутации», «Цифровые системы распределения сообщений».

Знания и умения, полученные в результате освоения материала курса «Дискретная математика», являются базой для формирования единого образовательного пространства при подготовке бакалавра по направлению «Информатика и вычислительная техника».
^ 3. Требования к результатам освоения дисциплины:

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

  • уметь логически верно, аргументировано и ясно строить устную и письменную речь (ОК-2);

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

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

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


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

Знать: основные положения теории множеств; отношения на множествах; базовые понятия математической логики; основные положения теории графов; основные виды комбинаторных алгоритмов; основы теории конечных автоматов.

Уметь: использовать математические методы в технических приложениях.

Владеть: методами математической логики, теории графов, теории алгоритмов, теории конечных автоматов.


    ^ 4. Объем дисциплины и виды учебной работы:

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


^ Виды учебной работы, формы контроля

Всего, час.

Учебные семестры

144

4

^ Аудиторные занятия

16

16

В том числе







Лекции

8

8

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

8

8

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







^ Самостоятельная работа (всего)

128

128

В том числе:







Подготовка к аудиторным занятиям (ПАЗ)







Курсовая работа (КР)







Экзамен

0

Экзамен

^ Общая трудоемкость по учебному плану

144

144

Трудоемкость в зачетных единицах

4

4


^ 5. Содержание дисциплины

5.1. Содержание разделов дисциплины

5.1.1. Элементы теории множеств

О понятии множества. Принадлежность элемента множеству. Универсум. Способы задания множеств. Свойства множеств. Равенство двух множеств. Мощность множества. Пустое множество. Конечные и бесконечные множества. Подмножества.

Теоретико - множественные операции. Интерпретация теоретико - множественных операций кругами Эйлера. Свойства операций над множествами. Изоморфизм теоретико-множественных операций и равносильностей алгебры логики. Вектор. Декартово произведение множеств.
5.1.2. Отношения

Отношения на множествах. Бинарное отношение. Определение бинарного отношения. Задание отношений. Свойства отношений. Интерпретация рефлексивности, симметричности и транзитивности с помощью теории графов. Отношение эквивалентности. Отношение порядка. Функция.

Отношение как базовое понятие в реляционных базах данных. Поле. Запись. Операции над таблицами.
^ 5.1.3 Элементы алгебры логики
Логическая переменная. Наборы значений логических переменных. Логические операции отрицание, конъюнкция, дизъюнкция, импликация, эквиваленция, сложение по модулю два. Таблицы истинности логических операций. Логические операции и линейно-контактные схемы.

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

Совершенная дизъюнктивная нормальная форма (СДНФ) логической функции. Восстановление СДНФ по таблице истинности.

Логические элементы. Логические схемы. Классический базис. Реализация логических функций в классическом базисе. Реализация операции суммирования в компьютере.

Минимизация булевых функций. Метод склеивания и поглощения. Метод минимизации по картам Карно.
^ 5.1.4. Основные понятия теории графов

Определение графа. Смежность. Инцидентность. Изоморфизм. Мультиграф. Псевдограф. Подграф. Полный граф. Двудольный граф. Планарный граф. Степень вершины. Теорема Эйлера.

Маршрут. Цепь. Простая цепь. Цикл. Простой цикл. Ориентированный граф. Полустепени исхода и захода. Ориентированный маршрут. Путь. Контур. Длина маршрута. Взвешенный граф.

Матрица смежностей. Матрица инциденций. Связный граф. Дерево. Остов. Минимальный остов.

Раскрашенный граф. Хроматическое число.
^ 5.1.5. Комбинаторные алгоритмы на графах

Интуитивное понятие алгоритма. Свойства алгоритма. Вычислительные и комбинаторные алгоритмы. Понятие жадного и эвристического алгоритмов.

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

Эвристические алгоритмы. Основные правила. Последовательный алгоритм раскраски графа в минимальное число цветов.
^ 5.1.6 Элементы теории автоматов
Элементы абстрактной теории конечных автоматов. Понятие абстрактного автомата. Автоматы Мили и Мура: законы функционирования, табличный и графический методы задания. Функционирование автоматов Мили и Мура.

Структурные автоматы. Cхемы структурных автоматов Мили и Мура. Достаточные условия для построения структурного автомата (полнота переходов, полнота выходов). Триггер типа линия задержки. Счётный триггер.

Проектирование структурных автоматов Мили и Мура.
^ 5.2 Разделы дисциплины и междисциплинарные связи

с обеспечиваемыми (последующими) дисциплинами

№ п/п

Наименование обеспечиваемых (последующих) дисциплин

№ разделов данной дисциплины, необходимых для изучения обеспечиваемых (последующих) дисциплин

5.1.1

5.1.2

5.1.3

5.1.4

5.1.5

5.1.6



Базы данных

+

+

+

+









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

+

+

+

+

+

+



Программное обеспечение средств распределения сообщений

+

+

+

+

+

+



Сети связи и системы коммутации

+

+

+

+

+

+



Цифровые системы

распределения сообщний

+

+

+











^ 5.3. Разделы дисциплин и виды занятий

№ п/п

Наименование раздела дисциплины

Лек-ции

Практ.

зан.

Семин

СРС

Всего

час.

I

Элементы теории множеств

1

1




14

16

II

Отношения

1

1




14

16

III

Элементы алгебры логики

2

3




30

35

IV

Основные понятия теории графов

1







20

21

V

Комбинаторные алгоритмы на графах

2

2




30

34

VI

Элементы теории автоматов

1

1




20

22




Итого по дисциплине

8

8




128

144


^ 6. Практические занятия (семинары)

№ п/п

№ раздела дисциплины

Тематика практических

занятий (семинаров)

Трудомкость

(час.)

1



Теоретико-множественные операции

1

2

II 

Свойства отношений

1

3

III

Вычисление логических функций по таблице истинности

1

4

III

Тождественные преобразования булевых функций

1

5

III

Реализация логических функций в элементных базисах

1

6

V

Нахождение минимального остовного дерева.

1

7

V

Раскраска графа в минимальное число цветов

1

8

VI

Функционирование конечных автоматов Мили и Мура

1


^ 7. Учебно-методическое и информационное обеспечение дисциплины

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

1. Некрасов В.П. Элементы дискретной математики: Учебное пособие. 2-е изд., перераб. и доп. — Екатеринбург: УрТИСИ ФГОБУ ВПО «СибГУТИ», 2006. — 142 с.
б) дополнительная литература

1. Некрасов В. П. Методы поиска: Учебное пособие. — Екатеринбург: УрТИСИ ФГОБУ ВПО «СибГУТИ», 2008

2. Некрасов В. П. Методы сортировки: Учебное пособие. — Екатеринбург: УрТИСИ ФГОБУ ВПО «СибГУТИ», 2007

3. Некрасов В. П. Структуры данных: Учебное пособие. — Екатеринбург: УрТИСИ ФГОБУ ВПО «СибГУТИ», 2007
^ 8. Материально-техническое обеспечение дисциплины

Компьютерный класс с подключением к сети Интернет.
9. Методические рекомендации по организации изучения дисциплины

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


  1   2   3   4   5   6   7   8   9   ...   12

Похожие:

В. П. Некрасов дискретная математика iconВ. П. Некрасов дискретная математика
Методические указания предназначены для выполнения домашней контрольной работы (дкр) по дисциплине «Дискретная математика»
В. П. Некрасов дискретная математика iconДискретная математика
Колесников А. В. Дискретная математика/ Задания и методические указания к курсовой работе для студентов специальностей 230102. 65...
В. П. Некрасов дискретная математика iconУчебно-методический комплекс по дисциплине «Дискретная математика и математическая логика»
Рабочей учебной программы по курсу «Дискретная математика и математическая логика», утверждённой деканом факультета непрерывного...
В. П. Некрасов дискретная математика iconВведение 5 1 введение в теорию множеств 6
Дискретная математика зародилась в глубокой древности и включает в себя многие разделы математики, такие как теория множеств, математическая...
В. П. Некрасов дискретная математика iconАннотация дисциплины «Дискретная математика» Целью дисциплины
Целью дисциплины является ознакомление обучающихся с основами теории графов и теории конечных автоматов. Дисциплина "Дискретная математика"...
В. П. Некрасов дискретная математика iconДискретная математика программа, методические указания и задания для контрольной работы
Методические указания предназначены для студентов второго курса заочной формы обучения по направлению «Телекоммуникации», изучающих...
В. П. Некрасов дискретная математика iconСрс по дисциплине «Дискретная математика»
Множества M, А, В, с – произвольные, множество I – универсальное (универсум),  пустое множество
В. П. Некрасов дискретная математика iconКонтрольная работа №1 По дисциплине «Дискретная математика 2»
В данном графе 4 вершины, следовательно, матрица смежности графа – это матрица A(44)
В. П. Некрасов дискретная математика iconАннотация рабочей программы учебной дисциплины "Дискретная математика"
Дисциплина учебного плана подготовки бакалавра по направлению 230100 Информатика и вычислительная техника (профиль подготовки "Автоматизированные...
В. П. Некрасов дискретная математика iconТемы курса пояснительная записка к методическим указаниям Методические...
Дисциплина «Дискретная математика» относится к вариативной части профессионального цикла основной профессиональной образовательной...

Вы можете разместить ссылку на наш сайт:
Школьные материалы


При копировании материала укажите ссылку © 2014
контакты
skachate.ru
Главная страница