Главная Другое
Экономика Финансы Маркетинг Астрономия География Туризм Биология История Информатика Культура Математика Физика Философия Химия Банк Право Военное дело Бухгалтерия Журналистика Спорт Психология Литература Музыка Медицина |
страница 1страница 2 ... страница 5страница 6 Бийский технологический институт (филиал) государственного образовательного учреждения высшего профессионального образования «Алтайский государственный технический университет им. И.И. Ползунова» Т.М. Тушкина, В.С. Фролов, О.Д. Ростова, Л.П. Кувшинова
Методические рекомендации по проведению практических занятий для студентов специальностей 080801 «Прикладная информатика в экономике», 230201 «Информационные системы и технологии» Бийск
Издательство Алтайского государственного технического университета им. И.И. Ползунова 2009
УДК 519.1 Рецензент: к.ф.-м.н., доцент кафедры МСИА БТИ АлтГТУ Пальчиков А.В. Тушкина, Т.М. Дискретная математика: методические рекомендации по прове-дению практических занятий для студентов специальностей 080801 «Прикладная информатика в экономике», 230201 «Информационные системы и технологии» / Т.М. Тушкина, В.С. Фролов, О.Д. Ростова, Л.П. Кувшинова; Алт. гос. техн. ун-т, БТИ. – Бийск: Изд-во Алт. гос. техн. ун-та, 2009. – 76 с. Данная методическая разработка является составной частью учебно-методического комплекса по дисциплине «Дискретная матема-тика» для студентов специальностей 080801 «Прикладная информатика в экономике» и 230201 «Информационные системы и технологии». В методических рекомендациях сформулированы цели и задачи прак-тических занятий по курсу «Дискретная математика», приведены тема-тика практических занятий и краткие теоретические сведения, раскры-вающие сущность изучаемых тем курса, рассмотрены решения основ-ных типов задач, даны задачи для самостоятельного решения и реко-мендации студентам по подготовке к занятиям. УДК 519.1
Рассмотрены и одобрены на заседании кафедры высшей математики и математической физики. Протокол № 6 от 02.12.08 г. © Т.М. Тушкина, В.С. Фролов, О.Д. Ростова, Л.П. Кувшинова, 2009
© БТИ АлтГТУ, 2009 1 ЦЕЛИ И ЗАДАЧИ ПРАКТИЧЕСКИХ ЗАНЯТИЙ ПО ДИСКРЕТНОЙ МАТЕМАТИКЕ Практические занятия способствуют закреплению теоретических знаний и приобретению навыков решения конкретных задач по основ-ным разделам дискретной математики: теории множеств, абстрактной алгебре, математической логике, комбинаторике, теории графов. Целью практических занятий является развитие познавательных спо-собностей, самостоятельности мышления и творческой активности студентов при изучении дисциплины «Дискретная математика». Задачами практических занятий являются:
Важность овладения методами дискретной математики переоце-нить сложно, так как современная техника переработки информации целиком основана на дискретных представлениях. 2 СОДЕРЖАНИЕ ЗАНЯТИЙ Ниже в таблице 1 представлены темы практических занятий по дисциплине «Дискретная математика». Таблица 1 – Темы практических занятий по дисциплине «Дискретная математика» Номер
темы Номер занятияТема занятияОбъем, ч123411Множества. Операции над множествами222Свойства операций над множествами233, 4Бинарные отношения. Способы задания бинарных отношений. Операции над бинарными отношениями445Свойства бинарных отношений256, 7Замыкания бинарных отношений. Отношение эквивалентности. Отношение порядка4Продолжение таблицы 1 123468Соответствия и их свойства279Операции и их свойства2810Гомоморфизмы2911Алгебры с одной бинарной операцией. Полугруппы. Моноиды. Группы21012Подгруппы. Циклические группы. Группа подстановок21113–15Алгебры с двумя бинарными операциями. Кольца. Поля. Решетки. Булевы алгебры641216–19 Комбинаторика81320Контрольная работа21421, 22Орграфы и бинарные отношения. Связность. Компоненты связности41523–25Минимальные пути в нагруженных орграфах. Эйлеровы цепи и циклы. Сети и потоки6
Элементы множества различны и отличимы друг от друга. Приняты следующие обозначения. Если a – элемент множества А, то пишут: а Множество А всех элементов, обладающих свойством Множество, не содержащее ни одного элемента, называется пустым и обозначается знаком Множество А называется подмножеством множества В ( Два множества равны тогда и только тогда, когда каждое из них является подмножеством другого, т.е. На утверждении, сформулированном выше, основан метод дока-зательства равенства двух множеств. Для того чтобы доказать, что множества А и В равны, необходимо доказать два факта: 1) 2) Мощностью ![]() ![]() Множество всех подмножеств данного множества М называется булеаном Для конечного множества М справедлив следующий факт: Если все рассматриваемые в ходе данного рассуждения множества являются элементами некоторого множества U, то множество U назы-вается универсальным для данного рассуждения или универсумом. Дополнением множества А называется множество ![]() ![]() Для более наглядного представления операций над множествами и их свойств применяют диаграммы Эйлера–Венна (рисунок 1). Каждое множество представляется множеством точек на плоскости. ![]() ![]() \ Рисунок 1 – Диаграммы Эйлера–Венна 2.1.1.1 Свойства операций над множествами:
.2`) Ассоциативность пересечения .3) Дистрибутивность объединения относительно пересечения .3`) Дистрибутивность пересечения относительно объединения
.4`) Идемпотентность пересечения .5) Свойства нуля ; 6) Свойства единицы ; .7) Свойства дополнения ; .8) Первый закон де Моргана .8`) Второй закон де Моргана .9) Первый закон поглощения .9`) Второй закон поглощения .10) Инволютивность .11) Выражение для разности .12) Выражение для дополнения .Приняты следующие обозначения для числовых множеств: N – множество натуральных чисел; Z – множество целых чисел; R – множество действительных чисел; Q – множество рациональных чисел; С – множество комплексных чисел. 2.1.2 Примеры решения задач Задача 1. Доказать и проиллюстрировать на примере множеств , , тождество алгебры множеств, выражающее закон ассоциативности операции пересечения множеств. Решение. Для доказательства тождества докажем два включения: и .
следовательно, ;
Окончательно получаем, что . Тем самым тождество доказано. Убедимся в верности равенства на примере данных множеств А, В, С. Вычислим: , ; , . Очевидно, что . Задача 2. Изобразить на координатной плоскости множества A и В точек координатной плоскости, удовлетворяющих соответственно соотношениям x2+y2 ≤1 и x2+(y-1)2 ≤1. Какие фигуры изображают множества AB, ? Решение. Оба множества представляют собой на плоскости круги с радиусами R = 1, при этом центр первого круга находится в точке с координатами (0, 0), а второй – (0, -1). Фигуры, изображающие множества А, В, AB, , представлены на рисунке 2 (закрашены темным цветом). А В AB Рисунок 2 – Решение задачи 2 (2.1.2) Задача 3. Доказать, что эквивалентны три предложения о произ-вольных множествах А, В и С: 1) ; 2) ; 3) . Решение. Докажем, что из первого предложения следует второе. Действительно, так как , то осталось показать, что . Но если , то . В самом деле, . Следовательно, . Докажем, что из второго предложения следует третье. Так как , то . По закону поглощения . Отсюда по закону коммутативности получаем . Докажем теперь, что из третьего предложения следует первое. Так как , а по условию третьего предложения , то .
X(YZ)=(XY)(XZ), X(YZ)=( XY)( XZ).
а) если и , то ; б) если и , то Ш; в) если А≠В и В≠С, то А≠С; г) если и , то В = Ш?
а) ; б) ; в) ; г) ; д) ; е) ; ж) ; з) . 21. Даны множества А, В и С такие, что . Доказать, что: а) ; б) ; в) . 22. Пусть универсум U – конечный, и число элементов в нем не превосходит размерности ЭВМ. Пронумеруем элементы U: . Пусть А – подмножество U, представим А машин-ным словом С, в котором i-й символ определяется из условия:
Аналогично можно представить любое другое подмножество U. Найти объединение, пересечение и дополнение множеств, представ-ленных машинными словами. Проиллюстрировать на примере. 23. Решить систему уравнений
при условии, что . 2.2 Практические занятия № 3–7. Бинарные отношения. Способы задания бинарных отношений. Операции над бинарными отношениями. Свойства бинарных отношений. Замыкания бинарных отношений. Отношение эквивалентности. Отношение порядка 2.2.1 Теоретические сведения и методические рекомендации по решению задач Упорядоченной парой или кортежем длины два назы-вается совокупность, состоящая из элементов х и у, стоящих в опреде-ленном порядке. Прямым (декартовым) произведением множеств А и В назы-вается множество упорядоченных пар, в котором первый эле-мент каждой пары принадлежит А, а второй принадлежит В, т.е. . Бинарным отношением из множества А во множество В назы-вается подмножество , т.е. . Областью определения бинарного отношения называется мно-жество такое у, что . Областью значений бинарного отношения называется мно-жество такое х, что . Тождественным называется отношение . Универсальным называется отношение . Обратным отношением для называется отношение . Композицией отношений и называется отношение существует такое z, что и . Пусть и . Перенумеруем элементы множества А. Матрицей отношения называется квадратная матрица порядка n, элементы которой Бинарные отношения обладают следующими свойствами. Рефлексивным называется отношение такое, что . Антирефлексивным называется отношение такое, что . Симметричным называется отношение такое, что . Антисимметричным называется отношение такое, что . Транзитивным называется отношение такое, что . Связным называется отношение такое, что или . Другими словами, или , или . Свойства бинарных отношений можно установить с помощью следующих признаков:
Пусть и – отношения на множестве А. Отношение называется замыканием относительно свойства С, если а) обладает свойством С, т.е. ; б) является надмножеством : ; в) является наименьшим: (любое , обладающее свойством С и содержащее в себе , содержит в себе также и ). Для вычисления замыканий бинарных отношений необходимо опираться на следующие факты: 1) транзитивным замыканием бинарного отношения является объединение положительных степеней 2) рефлексивным и транзитивным замыканием бинарного отно-шения является объединение неотрицательных степеней . Рефлексивное, симметричное и транзитивное отношение, задан-ное на множестве А, называется эквивалентностью на множестве А. Классом эквивалентности , порожденным элементом , называется подмножество множества А, состоящее из тех и только тех элементов у, которые состоят в отношении эквивалентности с х. Совокупность множеств , , …, называется разбиением множества А, если выполняются два условия: 1) ; 2) = Ш, , . Всякое отношение эквивалентности на множестве А определяет разбиение множества А, причем среди элементов разбиения нет пустых. Верно и обратное утверждение: всякое разбиение на множестве А, не содержащее пустых элементов, определяет отношение эквивалентности на этом множестве. Антисимметричное и транзитивное отношение, заданное на мно-жестве А, называется отношением порядка на множестве А. Порядок, обладающий свойством рефлексивности, называется нестрогим, а свойством антирефлексивности – строгим. Порядок, являющийся связным, называется полным (линейным), в противном случае порядок называется частичным. Смотрите также: Методические рекомендации по проведению практических занятий для студентов специальностей 080801 «Прикладная информатика в экономике»
1372.97kb.
6 стр.
Учебно-методический комплекс по дисциплине «Операционные системы, среды и оболочки» для студентов специальности 080801 «Прикладная информатика в экономике»
565.65kb.
3 стр.
Учебное пособие для студентов всех форм обучения специальности 080801 Прикладная информатика в экономике Разработчик
973.13kb.
13 стр.
Учебно-методический комплекс дисциплины фтд. 00 «История религий» Для специальностей : 030501 «Юриспруденция»
247.18kb.
1 стр.
Учебный план по специальности 080801. 65 «Прикладная информатика (в экономике)»
546.72kb.
4 стр.
Методическое пособие по итоговой государственной аттестации выпускников. Специальность: 080801. 65 Прикладная информатика (по областям) / Под ред проф. С. А. Курносова. Краснодар: фгоу впо кубгау, 2010. 83c
964.59kb.
13 стр.
Методические рекомендации для студентов всех специальностей и форм обучения Санкт-Петербург 2006 (076. 6)
459.61kb.
5 стр.
Рабочая программа для студентов специальности 080801. 65 «Прикладная информатика в скс»
222.27kb.
1 стр.
Методические указания для студентов по проведению практических занятий по дисциплине
503.69kb.
3 стр.
Методические указания для студентов по проведению практических занятий по дисциплине
1006.93kb.
6 стр.
Методические рекомендации по подготовке и проведению практических занятий Тематика практических занятий Тема №1 Образование множественного числа имен существительных. Грамматические категории существительного
42.18kb.
1 стр.
Методические рекомендации по составлению отчета по производственной практике «практика по профилю специальности» 131.75kb.
1 стр.
|