Основы дискретной математики

Федеральное агентство по образованию

Новомосковский институт (филиал)

Государственного образовательного учреждения высшего профессионального образования

«Российский химико-технологический университет имени Д.И. Менделеева»

T.П. Тюрина, В.И. Емельянов

Практикум по дискретной математике

(часть 1)

Учебно-методическое пособие

Новомосковск 2007

Оглавление

Введение....................................................................................................... 5

Практическая работа № 1 Изучение методов сортировки данных........... 6

1.1 Теоретическая часть............................................................................... 6

1.2 Методы, используемые при поиске и сортировке................................ 9

1.2.1 Основные понятия............................................................................... 9

1.2.2 Поиск................................................................................................. 10

1.2.3 Оценки времени исполнения............................................................. 18

1.2.4 Сортировки....................................................................................... 19

1.3 Практическая часть.............................................................................. 40

1.3.1 Содержание отчёта по практической работе................................... 40

1.3.2 Приложение на Delphi, в котором представлена работа некоторых методов сортировки и поиска.................................................................................. 40

1.3.3 Пример выполнения.......................................................................... 51

1.3.4 Варианты заданий............................................................................. 53

1.4 Вопросы для самопроверки................................................................ 62

Практическая работа № 2 Представление множеств в компьютере........ 64

2.1 Теоретическая часть............................................................................. 64

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

2.1.2 Представление множеств и отношений в программах.................... 67

2.1.4 Представление множеств в приложениях на Delphi........................ 82

2.1.5 Характеристический вектор множества........................................... 83

2.2 Практическая часть.............................................................................. 85

2.2.1 Задание к работе............................................................................... 85

2.2.2 Примеры выполнения....................................................................... 86

2.2.3 Варианты заданий............................................................................. 90

2.3 Вопросы для самопроверки................................................................ 92

Практическая работа № 3 Элементы теории графов............................... 94

3.1 Теоретическая часть............................................................................. 94

3.2 Практическая часть............................................................................ 111

3.2.1 Задание к работе............................................................................. 111

3.2.2 Примеры выполнения..................................................................... 111

3.2.3 Вариантв заданий............................................................................ 117

Практическая работа № 4 Элементы теории множеств и алгебры логики 122

4.1 Указание к выполнению..................................................................... 122

4.2 Задание к работе................................................................................ 122

4.3 Практическая часть............................................................................ 122

4.4 Вопросы для самопроверки.............................................................. 133

Практическая работа № 5 Исследование логических функций............. 135

5.1 Задание к работе................................................................................ 135

5.2 Практическая часть............................................................................ 135

5.2.1 Пример выполнения........................................................................ 135

5.2.2 Варианты заданий........................................................................... 138

5.3 Вопросы для самопроверки.............................................................. 140

Практическая работа № 6 Изучение методов минимизации логических функций 142

6.1 Краткие теоретические сведения....................................................... 142

6.2 Практическая часть............................................................................ 144

6.2.1 Задание к работе............................................................................. 144

6.2.2 Примеры выполнения..................................................................... 144

6.3 Вопросы для самопроверки.............................................................. 147

Практическая работа № 7 Моделирование работы узлов компьютера с помощью Еxcel................................................................................................................... 149

7.1 Теоретическая часть........................................................................... 149

7.2 Практическая часть............................................................................ 152

7.2.1 Схемы сравнения кодов.................................................................. 153

7.2.2 Дешифраторы.................................................................................. 158

7.3 Задания к работе................................................................................ 160

7.4 Вопросы для самопроверки.............................................................. 164

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

Введение

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

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

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

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

Практическая работа № 1. Изучение методов сортировки данных

Цель работы: изучение наиболее известных методов сортировки данных и их использование на примерах конкретных задач.

Похожие работы

Дискретная математика

Скачать

11313

1

5

... Е и множество и мы рассматриваем все его подмножества, то множество Е называется униварсельным. Пример: Если за Е взять множество книг то его подмножества: художественные книги, книги по математике, физики, физики … Если универсальное множество состоит из n элементов, то число подмножеств = 2n. Если , состоящее из элементов E, не принадлежащих А, называется дополненным. Множество можно задать: ...

Конспект по дискретной математики

Скачать

6003

0

1

в и формальных систем является центральной в дисциплине. В настоящие время от нее возникли ответвления, например, разработка алгоритмических языков программирования.Одной из важнейших проблем в дискретной математики является проблема сложности вычислений.Теория сложности вычислений помогает оценить расход времени и памяти при решении задач на ЭВМ. Теория сложности позволяет выделить объективно ...

Решение практических заданий по дискретной математике

Скачать

14778

4

22

... которой были разработаны в последней четверти 19 века Георгом Кантором. Цель контрольной работы – ознакомится с основными понятиями и методами решения по дискретной математике, уметь применить полученные знания при решении практического задания. Задание 1 Представить с помощью кругов Эйлера множественное выражение . Используя законы и свойства алгебры множеств, упростить заданное ...

Применение методов дискретной математики в экономике

Скачать

34329

6

25

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